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 A,B are sets and there are surjections from A onto B and from B onto A, then there is a bijection between A and B.”

* This follows from the axiom of choice. In fact, {\sf AC} 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 f:A\to B and g:B\to A, then one has a bijection h:A\to B contained in f\cup g^{-1}. So the argument above gives the same strengthened version of the dual S-B. Actually, over {\sf ZF}, 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 j : {}x \to y is onto, then there is k:{\mathcal P}(y)\to {\mathcal P}(x) 1-1, so if there are surjections in both directions between A and B, then {\mathcal P}(A) and {\mathcal P}(B) have the same size. Of course, this is possible even if A and B do not.

Open question. ({\sf ZF}) Does the dual Schröder-Bernstein theorem imply the axiom of choice?

* The dual S-B is not a theorem of {\sf ZF}.

a) The example A={\mathbb R}, B={\mathbb R}\times\omega_1 in Solovay’s model (or under determinacy) shows that the dual S-B is not a theorem of {\sf ZF}

[Let me expand some on this example. There is a definable bijection {\mathbb N}\times{\mathbb N}\leftrightarrow{\mathbb N}, so (by Schröder-Bernstein) (2^{\mathbb N})\times(2^{\mathbb N})\sim(2^{\mathbb N}), where A\sim B means that there is a bijection between A and B. Clearly, 2^{\mathbb N}\preceq{\mathbb N}^{\mathbb N}, where A\preceq B means that there is an injection from A into B. But also {\mathbb N}^{\mathbb N}\preceq 2^{\mathbb N}, since {\mathbb N}^{\mathbb N}\preceq(2^{\mathbb N})^{\mathbb N}\preceq 2^{\mathbb N}.

There is a bijection between {\mathbb N}^{\mathbb N} and (0,1)\setminus{\mathbb Q}; for example, we can identify the sequence (n_0,n_1,\dots) with the real \displaystyle\frac1{(n_0+1)+\frac1{(n_1+1)+\frac1\dots}}.

Finally, its is easy to check that (0,1)\setminus{\mathbb Q}\sim{\mathbb R}, for example, using that any countable dense subset of (0,1) is isomorphic to {\mathbb Q}, and appealing again to the Schröder-Bernstein theorem.

It follows that {\mathbb R}\times{\mathbb R}\sim{\mathbb R}.

There is a surjection {\mathbb R}\to\omega_1. For example, if the real x is an irrational in (0,1), then it corresponds to a sequence (n_0,n_1,\dots). Set n_i=2^{m_i}(2k_i+1)-1 for all i, let R_x be the relation \{(m_i,k_i):i<\omega\} and let A_x be the field of R_x, i.e, A_x={\rm dom}(R_x)\cup{\rm ran}(R_x). Then the real x encodes this way a structure (A_x,R_x). If this structure happens to be a well-order, it is isomorphic to a unique ordinal \alpha, and we say that the real x codes \alpha. If (A_x,R_x) is not a well-order, or if x is not in (0,1)\setminus{\mathbb Q}, we say that x codes 0. This is a surjection from {\mathbb R} onto \omega_1.

It follows that there is a surjection from A={\mathbb R} onto B={\mathbb R}\times\omega_1 (map {\mathbb R} onto {\mathbb R}\times{\mathbb R}, and compose with the surjection just described), and there is also a surjection {\mathbb R}\times\omega_1\to{\mathbb R}, namely, the projection onto the first coordinate.

So far, we have just worked under {\sf ZF}. Assume now that \omega_1\not\preceq{\mathbb R}, i.e., there is no injective \omega_1-sequence of reals. This holds in Solovay’s model, and also under determinacy. Then there can be no bijection between A and B.] 

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 {\sf ZF}). Take A= 2^{\mathbb N} and B=2^{\mathbb N} / E_0, where x E_0 y iff \exists n\forall m\ge n\,(x(m)=y(m)). Then the map which sends x to \null [x]_{E_0} is a surjection from A onto B. To get a surjection from B onto A, let P denote the set of points of the form (x|0) (x|1) (x|2) \dots, where x is in 2^{\mathbb N}. Send each equivalence class C in \null [P]_{E_0}/E_0 to the unique element of C in P, and send each point of B \setminus [P]_{E_0} / E_0 to 0^\infty.

It remains to check that there is no bijection between A and B. If there was, then we could use the lexicographic order on A and the bijection to get a linear ordering of B, 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 2^{\mathbb N} / E_0 which has the Baire property when thought of as a subset of 2^{\mathbb N} \times 2^{\mathbb N}.

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

  • Comeagerly many classes are \le C, or 
  • Comeagerly many classes are \ge C

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

  1. Comeagerly many classes are \le comeagerly many classes, or 
  2. Comeagerly many classes are \ge comeagerly many classes. 

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

