# Given an anti-chain of the powerset of a finite set, is there a disjoint maximal chain?

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?

• I don't know if this is of any interest to you, but I extended my answer to cover the case where $X$ is an infinite set.
– bof
Oct 29, 2018 at 7:15

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$$.