cylindric algebra
A cylindric algebra is a quadruple , where is a Boolean algebra, is a set whose elements we call variables, and are functions
such that
-
1.
is a monadic algebra for each ,
-
2.
for any ,
-
3.
for all ,
-
4.
for any with , and any , we have the equality
-
5.
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 :
-
•
(symmetric property)
- •
-
•
-
•
provided that
-
•
if , then
-
(a)
,
-
(b)
.
-
(a)
Remarks
-
1.
The dimension of a cylindric algebra is the cardinality of .
-
2.
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:
-
3.
Let be a the language of a first order logic, and a set of sentences in . Define on so that
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:
(1) (2) (3) (4) (5) (6) (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.
References
- 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).
Title | cylindric algebra |
---|---|
Canonical name | CylindricAlgebra |
Date of creation | 2013-03-22 17:51:21 |
Last modified on | 2013-03-22 17:51:21 |
Owner | CWoo (3771) |
Last modified by | CWoo (3771) |
Numerical id | 10 |
Author | CWoo (3771) |
Entry type | Definition |
Classification | msc 03G15 |
Classification | msc 06E25 |
Related topic | PolyadicAlgebra |
Related topic | PolyadicAlgebraWithEquality |