In my book, it proves that an infinite subset of a coutnable set is countable. But not all the details are filled in, and I've tried to fill in all the details below. Could someone tell me if what I wrote below is valid?

Let $S$ be an infinite subset of a countable set $T$. Since $T$ is countable, there exists a bijection $f: \mathbb{N} \rightarrow T$. And $S \subseteq T = \{ f(n) \ | \ n \in \mathbb{N} \}$. Let $n_{1}$ be the smallest positive integer such that $f(n_{1}) \in S$. And continue where $n_{k}$ is the smallest positive integer greater than $n_{k-1}$ such that $f(n_{k}) \in S$. And because $S$ is infinite, we continue forever. Now consider the function $\beta : \mathbb{N} \rightarrow S$ which sends $k \rightarrow f(n_{k})$.

So in order for $S$ to be countable, $\beta$ would have to be a bijection. $\beta$ is injective since if $f(n_{k}) = f(n_{j})$, then $n_{k} = n_{j}$ because $f$ is injective. We also can conclude $k = j$ because the various $n_{i}$ chosen were strictly increasing.

Edit: $\beta$ also needs to be surjective. So for every $r \in S$ there exists a $q \in \mathbb{N}$ such that $\beta(q) = f(n_{q}) = r$. We know that $f^{-1}(r) \in \{n_{1}, n_{2}, ..., n_{k} ... \}$, so we can let $f^{-1}(r) = n_{d}$. Thus $\beta(d) = f(n_{d}) = r$.

  • 2
    Your last statement doesn't really prove $\beta$ is surjective. You still need to establish that $q=f^{-1}(r)$ is equal to $n_k$ for some $k$. – Bill Cook Feb 9 '12 at 21:41
  • 2
    You're on the right track. Perhaps it is easier to show that any infinite subset of $\mathbb{N}$ is countable. In this case you can always use the fact that any nonempty subset of $\mathbb{N}$ contains the least element, in which case you have already done most of the proof above. Once you have demonstrated that any infinite subset of $\mathbb{N}$ is countable, notice that $f$ establishes a bijection between $S$ and an infinite subset of $\mathbb{N}$. – user2093 Feb 9 '12 at 21:41
  • @Bill: That $f$ is a bijection is given. – Brian M. Scott Feb 9 '12 at 21:41

To fix the last statement:

Suppose that $q=f^{-1}(r)$. Then $\{ 0,1,2,\dots,q\}$ is a finite set. Intersect this with $f^{-1}(S) = \{ n \in \mathbb{N} \;|\; f(n) \in S\}$ and get a finite set. By your definition of the $n_k$'s this set is $\{n_0,n_1,\dots,n_\ell\}$ for some $\ell$. Thus $q=n_\ell$. Therefore, $\beta(\ell)=f(n_\ell)=f(q)=r$. Patched.

  • 1
    Can you see if I understand what you mean in my edit? – Student Feb 9 '12 at 22:23
  • 1
    That's seems reasonable. – Bill Cook Feb 9 '12 at 22:35
  • @BillCook how is {0,1,2,...q} is finite ? thanks – Taylor Ted Jul 8 '15 at 5:17
  • It's finite since $\{0,1,2,\dots,q\}$ has exactly $q+1$ elements (a finite number of elements). – Bill Cook Jul 8 '15 at 11:18

The set $A$ is countable if there is $f:A\to\mathbb N$ which is injective.

Suppose $B\subseteq A$ then $f|_B:B\to\mathbb N$ is also injective, simply because you restrict an injective function you cannot counterexample the injectivity.

Suppose that $f:A\to\mathbb N$ is a bijection and $B\subseteq A$ is infinite. Let $N=\{f(b)\mid b\in B\}$, the image of $B$.

Since $B$ is infinite, we have that $N$ is infinite. Let us show that an infinite subset of $\mathbb N$ is countable:

We define inductively a function $g:\mathbb N\to N$, $g(0)=\min N$ the minimal number in $N$. Suppose $g(n)$ was defined, let $g(n+1)$ be the least number in $N$ which is larger than $g(n)$.

It is obvious that $g$ is a bijection between $\mathbb N$ and $N$. Now we have that $g^{-1}\circ f|_B:B\to\mathbb N$ is a bijection, as wanted.

  • 1
    I think his book uses the definition of $f$ being bijective, and I think that is the main problem that the OP is encountering. – user2093 Feb 9 '12 at 21:44
  • With g :ℕ→N, g(0) is undefined. – davide Jul 31 at 13:00
  • @davide: ??? I explicitly defined it. – Asaf Karagila Jul 31 at 13:04
  • g:ℕ→N and the g in the expression g(0) cannot be the same function, as 0 doesn't exist in ℕ. In order for g(0) to exist, the domain of g must not be ℕ. – davide Jul 31 at 13:09
  • @davide: Did you read the word "define"? We define the function $g$. And we define it by recursion. – Asaf Karagila Jul 31 at 13:13

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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