The rationals and their countability

Question

I know this question has been asked endlessly on the internet, however, I was hoping someone could help me see an error in these two "examples" that always popped into my head when anyone mentions the subject.

Countably infinite is defined as having a one-to-one mapping with the natural numbers. The immediate idea that comes to me is that the naturals are themselves rationals, so the identity mapping causes problems for me. We map each natural number to itself and viola, we've exhausted all counting numbers just mapping to themselves; nothing left for the likes of $\frac{1}{2}$. I try to counter this by using the "endless hotel" idea: since there's an infinite number of naturals, just scoot one space over and fit in another rational, then repeat. This seems fishy. For one, maybe it's wrong outright, but it also raises the question of why we can't do the same thing when working with the irrationals.

The other thought that comes to me is the mapping of some natural "$n$" to a rational $\frac{1}{10^n}$. This should be a one-to-one mapping that'll exhaust all naturals, yet we don't even get past one on the number line.

I've long since given up on trying to intuitively understand these things, though these thoughts want answers and I want to know how these seemingly simple counterexamples fail.

Thank you for input and your time!

Answer 1

The fact that one mapping is not a bijection of the naturals to the rationals doesn't prevent a different mapping from being one.

Answer 2

"The immediate idea that comes to me is that the naturals are themselves rationals"

That's okay. Infinite sets may be in one to one correspondence with proper subsets of themselves. The can never happen with finite sets but it's possible (sometimes) with infinite sets because we might (but not always) be able to infinintely squoosh them together.

"We map each natural number to itself and viola, we've exhausted all counting numbers just mapping to themselves; nothing left for the likes of 12. "

This isn't a problem. That was only one way of mapping them and it was a dead end. So we do a different mapping. A "thicker" mapping.

" I try to counter this by using the "endless hotel" idea: since there's an infinite number of naturals, just scoot one space over and fit in another rational, then repeat."

In theory this would work. But you need to have a list that places the rationals in order one by one. There are such lists and indeed making a one-to-one correspondence is nothing more or less then creating such a list.

I'll repeat that as that is key.

Putting things in one-to-one corespondence with the naturals is the same thing as making a list listing the things one after another.

It would be better to do the standard indexing $\frac 11, \frac 21, \frac 12, \frac 31, \frac 22, \frac 13, \frac 41, \frac 32, \frac 23, \frac 14, \frac 51$ ... etc. (and we toss out the repeats as we see them). That is a legitimate way to make a list of the rationals.

(Admittedly it's bit handwavy and visual rather than a rigorous mathematical proof, but it is a proper list.)

" For one, maybe it's wrong outright, but it also raises the question of why we can't do the same thing when working with the irrationals. "

Well,... heh, heh. That is because we can't list the irrationals one after another. So we can't add them one at a time. (Or... if we did we wouldn't get them all.)

Of course, figuring out that you can't list the irrationals one after another is a big deal, and a significant result. For now, I am asking you to take my word for it that it is impossible.

"The other thought that comes to me is the mapping of some natural "$n$" to a rational $\frac 1{10^n}$"

That is indeed a proper mapping and $\mathbb N$ and $\{\text{negative powers of ten}\}$ do indeed have the same cardinality.

*"This should be a one-to-one mapping..."

It is.

" that'll exhaust all naturals,"

It does.

" yet we don't even get past $1$ on the number line. "

This mapping, I'll call it $k$ is such that $k: \mathbb N \rightarrow \{\text{negative powers of ten}\}$ via $k(n) = \frac 1{10^n}$ "exhausts the naturals" as input to the mapping. The exhausted output may be entirely different range of values.

And there is not an issue that we never "get past $1$". There are an infinite number of points to pick between $0$ and $1$ so not getting past $1$ is not significant of anything, as we can pick them all from less than $1$.

=====

So that's that. That's how you can have 1-1 maps for $\mathbb N$ to (and from) subsets of $\mathbb N$. It's also how you can have 1-1 maps for $\mathbb N$ to (and from) sets of which $\mathbb N$ is subset. (Ex. $\mathbb N$ and $\mathbb Z$ can be made $1-1$. So can the set of all pairs of integers $(n,m)$ in the set you notate as $\mathbb Z \times \mathbb Z$ is also the same cardinality.)

The nest really BIG concepts are infinite sets that can NOT be put in 1-1 corespendence with the naturals.

Such as the reals. That's a discussion for later.