Cylindric algebra

From Wikipedia, the free encyclopedia

The notion of cylindric algebra, invented by Alfred Tarski, arises naturally in the algebraization of first-order logic. 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.

1 Definition of a cylindric algebra
2 Generalizations
3 See also
4 References
5 External links

[edit] Definition of a cylindric algebra

A cylindric algebra of dimension $α$ , where $α$ is any ordinal is an algebraic structure $(A,+,\cdot,-,0,1,c_\kappa,d_{\kappa\lambda})_{\kappa,\lambda<\alpha}$ such that $(A,+,\cdot,-,0,1)$ is a Boolean algebra, $c κ$ a unary operator on $A$ for every $κ$ , and $d κλ$ a distinguished element of $A$ for every $κ$ and $λ$ , such that the following hold:

(C1) $c κ 0 = 0$

(C2) $x\leq c_\kappa x$

(C3) $c_\kappa(x\cdot c_\kappa y)=c_\kappa x\cdot c_\kappa y$

(C4) $c κ c λ x = c λ c κ x$

(C5) $d κκ = 1$

(C6) If $\kappa\neq\lambda\mu$ , then $d_{\lambda\mu}=c_\kappa(d_{\lambda\kappa}\cdot d_{\kappa\mu})$

(C7) If $\kappa\neq\lambda$ , then $c_\kappa(d_{\kappa\lambda}\cdot x)\cdot c_\kappa(d_{\kappa\lambda}\cdot -x)=0$

[edit] Generalizations

Recently, cylindric algebras have been generalized to the many-sorted case, which allows for a better modeling of the duality between first-order formulas and terms.

[edit] See also

Abstract algebraic logic
Lambda calculus and Combinatory logic, other approaches to modelling quantification and eliminating variables
Hyperdoctrines are a categorical formulation of cylindric algebras
First-order logic

Relation algebras (RA)
Polyadic equality algebras (PEA)

[edit] References

Leon Henkin, Monk, J.D., and Alfred Tarski (1971) Cylindric Algebras, Part I. North-Holland. ISBN 978-0-7204-2043-2.
-------- (1985) Cylindric Algebras, Part II. North-Holland.
Caleiro, C., and Gonçalves, R (2007) "On the algebraization of many-sorted logics" in J. Fiadeiro and P.-Y. Schobbens, eds., Recent Trends in Algebraic Development Techniques - Selected Papers, Vol. 4409 of Lecture Notes in Computer Science. Springer-Verlag: 21-36.