(Part II of this post can be found here.)
Speaking of diagonal arguments: I ran across the blog of one Matt Baker yesterday, who sketched out probably the easiest proof I've ever seen of the uncountability of the real line. He also included a question in his post, one that I have a strong intuition about the answer, but so far haven't been able to prove I'm right.
(NB: when I say easiest proof I've ever seen, I mean that I sat down at lunch with a colleague who hadn't seen math since her freshman year of calc, and we finished lunch with her pretty much all over that shit.)
Anyway, I thought I'd record that argument in case Baker's blog disappears or (as has happened twice today) I can't figure out search terms to find it again. The next post will discuss his question, the version of an answer I can prove, and what makes the full problem more difficult. I'll try to pitch the level of these posts (well, more this one than the next) at the level of my lunch colleague.
Definition: A set \(X\) of numbers is countable if we can write \[X = \{x_0, x_1, x_2, x_3, \ldots, x_k, \ldots \} \]where \(k\) ranges over all the natural numbers.
When most non-mathematicians think of "infinity", this is the kind of set they have in mind: one can keep on listing out members of this set forever. The part they think is obvious, but is actually really important to point out, is that not only can we keep on listing new members, but we're sure that every member of the set will be listed somewhere along the way.
Example: The set \( \mathbb{N} \) of natural numbers is countable: let \[ x_0 = 0, \qquad x_1 = 1, \qquad \text{ etc.} \]
Example: The set \( \mathbb{Q} \) of rational numbers is countable: \[ \mathbb{Q} = \{ \frac{0}{1}, \frac{1}{1}, -\frac{1}{1}, \frac{2}{1}, - \frac{2}{1}, \frac{1}{2}, -\frac{1}{2}, \frac{3}{1}, -\frac{3}{1}, \frac{1}{3}, - \frac{1}{3}, \frac{4}{1}, -\frac{4}{1}, \frac{4}{3}, -\frac{4}{3}, \frac{3}{4}, -\frac{3}{4}, \ldots \} \](This is how we usually write this, instead of specifying what \(x_k\) is for each \(k\).)
Definition: A set is uncountable if it is infinite, but not countable.
Note that it's not immediately clear that any uncountable sets exist. This is what I need to convince you of.
But before we do any convincing, let's play a game. Here are the rules: There is some set \(T\) of "targets", which are numbers between 0 and 1. (We'll see why they're called targets in a minute.) There are two players, who we'll call Alice and Bob (because those are the traditional names). Alice plays first: she chooses a real number \(a_0\) so that \(0 < a_0 < 1\).
Then Bob plays: he chooses a real number \( b_0 \) so that \( a_0 < b_0 < 1 \).
Then Alice plays again: she chooses \( a_0 < a_1 < b_0 \). Bob responds by choosing \( a_1 < b_1 < b_0 \).
The game goes on for infinitely many turns like this, with Alice choosing a number \( a_k < a_{k+1} < b_k \), and Bob responding by choosing a number \( a_{k+1} < b_{k+1} < b_k \). (When explaining this to my coworker, it was very helpful to have a piece of paper to draw this process on. If I get around to it I might create some graphics to insert into this post, but don't hold your breath.)
Now: for those of you who have taken calculus, you might be able to see why the numbers \( a_k \) have to converge to a limit. If you haven't or don't see why, you can either take my word for it, or take a time out from learning the rules of the game and see if you can figure out why that has to be true.
Is everyone back? Good! We said that the \( a_k \) have to converge to a limit, which we'll call \(a\). Remember that set \(T\) from before? Well, if \(a\) belongs to \(T\), which we write \(a \in T\), then we say that Alice has hit the target, and she wins the game. If \( a \not \in T \), then she missed, and Bob wins the game.
Pretty simple rules, huh? It's too bad the game takes infinitely long to play; or maybe that's part of what makes it fun, because I don't know about you, I never get bored with a game until I've played it all the way through at least once.
Now clearly, the choice of the target set \(T\) makes all the difference in the world. For example, if \(T\) contains every number between 0 and 1, then of course Alice is going to win; if \(T\) is the empty set, then Bob is going to win no matter how he plays.
Test your understanding: Let's say the target set \[T = \{ \frac{1}{4}, \frac{1}{2}, \frac{3}{4} \} \]Do you want to play as Alice or as Bob? (That is, do you want to go first or second?)[1]
Is your understanding tested? Did you check your strategy against the footnote to make sure you agree on who will win this game? Good. We say that the player in question has a winning strategy: if they're careful, they can win the game no matter what their opponent chooses to do.
Test your understanding: Show that if the target set is finite, that is \[ T = \{ x_0, \ldots, x_k \}\]then the same player has a winning strategy as in the last example.
OK, now here's where it gets fun. Instead of \(T\) being a finite set, let's now let \(T\) be a countable set \[T = \{ t_0, t_1, \ldots \}.\] Do you think you want to play as Alice, or Bob, or maybe say "it depends, I need more information"?
Answer: If the target set is countable, Bob has a winning strategy, no matter what specific numbers belong to \(T\).
Why is this? Well, what we have to do is explain Bob's strategy and show that it guarantees that Alice can't win.
First we make an observation: the numbers played by Alice increase every turn, and the numbers played by Bob decrease. What this means is that, if Alice played \(a\) on her most recent turn, and Bob played \(b\) on his, then the final limit of Alice's plays will definitely be bigger than \(a\) but less than \(b\).
So what does this allow Bob to do? Well, in this case, it allows him to check off targets one by one, ensuring that Alice can't hit them.
To be specific: Alice plays first, and plays some number \(a_0\). Bob peeks at \(T\). Specifically, he checks what \(t_0\), the first element of \(T\) is, and
So I hear you saying, wow, it looks like Bob's definitely got the better of this game. He can win basically every time, no matter what the target set looks like.
Except... well, we already saw one case where that wasn't true.
Remember what it was? It was way back when we discussed the rules of the game. We said that if \(T\) was the whole interval \( (0,1) \), then Alice will definitely win.
Wait. Stop. Rewind.
Alice wins if \( T = (0,1) \).
Bob wins if \(T\) is countable.
Whoa. Headrush.
We've just proved that \(T\) is an uncountable set.
[1] You want to play as Bob. Think about what Alice might play on her first turn: whatever number she chooses for \(a_0\), Bob can choose \(b_0 \) just ever so slightly to the right of \(a_0\) so that there are no targets \(t\) such that \(a_0 < t < b_0 \). For example, if Alice played \(a_0 = \frac{24}{100} \), because she's hoping that her sequence can converge to \(\frac{1}{4} \) which is just a little bit greater, then Bob could respond with \( b_0 = \frac{49}{200} \), which is also just a little to the left of \( \frac{1}{4} \), but blocks Alice from getting any closer to that target point. And if Alice can't get close to \( \frac{1}{4} \), then she definitely can't get close to \( \frac{1}{2} \) or \( \frac{3}{4} \).
Speaking of diagonal arguments: I ran across the blog of one Matt Baker yesterday, who sketched out probably the easiest proof I've ever seen of the uncountability of the real line. He also included a question in his post, one that I have a strong intuition about the answer, but so far haven't been able to prove I'm right.
(NB: when I say easiest proof I've ever seen, I mean that I sat down at lunch with a colleague who hadn't seen math since her freshman year of calc, and we finished lunch with her pretty much all over that shit.)
Anyway, I thought I'd record that argument in case Baker's blog disappears or (as has happened twice today) I can't figure out search terms to find it again. The next post will discuss his question, the version of an answer I can prove, and what makes the full problem more difficult. I'll try to pitch the level of these posts (well, more this one than the next) at the level of my lunch colleague.
Definition: A set \(X\) of numbers is countable if we can write \[X = \{x_0, x_1, x_2, x_3, \ldots, x_k, \ldots \} \]where \(k\) ranges over all the natural numbers.
When most non-mathematicians think of "infinity", this is the kind of set they have in mind: one can keep on listing out members of this set forever. The part they think is obvious, but is actually really important to point out, is that not only can we keep on listing new members, but we're sure that every member of the set will be listed somewhere along the way.
Example: The set \( \mathbb{N} \) of natural numbers is countable: let \[ x_0 = 0, \qquad x_1 = 1, \qquad \text{ etc.} \]
Example: The set \( \mathbb{Q} \) of rational numbers is countable: \[ \mathbb{Q} = \{ \frac{0}{1}, \frac{1}{1}, -\frac{1}{1}, \frac{2}{1}, - \frac{2}{1}, \frac{1}{2}, -\frac{1}{2}, \frac{3}{1}, -\frac{3}{1}, \frac{1}{3}, - \frac{1}{3}, \frac{4}{1}, -\frac{4}{1}, \frac{4}{3}, -\frac{4}{3}, \frac{3}{4}, -\frac{3}{4}, \ldots \} \](This is how we usually write this, instead of specifying what \(x_k\) is for each \(k\).)
Definition: A set is uncountable if it is infinite, but not countable.
Note that it's not immediately clear that any uncountable sets exist. This is what I need to convince you of.
But before we do any convincing, let's play a game. Here are the rules: There is some set \(T\) of "targets", which are numbers between 0 and 1. (We'll see why they're called targets in a minute.) There are two players, who we'll call Alice and Bob (because those are the traditional names). Alice plays first: she chooses a real number \(a_0\) so that \(0 < a_0 < 1\).
Then Bob plays: he chooses a real number \( b_0 \) so that \( a_0 < b_0 < 1 \).
Then Alice plays again: she chooses \( a_0 < a_1 < b_0 \). Bob responds by choosing \( a_1 < b_1 < b_0 \).
The game goes on for infinitely many turns like this, with Alice choosing a number \( a_k < a_{k+1} < b_k \), and Bob responding by choosing a number \( a_{k+1} < b_{k+1} < b_k \). (When explaining this to my coworker, it was very helpful to have a piece of paper to draw this process on. If I get around to it I might create some graphics to insert into this post, but don't hold your breath.)
Now: for those of you who have taken calculus, you might be able to see why the numbers \( a_k \) have to converge to a limit. If you haven't or don't see why, you can either take my word for it, or take a time out from learning the rules of the game and see if you can figure out why that has to be true.
Is everyone back? Good! We said that the \( a_k \) have to converge to a limit, which we'll call \(a\). Remember that set \(T\) from before? Well, if \(a\) belongs to \(T\), which we write \(a \in T\), then we say that Alice has hit the target, and she wins the game. If \( a \not \in T \), then she missed, and Bob wins the game.
Pretty simple rules, huh? It's too bad the game takes infinitely long to play; or maybe that's part of what makes it fun, because I don't know about you, I never get bored with a game until I've played it all the way through at least once.
Now clearly, the choice of the target set \(T\) makes all the difference in the world. For example, if \(T\) contains every number between 0 and 1, then of course Alice is going to win; if \(T\) is the empty set, then Bob is going to win no matter how he plays.
Test your understanding: Let's say the target set \[T = \{ \frac{1}{4}, \frac{1}{2}, \frac{3}{4} \} \]Do you want to play as Alice or as Bob? (That is, do you want to go first or second?)[1]
Is your understanding tested? Did you check your strategy against the footnote to make sure you agree on who will win this game? Good. We say that the player in question has a winning strategy: if they're careful, they can win the game no matter what their opponent chooses to do.
Test your understanding: Show that if the target set is finite, that is \[ T = \{ x_0, \ldots, x_k \}\]then the same player has a winning strategy as in the last example.
OK, now here's where it gets fun. Instead of \(T\) being a finite set, let's now let \(T\) be a countable set \[T = \{ t_0, t_1, \ldots \}.\] Do you think you want to play as Alice, or Bob, or maybe say "it depends, I need more information"?
Answer: If the target set is countable, Bob has a winning strategy, no matter what specific numbers belong to \(T\).
Why is this? Well, what we have to do is explain Bob's strategy and show that it guarantees that Alice can't win.
First we make an observation: the numbers played by Alice increase every turn, and the numbers played by Bob decrease. What this means is that, if Alice played \(a\) on her most recent turn, and Bob played \(b\) on his, then the final limit of Alice's plays will definitely be bigger than \(a\) but less than \(b\).
So what does this allow Bob to do? Well, in this case, it allows him to check off targets one by one, ensuring that Alice can't hit them.
To be specific: Alice plays first, and plays some number \(a_0\). Bob peeks at \(T\). Specifically, he checks what \(t_0\), the first element of \(T\) is, and
- if \(0 < t_0 \leq a_0 \), that is, if \(t_0\) is already impossible, then Bob plays a number at random;
- but if \( a_0 < t_0 < 1\), then he has to destroy Alice's chances to hit \(t_0 \), so he plays \(b_0 = t_0\). (Remember: whatever Alice's final limit ends up being, it's got to be strictly less than anything Bob plays.)
- if \( t_{k+1} \leq a_{k+1} \) or \(b_k \leq t_{k+1} \), then this target is already impossible, so Bob plays whatever he feels like;
- but if \( a_{k+1} < t_{k+1} < b_k \), then Bob plays \( b_{k+1} = t_{k+1} \), thus eliminating this target as a possible limit.
So I hear you saying, wow, it looks like Bob's definitely got the better of this game. He can win basically every time, no matter what the target set looks like.
Except... well, we already saw one case where that wasn't true.
Remember what it was? It was way back when we discussed the rules of the game. We said that if \(T\) was the whole interval \( (0,1) \), then Alice will definitely win.
Wait. Stop. Rewind.
Alice wins if \( T = (0,1) \).
Bob wins if \(T\) is countable.
Whoa. Headrush.
We've just proved that \(T\) is an uncountable set.
[1] You want to play as Bob. Think about what Alice might play on her first turn: whatever number she chooses for \(a_0\), Bob can choose \(b_0 \) just ever so slightly to the right of \(a_0\) so that there are no targets \(t\) such that \(a_0 < t < b_0 \). For example, if Alice played \(a_0 = \frac{24}{100} \), because she's hoping that her sequence can converge to \(\frac{1}{4} \) which is just a little bit greater, then Bob could respond with \( b_0 = \frac{49}{200} \), which is also just a little to the left of \( \frac{1}{4} \), but blocks Alice from getting any closer to that target point. And if Alice can't get close to \( \frac{1}{4} \), then she definitely can't get close to \( \frac{1}{2} \) or \( \frac{3}{4} \).
No comments:
Post a Comment