580 -Some choiceless results (3)

[Updated December 3. The previous proof that there is a canonical bijection $\alpha\sim\alpha\times\alpha$ for all infinite ordinals $\alpha$ was seriously flawed. Thanks to Lorenzo Traldi for pointing out the problem.]

5. Specker’s lemma.

This result comes from Ernst Specker, Verallgemeinerte Kontinuumshypothese und Auswahlaxiom, Archiv der Mathematik 5 (1954), 332-337. I follow Akihiro Kanamori, David Pincus, Does GCH imply AC locally?, in Paul Erdős and his mathematics, II (Budapest, 1999), Bolyai Soc. Math. Stud., 11, János Bolyai Math. Soc., Budapest, (2002), 413-426 in the presentation of this and the following result. The Kanamori-Pincus paper, to which we will return next lecture, has several interesting problems, results, and historical remarks, and I recommend it. It can be found here.

Theorem. Assume that ${\mathfrak m}>1$ . Then ${\mathfrak m}+1<2^{\mathfrak m}$ .

Proof. Assume otherwise, so there is a set $X$ with at least two elements, an $a\notin X$ , and an injection $f:{\mathcal P}(X)\to X\cup\{a\}$ . Necessarily, $a\in{\rm ran}(f)$ (by the second version of Cantor’s theorem), so by switching two values if needed, we may assume that $f(X)=a$ . Now use the argument of the Zermelo’s theorem to find a well-ordering $(W,<)$ , i.e., $W\subseteq X$ and for all $x\in W$ , $f(\{y\in W:y<x\})=x$ . Moreover, $W$ is as large as possible.

Since $f$ is injective, it cannot be the case that $f(W)\in W$ . Otherwise, $f(W)=f(\{y\in W:y<f(W)\})$ , contradicting injectivity of $f$ . Thus, the construction of $W$ must end because $W=X$ , i.e., $X$ is well-orderable. If $X$ is finite, then $|X|+1<2^{|X|}$ (as shown by, say, induction), so we must have that $X$ is infinite. But then $|X|+1=|X|$ , and again we get a contradiction from the second version of Cantor’s theorem. ${\sf QED}$

Of course, strengthening the hypothesis one can find stronger conclusions. Specker’s paper actually shows that if ${\mathfrak m}$ is infinite then, for all finite $n$ , one has $n\cdot{\mathfrak m}<2^{\mathfrak m}$ . This he deduces from the fact that if ${\mathfrak m}\ge5$ , then $2^{\mathfrak m}\not\le{\mathfrak m}^2$ . In the next section we show a recent strengthening of this result (but notice that the hypothesis we use is stronger than simply assuming that ${\mathfrak m}$ is infinite).

6. The Halbeisen-Shelah theorem.

This comes from Lorenz Halbeisen, Saharon Shelah, Consequences of Arithmetic for Set Theory, The Journal of Symbolic Logic, 59 (1), (Mar., 1994), 30-40.

Theorem. Assume that $\aleph_0\le|X|$ . Then $|{\mathcal P}(X)|\not\le|{\rm Seq}(X)|$ , where ${\rm Seq}(X)$ denotes the set of finite sequences of elements of $X$ .

Proof. Assume otherwise, and let $G:{\mathcal P}(X)\to{\rm Seq}(X)$ be injective. We use $G$ to define a function $F$ from the set of well-orderings of infinite subsets of $X$ into $X$ with the property that if $Y\subseteq X$ is infinite and $R$ well-orders $Y$ , then $F(R)\in X\setminus Y$ .

Assume for now that we have such a function $F$ . By assumption, $\omega\preceq X$ , so ${\rm dom}(F)\ne\emptyset$ . Starting with any element of ${\rm dom}(F)$ , we can then argue as in the proof of Zermelo’s theorem, to produce a well-ordering $W$ of all of $X$ . This is of course a contradiction (since then $F(X)\in\emptyset$ ).

