Are there uncountable antichains in $\mathcal{P}(\mathbb{N})$

Question

As the title states, I am unsure of how to construct an uncountable antichain in the power set $\mathcal{P}(\mathbb{N})$.

Recall that an antichain is a set $\mathcal{A}\subset\mathcal{P}(\mathbb{N})$ where each element of $\mathcal{A}$ is not a subset of another element of $\mathcal{A}$.

It seems that everything I attempt requires me to assign a property to the "$n$-th set" but that already makes it countable...

Answer 1

Enumerate the (countably many) vertices of the infinite rooted binary tree by $\mathbb{N}$. Then each infinite path of this tree will induce an infinite subset of $\mathbb{N}$. Moreover, two such subsets are not comparable with respect to inclusion (and indeed, the intersection of two such subsets will be finite since two distinct infinite paths in this tree have only finitely many common edges.) Now try to count how many infinite paths there are in the infinite rooted binary tree.

Answer 2

Let $S\subset\mathbb{N}$. Let $$R_S=\{p_s^t:s\in S,t\notin S\}$$, where $p_s$ is the $s^{th}$ prime number.

Answer 3

It is enough to show there exists an uncountable antichain $\mathcal{A} \subset \mathcal{P}(\mathbf{Q})$.

\begin{align*} \mathcal{A} = \{\ [\alpha-1, \alpha] \cap \mathbf{Q} \mid \alpha \in \mathbf{R} \ \} \end{align*}

satisifies such a condition.

Answer 4

Old question, but I thought I'd post my solution too since the $1-1$ correspondence felt more intuitive to me than the other solutions on this page.

Construct the antichain:

$$\mathcal{A} = \{\alpha : \alpha \text{ for each unique } \alpha = \{a : \text{ Either } a = 2n \text{ or } a = 2n - 1 \text{ for each } n \in \mathbb{N}\} \}$$

For the $1-1$ correspondence use the function:

$$f(\alpha) = \{n : n = \frac{a}{2} \text{ for } a \in \alpha \text{ if } a \text{ is even }\}$$

which gives you $1-1$ and onto function $f: \mathcal{A} \rightarrow P(\mathbb{N})$

The intuition is at each pair of even-odd numbers in an element in the antichain, we make a choice whether to include the even or odd number. This is equivalent to making a choice of whether to include an element in $\mathbb{N}$ or not when constructing a subset of $\mathbb{N}$.