# cylindric algebra

A cylindric algebra is a quadruple $(B,V,\exists,d)$, where $B$ is a Boolean algebra, $V$ is a set whose elements we call variables, $\exists$ and $d$ are functions

 $\exists:V\to B^{B}\qquad\mbox{ and }\qquad d:V\times V\to B$

such that

1. 1.

$(B,\exists x)$ is a monadic algebra for each $x\in V$,

2. 2.

$\exists x\circ\exists y=\exists y\circ\exists x$ for any $x,y\in V$,

3. 3.

$d_{xx}=1$ for all $x\in V$,

4. 4.

for any $x,y\in V$ with $x\neq y$, and any $a\in B$, we have the equality

 $\exists x(a\wedge d_{xy})\wedge\exists x\big{(}a^{\prime}\wedge d_{xy}\big{)}=0$
5. 5.

for any $x,y,z\in V$ with $x\neq y$ and $x\neq z$, we have the equality

 $\exists x(d_{xy}\wedge d_{xz})=d_{yz}.$

where $\exists x$ and $d_{xy}$ are the abbreviations for $\exists(x)$ and $d(x,y)$ respectively.

Basically, the first two conditions say that the $(B,V,\exists)$ portion of the cylindric algebra is very similar 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 proposition $a$ and its complement $a^{\prime}$, 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$:

• (symmetric property) $d_{xy}=d_{yx}$

• (transitive property) $d_{xy}\wedge d_{yz}\leq d_{xz}$

• $\exists x(d_{xy})=1$

• $\exists x(d_{yz})=d_{yz}$ provided that $x\notin\{y,z\}$

• if $x\neq y$, then

1. (a)

$\exists x(d_{xy}\wedge a^{\prime})=(\exists x(d_{xy}\wedge a))^{\prime}$,

2. (b)

$d_{xy}\wedge a=d_{xy}\wedge\exists x(a\wedge d_{xy})$.

Remarks

1. 1.

The dimension of a cylindric algebra $(B,V,\exists,d)$ is the cardinality of $V$.

2. 2.

From the definition above, a cylindric algebra is a two-sorted structure, with $B$ and $V$ as the two distinct universes. 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 $\exists x$ as a unary operator on $B$, and each $d_{xy}$ as a constant in $B$. As a result, the cylindric algebra $(B,V,\exists,d)$ becomes a Boolean algebra with possibly infinitely many operators:

 $(B,\exists x,d_{xy})_{x,y\in V}.$
3. 3.

Let $L$ be a the language of a first order logic, and $S$ a set of sentences in $L$. Define $\equiv$ on $L$ so that

 $\varphi\equiv\psi\quad\mbox{ iff }\quad S\vdash(\varphi\leftrightarrow\psi).$

Then $\equiv$ is an equivalence relation on $L$. For each formula $\varphi\in L$, let $[\varphi]$ be the equivalence class containing $\varphi$. Let $V$ be a countably infinite set of variables available to $L$. Now, define operations $\vee,\wedge,^{\prime},\exists x,d_{xy}$ as follows:

 $\displaystyle[\varphi]\vee[\psi]$ $\displaystyle:=$ $\displaystyle[\varphi\vee\psi],$ (1) $\displaystyle\left[\varphi\right]\wedge[\psi]$ $\displaystyle:=$ $\displaystyle[\varphi\wedge\psi],$ (2) $\displaystyle\left[\varphi\right]^{\prime}$ $\displaystyle:=$ $\displaystyle[\neg\varphi],$ (3) $\displaystyle 0$ $\displaystyle:=$ $\displaystyle[\neg x=x],$ (4) $\displaystyle 1$ $\displaystyle:=$ $\displaystyle[x=x],$ (5) $\displaystyle\exists x[\varphi]$ $\displaystyle:=$ $\displaystyle[\exists x\varphi],$ (6) $\displaystyle d_{xy}$ $\displaystyle:=$ $\displaystyle[x=y].$ (7)

Then it can be shown that $(L/\equiv,V,\exists,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.

## References

• 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 Algebra, Algebraic Logic, and Databases, Kluwer Academic Publishers (1994).
Title cylindric algebra CylindricAlgebra 2013-03-22 17:51:21 2013-03-22 17:51:21 CWoo (3771) CWoo (3771) 10 CWoo (3771) Definition msc 03G15 msc 06E25 PolyadicAlgebra PolyadicAlgebraWithEquality