You are here
Homecylindric algebra
Primary tabs
cylindric algebra
A cylindric algebra is a quadruple $(B,V,\exists,d)$, where $B$ is a Boolean algebra, $V$ is a set whose elements we call variables, $\exists$ and $d$ are functions
$\exists:V\to B^{B}\qquad\mbox{ and }\qquad d:V\times V\to B$ 
such that
1. $(B,\exists x)$ is a monadic algebra for each $x\in V$,
2. $\exists x\circ\exists y=\exists y\circ\exists x$ for any $x,y\in V$,
3. $d_{{xx}}=1$ for all $x\in V$,
4. for any $x,y\in V$ with $x\neq y$, and any $a\in B$, we have the equality
$\exists x(a\wedge d_{{xy}})\wedge\exists x\big(a^{{\prime}}\wedge d_{{xy}}\big% )=0$ 5. for any $x,y,z\in V$ with $x\neq y$ and $x\neq z$, we have the equality
$\exists x(d_{{xy}}\wedge d_{{xz}})=d_{{yz}}.$
where $\exists x$ and $d_{{xy}}$ are the abbreviations for $\exists(x)$ and $d(x,y)$ respectively.
Basically, the first two conditions say that the $(B,V,\exists)$ portion of the cylindric algebra is very similar to a quantifier algebra, except the domain is no longer the subsets of $V$, but the elements of $V$ instead. The function $d$ is the algebraic abstraction of equality. Condition 3 says that $x=x$ is always true, condition 4 says that the proposition $a$ and its complement $a^{{\prime}}$, where any occurrences of the variable $x$ are replaced by the variable $y$, distinct from $x$, is always false, while condition 5 says $y=z$ iff there is an $x$ such that $x=y$ and $x=z$.
Below are some elementary properties of $d$:

(symmetric property) $d_{{xy}}=d_{{yx}}$

(transitive property) $d_{{xy}}\wedge d_{{yz}}\leq d_{{xz}}$

$\exists x(d_{{xy}})=1$

$\exists x(d_{{yz}})=d_{{yz}}$ provided that $x\notin\{y,z\}$

if $x\neq y$, then
(a) $\exists x(d_{{xy}}\wedge a^{{\prime}})=(\exists x(d_{{xy}}\wedge a))^{{\prime}}$,
(b) $d_{{xy}}\wedge a=d_{{xy}}\wedge\exists x(a\wedge d_{{xy}})$.
Remarks
1. The dimension of a cylindric algebra $(B,V,\exists,d)$ is the cardinality of $V$.
2. From the definition above, a cylindric algebra is a twosorted structure, with $B$ and $V$ as the two distinct universes. However, it is often useful to view a cylindric algebra as a onesorted structure. The way to do this is to dispense with $V$ and identify each $\exists x$ as a unary operator on $B$, and each $d_{{xy}}$ as a constant in $B$. As a result, the cylindric algebra $(B,V,\exists,d)$ becomes a Boolean algebra with possibly infinitely many operators:
$(B,\exists x,d_{{xy}})_{{x,y\in V}}.$ 3. Let $L$ be a the language of a first order logic, and $S$ a set of sentences in $L$. Define $\equiv$ on $L$ so that
$\varphi\equiv\psi\quad\mbox{ iff }\quad S\vdash(\varphi\leftrightarrow\psi).$ Then $\equiv$ is an equivalence relation on $L$. For each formula $\varphi\in L$, let $[\varphi]$ be the equivalence class containing $\varphi$. Let $V$ be a countably infinite set of variables available to $L$. Now, define operations $\vee,\wedge,^{{\prime}},\exists x,d_{{xy}}$ as follows:
$\displaystyle[\varphi]\vee[\psi]$ $\displaystyle:=$ $\displaystyle[\varphi\vee\psi],$ (1) $\displaystyle\left[\varphi\right]\wedge[\psi]$ $\displaystyle:=$ $\displaystyle[\varphi\wedge\psi],$ (2) $\displaystyle\left[\varphi\right]^{{\prime}}$ $\displaystyle:=$ $\displaystyle[\neg\varphi],$ (3) $\displaystyle 0$ $\displaystyle:=$ $\displaystyle[\neg x=x],$ (4) $\displaystyle 1$ $\displaystyle:=$ $\displaystyle[x=x],$ (5) $\displaystyle\exists x[\varphi]$ $\displaystyle:=$ $\displaystyle[\exists x\varphi],$ (6) $\displaystyle d_{{xy}}$ $\displaystyle:=$ $\displaystyle[x=y].$ (7) Then it can be shown that $(L/\equiv,V,\exists,d)$ 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 (LindenbaumTarski 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., NorthHolland, 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).
Mathematics Subject Classification
03G15 no label found06E25 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections