2
$\begingroup$

Let $X$ be an infinite set. I've been trying to prove that an injection from $X$ to $\mathbb{N}$ implies that $X$ is countable. I know this boils down to showing that an injection from $X$ to $\mathbb{N}$ implies the existence of a surjection from $X$ to $\mathbb{N}$. Or, equivalently, that a surjection from $\mathbb{N}$ to $X$ implies the existence of an injection from $\mathbb{N}$ to $X$.

Could someone give a proof of one of the above statements?

  • 1
    Hint, any infinite subset of $\mathbb N$ is countable.2012-09-07

3 Answers 3

3

An injection from $X$ to $\mathbb{N}$ is a bijection from $X$ to $C \subset \mathbb{N}$. As every subset of $\mathbb{N}$ is countable, we are done.

  • 0
    what about if $f$ is surjection from $X$ to $\mathbb N$ , then $X$ is countable.2014-05-18
7

Let $f : X \to \mathbb{N}$ be an injection.

Being a subset of $\mathbb{N}$, the set $f(X) = \{ f(x)\,:\, x \in X \}$ is well-ordered, and in particular it has a least element, a 2nd-least element, a 3rd-least element, and so on. Define $g : f(X) \to \mathbb{N}$ by sending the $n^{\text{th}}$-least element of $f(X)$ to $n \in \mathbb{N}$. Then the composite $g \circ f : X \to f(X) \to \mathbb{N}$ is in fact bijective, not merely surjective!

Essentially what $g$ does here is it pushes everything downwards so that there are no gaps.

6

Let $f:X\to\Bbb N$ be your injection. Let $M=f[X]$. First define a bijection $g:\Bbb N\to M$ recursively as follows. First, $g(0)=\min M$. If $n\in\Bbb Z^+$, and $g(k)$ has been defined for $k, let $g(n)=\min\Big(M\setminus\{g(0),\dots,g(n-1)\}\Big)\;.$ It’s straightforward to verify by induction that $g$ is a bijection.

Added: First, it’s clear that $g$ is injective, since the construction ensures that if $m, then $g(n)\ne g(m)$. To show that $g$ is surjective, it suffices to show that for each $n\in\Bbb N$, $\{g(k):k this ensures that each member of $M$ less than $g(n)$ is already ‘hit’ by the function $g$, so $g$ has no ‘holes’ in its range.

$(1)$ is trivially true for $n=0$: both sides are empty. Suppose that it holds for some $n\in\Bbb N$; we want to show that $\{g(k):k\le n\}=\{m\in M:m\le g(n)\}$. It’s clear that $\{g(k):k\le n\}\subseteq\{m\in M:m\le g(n)\}$, so suppose that $m\in M$, $m\le g(n)$, and $m\notin\{g(k):k\le n\}$. Then $m, and $m\notin\{g(k):k, contradicting the definition of $g(n)$ as the smallest member of $M$ not in $\{g(k):k. $\dashv$

Since $f$ is an injection, it’s a bijection from $X$ to $M$, and $f^{-1}$ is a bijection from $M$ to $X$. We now have

$\Bbb N\overset{g}\longrightarrow M\overset{f^{-1}}\longrightarrow X\;,$

where each of the maps is a bijection, so their composition is a bijection from $\Bbb N$ to $X$.

  • 0
    "It’s straightforward to verify by induction that $g$ is a bijection." Could you sketch this proof?2012-09-10