1. The -Rado theorem
Large homogeneous sets (of size or larger) can be ensured, at the cost of starting with a larger domain. The following famous result was originally shown by and Rado using tree arguments (with lowered to in the conclusion). We give instead an elementary substructures argument due to Baumgartner, Hajnal and which proves the stronger version. For a cardinal let
Proof: Let and let
Lemma 2 There is such that and
Proof: Start with any with and and inductively build a continuous chain
for so that if then and This is possible since is bounded in by regularity of and
Let Then is as required, by regularity of
Fix as in the lemma. Let
Then is a -complete ideal over i.e.:
- : Notice that since is definable in as the largest cardinal. If then so since
- ; and implies
- If and then : Let witness that Then since Thus, and it witnesses that In particular, since clearly for all
Then so, for some (since is -closed). Fix such We claim that for any such that there is such that and is -homogeneous. This will suffice, because is also -homogeneous (by definition of ) and has order type
To see the claim, it suffices to show, by regularity of that if is -homogeneous, then there is such that is also -homogeneous. Fix such and notice that Let
Then Since But then as witnessed by Since we must have that and in particular there is some
The full version of the -Rado theorem (for partitions of -sets with ) can be obtained by combining this method with the end-homogeneous sets approach, as in the proof of Ramsey’s theorem in Subsection 2.3 of lecture III.1. One can thus show the following:
-Rado also showed that cannot be replaced with in this result. And regarding Theorem 1 from last lecture, one can also prove a more general (non-topological) version:
Theorem 4 (-Dushnik-Miller) Let be regular and let and Then
Proof: Argue as before, and use the same notation. Now and we need either a -homogeneous set of size or an -homogeneous set of order type for some If for some the proof above works, so we can assume that for all Since is -complete, we then have
Let be a witness so and Let so and Then
so and It follows from elementarity (see below) that is unbounded in Since is regular, this means that and, by construction, it is 0-homogeneous and we are done.
To prove that is unbounded, notice that if then
as witnessed, for example, by By elementarity,
so, since was arbitrary,
By elementarity, the same holds in so is unbounded in
Theorem 5 () For any set any ordinal and any nonzero there is some initial ordinal such that
As mentioned in lecture III.2, this version of the -Rado theorem seems to have been rediscovered a few times, by Keisler and Morley in 1967, by Kleinberg and Seiferas in 1973, and by Forster (for finite) in 2007. I follow the elegant presentation from Keisler-Morley, which also seems to give the optimal bounds. The three arguments are rather similar, using the technique of end-homogeneous sets; the lack of choice actually does not affect very much the argument below:
Proof: Let’s begin with some notation.
- A cardinal will mean here an initial ordinal.
- Given a set write for the sup of the cardinals that inject into Note that we only look at cardinals rather than ordinals, so does not necessarily coincide with If is well-orderable, then the notation coincides with the standard usage: is the unique cardinal bijectable with .
- Write for the first cardinal larger than even if this is a finite number.
- Given an infinite cardinal let be the largest cardinal that can be represented as a union of many sets of size Hence, is either or and under choice it coincides with (The case was briefly discussed before Homework problem 7 in lecture II.1.)
- By transfinite recursion, define the numbers for an arbitrary set and ordinal as follows:
- is the least cardinal strictly larger than and at least as large as
- For limit,
Under choice, is the cardinality of the result of iterating many times the power set operation on i.e.,
Let be a set. We will show by induction on that if is an infinite cardinal, then This obviously gives the result.
Note that is well-orderable, as it can be identified in a natural way with a subset of Letting be a coloring, it follows that we may as well assume that The case is now immediate.
Assume and that the result is valid for We now describe a tree construction that gives rise to a large end-homogeneous set. We define for each a function according to the following requirements:
- is an ordinal,
- Whenever there is a such that Note that by 1 this is unique. Denote it by
- If then is the function defined by
Note that conditions 1–4 uniquely specify by a straightforward inductive argument. This is because, by 3, is the domain of iff is defined but does not coincide with any for
Lemma 6 Suppose is an ordinal and Then
Proof: If there is an obvious injection from into the ordinal so we can identify any function with domain with a -sequence of sequences of elements of each of these sequences of length at most Hence, we can identify with a sequence of length at most of elements of
Since there are at most many such sequences.
Since it follows from the lemma that there is some such that Fix such
Let note that and consider the coloring given by
By the induction hypothesis there is a with and an such that is -homogeneous for
It is enough to check that is also -homogeneous for For this, let and let and Then and, from conditions 3 and 4 above, it follows that as well.
Note that this argument also proves Theorem 3 above.
- James Baumgartner, András Hajnal, Stevo , Extensions of the -Rado theorem, in Finite and infinite combinatorics in sets and logic, NATO (1991), 1–18.
- Jerome Keisler, Michael Morley, Elementary extensions of models of set theory, Israel J. Math., 6 (1968) 49–65.
Typeset using LaTeX2WP. Here is a printable version of this post.