# A generalized Boolean algebra gives rise to an implication algebra

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.

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$.

• This is incredibly helpful! I will try to figure out (I3) given your comment on it. Thank you!
– Bey
Dec 26 '15 at 20:33