5
$\begingroup$

Theorem 3 A subset of a countable set is countable. In particular, every set of natural numbers is countable.

Proof Let $B$ be a countable set and $A$ a nonempty subset of $B$. First consider the case that $B$ is finite. Let $f$ be a one-to-one correspondence between $\{1,\dots,n\}$ and $B$. Define $g(1)$ to be the first natural number $j$, $1\le j\le n$, for which $f(j)$ belongs to $A$. If $A=\{f(g(1))\}$ the proof is complete since $f\circ g$ is a one-to-one correspondence between $\{1\}$ and $A$. Otherwise, define $g(2)$ to be the first natural number $j$, $1\le j\le n$, for which $f(j)$ belongs to $A\sim\{f(g(1))\}$. The pigeonhole principle tells us that this inductive selection process terminates after at most $N$ selections, where $N\le n$. Therefore $f\circ g$ is a one-to-one correspondence between $\{1,\dots,N\}$ and $A$. Thus $A$ is finite.

Can you elaborate on the statement "Define $g(1)$ to be the first natural number $j$, $1\le j\le n\dots$

I also don't understand the next sentence "If $A=\{f(g(1))\}$, the proof is complete."

I really appreciate if you explain these in easy terms.

$\endgroup$

4 Answers 4

8
$\begingroup$

The function $f$ is a bijection from $\{1,2,\ldots,n\}$ onto $B$. Since $A\subset B$, there are some elements $k\in\{1,2,\ldots,n\}$ such that $f(k)\in A$. The author calls $j$ to the first such element of $\{1,2,\ldots,n\}$ and then he defines $g(1)=j$. By this definition, $f\bigl(g(1)\bigr)=f(j)\in A$. Does it happen that $A=\bigl\{f\bigl(g(1)\bigr)\bigr\}$? If so, then we're done: $g$ is a bijection from $\{1\}$ onto $A$. Otherwise, we start all over again: let $j'$ be the second element of $\{1,2,\ldots,n\}$ such that $f(j')\in A$, let $g(2)=j'$, and so on…

$\endgroup$
2
  • 1
    $\begingroup$ The proof that was posted in the original question is terribly formulated and I can understand very well that it's hard to understand. Why don't they write it directly like you do! :-) By the way, there are for sure simpler proofs for this rather trivial statement. $\endgroup$
    – Luke
    Commented Jul 25, 2018 at 11:37
  • $\begingroup$ @Luke Thank you for the compliment. $\endgroup$ Commented Jul 25, 2018 at 11:38
2
$\begingroup$

Here is an example that can help you.

Let $B=\{b_1,b_2,b_3,b_4,b_5\}$ and $A=\{b_2,b_4,b_5\} \subset B$. Also let $f:\{1,2,3,4,5\} \longrightarrow B$ be given by $f(i)=a_i$. Then $g(1)=2$ because $f(2)=a_2$ is the first element in $A$.

$\endgroup$
2
$\begingroup$

$A \subset B$, $B$ is finite, $A,B \not = \emptyset$.

There is a bijection $f : I_n \rightarrow B$, where $I_n =${$1,2,3,...,n$}.

We have $B=${$f(1),f(2),...,f(n)$}, or written as a sequence $f_i:=f(i)$, $i=1,2,...n.$

Start to sort out:

Choose the smallest index

$i \in$ {$1,2,..,n$} with $f(i) \in A.$

Call the index $i_1$, i.e $f(i_1) \in A$,

in terms of $g$: $g(1):=i_1$

If $A= ${$f(i_1)$} we are done, else

we continue and look at: $B$ \ {$f(i_1)$}.

Proceed likewise find $g(2):= i_2 >i_1$,

where $f(i_2) \in B$ \ {$(f_1)$}, and $f(i_2) \in A.$

The inductive procedure comes to an end after at most $n$ selections.

Say, you have $k$ selections, $1 \le k \le n$, then

$A= ${$f(i_1),f(i_2),...f(i_k)$},

where $f_{i_s}=f(i_s)$, with $1 \le s \le k$ is a finite subsequence.

Note $i_1< i_2 < ......<i_k$.

Define $g: I_k \rightarrow$ {$i_1,i_2,....i_k$},

$g(s)= i_s$, where $1 \le s \le k$.

Finally:

$f \circ g$ is a bijection from $I_k \rightarrow A$.

$\endgroup$
1
$\begingroup$

The number $g(1)$ is defined as the minimum of the set $\{ j\in \{1,\ldots ,n\} | f(j)\in A\}$. This set is a subset of $\mathbb{N}$ which is not empty (because $A$ is not empty and $f$ is surjective), so the minimum indeed exists.

As for the second point, if $A=\{f(g(1))\}$, then $A$ is a set that contains only one element, so it surely is countable.

(Note that indeed, in any case, $f(g(1))$ is an element of $A$, by very definition of the number $g(1)$.)

$\endgroup$

You must log in to answer this question.

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