I’ll try to keep this one quick (hint: I’ll fail), but it’s been over two weeks so I want to get something down.

This week we learned about countably infinite sets (and uncountably infinite). I’ve always been fascinated with the concept of infinity (my first and least-original high-school tattoo can attest to this) and the opportunity to finally learn about it formally was dazzling to me. I’m a bit surprised by how few class sessions it takes to go from zero knowledge of discrete math to working out my own proofs about infinite sets. Granted, this is scratching the surface and probably very rudimentary still, but exciting to me nonetheless.

Maybe for this post I’ll try something different. A quick summary on an basic, interesting observation about infinite sets.

Countably Infinite

We’re going to use the positive integers and so on in this discussion. We’ll use the shorthand for this ‘set’ of numbers. Note that is infinite in size. Take the largest of which you can imagine and add 1 to it - the result is still a member of (this can be formally proved more thoroughly, but that’s outside our scope).

Think about the even numbers for a moment. 2,4,6, etc. It seems reasonable to think about this set of numbers as, in some way, being “half the size” of the set of all even and odd numbers together. After all, in any given section of the number line, say 1,2,3,4,5, there are fewer even numbers than the total count of all the numbers (two evens vs five total in this 1-5 section of the number line.)

But all you have to do is map the even numbers onto to convince yourself otherwise (or, create a bijection, more formally):

Since we know that is infinite and there’s a one-to-one mapping between and the even numbers, then these two sets are the same size. In this case, the relationship between and the even numbers is - take any number in and multiply it by two to get its mapping in the Evens set. As long as you can create a one-to-one mapping between any set and , you’ve shown the same thing as we’ve shown here - that it is countably infinite. (I suppose it’s called “countable” because it maps to the “counting numbers”, “whole numbers”, “number line numbers”, etc).

Uncountably Infinite…

There’s another, even more interesting type of infinite set, called uncountably infinite. Hold on, because this gets crazy…
Consider the fractions between 0 and 1, represented as decimals:

  • 0.10001
  • 0.55
  • 0.75
  • 0.7556
  • 0.99999
  • …whatever.

This set of numbers is infinite in a very different way and the proof of that is wacky and awesome.

Let’s take these random examples I gave and put them in a table, all made the same length by appending zeroes all the way out to the right forever:

Let’s forget about the in the beginning, since it’s shared by all and not important right now:

It stands to reason that you could keep adding to this table infinitely down and therefore capture every one of the (infinitely-many) decimals between 0 and 1. This looks a bit like our countably infinite proof above. That is, it maps onto the natural numbers. But there’s a brilliant catch that Georg Cantor discovered.

Cantor’s Diagonalization

We’ll take the diagonal of this table and inspect it as a row:

If we take each element of this new number and change it in a routine way, like adding 1 to it (wrapping around back to 0 if it was a 9) it would look like this:

  • increasing the 1st place number by 1:
  • now increasing the 2nd place number by 1:
  • now increasing the 3rd place number by 1:
  • now increasing the 4th place number by 1:
  • now increasing the 5th place number by 1:
  • etc. etc. infinitely out to the right…

We now have the number 26170…

Looking at our table again, this time with “place” numbers along the top:

reminder of diagonal: 26170…

Since this diagonal extends infinitely down the length and breadth of this table, we know this: For any row, we’ve changed the decimal at that row’s “place”. Take row 1, we’ve changed the number in 1st place, so the new number “26170…” definitely can’t be equal to the number in row 1 (since at least the 1st place digit is different!), similarly for row 2 - the 2nd place digit of the new number is necessarily different than whatever is in 2nd place in row 2… and so on and so on down the infinite table. So our new number does not appear in the countably infinite table.

Your objection might be “Well why don’t we just stick this row in the table somewhere? So the size of the table is infinite + 1… I can still be ok with that”. Well, not quite: if you shoehorn in a new row to the table, that row will have some digit at place . The diagonal now will necessarily have a different digit at place - and this row isn’t in the table! This goes on forever! 1

It’s a different kind of infinity - just when we got comfortable with countable infinity, we built uncountable infinity off of its back.

will it blend? 2

Maybe the question this begs is: Is this a real thing, or just a math thing? Sure, I can convince myself that there is an uncountable infinity between 0 and 1, conceptually, but does that relate to the natural, physical world? Obviously, I don’t have the answer to that, as I’ve just barely integrated this information myself… It seems to me that some facts in math-land are more readily observable in the natural world. I’m not sure where the line is between “real in math” and “real in nature”. I think that’s probably one of the most interesting questions of all.

At the very least, math provides a framework to think about the natural world. Ok, say physics tells us the universe is infinite - we can now ask which type of infinity it is. Do we take all the cubic inches of space and map them to the natural numbers and get a one-to-one mapping, making it countably infinite? Is there some clever proof to show its actually uncountably infinite - or worse, another Cantor comes along and shows it’s something else altogether nobody imagined? Fuck!

Anecdote time: I once asked a middle-school math teach how a worm grows from 1” to 2” if there are are infinitely many fractional inches in between. He didn’t provide me with a satisfying answer.

  1. This is a slightly misleading way to think of it. You’re not incrementally “adding rows” to the table. The entire table is infinitely-long to begin with and all this sort of “happens at the same time”. Clearly, the concept is difficult or impossible to picture and I choose to describe it in this somewhat inaccurate way hoping it would be clearer. ↩

  2. Will it blend? - I have no idea why this came to mind when trying to think of a way to ask “does this matter/is it real?” ↩