How to derive this identity for cylindric algebras?

50 Views Asked by At

I would like to show that the following identity holds for the cylindric algebras of dimension $n$:

$c_i(x\vee y)\approx c_i(x)\vee c_i(y)$.

I can easily show that $c_i(x)\vee c_i(y)\leq c_i(x\vee y)$ for such algebras, but I am having trouble showing the converse.

As for $c_i(x)\vee c_i(y)\leq c_i(x\vee y)$, it follows from

$$c_i(x)\wedge c_i(x\vee y)\approx c_i(x\wedge c_i(x\vee y)),$$

as $x\leq x\vee y\leq c_i(x\vee y)$.

This is part of exercise 12 in Ch. 4, Section 1, in Burris and Sankappanavar's A Course in Universal Algebra.

1

There are 1 best solutions below

2
On BEST ANSWER

For reference, let us recall that, according to that book, an $n$-dimensional cylindric algebra is an algebra $$\mathbf A = (A,\vee,\wedge,',c_0,\ldots,c_{n-1},0,1,d_{00},d_{01},\ldots,d_{n-1,n-1})$$ such that $c_0,\ldots,c_{n-1}$ are unary, $d_{00},\ldots, d_{n-1,n-1}$ are nullary, $(A,\vee,\wedge,',0,1)$ is a Boolean algebra and, among other identities, it satisfies, for $i<n$, \begin{equation} \label{CA3} x \leq c_i(x) \tag{CA3} \end{equation} and \begin{equation} \label{CA4} c_i(x \wedge c_i(y)) = c_i(x) \wedge c_i(y). \tag{CA4} \end{equation} The identity asked in the post is part (d) of the exercise, where the following are also included and can be proved (and apparently, were proved) without using (d): \begin{align} c_i(c_i(x)) &= c_i(x), \label{b}\tag{b}\\ c_i((c_i(x))') &= (c_i(x))'. \label{g}\tag{g} \end{align}

If $x \leq y$, then by \eqref{CA3}, $x \leq c_i(y)$, whence, by \eqref{CA4}, $$c_i(x) = c_i(x \wedge c_i(y)) = c_i(x) \wedge c_i(y),$$ and therefore $c_i(x) \leq c_i(y)$. Hence $c_i$ is order-preserving. Thus, using \eqref{b} and \eqref{CA3}, we obtain, $$c_i(x \vee y) \leq c_i(c_i(x) \vee c_i(y)) \leq c_i(c_i(x \vee y)) = c_i(x \vee y),$$ and so, $$c_i(x \vee y) = c_i(c_i(x) \vee c_i(y)).$$ We now prove that $c_i(c_i(x) \vee c_i(y)) = c_i(x) \vee c_i(y)$.
Using the de Morgan laws, \begin{align} c_i(c_i(x) \vee c_i(y)) &= c_i(((c_i(x))' \wedge (c_i(y))')')\\ &= c_i((c_i((c_i(x))') \wedge c_i((c_i(y))'))')\tag{by \eqref{g}} \end{align} Let $x_1 = (c_i(x))'$ and $y_1 = (c_i(y))'$. Thus, \begin{align} c_i(x \vee y) &= c_i( ( c_i(x_1) \wedge c_i(y_1) )' )\\ &= c_i( ( c_i(x_1 \wedge c_i(y_1)) )' )\tag{by \eqref{CA4}}\\ &= (c_i( x_1 \wedge c_i(y_1) ))'\tag{by \eqref{g}}\\ &= ( c_i(x_1) \wedge c_i(y_1) )'\tag{by \eqref{CA4}}\\ &= (c_i(x_1))' \vee (c_i(y_1))'\tag{by de Morgan}\\ &= (c_i((c_i(x))'))' \vee (c_i((c_i(y))'))'\\ &= ((c_i(x))')' \vee ((c_i(y))')'\tag{by \eqref{g}}\\ &= c_i(x) \vee c_i(y).\tag{by de Morgan} \end{align}


By the way, to prove \eqref{g}, just show that $c_i((c_i(x))')$ is the complement of $c_i(x)$.
To see that $c_i((c_i(x))') \wedge c_i(x) = 0$, use \eqref{CA4} and the fact that $c_i(0)=0$ (which is (CA2));
to see that $c_i((c_i(x))') \vee c_i(x) = 1$, use \eqref{CA3} and the fact that $(c_i(x))' \vee c_i(x) = 1$.