In Response to a Math Question

I got a comment a few posts back about Graham's number and whether it larger than a googolplex of towers or some such thing. Let me first say sorry for not replying to that; I thought I had, but apparently just thought about it for a little and forgot to write anything up. The answer is I have no idea. I don't even know where you would begin trying to prove something like that. If you read the wikipedia link about Graham's number, then you actually know more about it than I do, since I didn't finish reading it originally and then forgot all about it until now.

If you don't feel like reading about what it is, suffice it to say that it is a positive integer that was given as an upper bound to a problem in Ramsey theory, which is a branch of graph theory. I don't really know much about it, but it seems like an interesting branch of mathematics, albeit one that I don't think about much. As for how large it is, I think only the word unfathomably suffices to describe it. Something like there aren't enough particles in the universe to save it in digital form.

In order to keep this post slightly less low-content, I'll mention that what amazes me is that even though numbers like Graham's number are basically impossible to get a handle on, in math we routinely deal with things that are much, much larger than that. For as large as it is, it's still a finite number (which is the same as a finite ordinal [sort of]!), and we deal with sets that are infinite all the time.

I think we sort of lose track of how big infinite is because we think of sets like the natural numbers, which are infinite, but we think of them in forms like

{1,2, ...}

which sort of hides the fact that there are huge things in there and it's almost easy to forget that.

Now, to blow your mind a little bit, which are there more of, non-negative integers, or non-negative even numbers? Intuitively, there are more non-negative integers since all even non-negative integers are non-negative integers. But consider the function f(n) = 2n. It turns each non-negative integer into an even non-negative integer, and it does it in such a way that we don't repeat anything and every even non-negative integer gets hit. So there must be the same number of them.

So it's natural to think that maybe there are only finite and infinite things, and in the literal sense that is true: something is either finite or NOT finite, but in a sense it isn't true. There are lots of infinities. For example, consider the real numbers. If you don't know what that is, suffice it to say consider the set of all sequences you can make of 0's and 1's. Now, if that set is the same size as the positive integers (or non-negative integers, or just integers, or even rational numbers), then we can count them, and we can make a new sequence by starting with the first sequence and setting the first entry of the new sequence to be the opposite of whatever the first sequence is. That is, if the first sequence has a 0 in the first place, choose a 1, and if it had a 1, choose a 0. Then move on to the second sequence and do the same thing with the second entry of the new sequence.

If you keep doing this for each sequence, you'll get a new sequence that differs from every sequence in one place, so can't be an element of the original set of sequences, but is clearly just made of 0's and 1's, so must be an element of the original set. So, there's a contradiction and you must have a bigger set than the natural numbers. In math terms, we say that the real numbers form an uncountable set.

Can we get even bigger? Yeah, just consider the set of all subsets of the real numbers. Then consider the set of all subsets of that set, and so on and so forth. Cantor proved that you always get a bigger set by doing this, so that there is no largest set. It gets even crazier than that, but I guess that's enough food for thought.