polyadic algebra with equality


Let A=(B,V,,S) be a polyadic algebra. An equality predicate on A is a function E:V×VB such that

  1. 1.

    S(f)E(x,y)=E(f(x),f(y)) for any f:VV and any x,yV

  2. 2.

    E(x,x)=1 for every xV, and

  3. 3.

    E(x,y)aS(x/y)a, where aB, and (x/y) denotes the function VV that maps x to y, and constant everywhere else.

Heuristically, we can interpret the conditions above as follows:

  1. 1.

    if x=y and if we replace x by, say x1, and y by y1, then x1=y1.

  2. 2.

    x=x for every variableMathworldPlanetmath x

  3. 3.

    if we have a propositional function a that is true, and x=y, then the propositionPlanetmathPlanetmathPlanetmath obtained from a by replacing all occurrences of x by y is also true.

The second condition is also known as the reflexive property of the equality predicate E, and the third is known as the substitutive property of E

A polyadic algebra with equality is a pair (A,E) where A is a polyadic algebra and E is an equality predicate on A. Paul Halmos introduced this concept and called this simply an equality algebra.

Below are some basic properties of the equality predicate E in an equality algebra (A,E):

  • (symmetric property) E(x,y)E(y,x)

  • (transitive property) E(x,y)E(y,z)E(x,z)

  • E(x,y)a=E(x,y)S(x,y)a, where (x,y) in the S is the transposition on V that swaps x and y and leaves everything else fixed.

  • if a variable xV is not in the supportMathworldPlanetmathPlanetmathPlanetmath of aA, then a=(x)(E(x,y)S(y/x)a).

  • (x)(E(x,y)a)(x)(E(x,y)a)=0 for all aA and all x,yV whenever xy.

  • (x)(E(x,y)E(x,z))=E(y,z) for all x,y,zV where x{y,z}.

Remarks

  • The degree and local finiteness of a polyadic algebra (A,E) are defined as the degree and the local finiteness and degree of its underlying polyadic algebra A.

  • It can be shown that every locally finitePlanetmathPlanetmathPlanetmath polyadic algebra of infiniteMathworldPlanetmath degree can be embedded (as a polyadic subalgebraMathworldPlanetmathPlanetmathPlanetmath) in a locally finite polyadic algebra with equality of infinite degree.

  • Like cylindric algebras, polyadic algebras with equality is an attempt at “converting” a first order logic (with equality) into algebraic form, so that the logic can be studied using algebraic means.

References

  • 1 P. Halmos, Algebraic Logic, Chelsea Publishing Co. New York (1962).
  • 2 B. Plotkin, Universal AlgebraMathworldPlanetmathPlanetmath, Algebraic Logic, and Databases, Kluwer Academic Publishers (1994).
Title polyadic algebra with equality
Canonical name PolyadicAlgebraWithEquality
Date of creation 2013-03-22 17:51:37
Last modified on 2013-03-22 17:51:37
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 10
Author CWoo (3771)
Entry type Definition
Classification msc 03G15
Synonym equality algebra
Related topic CylindricAlgebra
Defines equality predicate
Defines substitutive
Defines reflexiveMathworldPlanetmathPlanetmath
Defines symmetric
Defines transitiveMathworldPlanetmathPlanetmathPlanetmath