Cylindric algebra

In

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 }$. Hence, reformulated using standard logical notations, the axioms read as

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

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

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

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

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

(C6) If ${\displaystyle \kappa }$ is a variable different from both ${\displaystyle \lambda }$ and ${\displaystyle \mu }$, then ${\displaystyle \lambda =\mu \iff \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)\iff {\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, ${\displaystyle c_{\kappa }S}$ is given by ${\displaystyle \{y\in X^{\alpha }\mid \exists x\in S\ \forall \beta \neq \kappa \ y(\beta )=x(\beta )\}}$, and ${\displaystyle d_{\kappa \lambda }}$ is given by ${\displaystyle \{x\in X^{\alpha }\mid x(\kappa )=x(\lambda )\}}$.^[1] It necessarily validates the axioms C1–C7 of a cylindric algebra, 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 called the base.

A representation of a cylindric algebra is an

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 (becomes a tautology). Thus monadic Boolean algebra can be seen as a restriction of cylindric algebra to the one variable case.

See also

• Abstract algebraic logic
• Lambda calculus and Combinatory logic—other approaches to modelling quantification and eliminating variables
• Hyperdoctrines are a categorical formulation of cylindric algebras
• Relation algebras (RA)
• Polyadic algebra
• Cylindrical algebraic decomposition

Notes

References

• Charles Pinter (1973). "A Simple Algebra of First Order Logic". Notre Dame Journal of Formal Logic. XIV: 361–366.
• ISBN 978-0-7204-2043-2
  .
• Leon Henkin, J. Donald Monk, and Alfred Tarski (1985) Cylindric Algebras, Part II. North-Holland.
• Robin Hirsch and Ian Hodkinson (2002) Relation algebras by games Studies in logic and the foundations of mathematics, North-Holland
• Carlos Caleiro, Ricardo Gonçalves (2006). "On the algebraization of many-sorted logics" (PDF). In J. Fiadeiro and P.-Y. Schobbens (ed.). Proc. 18th int. conf. on Recent trends in algebraic development techniques (WADT). LNCS. Vol. 4409. Springer. pp. 21–36.
  ISBN 978-3-540-71997-7
  .

• doi:10.1016/0022-0000(84)90077-1
  .

• example of cylindrical algebra by CWoo on planetmath.org