Set Theory – Cardinality of Cartesian Product of an Infinite Set with N

cardinalsset-theory

Here the problem 1.4.26 from Sohrab, Basic Real Analysis

Duplicate

This are not duplicate of this question:

Problem

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.

Proof

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?

Question

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?

Best Answer

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.

Related Question