[In more detail: Given $<_Y$ a well-ordering of an infinite subset $Y$ of $X$ , we have $F(<_Y)\notin Y$ , which provides us with a larger well-ordering, namely, put $F(<_Y)$ on top of $(Y,<_Y)$ . Starting with a $(Y,<)$ witnessing $\omega\preceq X$ , we then obtain a well-ordering $(W,<)$ with $W\subseteq X$ and $W$ largest among the well-orderable subsets of $X$ extending $Y$ such that for all $x\in W$ , $F(\{y\in W:y<x\})=x$ . Since $F(<_Y)\notin Y$ for any well-order $(Y,<_Y)$ , the map $F$ is injective, and we reach a contradiction as indicated above.]

Now we proceed to find $F$ :

Claim. There is a canonical way of associating to a well-ordering $<$ of an infinite set $Y$ a bijection $H:Y\to{\rm Seq}(Y)$ .

Proof. Begin by noticing:

Lemma. There is a canonical bijection $\alpha\to\alpha\times\alpha$ for each infinite ordinal $\alpha$ .

Proof. Say that an infinite ordinal $\beta$ is an indecomposable ordinal iff whenever $\gamma,\delta<\beta,$ then $\gamma+\delta<\beta.$ One then shows:

$\gamma+\beta=\beta$ for all $\gamma<\beta$ ; in fact, this is equivalent to the indecomposability of $\beta$ .
There is some ordinal $\gamma\le\beta$ such that $\beta=\omega^\gamma,$ where exponentiation is in the ordinal sense. (Equality is possible, in which case $\beta$ is called an $\epsilon$ number.) In fact, this is also equivalent to the indecomposability of $\beta$ .
For any ordinal $\alpha>0$ there is a finite sequence $\alpha_1>\dots>\alpha_k$ and a sequence of non-zero natural numbers $n_1,\dots,n_k$ such that $\alpha=\omega^{\alpha_1}n_1+\dots+\omega^{\alpha_k}n_k.$ This is usually called the Cantor canonical form of $\alpha.$

To prove the result, argue as follows: Begin with an injection $p: \omega\times\omega\to\omega$ such that $p(0,0)=0.$

Use $p$ to define an injection $G: {\sf ORD}\times{\sf ORD}\to{\sf ORD}$ as follows: Using the third item above, given any ordinals $\alpha,\beta$ , we can write

$\alpha= \omega^{\alpha_1}n_1 + \omega^{\alpha_2}n_2 + \dots + \omega^{\alpha_k}n_k$

and

$\beta= \omega^{\alpha_1}n'_1 + \omega^{\alpha_2}n'_2 + \dots + \omega^{\alpha_k}n'_k$

where $\alpha_1 > \alpha_2 > \dots > \alpha_k$ , and $n_1,\dots,n_k, n'_1,\dots,n'_k$ are all natural numbers.

