Cylindric algebra
Encyclopedia
The notion of cylindric algebra, invented by Alfred Tarski
Alfred Tarski
Alfred Tarski was a Polish logician and mathematician. Educated at the University of Warsaw and a member of the Lwow-Warsaw School of Logic and the Warsaw School of Mathematics and philosophy, he emigrated to the USA in 1939, and taught and carried out research in mathematics at the University of...

, arises naturally in the algebraization
Algebraic logic
In mathematical logic, algebraic logic is the study of logic presented in an algebraic style.What is now usually called classical algebraic logic focuses on the identification and algebraic description of models appropriate for the study of various logics and connected problems...

 of first-order logic
First-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate 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
Quantification
Quantification has several distinct senses. In mathematics and empirical science, it is the act of counting and measuring that maps human sense observations and experiences into members of some set of numbers. Quantification in this sense is fundamental to the scientific method.In logic,...

 and equality. They differ from polyadic algebra
Polyadic algebra
Polyadic algebras are algebraic structures introduced by Paul Halmos. They are related to first-order logic in a way analogous to the relationship between Boolean algebras and propositional logic .There are other ways to relate first-order logic to algebra, including Tarski's cylindric algebras...

s in that the latter do not model equality.

Definition of a cylindric algebra

A cylindric algebra of dimension , where is any ordinal
Ordinal number
In set theory, an ordinal number, or just ordinal, is the order type of a well-ordered set. They are usually identified with hereditarily transitive sets. Ordinals are an extension of the natural numbers different from integers and from cardinals...

 is an algebraic structure such that is a Boolean algebra, a unary operator on for every , and a distinguished element of for every and , 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
Existential quantification
In predicate logic, an existential quantification is the predication of a property or relation to at least one member of the domain. It is denoted by the logical operator symbol ∃ , which is called the existential quantifier...

 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 , then

(C7) If , then

Generalizations

Recently, cylindric algebras have been generalized to the many-sorted
Many-sorted logic
Many-sorted logic can reflect formally our intention, not to handle the universe as a homogeneous collection of objects, but to partition it in a way that is similar to types in typeful programming...

 case, which allows for a better modeling of the duality between first-order formulas and terms.

See also

  • Abstract algebraic logic
    Abstract Algebraic Logic
    In mathematical logic, abstract algebraic logic is the study of the algebraization of deductive systemsarising as an abstraction of the well-known Lindenbaum-Tarski algebra, and how the resulting algebras are related to logical systems.-Overview:...

  • Lambda calculus
    Lambda calculus
    In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...

     and Combinatory logic
    Combinatory logic
    Combinatory logic is a notation introduced by Moses Schönfinkel and Haskell Curry to eliminate the need for variables in mathematical logic. It has more recently been used in computer science as a theoretical model of computation and also as a basis for the design of functional programming...

    , other approaches to modelling quantification and eliminating variables
  • Hyperdoctrines are a categorical
    Category theory
    Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...

     formulation of cylindric algebras
  • First-order logic
    First-order logic
    First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...

  • Relation algebra
    Relation algebra
    In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation...

    s (RA
    RA
    RA may refer to:- Science :* Right ascension, an astronomical term* Relation algebra, a type of mathematical structure- Medicine :* Relative analgesia machine, a type of sedative* Right atrium, one of the four chambers of the heart...

    )
  • Polyadic algebra
    Polyadic algebra
    Polyadic algebras are algebraic structures introduced by Paul Halmos. They are related to first-order logic in a way analogous to the relationship between Boolean algebras and propositional logic .There are other ways to relate first-order logic to algebra, including Tarski's cylindric algebras...


External links

The source of this article is wikipedia, the free encyclopedia.  The text of this article is licensed under the GFDL.
 
x
OK