Is there a 1-1 function $f: \mathbb{N} \rightarrow A$? Assume $g: A \rightarrow A $ is a 1-1 but not onto function. What does that tell us about an injective function $f$ from $\mathbb{N}$ to $A$?


*

*In this case, $A$ would have to be an infinite set since if the set were finite, such a $g$ could not exist. It seems as though such a 1-1 function $f$ exists, but any suggestions on how to proceed from here to show that there is one?

 A: Once you have established that $A$ is an infinite set, it is possible to define $f$ by induction as follows. There exists some $a_1\in A$. Define $f(1)=a_1$. Since $A$ is infinite, there exists some $a_2\in A$ such that $a_2\neq a_1$. Define $f(2)=a_2$. Suppose you have defined $f(1),f(2),\dots f(n)$. Since $A$ is infinite, there exists $a_{n+1}$ different from all the previous elements $a_1,\dots, a_n$. Define $f(n+1)=a_{n+1}$. It is clear that $f$ is $1-1$.
A: The trick is to realize that if $A$ is finite then a function $f: A\to A$ is one-to-one if and only if it is surjective.  (Why?  That's a standard exercise.)
So if $f:A\to A$ is one to one but not surjective then $A$ must be infinite.  And the definition of infinite is that there injection from $\mathbb N \to A$.
So that's all there is to it.
A: Given such a function $g$, there is actually a more or less explicit way to construct an injective function $f : \mathbb{N} \to A$.  (To be more formal, you can show the existence of $f$ using only a single "choice" at the beginning - which then doesn't even require the Axiom of Choice, just a single application of the formal $\exists E$ rule.)
Namely, using the assumption that $g$ is not surjective, choose $a_0 \in A$ which is not in the image of $g$.  Now, define $f : \mathbb{N} \to A$ by recursion such that $f(0) = a_0$, $f(1) = g(a_0)$, $f(2) = g(g(a_0))$, $\ldots$, $f(n+1) = g(f(n))$, $\ldots$  It then turns out that $f$ will be injective.
To see this, we will show by induction on $n$ that whenever $m > n$, $f(m) \ne f(n)$.  For the base case $n = 0$, we need to show that if $m > 0$, then $f(m) \ne f(0)$.  However, $f(m) = g(f(m-1))$ whereas $f(0) = a_0$ is not in the image of $g$.
For the inductive case, assume that whenever $m > n$, $f(m) \ne f(n)$.  We then need to show that whenever $m > n+1$, $f(m) \ne f(n+1)$.  However, we have by the inductive hypothesis that $f(m-1) \ne f(n)$, so by the injectivity of $g$, we get $g(f(m-1)) \ne g(f(n))$.  But then, $g(f(m-1)) = f(m)$ and $g(f(n)) = f(n+1)$, so this gives exactly what we wanted.
