What Does it Really Mean to Have Different Kinds of Infinities?

Suppose no one ever taught you the names for ordinary numbers. Then suppose that you and I agreed that we would trade one bushel of corn for each of my sheep. But there's a problem, we don't know how to count the bushels or the sheep! So what do we do?

We form a "bijection" between the two sets. That's just fancy language for saying you pair things up by putting one bushel next to each of the sheep. When we're done we swap. We've just proved that the number of sheep is the same as the number of bushels without actually counting.

We can try doing the same thing with infinite sets. So suppose you have the set of positive integers and I have the set of rational numbers and you want to trade me one positive integer for each of my rationals. Can you do so in a way that gets all of my rational numbers?

Perhaps surprisingly the answer is yes! You make the rational numbers into a big square grid with the numerator and denominators as the two coordinates. Then you start placing your "bushels" along diagonals of increasing size, see wikipedia.

This says that the rational numbers are "countable" that is you can find a clever way to count them off in the above fashion.

The remarkable fact is that for the real numbers there's no way at all to count them off in this way. No matter how clever you are you won't be able to scam me out of all of my real numbers by placing a natural number next to each of them. The proof of that is Cantor's clever "diagonal argument."

Hilbert's Hotel is a classic demonstration.

How there can be different kinds of infinities?

This is very simple to see. This is because of:

Claim: A given set $X$ and its power set $P(X)$ can never be in bijection.

Proof: By contradiction. Let $f$ be any function from $X$ to $P(X)$. It suffices to prove $f$ cannot be surjective. That means that some member of $P(X)$ i.e., some subset of $S$, is not in the image of $f$. Consider the set:

$T=\{ x\in X: x\not\in f(x) \}.$

For every $x$ in $X$ , either $x$ is in $T$ or not. If $x$ is in $T$, then by definition of $T$, $x$ is not in $f(x)$, so the set $T$ can not be the set $f(x)$ (because $x\in T$ but $x\not\in f(x)$). On the other hand, if $x$ is not in $T$, then by definition of $T$, $x$ is in $f(x)$, so again the set $T$ can not be the set $f(x)$. We just proved that $T$ is NOT $f(x)$ for any $x$, and so $f$ is not surjective. Q.E.D.

Thus take any infinite set you like. Then take its power set, its power set, and so on. You get an infinite sequence of sets of increasing cardinality(Here I am skipping a little; but a use of the Schroeder-Bernstein theorem will fix things).