Infinite subset of $\mathbb{N}$ is countable. Proof by math induction.

Question

Proposition: Infinite subset of $\mathbb{N}$ is countable.

Proof: Suppose that $E$ is infinite subset of $\mathbb{N}$ and our goal to show that $E$ is countable, i.e. there is $f:\mathbb{N}\to E$ which is bijection.

Since $E\neq \varnothing$ then $\exists! e_1:=\min E$, then $E \backslash \{e_1\}\neq \varnothing$ then $\exists! e_2:=\min E \backslash \{e_1\}$. Also $\exists! e_3:=\min E \backslash \{e_1,e_2\}$ and we can continue this process by induction. The we define function $f:\mathbb{N}\to E$ in the following way: $f(n)=e_n$ for each $n\in \mathbb{N}$.

Intuitively I understand this very well. But how induction works here in a rigorous way?

Principle of mathematical induction is the following: If $S\subset \mathbb{N}$ with $1\in S$ and for each $n\in S$ we have $n+1\in S$ then it follows that $S=\mathbb{N}$.

How to write this set $S$ in our case in a rigorous way?

Would be very thankful for help!

Answer 1

HINT: Say that a finite $f\subseteq\Bbb N\times E$ is good if

• $f$ is a function,
• $\operatorname{dom}f=\{1,\ldots,n\}$ for some $n\in\Bbb N$, and
• $f(k)=\min(E\setminus\{f(i):i<k\})$ for each $k\in\operatorname{dom}f$.

Step $\mathbf1$. Show first that if $f$ and $g$ are good and have the same domain $\{1,\ldots,n\}$, then $f=g$. You can do this by induction by considering the set $$\{k\in\Bbb N:f(k)=g(k)\text{ or }k>n\}\,.$$

Step $\mathbf2$. Show by induction that for each $n\in\Bbb N$ there is a good function $f_n$ with domain $\{1,\ldots,n\}$; the first step ensures that $f_n$ is unique.

Step $\mathbf3$. Show that if $1\le k\le m\le n$, then $f_m(k)=f_n(k)$; this is similar to the first step.

Define a function $h:\Bbb N\to E:n\mapsto f_n(n)$. Use the result of Step $3$ to show that $h$ is injective, and use the fact that $\Bbb N$ is well-ordered to show that $h$ is surjective. (If $h$ is not surjective, consider the least element of $E\setminus h[\Bbb N]$ and get a contradiction.)

Answer 2

==== New Answer ====

First thing we need to be careful, exactly what where are proving by induction..

And what we are proving (by strong) induction is that the function described is well defined and true prove that by induction is to prove the statement:

$P(k):$ If $E_k= \{e_1,......,e_{k-1}\}$ is finite subset of of cardinality $k-1$ then $e_k := \min E\setminus E_k$ exists. And so $f(k) := e_k$ is well defined.

And that is done in a routine way:

Base case, $P(1)$: $E_1 =\emptyset \subset E$. $E\setminus \emptyset = E$ which is a nonempty subset of $E$. So by well-ordering principal $\min E$ exists and so $f(1)=e_1 = \min E$ is a well-defined assignment.

Induction step: If $E_{k}=\{e_1,....,e_{k-1}\}\subset E$ and $e_k =\min E\setminus E_k$ exists; then $e_k \in E$ and $e_k\not \in E_{k-1}$ and so $E_{k+1}=E_{k-1}\cup \{e_k\}=\{e_1,....,e_{k-1},e_k\}\subset E$. As $\{e_1,....,e_{k-1}\}$ is finite set of cardinality $k-1$ there exists a bijection $\phi_1: \{1,....,k-1\}\to \{e_1,....,e_{k-1}\}$. so we can define $\phi_2:\{1,....,k-1\} \to \{e_1,....,e_k\}$ five if $n < k; \phi_2(n)= \phi_1(n)$ and $\phi_2(k) =e_k$. $\phi_2$ is injective because: $\phi_2(k)=e_k\ne \phi_2(n)=e_n$ for all $n\ne k$ as $e_n \in E_k$ but $e_k\not \in E_k$. And for any $i\ne j; i\ne k;j\ne k$ then $\phi_2(i) =\phi_1(i)\ne \phi_2(j) = \phi_2(j)$ because $\phi_1$ is injective.

And $\phi_2$ is surjective as for all $w\in E_{k+1}$ where $w \ne e_k$ we have an $i< k$ where $\phi_1(i)=\phi_2(i) = w$ as $\phi_1$ is surjective. And for $e_k \in E_{k+1}$ we have $\phi_2(k) = e_k$.

So $\phi_2$ is an injection and $E_{k+1}$ is a finite subset of $E$ with cardinality $k$.

.... Sheesh......

Okay... now $E_{k+1}$ is a finite subset of $E$ and $E$ is infinite so $E_{k+1} \subsetneq E$. so $E\setminus E_{k+1} \ne \emptyset$ and $E\setminus E_{k+1}$ is a proper subset of $\mathbb N$ so $\min E\setminus E_{k+1}$ exists and $f(k+1) = e_{k+1} = E\setminus \min E\setminus E_{k+1}$ is a valid assignment.

....

Dont worry.... No-one will ever expect you to go into that much detail....

