If P is a partially ordered set, a subset A of P is called an antichain in P provided:
whenever $x,y \in A$ with $x \le y$ we have $x=y$.
(In other words, every pair of elements in an antichain are incomparable.)
GOAL: Show that P is linearly ordered if and only if every maximal antichain in P has a single element.
- If we let M be a maximal antichain of P, then M is not a proper subset of any other antichain.
- First, suppose every maximal antichain in P has only a single element. So let $a \in M: a \le a\le \cdots$ where a is the single element of the maximal antichain M in P. (I get stuck trying to get P linearly ordered probably because I'm not noticing some obvious fact.)
- Now, suppose P is a linearly ordered set. Then any two elements are comparable and P looks like: $p_1 \le p_2 \le p_3 \le \cdots$ where each p element is in P.
I appreciate the help!
Here is a hint in each direction:
Recall the defining feature of a linear order is that every pair of elements is comparable.
First, if $P$ is linearly ordered, then take any two elements $x$ and $y$. In an antichain, we must have $x \not \leq y$ and $y \not \leq x$. But what is the one thing we know about linear orders?
Conversely, if the largest antichain has size 1, then take two elements $x$ and $y$. Can you show they must be comparable (using an argument similar to the above)?
I hope this helps ^_^