Comparability of cardinals from Zorn’s lemma

September 26, 2014

One of the basic consequences of the axiom of choice is that any two sets are comparable, that is, there is an injection from one into the other. The standard argument for this uses that choice is equivalent to the well-ordering theorem: One can prove (without choice) that any two well-ordered sets are comparable, and the well-ordering theorem states that any set is well-orderable.

If for some (foolhardy) reason (say, one is teaching an analysis or algebra course) one is interested in the result, but wants to avoid discussing the theory or well-orders, it seems desirable to have a proof based directly on Zorn’s lemma.

A few weeks ago, Sam Coskey and I found ourselves discussing such a proof. It turns out the argument, though not as well-known as may be expected, dates back at least to Chaim Samuel Hönig, and his short note Proof of the well-ordering of cardinal numbers, Proc. Amer. Math. Soc., 5, (1954), 312. MR0060558 (15,690a). It goes as follows: Let the sets A and B be given. Consider the collection of all partial injections f from A into B. That f is partial means that there is a C\subseteq A such that f:C\to B. Order this collection by extension: f\le f' iff f\subseteq f'. This poset satisfies the conditions of Zorn’s lemma, so it admits maximal elements. One easily verifies that, if f is maximal, then A is the domain of f, or B is its range. In either case, this gives us an injection from one of the sets into the other.

A natural extension of the idea allows us to recover that the class of cardinals is not just linearly ordered, but in fact well-ordered, but an additional use of the axiom of choice is needed now (namely, in the form: The product of non-empty sets is non-empty). Suppose first that \mathcal C is a set. We argue that one of the members of \mathcal C injects into all others. The proof is essentially the same as before: Let A\in \mathcal C, and consider the family of all sequences (f_B\mid B\in\mathcal C) such that for some A'\subset A and all B, we have that f_B:A'\to B is injective. This is a partial order under coordinatewise inclusion. Again, Zorn’s lemma applies, so there is a maximal element \vec f=(f_B\mid B\in \mathcal C); call A' the common domain of all the f_B. If A'=A, we are done. Else (and this is where the additional use of choice comes in), for some B, the range of f_B is B: Otherwise, we can pick a'\in A\setminus A' and a sequence (b_B\mid B\in\mathcal C) such that, for all B, b_B\in B\setminus f_B[A']. But then, setting f'_B=f_B\cup\{(a',b_B)\}, we see that (f'_B\mid B\in\mathcal C) contradicts the maximality of \vec f. The result follows: Letting B be such that f_B is onto, we see that B injects into A', and A' injects into all sets in \mathcal C.

Finally, consider a (proper) class \mathcal C. Again, fix A\in\mathcal C. Let \mathcal C' be the collection of subsets of A equipotent to sets in \mathcal C. Since \mathcal C' is a set, the previous analysis applies, and we can find a C\in \mathcal C that injects into all members of \mathcal C that inject into A. It follows that C actually injects into all members of \mathcal C. Otherwise, there is a B\in\mathcal C that C does not inject into. But then B itself injects into C, and therefore into A. But this means that C injects into B after all.

Advertisement

Leave a Comment » | math.LO | Tagged: , , | Permalink
Posted by andrescaicedo

Coming attractions

September 26, 2014

cs

7 Comments | Life | Permalink
Posted by andrescaicedo

414/514 Homework 1 – The reals

September 11, 2014

This set is due in two weeks, on Friday September 26, at the beginning of lecture.

1. Recall that in the construction of the reals via Dedekind cuts, a real is simply the left set of a pair (A\mid B) in a cut of \mathbb Q, that is, a “real” is a set A\subset \mathbb Q that is non-empty, bounded above, closed to the left (meaning, if x\in A, y\in\mathbb Q, and y<x, then y\in A), and such that A has no maximum. We also have a copy \mathbb Q^* of \mathbb Q inside \mathbb R, given by the identification q\mapsto q^*:=\{t\in\mathbb Q\mid t<q\}. We left a few details to be verified when we presented this construction.

Let r be a real (in the sense just described). Define carefully the real -r (meaning, describe -r as a specific set of rationals, and verify that it is a real in the sense under discussion), and verify that -r+r=0, and that -r is the only real with this property.

Define carefully the product rs of reals r and s, and verify that the distributive property holds.

Check that \mathbb R is Dedekind-complete, that is, any cut of \mathbb R is realized. (S0, ignoring the formal difference between \mathbb Q and \mathbb Q^*, this version of \mathbb R is the Dedekind-completion of \mathbb Q, and this gives us that it is also the Dedekind completion of itself. )

2. More generally, define the Dedekind completion of a dense order, and verify its existence and uniqueness (up to isomorphism). In particular, the field \mathbb R(x) of  rational functions admits a completion, call it \hat{\mathbb R}(x). Can we extend the addition operation on \mathbb R(x) so it is defined in all of \hat{\mathbb R}(x) and makes it into an abelian group? Can we extend the order so \hat{\mathbb R}(x) is in fact an ordered group? What, if any, is the problem trying to extend multiplication?

3. Recall that in the construction of the reals via Cauchy sequences, a real is an equivalence class of Cauchy sequences of rationals, under the equivalence relation that states that two Cauchy sequences q_0,q_1,\dots and r_0,r_1,\dots are equivalent iff q_0,r_0,q_1,r_1,\dots is a Cauchy sequence.

Verify that this is indeed an equivalence relation, and that, given equivalent sequences \vec q and \vec r, the resulting interleaving sequence is equivalent to both. Verify that the (pointwise) definitions of addition and multiplication make sense, and that the resulting set equipped with these operations is indeed a field. Define carefully the ordering relation, and prove that it gives us a field ordering. Finally, verify that the resulting ordered field is indeed Dedekind complete.

4. Recall the construction of the reals described in Street’s paper An efficient construction of real numbers. His short note makes many claims that are not proved there. Provide as many of the missing details as possible.

5. Given a linear order (X,<), in the order topology the open sets are (by definition) those subsets of X that are union of (bounded or unbounded) open intervals in X. Show that a linear order (X,<) is order isomorphic to \mathbb R iff the following three properties are verified:

  • X has no first or last elements.
  • X is connected, that is, we cannot write X=A\cup B where A and B are open, nonempty, and disjoint.
  • X is separable, that is, there is a countable subset of X that is dense in X.

 

 

Leave a Comment » | 414/514: Analysis I | Permalink
Posted by andrescaicedo