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.


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.