Thread by @Arnaldo_AGITF

I'm coming out of Twitter hibernation to post a microlesson on a confusing but fascinating topic:

What are some different types of infinities, and how do you tell which is which? #math

First things first, let's define a (sort of) intuitive object to help us in our investigation; an infinite binary sequence.

This is just a sequence of 1's and 0's that's infinitely long.

We can then start thinking about different collections, or "sets", of these infinite binary sequences.

For example, we can consider a set of "n"—say, 2 or 3—different infinite binary sequences. As long as "n" is an actual number, then this set is (perhaps obviously) "finite".

Now consider the set of infinite binary sequences that contain a single 1 within them. This set of sequences is infinite, because you have an infinite number of different locations within each sequence to "place" the 1 in.

But what kind of infinity is this?

Well, note the following. If you wanted to list each sequence in this set, you can order them by where the 1 is in the sequence and go for it. You'd never finish listing 'em, but you can conceive an infinite process to do so.

Sets you can do this for are "countably infinite".

For example, the natural numbers (0,1,2,...), the integer numbers (...,-1,0,1,...), and the rational numbers (every # that's a fraction of two integers) are countably infinite.

So, is there any set "bigger" than countable infinity?

The answer is yes! In fact, the set of /all/ infinite binary sequences is so "big" that there's no way to come up with an infinite listing process for it that doesn't miss a sequence.

Let's prove this using a pretty mind-boggling technique called "Cantor's diagonal argument".

Come up with any listing process you want, and start listing the sequences.

Take the 1st symbol of the 1st sequence, switch it (1 to 0 or 0 to 1), and put it at the start of another sequence. Attach the "switched" 2nd number of the 2nd sequence to the other sequence, and so on.

The sequence you make from this switching process can't be in the list you generate because, by construction, it's different from every sequence in the list!

It'll differ from the 1st listed sequence because of its 1st digit, from the 2nd sequence because of the 2nd digit, etc.

As a result, you can always find a sequence you miss when you try to construct a list of all infinite binary sequences.

Unsurprisingly, sets like these—that are so "big" that they cannot even be listed through an infinite listing process—are called "uncountably infinite".

Lastly, notice that I've been writing the word big in quotes. That's because the notion of "big" for things like these isn't really well-defined!

To demonstrate it, consider whether or not the set of all infinite binary sequences with no consecutive 1's in them is uncountable.

One thing we can try is to "re-code" each sequence; every time you see a 10 or a 01, change it to 1*, and when you see a 00, change it to 0*.

This re-coding lets you transform any sequence in the original set into a sequence of 1*'s and 0*'s.

In fact, for /any/ sequence of 1*'s & 0*'s, you can find at least one sequence of 1's & 0's in the original set that "re-codes" into that new, arbitrary sequence!

Therefore, you can make any sequence of 1*'s & 0*'s by "re-coding" sequences from the original set.

As a result, the set of infinite binary sequences with no consecutive 1's contains the set of all infinite binary sequences of 1*'s and 0*'s—and since the latter is uncountable because it can't be listed, the original must be too!

But...

We defined the original set as "smaller" than the set of all infinite binary sequences—we picked specific sequences from it.

But we showed that it's as "big" as the set of all inf. binary sequences—there's at least 1 seq. in the set for every inf. binary seq.

What!?

The problem is, of course, infinity—our intuition for what is "smaller" and "bigger" goes in the toilet whenever we try to handle infinitely large objects.

In fact, with a small caveat, that original set and the set of all infinite binary sequences are exactly the same "size"!

These different notions of infinity aren't just fanciful; in fact, they can help discern when something is chaotic or not. (I'll talk more about this in my upcoming notes on dynamical systems—stay tuned!)

Anyways, that's it for this microlesson. I hope you enjoyed it!