Cylindric algebra

The notion of cylindric algebra, invented 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. Indeed, 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 algebraEdit

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  . Henceforth, 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 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.

Not every cylindric algebra has a representation as a cylindric set algebra.[citation needed][example needed] It is easier to connect the semantics of first-order predicate logic with cylindric set algebra. (For more details, see the Further reading section.)

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

See alsoEdit

NotesEdit

  1. ^ Hirsch and Hodkinson p167, Definition 5.16

ReferencesEdit

  • Charles Pinter (1973). "A Simple Algebra of First Order Logic" (PDF). Notre Dame Journal of Formal Logic. XIV: 361–366.
  • Leon Henkin, Monk, J.D., and Alfred Tarski (1971) Cylindric Algebras, Part I. North-Holland. ISBN 978-0-7204-2043-2.
  • Leon Henkin, Monk, J.D., 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. 4409. Springer. pp. 21–36. ISBN 978-3-540-71997-7.

Further readingEdit

External linksEdit