Given an infinite poset, show that it contains either a infinite chain or an infinite totally unordered set. [duplicate]

Solution 1:

I’m assuming that by totally unordered set you mean an antichain.

Let $\langle P,\preceq\rangle$ be your poset, and let $P_0$ be a countably infinite subset of $P$. $[P_0]^2$ is the set of two-element subsets of $P_0$. Define a map $c:[P_0]^2\to\{0,1\}$ by setting $c(\{x,y\})=1$ iff $x$ and $y$ are comparable (i.e., $p\preceq q$ or $q\preceq p$), and apply the infinite Ramsey theorem.

Solution 2:

A big edit, due to a flaw in the original post (thanks Mr. Karagila)

Assume no infinite chains exist. IF (edit) there's a maximal size M of any chain. Remove and set aside all bottom elements (x s.t. no y lower than x exists). This subset is totally unordered/anti chain. Repeat M times. The original set is thus partitioned in M disjoint subsets, each totally unordered.

As M finite, at least one subset must be infinite, qed

EDIT. IF there is no upper bound for chain size.

Considering only maximal chains (necessarily finite, possibly overlapping, but that cannot be extended). If there are an infinity of maximal chains (two by two distinct) below some length L*, apply the above argument to the subset represented by their union, done.

So the only concern is the situation where for any finite length there are only a finite number of distinct (maximal) chains of that length. We then have an infinite set of chains of increasing finite lengths (C1, C2, etc), not bounded above.

STEP A. Again, work within the confines of the their union (a subset of the original big set), with the original ordering. Take the set of their bottoms (lowest elements), which exist on account of finiteness. The set of bottoms is unordered (one bottom cannot be smaller than another on account of maximality). If the set of bottoms is infinite, done. If the set of bottoms is finite, so at least one bottom is a bottom to infinite number of distinct (in pair) chains.

Restrict to the union of the chains bounded below by this bottom (B1) MINUS B1 (subset SB1). The intersection of initial chains (C1, C2, etc) with SB1 results again in maximal chains within SB1.

Repeat Step A, resulting either in an infinite set of bottoms or another bottom to an infinite number of chains (B2). Observe that B2>B1.

So, either the process finishes by finding an infinite set of bottoms in a fininite number of iterations of the process, or we create an infinite chain B1 < B2 < B3 < ...

qed.