0
$\begingroup$

In Abbott's "Understanding Analysis," Abbott offers the following idea to run through the proof:

Assume B is a countable set. Thus, there exists a bijection $f:\mathbb{N} \rightarrow B$. Let $A\subseteq B$ be an infinite subset of $B$. We show $A$ is countable. Let $n_1=\min\{n\in \mathbb{N}: f(n)\in A\}$. As a start to a definition for $g: \mathbb{N}\rightarrow A$, set $g(1)=f(n_1)$. Show how to inductively continue this process to produce a bijection $g:\mathbb{N}\rightarrow A$.

I'm not seeing how to inductively continue this process to produce a definition for a bijection. Thanks for the help!

$\endgroup$
  • $\begingroup$ Isn't cardinality monotone, i.e., if $A \subset B \rightarrow |A| \leq |B|$? $\endgroup$ – Gary. May 31 '15 at 19:45
  • $\begingroup$ I would like to comment. Countable does NOT mean bijective with natural numbers. "Countable or finite " is unnecessary. Finite sets are countable. $\endgroup$ – user223391 May 31 '15 at 20:33
  • $\begingroup$ @Gary If you define $|A| \le |B|$ to mean that there is an injection from $A$ to $B$, then yes, that implication is clearly true. However, the OP's definition of "countable" seems to be "having a bijection with $\mathbb{N}$", so the point of the question is to get a bijection rather than just an injection (in the case that the subset is not finite.) $\endgroup$ – Trevor Wilson May 31 '15 at 21:39
2
$\begingroup$

Let $n_2$ be the next $n$ (after $n_1$) such that $f(n) \in A$. Let $g(2):=f(n_2)$. Can you see how to continue?

To prove $g$ is onto, note that $\{g(1),g(2),\dots,g(K)\} = A \cap \{f(1), \dots, f(n_K)\}$. Further, $n_i$ increases strictly and $f$ is onto.

$\endgroup$
  • $\begingroup$ So, if $g(1)=g(2)$, it would have to be the case that $n_1=n_2$ by definition. My only question is how would $n_2$ be defined in terms of a min? And then for onto, let $k\in A$. Then, how do I know there exists $n_j \in \mathbb{N}$ with $n_j=min\{n\in \mathbb{N}:f(n) \in A\}$? $\endgroup$ – Moz May 31 '15 at 19:45
  • $\begingroup$ Note that $n_2=\min \{n \in \mathbb{N} : n>n_1, \: f(n) \in A \}$. $\endgroup$ – TorsionSquid May 31 '15 at 19:51
  • $\begingroup$ Ah, I see specifically what you mean by the next one. Thanks! $\endgroup$ – Moz May 31 '15 at 19:56
  • $\begingroup$ To prove $g$ is onto, note that $\{g(1),g(2),\dots,g(K)\} = A \cap \{f(1), \dots, f(n_K)\}$. Further, $n_i$ increases strictly and $f$ is onto. $\endgroup$ – TorsionSquid May 31 '15 at 19:59
  • $\begingroup$ I am not able to see onto in the following way. Since $f$ is a bijection, there exists $a \in A$ satisfying $a=f(j)$ for some $j\in \mathbb{N}$. Then, $n_j>j$. I'm not sure how to get the necessary equality. $\endgroup$ – Moz May 31 '15 at 20:51
1
$\begingroup$

It is easier to produce a bijection in the other direction: $h:A\to\mathbb N$, by

$$ h(n) = \#\{a\in A\mid a<n\} $$

$\endgroup$
  • $\begingroup$ It's easier to define the function, but I'm not sure if it's really easier to prove that it's a bijection; to show that it is onto, it seems like you still need the induction argument from TorsionSquid's answer. $\endgroup$ – Trevor Wilson May 31 '15 at 21:46

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.