A generalized Boolean algebra gives rise to an implication algebra

203 Views Asked by At

A generalized Boolean algebra $G$ is relatively complemented distributive lattice with largest element 1.

That is, an element $a\in G$ has a complement in any interval $[x\,,\,1]$ that contains $a$.

Secondly,

An implication algebra is an algebra $\langle I, \to\rangle$ of type $(2)$ satisfying:

(I1) $(x\to y)\to x=x$

(I2) $(x\to y)\to y= (y\to x)\to x$

(I3) $x\to(y\to z) = y\to (x\to z)$.

Claim: Let $G$ be a generalized Boolean algebra. For $a,b\in G$, define $a\to b$ as the complement of $a$ in the interval $[a\wedge b\,,\, 1]$. Then $\langle G, \to\rangle$ is an implication algebra.

Certainly $G$ is closed under $\to$. Write $a'_{a\wedge b}$ for $a\to b$. Proving (I1) is not too bad:

We have that $(x\to y)\to x=(x'_{x\wedge y})\to x$ is the complement of $x'_{x\wedge y}$ in the interval $$\bigl[(x'_{x\wedge y})\wedge x\,,\, 1\bigr]=[x\wedge y\,,\, 1]$$ which is just $x$.

The identities (I2) and (I3) are less clear to me... For example,

$(x\to y)\to y$ is the complement of $x'_{x\wedge y}$ in the interval $\bigl[(x'_{x\wedge y})\wedge y\,,\, 1\bigr]$, while

$(y\to x)\to x$ is the complement of $y'_{x\wedge y}$ in the interval $\bigl[(y'_{x\wedge y})\wedge x\,,\, 1\bigr]$.

How exactly are these two equal? Any help is appreciated.

1

There are 1 best solutions below

1
On BEST ANSWER

It might be helpful to realize that (I2) is encoding the commutativity of disjunction (or join, $\vee$), since in a Boolean algebra, $$ (x\to y)\to y = \neg (\neg x \vee y) \vee y = (x \wedge \neg y) \vee y = (x\vee y ) \wedge (\neg y \vee y) = x \vee y. $$

In the same way, in a Boolean algebra both terms appearing in (I3) should be equal to $x\wedge y \to z = y\wedge x \to z$.

Another piece of useful information is that

in a distributive lattice, complements are unique.

In the following I'll use this several times.

To get started, it is easy to show that $(x\to y)\vee y$ is also a complement of $x$ in the interval $[x\wedge y,1]$. By uniqueness, we have $x\to y =(x\to y)\vee y$ and hence $$ (x\to y)\geq y \qquad (1). $$ This also means that $(x\to y)\to y$ is the complement of $x\to y$ in the interval $[(x\to y)\wedge y,1]=[y,1]$.

To finish, it is enough to show that $x\vee y$ is a complement of $x\to y$ in that interval. It is clear that $(x\vee y)\vee (x\to y) = 1$. Now $$ (x\vee y)\wedge(x\to y) = (x\wedge(x\to y))\vee (y\wedge(x\to y)) = (x\wedge y)\vee y = y, $$ where I'm using the definition of $x\to y$ and $(1)$. This gives $(x\to y)\to y = x\vee y$ by uniqueness. Since $x\vee y$ is commutative, you immediately have that $x\vee y = (y\to x)\to x$.