Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

If $(L, \land, \lor, 0, 1)$ is a lattice, and there exists a unary operation $'$ on $L$ such that

  1. $(x \lor x')=1$, and

  2. $(x \land x')=0$

both hold, is the unary operation $'$ an isomorphism between the semilattices $(L, \land)$ and $(L, \lor)$? If we add the condition that $'$ is an involution (i. e. $x''=x$), is $'$ an isomorphism?

share|improve this question

1 Answer 1

up vote 2 down vote accepted

No.

Consider this lattice:

                                    1
                                   / \
                                  /   \
                                 /     \
                                d       w
                               / \     / \
                              b   c   y   z
                               \ /     \ /
                                a       x
                                 \     /
                                  \   /
                                   \ /
                                    0

and make $'$ exchange $0\leftrightarrow 1$, $d\leftrightarrow w$, $b\leftrightarrow y$, $c\leftrightarrow z$, $a\leftrightarrow x$. It is easy to verify that $r\land r' = 0$ and $r\lor r' = 1$ for all $r$; but $'$ does not define an isomorphism from $(L,\land)$ to $(L,\lor)$, since for example $b'\lor c' = y\lor z = w$, but $(b\land c)' = a' = x\neq w$. Nor does it define an isomorphism going the other way, since the map is self-invertible.

Added. A smaller example:

                                     1
                                    / \
                                   /   \
                                  b     y
                                  |     |
                                  a     x
                                   \   /
                                    \ /
                                     0

But $a'\lor b' = x\lor y = y$, $(a\land b)' = a' = x$.

share|improve this answer
    
Did you use any particular method to find this? –  Doug Spoonwood Feb 16 '12 at 5:05
    
It suggested itself fairly quickly: take a disjoint union of two copies of the same lattice, stick a $0$ and a $1$ to that, then have $'$ swap the copies. Have enough elements to have a nontrivial join and a nontrivial meet, and make it as small as possible. Had I thought a bit more, I could have made it even smaller: remove $d$ and $w$, or remove $a$ and $x$; you don't need both a nontrivial join and a nontrivial meet, just one of them. –  Arturo Magidin Feb 16 '12 at 5:09
    
Or even smaller: remove $d$, $w$, $c$, and $z$. –  Arturo Magidin Feb 16 '12 at 5:13
    
I don't know what you mean by "nontrivial join (meet)". If we have an unordered pair {x, y} such that (x $\lor$ y)=z, where z $\neq$ y and z $\neq$ x, would you call their meet nontrivial? Or is there more to it? –  Doug Spoonwood Feb 16 '12 at 13:24
    
I meant "Nontrivial meet"$\neq 0$, "nontrivial join$\neq 1$. The second example shows you don't need $x\lor y\notin\{x,y\}$ for a counterexample to work. –  Arturo Magidin Feb 16 '12 at 16:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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