"Infinite Sperner's Theorem"

96 Views Asked by At

Sperner's theorem gives the size of a maximal antichain in $\mathcal{P}(X)$ where $X$ is a finite set.

In this, "antichain" means a set of mutually incomparable subsets (i.e. subsets such that for any two $A,B$ of them, neither $A\subseteq B$ nor $B\subseteq A$).

There must be a generalization of this to infinite sets: how is the cardinality of the maximal antichain in $\mathcal{P}(X)$ related to the cardinality of $X$? In particular, for infinite $|X|$, is it $2^{|X|}$? Is it a known statement? Is it perhaps trivial?

1

There are 1 best solutions below

0
On BEST ANSWER

Assuming the axiom of choice, if $X$ is infinite then $\mathcal{P}(X)$ has an antichain (with respect to inclusion) of size $2^{\vert X\vert}$ (which is obviously as large as possible).

Here's one way to prove this. For $A\subseteq X$, let $$\hat{A}=\{(x,1): x\in A\}\cup\{(x,0): x\not\in A\}.$$ Note that if $A$ and $B$ are distinct subsets of $X$, the sets $\hat{A}$ and $\hat{B}$ are inclusion-incomparable subsets of $X\times\{0,1\}$.

Now via the axiom of choice, since $X$ is infinite there is a bijection $f: X\times\{0,1\}\rightarrow X$. We use $f$ to "push through" the hat construction above to get a family of subsets of $X$. Specifically, for $A\subseteq X$ let $A'=\{f(i): i\in \hat{A}\}.$ It's easy to check that the family of subsets of $X$ $$\{A': A\subseteq X\}\subseteq\mathcal{P}(X)$$ is an antichain with respect to $\subseteq$ and has cardinality $2^{\vert X\vert}$.