I can not understand some steps in Tverberg's proof on Dilworth theorem

166 Views Asked by At

enter image description here

As is shown in the underlined part of the picture above. First, why after $c^+ \not\in S^-$, we can use induction hypothesis? how does it imply $S^-$ contains no antichain of cardinal $m + 1$? Second, why if $x \in S_i^-$, then $x \leq a_j$ for some $j$? I believe $a_j \in A$, it seems $x \parallel a_j$ is possible as well.

1

There are 1 best solutions below

0
On BEST ANSWER

Since $c^+\notin S^-$, we have $c^+\in S\setminus S^-$. The set $S$ is finite, so this implies that $|S^-|<|S|$, and the induction hypothesis therefore applies to $S^-$. (Remember, the induction is on $|S|$, not on $m$.) Every antichain in $S^-$ is an antichain in $S$, and $S$ has no antichain of cardinality $m+1$, so $S^-$ also has no antichain of cardinality $m+1$. Thus, the induction hypothesis does ensure that $S^-$ is the union of $m$ chains, say $S^-=S_1^-\cup\ldots\cup S_m^-$. Moreover, since $\{a_1,\ldots,a_m\}$ is an antichain in $S^-$, each $a_k$ must be in a different chain, and we might as well index the chains so that $a_k\in S_k^-$ for $k=1,\ldots,m$.

Now suppose that $x\in S_i^-$. Then $x\in S^-=\{y\in S:y\le a_j\text{ for some }j\}$, so $x\le a_j$ for some $j$; it’s just the definition of $S^-$.

You didn’t ask, but I’ll finish the argument, just to play safe. We know that $a_i\in S_i^-$, and $S_i^-$ is a chain, so either $a_i<x$, or $x\le a_i$. If $a_i<x$, then $a_i<a_j$, which is impossible, so $x\le a_i$; and $x$ was an arbitrary element of $S_i^-$, so $a_i$ must be the maximum element of $S_i^-$.