580 -Some choiceless results (4)

Let me begin with a remark related to the question of whether \aleph(X)\preceq {\mathcal P}^2(X). We showed that this is the case if X\sim Y^2 for some Y, or if X is Dedekind-finite.

Theorem. The axiom of choice is equivalent to the statement that any Dedekind-infinite cardinal is a square.

Proof. Let X be a set. Assuming that every D-infinite cardinal is a square, we need to show that X is well-orderable. We may assume that \omega\preceq X. Otherwise, replace X with X\cup\omega. Let \kappa=\aleph(X). Assume that X\sqcup\kappa is a square, say X\sqcup\kappa\sim Y^2. Then \kappa\preceq Y^2. By Homework problem 2, \kappa\preceq Y, so Y\sim \kappa\sqcup Z for some Z, and X\sqcup \kappa\sim Y^2\sim\kappa^2\sqcup 2\times\kappa\times Z\sqcup Z^2\succeq\kappa\times Z.

Lemma. Suppose A,B,C are D-infinite sets and \lambda is an (infinite) initial ordinal. If \lambda\times A\preceq B\cup C then either \lambda\preceq B or A\preceq C.

Proof. Let f:\lambda\times A\to B\sqcup C be an injection. If there is some a\in A such that f(\cdot,a):\lambda\to B we are done, so we may assume that for all a\in A there is some \alpha\in\lambda such that f(\alpha,a)\in C. Letting \alpha_a be the least such \alpha, the map a\mapsto f(\alpha_a,a) is an injection of A into C. {\sf QED}

By the lemma, it must be that either \kappa\preceq X or else Z\preceq\kappa. The former is impossible since \kappa=\aleph(X), so Z is well-orderable, and thus so is Y, and since Y\sim Y^2\succeq X, then X is well-orderable as well. {\sf QED}

9. k-trichotomy.

This is a very recent result, see David Feldman, Mehmet Orhon, Generalizing Hartogs’s trichotomy theorem, preprint (2008), available at the ArXiv.

[Update, January 1, 2013: Asaf Karagila recently pointed out that the result is due to Tarski. It appears as principle T_3(n) on page 22 of “Equivalents of the Axiom of CHoice. II” by Rubin and Rubin, and was announced by Tarski (with a sketch of the argument) in the Notices of AMS, vol. 11, 1964.]

Definition. Trichotomy is the statement that any two sets are comparable.

Theorem. (Hartogs). Trichotomy is equivalent to choice.

Proof. If choice holds, any set is equipotent with an ordinal, and any two ordinals are comparable.

Conversely, if any two sets are comparable, in particular X and \aleph(X) are. Since \aleph(X)\not\preceq X, we must have X\preceq\aleph(X), and we are done. {\sf QED}

Definition. Let 2\le k<\omega. k-trichotomy is the statement that given any k sets, at least two are comparable.

Theorem. For any 2\le k<\omega, k-trichotomy is equivalent to choice. 

Proof. (Blass). Assume k-trichotomy. Let X be a set. We want to show that X is well-orderable. Let Q(X)=X\times{\mathcal P}(X).

Lemma. Let \kappa be an initial ordinal. If Q(X)\preceq X+\kappa, then X is well-orderable.

Here, + is to be understood as disjoint union.

Proof. Let f:Q(X)\to X+\kappa be 1-1. For each x, since {\mathcal P}(X) does not inject into X, it must be the case that the range of f(x,\cdot) meets \kappa. Let \alpha_x be the least member of this intersection. Then x\mapsto\alpha_x is an injection of X into \kappa. {\sf QED}

Remark. If X\sim X+X, then {\mathcal P}(X)\preceq Q(X)\preceq{\mathcal P}(X)\times{\mathcal P}(X)\sim{\mathcal P}(X+X)\sim {\mathcal P}(X), and it follows that {\mathcal P}(X)\sim Q(X). However, it is not necessarily the case that X\sim X+X for X infinite. For example, this fails if X is D-finite. 

