Measuring infinity, and beyond

Alright, inspired by a conversation with my dear sister castlerock, I've decided to publish something a little different today. I'm going to be talking about infinity, and the different types of infinity that occur in higher mathematics.

Most people deal with infinity every day:

• "I will love you forever"
  
• "When you die, you are dead forever."
  
• "You go to heaven forever."

We also play games as children:

• "I'm better than you times infinity, plus 1!"

In one way, the concept of "infinity" is easy to understand. I believe the brain has a special internal language for the words "this pattern holds," also known as "and so on", "yadda yadda yadda," "forever". Forever encompasses the idea of closure. It means that if you understand a finite number of things, you can extrapolate and deal with real world problems. Mentally, we perform this powerful reduction all the time. Without it, we wouldn't be able to cope. In this way, infinity in comforting.

However, if you look at infinity from a size standpoint, infinity is dizzyingly terrifying. Most people don't have a proper concept of what "large" means, but mathematicians know better:

• The universe is 13.7 billion years old, or 4.3*10^-17 seconds. Current quantum theory has trouble measuring time below Planck's time constant, or 1.855×^-43 s. If we treat the idea of time as a discrete number of Planck's constants, then the age of the universe is 8*10^60 of these constants. Infinity is bigger than this.
  
• The number of atoms in the universe is estimated to be around 10^80.
  
• The biggest number ever seriously used in mathematics is Graham's number. The number is an upper bound for some mathematical property. The number is so huge that it cannot be written with scientific notation (the exponent would have more digits than atoms in the universe). Still, infinity is bigger than this number.
  
• The Ackermann function is a strange non primitive recursive function:
  
  This function generates huge finite numbers. For example, A(5,2) is so large that it cannot be describing it with common math notation would take more letters than there are atoms in the universe (this includes 9^9^9^9^9^9... etc.). Still, infinity is bigger than this number.

In fact, infinity is more than just a really huge number. Infinity breaks our notion of numbers altogether.

• Say we have a set of all integers, and we split that up into a sets of all even integers and all odd integers. Obviously, any integer is going to be even or odd, and no integer can be both. Therefore, the set of all even integers is smaller than the set of all integers, right? Wrong. The size of the set of even integers is the same size as integers.
  
• A line goes to infinity in two directions, but a ray only goes to infinity in one direction. Still, lines are the same size as rays, even though if you divide a line in half, you get two rays.

The reason our intuition breaks is that infinity isn't a number. x/2 is less than x if x is finite, but infinity/2 is an abuse of notation, and technically gives you infinity again. The same goes for infinity+1, or infinity+infinity. All our intuition about the "measure" of things is broken by infinity, so we need a new idea of what it means to measure something infinite.

Richard Dedekind and George Cantor came up with a clever solution to compare sets with infinite size. If you have two sets A and B, and you can construct a mapping (a->b) so that every b is covered, then size(A) >= size(B). For finite sets this can be seen by the following diagram. As you can see, there is no mapping from B to A that covers all of A.



This idea is useful because it allows us to compare the size of sets without having to say what size(A) is. Also this definition corresponds to infinite sets as well: For example, positive integers = even integers because we can construct the mappings (n -> 2n) and (2n -> n). Therefore, A <= B and B >= A, so A=B.

So what infinite sets are equal to each other? The following sets all have the same size:

• N, the set of positive integers
  
• The set of all integers
  
• All subsets of integers
  
• The 2d natural number plane, (N, N)
  
• Q, the set of all numbers that can be written as n/m where n and m are integers.

However, you can prove that the set of real numbers between 0 and 1 (which includes things like sqrt(2)-1) is BIGGER than the set of all positive integers. Wikipedia does a good job of explaining the proof, I'll write it out in detail if people are interested.

Higher mathematics has two different words for types of infinity. Countable infinity means the size of the set is equal to the size of positive integers, and uncountable infinity means that it's not. We distinguish between these two cases because working with countably infinite things is nice and working with uncountably infinite things is messy.

In numerical analysis, this is really important for solving equations. Let's say that we're trying to find a unique function from 0 to 1 to real numbers with a special property. There are an uncountably infinite number of these functions. If we write a computer program to test all these functions and let it run forever, that computer program can only do a countably infinite number of function tests. We can prove this by numbering the tests that the computer does them. Therefore, no computer can test all possible functions, even if it runs forever.

Does this mean that trying to solve a differential equation on a computer is hopeless? The answer is yes and no. We cannot solve a differential equation exactly, but by allowing some error, we can transform the uncountably infinite space into some thing that is countably infinite or even finite. This is the heart of all numerical analysis.

(
Side note, if you want to win the "I'm better times infinity plus 1" game, here are a couple of guidelines:
* ack(n,n) > n^n for large n
* n^n > n! for large n
* n! > x^n, x finite, for large n

When someone tells you they are better than you by "infinity plus 1", use some of these huge functions to blow them away.
)