# Infinite Sets and Injective Maps

Let $A$ be infinite, meaning that there is no injection from $A$ to $\{1,...,n\}$ for all $n\in \mathbb{N}$ and assume there exists $f:A\rightarrow \mathbb{N}$ which is injective. I am trying to show there must be an bijection from $A$ to $\mathbb{N}$.

My train of thought so far has been:

Assume there is no bijection from $A$ to $\mathbb{N}$. Then $f$ is not surjective. Let $i \in \mathbb{N}$ be the smallest element of $\mathbb{N}$ which is not mapped to $\mathbb{N}$ by $f$. This gives rise to an injective map $f_i:A \rightarrow \mathbb{N}\setminus \{i\}$. If $f_i$ were surjective this means for all $j \in \mathbb{N}\setminus \{i\}$ there exists some $a_j$ in $A$ such that $f_i(a_j)=j$. Define $g:\mathbb{N}\setminus \{i\} \rightarrow \mathbb{N}$ by $g(n)=n$ for $i<n$ and $g(n)=n-1$ for $n>i$. $g$ is a bijection, and so $g\circ f_i: A \rightarrow \mathbb{N}$ is a bijection, contradiction our assumption no such function exists. Thus $f_i$ cannot be surjective. Repeating this process shows that there is no bijective map

$$f_P:A \rightarrow \mathbb{N}\setminus \{P\},$$

where $P$ is a finite set of elements of $\mathbb{N}$.

I really don't know if this is going anywhere though. Is this train of thought correct, and (if so) is there a way to extend it to a proof? If not, how would one show this?

Note: this is not homework,at least not my homework. I found it in some lecture notes I was reading.

-

Here is an alternative way to prove that:

Let $B\subseteq\mathbb N$ be the range of the injection $f\colon A\to\mathbb N$.

We will define $g\colon B\to\mathbb N$ which is a bijection, then $g\circ f\colon A\to\mathbb N$ will be a bijection (can you see why?).

$B$ is infinite and therefore non-empty, therefore it has a minimal element. Let $b_0$ be the minimal element of $B$, denote $B_0=B\setminus\{b_0\}$. Note that $B_0$ is infinite.

Suppose that $b_n$ and $B_n$ were defined. Since $B_n$ is infinite, it is non-empty and thus has a minimal element. Call this element $b_{n+1}$, and define $B_{n+1}=B_n\setminus\{b_{n+1}\}$. We only removed one element, so $B_{n+1}$ is infinite.

The map $g(b_n)=n$ is a bijection between $B$ and $\mathbb N$. It is surjective because we defined $b_n$ for all $n\in\mathbb N$ in the induction process, and it is injective because whenever $b,b'\in B$, and $b\neq b'$ there is some $n$ such that $b\in B_n$ and $b'\notin B_n$ (or vice versa). In such case $g(b)\geq n>g(b')$.

Now we have a bijection between $A$ and $\mathbb N$ defined as $g\circ f$.

-

Perhaps this is equivalent to what you wrote, but I find it easier to argue directly rather than by contradiction:

Let $f:A \to \mathbb{N}$ be an injection. Define a function $g:A \cong \mathbb{N}$ by $$g(a) = |\{b \in A : f(b) < f(a)\}|.$$

One way to see that $g$ is a bijection $A \cong \mathbb{N}$ is to notice that because $A$ is infinite, the range of $f$ is unbounded and therefore has order type $\mathbb{N}$. The function $f$ induces a well-ordering of $A$ by $a \prec b \iff f(a) < f(b)$. The function $g$ is just the canonical bijection of $A$ with the order type of this well-ordering of $A$.

Less formally, $g(0)$ is the $a \in A$ such that $f(a)$ is least, $g(1)$ is the $a \in A$ such that $f(a)$ is second-least, and so forth.

-