A cylindric algebra of dimension (where is any ordinal number) is an algebraic structure such that is a Boolean algebra, a unary operator on for every (called a cylindrification), and a distinguished element of for every and (called a diagonal), such that the following hold:
(C1)
(C2)
(C3)
(C4)
(C5)
(C6) If , then
(C7) If , then
Assuming a presentation of first-order logic without function symbols,
the operator models existential quantification over variable in formula while the operator models the equality of variables and . Hence, reformulated using standard logical notations, the axioms read as
(C1)
(C2)
(C3)
(C4)
(C5)
(C6) If is a variable different from both and , then
(C7) If and are different variables, then
Cylindric set algebrasedit
A cylindric set algebra of dimension is an algebraic structure such that is a field of sets, is given by , and is given by .[1] It necessarily validates the axioms C1–C7 of a cylindric algebra, with instead of , instead of , set complement for complement, empty set as 0, as the unit, and instead of . 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.[2][example needed] It is easier to connect the semantics of first-order predicate logic with cylindric set algebra. (For more details, see § Further reading.)
Generalizationsedit
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 algebraedit
When and are restricted to being only 0, then becomes , 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.
Leon Henkin, J. Donald Monk, and Alfred Tarski (1971) Cylindric Algebras, Part I. North-Holland. 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.