example of cylindric algebra

Example 1.

Consider $\mathbb{R}^{3}$, the three-dimensional Euclidean space, and

 $R:=\{(x,y,z)\in\mathbb{R}^{3}\mid x^{2}+y^{2}+z^{2}\leq 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\mathbb{R}^{2}\mid x^{2}+y^{2}\leq 1\}.$
 $C_{z}(R):=p_{z}^{-1}p_{z}(R)=\{(x,y,z)\in\mathbb{R}^{3}\mid x^{2}+y^{2}\leq 1\}.$

$C_{z}(R)$ has the following properties:

 $\displaystyle R$ $\displaystyle\subseteq$ $\displaystyle C_{z}(R).$ (1)

Furthermore, it can be characterized as follows

 $C_{z}(R)=\{(x,y,z)\in\mathbb{R}^{3}\mid\exists r\in\mathbb{R}\mbox{ 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 $\mathbb{R}$, with respect to any of the three variables $x,y,z$. We have in addition  to (1) above the following properties:

 $\displaystyle C_{u}(\varnothing)$ $\displaystyle=$ $\displaystyle\varnothing,$ (2) $\displaystyle C_{u}(R\cap C_{u}(S))$ $\displaystyle=$ $\displaystyle C_{u}(R)\cap C_{u}(S),$ (3) $\displaystyle C_{u}(C_{v}(R))$ $\displaystyle=$ $\displaystyle C_{v}(C_{u}(R)),$ (4)

where $u,v\in\{x,y,z\}$ and $R,S\subseteq\mathbb{R}^{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\mathbb{R}$ such that $(a,b,r)\in R$ and $(a,b,r)\in C_{z}(S)$, which means there is an $s\in\mathbb{R}$ 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\mathbb{R}$ 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\mathbb{R}$ such that $(r,b,c)\in C_{y}(R)$, and so there is an $s\in\mathbb{R}$ 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\mathbb{R}^{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

 $\displaystyle D_{uu}$ $\displaystyle=$ $\displaystyle\{p\in\mathbb{R}^{3}\mid u=u\}=\mathbb{R}^{3},$ (5) $\displaystyle D_{uv}$ $\displaystyle=$ $\displaystyle D_{vu},$ (6)

where $u,v\in\{x,y,z\}$. For any subset $R\subseteq\mathbb{R}^{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 $\mathbb{R}^{3}$, and the diagonal sets as constants (nullary operations  ) on $\mathbb{R}^{3}$. Two additional noteworthy properties are

 $\displaystyle C_{u}(R_{uv})\cap C_{u}(R^{\prime}_{uv})=\varnothing$ if $\displaystyle u\neq v,$ (7) $\displaystyle C_{u}(D_{uv}\cap D_{uw})=D_{vw}$ if $\displaystyle 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^{\prime}_{xy})$. Then there is $r\in\mathbb{R}$ 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\mathbb{R}$ such that $(s,b,c)\in R^{\prime}_{xy}$, 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\mathbb{R}$ 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 $\mathbb{R}^{3}$ is just a ternary relation  on $\mathbb{R}$, and the collection  of all ternary relations on $R$ is just $P(\mathbb{R}^{3})$.

Proposition 1.

$P(\mathbb{R}^{3})$ is a Boolean algebra  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.

Proof.

Write $A=P(\mathbb{R}^{3})$. It is easy to see that $A$ is a Boolean algebra with operations $\cup,\cap,^{\prime},\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\mbox{ such that }r(y)=p(y)\mbox{ for % any }y\neq 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.

References

Title example of cylindric algebra ExampleOfCylindricAlgebra 2013-03-22 17:52:26 2013-03-22 17:52:26 CWoo (3771) CWoo (3771) 10 CWoo (3771) Example msc 03G15 cylindrification cylindric set algebra