Are there $\in$-antichains of all cardinalities?

Question

Say that a set $X$ is a $\in$-antichain iff $x\not\in y$ for any $x,y\in X$. Are there $\in$-antichains of cardinality $\mathfrak c$ ? More generally, for any ordinal $\alpha$, is there a $\in$-antichain of cardinality $\alpha$.

Answer 1

Let $\kappa$ be a cardinal, and for each $\xi\in\kappa$ let $A_\xi=\kappa\setminus\{\xi\}$. Then $\{A_\xi:\xi\in\kappa\}$ is an $\in$-antichain of power $\kappa$.

Answer 2

This is similar to Brian M. Scott's answer, but perhaps a bit simpler.

Given any ordinal $\alpha > 0$ the family $\{ \{ \xi \} : \xi \in \alpha \setminus \{ 0 \} \}$ is an $\in$-antichain. (If $\xi , \eta \in \alpha \setminus \{ 0 \}$ are such that $\{ \xi \} \in \{ \eta \}$, then $\{ \xi \} = \eta$, meaning, in particular, that $\{ \xi \}$ is also an ordinal. But the only ordinal $\xi$ such that $\{ \xi \}$ is also an ordinal is $0$, which we have explicitly omitted.)

Answer 3

Yet another proof:

Let $( V_\alpha \mid \alpha \in \operatorname{Ord} )$ be the cumulative hierarchy and for all $x$ let $\operatorname{rk}(x)$ denote the $\in$-rank of $x$, i.e. least $\alpha$ such that $x \in V_{\alpha +1}$. Note that $\operatorname{card}(V_{\alpha+1} \setminus V_\alpha) \ge \alpha$ and that $x \in y$ implies $\operatorname{rk}(x) < \operatorname{rk}(y)$. Thus any subset $X \subseteq V_{\alpha+1} \setminus V_\alpha$ of size $\alpha$ will do.

Answer 4

Without using ordinals at all (in fact, this construction shows that for any set $X$, there is an $\epsilon$-antichain in bijection with $X$; without the axiom of choice, the other answers don't do this):

Suppose I have any family of distinct sets whatsoever, $\{A_i: i\in I\}$. I can turn this into an $\in$-antichain of the same size: let $$B_i=\{\{A_i\}, \{\{A_i\}\}\}.$$ Then each $B_i$ is a set with exactly two elements, each of which has exactly one element; so we never have $B_i\in B_j$.

---

Meanwhile, it's easy to show $B_i=B_j\implies i=j$: suppose $B_i=B_j$. Then we have two possibilities:

• $\{A_i\}=\{A_j\}$, or

• $\{A_i\}=\{\{A_j\}\}$ and $\{\{A_i\}\}=\{A_j\}$.

In the first case, we clearly have $i=j$. In the second case, we have $$\{A_j\}=\{\{A_i\}\}=\{\{\{A_j\}\}\},$$ which contradicts Foundation. Note however that we do need the axiom of Foundation to handle this case: I believe it is consistent with NF that we can have $i\not=j$ but $B_i=B_j$.

---

EDIT: So as a side question, we can ask what set-theoretic axioms we need to prove "there is an $\in$-antichain of every size." Choice and Foundation are the obviously useful ones, but what is necessary? It's not clear that there's a clean answer, but let me note one very weak axiom which is enough:

If there is no "set of all sets," then there are $\in$-antichains of every size.

Proof: Fix any set $X$, and let $y\not\in X$. Then the set $Y=\{\{\{y\}, \{x\}\}: x\in X\}$ is an $\in$-antichain in bijection with $X$. We're using the fact that $y\not\in X$ to argue that $Y$ is in fact an $\in$-antichain, since $y\not\in X$ implies that every element of $Y$ is a two-element set of one-element sets.

Also, note that the only axioms we needed to get this implication (that is, the base theory we work over) were basically extensionality, singleton, and "Cartesian products exist."

Now, that this isn't as strong a result as it seems: there are natural(ish?) set theories which do allow (in fact, require) a set-of-all-sets, such as New Foundations (NF). Still, it's neat.

If this sort of question interests you, you may be interested in Reverse Mathematics! $<$/shamelessplug$>$