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 ${\mathbb{R}}^{3}$, the three-dimensional Euclidean space, and
$$R:=\{(x,y,z)\in {\mathbb{R}}^{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 {\mathbb{R}}^{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 {\mathbb{R}}^{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 {\mathbb{R}}^{3}\mid \exists r\in \mathbb{R}\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 $\mathbb{R}$, 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 {\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
${D}_{uu}$ | $=$ | $\mathrm{\{}p\in {\mathbb{R}}^{3}\mid u=u\}=\mathbb{R}{}^{3},$ | (5) | ||
${D}_{uv}$ | $=$ | ${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
${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 \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}_{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 \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\mathrm{=}\mathrm{\{}x\mathrm{,}y\mathrm{,}z\mathrm{\}}$, 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},\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.
References
- 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 Algebra^{}, 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 |