**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

Theorem 1 (-Rado)Let be a regular cardinal and let Then

for all

*Proof:* Let and let

Lemma 2There 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

For let

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:

Theorem 3 (-Rado)Let and for Let and let be an infinite regular cardinal. Then

-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

Let

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

The proofs of Theorems 1 and 3 above require the axiom of choice. However, the proof of Theorem 4 in lecture III.2 requires a choiceless version. I now proceed to establish this version.

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:

- implies
- 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 6Suppose 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.

** Bibliography **

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

[…] generalization of the elementary substructures argument used to prove the -Rado Theorem 1 from last lecture. Together with the argument below, this provides us with a nice, relatively short, purely […]