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.

This entry was posted on Thursday, January 29th, 2009 at 12:34 am and is filed under 580: Topics in set theory. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

2 Responses to 580 -Some choiceless results (4)

580 -Some choiceless results (5) « Teaching page says:

February 2, 2009 at 2:57 pm

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

Reply
580 -Some choiceless results (5) « A kind of library says:

January 1, 2013 at 3:13 pm

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

Reply

	ปั่นสล็อต on 414/514 The theorems of Rieman…
	Richard Kimberly Hec… on Woodin’s proof of the se…
	Is there a Borel-mea… on 414/514 Examples of Baire clas…
	Simple bijectiveness… on 580 -Some choiceless results…
	Schur’s theore… on 580 -III. Partition calcu…
	Uncountable linearly… on 403/503 – Homework …
	What is a non-constr… on On strong measure zero se…
	function from Nmathb… on Hindsight
	Cauchy Schwarz Inequ… on 275 -Positive polynomials
	What is a Cantor-sty… on 580 -Some choiceless results…
	Question about Gener… on 580 -Some choiceless results…
	Set has Measure Zero… on On strong measure zero se…
	Non-measurable subse… on 580 -Cardinal arithmetic …
	hmeng1 on 414/514 The theorems of Rieman…
	580 -Cardinal arithm… on 580 -Cardinal arithmetic …

M	T	W	T	F	S	S
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

A kind of library