Cylindric Algebras

Origin. Tarski with Henkin and Monk developed cylindric algebras (1950s-70s). Algebraic approach to first-order logic. Cylindrifications model existential quantification. Diagonal elements model equality. Part of algebraic logic tradition alongside relation algebras.

Models. Quantifiers as algebraic operations. Boolean algebra: propositional logic algebraically. Cylindric algebra: add operations for quantifiers and equality. Cylindrification cₖ captures ∃xₖ. Diagonal dₖₗ captures xₖ = xₗ. Alpha dimension captures number of variables.

Formalism.

Cylindric algebra of dimension α: (A, +, ·, -, 0, 1, cₖ, dₖₗ)ₖ,ₗ<α where:

(A, +, ·, -, 0, 1) is Boolean algebra
cₖ: A → A (cylindrification for variable k)
dₖₗ ∈ A (diagonal element for k = l)

Axioms: (C1) cₖ0 = 0 (C2) x ≤ cₖx (C3) cₖ(x · cₖy) = cₖx · cₖy (C4) cₖcₗx = cₗcₖx (C5) dₖₖ = 1 (C6) if k ≠ l,m then dₗₘ = cₖ(dₖₗ · dₖₘ) (C7) if k ≠ l then cₖ(dₖₗ · x) · cₖ(dₖₗ · -x) = 0

Interpretation:

cₖx corresponds to ∃xₖ.φ
dₖₗ corresponds to xₖ = xₗ
Substitution s(k,l)x = cₖ(dₖₗ · x)

Representable cylindric algebras: Concrete: subalgebras of (P(αU), ...) for some set U. Abstract cylindric algebras may not be representable.

Locally finite dimensional: Only finitely many variables "active" in each element. Models finitary first-order logic.

Symbols.

Symbol	Unicode	Name	Meaning
cₖ	—	Cylindrification	Existential quantifier
dₖₗ	—	Diagonal	Equality
+	—	Join	Disjunction
·	—	Meet	Conjunction
-	—	Complement	Negation
α	U+03B1	Dimension	Number of variables
s(k,l)	—	Substitution	Replace variable

Metatheory. Finite-dimensional cylindric algebras: equational class, but not finitely axiomatizable for dim ≥ 3. Representation problem: which abstract CA are representable? Dim 2: all representable. Dim ≥ 3: not all representable. Completeness: FOL complete iff representable CA semantics. Undecidability: equational theory undecidable for dim ≥ 3.

Applies to. Algebraic foundations of logic. Database theory (cylindric algebra of relations). Model theory (algebraic methods). Storage and retrieval. Algebraic specification. Relation to dynamic algebra.

Limitations. Very abstract — not computational. Representability problem is complex. Infinite-dimensional needed for full FOL. Non-finite axiomatizability complicates. Less intuitive than syntactic FOL. Specialized algebraic background required.