Write to indicate that there is an injection from into , and to mean that either , or else there is a surjection from onto . It is a result of Kuratowski that (provably in ) if , then in fact , and therefore . 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 . Suppose is an injection of into . These sets induce a partition of : Consider the equivalence classes of the relation iff
It is natural to attempt to show that these equivalence classes can be enumerated. Of course, the class of is completely specified by the list of values of such that , but this list may be “wasteful” in the sense that it may contain redundant information. For example, if , and we know that , then we automatically know that , and there is no need to include in our list if we already included . (On the other hand, if all we know is that then including in the list is certainly providing us with more information.) This suggests to assign to each the set defined recursively as follows: Let be least such that , if it exists. If is defined, let be least such that and , if it exists, and note that this is the same as requiring that . Similarly, if is defined, let be least such that , and , if it exists, etc.
Clearly, for any , iff . There are now two possibilities:
- Case 1. For some , the set is infinite.
In this case, we are done (and we do not even need to bother enumerating the classes), because the sequence
is a countably infinite collection of non-empty disjoint subsets of .
- Case 2. All sets are finite.
In this case we are done as well, because there is a (canonical) bijection between and , which means that we have enumerated the equivalence classes (and, of course, there are infinitely many, since the sets 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 be a countable collection of distinct subsets of . It suffices to show that there is a countably infinite collection of non-empty pairwise disjoint subsets of . This is certainly the case if there is an infinite descending chain where each is the intersection of finitely many sets . Suppose that this is not the case. We claim that there must exist a set such that:
- is the intersection of finitely many sets ,
- , and
- For all , either or .
In effect, if no such set exists, an easy induction produces a sequence of indices such that for any , , contrary to our assumption. From condition 3., it follows that there is a sequence such that either for all , or for all .
Let , where for each . Then is a countable collection of nonempty sets, all of them disjoint from . We can then iterate the procedure above, and either find a descending sequence of subsets of , or a set satisfying conditions 1-3 with respect to the sets .
Continue this way inductively. Either at some stage some such decreasing sequence of sets is obtained, and we are done, or else, we have built a sequence of nonempty pairwise disjoint subsets of , and again we are done.