prove that a partially ordered set of elements mn+1 has a chain of size m+1 or antichain of size n+1

Question

Theorem Required.

Not sure how to solve this problem,my idea is to suppose that such antichain exist and construct a chain, and suppose that a chain exist a prove and create such antichain. not sure if this is going to work

Answer 1

Suppose the largest chain in $X$ is of size $r$ and the largest antichain is of size $s$. By Theorem 5.6.1, $X$ can be partitioned into $r$ antichains $C_1, C_2,\ldots, C_r$.

Since they form a partition of $X$, $$|C_1| + |C_2| + \cdots + |C_r| = |X|$$ and since the largest antichain in $X$ is of size $s$, we know each $|C_i|\le s$, so $$|X| = |C_1|+|C_2|+···+|C_r| ≤ sr.$$

If both $s \le n$ and $r \le m$, then $|X| \le sr \le mn$, contradicting the fact that $|X|=mn+1$.

Thus, either $s\ge n+1$ or $r\ge m+1$.