using diagonal argument to show existence of uncountable antichain

Question

Consider the poset $$(\mathcal{P}(\mathbb{N}),\subseteq)$$

i.e. subsets of the naturals with partial ordering given by set inclusion. An antichain in this poset is a family of sets $\mathcal{F}\subseteq \mathcal{P}(\mathbb{N})$ such that for any distinct $A,B\in \mathcal{F}$, we have $A\not\subseteq B$ and $B\not\subseteq A$.

The objective is to construct an uncountable antichain in this poset. We can represent subsets $A\subseteq \mathbb{N}$ by their indicator sequence $(a_i)_{i\in\mathbb{N}}$, with $a_i=1$ if $i\in A$ and $a_i=0$ if $i\notin A$. Using this representation we can apply a variant of Cantor's diagonal argument to show that given a countably infinite antichain (modulo some conditions), we can always construct a new element that can be added to the original antichain to get a larger antichain.

My question is: how do we use this insight to show that we can get an uncountable antichain?

I've been told to consider a 'maximal' antichain, say $\mathcal{A}$. Then if $\mathcal{A}$ is still countably infinite, we can use the diagonal argument to find an additional element to append to it, which is a contradiction. However I'm unsure 1) what 'maximality' should mean here exactly, and/or 2) why such a 'maximal' antichain should exist.

My guess is that 'maximal' = 'no elements can be appended without losing the antichain property' - but then I am unsure as to why there must exist a maximal antichain.

EDIT: I am aware of other ways to show the existence of such uncountable antichains in $\mathcal{P}(\mathbb{N})$, but I am interested here in understanding this specific approach.

Answer 1

Your understanding of maximal is correct. The existence of a maximal antichain is a straightforward consequence of Zorn’s lemma applied to the set of all antichains in $\wp(\Bbb N)$.

Let $\mathfrak{A}$ be the set of all antichains in $\wp(\Bbb N)$, ordered by inclusion. Let $\mathfrak{C}$ be a chain in $\mathfrak{A}$. That is, $\mathfrak{C}\subseteq\mathfrak{A}$, and for any antichains $\mathscr{A}_0,\mathscr{A}_1\in\mathfrak{C}$, either $\mathscr{A}_0\subseteq\mathscr{A}_1$, or $\mathscr{A}_1\subseteq\mathscr{A}_0$.

• Show that $\bigcup\mathfrak{C}\in\mathfrak{A}$, i.e., that $\bigcup\mathfrak{C}$ is an antichain in $\wp(\Bbb N)$.

Clearly $\bigcup\mathfrak{C}$ is an upper bound for $\mathfrak{C}$ in the partial order $\subseteq$ on $\mathfrak{A}$, so this shows that every chain in $\mathfrak{A}$ has an upper bound in $\mathfrak{A}$. Zorn’s lemma then says that $\mathfrak{A}$ has a maximal element $\mathscr{M}$. $\mathscr{M}$ is an antichain in $\wp(\Bbb N)$, and it is maximal among all such antichains, meaning that if $\mathscr{M}\subseteq\mathscr{A}\in\mathfrak{A}$, then $\mathscr{M}=\mathscr{A}$: $\wp(\Bbb N)$ has no antichain that properly contains $\mathscr{M}$.

And once you have $\mathscr{M}$, the diagonal argument that you sketched will show that $\mathscr{M}$ must be uncountable.