example of cylindric algebra

In this example, we give two examples of a cylindric algebra, in which the first is a special case of the second. The first example also explains why the algebraMathworldPlanetmathPlanetmath is termed cylindric.

Example 1.

Consider 3, the three-dimensional Euclidean space, and


Thus R is the closed unit ball, centered at the origin (0,0,0). Project R onto the x-y plane, so its image is


Taking its preimageMathworldPlanetmath, we get a cylinder


Cz(R) has the following properties:

R Cz(R). (1)

Furthermore, it can be characterized as follows

Cz(R)={(x,y,z)3r such that (x,y,r)R}.

Cz(R) is called the cylindrification of R with respect to the variableMathworldPlanetmath z. It is easy to see that the characterizationMathworldPlanetmath above permits us to generalize the notion of cylindrification to any subset of , with respect to any of the three variables x,y,z. We have in additionPlanetmathPlanetmath to (1) above the following properties:

Cu() = , (2)
Cu(RCu(S)) = Cu(R)Cu(S), (3)
Cu(Cv(R)) = Cv(Cu(R)), (4)

where u,v{x,y,z} and R,S3.

Property (2) is obvious. To see Property (3), it is enough to assume u=z (for the other cases follow similarly). First let (a,b,c)Cz(RCz(S)). Then there is an r such that (a,b,r)R and (a,b,r)Cz(S), which means there is an s such that (a,b,s)S. Since (a,b,r)R, we have that (a,b,c)Cz(R), and since (a,b,s)S, we have that (a,b,c)Cz(S) as well. This shows one inclusion. Now let (a,b,c)Cz(R)Cz(S), then there is an r such that (a,b,r)R. But (a,b,r)Cz(S) also, so (a,b,c)Cz(RCz(S)). To see Property (4), it is enough to assume u=x and v=y. Let (a,b,c)Cx(Cy(R)). Then there is an r such that (r,b,c)Cy(R), and so there is an s such that (r,s,c)R. This implies that (a,s,c)Cx(R), which implies that (a,b,c)Cy(Cx(R)). So Cx(Cy(R))Cy(Cx(R)). The other inclusion then follows immediately.

Next, we define the diagonal set


with respect to x and y. This is just the plane whose projection onto the x-y plane is the line x=y. We may define a total of nine possible diagonal sets Dvw where v,w{x,y,z}. However, there are in fact four distinct diagonal sets, since

Duu = {p3u=u}=3, (5)
Duv = Dvu, (6)

where u,v{x,y,z}. For any subset R3, set Ruv:=RDuv. For instance, Rxy={(a,b,c)Ra=b}.

We may consider Cx,Cy,Cz as unary operations on 3, and the diagonal sets as constants (nullary operationsMathworldPlanetmath) on 3. Two additional noteworthy properties are

Cu(Ruv)Cu(Ruv)= if uv, (7)
Cu(DuvDuw)=Dvw if u{v,w}, (8)

where u,v,w{x,y,z}.

To see Property (7), we may assume u=x and v=y. Suppose (a,b,c)Cx(Rxy)Cx(Rxy). Then there is r such that (r,b,c)Rxy, which implies that r=b, or that (b,b,c)R. On the other hand, there is s such that (s,b,c)Rxy, which implies s=b, or that (b,b,c)R, a contradictionMathworldPlanetmathPlanetmath. To see Property (8), we may assume u=x,v=w,w=z. If (a,b,c)Cx(DxyDxz), then there is r such that (r,b,c)DxyDxz. So r=b and r=c. Therefore, (a,b,c)=(a,r,r)Dyz. On the other hand, for any (a,r,r)Dyz, (r,r,r)DxyDxz, and so (a,r,r)Cx(DxyDxz) as well.

Finally, we note that a subset of 3 is just a ternary relationPlanetmathPlanetmath on , and the collectionMathworldPlanetmath of all ternary relations on R is just P(3).

Proposition 1.

P(3) is a Boolean algebraMathworldPlanetmath with the usual set-theoretic operations, and together with cylindrification operators and the diagonal sets, on the set V={x,y,z}, is a cylindric algebra.


Write A=P(3). It is easy to see that A is a Boolean algebra with operations ,,,. Next define :VAA by v:=Cv where v{x,y,z}, and d:V×VA by dxy:=Dxy. Then Properties (1), (2), and (3) show that (A,v) is a monadic algebra, and Properties (4), (5), (7), and (8) show that (A,V,,d) is cylindric. ∎

Example 2 (Cylindric Set Algebras).

Example 1 above may be generalized. Let A,V be sets, and set B=P(AV). For any subset RB and any x,yV, define the cylindrification of R by

Cx(R):={pAVrR such that r(y)=p(y) for any yx},

and the diagonal set by


Now, define :VBB and d:V×VB by x=Cx and dxy=Dxy.

Proposition 2.

(B,V,,d) is a cylindric algebra, called a cylindric set algebra.

The proof of this can be easily derived based on the discussion in Example 1, and is left for the reader as an exercise.

Remark. For more examples of cylindric algebras, see the second reference below.


  • 1 L. Henkin, J. D. Monk, A. Tarski, Cylindric Algebras, Part I., North-Holland, Amsterdam (1971).
  • 2 J. D. Monk, Connections Between Combinatorial Theory and Algebraic Logic, Studies in Algebraic Logic, The Mathematical Association of America, (1974).
  • 3 J. D. Monk, Mathematical Logic, Springer, New York (1976).
  • 4 B. Plotkin, Universal AlgebraMathworldPlanetmathPlanetmath, Algebraic Logic, and Databases, Kluwer Academic Publishers (1994).
Title example of cylindric algebra
Canonical name ExampleOfCylindricAlgebra
Date of creation 2013-03-22 17:52:26
Last modified on 2013-03-22 17:52:26
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 10
Author CWoo (3771)
Entry type Example
Classification msc 03G15
Defines cylindrification
Defines cylindric set algebra