Denote by $X^{(r)}$ the subset of $\mathcal{P}(X)$ such that every element has cardinality $r$ where $ 1 \leq r \leq n = |X|$
Suppose we have an antichain $\mathcal{A}$ of the partial ordering of $\mathcal{P}(X)$ by inclusion, that is not of the form $X^{(r)}$ for some $r$. Must there exist then a maximal chain that is disjoint from $\mathcal{A}$?
I am very stuck on this, however I suspect that it is true. I have a two ideas of how one might go about showing this that I can't seem to complete:
For contraposition, we supposed that for an antichain $\mathcal{A}$ we do not have any maximal chains that are disjoint from it. We want to show that $\mathcal{A}$ is then $X^{(r)}$ for some $r$.
I've thought about considering the set $C$ of chains that are disjoint from $\mathcal{A}$, and considering the subset $C' \subset C$ containing all chains of length maximal in $C$. Then we can look at $\mathcal{B} = \{c \in X^{(|C'|)} \mid \exists A \in C' \text{ such that } c \in A\}$. This is the subset of $X^{(|C'|)}$ that contains all the last elements of the chains in $C'$.
My thinking was to either show that $|C'| = n$ or that you can extend some chain in $C'$, contradicting maximality. However, I can't think of a good way to do either of these things.
For contradiction, suppose we have $\mathcal{A}$ an antichain not of the form $X^{(r)}$. Then I wanted to show that there exists a maximal chain that is disjoint from $\mathcal{A}$.
Consider then $\mathcal{A}_r = \mathcal{A} \cap X^{(r)}$. Then we know that $\mathcal{A}_r$ is strictly contained in $X^{(r)}$ for every $r$.
I want to then construct a maximal chain through the gaps in every layer $X^{(r)}$ that is not occupied by $\mathcal{A}$. However, I am also unsure how I might go about proving this.
I wanted to ask if I am on the right track and how I might be able to finish these proofs off. More importantly, is my suspicion that this result is true correct, or is there a counter example that I didn't find?
$\endgroup$ 11 Answer
$\begingroup$The result is correct. Here is a proof.
Let $X$ be a finite set. Suppose $\mathcal A$ is an antichain which meets every maximal chain in $\mathcal P(X)$;
I claim that $\mathcal A=X^{(r)}$ for some $r$. It will be enough to show that, if $\mathcal A\cap X^{(r)}\ne\emptyset$, then $\mathcal A\supseteq X^{(r)}$.
Suppose $\mathcal A\cap X^{(r)}\ne\emptyset$; I have to show that $X^{(r)}\subseteq\mathcal A$. We may assume that $r\gt0$. Consider any set $\{x_1,\dots,x_{r-1},x\}\in\mathcal A\cap X^{(r)}$ and any element $y\in X\setminus\{x_1,\dots,x_{r-1},x\}$. There is a maximal chain $\mathcal C$ containing $\{x_1,\dots,x_{r-1}\}$ and $\{x_1,\dots,x_{r-1},y\}$ and $\{x_1,\dots,x_{r-1},x,y\}$. Now $\mathcal A$ contains some element of $\mathcal C$; since $\mathcal A$ is an antichain, and since the only element of $\mathcal C$ which is incomparable with $\{x_1,\dots,x_{r-1},x\}$ is $\{x_1,\dots,x_{r-1},y\}$, it follows that $\{x_1,\dots,x_{r-1},y\}\in\mathcal A$.
I have shown that, if we take any $r$-element set in $\mathcal A$, and arbitrarily replace one of its elements with another element of $X$, the resulting $r$-element set will also be in $\mathcal A$. Starting with any element of $\mathcal A\cap X^{(r)}$, we can reach any other element of $X^{(r)}$ by replacing one element at a time. Therefore $X^{(r)}\subseteq\mathcal A$. Finally, since $X^{(r)}$ is a maximal antichain in $\mathcal P(X)$, we conclude that $\mathcal A=X^{(r)}$.
P.S. If $X$ is an infinite set, then the only antichains in $\mathcal P(X)$ that meet every maximal chain in $\mathcal P(X)$ are $\{\emptyset\}$ and $\{X\}$. In other words:
Theorem. Let $X$ be an infinite set and let $\mathcal A$ be an antichain in $\mathcal P(X)$ such that $\mathcal A\ne\{\emptyset\}$ and $\mathcal A\ne\{X\}$. Then there is a maximal chain $\mathcal C$ in $\mathcal P(X)$ that is disjoint from $\mathcal A$.
Proof. We may assume that $\mathbb Z\subseteq X$ and that $\mathcal A$ is nonempty. Since $\mathcal A$ is an antichain, from our assumption that $\mathcal A\ne\{\emptyset\}$ and $\mathcal A\ne\{X\}$ it follows that $\emptyset\notin\mathcal A$ and $X\notin\mathcal A$. We consider two cases.
Case 1. Some member of $\mathcal A$ is a finite set.
Thus $\mathcal A\cap X^{(r)}\ne\emptyset$ for some positive integer $r$. Now, if there are sets $A,B\in X^{(r)}$ such that $|A\cap B|=r-1$, $A\in\mathcal A$, and $B\notin\mathcal A$, then we can take a maximal chain $\mathcal C$ extending the chain $\{A\cap B,B,A\cup B\}$, and it will be disjoint from $\mathcal A$. On the other hand, if there are no such sets $A,B$, then starting with one set in $\mathcal A\cap X^{(r)}$ and changing one element at a time, we can see that every element of $X^{(r)}$ belongs to $\mathcal A$. Since $X^{(r)}$ is a maximal antichain, it follows that $\mathcal A=X^{(r)}$, and in particular that every member of $\mathcal A$ is a nonempty finite set. Now let $\mathcal C$ be a maximal chain such that $\{x\in\mathbb Z:x\le n\}\in\mathcal C$ for each $n\in\mathbb Z$; since the only finite member of $\mathcal C$ is $\emptyset$, it follows that $\mathcal C$ is disjoint from $\mathcal A$.
Case 2. Every member of $\mathcal A$ is an infinite set.
Let $\kappa=\min\{|A|:A\in\mathcal A\}$. Choose $A\in\mathcal A$ with $|A|=\kappa$. Since $A\ne X$, we can choose a set $B\subseteq X$ so that $A$ is a proper subset of $B$ and $|B|=\kappa$. Well-order $B$ so that every proper initial segment of $B$ has cardinality less than $\kappa$. The set of all initial segments of $B$ is a chain, which we extend to a maximal chain $\mathcal C$. Now, for each $C\in\mathcal C$, either $|C|\lt\kappa$ or else $A$ is a proper subset of $C$; in either case $C\notin\mathcal A$, so $\mathcal C$ is disjoint from $\mathcal A$.
$\endgroup$
