1516: "Win by Induction"

This forum is for the individual discussion thread that goes with each new comic.

Moderators: Moderators General, Prelates, Magistrates

User avatar
Al-pocalypse
Posts: 52
Joined: Wed Jul 29, 2009 11:35 am UTC
Location: Blighty
Contact:

1516: "Win by Induction"

Postby Al-pocalypse » Fri Apr 24, 2015 7:58 am UTC

Image
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..."

User avatar
Kozmo
Posts: 23
Joined: Mon Mar 09, 2015 8:07 pm UTC
Contact:

Re: 1516: "Win by Induction"

Postby Kozmo » Fri Apr 24, 2015 8:00 am UTC

Beat me by a second! :)

Electromagnetic induction jokes anyone?

User avatar
rhomboidal
Posts: 801
Joined: Wed Jun 15, 2011 5:25 pm UTC
Contact:

Re: 1516: "Win by Induction"

Postby rhomboidal » Fri Apr 24, 2015 8:31 am UTC

First Tribbles, then Gremlins, now Pikachu. We're doomed by cuteness.

User avatar
Envelope Generator
Posts: 582
Joined: Sat Mar 03, 2012 8:07 am UTC
Location: pareidolia

Re: 1516: "Win by Induction"

Postby Envelope Generator » Fri Apr 24, 2015 8:57 am UTC

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.

User avatar
Flumble
Yes Man
Posts: 2264
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: 1516: "Win by Induction"

Postby Flumble » Fri Apr 24, 2015 9:01 am UTC

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.

fluffysheap
Posts: 45
Joined: Sat Sep 28, 2013 7:53 am UTC

Re: 1516: "Win by Induction"

Postby fluffysheap » Fri Apr 24, 2015 9:03 am UTC

Image

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.

User avatar
NeatNit
Posts: 44
Joined: Tue Apr 03, 2012 9:10 pm UTC

Re: 1516: "Win by Induction"

Postby NeatNit » Fri Apr 24, 2015 9:56 am UTC

This is one of those rare examples where you can see that Randall actually can't draw.

User avatar
Eternal Density
Posts: 5590
Joined: Thu Oct 02, 2008 12:37 am UTC
Contact:

Re: 1516: "Win by Induction"

Postby Eternal Density » Fri Apr 24, 2015 10:27 am UTC

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.
Play the game of Time! castle.chirpingmustard.com Hotdog Vending Supplier But what is this?
In the Marvel vs. DC film-making war, we're all winners.

User avatar
Copper Bezel
Posts: 2426
Joined: Wed Oct 12, 2011 6:35 am UTC
Location: Web exclusive!

Re: 1516: "Win by Induction"

Postby Copper Bezel » Fri Apr 24, 2015 10:54 am UTC

10-15 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

Cygnwulf
Posts: 19
Joined: Fri Jul 01, 2011 1:19 pm UTC

Re: 1516: "Win by Induction"

Postby Cygnwulf » Fri Apr 24, 2015 12:22 pm UTC

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....

User avatar
Neil_Boekend
Posts: 3220
Joined: Fri Mar 01, 2013 6:35 am UTC
Location: Yes.

Re: 1516: "Win by Induction"

Postby Neil_Boekend » Fri Apr 24, 2015 12:36 pm UTC

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

dp2
Posts: 346
Joined: Wed Aug 18, 2010 3:06 pm UTC

Re: 1516: "Win by Induction"

Postby dp2 » Fri Apr 24, 2015 12:59 pm UTC

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.

User avatar
Copper Bezel
Posts: 2426
Joined: Wed Oct 12, 2011 6:35 am UTC
Location: Web exclusive!

Re: 1516: "Win by Induction"

Postby Copper Bezel » Fri Apr 24, 2015 1:04 pm UTC

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

User avatar
alvinhochun
Posts: 54
Joined: Wed Nov 14, 2012 3:07 pm UTC

