0
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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$. $\endgroup$
    – amrsa
    Commented Oct 27, 2020 at 18:03
  • $\begingroup$ @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. $\endgroup$
    – stoic-santiago
    Commented Oct 28, 2020 at 16:03

2 Answers 2

Reset to default
3
$\begingroup$

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

enter image description here

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$
    – amrsa
    Commented Oct 28, 2020 at 16:33
  • $\begingroup$ 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! $\endgroup$
    – stoic-santiago
    Commented Oct 28, 2020 at 16:44
  • 1
    $\begingroup$ 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. $\endgroup$
    – amrsa
    Commented Oct 28, 2020 at 16:47
  • $\begingroup$ 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. $\endgroup$
    – stoic-santiago
    Commented Oct 28, 2020 at 16:49
  • $\begingroup$ 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. $\endgroup$
    – amrsa
    Commented Oct 28, 2020 at 16:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .