1516: "Win by Induction"
Moderators: Moderators General, Prelates, Magistrates
 Alpocalypse
 Posts: 52
 Joined: Wed Jul 29, 2009 11:35 am UTC
 Location: Blighty
 Contact:
1516: "Win by Induction"
http://xkcd.com/1516/
Title Text:
"This would be bad enough, but every 30th or 40th Pokéball has TWO of them inside."
Ali
"If I were creating a world I wouldn't mess around with butterflies and daffodiles. I'd have started with lasers, eight o'clock, day one!"
[BOOM!]
"...sorry..."
"If I were creating a world I wouldn't mess around with butterflies and daffodiles. I'd have started with lasers, eight o'clock, day one!"
[BOOM!]
"...sorry..."
Re: 1516: "Win by Induction"
Beat me by a second!
Electromagnetic induction jokes anyone?
Electromagnetic induction jokes anyone?
 rhomboidal
 Posts: 801
 Joined: Wed Jun 15, 2011 5:25 pm UTC
 Contact:
Re: 1516: "Win by Induction"
First Tribbles, then Gremlins, now Pikachu. We're doomed by cuteness.
 Envelope Generator
 Posts: 582
 Joined: Sat Mar 03, 2012 8:07 am UTC
 Location: pareidolia
Re: 1516: "Win by Induction"
Explainxkcd, I choose you.
I'm going to step off the LEM now... here we are, Pismo Beach and all the clams we can eat
eSOANEM wrote:If Fonzie's on the order of 100 zeptokelvin, I think he has bigger problems than difracting through doors.
Re: 1516: "Win by Induction"
Kozmo wrote:Beat me by a second!
Electromagnetic induction jokes anyone?
Thanks!
Infinite pikachus go to a bar. They don't get served because they're underage. End of joke.

 Posts: 45
 Joined: Sat Sep 28, 2013 7:53 am UTC
Re: 1516: "Win by Induction"
So far the only thing about this I understand is that the explainxkcd is wrong, because if occasionally you get two pikachus instead of one, they're still countably infinite.
Re: 1516: "Win by Induction"
This is one of those rare examples where you can see that Randall actually can't draw.
 Eternal Density
 Posts: 5590
 Joined: Thu Oct 02, 2008 12:37 am UTC
 Contact:
Re: 1516: "Win by Induction"
I have no idea what this comic is trying to say.
I'm not into pokémolps.
*reads explainxkcd*
Ok.
Internet osmosis (and smash bros, a very old version) gave me the idea that pokeballs were bigger than that.
I'm not into pokémolps.
*reads explainxkcd*
Ok.
Internet osmosis (and smash bros, a very old version) gave me the idea that pokeballs were bigger than that.
Play the game of Time! castle.chirpingmustard.com Hotdog Vending Supplier But what is this?
In the Marvel vs. DC filmmaking war, we're all winners.
In the Marvel vs. DC filmmaking war, we're all winners.
 Copper Bezel
 Posts: 2426
 Joined: Wed Oct 12, 2011 6:35 am UTC
 Location: Web exclusive!
Re: 1516: "Win by Induction"
1015 cm, but the Pikachu themselves are too big (closer to the Smash Brothers scale, actually.)
So much depends upon a red wheel barrow (>= XXII) but it is not going to be installed.
she / her / her
she / her / her
Re: 1516: "Win by Induction"
It always seemed like to me that Ash's Pikachu's size was somewhat variable....
hell considering that they all fit down into the balls, all pokemon's sizes would be malleable....
hell considering that they all fit down into the balls, all pokemon's sizes would be malleable....
 Neil_Boekend
 Posts: 3220
 Joined: Fri Mar 01, 2013 6:35 am UTC
 Location: Yes.
Re: 1516: "Win by Induction"
Maybe pokeballs are bigger on the inside.
Mikeski wrote:A "What If" update is never late. Nor is it early. It is posted precisely when it should be.
patzer's signature wrote:flicky1991 wrote:I'm being quoted too much!
he/him/his
Re: 1516: "Win by Induction"
fluffysheap wrote:So far the only thing about this I understand is that the explainxkcd is wrong, because if occasionally you get two pikachus instead of one, they're still countably infinite.
It doesn't say they're not countably infinite (at the time of this posting). It just says that the growth is exponential instead of linear.
 Copper Bezel
 Posts: 2426
 Joined: Wed Oct 12, 2011 6:35 am UTC
 Location: Web exclusive!
Re: 1516: "Win by Induction"
Ostensibly, they're not stored physically in any case, but as data. (Not in a scientifically parsable sense, but in the fantasy sense of Tron and things.)
So much depends upon a red wheel barrow (>= XXII) but it is not going to be installed.
she / her / her
she / her / her
 alvinhochun
 Posts: 54
 Joined: Wed Nov 14, 2012 3:07 pm UTC
Re: 1516: "Win by Induction"
explainxkcd wrote:Pikachu is a type of Pokémon from the cartoon series Pokémon.
Pokémon is also a game. In fact the anime is there only to promote the game.
/facepalm
Re: 1516: "Win by Induction"
So, what, the idea is that each Pikachu has a Pokéball containing a Pikachu? That doesn't seem to make much sense...
If you really wanted to do some kind of Pokémon proof by induction, maybe you could work out where Cubone's skull comes from.
For any given Cubone, it's wearing the skull of its dead mother. This particular Cubone certainly is. So there must have been infinite Cubones if we try to trace the family tree backwards...
(Not to mention a single Marowak can have hundreds of baby Cubones from eggs, all wearing its skull, without dying...)
If you really wanted to do some kind of Pokémon proof by induction, maybe you could work out where Cubone's skull comes from.
For any given Cubone, it's wearing the skull of its dead mother. This particular Cubone certainly is. So there must have been infinite Cubones if we try to trace the family tree backwards...
(Not to mention a single Marowak can have hundreds of baby Cubones from eggs, all wearing its skull, without dying...)
 alvinhochun
 Posts: 54
 Joined: Wed Nov 14, 2012 3:07 pm UTC
Re: 1516: "Win by Induction"
Fudge it, I'm done with this strip, I'm just going to consider it as broken. Both the visual (seriously, that drawing) and the explanation.
Re: 1516: "Win by Induction"
Win by Induction:
If each Pikachu summons one (or more) more Pikachu, then eventually they will produce enough static electricity to produce a large enough lightning strike to defeat any opponent.
If each Pikachu summons one (or more) more Pikachu, then eventually they will produce enough static electricity to produce a large enough lightning strike to defeat any opponent.

 Posts: 53
 Joined: Fri Jan 01, 2010 11:03 pm UTC
Re: 1516: "Win by Induction"
Eternal Density wrote:I have no idea what this comic is trying to say.
I'm not into pokémolps.
*reads explainxkcd*
Ok.
Me too. The first time ever I have to resort to explainxkcd, and it's not about maths or physics or gastronomy, it's ... pokémon. The analogy to mathematical proof by induction that there's an infinite number of pikachus, each creating the next, yes; all the other implied stuff about throwing balls, no. Tsk.
 Jackpot777
 Posts: 328
 Joined: Wed Sep 14, 2011 1:19 pm UTC
Re: 1516: "Win by Induction"
Neil_Boekend wrote:Maybe pokeballs are bigger on the inside.
Well THAT explains this scene...
Re: 1516: "Win by Induction"
Jackpot777 wrote:Neil_Boekend wrote:Maybe pokeballs are bigger on the inside.
Well THAT explains this scene...
That one's just smaller on the outside.
Re: 1516: "Win by Induction"
Flumble wrote:Jackpot777 wrote:Neil_Boekend wrote:Maybe pokeballs are bigger on the inside.
Well THAT explains this scene...
>snip<
That one's just smaller on the outside.
My god! It's full of Daleks!
Re: 1516: "Win by Induction"
Kozmo wrote:Beat me by a second!
...By breaking the rules and posting before he or she bothered to think of anything to say.
ObTopic: I too am "not really into Pokémon." A bit odd that Randall now is. Seems more like the kind of thing a teenager would grow out of, than an adult grow into.
Re: 1516: "Win by Induction"
At first I thought I didn't get this because I don't know much about Pokemon.
Now I know I didn't get it because Randall doesn't know much about Pokemon.
Now I know I didn't get it because Randall doesn't know much about Pokemon.
 Quizatzhaderac
 Posts: 1824
 Joined: Sun Oct 19, 2008 5:28 pm UTC
 Location: Space Florida
Re: 1516: "Win by Induction"
Don't pokemon have to wait a turn after summoning before they can act?
One the first split, add "one" to one pikachu's set but not the other.
One each second split add "two" to one pikachu's set but not the other.
Repeat once for each of the natural numbers. The terminal pikachai each have one of all of the possible sets of natural numbers.
Start the first pikachu with an empty set.fluffysheap wrote:So far the only thing about this I understand is that the explainxkcd is wrong, because if occasionally you get two pikachus instead of one, they're still countably infinite.
One the first split, add "one" to one pikachu's set but not the other.
One each second split add "two" to one pikachu's set but not the other.
Repeat once for each of the natural numbers. The terminal pikachai each have one of all of the possible sets of natural numbers.
The thing about recursion problems is that they tend to contain other recursion problems.
Re: 1516: "Win by Induction"
I don't think the set of pikachus can be infinite. While Pikachu (the individual character) can become a trainer and capture pokemon, the pikachu (species of pokemon) is not inherently recursive (doesn't include the pokeball with another pikachu). That means the set of pikachus had to have been sequentially captured with each step taking a finite amount of time and therefore could not be infinite without requiring infinite time to build the set.
Re: 1516: "Win by Induction"
In that case they can still produce the Win by Induction if beforehand they've prepared sufficiently many pikachim that once all are summoned they are guaranteed to overwhelm and defeat any opponent.

 Posts: 12
 Joined: Thu Jan 03, 2013 7:58 am UTC
Re: 1516: "Win by Induction"
slinches wrote:While Pikachu (the individual character) can become a trainer and capture pokemon…
[citation needed]
Re: 1516: "Win by Induction"
I just thought I remembered seeing some game that had Pikachu as a playable character, but that means almost nothing. I'm not really into pokemon.
Re: 1516: "Win by Induction"
Thank you. Someone who gets the horror of infinite binary trees and their leafcount.Quizatzhaderac wrote:Don't pokemon have to wait a turn after summoning before they can act?Start the first pikachu with an empty set.fluffysheap wrote:So far the only thing about this I understand is that the explainxkcd is wrong, because if occasionally you get two pikachus instead of one, they're still countably infinite.
One the first split, add "one" to one pikachu's set but not the other.
One each second split add "two" to one pikachu's set but not the other.
Repeat once for each of the natural numbers. The terminal pikachai each have one of all of the possible sets of natural numbers.
Sorry, I know R allows all kinds of neat tricks which physicists need like air to breathe (and adding i it only gets better), but I still get a bit twitchy when I see a set whose members are, save for a select few, not just practically but fundamentally undescribable.
Similarly, topology is lovely, but why is Choice a necessary part of just about every interesting proof?
Re: 1516: "Win by Induction"
Fluffysheap is right though, aren't they? You can label each pikachu with a pair of naturals (which generation and how many splits), and the cardinality of the set of pairs of naturals is the same as the cardinality of the naturals because you can map each pair (x,y) to 2^{x}3^{y}. It's the same reason that the rationals are countable.
xtifr wrote:... and orthogon merely sounds undecided.
 Copper Bezel
 Posts: 2426
 Joined: Wed Oct 12, 2011 6:35 am UTC
 Location: Web exclusive!
Re: 1516: "Win by Induction"
Zylon wrote:At first I thought I didn't get this because I don't know much about Pokemon.
Now I know I didn't get it because Randall doesn't know much about Pokemon.
Yep. It's not something I expect to say about an xkcd strip, but this one's definitely an outside joke. 1336, "Transformers," was kinda that, too. And also with singularly bad art. I don't know whether these are things he really doesn't have much familiarity with, or things he's trying not to indulge the injoke with for various reasons, but I think Randall needs to stay away from the irrelevant kid toy franchise property jokes, because they seem to be not funny no matter how much or how little you know about the franchises involved.
So much depends upon a red wheel barrow (>= XXII) but it is not going to be installed.
she / her / her
she / her / her
Re: 1516: "Win by Induction"
No, because the generation and number of splits doesn't give you the order in which you took lefts and rights.orthogon wrote:Fluffysheap is right though, aren't they? You can label each pikachu with a pair of naturals (which generation and how many splits), and the cardinality of the set of pairs of naturals is the same as the cardinality of the naturals because you can map each pair (x,y) to 2^{x}3^{y}. It's the same reason that the rationals are countable.
Since each pika from a split gives rise to a sequence of pika's eventually resulting in another split, and the length of this sequence(if always finite) has no effect on cardinality, we can simplify by saying each pika causes a split(and so each pika except the root is the direct result of a split).
How many pika does this yield? Well, at least one for each unique path through the tree(I suspect this might take Choice, but it's easily seen from the properties of a tree). How many paths are there? Each path is effectively equivalent to a sequence of "left" and "right" instructions, one for each split. Considering only the infinite paths, we can map them effectively to infinite sequences of 1's and 0's. By putting these sequences behind a decimal point, we easily map them to the binary notations for all real numbers between 0 and 1.
Refer to Cantor's diagonal argument to see why this means there will be more pika than natural numbers(actually, diagonal already is possible once we have "all possible sequences of left and right instructions", but the canonical form proves the real numbers are not countable).
Re: 1516: "Win by Induction"
Garnasha wrote:How many pika does this yield? Well, at least one for each unique path through the tree(I suspect this might take Choice, but it's easily seen from the properties of a tree). How many paths are there? Each path is effectively equivalent to a sequence of "left" and "right" instructions, one for each split. Considering only the infinite paths
Stop right there!
By the time you have infinite paths to consider, you've already completed the induction an infinite number of steps previously.
The dyadic rationals (those numbers whose binary representation terminates) between 0 and 1, a subset of the rationals, can also be generated as a binary tree, and you can use the same argument of looking only at the infinite ones to "prove" that the rationals are uncountable.
For that matter, you can "prove" that the counting numbers are uncountable by pretty much the same approach  take all the infinite ones, reverse their representations to turn them into infinite decimals, and diagonalise.
The problem is that the induction process only applies to sequences that run for a countable number of steps  so every Pikachu that's generated is generated after only a finite number of steps, so only has a finite number of predecessors. There are no infinite paths to consider, just like there are no infinite counting numbers.

 Posts: 409
 Joined: Sun Nov 22, 2009 10:23 pm UTC
Re: 1516: "Win by Induction"
Reminds me of a bug I found when playing "Baldur's Gate" on linux with Cedega. (That's what it was called then, so many years ago.) I used a cheat to create several bags of holding, then added items to one. When I opened the next bag, the items I stored in the first bag were already in the second bag. Removing them from one bag removed the items from all bags. Maybe that is how the multiple pikachus were created.
I am Lord Titanius Englesmith, Fancyman of Cornwood.
See 1 Kings 7:23 for pi.
If you put a prune in a juicer, what would you get?
See 1 Kings 7:23 for pi.
If you put a prune in a juicer, what would you get?
 Copper Bezel
 Posts: 2426
 Joined: Wed Oct 12, 2011 6:35 am UTC
 Location: Web exclusive!
Re: 1516: "Win by Induction"
Only awesome if you could put the one bag in the other as an item.
So much depends upon a red wheel barrow (>= XXII) but it is not going to be installed.
she / her / her
she / her / her
Re: 1516: "Win by Induction"
I'm pretty sure that the content of a pokeball has to be well founded.
But for the record, a pokemon can hold pokeballs which contain other pokemon (see the episode in the rse time period AG010: Said a Mouthful!") where someone has a Pelliper which hides a bunch of pokeballs in its beak, and the pokemon inside of those (somehow) are able to use their attacks from inside the beak, such that it appears that the peliper knows attacks it should not be able to know. Also see the first pokemon movie in which Mewtwo uses clones of pokemon.) and in some instances can speak (see the tv show's meowth character, and the legendary pokemon in most of the movies). Also, a pokeball can contain another pokeball, which contains a pokemon (see again the first movie).
So it seems likely that hypothetically a pikachu that can speak could catch a pikachu that can speak which has caught a pikachu that can speak,
But I doubt that there could be a not well founded collection like that.
But for the record, a pokemon can hold pokeballs which contain other pokemon (see the episode in the rse time period AG010: Said a Mouthful!") where someone has a Pelliper which hides a bunch of pokeballs in its beak, and the pokemon inside of those (somehow) are able to use their attacks from inside the beak, such that it appears that the peliper knows attacks it should not be able to know. Also see the first pokemon movie in which Mewtwo uses clones of pokemon.) and in some instances can speak (see the tv show's meowth character, and the legendary pokemon in most of the movies). Also, a pokeball can contain another pokeball, which contains a pokemon (see again the first movie).
So it seems likely that hypothetically a pikachu that can speak could catch a pikachu that can speak which has caught a pikachu that can speak,
But I doubt that there could be a not well founded collection like that.
I found my old forum signature to be awkward, so I'm changing it to this until I pick a better one.
Re: 1516: "Win by Induction"
After any finite amount of time, the amount of pika is going to be finite. After a countable infinity of iterations (which would take infinite time, admittedly), we can do the map the other way around, if that makes it more obvious: for any x in (0,1), take its binary expansion, and iterate over the digits, interpreting a 0 as an instruction to go to the left child of the pika you're at, and a 1 as an instruction to go to the right child of the pika you're at. Clearly, at every pika, those children exist, since for any n in N, the nth pika has two children. So this maps (0,1) onto infinite walks through your tree, injectively (since if two elements of (0,1) differ, then there is a finite n such that they differ in the nth digit, and the path they describe diverges there (or before, since we didn't specify it had to be the first n)). Therefore, (0,1) has cardinality at most equal to the amount of paths possible through the tree, therefore there's an uncountable amount of walks possible. Of course, to reach the uncountable pika implied by the existence of those walks, you need to step through a countable infinity of pika. This corresponds to the idea that for most real numbers, you need to write a countably infinite amount of data to describe them.rmsgrey wrote:Garnasha wrote:How many pika does this yield? Well, at least one for each unique path through the tree(I suspect this might take Choice, but it's easily seen from the properties of a tree). How many paths are there? Each path is effectively equivalent to a sequence of "left" and "right" instructions, one for each split. Considering only the infinite paths
Stop right there!
By the time you have infinite paths to consider, you've already completed the induction an infinite number of steps previously.
The dyadic rationals (those numbers whose binary representation terminates) between 0 and 1, a subset of the rationals, can also be generated as a binary tree, and you can use the same argument of looking only at the infinite ones to "prove" that the rationals are uncountable.
For that matter, you can "prove" that the counting numbers are uncountable by pretty much the same approach  take all the infinite ones, reverse their representations to turn them into infinite decimals, and diagonalise.
The problem is that the induction process only applies to sequences that run for a countable number of steps  so every Pikachu that's generated is generated after only a finite number of steps, so only has a finite number of predecessors. There are no infinite paths to consider, just like there are no infinite counting numbers.
This does not clash with the countability of dyadics, by the way: most paths do not correspond to a dyadic number (since they keep going right every so often), and while the dyadics do injectively map onto the paths, that means there are at most as many dyadics as there are paths, but that's fine: countable infinity is at most uncountable sounds stupid but holds true.
It also doesn't clash with the natural numbers: the normal natural numbers are indeed all finite (but iirc, it turns out to be impossible to forbid them being infinite using first order logic, which gives rises to abnormal natural numbers, and nonstandard analysis). Again, not every path can be described by a natural number, but the natural numbers can be mapped injectively into the pikatree.
Of course, there's still the question "do we allow an infinite amount of iterations", but if we don't, we don't even have an infinity of pikachu: we have either a finite amount, or an uncountable infinity, but if they split, there's never going to be a countably infinite amount.
Ps. Did I mention how headacheinducing uncountable infinities are? This is why.
Re: 1516: "Win by Induction"
Even though I normally lurk, this was bothering me enough that I made an account. There can only be at most a countable number of pikachu in this scenario: at any finite step there are finitely many pikachu, and the collection of all the pikachu after a countable number of steps is the union of all these finite sets. The countable union of finite sets is at most countable, ergo, the number of pikachu is at most countable.
To be more explicit, we can enumerate the pikachu. I'll simplify and suppose the the number of pikachu doubles at each step, rather than every 3040 steps. We can then enumerate thusly:
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ...
In the scenario described in the comic it's more like
1
2
3 ...
38
39
40 41
42 43 ...
120 121 122 123 ...
Still, I hope this is convincing.
The fallacy here is that no pikachu is ever assigned an infinite subset of the natural numbers. Indeed, the set of all finite subsets of the natural numbers is countably infinite.
Each pikachu is uniquely descibed by a finite path through the tree, and there are only countably many such paths. Someone else on this thread brought up dyadic rationals. With the correspondence you describe, finite paths are the dyadic rationals (countable), whereas infinite paths are the reals (uncountable).
To be more explicit, we can enumerate the pikachu. I'll simplify and suppose the the number of pikachu doubles at each step, rather than every 3040 steps. We can then enumerate thusly:
1
2 3
4 5 6 7
8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ...
In the scenario described in the comic it's more like
1
2
3 ...
38
39
40 41
42 43 ...
120 121 122 123 ...
Still, I hope this is convincing.
Quizatzhaderac wrote:Don't pokemon have to wait a turn after summoning before they can act?Start the first pikachu with an empty set.fluffysheap wrote:So far the only thing about this I understand is that the explainxkcd is wrong, because if occasionally you get two pikachus instead of one, they're still countably infinite.
One the first split, add "one" to one pikachu's set but not the other.
One each second split add "two" to one pikachu's set but not the other.
Repeat once for each of the natural numbers. The terminal pikachai each have one of all of the possible sets of natural numbers.
The fallacy here is that no pikachu is ever assigned an infinite subset of the natural numbers. Indeed, the set of all finite subsets of the natural numbers is countably infinite.
Garnasha wrote:No, because the generation and number of splits doesn't give you the order in which you took lefts and rights.orthogon wrote:Fluffysheap is right though, aren't they? You can label each pikachu with a pair of naturals (which generation and how many splits), and the cardinality of the set of pairs of naturals is the same as the cardinality of the naturals because you can map each pair (x,y) to 2^{x}3^{y}. It's the same reason that the rationals are countable.
Since each pika from a split gives rise to a sequence of pika's eventually resulting in another split, and the length of this sequence(if always finite) has no effect on cardinality, we can simplify by saying each pika causes a split(and so each pika except the root is the direct result of a split).
How many pika does this yield? Well, at least one for each unique path through the tree(I suspect this might take Choice, but it's easily seen from the properties of a tree). How many paths are there? Each path is effectively equivalent to a sequence of "left" and "right" instructions, one for each split. Considering only the infinite paths, we can map them effectively to infinite sequences of 1's and 0's. By putting these sequences behind a decimal point, we easily map them to the binary notations for all real numbers between 0 and 1.
Refer to Cantor's diagonal argument to see why this means there will be more pika than natural numbers(actually, diagonal already is possible once we have "all possible sequences of left and right instructions", but the canonical form proves the real numbers are not countable).
Each pikachu is uniquely descibed by a finite path through the tree, and there are only countably many such paths. Someone else on this thread brought up dyadic rationals. With the correspondence you describe, finite paths are the dyadic rationals (countable), whereas infinite paths are the reals (uncountable).
Re: 1516: "Win by Induction"
Garnasha wrote:After any finite amount of time, the amount of pika is going to be finite. After a countable infinity of iterations (which would take infinite time, admittedly), we can do the map the other way around, if that makes it more obvious: for any x in (0,1), take its binary expansion, and iterate over the digits, interpreting a 0 as an instruction to go to the left child of the pika you're at, and a 1 as an instruction to go to the right child of the pika you're at. Clearly, at every pika, those children exist, since for any n in N, the nth pika has two children. So this maps (0,1) onto infinite walks through your tree, injectively (since if two elements of (0,1) differ, then there is a finite n such that they differ in the nth digit, and the path they describe diverges there (or before, since we didn't specify it had to be the first n)). Therefore, (0,1) has cardinality at most equal to the amount of paths possible through the tree, therefore there's an uncountable amount of walks possible. Of course, to reach the uncountable pika implied by the existence of those walks, you need to step through a countable infinity of pika. This corresponds to the idea that for most real numbers, you need to write a countably infinite amount of data to describe them.rmsgrey wrote:Garnasha wrote:How many pika does this yield? Well, at least one for each unique path through the tree(I suspect this might take Choice, but it's easily seen from the properties of a tree). How many paths are there? Each path is effectively equivalent to a sequence of "left" and "right" instructions, one for each split. Considering only the infinite paths
Stop right there!
By the time you have infinite paths to consider, you've already completed the induction an infinite number of steps previously.
The dyadic rationals (those numbers whose binary representation terminates) between 0 and 1, a subset of the rationals, can also be generated as a binary tree, and you can use the same argument of looking only at the infinite ones to "prove" that the rationals are uncountable.
For that matter, you can "prove" that the counting numbers are uncountable by pretty much the same approach  take all the infinite ones, reverse their representations to turn them into infinite decimals, and diagonalise.
The problem is that the induction process only applies to sequences that run for a countable number of steps  so every Pikachu that's generated is generated after only a finite number of steps, so only has a finite number of predecessors. There are no infinite paths to consider, just like there are no infinite counting numbers.
This does not clash with the countability of dyadics, by the way: most paths do not correspond to a dyadic number (since they keep going right every so often), and while the dyadics do injectively map onto the paths, that means there are at most as many dyadics as there are paths, but that's fine: countable infinity is at most uncountable sounds stupid but holds true.
It also doesn't clash with the natural numbers: the normal natural numbers are indeed all finite (but iirc, it turns out to be impossible to forbid them being infinite using first order logic, which gives rises to abnormal natural numbers, and nonstandard analysis). Again, not every path can be described by a natural number, but the natural numbers can be mapped injectively into the pikatree.
Of course, there's still the question "do we allow an infinite amount of iterations", but if we don't, we don't even have an infinity of pikachu: we have either a finite amount, or an uncountable infinity, but if they split, there's never going to be a countably infinite amount.
Ps. Did I mention how headacheinducing uncountable infinities are? This is why.
The number of pikas remains countably infinite. You are correct that the number of infinite paths through the tree is uncountably infinite, but none of those paths describes an actual Pikachu. The actual pikachus are described by those sequences of 0's and 1's which terminate at some point (although there is a Pikachu corresponding to sequences of arbitrary length). I believe that what you are counting is somehow related to the power set of the pikachus (each one of your paths does correspond to a member of the power set if you think of it as the set containing each Pikachu that you touch in such a path).
Another way to look at it is that there are a finite number of pika's in each generation (at most 2^N where N is the generation number), and there are a countably infinite number of generations. The total number of Pikachu's is given by the union of the generations, and any countable union of finite sets is countable (this might require the axiom of choice, but I think it can be done without it as each set is finite). The same result would be true if the number in each generation was countable and not necessarily finite (but that result would require AC).
Re: 1516: "Win by Induction"
Errg. But it IS uncountable! If it isn't than, neither are the reals. Are you saying that the reals are actually countable all of the sudden? And just because you can count the finite number of pikachu (no, not pika chi autorcorrect) after a finite number of generations doesn't mean the number after countably infinite generations will be countable as well. For example, the number of reals in [0,1) is uncountable, correct? Let's use binary representation to list all those whose representations terminate after one digit, then in the next line all those terminating after two digits, etc.
0.0, 0.1
0.00, 0.01, 0.10, 0.11
0.000, 0.001, 0.010, 0.011, 0.100, 0.101, 0.110, 0.111
...
So, even with some redundancy, this process enumerates through the reals in [0,1) after a countably infinite number of iterations (since any number has at most countably infinite digits, or else the naturals would not be countable). Note that for a finite number of iterations, the number of elements in this list is finite.
Now to show that this list of the reals can be exhausted by some subset of the pikachu. If it always takes only a finite number of steps to get to a split, then there must be a countably infinite number of splits after a countably infinite number of steps no matter which chain pika you follow. Just let 0 be the choice to follow one pikachu and 1 be the choice to follow another pikachu after a split. Then every number in [0,1) can be mapped to a distinct pikachu by simply choosing one type of pikachu if the next digit is a zero and another type if the next digit is a one. Now, saying that the number pika is countable is equivalent to saying that the numbers in [0,1) are uncountable. You agree that the reals in [0,1) are uncountable, yes? If not, we've got a different problem altogether.
0.0, 0.1
0.00, 0.01, 0.10, 0.11
0.000, 0.001, 0.010, 0.011, 0.100, 0.101, 0.110, 0.111
...
So, even with some redundancy, this process enumerates through the reals in [0,1) after a countably infinite number of iterations (since any number has at most countably infinite digits, or else the naturals would not be countable). Note that for a finite number of iterations, the number of elements in this list is finite.
Now to show that this list of the reals can be exhausted by some subset of the pikachu. If it always takes only a finite number of steps to get to a split, then there must be a countably infinite number of splits after a countably infinite number of steps no matter which chain pika you follow. Just let 0 be the choice to follow one pikachu and 1 be the choice to follow another pikachu after a split. Then every number in [0,1) can be mapped to a distinct pikachu by simply choosing one type of pikachu if the next digit is a zero and another type if the next digit is a one. Now, saying that the number pika is countable is equivalent to saying that the numbers in [0,1) are uncountable. You agree that the reals in [0,1) are uncountable, yes? If not, we've got a different problem altogether.
Return to “Individual XKCD Comic Threads”
Who is online
Users browsing this forum: Google [Bot], mscha and 89 guests