|
|
|
|
cylindric algebra
|
(Definition)
|
|
|
A cylindric algebra is a quadruple
, where is a Boolean algebra, is a set whose elements we call variables, and are functions
 and 
such that
-
is a monadic algebra for each ,
-
for any ,
for all ,
- for any
with , and any , we have the equality
- for any
with and , we have the equality
where and are the abbreviations for
and respectively.
Basically, the first two conditions say that the
portion of the cylindric algebra is very similar to a quantifier algebra, except the domain is no longer the subsets of , but the elements of instead. The function is the algebraic abstraction of equality. Condition 3 says that is always true, condition 4 says that the proposition and its complement , where any occurrences of the variable are replaced by the variable , distinct from , is always false, while condition 5 says iff there is an such that and .
Below are some elementary properties of :
Remarks
- The dimension of a cylindric algebra
is the cardinality of .
- From the definition above, a cylindric algebra is a two-sorted structure, with
and as the two distinct universes. However, it is often useful to view a cylindric algebra as a one-sorted structure. The way to do this is to dispense with and identify each as a unary operator on , and each as a constant in . As a result, the cylindric algebra
becomes a Boolean algebra with possibly infinitely many operators:
- Let
be a the language of a first order logic, and a set of sentences in . Define on so that
 iff 
Then is an equivalence relation on . For each formula
, let be the equivalence class containing . Let be a countably infinite set of variables available to . Now, define operations
as follows:
![$\displaystyle [\varphi] \vee [\psi]$ $\displaystyle [\varphi] \vee [\psi]$](http://images.planetmath.org:8080/cache/objects/10331/l2h/img75.png) |
 |
![$\displaystyle [\varphi \vee \psi],$ $\displaystyle [\varphi \vee \psi],$](http://images.planetmath.org:8080/cache/objects/10331/l2h/img77.png) |
(1) |
![$\displaystyle \left[ \varphi \right] \wedge [\psi]$ $\displaystyle \left[ \varphi \right] \wedge [\psi]$](http://images.planetmath.org:8080/cache/objects/10331/l2h/img78.png) |
 |
![$\displaystyle [\varphi \wedge \psi],$ $\displaystyle [\varphi \wedge \psi],$](http://images.planetmath.org:8080/cache/objects/10331/l2h/img80.png) |
(2) |
![$\displaystyle \left[ \varphi \right]'$ $\displaystyle \left[ \varphi \right]'$](http://images.planetmath.org:8080/cache/objects/10331/l2h/img81.png) |
 |
![$\displaystyle [\neg \varphi],$ $\displaystyle [\neg \varphi],$](http://images.planetmath.org:8080/cache/objects/10331/l2h/img83.png) |
(3) |
| 0 |
 |
![$\displaystyle [\neg x=x],$ $\displaystyle [\neg x=x],$](http://images.planetmath.org:8080/cache/objects/10331/l2h/img85.png) |
(4) |
 |
 |
![$\displaystyle [x=x],$ $\displaystyle [x=x],$](http://images.planetmath.org:8080/cache/objects/10331/l2h/img88.png) |
(5) |
![% latex2html id marker 583 $\displaystyle \exists x[\varphi]$ % latex2html id marker 583 $\displaystyle \exists x[\varphi]$](http://images.planetmath.org:8080/cache/objects/10331/l2h/img89.png) |
 |
![% latex2html id marker 587 $\displaystyle [\exists x \varphi],$ % latex2html id marker 587 $\displaystyle [\exists x \varphi],$](http://images.planetmath.org:8080/cache/objects/10331/l2h/img91.png) |
(6) |
 |
 |
![$\displaystyle [x=y].$ $\displaystyle [x=y].$](http://images.planetmath.org:8080/cache/objects/10331/l2h/img94.png) |
(7) |
Then it can be shown that
is a cylindric algebra. Thus a cylindric algebra can be thought of as an “algebraization” of first order logic (with equality), much the same way as a Boolean algebra (Lindenbaum-Tarski algebra) as the algebraic counterpart of propositional logic.
- 1
- P. Halmos, Algebraic Logic, Chelsea Publishing Co. New York (1962).
- 2
- L. Henkin, J. D. Monk, A. Tarski, Cylindric Algebras, Part I., North-Holland, Amsterdam (1971).
- 3
- J. D. Monk, Mathematical Logic, Springer, New York (1976).
- 4
- B. Plotkin, Universal Algebra, Algebraic Logic, and Databases, Kluwer Academic Publishers (1994).
|
"cylindric algebra" is owned by CWoo.
|
|
(view preamble)
Cross-references: propositional logic, Lindenbaum-Tarski algebra, operations, countably infinite, equivalence class, formula, equivalence relation, sentences, first order logic, language, operator, unary, universes, structure, cardinality, dimension, transitive property, symmetric, properties, iff, occurrences, complement, proposition, algebraic, subsets, domain, quantifier algebra, similar, equality, monadic algebra, functions, variables, Boolean algebra
There are 3 references to this entry.
This is version 6 of cylindric algebra, born on 2008-02-24, modified 2008-03-16.
Object id is 10331, canonical name is CylindricAlgebra.
Accessed 285 times total.
Classification:
| AMS MSC: | 03G15 (Mathematical logic and foundations :: Algebraic logic :: Cylindric and polyadic algebras; relation algebras) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|