Prove that an infinite poset contains either an infinite chain or an infinite totally unordered subset.

Question

dan815 · Answer

could you state some of the supplemantary info

dan815 · Answer

:)

anonymous · Answer

You can place an equivalence relation on your poset. Say: $$a\sim b\iff a\le b 	ext { or }b\le a.$$This will partition your poset into classes where each class has chains.

anonymous · Answer

Then look at the number of equivalence classes. If its infinite, then you can grab one element from each class (via Axiom of Choice), and the infinite set you have created will be  totally unordered (else they would be in the same class as defined by the equivalence relation).

anonymous · Answer

If its a finite number of classes, then one of the classes must be infinite (since your original poset had an infinite number of elements). You can show that this class has an infinite chain.

anonymous · Answer

Sure, we can construct an argument that supposes there is no infinite chain. It will be very similar to what I posted above. It's really important that we use the idea of equivalence classes, because that's the best way to group together elements that are comparable to each other with the partial order. (Recall, just because $a,b$ are both elements of a poset doesn't mean that $a\le b$  or $b\le a$.)

anonymous · Answer

So suppose there isn't an infinite chain. Then all chains are finite, and it follows that there must be an infinite number of chains. Let $U$ be the set of all chains of your poset. If $A$ and $B$  are two chains in $U$, create the equivalence relation:  $$A\sim B \iff  A\text{ and }B \text{ share an element of the poset.}$$ This equivalence relation will group together all the chains that have common elements.

Is it possible there can only be finitely many equivalence classes? No because these chains are all finite, so if there were finitely many equivalence classes your poset would have a finite number of elements, a contradiction. Thuse there are infinitely many equivalence classes.

Now to make your infinite totally unordered set, just pick one element from each class. This should do the job.

zzr0ck3r · Answer

I am confused about how you showed that there are infinite classes. Could we not have infinite amount of chains in one class? Then the argument for why there are infinite classes is not valid?