Why can the set of all natural numbers and omega be put in one-to-one correspondence with natural numbers? 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.

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$.
