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

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:

$F(S_0)$ is the intersection of finitely many sets $A_n$ ,
$F(S_0)\ne\emptyset$ , and
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.

This entry was posted on Thursday, November 15th, 2012 at 4:11 pm and is filed under 580: Topics in set theory. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

2 Responses to Dedekind infinite power sets

Asaf Karagila says:

November 19, 2012 at 11:01 am

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

Reply
- Asaf Karagila says:
  
  November 22, 2012 at 2:32 pm
  
  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$ .
  
  Reply

	ปั่นสล็อต on 414/514 The theorems of Rieman…
	Richard Kimberly Hec… on Woodin’s proof of the se…
	Is there a Borel-mea… on 414/514 Examples of Baire clas…
	Simple bijectiveness… on 580 -Some choiceless results…
	Schur’s theore… on 580 -III. Partition calcu…
	Uncountable linearly… on 403/503 – Homework …
	What is a non-constr… on On strong measure zero se…
	function from Nmathb… on Hindsight
	Cauchy Schwarz Inequ… on 275 -Positive polynomials
	What is a Cantor-sty… on 580 -Some choiceless results…
	Question about Gener… on 580 -Some choiceless results…
	Set has Measure Zero… on On strong measure zero se…
	Non-measurable subse… on 580 -Cardinal arithmetic …
	hmeng1 on 414/514 The theorems of Rieman…
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …

A kind of library