Let $(X, \leq)$ be an infinite poset. Prove that there is an infinite $X' \subset X$ for which holds one of the following:
1) Induced order on $X'$ is linear.
2) $(X', \leq_\mathrm{ind})$ is antichain. (Every two elements in $X'$ are incomparable)
My attempt:
Let's start trying to construct a linearly ordered set $(X', \leq_\mathrm{ind})$ element by element. First we take some element $x_1 \in X$, then we take another $x_2 \in X$ such as $x_1 \leq x_2$ or $x_2 \leq x_1$. Basically, we take an element from $X$, if it is "good" we put it in our chain, otherwise we throw it away. We continue constructing the chain that way. If we do not stop at some finite step, then we are done, we have constructed linearly ordered subset.
If we do stop at some $x_n$ that means that we have finite amount of comparable elements, which means that $X \setminus X'$ is an antichain.
a) I am not sure about the soundness in the last step, could somebody please check it?
b) Can this be proved without a choice function?
Best Answer
If we also require that the infinite chain or anti-chain will be maximal, then we do need the axiom of choice. Indeed Zorn's lemma is a useful tool when finding maximal chains and anti-chains.
There is a choice principle called Hausdorff's maximality principle stating that in every partially ordered set there exists a maximal chain. It too is equivalent to the axiom of choice, so when you negate the axiom of choice you add a partially ordered set without a maximal chain.
For anti-chains there exists a similar principle, which too implies the axiom of choice.
If you just want to find an infinite anti-chain or chain, some axiom of choice may be needed. Indeed there are trees that every branch can be extended, but there is no infinite branch (thus no infinite chain).
On the other hand, there exists a model of ZF assuming some amount of finite choice, in which there exists a partially ordered set which is infinite but has no infinite chains or anti-chains.
The proof is quite complicated, but appears on Jech, The Axiom of Choice as the model given in Theorem 7.11 (p. 107) and in exercise 7.14 (p. 115)
Your proof is fine for the most, assuming the axiom of choice (or at least The Principle of Dependent Choice). However if we only remove a finite number of comparable elements we don't have to have an anti-chain left.
Dichotomy proofs should show that if condition I failed then condition II holds. And indeed, suppose that $X$ is infinite, but every chain is finite. We define a sequence of elements $x_n\in X$ by induction:
Let $x_0\in X$ be an element such that $X_0=\{x\in X\mid x\nleq x_0\land x_0\nleq x\}$ is infinite. If no element has this property, we can use the same induction to define an infinite chain (taking all the elements comparable with $x_0$ instead).
Suppose $x_n$ and $X_n$ were defined, let $x_{n+1}\in X_n$ be such that $X_{n+1}=\{x\in X_n\mid x\nleq x_{n+1}\land x_{n+1}\nleq x\}$ is infinite. If we got stuck at the $n$-th stage (that is $X_{n+1}$ is finite for every $x\in X_n$) then we can define an infinite chain *within $X_n$* by the same induction as in the first step.
I claim that $\{x_n\mid n\in\mathbb N\}$ is an infinite anti-chain. First note that $\ldots\subsetneq X_n\subsetneq X_{n-1}\subsetneq\ldots\subsetneq X$, and $x_n\in X_{n-1}$ and $x_0\in X$. Each $x_n$ defined $X_n$ and those are unique so $x_n\neq x_k$ for $n\neq k$.
Secondly, since $x_k\in X_{k-1}$ if $x_k$ and $x_n$ are comparable and $n<k$ then $x_k\in X_n$ which was defined as a set of elements incomparable with $x_n$ to begin with, therefore we have an infinite anti-chain.