TREE(3) (extra footage) - Numberphile

hi everyone this is extra footage about the massive number tree three if you haven't watched the original video on the numberphile channel it might be worth watching that first what is it good for what what is it useful for what is this any of this got to do with anything that's important this is really important in proof theory okay so there's something called kruskal's tree theorem it's quite a long story short let me sort of very loosely paraphrase what what kruskal's tree theorem is well this was something that comes from a guy called joseph kruskal he was a very influential mathematician did stuff in computer science did stuff in combinatorics and he proved this this particular tree thing which involves these something to do with all these trees okay but basically he says imagine the set of all the different combinations of seeds that you use okay and imagine there's some sort of ordering some sort of it's called well quasi ordering okay so some sort of notion of ordering in that set then he said the corresponding trees that you build out of those the set of all them is also has some sort of notion of ordering and for us the the notion of ordering is this idea that eventually you'll find one tree that contains a previous tree right what's what's any of this got to do with proof theory you can't prove kruskal's theorem using finite arithmetic so if you just play with finite arithmetic finite number you cannot prove kruskal's theorem another way of saying that is if you try to prove that tree of n was finite for all n you can't do that using finite arithmetic it's just not possible you can however it's given any value of n you can prove that tree n is finite so if you say can i prove is tree three finite or tree four finite you can so you can't generalize but you can do specifics yes so you can take any particular choice of n tree three tree four tree five and you can use finite arithmetic to prove it's finite it just takes a very long time okay so how long does it take to prove it for tree three so if i'm going to use finite arithmetic that's all i'm going to use and i want to prove that tree 3 is finite well a guy called harvey freeman worked this out and he said to prove that tree three is finite using finite arithmetic you would need this many symbols okay and this is ridiculous right two arrow arrow a thousand now you may remember what this north arrow notation means it basically it's kind of the it's like explanation exponentiation on on steroids right so if this really means two to the two to the two to the two a thousand times so this tower contains a thousand twos okay so this is how many symbols you would need to prove that tree three is finite using only finite arithmetic what do you mean by symbols you mean like plus sign yeah just yeah essentially yeah any kind of operation yeah those sorts of things okay now you could use trans-finite arithmetic this whole game of ordinals and all that and do things much quicker right and that's how you can prove it's true for all n actually but if you just want to use finite arithmetic you need this many symbols so presumably that hasn't been done well let me see if let's ask can it be done okay so how fast could you do it what's the fastest you could write down any one symbol okay that's a plank time you definitely can't write a symbol down faster than one planck time which is about 10 to the minus 43 seconds it's a tiny length of time so let's assume you can write down one symbol every planck time which is pretty fast which is pretty fast it is and you definitely aren't going to do any faster without things collapsing into black holes okay so that's the fastest you can go right could you have got anywhere if you even if you'd started at the big bang so you start the big bang do a symbol every plank time would you've got anywhere nowhere you'd have got nowhere in this proof okay could you ever finish there's another thing you could ask could you you know carry on arbitrarily far in the future could i have a finish and even the answer to that is no and the reason the answer to that is no is because well we we look outside we do cosmological observations and there's a strong evidence to suggest that there's a finite entropy in our universe and what that means is there's a finite number of states what that means is is that eventually you'll get what's called a poincare recurrence which we've talked about before and the universe will eventually reset itself the universe will eventually reset itself and that will happen after this poincare recurrence time so which happens first do you finish the proof or does the universe reset itself easy the universe resets itself way before so before you're doing this proof and then ah the universe resets itself this is a disaster so you've never finished this proof of practice it's just it's just crazy you see then you might ask okay right so i can't actually write down this proof this is gonna just the universe is gonna reset itself before i get a chance to finish it off okay could the proof just materialize well let's just imagine it did okay well then you have a problem because you can't fit the proof in our universe so this is no good anyway so it's just it it's just it might the proof might exist in principle but no mathematician is going to write it down at any point but yeah so the the trans finite proofs you know in particular you can prove kruskal's tree theorem so you can prove that these trees are finite for any n you know all this sort of ordinal arithmetic all this sort of stuff to um to prove that uh but yeah if you just want to use finite arithmetic but you can't prove kruskal's tree theorem using finite arithmetic but you can proving any individual tree and number using using the final arithmetic it just takes a really really really really really long time if i said to you okay start working your way towards tree three and start drawing all the trees and it would take obviously a long time until you ran out well we could kill the forest straight away if we wanted to but yeah that's the longest we could do yeah absolutely yeah does it excite you to think there is a number like does it excite you to think there is this finite number just i think so i think that's what's so cool about it it's not that that it's i mean it's well there's two things that i think are particularly cool about one that it is finite that this game whatever happens is going to end now the universe might reset itself before it ends but we won't go into that detail but this game is going to end right the other thing that's mad about this is absolutely crazy about it is that you go from one to three to just something that's just unbelievably gargantuan it's just that's what kind of sequence does that that's just mad right but you get these sorts of things in mathematics and and it's only enough facts that i think these things really happen i want to know what it is it's just lurking out there like it's too big to for any kind of physical anything in physics just you know it you can't relate it to this to this uh to this process to this to this number it's just too big is it one of those cases where we know the last digit is a four no nothing the only thing we know it's it's the only thing is that it'll take this long to prove how big it is that's the closest we can get to touching it and even that is just ridiculous often when we do these videos there's there's uh on big numbers there's some clever person we'll put on the on the comments oh i know a bigger one and they'll put on this one tree three plus one okay you've seen them right okay to pre-empt that i want to do something a bit better okay so three three plus two now well three three four three yeah okay very good well there's certain things you could start writing down one of them would be of course very simply tree four all right that's not so amazing that's way bigger than three three okay but so what right how about this one three three but not three tree three let's put tree of tree three okay so now what we're saying is we've got three three number of possible like a seed and we're gonna ask how many trees can we build out there that's off the scale that i mean that is what god knows about like and then we could do that again look what we do we can do tree it's getting bigger and bigger right what we're doing is we're iterating this is what we're doing we're iterating so in a way we could define the following right we could take any tree of n okay and i'm going to put a little uh subscript on it okay so we take tree of n i'm going to call 3 of 0 of n tree of n and i'm going to call tree of m plus one of n is tree of tree of m of n so what this is saying is is that i keep doing this kind of thing i keep adding another tree to increase this number by one i just apply tree again right so i could keep doing that and i could just do it and i can define this new quantity which is tree of m of n right you might think okay i can get really big stuff with these things right well but now i need two numbers to describe it no i don't i can diagonalize and i can introduce a new thing which is tree n of n so it's n applications of tree to the number n right and i'm going to call that tree bar okay and now what i've done is i've caught i've i've suddenly opened the whole thing up again i've kind of almost gone back to the start but gone back to the start somewhere that's way bigger right so this what we're doing is we've got the idea of recursion and diagonalization and this is how in maths you build really really really really really big things these fast growing hierarchies um but that's definitely another video you know the thing i like there is compared to like the infinite number of numbers we're still just a drop in the ocean it is it's not it's not yeah that's true it's true it is it's nothing compared to those guys this is just way bigger than anything that you could even begin to imagine in physics does this make you happy it sort of it makes me sort of it makes me kind of feel kind of powerful it's like knowing that there's this there's this crazy number that you know somebody say oh show you a big number oh yeah whatever tree three is bigger than that you know this this thing there's like this thing out there that you've got all these physical processes going on in the universe all around you none of them are anything compared to tree three tree three could batter them and then even if you came up with something that three three could batter i just do three of three three and i can batter it again and it just goes on and on and on it's like it suddenly you wield this incredible power uh that only mask can give you i think well if you're still watching now you obviously like this extra material have you subscribed to numberphile2 the channel you're on now if you haven't press the subscribe button and maybe press the little bell to get notifications as well thanks for watching we'll be back again soon

Channel: Numberphile2

Views: 708,644

Keywords: tree3, planck, Joseph Kruskal, kruskal

Id: IihcNa9YAPk

Length: 11min 2sec (662 seconds)

Published: Thu Oct 19 2017