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

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!

• Perhaps $S=\{ n \in \mathbb{N} | \exists k \in E, k > n \}$? Commented Jan 11, 2021 at 21:33
• @copper.hat, I am not sure. In your case $S$ does not have any information about $e_k$.
– RFZ
Commented Jan 11, 2021 at 21:46

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

• About step 1. In order to prove that any two good functions are equal I guess it is better to consider the $\{k\in\mathbb{N}: \forall i\leq k \ f(i)=g(i) \ \text{or} \ k>n\}$. Because in this case it is easy to see that $1$ belongs to this set and is inductive set and hence it is equal to $\mathbb{N}$. Right or not?
– RFZ
Commented Jan 12, 2021 at 11:15
• @ZFR: I’d use the set that I suggested. It’s easy enough to see that it contains $1$: $f(1)=\min(E\setminus\varnothing)=g(1)$ by definition. Commented Jan 12, 2021 at 20:49
• What is $g(1)$? Also how to show that your set is inductive? i.e. if it contains $n$ then it also contains $n+1$. Could you show it please?
– RFZ
Commented Jan 12, 2021 at 22:38
• @ZFR: The fact that $g$ is a good function with domain $\{1,\ldots,n\}$ immediately tells you that $g(1)$ is exactly what I said in the previous comment: $\min(E\setminus\varnothing)=\min E$. Suppose that $k$ is minimal such that $k$ is not in my set; clearly $1<k\le n$, so $1,\ldots,k-1$ are all in the set, and therefore $f(i)=g(i)$ for $i=1,\ldots,k-1$. The definition of good function immediately implies that $f(k)=g(k)$, contradicting the choice of $k$. Commented Jan 12, 2021 at 22:45
• Also could you show why $h$ is surjective? I am trying to use your hint but I do not know what to do further.
– RFZ
Commented Jan 13, 2021 at 10:11

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.

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.

• In the second paragraph probably you meant: $i\mapsto e_i$ instead of $m\mapsto e_i$
– RFZ
Commented Jan 11, 2021 at 22:50
• Btw, it would be nice to see your proof that the function is surjective. I will appreciate your help!
– RFZ
Commented Jan 11, 2021 at 23:16
• thing to note is to add a $e_k = \min E\setminus\{e_1,e_2,....,e_{k-1}\}$ that $k \le e_k$. so for every $w\in E$ we have there is an $e_k$ so that $e_k \ge w$. (For example $e_w \ge w$). That means if $e_k = \min E\setminus\{e_1,....,e_{k-1}\}$ and $e_k \ge w$ either $w=\min E\setminus\{e_1,...,e_{k_1}\}$ or $w \not \in E\setminus \{e_1,...,e_{k-1}\}$ but the latter would mean $w \in \{e_1,...,e_{k-1}\}$. Eitherway there is an $e_j = w$. Commented Jan 11, 2021 at 23:38
• To be honest your second part of your reply is difficult to understand. It is a bit confusing
– RFZ
Commented Jan 12, 2021 at 10:09
• Yeah, I had a bit of a headache let me redo. Commented Jan 12, 2021 at 16:32

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.

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.