I'm trying to prove "Dilworth's theorem" using Pigeonhole principle.
Definitions
Let $ (X,\le)$ be a partially ordered set, it means:
- $\forall x \in X: x\le x$
- $\forall x ,y\in X: x\le y,y\le x\implies x=y$
- $\forall x ,y,z\in X: x\le y,y\le z\implies x\le z$
A chain is a $A\subseteq X$ s.t $\forall a\ne b \in A: a\le b \ \vee \ b \le a$.
An anti-chain is a $B \subseteq X$ s.t $\forall a\ne b \in A: (a,b) \notin \le $ (every two different elements are not comparable)
The theorem
Let's say $ (X,\le)$ is a partially ordered set of size $n^2+1$. Prove there is a chain or an anti-chain of size $n+1$.
My attempt
We need to use the PHP.A naive way is to set - pigeons $:=$ chains of size $i$ (subsets of $X$ which are chains). I'm not sure how to continue.
Can you help me to continue/finish the proof, please? (if you do, I'd like to know also the explanation "behind" figuring it out)