5.2 Cylindric algebras: definition and basic properties

Cylindric algebras expand on Boolean algebras, adding cylindrification operators and diagonal elements. These additions allow for more complex logical structures, mirroring existential quantification and equality in first-order logic.

Key properties of cylindric algebras include expansion, distribution, and idempotence of cylindrification operators. These properties, along with the interaction between cylindrification and Boolean operations, form the foundation for working with these advanced algebraic structures.

Cylindric Algebras: Foundations and Properties

Definition of cylindric algebras

• Cylindric algebras extend Boolean algebras with additional operations and elements
• Basic components combine Boolean algebra structure with cylindrification operators $c_i$ for each dimension $i$ and diagonal elements $d_{ij}$ for dimension pairs $i$ and $j$
• Cylindrification operators $c_i$ generalize existential quantification by projecting elements onto higher dimensions
• Diagonal elements $d_{ij}$ represent equality between variables in different dimensions (x = y)
• Inherited Boolean operations include join (∨), meet (∧), complement (¬)
• Specific axioms govern cylindric algebras such as commutativity of cylindrification ($c_i c_j x = c_j c_i x$) and cylindrification of diagonal elements ($c_i d_{ij} = 1$)

Properties of cylindric algebras

• Cylindrification axioms describe fundamental behavior of $c_i$ operators:
  1. Expansion: $x ≤ c_i x$
  2. Distribution: $c_i(x ∧ c_i y) = c_i x ∧ c_i y$
  3. Idempotence: $c_i c_i x = c_i x$
• Proof techniques utilize Boolean algebra laws, cylindric algebra-specific axioms, and induction on term structure
• Key properties include monotonicity of cylindrification, interaction with Boolean operations, and relationship between cylindrification and diagonal elements
• Monotonicity states if $x ≤ y$, then $c_i x ≤ c_i y$
• Interaction with Boolean operations shows $c_i(x ∨ y) = c_i x ∨ c_i y$
• Relationship between cylindrification and diagonal elements demonstrates $c_i(d_{ij} ∧ x) = x$ if $i ≠ j$

Cylindric vs Boolean algebras

• Cylindric algebras extend Boolean algebras while retaining all Boolean operations and laws
• Dimensions in cylindric algebras correspond to number of free variables (Boolean algebras are 0-dimensional)
• Representation theory extends Stone's theorem for Boolean algebras to cylindric algebras
• Algebraization of logic shows Boolean algebras algebraize propositional logic while cylindric algebras algebraize first-order logic with equality

Construction of cylindric algebras

• Finite cylindric algebras based on power sets of finite sets with dimension determined by coordinate number in base set
• Set-theoretic cylindric algebras use power set of $^ωX$ (functions from ω to X) as universe
• Cylindrification in set-theoretic algebras defined as $c_i(A) = \{s ∈ ^ωX : ∃t ∈ A, t(j) = s(j) for j ≠ i\}$
• Diagonal elements in set-theoretic algebras defined as $d_{ij} = \{s ∈ ^ωX : s(i) = s(j)\}$
• Cylindric algebras from relational structures use set of all formulas in given language
• Dimension determined by counting distinct cylindrification operators or analyzing diagonal element structure
• Concrete examples include 2-dimensional cylindric algebra of binary relations and 3-dimensional cylindric algebra of ternary relations