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\mathit{\hspace{1em}\hspace{1em}}\text{ and }\mathit{\hspace{1em}\hspace{1em}}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\left(a^{\prime }\wedge d_{xy}\right)=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}.$$

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}\le d_{xz}$

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

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

• if $x\ne y$, then

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

  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

   $$\phi \equiv \psi \mathit{\hspace{1em}}\text{ iff }\mathit{\hspace{1em}}S⊢(\phi \leftrightarrow \psi ).$$

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

   $[\phi ]\vee [\psi ]$$:=$$[\phi \vee \psi ],$(1)

   $\left[\phi \right]\wedge [\psi ]$$:=$$[\phi \wedge \psi ],$(2)

   ${\left[\phi \right]}^{\prime }$$:=$$[\mathrm{\neg }\phi ],$(3)

   $0$$:=$$[\mathrm{\neg }x=x],$(4)

   $1$$:=$$[x=x],$(5)

   $\exists x[\phi ]$$:=$$[\exists x\phi ],$(6)

   $d_{xy}$$:=$$[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.