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

Read the rest of this entry »

Advertisement

2 Comments | 580: Topics in set theory | Tagged: , , , | Permalink
Posted by andrescaicedo