Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

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$.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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