In mathematics, the notion of cylindric algebra, developed by Alfred Tarski, arises naturally in the algebraization of first-order logic with equality. This is comparable to the role Boolean algebras play for propositional logic. 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 \alpha (where \alpha is any ordinal number) is an algebraic structure such that is a Boolean algebra, c_\kappa a unary operator on A for every \kappa (called a cylindrification), and a distinguished element of A for every \kappa and \lambda (called a diagonal), such that the following hold: Assuming a presentation of first-order logic without function symbols, the operator c_\kappa x models existential quantification over variable \kappa in formula x while the operator models the equality of variables \kappa and \lambda. Hence, reformulated using standard logical notations, the axioms read as

Cylindric set algebras

A cylindric set algebra of dimension \alpha is an algebraic structure such that is a field of sets, c_\kappa S is given by, and is given by. It necessarily validates the axioms C1–C7 of a cylindric algebra, with \cup instead of +, \cap instead of \cdot, set complement for complement, empty set as 0, X^\alpha as the unit, and \subseteq instead of \le. The set X is called the base. A representation of a cylindric algebra is an isomorphism from that algebra to a cylindric set algebra. Not every cylindric algebra has a representation as a cylindric set algebra. It is easier to connect the semantics of first-order predicate logic with cylindric set algebra. (For more details, see .)

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 \alpha = 1 and are restricted to being only 0, then c_\kappa becomes \exists, the diagonals can be dropped out, and the following theorem of cylindric algebra (Pinter 1973): turns into the axiom 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.