Proof of Dilworth's theorem using PHP

43 Views Asked by At

I'm trying to prove "Dilworth's theorem" using Pigeonhole principle.

Definitions

Let $ (X,\le)$ be a partially ordered set, it means:

  1. $\forall x \in X: x\le x$
  2. $\forall x ,y\in X: x\le y,y\le x\implies x=y$
  3. $\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)