# Any infinite set contains a countable subset. Why is my proof wrong? (Axiom of Choice) [duplicate]

Let $$M$$ be an infinite set.

Proposition 1:
For any $$n \in \mathbb{N}$$, there exists an injection from $$\{1, \cdots, n\}$$ to $$M$$.

(1)
Since $$M \neq \emptyset$$, there exists $$x \in M$$.
Define $$f(1)$$ as $$f(1) := x$$.
$$f$$ is an injection from $$\{1\}$$ to $$M$$.
(2)
Suppose that there exists an injection $$f$$ from $$\{1, \cdots, n\}$$ to $$M$$.
Since $$M$$ is an infinite set, $$M - \{f(1), \cdots, f(n)\}$$ is not an empty set.
So, there exists $$x \in M - \{f(1), \cdots, f(n)\}$$.
Define $$g(1), \cdots, g(n+1)$$ as $$g(1) := f(1), \cdots, g(n):=f(n)$$ and $$g(n+1) := x$$.
Obviously, $$g$$ is an injection from $$\{1, \cdots, n+1\}$$ to $$M$$.

Let $$n_1$$ be an arbitrary natural number.
If I wanna calculate $$h(n_1)$$, then I get an injection $$g$$ from $$\{1, \cdots, n_1\}$$ to $$M$$ by Proposition 1.
And I return $$g(n_1)$$ as the value of $$h(n_1)$$.
And I store the pairs $$(1, g(1)), \cdots, (n_1, g(n_1))$$ to my database.

If I wanna calculate $$h(n_2)$$ for $$n_2 \leq n_1$$, then I search my database and I get the value $$g(n_2)$$ from my database and I return $$g(n_2)$$ as the value of $$h(n_2)$$.

If I wanna calculate $$h(n_3)$$ for $$n_3 > n_1$$, then I add the pairs $$(n_1 + 1, g(n_1+1)), \cdots, (n_3, g(n_3))$$ to my database by Proposition 1 and I return $$g(n_3)$$ as the value of $$h(n_3)$$.

I can calculate $$h(n)$$ for any $$n \in \mathbb{N}$$.

From above, we get an injection $$h : \mathbb{N} \to M$$.

Why is my proof wrong?

By the way.
Suppose that a man wanna know if I have an injection $$h : \mathbb{N} \to M$$ or not.
Then how can the man know if I have an injection $$h : \mathbb{N} \to M$$ or not?

• At "obivious g is an injection," what remains is to invoke induction. From the inmature "wanna" onward is math jibberish. What is that h thing and what is that database stuff? You are confusing programming with math. – William Elliot Feb 24 at 5:44
• How is it that $g(1) = f(1) = x$ and yet $g(n+1) = x$ means that $g$ is clearly an injection? – Boots Feb 24 at 6:48
• Also I agree with the previous comment that everything after "wanna" is complete and total nonsense. h isn't even defined for example. – Boots Feb 24 at 6:49
• I feel like I'm missing a few others from this duplicate list. While it might be that none of them analyze this specific argument, they all give the same explanation. Induction lets you get all the way to $\omega$, but not to $\omega+1$. – Asaf Karagila Feb 24 at 8:15
• My favorite example to illustrate that last point, by the way, is as follows. Proposition 1. For every $n$ there is a decreasing sequence of natural numbers of length $n$. Proposition 2. There is no infinite decreasing sequence of natural numbers. – Asaf Karagila Feb 24 at 11:36