I am reading the proof of Dilworth's theorem which uses induction.I have several doubts regarding the proof and I am looking for explanation.I first tried to resolve those doubts on my own but it seems to be too much difficult without any help as my brain is not so combinatorial.I state the theorem below and give the proof which I read.I will mention where I have doubts.
Theorem(Dilworth,1950)
Let $P$ be a finite poset.Then the maximum size of an antichain in $P$ is equal to the minimum size of a cover of $P$ by disjoint chains.
Proof: Let $M$ and $m$ denote respectively the maximum size of an antichain in $P$ and minimum size of a cover of $P$ by disjoint chains.
It is trivial that $m\geq M$.
Now we will show that $m\leq M$.We proceed by induction on $|P|$.
For $|P|=1$ ,it is trivial as both the sizes are $1$.
Now assume that the result is true for $k<|P|$.
Now,we prove the result for $k=|P|$.
Let $C$ be a maximal chain in $P$.
Case-1: Every antichain in $P\setminus C$ contains at most $M-1$ elements.
So,$P\setminus C$ is a union of $\leq M-1$ disjoint chains by induction hypothesis.
$\implies$ $P$ is a union of $\leq M$ disjoint chains.
So,$m\leq M$.
Case-2:
Assume that $\{a_1,a_2,…,a_M\}=A$ is an antichain in $P\setminus C$.
Define $S^-=\{x\in P:x\leq a_i \text{ for some } i \}$
$S^+=\{x\in P:x\geq a_i \text{ for some } i \}$
Therefore $A\subset S^-$
Because of maximality,the largest element in $C$ is not in $S^-$
So,$|S^-|<|P|$
By induction hypothesis, $S^-$ is the union of $M$ disjoint chains $S_1^-,S_2^-,…,S_M^-$ where $a_i\in S_i^-$ $\color{red}{\text{(Why?)}}$
If $x\in S_i^-$ and $x>a_i$ then since $x\leq a_j$ for some $j$ we would get $a_i<a_j$ which is a contradiction.
Therefore $a_i$ is the maximal element of $S_i^-$ for all $i=1(1)M$
Do,the same for $S^+=\bigcup\limits_{i=1}^M S_i^+$ where $S_i^+\cap S_j^+=\phi$ for all $i\neq j$ and $a_i\in S_i^+$ such that $a_i$ is the minimal element of $S_i^+$
$D_i=S_i^+\cup S_i^-$ is a chain for $i=1(1)M$ observing that $P=S^+\cup S^-$ is the union of disjoint chains $D_i$ where $i=1(1)M$
This is from a note given by our instructor.Can someone explain me the proof so that it becomes crystal clear?Concrete examples at critical points is also welcome.
Addendum
I have tried to provide as much I have understood below.
Clearly,$m\geq M$ because if $\{a_1,a_2,…,a_M\}$ is a maximal antichain and $P=A_1\cup A_2\cup…\cup A_m$ is a cover of $P$ by disjoint chains,then no two $a_i$'s are in the same $A_k$ so,at least $M$ disjoint chains are required.
Now,we have to show,$m\leq M$.
Now to understand Case:1 let us consider the following example:
Let,$X=\{1,2,3\}$ and $P=\mathcal P(X)$.Notice that $M=3$ here.
Now,$C=\{\phi,\{1\},\{1,2\},\{1,2,3\}\}$
Then,$P\setminus C=\{\{2\},\{3\},\{2,3\},\{3,1\}\}$
Antichains in $P\setminus C$ are $\{\{2\},\{3\}\}$ and $\{\{2,3\},\{3,1\}\},\{\{2\},\{3,1\}\}$.
So,we observe that all antichains in $P\setminus C$ contains $\leq 3-1=2$ elements and hence we are in Case:1.
Now,clearly we obtain that $P$ is a union of at most $3$ disjoint chains.So,$m\leq 3=M$.
Now let us come to Case:2 which says that there is an antichain in $P\setminus C$ of size $M$.
Assume that $A=\{a_1,…,a_M\}$ is an antichain in $P\setminus C$.
Let, $S^-=\{x\in P:x\leq a_i$ for some $i\}$
Then,$A\subset S^-$.The explanation is given below:
$x\in A\implies x=a_i\leq a_i$ for some $i\implies x \in S^-$
Now,$C$ is a finite chain and hence it has a largest element say $a$.
Due to maximality of size of $C=\{…,a\}$,$a\notin S^-$.
If $a\in S^-\implies a\leq a_i$ for some $i\implies C\cup \{a_i\}$ is larger chain in size that $C$.
So,$|S^-|<|P|$.
So,we can use the induction hypothesis.
$S^-=S_1^-\cup…\cup S_M^-$ disjoint chains $\color{red}{\text{(Why $M$ chains?It could have been any number $k\geq M$,so why $k>M$ is not possible?)}}$
Where $a_i\in S_i$ .
Because for $i\neq j$, $a_i,a_j$ both cannot be in $S_i$ together or in $S_j$ together.
Now,$a_i$ is (the) maximal element of $S_i^-$.
Because if $x\in S_i^-$ and $x>a_i$ Then since $x\in S_i^-\subset S^-\implies x\leq a_j$ and so,$a_i<a_j$ which is a contradiction.
Doing the same for $S^+$ we can show that $a_i$ is the minimal element of $S_i^+$.
So,$D_i=S_i^-\cup S_i^+=\{….\leq a_i\leq…\}$ is a chain.
For $i\neq j$, $D_i\cap D_j=\phi$.$\color{red}{\text{(Why?)}}$
So, $P=S^+\cup S^-=D_1\cup…\cup D_M$ which is a union of $M$ disjoint chains.
So,$m\leq M$.
Best Answer
You have understood the most part of the proof pretty well.
What is the induction hypothesis? It is the assumption that the result (i.e., Dilworth's theorem) is true for every poset $Q$ such that $\color{red}{|Q|<k}$. More specifically, if a poset $|Q|<k$, then the maximum size of an antichain in $Q$ is equal to the minimum size of a cover of $Q$ by disjoint chains.
Since $|S^-|<|P|=k$, by the induction hypothesis, the maximum size of an antichain in $S^-$ is equal to the minimum size of a cover of $S^-$ by disjoint chains.
Since $S^-\subset P$, the maximum size of an antichain in $S^-$ is $\le$ the maximum size of an antichain in $P$, which is $M$.
On the other hand, the maximum size of an antichain in $S^-$ is $\ge M$, the size of antichain $A\subset S^-$.
Hence, the maximum size of an antichain in $S^-$ is $M$.
Hence, $M$ is equal to the minimum size of a cover of $S^-$ by disjoint chains. That is, $S^-$ is a union of $M$ disjoint chains.
$D_i=S_i^-\cup S_i^+$
$D_j=S_j^-\cup S_j^+$
For the sake of contradiction, suppose $c\in D_i\cap D_j$. Since $c\in D_i$, there are two cases.
Since $S_i^-$ and $S_j^-$ are disjoint, $c\in S_j^+$.
By definition of $S_i^-$, $c\le a_i$.
By definition of $S_j^+$, $c\ge a_j$.
Hence $a_j\le c \le a_i$, which says $a_i$ and $a_j$ are comparable. A contradiction.
Since $S_i^+$ and $S_j^+$ are disjoint, $c\in S_j^-$.
By definition of $S_i^+$, $c\ge a_i$.
By definition of $S_j^-$, $c\le a_j$.
Hence $a_i\le c \le a_j$, which says $a_i$ and $a_j$ are comparable. A contradiction.
Hence, there is no such $c$. So $D_i\cap D_j=\emptyset$
In fact, it is unnecessary to prove $D_i\cap D_j=\emptyset$. If $P$ is a union of $M$ chains, $P$ is also a union of $M$ or less disjoint chains, since we can keep removing any shared element from one of the sharing pair until there is no intersecting pair. In other words, the minimum size of a cover of $P$ by disjoint chains is the same as the minimum size of a cover of $P$ by chains.