Do you know whether this inequality is true?

clip_image002[3]

It’s a simple question, but with an intriguing and revealing answer.

Infinity #1

One concept of infinity that most people would have encountered in a math class  is the infinity of limits. With limits, we can try to understand 2 as follows:

clip_image002

The infinity symbol is used twice here: first time to represent “as x grows”, and a second to time to represent “2x eventually permanently exceeds any specific bound”.

If we use the notation a bit loosely, we could “simplify” the limit above as follows:

clip_image002[4]

This would suggest that the answer to the question in the title is “No”, but as will be apparent shortly, using infinity notation loosely is not a good idea.

Infinity #2

In addition to limits, there is another place in mathematics where infinity is important: in set theory.

Set theory recognizes infinities of multiple “sizes”, the smallest of which is the set of positive integers: { 1, 2, 3, … }. A set whose size is equal to the size of positive integer set is called countably infinite.

  • “Countable infinity plus one”
    If we add another element (say 0) to the set of positive integers, is the new set any larger? To see that it cannot be larger, you can look at the problem differently: in set { 0, 1, 2, … } each element is simply smaller by one, compared to the set { 1, 2, 3, … }. So, even though we added an element to the infinite set, we really just “relabeled” the elements by decrementing every value.

    image

  • “Two times countable infinity”
    Now, let’s “double” the set of positive integers by adding values 0.5, 1.5, 2.5, … The new set might seem larger, since it contains an infinite number of new values. But again, you can say that the sets are the same size, just each element is half the size:

    image

  • “Countable infinity squared”
    To “square” countable infinity, we can form a set that will contain all integer pairs, such as [1,1], [1,2], [2,2] and so on. By pairing up every integer with every integer, we are effectively squaring the size of the integer set.

    Can pairs of integers also be basically just relabeled with integers? Yes, they can, and so the set of integer pairs is no larger than the set of integers. The diagram below shows how integer pairs can be “relabeled” with ordinary integers (e.g., pair [2,2] is labeled as 5):

    image

  • “Two to the power of countable infinity”
    The set of integers contains a countable infinity of elements, and so the set of all integer subsets should – loosely speaking – contain two to the power of countable infinity elements. So, is the number of integer subsets equal to the number of integers? It turns out that the “relabeling” trick we used in the first three examples does not work here, and so it appears that there are more integer subsets than there are integers.

Let’s look at the fourth example in more detail to understand why it is so fundamentally different from the first three. You can think of an integer subset as a binary number with an infinite sequence of digits: i-th digit is 1 if i is included in the subset and 0 if i is excluded. So, a typical integer subset is a sequence of ones and zeros going forever and ever, with no pattern emerging.

And now we are getting to the key difference. Every integer, half-integer, or integer pair can be described using a finite number of bits. That’s why we can squint at the set of integer pairs and see that it really is just a set of integers. Each integer pair can be easily converted to an integer and back.

However, an integer subset is an infinite sequence of bits. It is impossible to describe a general scheme for converting an infinite sequence of bits into a finite sequence without information loss. That is why it is impossible to squint at the set of integer subsets and argue that it really is just a set of integers.

The diagram below shows examples of infinite sets of three different sizes:

image

So, in set theory, there are multiple infinities. The smallest infinity is the “countable” infinity, image0, that matches the number of integers. A larger infinity is image1 that matches the number of real numbers or integer subsets. And there are even larger and larger infinite sets.

Since there are more integer subsets than there are integers, it should not be surprising that the mathematical formula below holds (you can find the formula in the Wikipedia article on Continuum Hypothesis):

clip_image002[4]

And since image0 denotes infinity (the smallest kind), it seems that it would not be much of a stretch to write this:

clip_image0023

… and now it seems that the answer to the question from the title should be “Yes”.

The answer

So, is it true that that 2 > ∞? The answer depends on which notion of infinity we use. The infinity of limits has no size concept, and the formula would be false. The infinity of set theory does have a size concept and the formula would be kind of true.

Technically, statement 2 > ∞ is neither true nor false. Due to the ambiguous notation, it is impossible to tell which concept of infinity is being used, and consequently which rules apply.

Who cares?

OK… but why would anyone care that there are two different notions of infinity? It is easy to get the impression that the discussion is just an intellectual exercise with no practical implications.

On the contrary, rigorous understanding of the two kinds of infinity has been very important. After properly understanding the first kind of infinity, Isaac Newton was able to develop calculus, followed by the theory of gravity. And, the second kind of infinity was a pre-requisite for Alan Turing to define computability (see my article on Numbers that cannot be computed) and Kurt Gödel to prove Gödel’s Incompleteness Theorem.

So, understanding both kinds of infinity has lead to important insights and practical advancements.

14 Comments to “Is two to the power of infinity more than infinity?”

  1. Xamuel says:

    There is also a third type of infinity: ordinal numbers. The question becomes more complicated there, since there are infinite ordinals x with 2^x>x, but there are also infinite ordinals x with 2^x=x.

  2. \aleph_1 is by definition the smallest infinity greater than \aleph_0, and \aleph_2 is the smallest infinity greater than \aleph_1. So the number of real numbers is only \aleph_1 if the continuum hypothesis is true. See Aleph number and Beth number.

  3. Xamuel: Yeah, ordinal numbers are an interesting topic. That is getting beyond my current level of math competence, though. :)

    Alexey Romanov: That is a fair point. Had I used the Beth number notation, the article would not have to rely on this unexplained assumption.

  4. Andrew Borodin says:

    Hello, Igor! Nice article, it’s always so exciting to get back to math analysis theory class in thoughts…Oh yeah, i’ve burned my first parker on math analysis, literally burned, inserting it into scratched wall outlet.
    So, to the point. How do you think, would it be interesting to write article on floating point resolution? There are so many integers in most recent articles..

  5. [...] Igor Ostrovski: Is two to the power of infinity more than infinity? [...]

  6. craig says:

    Also
    Lim x/2^x = 0
    x->oo

    from which it can be vaguely inferred that 2^x(set of all subsets) grows extremely faster than x.

  7. am says:

    2^x > x

    Who told you it is always right?

    if x is 0 ,is it right?

    if x > 0, is it right? the program of x variable overflow.result is right?

  8. [...] Is two to the power of infinity more than infinity? (igoro.com) [...]

  9. George says:

    There is also a third type of infinity: ordinal numbers. The question becomes more complicated there, since there are infinite ordinals x with 2^x>x, but there are also infinite ordinals x with 2^x=x

  10. jods says:

    This comment is regarding your MSDN article about C# Memory Model (part 2). Sorry to post here but I couldn’t find any other place to discuss it.

    One section really bothered me: the one about “read introduction”. What are the rules here precisely? Many code patterns rely on a local variable to guarantee immutability of values during the scope of execution. The most famous one being thread-safe event invocation:

    void OnSomeEvent(EventArgs e)
    {
    SomeEventHandler handler = this.SomeEvent;
    if (handler != null)
    handler(this, e);
    }

    This has been the recommended pattern to raise an event in a thread-safe way since .net 1.

    The reasoning is that if this.SomeEvent becomes null because of a concurrent event removal between the if() and the call, the call wouldn’t throw NullReferenceException since it would use its non-null local variable.

    Now, if you allow the CLR to perform a read introduction and effectively replacing the if body “handler(this, e)” by “this.SomeEvent(this, e)”, you’ve lost all tread safety.

    Is this pattern really broken? Am I missing something here?

    It seems to me that introducing reads instead of using a local variable is a very dangerous thing to do.

  11. Anonymous says:

    Congratulations for reinventing the wheel! You just quote here Cantor’s theorem stating that a power set (P(X)) is always greater than the original set (X).
    Or from the other point of view, big-O notation, O(2^x) > O(x) which is also a very basic fact.
    Sorry for that, but some other articles of yours are really interesting (CPU cache effects for example).

  12. reshmi says:

    Which one will go faster and why : 2∞ ( 2 to the power infinity) or ∞2 (infinity square) ?

  13. Joshua Scholar says:

    Even though the usual definition of integers doesn’t include the uncountable infinities that 2^(aleph0) gives you, if you DID use the resulting set of both integers and uncountable infinities as a new integer set, I’m sure the resulting mathematics would still be consistent.

    So now you have integers with the order of the continuum. I wonder if they’re useful for anything.

    The obvious first question is whether 2^(continuum) is a different set than 2^(aleph0) or whether it even makes sense to write 2^(continuum).

  14. Joshua Scholar says:

    One way to look at it is that our usual definition of reals is not symmetrical.

    reals have a finite number of digits before the decimal (or since you write 2^ rather than 10^, binary point) but an infinite number of digits AFTER the point.

    But you COULD base a mathematics on having an infinite number of digits before the point. Since the infinite sequence could be all zeros you’d still have a subset of finite integers.

    You could also have a mathematics that only has a finite number of digits after the point (machine fixed point numbers), but in that you couldn’t represent fractions precisely.

Leave a Reply

You can use these tags: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>