9
$\begingroup$

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$.

$\endgroup$
3
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Bill Cook
    Commented Feb 9, 2012 at 21:41
  • 2
    $\begingroup$ 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}$. $\endgroup$
    – user2093
    Commented Feb 9, 2012 at 21:41
  • $\begingroup$ @Bill: That $f$ is a bijection is given. $\endgroup$ Commented Feb 9, 2012 at 21:41

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ I think his book uses the definition of $f$ being bijective, and I think that is the main problem that the OP is encountering. $\endgroup$
    – user2093
    Commented Feb 9, 2012 at 21:44
  • $\begingroup$ With g :ℕ→N, g(0) is undefined. $\endgroup$
    – davide
    Commented Jul 31, 2018 at 13:00
  • $\begingroup$ @davide: ??? I explicitly defined it. $\endgroup$
    – Asaf Karagila
    Commented Jul 31, 2018 at 13:04
  • $\begingroup$ 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 ℕ. $\endgroup$
    – davide
    Commented Jul 31, 2018 at 13:09
  • $\begingroup$ @davide: Did you read the word "define"? We define the function $g$. And we define it by recursion. $\endgroup$
    – Asaf Karagila
    Commented Jul 31, 2018 at 13:13
4
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .