To infinity, and beyond!
Oct. 19th, 2019 02:10 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
shadowscastA little while ago, somebody in my circles posted about how they're taking a class in metaphysics for fun. They mentioned that the concept of different sizes of infinity had come up recently in their class, and that they found the concept really cool but that it had been presented too briefly for them to really understand what was going on with the math (particularly Cantor's diagonalization proof of the uncountability of the reals). So I popped in and said, basically, "I can explain that stuff!" and they said, essentially "Hooray, please do!" and so I did!
I had so much fun writing it up, I figured I'd share it here too for posterity. Maybe there are other people in my circles who are also interested in infinity! (In particular, I just found out that my little brother has started reading this journal, and I know that he's into math and not into fanfic, so let's just say that I'm throwing him a bone.)
First, let's define four kinds of numbers!
The natural numbers are the counting numbers: 1, 2, 3, 4, 5, ...
(A fun famous math quote: "God made the natural numbers; all else is the work of man." - Leopold Kronecker. As a feminist atheist, I prefer not to interpret that quote literally, but on a metaphorical level I really enjoy it!)
The integers include all of the natural numbers, and also 0 and the negative numbers. So the integers are:
... -3, -2, -1, 0, 1, 2, 3, ...
The rational numbers are the numbers which can be expressed as fractions (ie: ratios) where the numerator and denominator are integers. So 3/2 is a rational number, and so is -103/7. All of the natural numbers and integers are also rational numbers, since for instance 5 is the fraction 5/1.
If you express a rational number in decimal form, the decimal part eventually either ends (for instance 1/4 = 0.25, full stop) or starts repeating (for instance 7/6 = 1.1666666... and the 6's just keep on going forever).
The real numbers are all of the numbers on the number line. They include all of the rationals, and also other numbers, called "irrational", which can't be expressed as a fraction of integers. Pi (3.1415...) is a famous irrational number. All of the square roots that aren't perfect squares are also irrational (for instance the square root of 2 is irrational). If you write an irrational number in decimal form, the decimal part goes on forever without ending or repeating.
The natural numbers are a subset of the integers, and the integers are a subset of the rational numbers, and the rational numbers are a subset of the real numbers. (Are the real numbers a subset of something else? Yes! But that doesn't have to do with what we're talking about today.)
Now, there are infinitely many natural numbers, so obviously there are infinitely many integers, rational numbers, and real numbers as well. The question that we're dealing with is: even if they're all infinite, is there some sense in which some of them are more infinite than others?
Here's where we get into cardinality.
Cardinality
The cardinality of a set is the number of elements in that set.
The set {5, 6, 7} has cardinality 3, because there are three elements in it.
The set {Buffy, Willow, Xander} also has cardinality 3.
The set of all natural numbers would have a cardinality of "infinity," because there are infinitely many elements in it, but if we want to start talking about some sets being more infinite than others, we need a new word to describe this. So we call the cardinality of the set of natural numbers "aleph-null" (that's written with the Hebrew letter aleph, and a subscript zero, but I don't know how to do that in html so I'll just say "aleph-null").
So, in some sense, we have just given the name "aleph-null" to the total number of natural numbers.
Now, here's where things get weird: we can prove that the cardinality of the set of integers is also aleph-null. And so is the cardinality of the set of rational numbers! Which is unintuitive, since if you pick any two rational numbers, no matter how close together they are, there are infinitely many additional rational numbers in between them! (Proof: let a and b be rational numbers. (a+b)/2 is between them. You can do that as many times as you want, splitting the differences each time.)
But, according to Cantor's proof, the cardinality of the real numbers is greater than aleph-null.
Before you can be properly surprised by that fact, though, you first have to understand how it is that there are the same number of rational numbers as natural numbers! (In the sense of their sets having the same cardinality.)
Countability
Okay, remember: the cardinality of the set of natural numbers is defined to be aleph-null.
For any other set, we'll say that its cardinality is aleph-null if we can count the elements of that set using the natural numbers. In this case, the other set is called "countable."
The set of integers is countable, therefore its cardinality is aleph-null. Here's the proof: I will show you how to count the integers, using the natural numbers.
First: 0
Second: 1
Third: -1
Fourth: 2
Fifth: -2
Sixth: 3
Seventh: -3
Eighth: 4
Ninth: -4
etc.
So, we can go on like that literally forever. If you think of any particular integer, our count will get to it eventually. Since we'll never run out of natural numbers to count with, we can count the integers. Therefore the integers are countable.
Any set that we can do that with is called "countable," and its cardinality is aleph-null. Any set that we can't do that with is called uncountable, and its cardinality is something bigger (aleph-one or more).
The rational numbers are countable (or we could also say: "countably infinite"). The real numbers are uncountable.
Countability of the Rational Numbers
Now I'm going to prove that the rational numbers are countable—which is perhaps a bit surprising, considering for instance that there are infinitely many rational numbers between 0 and 1.
(This proof is based on Cantor's original work, and I learned it as an undergrad.)
All we need is a systematic way to list all of the rational numbers, making sure we're not going to miss any.
So imagine making a grid. And in the first row, put:
1/1, 1/2, 1/3, 1/4, ... (etc)
In the second row, put:
2/1, 2/2, 2/3, 2/3, ... (etc)
In the third row, put:
3/1, 3/2, 3/2, 3/4, ... (etc)
and so on.
Every rational number will appear somewhere in this grid. (In fact, every rational number will appear more than once, because of equivalent fractions; for example 1/1 is the same number as 2/2. But the important thing is: every rational number will be there somewhere.)
We can use this grid to count the positive rational numbers. We start at the upper left corner and go in a zigzag pattern. Here I'm going to cheat and link you to a picture I found online: Link to picture. While following the zigzag, we can skip any duplicate numbers (they're grey and crossed out in the linked picture).
So we can count the positive rational numbers as follows (following the zigzag):
First: 1
Second: 2
Third: 1/2
Fourth: 1/3
Fifth: 3
Sixth: 4
Seventh: 3/2
Eighth: 2/3
Ninth: 1/4
etc.
And, just as I said for the integers: we can go on like that literally forever. If you think of any particular positive rational number, our count will get to it eventually. Since we'll never run out of natural numbers to count with, we can count the positive rational numbers. Therefore the positive rational numbers are countable.
If we want to prove that the entire set of rational numbers is countable, we can follow the same trick that I did for the integers: stick 0 on at the beginning, and count the negative version of each number right after the positive version. So, using our count of the positive rationals as a guide, we can count all of the rationals as follows:
First: 0
Second: 1
Third: -1
Fourth: 2
Fifth: -2
Sixth: 1/2
Seventh: -1/2
Eighth: 1/3
Ninth: -1/3
Tenth: 3
Eleventh: -3
Twelfth: 4
Thirteenth: -4
Fourteenth: 3/2
Fifteenth: -3/2
etc.
So the rationals are countable. The cardinality of the rational numbers is aleph-null, same as the natural numbers. (Even though there are infinitely many rational numbers just between 0 and 1! In fact, the cardinality of the set of rational numbers between 0 and 1 is also aleph-null. Infinity is so weird!)
Next up: Cantor's proof of the uncountability of the real numbers.
Uncountability of the Reals
So, remember how I made those lists, first-second-third-fourth-etc, and counted the integers and the rational numbers? To prove that the real numbers aren't countable, we need to prove that we can't possibly make a list like that for the real numbers.
One of the ways that mathematicians sometimes prove that something can't be done is by saying "Let's pretend that it can be done!" and then showing that this leads to something impossible; this is called "proof by contradiction."
So we're going to pretend, for the moment, that the real numbers are countable. And actually, to keep things under control, we're just going to work with the real numbers between 0 and 1.
If the real numbers between 0 and 1 are countable, then by definition there is some way to list them:
First: first number
Second: second number
Third: third number
etc.
in a way such that any particular real number between 0 and 1 definitely has a place on the list.
The real numbers between 0 and 1 can all be expressed in decimal form as 0.something, where the "something" is a string of digits, which may or may not terminate or repeat. For purposes of this proof, we'll want those strings of digits to all go on forever, so in the case of a terminating decimal we'll just fill in the end with infinitely many zeros, ex: 1/4 = 0.250000000000...
So, remember, we've just said "let's pretend that the reals are countable," and that means that we can list all of the real numbers between 0 and 1 in some kind of order. To represent the numbers without actually knowing which numbers they are, I'll represent their digits with subscripted letters. So our list is:
First: 0.a1 a2 a3 a4 a5 a6 a7 a8 ...
Second: 0.b1 b2 b3 b4 b5 b6 b7 b8 ...
Third: 0.c1 c2 c3 c4 c5 c6 c7 c8 ...
Fourth: 0.d1 d2 d3 d4 d5 d6 d7 d8 ...
etc.
So every single real number between 0 and 1 should have a place on this list.
Here's where the contradiction comes in: we'll prove that there's a number that can't be found anywhere on this list.
We construct a number (call it p) whose first decimal place is not a1, and whose second decimal place is not b2, and whose third decimal place is not c3, etc.
This number p can't be the first number on the list, since its first decimal place isn't a1; p can't be the second number on the list, since its second decimal place isn't b2; p can't be the third number on the list, since its third decimal place isn't c3; etc.
So p can't be anywhere on the list.
So there is no such thing as a list of all the real numbers between 0 and 1.
So the real numbers are not countable.
End of proof!
More weirdness
It does kind of feel right that there are more real numbers than natural numbers, since the natural numbers are so widely spaced. But whenever you're dealing with infinity and you find yourself thinking, "Okay, this bit makes intuitive sense," be careful—infinity blows our intuition right out of the water! Remember that there are the same number of rational numbers as natural numbers (in the sense that the sets have the same cardinality, aleph-null) and yet there are infinitely many rational numbers between 0 and 1.
But here's another couple of crazy things that are true!
If you look at the set of all numbers between 0 and 1, 0% of them are rational. Even though there are infinitely many rational numbers between 0 and 1! And that's not "nearly 0%" or "rounds down to 0%"; in a precise mathematical sense, exactly 0% of the numbers between 0 and 1 are rational. (Okay, I'm cheating a little with the language here, in that the concept of % isn't exactly well-defined for infinite sets. The proper explanation involves something called Lebesgue measure, which I'm not actually qualified to explain.)
And yet, between any two real numbers, no matter how close together they are, there is a rational number! So weird! (Here's a proof; this one's pretty short.)
So anyway ... that was fun for me! I hope it was fun for you. :-D
Math is so weird and cool!
I had so much fun writing it up, I figured I'd share it here too for posterity. Maybe there are other people in my circles who are also interested in infinity! (In particular, I just found out that my little brother has started reading this journal, and I know that he's into math and not into fanfic, so let's just say that I'm throwing him a bone.)
First, let's define four kinds of numbers!
The natural numbers are the counting numbers: 1, 2, 3, 4, 5, ...
(A fun famous math quote: "God made the natural numbers; all else is the work of man." - Leopold Kronecker. As a feminist atheist, I prefer not to interpret that quote literally, but on a metaphorical level I really enjoy it!)
The integers include all of the natural numbers, and also 0 and the negative numbers. So the integers are:
... -3, -2, -1, 0, 1, 2, 3, ...
The rational numbers are the numbers which can be expressed as fractions (ie: ratios) where the numerator and denominator are integers. So 3/2 is a rational number, and so is -103/7. All of the natural numbers and integers are also rational numbers, since for instance 5 is the fraction 5/1.
If you express a rational number in decimal form, the decimal part eventually either ends (for instance 1/4 = 0.25, full stop) or starts repeating (for instance 7/6 = 1.1666666... and the 6's just keep on going forever).
The real numbers are all of the numbers on the number line. They include all of the rationals, and also other numbers, called "irrational", which can't be expressed as a fraction of integers. Pi (3.1415...) is a famous irrational number. All of the square roots that aren't perfect squares are also irrational (for instance the square root of 2 is irrational). If you write an irrational number in decimal form, the decimal part goes on forever without ending or repeating.
The natural numbers are a subset of the integers, and the integers are a subset of the rational numbers, and the rational numbers are a subset of the real numbers. (Are the real numbers a subset of something else? Yes! But that doesn't have to do with what we're talking about today.)
Now, there are infinitely many natural numbers, so obviously there are infinitely many integers, rational numbers, and real numbers as well. The question that we're dealing with is: even if they're all infinite, is there some sense in which some of them are more infinite than others?
Here's where we get into cardinality.
Cardinality
The cardinality of a set is the number of elements in that set.
The set {5, 6, 7} has cardinality 3, because there are three elements in it.
The set {Buffy, Willow, Xander} also has cardinality 3.
The set of all natural numbers would have a cardinality of "infinity," because there are infinitely many elements in it, but if we want to start talking about some sets being more infinite than others, we need a new word to describe this. So we call the cardinality of the set of natural numbers "aleph-null" (that's written with the Hebrew letter aleph, and a subscript zero, but I don't know how to do that in html so I'll just say "aleph-null").
So, in some sense, we have just given the name "aleph-null" to the total number of natural numbers.
Now, here's where things get weird: we can prove that the cardinality of the set of integers is also aleph-null. And so is the cardinality of the set of rational numbers! Which is unintuitive, since if you pick any two rational numbers, no matter how close together they are, there are infinitely many additional rational numbers in between them! (Proof: let a and b be rational numbers. (a+b)/2 is between them. You can do that as many times as you want, splitting the differences each time.)
But, according to Cantor's proof, the cardinality of the real numbers is greater than aleph-null.
Before you can be properly surprised by that fact, though, you first have to understand how it is that there are the same number of rational numbers as natural numbers! (In the sense of their sets having the same cardinality.)
Countability
Okay, remember: the cardinality of the set of natural numbers is defined to be aleph-null.
For any other set, we'll say that its cardinality is aleph-null if we can count the elements of that set using the natural numbers. In this case, the other set is called "countable."
The set of integers is countable, therefore its cardinality is aleph-null. Here's the proof: I will show you how to count the integers, using the natural numbers.
First: 0
Second: 1
Third: -1
Fourth: 2
Fifth: -2
Sixth: 3
Seventh: -3
Eighth: 4
Ninth: -4
etc.
So, we can go on like that literally forever. If you think of any particular integer, our count will get to it eventually. Since we'll never run out of natural numbers to count with, we can count the integers. Therefore the integers are countable.
Any set that we can do that with is called "countable," and its cardinality is aleph-null. Any set that we can't do that with is called uncountable, and its cardinality is something bigger (aleph-one or more).
The rational numbers are countable (or we could also say: "countably infinite"). The real numbers are uncountable.
Countability of the Rational Numbers
Now I'm going to prove that the rational numbers are countable—which is perhaps a bit surprising, considering for instance that there are infinitely many rational numbers between 0 and 1.
(This proof is based on Cantor's original work, and I learned it as an undergrad.)
All we need is a systematic way to list all of the rational numbers, making sure we're not going to miss any.
So imagine making a grid. And in the first row, put:
1/1, 1/2, 1/3, 1/4, ... (etc)
In the second row, put:
2/1, 2/2, 2/3, 2/3, ... (etc)
In the third row, put:
3/1, 3/2, 3/2, 3/4, ... (etc)
and so on.
Every rational number will appear somewhere in this grid. (In fact, every rational number will appear more than once, because of equivalent fractions; for example 1/1 is the same number as 2/2. But the important thing is: every rational number will be there somewhere.)
We can use this grid to count the positive rational numbers. We start at the upper left corner and go in a zigzag pattern. Here I'm going to cheat and link you to a picture I found online: Link to picture. While following the zigzag, we can skip any duplicate numbers (they're grey and crossed out in the linked picture).
So we can count the positive rational numbers as follows (following the zigzag):
First: 1
Second: 2
Third: 1/2
Fourth: 1/3
Fifth: 3
Sixth: 4
Seventh: 3/2
Eighth: 2/3
Ninth: 1/4
etc.
And, just as I said for the integers: we can go on like that literally forever. If you think of any particular positive rational number, our count will get to it eventually. Since we'll never run out of natural numbers to count with, we can count the positive rational numbers. Therefore the positive rational numbers are countable.
If we want to prove that the entire set of rational numbers is countable, we can follow the same trick that I did for the integers: stick 0 on at the beginning, and count the negative version of each number right after the positive version. So, using our count of the positive rationals as a guide, we can count all of the rationals as follows:
First: 0
Second: 1
Third: -1
Fourth: 2
Fifth: -2
Sixth: 1/2
Seventh: -1/2
Eighth: 1/3
Ninth: -1/3
Tenth: 3
Eleventh: -3
Twelfth: 4
Thirteenth: -4
Fourteenth: 3/2
Fifteenth: -3/2
etc.
So the rationals are countable. The cardinality of the rational numbers is aleph-null, same as the natural numbers. (Even though there are infinitely many rational numbers just between 0 and 1! In fact, the cardinality of the set of rational numbers between 0 and 1 is also aleph-null. Infinity is so weird!)
Next up: Cantor's proof of the uncountability of the real numbers.
Uncountability of the Reals
So, remember how I made those lists, first-second-third-fourth-etc, and counted the integers and the rational numbers? To prove that the real numbers aren't countable, we need to prove that we can't possibly make a list like that for the real numbers.
One of the ways that mathematicians sometimes prove that something can't be done is by saying "Let's pretend that it can be done!" and then showing that this leads to something impossible; this is called "proof by contradiction."
So we're going to pretend, for the moment, that the real numbers are countable. And actually, to keep things under control, we're just going to work with the real numbers between 0 and 1.
If the real numbers between 0 and 1 are countable, then by definition there is some way to list them:
First: first number
Second: second number
Third: third number
etc.
in a way such that any particular real number between 0 and 1 definitely has a place on the list.
The real numbers between 0 and 1 can all be expressed in decimal form as 0.something, where the "something" is a string of digits, which may or may not terminate or repeat. For purposes of this proof, we'll want those strings of digits to all go on forever, so in the case of a terminating decimal we'll just fill in the end with infinitely many zeros, ex: 1/4 = 0.250000000000...
So, remember, we've just said "let's pretend that the reals are countable," and that means that we can list all of the real numbers between 0 and 1 in some kind of order. To represent the numbers without actually knowing which numbers they are, I'll represent their digits with subscripted letters. So our list is:
First: 0.a1 a2 a3 a4 a5 a6 a7 a8 ...
Second: 0.b1 b2 b3 b4 b5 b6 b7 b8 ...
Third: 0.c1 c2 c3 c4 c5 c6 c7 c8 ...
Fourth: 0.d1 d2 d3 d4 d5 d6 d7 d8 ...
etc.
So every single real number between 0 and 1 should have a place on this list.
Here's where the contradiction comes in: we'll prove that there's a number that can't be found anywhere on this list.
We construct a number (call it p) whose first decimal place is not a1, and whose second decimal place is not b2, and whose third decimal place is not c3, etc.
This number p can't be the first number on the list, since its first decimal place isn't a1; p can't be the second number on the list, since its second decimal place isn't b2; p can't be the third number on the list, since its third decimal place isn't c3; etc.
So p can't be anywhere on the list.
So there is no such thing as a list of all the real numbers between 0 and 1.
So the real numbers are not countable.
End of proof!
More weirdness
It does kind of feel right that there are more real numbers than natural numbers, since the natural numbers are so widely spaced. But whenever you're dealing with infinity and you find yourself thinking, "Okay, this bit makes intuitive sense," be careful—infinity blows our intuition right out of the water! Remember that there are the same number of rational numbers as natural numbers (in the sense that the sets have the same cardinality, aleph-null) and yet there are infinitely many rational numbers between 0 and 1.
But here's another couple of crazy things that are true!
If you look at the set of all numbers between 0 and 1, 0% of them are rational. Even though there are infinitely many rational numbers between 0 and 1! And that's not "nearly 0%" or "rounds down to 0%"; in a precise mathematical sense, exactly 0% of the numbers between 0 and 1 are rational. (Okay, I'm cheating a little with the language here, in that the concept of % isn't exactly well-defined for infinite sets. The proper explanation involves something called Lebesgue measure, which I'm not actually qualified to explain.)
And yet, between any two real numbers, no matter how close together they are, there is a rational number! So weird! (Here's a proof; this one's pretty short.)
So anyway ... that was fun for me! I hope it was fun for you. :-D
Math is so weird and cool!
(no subject)
Date: 2019-10-19 08:56 pm (UTC)Having just rewatched Endgame, this immediately reminded me of Scott asking Cap and Nat if they'd ever read anything on particle physics and Nat said "Only to make conversation." Which, if you ask me, should have been the lead off to a fic right there.
I am also now imagining Scott Lang sitting and watching Professor Hulk discuss infinity.
(no subject)
Date: 2019-10-19 09:16 pm (UTC)Haha, yeah. At a party.
(no subject)
Date: 2019-10-20 04:40 pm (UTC)(no subject)
Date: 2019-10-20 04:47 pm (UTC)(no subject)
Date: 2019-10-21 12:19 am (UTC)Thank you. Thank you. Thank you so much.
Would you mind if I post a new entry on my journal linking to this entry?
(no subject)
Date: 2019-10-21 03:10 am (UTC)Would you mind if I post a new entry on my journal linking to this entry?
Not at all.