Question. If {\mathcal P}(X)\preceq X+\kappa for some initial ordinal \kappa, does it follow that X is well-orderable?

Define a sequence of k cardinals, \kappa_0(X,k),\dots,\kappa_{k-1}(X,k) as follows: 

  • \kappa_0=\kappa_0(X,k)=\aleph(Q^{k-1}(X)).
  • \kappa_{i+1}=\kappa_{i+1}(X,k)=\aleph(Q^{k-i-1}(X)+\kappa_i).

(Then \kappa_0<\kappa_1<\dots)

We claim that if X is not well-orderable, the set \{Q^{k-i-1}(X)+\kappa_i:i<k\} contradicts k-trichotomy. Or, positively, k-trichotomy applied to this set implies the well-orderability of X. Because if i\ne j and there is an injection Q^{k-i-1}(X)+\kappa_i\to Q^{k-j-1}(X)+\kappa_j, then in particular \kappa_i\preceq Q^{k-j-1}(X)+\kappa_j. If j=k-1, then i<j. Otherwise, \kappa_{j+1} is defined, and \kappa_i<\kappa_{j+1} (since \kappa_{j+1} is the aleph of the set that \kappa_i injects into). Since the sequence of cardinals \kappa_n is increasing, we must have i<j+1, so i\le j and (since i\ne j) in fact i<j.

Let Y=Q^{k-j-1}(X). Then X\preceq Y\prec Q(Y)\preceq Q^{j-i}(Y), using that j>i. Also, Q^{j-i}(Y)=Q^{k-i-1}(X)\preceq Q^{k-i-1}(X)+\kappa_i\preceq Q^{k-j-1}(X)+\kappa_j, by assumption. But Q^{k-j-1}(X)+\kappa_j=Y+\kappa_j, and we have that Q(Y)\preceq Y+\kappa_j. By the lemma, Y is well-orderable and we are done, since X injects into Y. {\sf QED}

Open question. With the obvious definition, does \omega-trichotomy imply choice? 

Let \infty-trichotomy be the statement that any infinite family of sets contains two that are comparable. 

Open question. Does \omega-trichotomy imply \infty-trichotomy? Does \infty-trichotomy imply choice?

10. The generalized continuum hypothesis.

The last topic of this part of the course is Specker’s theorem that {\sf GCH} implies {\sf AC}.

Definition. Let {\mathfrak m} be a cardinal. The continuum hypothesis for {\mathfrak m}, {\rm CH}({\mathfrak m}), is the statement that for any cardinal {\mathfrak n}, if {\mathfrak m}\le {\mathfrak n}\le 2^{\mathfrak m}, then either {\mathfrak n}={\mathfrak m} or else {\mathfrak n}=2^{\mathfrak m}.

Definition. The Generalized Continuum Hypothesis, {\sf GCH}, is the statement that {\rm CH}({\mathfrak m}) holds for all infinite cardinals {\mathfrak m}.

Theorem. (Specker). {\sf GCH} implies {\sf AC}, the axiom of choice.

Remark. In fact, it suffices that {\sf GCH} holds for all infinite initial ordinals. I am not sure who first proved this; it is a consequence of a result of Kanamori and Pincus in the paper mentioned last lecture.

Specker’s result is in fact a local argument. What one proves is the following:

Theorem. Assume {\rm CH}({\mathfrak m}) and {\rm CH}(2^{\mathfrak m}). Then 2^{\mathfrak m} is well-orderable and, in fact, 2^{\mathfrak m}=\aleph({\mathfrak m}).

Next lecture will be devoted to the proof of this result.

2 Responses to 580 -Some choiceless results (4)

  1. […] , so, if has size , then is equipotent with , as shown on lecture 4, section 9 (remark after the proof of the first […]

  2. […] , so, if has size , then is equipotent with , as shown on lecture 4, section 9 (remark after the proof of the first […]

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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: