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!


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

The second sentence in you proof has a wrong preamble. It should read:

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.

  • $\begingroup$ diagonalize! yay, i love diagonalization arguments $\endgroup$ – Rustyn Aug 26 '14 at 21:49
  • $\begingroup$ @EmanuelePaolini , I've re-elaborated my proof, check it again. $\endgroup$ – Guilherme Duarte Aug 27 '14 at 0:07
  • $\begingroup$ @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. $\endgroup$ – Emanuele Paolini Aug 27 '14 at 6:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.