# Different kinds of infinities?

Can someone explain to me how there can be different kinds of infinities?

I was reading "the man who loved only numbers" and came across the concept of countable and uncountable infinities, but they're only words to me.

Any help would be appreciated.

-
I've removed the tag "infinity," which I believe to be an odd combination of too vague and too localized, and thus easily abused. If there end up being a lot of questions about "infinity" later on, as I suspect there might be given the broader audience, I could be convinced that it's a good tag to reinstate for askers that will not know where their question fits in otherwise. –  Jamie Banks Jul 22 '10 at 19:11

Suppose no one every 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 numbers and I have the set of rational numbers and you want to trade me one positive number 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."

-
Fantastic answer! –  Allain Lalonde Jul 20 '10 at 19:24
I like this so far, but maybe add a bit on uncountable to distinguish the difference. –  BBischof Jul 20 '10 at 19:26
That's a really good answer, thanks :D –  FallingBullets Jul 20 '10 at 19:39
Why can't lecturers at Uni explain things in this way? –  Sachin Kainth Oct 1 '12 at 16:45
+1 for "fancy language" –  Tyler Langan Dec 4 '12 at 9:36

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 $T$ is not equal to $f(x)$. On the other hand, if $s$ is not in $T$, then by definition of $T$, $x$ is in $f(x)$, so again $T$ is not equal to $f(x)$. 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).

-

Hilbert's Hotel is a classic demonstration.

-
A really good book on the subject was written by David Wallace Foster, Everything and More: A Compact History of Infinity –  FordBuchanan Jul 20 '10 at 19:37
David Foster Wallace. (RIP :-( ) –  Jason S Jul 20 '10 at 23:03

A countably infinite set is a set for which you can list the elements a1,a2,a3,...

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?

1/1,1/2,2/1,1/3,2/2,3/1,1/4,2/3,3/2,4/1,1/5,2/4,...

(Hint: Add the numerator and denominator to see a different pattern.) This listing has lots of repeats, e.g. 1/1, 2/2 and 1/2, 2/4. That's ok since I can condense the listing by skipping over any repeats.

1/1,1/2,2/1,1/3,3/1,1/4,2/3,3/2,4/1,1/5,...

Let's write qn for the n-th element of this list. Then 0,q1,-q1,q2,-q2,q3,-q3,... 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...

-

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.

-

You can see that there are infinitely many natural numbers 1, 2, 3, ..., and infinitely many real numbers, such as 0, 1, pi, etc. But are these two infinities the same?

Well, suppose you have two sets of objects, e.g. people and horses, and you want to know if the number of objects in one set is the same as in the other. The simplest way is to find a way of corresponding the objects one-to-one. For instance, if you see a parade of people riding horses, you will know that there are as many people as there are horses, because there is such a one-to-one correspondence.

We say that an set with infinitely many things is "countable," if we can find a one-to-one correspondence between the things in this set and the natural numbers.

E.g., the integers are countable: 1 <-> 0, 2 <-> -1, 3 <-> 1, 4 <-> -2, 5 <-> 2, etc, gives such a correspondence.

However, the set of real numbers is NOT countable! This was proven for the first time by Georg Cantor. Here is a proof using the so-called diagonal argument.

-

Infinity is an overloaded term that can mean many things.

One common non-mathematical use of infinity is to refer to everything in the universe. This is not what mathematicians mean when they say infinity. That would be a kin to the set of all sets, which is a paradoxical concept that is not part of mathematical discourse.

Mathematicians will use infinity as a way to represent a process that continues indefinitely. This is a kin to saying "take the limit as n goes to infinity", which is close to saying "continue this process indefinitely."

Infinity is also use infinity to talk about size. All sets are either infinite or finite.

The story doesn't stop there. There is something fundamentally different about sets like the points on a line, where there are no holes, and sets like the integers where there are holes. They are both infinite but one seems denser then the other.

That's where whole countable uncountable thing comes in. Infinite sets have a size, but it is not a number in the traditional sense. Its more like "relative size". Bijections are how we determine size for infinite sets, which are explained well on this page, so I won't repeat the explanation.

A more in-depth, but still understandable explanation is given in Computability and Logic by George Boolos.

-

How many Natural (Integers) Numbers could you count? There are infinitely many, yet you can count them. It's called Countable Set.

How many Real Numbers are there? Infinitely as well (Since at least every Natural Number is a Real Number). Yet you won't be able to count them (Intuitively, Let's say you name a number the first, then find the second, I can, for sure, find a number in between, their average which is Real Number as well).. It's called Uncountable Set.

What you are after is how we define how big is a given set. Then you should look for Cardinality.

-
Your argument that you can't count the real numbers isn't correct. To see this, notice that if you replace "real numbers" with "rational numbers", then your reasoning is still valid but the conclusion is false. That is, the rational numbers CAN be counted despite the fact that the average of any two is another one. –  Jason DeVito Oct 20 '10 at 1:50
I don't think there's an "intuitive" explanation for the unocuntability of the reals that bypasses Cantor's diagonalization argument. The countability of the rationals comes from numbering them by increasing "size"-- but we need the right idea of size for this to work. Absolute value is the wrong idea. But, for example, if we say the size is |numerator|+|denominator|, we can list all rational numbers without missing any. Try to think of such a scheme for real numbers... and diagonalization shows why it doesn't work! –  Jonas Kibelbek Oct 20 '10 at 3:14
Jason, I didn't suggest that this property is the reason why the Real numbers aren't Countable. Just intuition that their Cardinality is bigger. Intuition, not a proof. –  Drazick Nov 2 '10 at 17:32
The problem is that it is incorrect intuition. If there were validity to the intuition, then it should apply equally to the rational numbers, as Jason DeVito already pointed out. –  Jonas Meyer Jun 17 '11 at 8:50
@JonasKibelbek I think there is a kind of "a postiori intuition" for the uncountability of the real numbers: there isn't any scheme of giving finite descriptions of individual real numbers that works for all (or even most) of them. It is not much of an explanation, since it just amounts to saying they are not in bijection with a somewhat different countable set than the natural numbers, but it does give some more intuition to the notion of being countable, making obvious why the rationals are countable, for instance. –  Marc van Leeuwen Apr 28 at 7:28