Cylindric algebra

In mathematics, 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. 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. 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 A cylindric set algebra of dimension is an algebraic structure such that is a field of sets, is given by , and is given by . 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. It is easier to connect the semantics of first-order predicate logic with cylindric set algebra. (For more details, see .) 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.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (6)

Paul Halmos

Paul Richard Halmos (Halmos Pál; March 3, 1916 – October 2, 2006) was a Hungarian-born American mathematician and statistician who made fundamental advances in the areas of mathematical logic, probability theory, statistics, operator theory, ergodic theory, and functional analysis (in particular, Hilbert spaces). He was also recognized as a great mathematical expositor. He has been described as one of The Martians. Born in Hungary into a Jewish family, Halmos arrived in the U.S. at 13 years of age. He obtained his B.

Quantifier (logic)

In logic, a quantifier is an operator that specifies how many individuals in the domain of discourse satisfy an open formula. For instance, the universal quantifier in the first order formula expresses that everything in the domain satisfies the property denoted by . On the other hand, the existential quantifier in the formula expresses that there exists something in the domain which satisfies that property. A formula where a quantifier takes widest scope is called a quantified formula.

Combinatory logic

Combinatory logic is a notation to eliminate the need for quantified variables in mathematical logic. It was introduced by Moses Schönfinkel and Haskell Curry, and 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 languages. It is based on combinators, which were introduced by Schönfinkel in 1920 with the idea of providing an analogous way to build up functions—and to remove any mention of variables—particularly in predicate logic.