Here the problem 1.4.26 from Sohrab, Basic Real Analysis


This are not duplicate of this question:


Show that, if $A$ is an infinite set, then $|A\times\mathbb{N}|=|A|$. Hint: Let $\mathcal{F}$ denote the set of all bijective maps $f:S\times\mathbb{N}\to S$, where $S\subset A$. Since $|\mathbb{N}\times\mathbb{N}|=|\mathbb{N}|$, we have $\mathcal{F}\neq \varnothing$ (Why?) Show that Zorn's Lemma can be applied in $\mathcal{F}$ to produce a maximal bijection $h:B\times\mathbb{N}\to B$, with $B\subset A$, and that we must have $B=A$, by examining the cases where $S\setminus B$ is finite or infinite.


Let $\mathcal{F}$ denote the set of all bijective maps $f:S\times\mathbb{N}\to S$, where $S\subset A$. Since $|\mathbb{N}\times\mathbb{N}|=|\mathbb{N}|$ (see exercise 1.4.10(i)), we have $\mathcal{F}\neq \varnothing$ (From Exercise 1.4.22(d) we know that for a infinite set $A$, we have $|A|\geq\aleph_0$, and $|\mathbb{N}|=\aleph_0$, thus there is an injection from $g:\mathbb{N}\to A$, and, by defining $S:=g(\mathbb{N})\subset A$, we get a bijective map (composition of two bijective maps) $S\times\mathbb{N}\to\mathbb{N}\times\mathbb{N}\to\mathbb{N}\in\mathcal{F}$).

If we consider the inclusion as partial order, then every chain $S_i\subset A$, $i\in I$, has $A$ as upper bound and applying Zorn's Lemma, we get the existence of a maximal $\bar{S}$ and hence a bijection $h:\bar{S}\times\mathbb{N}\to\bar{S}$, with $\bar{S}\subset A$.

Now we prove that $\bar{S}=A$. $R:=A\setminus \bar{S}$. $\bar{S}$ is infinite, since the example of element of $\mathcal{F}$, that we gave above is bijective to $\mathbb{N}$. We have to do this. The second is trying to follow the hint and is incomplete:

  • Consider that $A\neq\bar{S}$, then there is $r\in R:=A\setminus\bar{S}$. We chose an element $s\in\bar{S}$ and define the bijection $h':\bar{S}\cup\{r\}\times\mathbb{N}\to \bar{S}\cup\{r\}$ as follow

    $h'(a,n)=\begin{cases}h(s,2n-1)&\text{for }a=s\\ r&\text{for }a=r,n=1\\ h(s,2n-2)&\text{for }a=r,n\neq 1\\ h(a,n)&\text{otherwise}\end{cases} $

    Since $\bar{S}\subsetneq \bar{S}\cup\{r\}$ we get a contradiction to the maximality of $\bar{S}$.

  • Now either $R$ is finite or infinite. 1) $R$ finite, let say $R=\{r_1,\cdots,r_n\}$. Then chose $n$ elements $s_1,\cdots,s_n\in\bar{S}$ and we define the bijection $h':A\times\mathbb{N}\to A$ as follow $h'(a,n)=\begin{cases}h(a,2n-1)&\text{for }a\in\{s_1,\cdots,s_n\}\\ a&\text{for }n=1,a\in\{r_1,\cdots,r_n\}\\ h(s_i,2n-2)&\text{for }a=r_i\\ h(a,n)&\text{otherwise}\end{cases}$

    In case $n>0$ we get a contradiction with $\bar{S}$ being the maximal element.

    Thus we have only to exclude the case 2) $R$ infinite. HOW TO DO THAT?


Above I tried two proofs. The first part is the same. The two second parts are given by the two bullets.

The second proof tries to follow the hint.

My questions are: - Is my proof correct? - In which direction should go the proof from the hint?


Your attempt to apply Zorn’s lemma doesn’t actually work, because you’re applying it to the wrong partial order. You’re taking as your partial order the family of subsets $S$ of $A$ such that there is some bijection from $S\times\Bbb N$ to $S$. If $\mathscr{C}$ is a chain in this partial order, $A$ is not known to be an upper bound for $\mathscr{C}$ in the partial order, because you don’t know that there is a bijection between $A\times\Bbb N$ and $A$: that, in fact, is what you’re trying to prove.

In order to follow the hint, you should consider the partial order $\langle\mathscr{F},\subseteq\rangle$. Let $\mathscr{C}$ be a chain in this partial order, let $f=\bigcup\mathscr{C}$. For each $f\in\mathscr{C}$ there is an $S_f\subseteq A$ such that $f$ is a bijection from $S_f\times\Bbb N$ to $S_f$; let $S=\bigcup_{f\in\mathscr{C}}S_f$.

  • Show that $f$ is a bijection from $S\times\Bbb N$ to $S$. Conclude that $h\in\mathscr{F}$ is an upper bound for $\mathscr{C}$.

Now apply Zorn’s lemma to get a maximal $h\in\mathscr{F}$, and let $B\subseteq A$ be such that $h$ is a bijection from $B\times\Bbb N$ to $B$.

Once you have this, the argument at your first bullet point works fine. I see no need to make two cases out of this depending on whether $A\setminus B$ is finite; that’s an unnecessary complication.

  • $\begingroup$ Do I understand correct? Your special font for F (latex command?) is my $\mathcal{F}$. Your order is the order of the functions in $\mathcal{F}$ as a cartesian product, that is $A\times\mathbb{N}\times A$? $\endgroup$ – PeptideChain Aug 18 '16 at 19:59
  • $\begingroup$ @LiPo: Yes to both: all of these functions are subsets of $A\times\Bbb N\times A$. (I prefer \mathscr{} to \mathcal{}.) $\endgroup$ – Brian M. Scott Aug 18 '16 at 20:01
  • $\begingroup$ wow, very interesting, thank you very much $\endgroup$ – PeptideChain Aug 18 '16 at 20:05
  • $\begingroup$ @LiPo: You’re very welcome. $\endgroup$ – Brian M. Scott Aug 18 '16 at 20:09
  • $\begingroup$ The first bullet does not work, as there is no contradiction. The restriction to $\overline{S}$ is not the correct one, so the bijection you create is not bigger than the previous one. $\endgroup$ – Jérémy Blanc Oct 29 '17 at 9:53

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.