# Why $\omega$ can't be bijectively mapped to $\omega +1$

Let $\omega$ be the order type of the totally ordered set $\mathbb{N}$, and $\omega +1$ the set $\Bbb{N}\cup \{0\}$.

$0$ is greater than all the natural numbers as per this ordering.

My question is why can't $\Bbb{N}$ be bijectively mapped to $\Bbb{N}\cup\{0\}$? I understand the basic argument:

1. There is no element in $\Bbb{N}$ which maps to $\{0\}$.

2. $\Bbb{N}$ is bijectively mapped to a proper subset of $\Bbb{N}\cup\{0\}$. A set can't be bijectively mapped to a proper subset of the co-domain and also the co-domain.

But I'm not confident about whether these arguments work for infinite sets. One of the reasons being I used to think if a set can be bijectively mapped to another set, then any permutation of that set can be bijectively mapped to the same set. But this is not true for mapping $\Bbb{N}\cup\{0\}$ to $\Bbb{N}$. Hence I'm not quite sure what arguments are valid for infinite sets. My questions:

1. Do my arguments work for infinite sets? If not, what arguments are required to prove that $\omega$ can't be bijectively mapped to $\omega + 1$?

2. Is picking out every element from the co-domain and proving that it has been injectively mapped to the only way of proving bijection? Does the selection of such an element assume the axiom of choice?

I realise my question may be unclear, and will attempt to make it more clear should anyone find it difficult to navigate this mess. Thanks in advance!

-
It's common to define $\omega+1$ as $\omega\cup\{\omega\}$. Since $0$ is a natural number in the context of set theory, you should probably write $\Bbb N\cup\{\Bbb N\}$. – Asaf Karagila Jul 14 '13 at 11:34

But $\omega$ and $\omega+1$ are equipotent, which is to say: there is a bijection between the two sets. Consider the map $f(n)=n+1, f(\omega)=0$.

There is just no order isomorphism between the two sets. Because order isomorphism preserves the properties of the order, in particular the existence of a maximal element. $\omega+1$ has a maximal element, whereas $\omega$ doesn't.

But more can be said: If two ordinals are order-isomorphic then they are equal.

Note that when working with sets which are well-ordered, the axiom of choice is not used. We have a definable choice function (definable from the well-order, that is). In particular, if the codomain is countable we can always make choices.

-
Yes sorry I meant a 'similarity mapping' as described in a book. $f(a)\geq f(b)$ iff $a\geq b$. I suppose that is what is meant by order isomorphism. – Ayush Khaitan Jul 14 '13 at 11:34
Sorry I'd like to add a small question with respect to your answer. You said $f(\omega)=0$. Can we do that? Is that different from saying $f(\infty)=0$ because this is a specific infinite number out of many possible infinitely huge numbers like $\omega^2$ etc? Thanks. – Ayush Khaitan Jul 14 '13 at 11:38
You should review your basics again. What is $\infty$? $\omega$ is an element in the set $\omega+1$. If we want to define a bijection we need to say where does it go. $\infty$ is not a well-defined set (at least not without context). Is it in the domain of $\omega+1$? Is it something else? Why should $f$ be defined on $\infty$? – Asaf Karagila Jul 14 '13 at 11:39
Note that there are bijections between $\omega$ and any countable ordinal, and there are countable ordinals that you can't even begin to imagine. None of these bijections is order preserving, except for the identity function. – Asaf Karagila Jul 14 '13 at 11:40
Thanks for your answer! With regard to my argument: set $A$ can't be order isomorphic with both set $B$ and a proper subset of set $B$; is this argument also valid for infinite sets? – Ayush Khaitan Jul 14 '13 at 11:48