# Find an injective but not surjective function to a infinite set X

A set if infinite iff there exists an injective function f that maps X to X for which f(x) is a proper subset of X. I only know that set X is infinite and I do not know anything about the range of the set. Could any one give me an example of an injective but not surjective mapping of X?

Thank you

## 2 Answers

If the only thing you know about $X$ is that it is infinite, then it is not possible to describe such a mapping precisely enough that you can know what it does to each element. You don't even know what the elements are, so how would the example be able to tell what happens to them?

Using the Axiom of Choice, one can prove (see below) that every infinite $X$ has a subset $Y$ that is in bijective correspondence with $\mathbb N$. In that case you can construct $f$ as "for every element $x$ that corresponds to a natural number $n$, $f(x)$ is the element that corresponds to $n+1$; if $x$ doesn't correspond to a natural, $f(x)=x$.

Proof of above claim. Let $X$ be infinite; we want to construct a injection $\varphi:\mathbb N\to X$. Then the image of $\varphi$ will be the requested $Y$.

Fix a choice function $g:\mathcal P(X)\setminus\{\varnothing\}\to X$, and define $\varphi$ recursively: $$\varphi(n) = g\bigl( X\setminus \{\varphi(i) \mid i<n\} \bigr)$$ The argument $X\setminus\{\varphi(i) \mid i<n\}$ is always non-empty because $X$ is infinite and there are only finitely many $\varphi(i)$ with $i<n$. So there are elements in $X$ that don't get removed.

Then $\varphi$ is injective: If $b>a$, then $\varphi(a)\ne\varphi(b)$ because $\varphi(b)$ will have been constructed as $g$ of a set where $\varphi(a)$ has explicitly been removed.

(Actually one needs only the axiom of Countable Choice, but that's a bit more involved -- see sketch by Asaf in the comments).

• Actually with the given definition of infinite, we don't need the axiom of choice. But as long as $X$ is arbitrary we can't really give any examples. – Asaf Karagila Apr 2 '14 at 22:46
• @AsafKaragila: My interpretation was that the first sentence of the question was a result following from the standard definition rather than a definition itself. Otherwise "I only know $X$ is infinite" would mean that the only thing the OP knows is the very function he's looking for ... – Henning Makholm Apr 2 '14 at 22:48
• (Also, one just needs countable choice which is weaker than Dependent Choice, and in fact that too is more than needed for the theorem you give (but probably the simplest nontrivial choice principle we can formulate for this proof)) – Asaf Karagila Apr 2 '14 at 22:49
• @Asaf: Is countable choice enough? Since we have no bound on the size of $X$, I don't see how we could bring that to bear here. (Edit: I found a proof on Wikipedia). – Henning Makholm Apr 2 '14 at 22:51
• @user139950: That is definitely the wrong hint. The correct hint is that the union of two finite sets is finite. – Asaf Karagila Apr 2 '14 at 23:02

Let $X$ be the natural numbers and let $f ( x ) = x+1$ the mapping is injective and range$(f )=\mathbb {N}\setminus \{1\}$ which is infinite.