5
$\begingroup$

I want to prove that if $A$ is an infinite subset of the natural numbers, then it is countable.

I thought of an informal proof: put the elements of $A$ in increasing order. Then associate the smallest to $1$, the second smallest to $2$, the third smallest to $3$ and so on.

I've tried to formalise this proof in this way: consider the sequence $$ \begin{cases} A_1=A \\ A_n=A_{n-1}-\min{A_{n-1}}\end{cases}$$ The function $f(\min{A_n})=n$ has domain $A$ and codomain $\mathbb{N}$ and is a bijection, therefore $A$ is countable.

My questions are the following:

  1. Is what I wrote correct?
  2. If so, how do you prove that $f$ is actually a function from $A$ to $\mathbb{N}$ and is also a bijection?
$\endgroup$
2
  • $\begingroup$ By $\min{A_{n-1}}$ do you mean $\min( A_0,..., A_{n-1})$? $\endgroup$
    – Paul
    Apr 18, 2015 at 14:16
  • $\begingroup$ I mean the smallest element of the set of natural numbers $A_{n-1}$ $\endgroup$
    – Nicol
    Apr 18, 2015 at 14:19

3 Answers 3

1
$\begingroup$

Let me write down a rigorous definition of a bijection $f : \mathbb{N} \to A$.

Claim: For each integer $n \ge 1$ there exists a function $$f_n : \{1,\ldots,n\} \to A $$ such that for each $i=1,\ldots,n$, the least element of $A - \{f_n(j) \bigm| 1 \le j < i\}$ is $f_n(i)$.

The proof of this claim is by induction on $n$.

Basis step: The function $f_1 : \{1\} \to A$ is defined by $f_1(1) =$ the least element of $A$.

Induction step: Suppose that $n \ge 2$ and that the function $f_{n-1}$ exists. Define the function $f_n$ so that its restriction to $\{1,\dots,n-1\}$ equals $f_{n-1}$, and so that $f_n(n) =$ the least element of $A - \{f_{n-1}(1),\ldots,f_{n-1}(n-1)\}$.

QED Claim.

Now define $f : \mathbb{N} \to A$ by $f(n) = f_n(n)$.

Okay, so, it still remains to prove rigorously that $f$ is a bijection. Here I'll punt, and say that what one does to accomplish this are further induction proofs. For instance, one proves that for each $n \in \mathbb{N}$, the least element of $A - \{f(i) \bigm| 1 \le i < n\}$ is $f(n)$. Injectivity and subjectivity follow.

$\endgroup$
1
$\begingroup$

I'd rather use the well known and comfortable property of the natural numbers of being a well ordered set:

First, let $\;a_1\in A\;$ be the smallest (wrt the usual order) element in $\;A\;$

Now, let $\;a_2\in A\setminus\{a_1\}\;$ be the smallest element, etc.

$\endgroup$
7
  • $\begingroup$ @Paul There always is: it's one of the most important characteristics of the natural numbers, and one that allows us to use mathematical induction, for example. $\endgroup$
    – Timbuc
    Apr 18, 2015 at 14:19
  • $\begingroup$ This is my idea. I just wanted to avoid using "etc." and actually define a function and prove its bijectivity. $\endgroup$
    – Nicol
    Apr 18, 2015 at 14:21
  • $\begingroup$ @Nicol If you mean an explicit function I can't see how is this possible as we're not given an explicit subset $\;A\subset \Bbb N\;$ ... $\endgroup$
    – Timbuc
    Apr 18, 2015 at 14:23
  • $\begingroup$ Nope, not an actual numerical expression, but a function like the one I defined, which I think expresses formally the idea of putting the elements of $A$ in increasing order. $\endgroup$
    – Nicol
    Apr 18, 2015 at 14:25
  • $\begingroup$ @Nicol I see... Yet you're defining a function to the naturals but not on $\;A\;$ but rather on its power set $\;P(A)\;$ . I'm not sure this will work. $\endgroup$
    – Timbuc
    Apr 18, 2015 at 14:31
1
$\begingroup$

I am also trying to formalize this proof to my taste and I do so with an equally shared distaste for "etc." Here is what I have so far...

Let $A \subset \mathbb{N}$ be infinite. Let $\mathbb{N}_k$ denote $\{0,1,...,k-1\}$. Suppose $f:A \rightarrow A$ is defined by the rule, $n \mapsto \min(A \setminus \mathbb{N}_{n+1})$. We know that this minimum always exists since $\mathbb{N}$ is well-ordered and $A \setminus \mathbb{N}_k$ is never empty (because if it is for some $k$, then $A$ could not be infinite). So, $f$ is well-defined. Less formally, we can say that $f$ maps each number in $A$ to its immediate successor in $A$. Therefore, $n < f(n)$ for all $n \in \mathbb{N}$.

By the Recursion Theorem, there exists a unique function $F: \mathbb{N} \rightarrow A$ such that:

$$F(0) = \min(A) \\ F(k + 1) = f(F(k))$$

for any $k ∈ \mathbb{N}$. Since $F(k) < f(F(k)) = F(k+1)$, $F$ is injective. Since $\iota:A \rightarrow \mathbb{N}$ is also injective, $A \sim \mathbb{N}$ by the Schroeder-Bernstein Theorem. $\square$

$\endgroup$
1

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