[Updated December 3. The previous proof that there is a canonical bijection for all infinite ordinals was seriously flawed. Thanks to Lorenzo Traldi for pointing out the problem.]
5. Specker’s lemma.
This result comes from Ernst Specker, Verallgemeinerte Kontinuumshypothese und Auswahlaxiom, Archiv der Mathematik 5 (1954), 332-337. I follow Akihiro Kanamori, David Pincus, Does GCH imply AC locally?, in Paul Erdős and his mathematics, II (Budapest, 1999), Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, (2002), 413-426 in the presentation of this and the following result. The Kanamori-Pincus paper, to which we will return next lecture, has several interesting problems, results, and historical remarks, and I recommend it. It can be found here.
Theorem. Assume that . Then .
Proof. Assume otherwise, so there is a set with at least two elements, an , and an injection . Necessarily, (by the second version of Cantor’s theorem), so by switching two values if needed, we may assume that . Now use the argument of the Zermelo’s theorem to find a well-ordering , i.e., and for all , . Moreover, is as large as possible.
Since is injective, it cannot be the case that . Otherwise, , contradicting injectivity of . Thus, the construction of must end because , i.e., is well-orderable. If is finite, then (as shown by, say, induction), so we must have that is infinite. But then , and again we get a contradiction from the second version of Cantor’s theorem.
Of course, strengthening the hypothesis one can find stronger conclusions. Specker’s paper actually shows that if is infinite then, for all finite , one has . This he deduces from the fact that if , then . In the next section we show a recent strengthening of this result (but notice that the hypothesis we use is stronger than simply assuming that is infinite).
6. The Halbeisen-Shelah theorem.
This comes from Lorenz Halbeisen, Saharon Shelah, Consequences of Arithmetic for Set Theory, The Journal of Symbolic Logic, 59 (1), (Mar., 1994), 30-40.
Theorem. Assume that . Then , where denotes the set of finite sequences of elements of .
Proof. Assume otherwise, and let be injective. We use to define a function from the set of well-orderings of infinite subsets of into with the property that if is infinite and well-orders , then .
Assume for now that we have such a function . By assumption, , so . Starting with any element of , we can then argue as in the proof of Zermelo’s theorem, to produce a well-ordering of all of . This is of course a contradiction (since then ).
[In more detail: Given a well-ordering of an infinite subset of , we have , which provides us with a larger well-ordering, namely, put on top of . Starting with a witnessing , we then obtain a well-ordering with and largest among the well-orderable subsets of extending such that for all , . Since for any well-order , the map is injective, and we reach a contradiction as indicated above.]
Now we proceed to find :
Claim. There is a canonical way of associating to a well-ordering of an infinite set a bijection .
Proof. Begin by noticing:
Lemma. There is a canonical bijection for each infinite ordinal .
Proof. Say that an infinite ordinal is an indecomposable ordinal iff whenever then One then shows:
- for all ; in fact, this is equivalent to the indecomposability of .
- There is some ordinal such that where exponentiation is in the ordinal sense. (Equality is possible, in which case is called an number.) In fact, this is also equivalent to the indecomposability of .
- For any ordinal there is a finite sequence and a sequence of non-zero natural numbers such that This is usually called the Cantor canonical form of
To prove the result, argue as follows: Begin with an injection such that
Use to define an injection as follows: Using the third item above, given any ordinals , we can write
where , and are all natural numbers.
It is clear that is an injection. The point of using is that if is some (infinite) indecomposable ordinal, then the restriction of to ordinals in is an injection into
By induction, this gives a canonical bijection for each and, by canonicity, we then have that , and we are done since the Schröder-Bernstein theorem has a constructive proof.
For an infinite well-order with and as above, let is defined and . Since is a subset of , is defined and may or may not belong to . If it does, then there is an such that , and it follows that iff , by definition of . This is a contradiction, and therefore we must conclude that . Hence, is a finite sequence and at least one of its elements is not a member of .
Define to be the element of this sequence with least index which is not in .
Definition. A set is Dedekind-finite (or D-finite) iff is not equipotent with any of its proper subsets. Equivalently, any injection is a bijection.
Of course, under choice, a set is Dedekind-finite if and only if it is finite, but without choice one may have infinite Dedekind-finite sets. Notice that if , as in the hypothesis of the Halbeisen-Shelah result, then is Dedekind-infinite, since is.
Remark. In abstract algebra, a ring is called Dedekind-finite iff for any , implies . This has nothing to do with the set theoretic notion.
Homework problem 1. Show Specker’s result that if then and conclude that if is infinite then, for all finite , one has .
7. Hartogs theorem.
For any set define is 1-1. is called Hartogs function.
Theorem. For all sets , is a set. In fact, it is an ordinal. In fact, it is a cardinal (i.e., an initial ordinal).
Proof. That is a set follows from noticing that it is the surjective image of under the map that sends to zero unless is a well-ordering of its field, in which case for a unique ordinal , and we set . That this is a surjection follows from noticing that any injection induces an with .
Now that we know that is a set of ordinals, to show that it is an ordinal it suffices to notice that it is closed under initial segments, but this is clear: If witnesses , then for any , the map witnesses . Similarly, that is a cardinal follows from noticing that if and then .
We have shown that for any set there is a first ordinal (necessarily, a cardinal) that does not inject into . For example, if there is no -sequence of distinct reals (i.e., if ) as is the case under determinacy, then . Of course, under choice, .
Proof. For an injection, let be the set and notice that uniquely determines (otherwise, reach a contradiction by considering the first such that does not uniquely determine ).
For let is 1-1 and set . This is an injection of into .
One cannot improve the result to . For example, does not necessarily embed into . However, since : simply map to the set of reals coding in the fashion explained in the previous lecture.
I don’t think one can improve the result to , but I don’t know of any references for this, and counterexamples are more difficult to come by. To illustrate the difficulty, we prove the following simple lemma; notice that if , then satisfies the hypothesis, and that if is Dedekind-finite, then .
Lemma. Suppose that either there is such that or is Dedekind-finite. Then .
Proof. Assume first that is Dedekind-finite. We may as well assume that is infinite, or there is nothing to prove. As shown in the next section, , and .
For any , the map is a well-ordering (of its field) isomorphic to is an injection of into . Suppose now that . If is finite, the result is obvious; otherwise, it follows from the observation that holds for any infinite set (this is homework problem 3, below).
Notice that under choice the assumption of the lemma always holds, but in this case we in fact have .
Remark. The axiom of choice is equivalent to the statement: For all ordinals , is well-orderable; a proof can be found on lecture 5. Hence, if choice fails, some is not well-orderable, and by the above, . In Section 10 we will show that if in addition the continuum hypothesis holds for , then as well. An example of this situation occurs under determinacy, where every set of reals has the perfect set property, so the continuum hypothesis holds.
Here are some corollaries of the injection :
Corollary. For any set , and .
Corollary. There is no sequence such that for all , .
Proof. Otherwise, by the previous corollary, would be a strictly decreasing sequence of ordinals.
In the interest of being (reasonably self-contained) remember that the sequence of infinite initial ordinals can be defined in terms of Hartogs function: . Given let At limit stages, simply set where the supremum coincides with the union of the corresponding ordinals.
8. Dedekind-finite sets.
Theorem. A set is D-finite iff .
Proof. Clearly, implies that is Dedekind-infinite. If is injective but not surjectve, and , then the sequence witnesses that .
Corollary. Let be a set and let . Then is D-finite iff is D-finite.
Proof. Clearly, every subset of a D-finite set is D-finite. To see the other direction, if injects into then it injects into one of the copies of (by the pigeonhole principle).
Corollary. If is infinite, then is Dedekind-infinite.
Proof. as witnessed by , where . The assumption that is infinite is used to check (by induction) that no is empty, which immediately gives us that the map is injective.
Homework problem 2. Show that if is a well-ordered cardinal (an initial ordinal) and , then either or . In particular, if and are Dedekind-finite, then so is .
Homework problem 3. Show that for any infinite set , .
Remark. A previous version of this post made use of Gödel’s pairing. Though that’s no longer the case, I recall the definition here: This is a well-ordering of in order-type defined as follows: Given ordinals , set iff
- , or
- and , where is the lexicographic ordering.
One easily checks that is a well-ordering of that is set-like, meaning that the set of predecessors of any pair of ordinals is a set.