# Cylindric algebra

The notion of cylindric algebra, invented by Alfred Tarski, arises naturally in the algebraization of equational first-order logic. This is comparable to the role Boolean algebras play for propositional logic. Indeed, cylindric algebras are Boolean algebras equipped with additional cylindrification operations that model quantification and equality. They differ from polyadic algebras in that the latter do not model equality.

## Definition of a cylindric algebra

A cylindric algebra of dimension ${\displaystyle \alpha }$ (where ${\displaystyle \alpha }$ is any ordinal number) is an algebraic structure ${\displaystyle (A,+,\cdot ,-,0,1,c_{\kappa },d_{\kappa \lambda })_{\kappa ,\lambda <\alpha }}$ such that ${\displaystyle (A,+,\cdot ,-,0,1)}$ is a Boolean algebra, ${\displaystyle c_{\kappa }}$ a unary operator on ${\displaystyle A}$ for every ${\displaystyle \kappa }$ (called a cylindrification), and ${\displaystyle d_{\kappa \lambda }}$ a distinguished element of ${\displaystyle A}$ for every ${\displaystyle \kappa }$ and ${\displaystyle \lambda }$ (called a diagonal), such that the following hold:

(C1) ${\displaystyle c_{\kappa }0=0}$

(C2) ${\displaystyle x\leq c_{\kappa }x}$

(C3) ${\displaystyle c_{\kappa }(x\cdot c_{\kappa }y)=c_{\kappa }x\cdot c_{\kappa }y}$

(C4) ${\displaystyle c_{\kappa }c_{\lambda }x=c_{\lambda }c_{\kappa }x}$

(C5) ${\displaystyle d_{\kappa \kappa }=1}$

(C6) If ${\displaystyle \kappa \notin \{\lambda ,\mu \}}$, then ${\displaystyle d_{\lambda \mu }=c_{\kappa }(d_{\lambda \kappa }\cdot d_{\kappa \mu })}$

(C7) If ${\displaystyle \kappa \neq \lambda }$, then ${\displaystyle c_{\kappa }(d_{\kappa \lambda }\cdot x)\cdot c_{\kappa }(d_{\kappa \lambda }\cdot -x)=0}$

Assuming a presentation of first-order logic without function symbols, the operator ${\displaystyle c_{\kappa }x}$ models existential quantification over variable ${\displaystyle \kappa }$ in formula ${\displaystyle x}$ while the operator ${\displaystyle d_{\kappa \lambda }}$ models the equality of variables ${\displaystyle \kappa }$ and ${\displaystyle \lambda }$. Henceforth, reformulated using standard logical notations, the axioms read as

(C1) ${\displaystyle \exists \kappa .{\mathit {false}}\Leftrightarrow {\mathit {false}}}$

(C2) ${\displaystyle x\Rightarrow \exists \kappa .x}$

(C3) ${\displaystyle \exists \kappa .(x\wedge \exists \kappa .y)\Leftrightarrow (\exists \kappa .x)\wedge (\exists \kappa .y)}$

(C4) ${\displaystyle \exists \kappa \exists \lambda .x\Leftrightarrow \exists \lambda \exists \kappa .x}$

(C5) ${\displaystyle \kappa =\kappa \Leftrightarrow {\mathit {true}}}$

(C6) If ${\displaystyle \kappa }$ is a variable different from both ${\displaystyle \lambda }$ and ${\displaystyle \mu }$, then ${\displaystyle \lambda =\mu \Leftrightarrow \exists \kappa .(\lambda =\kappa \wedge \kappa =\mu )}$

(C7) If ${\displaystyle \kappa }$ and ${\displaystyle \lambda }$ are different variables, then ${\displaystyle \exists \kappa .(\kappa =\lambda \wedge x)\wedge \exists \kappa .(\kappa =\lambda \wedge \neg x)\Leftrightarrow {\mathit {false}}}$

## Cylindric set algebras

A cylindric set algebra of dimension ${\displaystyle \alpha }$ is an algebraic structure ${\displaystyle (A,\cup ,\cap ,-,\emptyset ,X^{\alpha },c_{\kappa },d_{\kappa \lambda })_{\kappa ,\lambda <\alpha }}$ such that ${\displaystyle \langle X^{\alpha },A\rangle }$ is a field of sets. Its axioms are the axioms C1–C7 of a cylindric algebra but with ${\displaystyle \cup }$ instead of ${\displaystyle +}$, ${\displaystyle \cap }$ instead of ${\displaystyle \cdot }$, set complement for complement, empty set as 0, ${\displaystyle X^{\alpha }}$ as the unit, and ${\displaystyle \subseteq }$ instead of ${\displaystyle \leq }$. The set X is the domain of each of the variables and it is called the base.

Any cylindric algebra has a representation as a cylindric set algebra, due to Stone's representation theorem. It is easier to connect the semantics of first-order predicate logic with cylindric set algebra. (For more details, see the Further reading section.)

## Generalizations

Cylindric algebras have been generalized to the case of many-sorted logic (Caleiro and Gonçalves 2006), which allows for a better modeling of the duality between first-order formulas and terms.

## Relation to monadic Boolean algebra

When ${\displaystyle \alpha =1}$ and ${\displaystyle \kappa ,\lambda }$ are restricted to being only 0, then ${\displaystyle c_{\kappa }}$ becomes ${\displaystyle \exists }$, the diagonals can be dropped out, and the following theorem of cylindric algebra (Pinter 1973):

${\displaystyle c_{\kappa }(x+y)=c_{\kappa }x+c_{\kappa }y}$

turns into the axiom

${\displaystyle \exists (x+y)=\exists x+\exists y}$

of monadic Boolean algebra. The axiom (C4) drops out. Thus monadic Boolean algebra can be seen as a restriction of cylindric algebra to the one variable case.