Goodstein Sequences and Huge Numbers - MegaFavNumbers

[@singingbanana]

This was great. I've thought about doing a Goodstein's theorem video before, but I didn't want to get too bogged down in the undecidable stuff. This was very nicely done.

[@jpphoton]

how confident are you guys that this theorem is indeed true? it seems to me still impossible and a fallacy lay in how this problem is mapped to herditary notation. i guess is all predicated on assuming trans-finite ordinal are a legit thing no?

[@TheLuckySpades]

​@@jpphotonif you accept a standard model of set theory (as in a standard model of ZF(C)) as true then GT is provable within ZF(C) since that is where transfinite ordinals are defined Very few mathematicians (I can only think of one and he is considered extremely fringe and doubt there are others) do not accept at least ZF

[@kevindu3099]

Truly huge number are pretty cool. - another member of the Googology squad

[@legendgames128]

I noticed that for any tiny Goodstein sequence (let's take 3 to be our input), once the only term is a constant less than the base number, the sequence *will* terminate. So now the simpler question is do all Goodstein sequences reach this constant less than the current base number?

[@mathematimpa]

Yes, this is true and the proof of the theorem aims exactly on that. The tricky part is that you need to use transfinite ordinals to get to this conclusion, as regular arithmetic won't cut it.

[@Pika250]

And who else would say "GT is not in logic" and actually mean it? To timpa and mathematicians like him, this means "[the proof of] Goodstein's Theorem is not in first-order [arithmetical] logic". To someone like, say Andy Laso on a Legend of Zelda A Link to the Past randomizer, the GT would instead be Ganon's Tower (the gauntlet Link needs to conquer to unlock the "Ganon" dropdown, named as such because it whisks Link into the final fight against Ganon in the vanilla game, and indeed on some randomizers), and the logic would be based on Link's current arsenal (in this case he doesn't have the right items to conquer all the crystal dungeons needed to open Ganon's Tower, perhaps for example his Master Sword pedestal has his ice rod which he would need for Trinexx which guards a crystal, and he would need all of the pendants to pull it and two of them are locked by the hammer which in turn would require showing the third pendant to Sahasrahla).

[@Pika250]

And this is a fitting analogy, especially if it's a seed like this. The tower represents the big theorem, the pieces of equipment and corresponding logic represent the pieces of the puzzle, and that specific seed becomes unbeatable if the specific pendant that leads to the hammer is also locked by the hammer, for example the pendants being Skull Woods (with fire rod in Thieves' Town big chest, which requires hammer to access, where fire rod is needed to unlock the path to the boss), Swamp Palace and Palace of Darkness (both of which need hammer for Link to progress)

[@humbledb4jesus]

never thought of base numbers like this...great job...

[@ravi12346]

Great video! But doesn't the Goodstein sequence for 4 reach 3 * 2^402653210 - 1 (i.e. about twice what it says in the video)? That's what I got when working it out by hand, and Wikipedia seems to agree.

[@mathematimpa]

You are right, I must have mixed it up with the basis.

[@lilmarionscorner]

When calculating I got 3 * 2^201326605 -1 (sqrt the amount you calculated) I must have calculated it wrong of missed a step because I sometimes do.

[@muskyoxes]

Whenever a video says that i already know something, that video is guaranteed to explain that something anyway.

[@MrBrain4]

I do not concur with the expression at 3:08 for 1080. That hereditary base expression adds up to 1008. For 1080, I get the hereditary base notation of 3^(2*3^1)+3^(3^1+2)+3^(3^1+1)+3^(3^1).

[@falkland_pinguin]

Me too...

[@schwartztutoring]

The videos answer corresponds to 1008

[@tony0000]

Hereditary mean coefficients LESS than base? Seems less than or equal to.

[@gepmrk]

Almost as dramatic an increase as TREE(3).

[@nzqarc]

Haha...nope This is addition compared to TREE(n)

[@karlwaugh30]

Excellent video. Personally I'd have loved it to go deeper but it was still pretty full on so fair play.

[@zhadoomzx]

If the size of a number was related to how decidable a statement including that number is, then no induction proof should be decidable either.

[@mathematimpa]

The size of the number is not the problem, but the family of sequences where it originates from. A related idea shows up in 'Busy Beavers'

[@DavidRabahy]

Really good!

[@usernameisamyth]

Thanks Good stuff

[@robertunderwood1011]

So can that exponent be factored?

[@ffggddss]

Prime factorization: 402653209 = 7·57521887 According to Ravi Fernando's comment, the exponent should be larger by 1: 402653210 = 2·5·41·991² Fred

[@seneca983]

If you're using Linux, you can just write "factor 402653209" on the command line and get the result.

[@fullfungo]

I’m pretty sure it’s not undecidable. Let’s define a predicate GS(n) as “Goodstein sequence starting from *n* eventually reaches 0”. Then GS(n) holds for all *n* . That’s it, no undecidability; even better, you don’t need to check what *n* is, except that it’s a natural number. The set of *n* for which GS(.) holds is trivially *N* It is decidable by definition, since there is a program that gives the correct result for all valid inputs, namely “return true”

