## Dedekind infinite power sets

November 15, 2012

Write $A\preceq B$ to indicate that there is an injection from $A$ into $B$, and $A\preceq^* B$ to mean that either $A=\emptyset$, or else there is a surjection from $B$ onto $A$. It is a result of Kuratowski that (provably in $\mathsf{ZF}$) if $\omega\preceq\mathcal P(X)$, then in fact $\omega\preceq^* X$, and therefore $\mathcal P(\omega)\preceq \mathcal P(X)$. This appears as Théorème B in pages 94-95 of

Alfred Tarski. Sur les ensembles ﬁnis, Fund. Math. 6 (1924), 45–95.

To prove this result, note that it suffices to find a countably infinite family of disjoint subsets of $X$. Suppose $(m_n\mid n<\omega)$ is an injection of  $\omega$ into $\mathcal P(X)$. These sets induce a partition of $X$: Consider the equivalence classes of the relation $x\sim y$ iff

$\forall n(x\in m_n\Longleftrightarrow y\in m_n)$.

It is natural to attempt to show that these equivalence classes can be enumerated. Of course, the class of $x$ is completely specified by the list of values of $n$ such that $x\in m_n$, but this list may be “wasteful” in the sense that it may contain redundant information. For example, if $m_3\subsetneq m_{27}$, and we know that $x\in m_3$, then we automatically know that $x\in m_{27}$, and there is no need to include $27$ in our list if we already included $3$. (On the other hand, if all we know is that $x\in m_{27},$ then including $3$ in the list is certainly providing us with more information.) This suggests to assign to each $x\in X$ the set $F(x)=\{n_0,n_1,\dots\}\subseteq\omega$ defined recursively as follows: Let $n_0$ be least such that $x\in m_{n_0}$, if it exists. If $n_0$ is defined, let $n_1>n_0$ be least such that $x\in m_{n_1}$ and $m_{n_1}\not\supset m_{n_0}$, if it exists, and note that this is the same as requiring that $m_{n_1}\cap m_{n_0}\subsetneq m_{n_0}$. Similarly, if $n_1$ is defined, let $n_2>n_1$ be least such that $x\in m_{n_2}$, and $m_{n_2}\cap m_{n_1}\cap m_{n_0}\subsetneq m_{n_1}\cap m_{n_0}$, if it exists, etc.

Clearly, for any $x,y\in X$, $x\sim y$ iff $F(x)\sim F(y)$. There are now two possibilities:

• Case 1. For some $x$, the set $F(x)$ is infinite.

In this case, we are done (and we do not even need to bother enumerating the classes), because the sequence

$m_{n_0}\setminus m_{n_1}, (m_{n_0}\cap m_{n_1})\setminus m_{n_2},(m_{n_0}\cap m_{n_1}\cap m_{n_2})\setminus m_{n_3},\dots$

is a countably infinite collection of non-empty disjoint subsets of $X$.

• Case 2. All sets $F(x)$ are finite.

In this case we are done as well, because there is a (canonical) bijection between $\omega$ and $\text{Fin}(\omega)$, which means that we have enumerated the equivalence classes (and, of course, there are infinitely many, since the sets $m_n$ are all distinct, and each is a union of equivalence classes).