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


\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.


10 Responses to 580 -Some choiceless results (3)

  1. billy hudson says:

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

  2. 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.

  3. billy hudson says:

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

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

  5. 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.

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

  7. 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.

  8. […] (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 […]

  9. […] 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 […]

  10. […] 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 […]

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: