## 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 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. 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, so $i\le j$ and (since $i\ne j$) in fact $i.

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.