Dedekind infinite power sets

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 finis, 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).

This argument, though similar to Kuratowski’s original approach, is due to Halbeisen and Shelah, and their approach can be generalized to study other situations. See

Lorenz Halbeisen, and Saharon Shelah. Consequences of arithmetic for set theory, J. Symbolic Logic 59 (1), (1994), 30–40.  MR1264961 (95c:03128).

Kuratowski’s original proof is as follows:

Let S_0=\{A_n\mid n\in\omega\} be a countable collection of distinct subsets of X. It suffices to show that there is a countably infinite collection of non-empty pairwise disjoint subsets of \bigcup_nA_n. This is certainly the case if there is an infinite descending chain B_0\supsetneq B_1\supsetneq \dots where each B_i is the intersection of finitely many sets A_n. Suppose that this is not the case. We claim that there must exist a set F(S_0) such that:

  1. F(S_0) is the intersection of finitely many sets A_n,
  2. F(S_0)\ne\emptyset, and
  3. For all n, either F(S_0)\subseteq A_n or F(S_0)\cap A_n=\emptyset.

In effect, if no such set F(S_0) exists, an easy induction produces a sequence n_0<n_1<\dots of indices such that for any k, \bigcap_{i<k}A_{n_i}\supsetneq\bigcap_{i\le k}A_{n_i}, contrary to our assumption. From condition 3., it follows that there is a sequence m_0<m_1<\dots such that either F(S_0)\subsetneq A_{m_i} for all i, or F(S_0)\cap A_{m_i}=\emptyset for all i.

Let S_1=\{A_i'\mid i<\omega\}, where A_i'=A_{m_i}\setminus F(S_0) for each i. Then S_1 is a countable collection of nonempty sets, all of them disjoint from F(S_0). We can then iterate the procedure above, and either find a descending sequence B_0\supsetneq B_1\supsetneq\dots of subsets of \bigcup S_1, or a set F(S_1) satisfying conditions 1-3 with respect to the sets A_i'.

Continue this way inductively. Either at some stage some such decreasing sequence of sets B_i is obtained, and we are done, or else, we have built a sequence \{F(S_i)\mid i<\omega\} of nonempty pairwise disjoint subsets of \bigcup_nA_n, and again we are done.

2 Responses to Dedekind infinite power sets

  1. Does the result extend immediately to larger aleph numbers? Or do we need to assume some dependent choice holds, and some “inaccessibility”?

    • Well, in the meantime here is a counterexample: Let A be \aleph_1-amorphous in a model where 2^\omega=\aleph_1. Every function from A into a well-ordered codomain must have a countable range, therefore A cannot be surjected onto \omega_1, but A has countably infinite subsets and therefore its power set has a subset of size \aleph_1.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: