cylindric algebra


A cylindric algebra is a quadruple (B,V,,d), where B is a Boolean algebraMathworldPlanetmath, V is a set whose elements we call variables, and d are functions

:VBB   and   d:V×VB

such that

  1. 1.

    (B,x) is a monadic algebra for each xV,

  2. 2.

    xy=yx for any x,yV,

  3. 3.

    dxx=1 for all xV,

  4. 4.

    for any x,yV with xy, and any aB, we have the equality

    x(adxy)x(adxy)=0
  5. 5.

    for any x,y,zV with xy and xz, we have the equality

    x(dxydxz)=dyz.

where x and dxy are the abbreviations for (x) and d(x,y) respectively.

Basically, the first two conditions say that the (B,V,) portion of the cylindric algebra is very similarMathworldPlanetmathPlanetmath to a quantifier algebra, except the domain is no longer the subsets of V, but the elements of V instead. The function d is the algebraic abstraction of equality. Condition 3 says that x=x is always true, condition 4 says that the propositionPlanetmathPlanetmath a and its complementMathworldPlanetmathPlanetmath a, where any occurrences of the variable x are replaced by the variable y, distinct from x, is always false, while condition 5 says y=z iff there is an x such that x=y and x=z.

Below are some elementary properties of d:

  • (symmetricMathworldPlanetmathPlanetmathPlanetmath property) dxy=dyx

  • (transitive property) dxydyzdxz

  • x(dxy)=1

  • x(dyz)=dyz provided that x{y,z}

  • if xy, then

    1. (a)

      x(dxya)=(x(dxya)),

    2. (b)

      dxya=dxyx(adxy).

Remarks

  1. 1.

    The dimension of a cylindric algebra (B,V,,d) is the cardinality of V.

  2. 2.

    From the definition above, a cylindric algebra is a two-sorted structureMathworldPlanetmath, with B and V as the two distinct universesPlanetmathPlanetmath. However, it is often useful to view a cylindric algebra as a one-sorted structure. The way to do this is to dispense with V and identify each x as a unary operator on B, and each dxy as a constant in B. As a result, the cylindric algebra (B,V,,d) becomes a Boolean algebra with possibly infinitely many operators:

    (B,x,dxy)x,yV.
  3. 3.

    Let L be a the languagePlanetmathPlanetmath of a first order logic, and S a set of sentencesMathworldPlanetmath in L. Define on L so that

    φψ iff S(φψ).

    Then is an equivalence relationMathworldPlanetmath on L. For each formulaMathworldPlanetmath φL, let [φ] be the equivalence classMathworldPlanetmath containing φ. Let V be a countably infiniteMathworldPlanetmath set of variables available to L. Now, define operationsMathworldPlanetmath ,,,x,dxy as follows:

    [φ][ψ] := [φψ], (1)
    [φ][ψ] := [φψ], (2)
    [φ] := [¬φ], (3)
    0 := [¬x=x], (4)
    1 := [x=x], (5)
    x[φ] := [xφ], (6)
    dxy := [x=y]. (7)

    Then it can be shown that (L/,V,,d) is a cylindric algebra. Thus a cylindric algebra can be thought of as an “algebraization” of first order logic (with equality), much the same way as a Boolean algebra (Lindenbaum-Tarski algebra) as the algebraic counterpart of propositional logic.

References

  • 1 P. Halmos, Algebraic Logic, Chelsea Publishing Co. New York (1962).
  • 2 L. Henkin, J. D. Monk, A. Tarski, Cylindric Algebras, Part I., North-Holland, Amsterdam (1971).
  • 3 J. D. Monk, Mathematical Logic, Springer, New York (1976).
  • 4 B. Plotkin, Universal AlgebraMathworldPlanetmathPlanetmath, Algebraic Logic, and Databases, Kluwer Academic Publishers (1994).
Title cylindric algebra
Canonical name CylindricAlgebra
Date of creation 2013-03-22 17:51:21
Last modified on 2013-03-22 17:51:21
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 10
Author CWoo (3771)
Entry type Definition
Classification msc 03G15
Classification msc 06E25
Related topic PolyadicAlgebra
Related topic PolyadicAlgebraWithEquality