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. $(B,\exists x)$ is a monadic algebra for each $x\in V$ ,
2. $\exists x\circ \exists y = \exists y\circ \exists x$ for any $x,y\in V$ ,
3. $d_{xx}=1$ for all $x\in V$ ,
4. for any $x,y\in V$ with $x\ne y$ , and any $a \in B$ , we have the equality $$\exists x(a\wedge d_{xy})\wedge \exists x\big(a'\wedge d_{xy}\big)=0$$
5. for any $x,y,z\in V$ with $x\ne y$ and $x\ne z$ , we have the equality $$\exists x (d_{xy}\wedge d_{xz})=d_{yz}.$$

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'$ , 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}\le d_{xz}$
• $\exists x(d_{xy})=1$
• $\exists x(d_{yz})=d_{yz}$ provided that $x\notin \lbrace y,z\rbrace$
• if $x\ne y$ , then
  1. $\exists x(d_{xy}\wedge a')= (\exists x(d_{xy}\wedge a))'$ ,
  2. $d_{xy} \wedge a =d_{xy} \wedge \exists x(a\wedge d_{xy})$ .

Remarks

1. The dimension of a cylindric algebra $(B,V,\exists,d)$ is the cardinality of $V$ .
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. 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,',\exists x,d_{xy}$ as follows:
   \begin{eqnarray} [\varphi] \vee [\psi] &:=& [\varphi \vee \psi], \\ \left[ \varphi \right] \wedge [\psi] &:=& [\varphi \wedge \psi], \\ \left[ \varphi \right]' &:=& [\neg \varphi], \\ 0 &:=& [\neg x=x], \\ 1 &:=& [x=x], \\ \exists x[\varphi] &:=& [\exists x \varphi], \\ d_{xy} &:=& [x=y]. \end{eqnarray}
   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.

Bibliography

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).