Why can the set of all natural numbers and omega be put in one-to-one correspondence with natural numbers?

Question

If $\omega$ comes literally after we've run out of all natural numbers, then why can the set of all natural numbers and omega be put in one-to-one correspondence with natural numbers? I feel the existence of $\omega$ is somewhat contradictory for this reason. Please explain.

Answer 1

There are two distinct notions that are relevant here:

• Sets
• Ordered sets

When you talk about "$\omega$ coming after the natural numbers", you are talking about ordered sets — specifically, the ordered set $\omega + 1$. (the underlying set of $\omega + 1$ is is $\mathbb{N} \cup \{ \omega \}$)

There does not exist an order-preserving bijection between $\mathbb{N}$ and $\omega+1$.

When you talk about "$\omega+1$ can be put into one-to-one correspondence with natural numbers", you are talking about sets.

There does exist a bijection between $\mathbb{N}$ and (the underlying set of) $\omega + 1$. But by the above remarks, no such bijection can be order-preserving. As mentioned in the comments, an easy-to-consider bijection is the following correspondence:

$$ \begin{matrix} 0 & 1 & 2 & 3 & \ldots \\ \updownarrow &\updownarrow &\updownarrow &\updownarrow & \\ \omega & 0 & 1 & 2 & \ldots \end{matrix} $$

See how it doesn't preserve order: we've corresponded $0 \leftrightarrow \omega$ and $1 \leftrightarrow 0$, but as to the ordering on these two sets we have $0<1$ and $\omega > 0$.