Showing that the set of natural number, $\omega$, is Dedekind infinite. It is an easy task to show this directly by sending $n$ to $2n$, then we produces a injective map that is not surjective.

But suppose I want to make use of this fact that there is a bijection between $\omega $ and $\omega+1 = \omega\ \cup \{\omega\}$, how might one produce an injective map from $\omega$ to $\omega$ that is not surjective ?

Cheers and thanks


Simply compose a bijection $f\colon\omega+1\to\omega$ with the inclusion map $\omega\subseteq\omega+1$. In other words, simply restrict $f$ to $\omega$.

Since $\omega$ is a proper subset of $\omega+1$, the result will be an injection from $\omega$ to itself whose range is not $\omega$.

  • $\begingroup$ Ah! Because I need the '+1' to hit every $x \in X$ using $f$, so if I just restrict $f$, then I am bound to miss some guy. It remains injective because restriction does not affect injectivity. $\endgroup$ – some1fromhell Nov 27 '19 at 15:44

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.