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:
There is no element in $\Bbb{N}$ which maps to $\{0\}$.
$\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!
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.