580 -Some choiceless results (2)

There are a few additional remarks on the Schröder-Bernstein theorem worth mentioning. I will expand on some of them later, in the context of descriptive set theory.

The dual Schröder-Bernstein theorem (dual S-B) is the statement “Whenever are sets and there are surjections from onto and from onto then there is a bijection between and .”

* This follows from the axiom of choice. In fact, is equivalent to: Any surjective function admits a right inverse. So the dual S-B follows from choice and the S-B theorem. 

* The proofs of S-B actually show that if one has injections and , then one has a bijection contained in . So the argument above gives the same strengthened version of the dual S-B. Actually, over , this strengthened version implies choice. This is in Bernhard Banaschewski, Gregory H. Moore, The dual Cantor-Bernstein theorem and the partition principle, Notre Dame J. Formal Logic 31 (3), (1990), 375-381. 

* If is onto, then there is 1-1, so if there are surjections in both directions between and , then and have the same size. Of course, this is possible even if and do not.

Open question. () Does the dual Schröder-Bernstein theorem imply the axiom of choice?

* The dual S-B is not a theorem of .

a) The example , in Solovay’s model (or under determinacy) shows that the dual S-B is not a theorem of . 

[Let me expand some on this example. There is a definable bijection , so (by Schröder-Bernstein) , where means that there is a bijection between and . Clearly, , where means that there is an injection from into . But also , since .

There is a bijection between and ; for example, we can identify the sequence with the real .

Finally, its is easy to check that , for example, using that any countable dense subset of is isomorphic to , and appealing again to the Schröder-Bernstein theorem.

It follows that .

There is a surjection . For example, if the real is an irrational in , then it corresponds to a sequence . Set for all , let be the relation and let be the field of , i.e, . Then the real encodes this way a structure . If this structure happens to be a well-order, it is isomorphic to a unique ordinal , and we say that the real codes . If is not a well-order, or if is not in , we say that codes 0. This is a surjection from onto .

It follows that there is a surjection from onto (map onto , and compose with the surjection just described), and there is also a surjection , namely, the projection onto the first coordinate.

So far, we have just worked under . Assume now that , i.e., there is no injective -sequence of reals. This holds in Solovay’s model, and also under determinacy. Then there can be no bijection between and .] 

Since Solovay’s model requires an inaccessible cardinal, this example may lead one to wonder whether in consistency strength one needs an inaccessible for an example.

b) One does not; an example has been found by Benjamin Miller, the details of this and what follows are in the note I am attaching here (from September, 2008); they require a stronger background in descriptive set theory than I am assuming in lecture:

Miller’s example holds in Solovay’s model but actually one only needs the Baire property of all sets of reals (and Shelah showed this is equiconsistent with ). Take and , where iff . Then the map which sends to is a surjection from onto . To get a surjection from onto , let denote the set of points of the form , where is in . Send each equivalence class in to the unique element of in , and send each point of to .

It remains to check that there is no bijection between and . If there was, then we could use the lexicographic order on and the bijection to get a linear ordering of , and since we are assuming that all sets of reals have the Baire property, this would contradict the well-known fact that there is no linear ordering of which has the Baire property when thought of as a subset of .

(This latter fact is proven as follows: If is such an ordering, then for each equivalence class , either

• Comeagerly many classes are , or 
• Comeagerly many classes are , 

by generic ergodicity. Another application of generic ergodicity then gives that either

1. Comeagerly many classes are comeagerly many classes, or 
2. Comeagerly many classes are comeagerly many classes. 

The Kuratowski-Ulam theorem then implies that both 1. and 2. hold, thus there is an -invariant comeager set such that , for all , which contradicts the fact that is a partial order.)

c) In example a) there is an injection from into . In example b) there is an injection from into ; one can use the above to build this injection, or appeal to Silver’s theorem. This may lead one to wonder whether in any example and are always comparable. That is not the case; and Miller’s note addresses this:

One can find a model in which there are Borel equivalence relations and on Polish and such that there is no injection from to or from to . For example, and work; one can check that if is comeager, then there is no Baire measurable reduction of to . This gives that there is no injection of the quotient by into the quotient by in any model of all sets of reals have the the version of uniformization for subsets of the plane given in Saharon Shelah, Can you take Solovay‘s inaccessible away?, Israel J. Math. 48 (1), (1984), 1-47. So the consistency of this example follows from that of .

(However, no pair of countable Borel equivalence relations have this property, although if one does not care about consistency strength and uses Lebesgue measurability instead of Baire category, then one can find countable Borel.) 

To see that this works, one simply has to observe that, essentially, by Silver’s theorem, if and are any two Borel equivalence relations on Polish spaces and , and has uncountably many equivalence classes, then there is a homomorphism from to whose graph is Borel (when viewed as a subset of ); this follows for example from results of Alexander Kechris, Alain Louveau, The classification of hypersmooth Borel equivalence relations, J. Amer. Math. Soc. 10 (1), (1997), 215-242.

* Finally, the Partition principle is the statement that if there is a surjection then there is an injection . So the axiom of choice implies the partition principle and the partition principle implies the dual S-B. It is open whether either implication is reversible. But if one thinks about example a), one sees that if the dual S-B holds then, for example, whenever is a set and is equipotent to then whenever there is a surjection from onto a set , then there is an injection from into , so a weak version of the partition principle holds.

4. Zermelo’s well-ordering theorem.

Here I follow the nice article Akihiro Kanamori, The mathematical import of Zermelo’s well-ordering theorem, The Bulletin of Symbolic Logic, 3 (3), (1997), 281-311, available here.

Theorem. If  then there is a unique well-ordering , , such that 

1. , and 
2. .

Proof. There are two (essentially equivalent) ways of showing this. Assuming that the theory of ordinals has been developed, one simply notices that where for all , and is largest such that the map given by is injective. That exists is a consequence of Hartog’s theorem (to be presented in the next lecture) that for any set there is a least ordinal that does not inject into . It follows from this that there is a least such that defined as above is injective, but has already been listed as for some .

Another way of presenting this argument, without the need for the prior development of the theory of the ordinals is to argue as Zermelo originally did, in his 1904 paper (prior to Von Neumann’s result that each well-ordering is isomorphic to a unique ordinal). Say that is an -set iff there is a well-ordering or such that for all , . One then argues (by considering least counterexamples) that any two -sets are comparable, in that one is an initial segment of the other. In particular, the well-ordering associated to an -set is unique. It follows from this that is itself an -set, and is as wanted, for if , then would also be an -set.

Corollary. If admits a choice function, then is well-orderable.

Proof. Let be a choice function, so for all . Let for , and notice that if , then . Let now be as in Zermelo’s theorem. Then (and therefore is well-orderable), since .

Corollary. If , then (definably from ) there is a pair of distinct subsets of such that .

Contrast this with the proof of the `dual’ version of Cantor’s theorem given in the previous lecture, in which we defined from  a set for which there is another set with , but we failed to define some such .

Proof. Let be as in Zermelo’s theorem, and set , , and .

Corollary. Given a set , set denote the collection of well-orderable subsets of , and let denote the collection of relations that are well-orderings of their field. Then and .

Advertisement