[@mathematimpa]

The point that's important for undecidability is whether or not you can prove the statement USING A GIVEN SET OF AXIOMS. So unlike truth, it is dependant on what axioms you start with. Goodstein's Theorem is undecidable under Peano's Axioms of arithmetic, which to fit in your reasoning means you can't use just Peano's Axioms to conclude that your program that just returns "true" is correct. If you argue that it works because there are no counterexamples, then you are not proving anything because you are assuming your conclusion as an hypothesis. On the other hand Goodstein's Theorem can be proved true if we use Transfinite Ordinals (it is a consequence that any strictly decreasing sequence of ordinals must end at 0)

[@fullfungo]

@@mathematimpa from Wikipedia “decision problem is a problem that can be posed as a yes-no question of the input values” “a true/false decision problem is decidable if there exists an effective method for deriving the correct answer.” “effective procedure is a procedure for solving a problem by any intuitively 'effective' means from a specific class. An effective method is sometimes also called a mechanical method or procedure […] It consists of a finite number of exact, finite instructions. When it is applied to a problem from its class: It always finishes (terminates) after a finite number of steps. It always produces a correct answer. In principle, it can be done by a human without any aids except writing materials. Its instructions need only to be followed rigorously to succeed. In other words, it requires no ingenuity to succeed.” So I still believe my comment is correct. The program GS(.): Consists of a finite number of instructions (return true); Always terminates in a finite number of steps (1); Always produces a correct answer (Goodstein sequences do indeed reach 0 for any input); It can be done by a human (say/write “yes” or “true”) Additionally, GS(.) is indeed a yes/no problem. And an effective method for it exists “return true” (as argued above) What you are describing is unprovability or independence: “In mathematical logic, independence is the unprovability of a sentence from other sentences. A sentence σ is independent of a given first-order theory T if T neither proves nor refutes σ; that is, it is impossible to prove σ from T, and it is also impossible to prove from T that σ is false. Sometimes, σ is said (synonymously) to be undecidable from T; this is not the same meaning of "decidability" as in a decision problem.” So it *could* be called undecidable, but this is not the normative use of “undecidable”, the term “unprovable” is more common and does not cause such a confusion.

[@fullfungo]

@@andretimpa I’m a CS bachelor, so I might be biased in terms of definitions. During my studies, the term “undecidability” was only used for “a question that can’t be answered by a computer program”; and “unprovability” for “a theorem you can’t prove” (more or less). I’m also obviously limited by the fields of maths that I like to research and dig into. So I have never seen “undecidable” used in place of “unprovable”. Btw, can you tell me which areas use this terminology?

[@mathematimpa]

@@fullfungo I might be in a different "bubble" in this aspect, since I'm a physicist (also English is not my first language, I'm more used to how these things are called in Portuguese). KZbin deleted the previous comment because I put an external link, but look for "Proving a statement is true by proving it is undecidable." in math exchange or look for "Undecidable but true" in Google. Everyone there is talking about undecidability in the sense of being unprovable and everyone is just roling with it. That's why I'd take that statement about how customary it is to use each meaning with a grain of salt (it's Wikipedia after all). That being said I have also heard about independence (I just thought they were synonyms) when used for axioms (like the axiom of choice being independent from ZF). In the end I think it's more of a question of knowing your audience and checking the definitions if things start to get fishy.

[@tony0000]

@@mathematimpa Are you saying that Goodstein's Theorem can be derived from Paeno's Axioms plus the statement "any strictly decreasing sequence of ordinals must end at 0"?

[@blcrlink3d138]

I don’t get why it is undecidable can you elaborate it?

[@legendgames128]

Undecidable in 1st order arithmetic is what he says. If we use 2nd order arithmetic, or use infinite ordinals, it can be proven.

[@NorbertKasko]

Well, no. That's the number of STEPS after the Goodstein sequence of 4 terminates. It's not the the largest number in the sequence. We don't know that. Simply because nobody ever will be able to calculate all the numbers in a sequence with 3* 2^402653209 STEPS. Too much calculation. It would take an eternity especially considering how difficult is to wtite an effective algorithm for the sequence but the sheer number of steps also makes it impossible.

[@ibrahimali3192]

Well, no. We DO know that is the largest number in the Goodstein sequence of 4. The number of steps is bigger than that. It is proven that it gets to that number and then begins a VERY SLOW descent down to 0. This is because, at that point, the actual number ends up becoming smaller than the hereditary base and doesn't increase anymore, so the -1 slowly but surely eats it up.

[@NorbertKasko]

@ibrahimali3192 Your logic doesn't make any sense. After each step you have bigger and bigger jumps between the numbers how would you be able to tell which number is the last before descending in a very long sequence?! You said that number of steps is even bigger than 3*2^402653209. (Which it isn't. That's the exact number).

[@ibrahimali3192]

​@@NorbertKasko i did a little more research; the number of steps is 3*2^402653211 - 2. The biggest number is 3*2^402653210 - 1. (so we were both wrong)