I am trying to prove Proposition 1.7 of http://math.bu.edu/people/aki/7.pdf:

Proposition 1.7 (Halbeisen–Shelah). If $\aleph_0\le|X|$, then $|{\cal P}(X)|\not\le|{\rm Seq}(X)|$.

In words, this says that if $X$ is a Dedekind-infinite set, then the powerset of $X$ does not inject into the set ${\rm Seq}(X)$ of finite sequences on $X$. The proof is described in the link, and I follow most of it well enough. But it requires that we "canonically associate to [the well-ordering] $R$ of $Y$ a bijection $H:Y\to {\rm Seq}(Y)$", and I don't see how this is done.

I do have a proof that $|Y|=|{\rm Seq}(Y)|$, and by tracing the proof, in principle I should get an explicit bijection. The proof $|{\rm Seq}(Y)|\le|Y|$ produces an explicit injection by iterating an injection $f:Y\times Y\to Y$, so it is sufficient to prove the following:

There is a definable term $F$ in ZF such that if $\alpha$ is an infinite ordinal, then $F(\alpha)$ is an injection from $\alpha\times\alpha$ to $\alpha$.

My current (nonconstructive) proof of $|\alpha\times\alpha|=|\alpha|$ goes roughly as follows:

Define $\langle\alpha_1,\alpha_2\rangle\prec\langle\beta_1,\beta_2\rangle$ when $\max(\alpha_1,\alpha_2)<\max(\beta_1,\beta_2)$, or $\max(\alpha_1,\alpha_2)=\max(\beta_1,\beta_2)$ and $\alpha_1<\beta_1$, or $\alpha_1=\beta_1$ and $\alpha_2<\beta_2$. (In other words, lexicographic order on $\max(\alpha_1,\alpha_2);\alpha_1;\alpha_2$.) Then this is a well-order of $\sf On\times On$ with the property that for any infinite cardinal $\kappa$ and $\alpha<\kappa$, its restriction to $\alpha\times\alpha$ has order type $<\kappa$. Thus the unique order isomorphism corresponding to this well-order is a canonical bijection from $\kappa\times\kappa\to\kappa$ on cardinals, and any other $\alpha$ can be put in bijection with some cardinal $\kappa$, yielding a (non-canonical) bijection $\alpha\times\alpha\to\alpha$.

  • $\begingroup$ How is this a non-canonical bijection? An isomorphism between two well-ordered sets is unique. What can be more canonical than that, in the confines of classical logic and the axioms of $\sf ZF$? $\endgroup$ – Asaf Karagila May 19 '15 at 19:11
  • $\begingroup$ @AsafKaragila It is canonical, but it only works on cardinals. Off the cardinals, you have to choose a bijection to the nearest cardinal nonconstructively. I.e. the proof does not give a canonical bijection $\omega+1\times\omega+1\to\omega+1$ since you have to first choose a bijection $\omega+1\to\omega$. (If I'm not mistaken, the restriction of the order isomorphism to $\omega+1\times\omega+1$ gives a bijection onto $3\omega+1$, not $\omega+1$.) $\endgroup$ – Mario Carneiro May 19 '15 at 19:14
  • $\begingroup$ It works for any closure point of this relation; which I believe is any ordinal of the form $\gamma=\omega^\gamma$ (I could be mistaken about this characterization, but I do recall seeing something not too far from this). But you're right it's not the same. In either case, it seems from your comment that your question, and your title are not what you intend to ask. $\endgroup$ – Asaf Karagila May 19 '15 at 19:17
  • $\begingroup$ @Asaf As in I misinterpreted the meaning of "canonical" used in the Halbeisen proof, or that my statement is incorrect? I'm pretty sure that the second box correctly characterizes the goal; the order isomorphism does not satisfy the claim on $F$ because it is not an injection $\alpha\times\alpha\to\alpha$ for every infinite ordinal $\alpha$, only for some (the indecomposable ordinals, which include the cardinals). $\endgroup$ – Mario Carneiro May 19 '15 at 19:26
  • $\begingroup$ Well. I'm not sure yet what "canonical" means in that paper. But let me get back to you on that issue. $\endgroup$ – Asaf Karagila May 19 '15 at 19:28

I'm recording my solution here for posterity. The key step is indeed the usage of Cantor normal form, but there are quite a few extra details that were not obvious to me at the start. First, some facts about ordinals, whose proofs are relatively straightforward and so ommitted:

If $\alpha<\omega^\gamma\le\beta$, then $\alpha+\beta=\beta$.

If $\alpha<\omega^\gamma$, then $\alpha\cdot\omega^\gamma=\omega^\gamma$.

The ordinal sum $\alpha+\beta$ is equinumerous to the disjoint union $\alpha\sqcup\beta$ (written $\alpha+\beta\approx\alpha\sqcup\beta$).

The ordinal product $\alpha\cdot\beta$ is equinumerous to the cartesian product $\alpha\times\beta$.

The ordinal exponential $\alpha^\beta$ is equinumerous to the set of functions $f:\beta\to\alpha$ such that $f(\gamma)=0$ for all but finitely many $\gamma<\beta$.

The last statement is equivalent to the Cantor normal form theorem. All of the bijections here are explicitly definable. This also implies that if $\alpha\approx\beta$, $\gamma\approx\delta$, then $\alpha+\gamma\approx\beta+\delta$, $\alpha\cdot\gamma\approx\beta\cdot\delta$, $\alpha^\gamma\approx\beta^\delta$, and additionally $\alpha+\beta\approx\beta+\alpha$ and $\alpha\cdot\beta\approx\beta\cdot\alpha$ follow from properties of the disjoint union and cartesian product mapping to equivalent statements for ordinals.

Now, using these bijections inductively on the Cantor normal form of $\alpha=\sum_{i=0}^n\omega^{\alpha_i}k_i$ (where the sequence is summed in descending order of $\alpha_i$'s), we have that $$\alpha=\sum_{i=0}^n\omega^{\alpha_i}k_i\approx\sum_{i=n}^0\omega^{\alpha_i}k_i=\omega^{\alpha_0}k_0\approx k_0\omega^{\alpha_0}=\omega^{\alpha_0},$$ where in the second equality we have reversed the order of summation and in the fourth we reverse the product using the bijections above. Thus we establish:

Lemma: there is a definable term $F$ such that for all infinite ordinals $\alpha$, $F(\alpha)$ is a bijection from $\alpha$ to $\omega^\gamma$ for some $\gamma$.

Then, since $\omega^2\approx\omega\times\omega\approx\omega$ by the original proof (which is constructive for cardinals), we have $$\alpha\approx\omega^\gamma\approx(\omega^2)^\gamma=\omega^{2\cdot\gamma}\approx\omega^{\gamma\cdot2}=\omega^\gamma\cdot\omega^\gamma\approx\omega^\gamma\times\omega^\gamma\approx\alpha\times\alpha,$$

and all the bijections here are explicitly definable.

| cite | improve this answer | |

Looking at the original Halbeisen-Shelah paper, they point out this in Corollary 3.

This is a corollary of the fact every ordinal has a Cantor normal form. We use that fact to produce an injection from $\operatorname{Seq}(\alpha)$ into $\alpha$, then use the Cantor-Bernstein theorem (which, given two injections gives a well-defined and relatively canonical bijection).

| cite | improve this answer | |
  • $\begingroup$ I guess the accept was a bit premature, as I just realized I still don't understand the proof. (I just spent a week proving the cantor normal form theorem, but now I don't know what to do with it.) What does Cantor normal form do for us here? The paper claims (as a lemma?) that $|\alpha|=|\omega^{a_0}b_0|$, where $\omega^{a_0}b_0$ is the leading term of the CNF for $\alpha$, but I looked up the reference to the proof, and in addition to being in German (which I can't read so well), it didn't seem to have anything to do with the claimed result. $\endgroup$ – Mario Carneiro May 29 '15 at 22:16
  • $\begingroup$ You got an acknowledgement in arxiv.org/abs/1506.03533 for pointing me in the right direction. $\endgroup$ – Mario Carneiro Jun 12 '15 at 8:30
  • $\begingroup$ @Mario: I saw! Thanks! I was surprised that you didn't add the reference to the Halbeisen-Shelah paper though. :-) $\endgroup$ – Asaf Karagila Jun 12 '15 at 8:31
  • $\begingroup$ Strictly speaking, I do mention the names Halbeisen-Shelah in theorem 2, and you can track down the reference via Kanamori & Pincus [5], but it's true that I don't reference them directly. Perhaps I should have mentioned them as motivation, because their proof was so criminally brief that I had to spend a week working out how to connect the dots (hence the paper)! $\endgroup$ – Mario Carneiro Jun 12 '15 at 9:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.