Re: 1516: "Win by Induction"

Postby alvinhochun » Fri Apr 24, 2015 1:08 pm UTC

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

Showsni
Posts: 118
Joined: Wed Sep 14, 2011 9:09 pm UTC

Re: 1516: "Win by Induction"

Postby Showsni » Fri Apr 24, 2015 1:11 pm UTC

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...)

User avatar
alvinhochun
Posts: 54
Joined: Wed Nov 14, 2012 3:07 pm UTC

Re: 1516: "Win by Induction"

Postby alvinhochun » Fri Apr 24, 2015 1:16 pm UTC

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.

airdrik
Posts: 246
Joined: Wed May 09, 2012 3:08 pm UTC

Re: 1516: "Win by Induction"

Postby airdrik » Fri Apr 24, 2015 2:03 pm UTC

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.

leeharveyosmond
Posts: 53
Joined: Fri Jan 01, 2010 11:03 pm UTC

Re: 1516: "Win by Induction"

Postby leeharveyosmond » Fri Apr 24, 2015 2:20 pm UTC

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.

User avatar
Jackpot777
Posts: 328
Joined: Wed Sep 14, 2011 1:19 pm UTC

Re: 1516: "Win by Induction"

Postby Jackpot777 » Fri Apr 24, 2015 2:40 pm UTC

Neil_Boekend wrote:Maybe pokeballs are bigger on the inside.


Well THAT explains this scene...

Image

User avatar
Flumble
Yes Man
Posts: 2264
Joined: Sun Aug 05, 2012 9:35 pm UTC

Re: 1516: "Win by Induction"

Postby Flumble » Fri Apr 24, 2015 4:00 pm UTC

Jackpot777 wrote:
Neil_Boekend wrote:Maybe pokeballs are bigger on the inside.


Well THAT explains this scene...

Image

That one's just smaller on the outside.

rmsgrey
Posts: 3655
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: 1516: "Win by Induction"

Postby rmsgrey » Fri Apr 24, 2015 5:56 pm UTC

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!

ps.02
Posts: 378
Joined: Fri Apr 05, 2013 8:02 pm UTC

Re: 1516: "Win by Induction"

Postby ps.02 » Fri Apr 24, 2015 6:05 pm UTC

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.

Zylon
Posts: 142
Joined: Fri Jan 30, 2009 5:37 pm UTC

Re: 1516: "Win by Induction"

Postby Zylon » Fri Apr 24, 2015 6:08 pm UTC

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.

User avatar
Quizatzhaderac
Posts: 1824
Joined: Sun Oct 19, 2008 5:28 pm UTC
Location: Space Florida

Re: 1516: "Win by Induction"

Postby Quizatzhaderac » Fri Apr 24, 2015 7:29 pm UTC

Don't pokemon have to wait a turn after summoning before they can act?
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.
Start the first pikachu with an empty set.
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.

User avatar
slinches
Slinches get Stinches
Posts: 1036
Joined: Tue Mar 26, 2013 4:23 am UTC

Re: 1516: "Win by Induction"

Postby slinches » Fri Apr 24, 2015 7:57 pm UTC

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.

airdrik
Posts: 246
Joined: Wed May 09, 2012 3:08 pm UTC

Re: 1516: "Win by Induction"

Postby airdrik » Fri Apr 24, 2015 8:17 pm UTC

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.

Epistemonas
Posts: 12
Joined: Thu Jan 03, 2013 7:58 am UTC

Re: 1516: "Win by Induction"

Postby Epistemonas » Fri Apr 24, 2015 8:27 pm UTC

slinches wrote:While Pikachu (the individual character) can become a trainer and capture pokemon…

[citation needed]

User avatar
slinches
Slinches get Stinches
Posts: 1036
Joined: Tue Mar 26, 2013 4:23 am UTC

Re: 1516: "Win by Induction"

Postby slinches » Fri Apr 24, 2015 9:09 pm UTC

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.

