# Show $x \leq y$ iff $y^c \leq x^c$ in a lattice which is a boolean algebra

Show $$x \leq y$$ iff $$y^c \leq x^c$$ where $$x,y$$ are elements of a lattice $$(B,\leq,\lor, \land)$$. $$(B,\leq)$$ is a partially ordered set, and $$\lor$$ and $$\land$$ refer to the l.u.b and g.l.b operations respectively.

I started off with the definition of the complement $$^c$$, which is:

• $$x \land x^c = 0$$
• $$x \lor x^c = 1$$

Then, assuming $$x \leq y$$, I am trying to show $$y^c \leq x^c$$ - or equivalently, $$x^c \leq y^c$$ will result in a contradiction. However, I'm unable to proceed. Could someone please help?

• That is not necessarilly true. Suppose you have a pentagon $N_5$ with another (new) element $y_1$ not comparable with $x,y,z$, and define $x^c=y$, $z^c=y_1$, $y^c=x$ and $y_1^c=z$. Then $z<x$ but $x^c \nleq z^c$. Commented Oct 27, 2020 at 18:03
• @amrsa Could you check my answer and tell me if there's some gap in my understanding? I don't really understand the pentagon example. Commented Oct 28, 2020 at 16:03

What I meant in my comment (before you added that the lattice is a Boolean algebra) is that, for example, with the lattice in the following picture below (where $$x'$$ is what you denote as $$x^c$$)

we have $$a < b$$ but $$b^c = d \nleq c = a^c$$.
Likewise, $$c^c < d^c$$ but $$d \nleq c$$.
So neither of the implications in the equivalence apply.

Of course this is not a Boolean algebra (neither it is a distributive or even modular lattice), and also the de Morgan laws don't apply, since for example, $$(a \wedge b)^c = a^c = c \neq 1 = c \vee d = a^c \vee b^c.$$

If $$x \leq y$$, we know that $$x \land y = x$$ and $$x \lor y = y$$. Also, from De-morgan's laws we know that $$(x \land y)^c = x^c \lor y^c$$ and $$(x \lor y)^c = x^c \land y^c$$.

To show $$y^c \leq x^c$$, we see that:

• $$y^c \land x^c = (x\lor y)^c = y^c$$
• $$y^c \lor x^c = (x \land y)^c = x^c$$

Similarly, starting with $$y^c \leq x^c$$, we can show $$x \leq y$$, which completes the proof.

• Your reasoning is right, provided the de Morgan laws apply. The problem is that that is not always the case. In the example I provided, the de Morgans laws don't hold. I'll give you an answer with that comment in more detail. Commented Oct 28, 2020 at 16:33
• Okay sure, that would be nice! I'm doing a course on Boolean Algebra, and I haven't come across any such lattices so far - where De Morgan's laws don't hold. In fact, the question was related to a section that introduced Boolean algebras as lattices. Nonetheless, it'd be interesting to know when De Morgan's laws don't hold, so I'm awaiting your answer! Commented Oct 28, 2020 at 16:44
• Well, for Boolean algebras, the solution can be as you stated in your answer. But in the question you didn't say the lattice was a Boolean algebra. Commented Oct 28, 2020 at 16:47
• Oh, you're right! I'm not sure I completely understand the difference then. I thought every lattice, i.e. a partially ordered set with l.u.b and g.l.b operations is a boolean algebra? Please help me understand the difference, I haven't formally learnt about lattices yet. Commented Oct 28, 2020 at 16:49
• Ok, so I'm having trouble now with my tex installation and in order to give you an answer as I wanted I'd need to draw the lattice Hasse diagram. I can't do it now, so I'm not giving you that answer after all, sorry. If you don't get one meanwhile, I might do it later. Commented Oct 28, 2020 at 16:57