# Verify my proof: If $X$ is infinite, then there exists $f: \mathbb{N} \rightarrow X$ such that $f$ is injective.

Proposition: If $X$ is infinite, then there exists $f: \mathbb{N} \rightarrow X$ such that $f$ is injective.

Proof: Define $X$ as a infinite set, i. e., there does not exist $g: [k] \rightarrow X$ bijective for $k \in \mathbb{N}$.

Assume by hypothesis there does not exist a function $f: \mathbb{N} \rightarrow X$ injective. So there does not exist a function $f$ such that for all $y_1, y_{2} \in \mathbb{N}$, if $y_{1} \neq y_{2}$, then $f(y_{1}) \neq f(y_{2})$.

Suppose a function $f$ that has the largest value of k such that, for $k \in \mathbb{N} \text{ elements of } \mathbb{N}$, if $y_{1} \neq y_{2} \neq y_{3} ... \neq y_{k}$ then $f(y_{1})\neq f(y_{2}) \neq f(y_{3}) ... \neq f(y_{k})$. For other elements $y_{k+1}$ and $y_{k}$, we can have $y_{k+1} \neq y_{k}$ and $f(y_{k+1}) = f(y_{k})$. Hence we can have a function $g: [k] \rightarrow X$ bijective and X is finite. Contradiction!

Q.E.D.

• What is your definition of infinite set? – carlosayam Aug 26 '14 at 20:12
• @caya, X is infinite when there does not exist $g:{1,2,3, ..., k} \rightarrow X$ bijective for $k \in \mathbb{N}$. – Guilherme Duarte Aug 26 '14 at 20:13
• If you check en.m.wikipedia.org/wiki/Infinite_set, what you want to prove is mentioned there and requires the axiom of choice. – carlosayam Aug 26 '14 at 20:15
• But does it depend on axiom of choice? – Guilherme Duarte Aug 26 '14 at 20:18
• Your definition is different. – carlosayam Aug 26 '14 at 20:19

There does not exist a function $f$ such that for $y_1, y_{2} \in \mathbb{N}$, if $y_{1} \neq y_{2}$, then $f(y_{1}) \neq f(y_{2})$.
The last sentence is not clear at all. How is $k$ defined? I doubt you can turn that into a real proof.
To achieve the result you can proceed by induction to prove that for all $n \in \mathbb N$ there exists $f_n \colon [n] \to X$ which is injective and such that if $n<m$ then $f_n(k) = f_m(k)$ for all $k\in[n]$. You can then define the "union" of these function.
• @Guilherm: I cannot understand your proof. Seems you are saying: take the function $f$ such that the maximal set where $f$ is injective, is maximal. It's not clear at all how you can define such things. Take $f(n)=\lfloor n/2\rfloor$ and explain what is $k$ for such a function. Also the notation $a \neq b \neq c$ is bad, don't use it. – Emanuele Paolini Aug 27 '14 at 6:59