Garnasha
Posts: 45
Joined: Sat Dec 04, 2010 12:32 am UTC

Re: 1516: "Win by Induction"

Postby Garnasha » Fri Apr 24, 2015 10:20 pm UTC

Quizatzhaderac wrote:Don't pokemon have to wait a turn after summoning before they can act?
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.
Start the first pikachu with an empty set.
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.
Thank you. Someone who gets the horror of infinite binary trees and their leafcount.

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?

User avatar
orthogon
Posts: 3103
Joined: Thu May 17, 2012 7:52 am UTC
Location: The Airy 1830 ellipsoid

Re: 1516: "Win by Induction"

Postby orthogon » Fri Apr 24, 2015 10:48 pm UTC

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 2x3y. It's the same reason that the rationals are countable.
xtifr wrote:... and orthogon merely sounds undecided.

User avatar
Copper Bezel
Posts: 2426
Joined: Wed Oct 12, 2011 6:35 am UTC
Location: Web exclusive!

Re: 1516: "Win by Induction"

Postby Copper Bezel » Fri Apr 24, 2015 11:20 pm UTC

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 in-joke 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

Garnasha
Posts: 45
Joined: Sat Dec 04, 2010 12:32 am UTC

Re: 1516: "Win by Induction"

Postby Garnasha » Sat Apr 25, 2015 12:51 am UTC

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 2x3y. It's the same reason that the rationals are countable.
No, because the generation and number of splits doesn't give you the order in which you took lefts and rights.

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).

rmsgrey
Posts: 3655
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: 1516: "Win by Induction"

Postby rmsgrey » Sat Apr 25, 2015 2:55 am UTC

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.

RogueCynic
Posts: 409
Joined: Sun Nov 22, 2009 10:23 pm UTC

Re: 1516: "Win by Induction"

Postby RogueCynic » Sat Apr 25, 2015 3:16 am UTC

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?

User avatar
Copper Bezel
Posts: 2426
Joined: Wed Oct 12, 2011 6:35 am UTC
Location: Web exclusive!

Re: 1516: "Win by Induction"

Postby Copper Bezel » Sat Apr 25, 2015 3:35 am UTC

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

madaco
Posts: 165
Joined: Sat Feb 13, 2010 11:25 pm UTC

Re: 1516: "Win by Induction"

Postby madaco » Sat Apr 25, 2015 9:23 pm UTC

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.
I found my old forum signature to be awkward, so I'm changing it to this until I pick a better one.

Garnasha
Posts: 45
Joined: Sat Dec 04, 2010 12:32 am UTC

Re: 1516: "Win by Induction"

Postby Garnasha » Sun Apr 26, 2015 12:58 am UTC

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.
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 n-th 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 n-th 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.

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 headache-inducing uncountable infinities are? This is why.

zeta12ti
Posts: 1
Joined: Sun Apr 26, 2015 5:57 am UTC

Re: 1516: "Win by Induction"

Postby zeta12ti » Sun Apr 26, 2015 6:21 am UTC

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 30-40 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?
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.
Start the first pikachu with an empty set.
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:
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 2x3y. It's the same reason that the rationals are countable.
No, because the generation and number of splits doesn't give you the order in which you took lefts and rights.

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).

mhalver
Posts: 1
Joined: Sun Apr 26, 2015 7:05 am UTC

Re: 1516: "Win by Induction"

Postby mhalver » Sun Apr 26, 2015 7:20 am UTC

Garnasha wrote:
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.
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 n-th 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 n-th 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.

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 headache-inducing 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).

exfret
Posts: 22
Joined: Sat Feb 08, 2014 12:55 am UTC

Re: 1516: "Win by Induction"

Postby exfret » Sun Apr 26, 2015 11:26 pm UTC

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.


Return to “Individual XKCD Comic Threads”

Who is online

Users browsing this forum: Google [Bot], mscha and 89 guests