c) In example a) there is an injection from {\mathbb R} into {\mathbb R}\times\omega_1. In example b) there is an injection from 2^{\mathbb N} into 2^{\mathbb N}/E_0; one can use the P above to build this injection, or appeal to Silver’s theorem. This may lead one to wonder whether in any example A and B 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 E and F on Polish X and Y such that there is no injection from X/E to Y/F or from Y/F to X/E. For example, E_1 and E_0^{\mathbb N} work; one can check that if C is comeager, then there is no Baire measurable reduction of C / E to (2^\omega)^\omega / F. This gives that there is no injection of the quotient by E into the quotient by F in any model of {\sf ZF} + all sets of reals have the {\sf BP} + 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 {\sf ZF}.

(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 E, F countable Borel.) 

To see that this works, one simply has to observe that, essentially, by Silver’s theorem, if E' and F' are any two Borel equivalence relations on Polish spaces X' and Y', and E' has uncountably many equivalence classes, then there is a homomorphism from X'/E' to Y'/F' whose graph is Borel (when viewed as a subset of X' \times Y'); 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 f:A\to B then there is an injection g:B\to A. 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 x is a set and x\times x is equipotent to x then whenever there is a surjection from x onto a set y, then there is an injection from y into x, 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 F:{\mathcal P}(X)\to X then there is a unique well-ordering (W,<), W\subseteq X, such that 

  1. \forall x\in W\,F(\{y\in W:y<x\})=x, and 
  2. F(W)\in W.

Proof. There are two (essentially equivalent) ways of showing this. Assuming that the theory of ordinals has been developed, one simply notices that W=\{a_\alpha:\alpha<\beta\} where a_\alpha=F(\{a_\gamma:\gamma<\alpha\} for all \alpha<\beta, and \beta is largest such that the map \varphi=\varphi_\beta:\beta\to X given by \varphi(\alpha)=a_\alpha is injective. That \beta 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 X. It follows from this that there is a least \beta such that \varphi_\beta defined as above is injective, but a_\beta has already been listed as a_\alpha for some \alpha<\beta.

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 A\subseteq X is an F-set iff there is a well-ordering < or A such that for all x\in A, F(\{y\in A:y<x\})=x. One then argues (by considering least counterexamples) that any two F-sets are comparable, in that one is an initial segment of the other. In particular, the well-ordering < associated to an F-set A is unique. It follows from this that W=\bigcup\{F\mbox{-sets}\} is itself an F-set, and is as wanted, for if F(W)\notin W, then W\cup\{F(W\} would also be an F-set. {\sf QED}

Corollary. If {\mathcal P}(X) admits a choice function, then X is well-orderable.

Proof. Let G:{\mathcal P}(X)\to X be a choice function, so G(A)\in A for all \emptyset\ne A\subseteq X. Let F(Y)=G(X\setminus Y) for Y\subseteq X, and notice that if Y\ne X, then F(Y)\notin Y. Let now W be as in Zermelo’s theorem. Then W=X (and therefore X is well-orderable), since F(W)\in W. {\sf QED}

Corollary. If f:{\mathcal P}(X)\to X, then (definably from f) there is a pair (A,B) of distinct subsets of X such that f(A)=f(B).

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

Proof. Let (W,<) be as in Zermelo’s theorem, and set A=W, x=F(W), and B=\{y\in W:y<x\}. {\sf QED}

Corollary. Given a set X, set {\mathcal W}(X) denote the collection of well-orderable subsets of X, and let {\mathcal O}(X) denote the collection of relations R\subseteq X\times X that are well-orderings of their field. Then |X|<|{\mathcal O}(X)| and |X|<|{\mathcal W}(X)|. \Box


4 Responses to 580 -Some choiceless results (2)

  1. […] is a rough idea of their argument: Recall from lecture 2 that denotes the set of well-orderings of subsets of so . Define for ordinals by iterating […]

  2. […] of this note have been discussed elsewhere in the blog, sometimes in a different form (see here and here, for example), but I haven’t examined before the equivalence of 5–7 with choice. In the […]

  3. […] is a rough idea of their argument: Recall from lecture 2 that denotes the set of well-orderings of subsets of so . Define for ordinals by iterating […]

  4. […] choice fails.) See this MO question for closely related issues, and links to examples, or see this blog post of […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: