# What Does it Really Mean to Have 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" by Paul Hoffman and came across the concept of countable and uncountable infinities, but they're only words to me.

Any help would be appreciated.

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

• I like this so far, but maybe add a bit on uncountable to distinguish the difference. – BBischof Jul 20 '10 at 19:26

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

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

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.

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.

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.

This is an answer to the following question marked as duplicate which redirects here: "I've known for some time that infinitary numbers can be different in order, such as the integers (countable), and the real numbers (uncountable). I read that you can always find a higher order of infinity given any order of infinity. Since infinity is the limit of the natural numbers under the successor function, I would like to know if there is a similar concept for orders of infinity under taking power-sets, if there is a sort of "super-infinity", a limit to the orders of infinity."

Yes, there is such a concept: the smallest strongly inaccessible cardinal. Roughly, it is the smallest uncountable infinity that can not be reached by taking either unions or power sets of infinities under it, see here http://en.wikipedia.org/wiki/Limit_cardinal. Existence of such cardinals is widely believed to be independent of the standard axioms of set theory (ZFC), in other words it can neither be proved nor disproved from them. However, there are many works, where people postulate existence of strongly inaccessible cardinals and see what they can derive from it.

Of course, even with such a postulate you still don't get the "infinity of all infinities", such a concept is self-contradictory according to the Russel paradox, but the smallest strongly inaccessible cardinal is in a similar relation to the ones under it regarding power sets as the countable cardinal is regarding successors and unions.

• This is inaccurate at best. A strongly inaccessible cardinal, no matter how large, is but one size of infinity, and therefore there are yet larger ones. It does not answer the question. – Andrés E. Caicedo May 23 '14 at 2:44
• What exactly is inaccurate? As for answering the question, it is somewhat vague, but does ask for a "super-infinity" which is a "limit" for power sets in the similar way to aleph null being a "limit" for successors. Aleph null also has cardinalities above it so the analogy with the first inaccessible still holds. – Conifold May 24 '14 at 22:18
• The question asks whether there is a limit to the orders of infinity. The answer is no. It is true that the question mentions power sets, and so we may think we are discussing strong limit cardinals, but this is just because passing to power sets seems to be the only way of increasing size that the person asking knows of. We cold read even more into the question, and then decide we are discussing limits under power sets and unions, thus reaching strongly inaccessible cardinals. Again, this is us putting into the question something that is not actually there. – Andrés E. Caicedo May 24 '14 at 22:33
• The question has been edited again, and now it is explicitly about strong limit cardinals. I'm voting to reopen since this question is definitely different than "a limit to the orders of infinity" and so no longer a duplicate of this one. – Andrés E. Caicedo May 24 '14 at 22:40

Just simple intuitive explanation.

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
• 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. – Royi 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 '13 at 7:28
• And what if I name the average of my first and second number as my third number? (Perhaps you are assuming that my list is increasing; but then you should note that there are countable sets, such as the set of all integers, that can't be counted in increasing order.) – Trevor Wilson May 24 '14 at 4:11