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

  5. 5.

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


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)


    2. (b)



  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:

  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.


  • 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