5
$\begingroup$

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$
1
  • $\begingroup$ 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. $\endgroup$
    – bof
    Oct 29, 2018 at 7:15

1 Answer 1

5
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.