Counter example for associativity of partially ordered sets

152 Views Asked by At

I wasn’t convinced about the associativity property of posets, and the proof i found on math.stackexchange seemed reasonable, but still i couldnt wrap my head around it.

I tried to make a counter example, such that (x ∨ y) ∨ z ≠ x ∨ (y ∨ z)

(b ∨ c) ∨ d = h and b ∨ (c ∨ d) = i ; in this diagram this diagram

But associativity rule says that both should be equal, i.e “h = i”.

I’m not able to figure out where im going wrong. I feel that the diagram is a poset, because it is reflexive, antisymmetric and transitive, but i know it has to be wrong, otherwise it would’ve satisfied associativity.

But i cant seem to figure out why this diagram isn’t a poset and where am i going wrong. please help

1

There are 1 best solutions below

2
On BEST ANSWER

Your partially ordered set does not have a well defined least upper bound function; that is, $\vee$ does not define an operation in your set. That’s why you are not getting equality.

For the benefit of those who don’t want to open your image, you are taking a sub-poset of the power set of $\{1,2,3,4,5,6\}$, that consists of the following sets:

  • $\{1\}$
  • $\{1,2\}$, $\{1,3\}$, $\{1,4\}$
  • $\{1,2,3\}$, $\{1,3,4,5\}$, $\{1,2,3,4\}$
  • $\{1,3,4,5,6\}$
  • $\{1,2,3,4,5,6\}$.

You are then taking $b=\{1,2\}$, $c=\{1,3\}$, $d=\{1,4\}$.

Then the least upper bound of $b$ and $c$, $b\vee c$, is $\{1,2,3\}$; the least upper bound of $\{1,2,3\}$ and $d=\{1,4\}$, $(b\vee c)\vee d$ is $h=\{1,2,3,4\}$.

You then say that the least upper bound of $c=\{1,3\}$ and $d=\{1,4\}$ is $j=\{1,3,4,5\}$, and then taking $\{1,2\}\vee\{1,3,4,5\}$ you get $i=\{1,2,3,4,5,6\}$.

But the claim that $\{1,3\}\vee\{1,4\} = \{1,3,4,5\}$ is unwarranted. It could just as well be $h=\{1,2,3,4\}$: both $\{1,3,4,5\}$ and $\{1,2,3,4\}$ contain $\{1,3\}$ and $\{1,4\}$; and there is no strictly smaller element that contains both: you have two incomparable minimal upper bounds for $\{1,3\}$ and $\{1,4\}$, so you cannot even calculate $\{1,3\}\vee\{1,4\}=b\vee c$.

In general, you can’t define least upper bounds for arbitrary posets; you need more properties before the notion of $\vee$ even makes sense. Specifically, you need an upper semilattice. What you have is a poset, but not an upper semilattice.