....

And that proves that the function $f$ is well defined.

Now we just have to prove it is injective and surjective.

Injective is straightforward. In the above proof $E_k=\{e_1,....., e_{k-1}\}=\{f(n)|n\in \mathbb N; n< k\}$ and $f(k) = e_k = \min E\setminus E_k$ were well defined. For any $i\ne j; i< j$ we have $f(i)\in \{f(n)|n\in \mathbb N; n< k\}=E_j$ but $f(j) = \min E\setminus E_j \not \in E_j$ so $f(i) \ne f(j)$.

Proving $f$ is surjective is a little tricky and relies an the observation that it must be that $f(k) \ge k$.

To prove that by induction:

Base case: $f(1) = \min E$. As $E \subset \mathbb N$, $\min E \ge 1$.

Indcution. If $f(k) \ge k$ then $\min E\setminus E_k \ge k$ and all $w\in E\setminus E_k$ are $w \ge k$ and if $w \ne e_k = \min E\setminus E_k$ then $w > e_k \ge k$ and $w \ge k+1$. so $f(k+1) = \min E\setminus E_{k+1} = \min ( E\setminus E_k)\setminus \{e_k\}\ge k+1$.

...(ta-da.....)....

Foo, where were we... oh, yeah, proving surjective.

.... Hey! Watch this!

Let $w \in E$. Let $U_w = \{n\in N| f(n) \ge w\}$. As $f(w)\ge w$ we have $w\in U_w$ so $U_w$ is not empty. So $\min U_w$ exists. Claim: $f(\min U_w) = w$.

Pf: Let $\omega = \min U_w$. Then for all $k < \omega; k \not \in U_w$ so $f(k) < w$. So $w \not \in E_\omega$ and $w \in E\setminus E_k$.

Now $f(\omega) = \min E\setminus E_k$ and $\omega \in U_w$ so $f(\omega)=\min E\setminus E_k \ge w$ and $w\in E\setminus E_k$. So $w \ge \min E\setminus E_k = f(\omega)$. So $w = f(\omega)$.

And that proves surjectivity.

===old answer ====

Yeah... this a matter of saying the right words in order at the right time.

Our Propostion: $P(k)$ For every $i \le k$ we can map each $i\mapsto e_i$ to a distinct $e_i \in E$.

$P(1):$. $E \subset \mathbb N$ so $\min E$ exists. Let $1\mapsto e_1 = \min E$.

Induction step: Assume $P(k)$. That is for $1,2,3,.....,k$ we have $E_k = \{e_1,e_2,....,e_k\}\subset E$ where the $e_i$ are distinct.

As $E$ is infinite and $E_k$ is finite $E_k \subsetneq E$ and $E\setminus E_k \ne \emptyset$. And as $E\setminus E_k\subset \mathbb N$ we know $\min E\setminus E_k$ exist. And we know that as $E_k$ and $E\setminus E_k$ are disjoint $\min E\setminus E_k$ is distinct from all the other $e_i$.

So we let $k+1 \mapsto e_{k+1}:= \min E\setminus E_k$. And thus $\{e_1,....,e_k,e_{k+1}\}$ has been a mapping of all $i \le k+1$ to distinct elements of $E$.

So we have proven $P(k+1)$.

So we conclude that the for any $n \in \mathbb N$, $P(n)$ is true. And thus we have every $n \in \mathbb N$ will map to an $e_n$. And for all $i < n$ we know $e_i \ne e_n$ And for all $m > n$ we know $P(m)$ is true and $e_m \ne e_n$ so $e_n$ is distinct for all $e_i; i \ne n$.

And that's it. Let $f(n) = e_n$ and that is an injective map. Oh.... I guess we have to also prove it is surjective.

Well, that's a different step.

Answer 3

At the $n$-th iteration of the process you described, you essentially define an injection $f_n: [n] \to E$, where $[n] := \{1,2,\ldots,n\}$.

$f_{n+1}$ is defined as $f_n \cup (n+1, \min(E \setminus f_n([n]))$. In other words $$f_{n+1}(i) := \begin{cases} f_n(i) &, \;\; i \in \{1,\ldots,n\}\\ \min(E \setminus f_n([n]) &, \;\; i= n+1 \end{cases}.$$ The existence of these $f_n$ can be proven using induction. Moreover, these $f_n$ satisfy some additional properties that allow you to define $f: \mathbb N \to E$ as $\bigcup_{n \in \mathbb N} f_n$ and show it is bijective. You want to include those properties in your induction hypothesis as well.

So, given $n \in \mathbb N$ consider the property $$P(n)= \text{there are } f_1,f_2,\ldots,f_n \text{ such that [insert desired properties here]}$$ and the set $S = \{n \in \mathbb N \mid P(n) \text{ is true} \}$. You can show by induction that $S = \mathbb N$, hence proving the existence of $f_1,f_2,\dots,$ with the desired properties.

Addendum
The desired properties are that $f_k$ is an injection $[k] \to E$, $f_k \subseteq f_{k+1}$ (this ensures that $f$ is well defined), and I think you'll need something like $\max(f_k([k])) < \min(E \setminus f_k([k]))$ to show that $f$ is surjective.