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


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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.