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 algebra is termed cylindric.

Example 1.

Consider ${ℝ}^3$, the three-dimensional Euclidean space, and

$$R:=\{(x,y,z)\in {ℝ}^3\mid x^2+y^2+z^2\le 1\}.$$

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

$$p_z(R)=\{(x,y)\in {ℝ}^2\mid x^2+y^2\le 1\}.$$

Taking its preimage, we get a cylinder

$$C_z(R):=p_z^{-1}{p}_z(R)=\{(x,y,z)\in {ℝ}^3\mid x^2+y^2\le 1\}.$$

$C_z(R)$ has the following properties:

$R$ $\subseteq$ $C_z(R).$ (1)

Furthermore, it can be characterized as follows

$$C_z(R)=\{(x,y,z)\in {ℝ}^3\mid \exists r\in ℝ\text{ such that }(x,y,r)\in R\}.$$

$C_z(R)$ is called the cylindrification of $R$ with respect to the variable $z$. It is easy to see that the characterization 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 addition to (1) above the following properties:

$C_u(\mathrm{\varnothing })$ $=$ $\mathrm{\varnothing },$ (2)

$C_u(R\cap C_u(S))$ $=$ $C_u(R)\cap C_u(S),$ (3)

$C_u(C_v(R))$ $=$ $C_v(C_u(R)),$ (4)

where $u,v\in \{x,y,z\}$ and $R,S\subseteq {ℝ}^3$.

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)\in C_z(R\cap C_z(S))$. Then there is an $r\in ℝ$ such that $(a,b,r)\in R$ and $(a,b,r)\in C_z(S)$, which means there is an $s\in ℝ$ such that $(a,b,s)\in S$. Since $(a,b,r)\in R$, we have that $(a,b,c)\in C_z(R)$, and since $(a,b,s)\in S$, we have that $(a,b,c)\in C_z(S)$ as well. This shows one inclusion. Now let $(a,b,c)\in C_z(R)\cap C_z(S)$, then there is an $r\in ℝ$ such that $(a,b,r)\in R$. But $(a,b,r)\in C_z(S)$ also, so $(a,b,c)\in C_z(R\cap C_z(S))$. To see Property (4), it is enough to assume $u=x$ and $v=y$. Let $(a,b,c)\in C_x(C_y(R))$. Then there is an $r\in ℝ$ such that $(r,b,c)\in C_y(R)$, and so there is an $s\in ℝ$ such that $(r,s,c)\in R$. This implies that $(a,s,c)\in C_x(R)$, which implies that $(a,b,c)\in C_y(C_x(R))$. So $C_x(C_y(R))\subseteq C_y(C_x(R))$. The other inclusion then follows immediately.

Next, we define the diagonal set

$$D_{xy}:=\{(x,y,z)\in {ℝ}^3\mid x=y\}$$

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 $D_{vw}$ where $v,w\in \{x,y,z\}$. However, there are in fact four distinct diagonal sets, since

$D_{uu}$ $=$ $\mathrm{\{}p\in {ℝ}^3\mid u=u\}=ℝ{}^3,$ (5)

$D_{uv}$ $=$ $D_{vu},$ (6)

where $u,v\in \{x,y,z\}$. For any subset $R\subseteq {ℝ}^3$, set $R_{uv}:=R\cap D_{uv}$. For instance, $R_{xy}=\{(a,b,c)\in R\mid a=b\}$.

We may consider $C_x,C_y,C_z$ as unary operations on ${ℝ}^3$, and the diagonal sets as constants (nullary operations) on ${ℝ}^3$. Two additional noteworthy properties are

$C_u(R_{uv})\cap C_u(R_{uv}^{\prime })=\mathrm{\varnothing }$ if $u\ne v,$ (7)

$C_u(D_{uv}\cap D_{uw})=D_{vw}$ if $u\notin \{v,w\},$ (8)

where $u,v,w\in \{x,y,z\}$.

To see Property (7), we may assume $u=x$ and $v=y$. Suppose $(a,b,c)\in C_x(R_{xy})\cap C_x(R_{xy}^{\prime })$. Then there is $r\in ℝ$ such that $(r,b,c)\in R_{xy}$, which implies that $r=b$, or that $(b,b,c)\in R$. On the other hand, there is $s\in ℝ$ such that $(s,b,c)\in R_{xy}^{\prime }$, which implies $s=b$, or that $(b,b,c)\in R^{\prime }$, a contradiction. To see Property (8), we may assume $u=x,v=w,w=z$. If $(a,b,c)\in C_x(D_{xy}\cap D_{xz})$, then there is $r\in ℝ$ such that $(r,b,c)\in D_{xy}\cap D_{xz}$. So $r=b$ and $r=c$. Therefore, $(a,b,c)=(a,r,r)\in D_{yz}$. On the other hand, for any $(a,r,r)\in D_{yz}$, $(r,r,r)\in D_{xy}\cap D_{xz}$, and so $(a,r,r)\in C_x(D_{xy}\cap D_{xz})$ as well.

Finally, we note that a subset of ${ℝ}^3$ is just a ternary relation on $ℝ$, and the collection of all ternary relations on $R$ is just $P({ℝ}^3)$.

Proposition 1.

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

Proof.

Write $A=P({ℝ}^3)$. It is easy to see that $A$ is a Boolean algebra with operations $\cup ,\cap {,}^{\prime },\mathrm{\varnothing }$. Next define $\exists :V\to A^A$ by $\exists v:=C_v$ where $v\in \{x,y,z\}$, and $d:V\times V\to A$ by $d_{xy}:=D_{xy}$. Then Properties (1), (2), and (3) show that $(A,{\exists }_v)$ is a monadic algebra, and Properties (4), (5), (7), and (8) show that $(A,V,\exists ,d)$ is cylindric. ∎

Example 2 (Cylindric Set Algebras).

Example 1 above may be generalized. Let $A,V$ be sets, and set $B=P(A^V)$. For any subset $R\subseteq B$ and any $x,y\in V$, define the cylindrification of $R$ by

$$C_x(R):=\{p\in A^V\mid \exists r\in R\text{ such that }r(y)=p(y)\text{ for any }y\ne x\},$$

and the diagonal set by

$$D_{xy}=\{p\in A^V\mid p(x)=p(y)\}.$$

Now, define $\exists :V\to B^B$ and $d:V\times V\to B$ by $\exists x=C_x$ and $d_{xy}=D_{xy}$.

Proposition 2.

$(B,V,\exists ,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.

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