Set $G(\alpha,\beta)= \omega^{\alpha_1}p(n_1,n'_1) + \omega^{\alpha_2}p(n_2,n'_2) + \dots + \omega^{\alpha_k}p(n_k,n'_k).$

It is clear that $G$ is an injection. The point of using $G$ is that if $\alpha=\omega^\beta$ is some (infinite) indecomposable ordinal, then the restriction of $G$ to ordinals in $\alpha\times\alpha$ is an injection into $\alpha.$

We can then use $G$ to define a map $F$ that to each infinite ordinal $\alpha$ assigns a bijection between $\alpha$ and $\alpha\times\alpha:$ First, if $\alpha$ is indecomposable, $G$ gives an injection $\alpha\times\alpha\to\alpha.$ The map from $\alpha$ into $\alpha\times\alpha$ that sends each $\beta$ to $(\beta,0)$ is also an injection. Our explicit proof of the Schröder-Bernstein theorem defines now a bijection $F(\alpha)$ between $\alpha$ and $\alpha\times\alpha.$

Finally, notice that any infinite ordinal $\alpha$ can be written in a unique way as $\alpha=\omega^\beta\cdot n+\gamma,$ where $n\in\omega$ and $\gamma<\omega^\beta.$ There is an obvious bijection between $\omega^\beta+\gamma$ and $\gamma+\omega^\beta=\omega^\beta.$ By induction on $n,$ from the bijection shown above, there is an explicit bijection between $\omega^\beta$ and $\omega^\beta\cdot n.$ It follows that there is an explicit (canonical) bijection between $\alpha$ and $\omega^\beta$ and, therefore, a bijection $F(\alpha)$ between $\alpha$ and $\alpha\times\alpha$ , as we wanted to show. ${\sf QED}$

By induction, this gives a canonical bijection $\alpha\to{}^n\alpha$ for each $0<n<\omega$ and, by canonicity, we then have that $\alpha\preceq{\rm Seq}(\alpha)=\bigcup_n {}^n\alpha\sim\sqcup_n\alpha\sim\alpha\cdot\omega\preceq \alpha\times\alpha\sim\alpha$ , and we are done since the Schröder-Bernstein theorem has a constructive proof. ${\sf QED}$

For $(Y,<)$ an infinite well-order with $Y\subseteq X$ and $H$ as above, let $D=\{x\in Y:G^{-1}(H(x))$ is defined and $x\notin G^{-1}(H(x))\}$ . Since $D$ is a subset of $X$ , $G(D)$ is defined and may or may not belong to ${\rm Seq}(Y)$ . If it does, then there is an $x_0\in Y$ such that $G(D)=H(x_0)$ , and it follows that $x_0\in D$ iff $x_0\notin D$ , by definition of $D$ . This is a contradiction, and therefore we must conclude that $G(D)\notin{\rm Seq}(Y)$ . Hence, $G(D)$ is a finite sequence and at least one of its elements is not a member of $Y$ .

Define $F(<)$ to be the element of this sequence with least index which is not in $Y$ . ${\sf QED}$

Definition. A set $X$ is Dedekind-finite (or D-finite) iff $X$ is not equipotent with any of its proper subsets. Equivalently, any injection $f:X\to X$ is a bijection.

Of course, under choice, a set is Dedekind-finite if and only if it is finite, but without choice one may have infinite Dedekind-finite sets. Notice that if $\omega\preceq X$ , as in the hypothesis of the Halbeisen-Shelah result, then $X$ is Dedekind-infinite, since $\omega$ is.

Remark. In abstract algebra, a ring $R$ is called Dedekind-finite iff for any $a,b\in R$ , $ab=1$ implies $ba=1$ . This has nothing to do with the set theoretic notion.

Homework problem 1. Show Specker’s result that if ${\mathfrak m}\ge5$ then $2^{\mathfrak m}\not\le{\mathfrak m}^2$ and conclude that if ${\mathfrak m}$ is infinite then, for all finite $n$ , one has $n\cdot{\mathfrak m}<2^{\mathfrak m}$ .

7. Hartogs theorem.

For any set $X$ define $\aleph(X)=\{\alpha:\exists f:\alpha\to X\,(f$ is 1-1 $)\}$ . $\aleph(\cdot)$ is called Hartogs function.

Theorem. For all sets $X$ , $\aleph(X)$ is a set. In fact, it is an ordinal. In fact, it is a cardinal (i.e., an initial ordinal).

Proof. That $\aleph(X)$ is a set follows from noticing that it is the surjective image of ${\mathcal P}(X\times X)$ under the map $\pi$ that sends $R$ to zero unless $R$ is a well-ordering of its field, in which case $({\rm field}(R),R)\cong\alpha$ for a unique ordinal $\alpha$ , and we set $\pi(R)=\alpha$ . That this is a surjection follows from noticing that any injection $f:\alpha\to X$ induces an $R$ with $\pi(R)=\alpha$ .

Now that we know that $\aleph(X)$ is a set of ordinals, to show that it is an ordinal it suffices to notice that it is closed under initial segments, but this is clear: If $f:\alpha\to X$ witnesses $\alpha\in\aleph(X)$ , then for any $\beta<\alpha$ , the map $f\upharpoonright\beta$ witnesses $\beta\in\aleph(X)$ . Similarly, that $\aleph(X)$ is a cardinal follows from noticing that if $\alpha\sim\beta$ and $\alpha\in\aleph(X)$ then $\beta\in\aleph(X)$ . ${\sf QED}$

We have shown that for any set $X$ there is a first ordinal (necessarily, a cardinal) that does not inject into $X$ . For example, if there is no $\omega_1$ -sequence of distinct reals (i.e., if $\omega_1\not\preceq{\mathbb R}$ ) as is the case under determinacy, then $\aleph({\mathbb R})=\omega_1$ . Of course, under choice, $\aleph(X)=|X|^+$ .

Theorem. $\aleph(X)\preceq{\mathcal P}^3(X)$ .

Proof. For $f:\alpha\to X$ an injection, let $T_f$ be the set $\{f[\gamma]:\gamma\le\alpha\}=\{ \{f(\beta):\beta<\gamma\}:\gamma\le\alpha\}$ and notice that $T_f$ uniquely determines $f$ (otherwise, reach a contradiction by considering the first $\gamma$ such that $T_f$ does not uniquely determine $f\upharpoonright\gamma$ ).

For $\alpha\in\aleph(X)$ let $A_\alpha=\{f\in{}^\alpha X:f$ is 1-1 $\}$ and set $\pi(\alpha)=\{T_f:f\in A_\alpha\}$ . This is an injection of $\aleph(X)$ into ${\mathcal P}^3(X)$ . ${\sf QED}$

One cannot improve the result to $\aleph(X)\preceq{\mathcal P}(X)$ . For example, $\aleph(\omega)=\aleph_1$ does not necessarily embed into ${\mathcal P}(\omega)\sim{\mathbb R}$ . However, $\omega_1\preceq{\mathcal P}^2(\omega)$ since $\omega_1\preceq{\mathcal P}({\mathbb R})$ : simply map $\alpha<\omega_1$ to the set of reals coding $\alpha$ in the fashion explained in the previous lecture.

I don’t think one can improve the result to $\aleph(X)\preceq{\mathcal P}^2(X)$ , but I don’t know of any references for this, and counterexamples are more difficult to come by. To illustrate the difficulty, we prove the following simple lemma; notice that if $X\sim X^2$ , then $X$ satisfies the hypothesis, and that if $X$ is Dedekind-finite, then $X\not\sim X^2$ .

Lemma. Suppose that either there is $Y$ such that $X\sim Y^2$ or $X$ is Dedekind-finite. Then $\aleph(X)\preceq{\mathcal P}^2(X)$ .

Proof. Assume first that $X$ is Dedekind-finite. We may as well assume that $X$ is infinite, or there is nothing to prove. As shown in the next section, $\aleph(X)=\omega$ , and $\omega\preceq{\mathcal P}^2(X)$ .

For any $Y$ , the map $\alpha\mapsto\{ R\subseteq Y^2:R$ is a well-ordering (of its field) isomorphic to $\alpha\}$ is an injection of $\aleph(Y)$ into ${\mathcal P}^2(Y^2)$ . Suppose now that $X\sim Y^2$ . If $Y$ is finite, the result is obvious; otherwise, it follows from the observation that $\aleph(Y)=\aleph(Y^2)$ holds for any infinite set $Y$ (this is homework problem 3, below). ${\sf QED}$

Notice that under choice the assumption of the lemma always holds, but in this case we in fact have $\aleph(X)\preceq{\mathcal P}(X)$ .

Remark. The axiom of choice is equivalent to the statement: For all ordinals $\alpha$ , ${\mathcal P}(\alpha)$ is well-orderable; a proof can be found on lecture 5. Hence, if choice fails, some ${\mathcal P}(\alpha)$ is not well-orderable, and by the above, $\aleph(\alpha)=|\alpha|^+\preceq {\mathcal P}^2(\alpha)$ . In Section 10 we will show that if in addition the continuum hypothesis holds for $\alpha$ , then $\aleph({\mathcal P}(\alpha))=|\alpha|^+$ as well. An example of this situation occurs under determinacy, where every set of reals has the perfect set property, so the continuum hypothesis holds.

Here are some corollaries of the injection $\aleph(X)\preceq{\mathcal P}^3(X)$ :

Corollary. For any set $X$ , $\aleph(X)<|{\mathcal P}^4(X)|$ and $\aleph(X)<\aleph({\mathcal P}^3(X))$ . $\Box$

Corollary. There is no sequence $(X_n:n<\omega)$ such that for all $n$ , $|{\mathcal P}(X_{n+1})|\le|X_n|$ .

Proof. Otherwise, by the previous corollary, $(\aleph(X_{3n}):n<\omega)$ would be a strictly decreasing sequence of ordinals. ${\sf QED}$

In the interest of being (reasonably self-contained) remember that the sequence $(\aleph_\alpha:\alpha\in{\sf ORD})$ of infinite initial ordinals can be defined in terms of Hartogs function: $\aleph_0=\omega_0=\omega$ . Given $\aleph_\alpha=\omega_\alpha,$ let $\aleph_{\alpha+1}=\omega_{\alpha+1}=\aleph(\aleph_\alpha).$ At limit stages, simply set $\aleph_\alpha=\omega_\alpha=\sup_{\beta<\alpha}\omega_\beta,$ where the supremum coincides with the union of the corresponding ordinals.

8. Dedekind-finite sets.

Theorem. A set $X$ is D-finite iff $\aleph(X)\le\omega$ .

Proof. Clearly, $\omega\preceq X$ implies that $X$ is Dedekind-infinite. If $f:X\to X$ is injective but not surjectve, and $a\in X\setminus f[X]$ , then the sequence $(f^n(a):n\in\omega)$ witnesses that $\omega\preceq X$ . ${\sf QED}$

Corollary. Let $X$ be a set and let $0<n<\omega$ . Then $X$ is D-finite iff $n\cdot X$ is D-finite.

Proof. Clearly, every subset of a D-finite set is D-finite. To see the other direction, if $\omega$ injects into $\sqcup_{i<n}X$ then it injects into one of the copies of $X$ (by the pigeonhole principle). ${\sf QED}$

Corollary. If $X$ is infinite, then ${\mathcal P}^2(X)$ is Dedekind-infinite.

Proof. $\omega\preceq{\mathcal P}^2(X)$ as witnessed by $n\mapsto A_n$ , where $A_n=[X]^n =\{ Y\subseteq X : |Y| =n \}$ . The assumption that $X$ is infinite is used to check (by induction) that no $A_n$ is empty, which immediately gives us that the map is injective. ${\sf QED}$

Homework problem 2. Show that if $\kappa$ is a well-ordered cardinal (an initial ordinal) and $\kappa\preceq A\times B$ , then either $\kappa\preceq A$ or $\kappa\preceq B$ . In particular, if $A$ and $B$ are Dedekind-finite, then so is $A\times B$ .

Homework problem 3. Show that for any infinite set $A$ , $\aleph(A)=\aleph(A^2)$ .

Remark. A previous version of this post made use of Gödel’s pairing. Though that’s no longer the case, I recall the definition here: This is a well-ordering of ${\sf ORD}\times{\sf ORD}$ in order-type ${\sf ORD},$ defined as follows: Given ordinals $\eta,\beta,\gamma,\delta$ , set $(\eta,\beta)<_G(\gamma,\delta)$ iff

$\max\{\eta,\beta\}<\max\{\gamma,\delta\}$ , or
$\max\{\eta,\beta\}=\max\{\gamma,\delta\}$ and $(\eta,\beta)<_{lex}(\gamma,\delta)$ , where $<_{lex}$ is the lexicographic ordering.

One easily checks that $<_G$ is a well-ordering of ${\sf ORD}\times{\sf ORD}$ that is set-like, meaning that the set of $<_G$ predecessors of any pair of ordinals is a set.

This entry was posted on Tuesday, January 27th, 2009 at 3:49 pm 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.

16 Responses to 580 -Some choiceless results (3)

billy hudson says:

January 29, 2009 at 8:23 am

The link for ” For all ordinals $\alpha$ , ${\mathcal P}(\alpha)$ is well-orderable;” links to another class’ homework.

Reply
andrescaicedo says:

January 29, 2009 at 9:21 am

Hi Billy,

Yes, problem 3 is the stated result. The solution of problem 3 (the proof of: ${\sf AC}$ iff for all $\alpha$ , ${\mathcal P}(\alpha)$ is well-orderable) is written there.

Reply
billy hudson says:

January 30, 2009 at 10:21 am

AH. If I’d only bothered to read it . . . 🙂

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

February 2, 2009 at 2:56 pm

[…] where the strict inequality is Specker’s lemma, shown on lecture 3, section 5. By , we have . (In particular, is […]

Reply
andrescaicedo says:

February 6, 2009 at 2:57 pm

I have replaced the link with one to lecture 5 and, in lecture 5, I have added the proof of the result to the notes, to make them more self-contained.

Reply
580 -II. Cardinal arithmetic « Teaching page says:

February 8, 2009 at 11:42 am

[…] is infinite, and the fact that and have the same size, for any infinite ordinal , as shown on lecture 3, lemma in section […]

Reply
580 -Some choiceless results « Teaching blog says:

December 3, 2009 at 5:37 pm

[…] (Dec. 3, 2009). The pdf file still contains an error that was pointed out to me recently. In the third lecture on choiceless results, the correct argument is […]

Reply
andrescaicedo says:

December 3, 2009 at 5:34 pm

Lorenzo Traldi noticed that there was an error in the proof that there is a canonical bijection between $\alpha$ and $\alpha\times\alpha$ for all infinite ordinals $\alpha.$ I have replaced the flawed argument with a correct one.

Reply
580- Specker trees « Teaching blog says:

February 11, 2011 at 9:06 pm

[…] set of all ordinals that inject into , so is the first ordinal that cannot inject. Sierpiński proved that and therefore . This observation gives us immediately that the Specker tree of any set is […]

Reply
580- Specker trees « A kind of library says:

August 27, 2012 at 1:11 pm

[…] set of all ordinals that inject into , so is the first ordinal that cannot inject. Sierpiński proved that and therefore . This observation gives us immediately that the Specker tree of any set is […]

Reply
580 -II. Cardinal arithmetic « A kind of library says:

January 1, 2013 at 3:06 pm

[…] is infinite, and the fact that and have the same size, for any infinite ordinal , as shown on lecture 3, lemma in section […]

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

January 1, 2013 at 3:13 pm

[…] where the strict inequality is Specker’s lemma, shown on lecture 3, section 5. By , we have . (In particular, is […]

Reply
Yu Mika says:

February 16, 2019 at 5:06 am

In the proof for the lemma for Halbeisen-Shelah why you have that both α and β has the same sequence in the exponential part? Also in the end of the proof for Halbeisen-Shelah what is the canonical injective from αω to αα?

Reply
580 -Some choiceless results | A kind of library says:

February 26, 2019 at 7:40 pm

[…] (Dec. 3, 2009). The pdf file still contains an error that was pointed out to me recently. In the third lecture on choiceless results, the correct argument is […]

Reply
Question about Generalized Continuum Hypothesis [closed] – Math Solution says:

March 7, 2022 at 8:29 am

[…] set of finite sequences of elements of X. This was proved by Halbeisen and Shelah, see for example this blog post of […]

Reply
What is a Cantor-style proof of 2n>nk2^n > n^k? – Math Solution says:

March 8, 2022 at 4:52 am

[…] that mathfrak m^2=mathfrak m for all infinite mathfrak m — see the first lemma in section 6, here, where it is also shown that there are explicit bijections f_alpha:alphatoalphatimesalpha for […]

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 …

A kind of library