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

Solution 1:

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

Solution 2:

Hilbert's Hotel is a classic demonstration.

Solution 3:

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

Solution 4:

A countably infinite set is a set for which you can list the elements $a_1,a_2,a_3,...$

For example, the set of all integers is countably infinite since I can list its elements as follows:

$0,1,-1,2,-2,3,-3,...$

So is the set of rational numbers, but this is more difficult to see. Let's start with the positive rationals. Can you see the pattern in this listing?

$\frac{1}{1},\frac{1}{2},\frac{2}{1},\frac{1}{3},\frac{2}{2},\frac{3}{1},\frac{1}{4},\frac{2}{3},\frac{3}{2},\frac{4}{1},\frac{1}{5},\frac{2}{4},...$

(Hint: Add the numerator and denominator to see a different pattern.)

This listing has lots of repeats, e.g. $\frac{1}{1}, \frac{2}{2}$ and $\frac{1}{2}, \frac{2}{4}$. That's ok since I can condense the listing by skipping over any repeats.

$\frac{1}{1},\frac{1}{2},\frac{2}{1},\frac{1}{3},\frac{3}{1},\frac{1}{4},\frac{2}{3},\frac{3}{2},\frac{4}{1},\frac{1}{5},...$

Let's write $q_n$ for the $n$-th element of this list. Then $0,q_1,-q_1,q_2,-q_2,q_3,-q_3,...$ is a listing of all rational numbers.

A countable set is a set which is either finite or countably infinite; an uncountable set is a set which is not countable.

Thus, an uncountable set is an infinite set which has no listing of all of its elements (as in the definition of countably infinite set).

An example of an uncountable set is the set of all real numbers. To see this, you can use the diagonal method. Ask another question to see how this works...

Solution 5:

The basic concept is thus:

• A 'countable' infinity is one where you can give each item in the set an integer and 'count' them (even though there are an infinite number of them)
• An 'uncountable' infinity defies this. You cannot assign an integer to each item in the set because you will miss items.

The key to seeing this is using the 'diagonal slash' argument as originally put forward by Cantor. With a countable infinity, you can create a list of all the items in the set and assign each one a different natural number. This can be done with the naturals (obviously) and the complete range of integers (including negative numbers) and even the rational numbers (so including fractions). It cannot be done with the reals due to the diagonal slash argument:

1. Create your list of all real numbers and assign each one an integer
2. Create a real number with the rule that the first digit after the decimal point is different from the first digit of your first number, the second digit is different from the second digit of your second number, and so on for all digits
3. Try and place this number in your list of all numbers... it can't be the first number, or the second or the third... and so on down the list.
4. Reductio Ad Absurdium, your number does not exist in your countable list of all real numbers and must be added on to create a new list. The same process can then be done again to show the list still isn't complete.

This shows a difference between two obviously infinite sets and leads to the somewhat scary conclusion that there are (at least) 2 different forms of infinity.