2Fast2Finite: Breaking the natural speed limit of finite numbers

To try everything Brilliant has to offer-free-for a full 30 days, visit brilliant.org/GSheaf/ . You’ll also get 20% off an annual premium subscription.
In a previous video, we used infinite ordinals to prove that certain finite number sequences called Goodstein sequences were necessarily finite. Now, let's take this one step further and derive a formula for computing the precise length of these sequences! This will also give a bit of insight to why the previous video delved into a language of "infinities" even though the problem is purely of finite nature.
Prerequisite:
• Solving a finite numbe...
References:
[Cai07] A.E. Caicedo. 2007. "Goodstein's function."
[Cic83] E.A. Cichon. 1983. "A short proof of two recently discovered independence results using recursion theoretic methods." Proc. of the Am. Math. Soc. 87(4), 704--706.
[Wai70] S.S. Wainer. 1970. "A Classification of the Ordinal Recursive Functions." Arch. Math. Logik 13, 136--153.
__________
Timestamps:
00:00 - Introduction
01:15 - Recap
02:36 - A closer look at each term's shape
03:26 - omega minus one
04:04 - Wainer fundamental sequences
06:43 - Ordinal "predecessor"
08:48 - The main focus
09:41 - Fast-growing hierarchy
11:25 - The main theorem
12:19 - Induction base case
12:38 - Induction step
15:03 - Formula for Goodstein sequence length
15:50 - Thx 4 watching
16:00 - Epilogue
__________
This video was sponsored by Brilliant.

[@SheafificationOfG]

Thank you Brilliant for sponsoring! To try everything Brilliant has to offer-free-for a full 30 days, visit brilliant.org/GSheaf/ . You’ll also get 20% off an annual premium subscription!

[@Fire_Axus]

you are a monster

[@denizgoksu9868]

Fast growing hierarchy my beloved

[@huhneat1076]

This video is so wild. I can't tell at any moment if the 3B1B music is going to fade in, or if Kusuo is going to sneeze the video in half

[@Filup]

I am currently recovering from the flu and the Neir credits caught me so off guard that I almost died hacking my lungs up lmfao

[@SheafificationOfG]

You almost experienced your own fast-credit ending! Glad you survived

[@newwaveinfantry8362]

That was a genius way to end the video!

[@notEphim]

Now I hope one day you get ω-th subscriber, so your statement at the end is false

[@viliml2763]

it would also be false if he had 0 subscribers

[@computationaltrinitarianism]

If he makes it to ε_0, and even base-k borrows will not make sense.

[@finxy3500]

@@viliml2763 You forgot his desk fan

[@newwaveinfantry8362]

I never thought I would see Psaiki K in a Googology video. 2024 is both amazing and terrible.

[@AdvayMengle]

Good to see transfinite induction repped on YT so well.

[@carloselfrancos7205]

Well, I'm almost finished watching all of your videos. I can only say this: if you make more, I'll gladly watch it :)

[@StefanoTrevisani]

This was so enjoyable to watch. 😂 Finding the perfect spot between inflrmative and just trolling your viewers is not easy, chapeau!

[@glorialee-goldthorpe1007]

Awesome video ❤

[@redpepper74]

“teal DW” really tickled my funny femur

[@Deathington.]

I appreciate the subtitles ❤

[@carloselfrancos7205]

Love this channel ! Very good work man

[@SheafificationOfG]

Thanks fam!

[@Fire_Axus]

your feelings are irrational

[@VaradMahashabde]

The proof for the process ending in finite steps is relatively simple. Suppose the number in 42, in base 2 is 0b101010. Then make a tuple (1,0,1,0,1,0), with the numerical form being in base 2. Then the next entry is (1,0,1,0,0,2) = 101002 in base 3, then (1,0,1,0,0,1) in base 4, (1,0,1,0,0,0) in base 5, (1,0,1,0,1,0) in base 6, (1,0,0,6,6,6) in base 7, and so on. In this form, it is abundantly clear that the number is increasing in representation by increasing the base, but not in the actual face values. If we give a comparison relation to the tuples x= (x_m, ....,x_2,x_1,x_0), y= (y_n, ...,y_2,y_1,y_0), as x>y if m>n. If m=n, then x>y, if x_m > y_n. If x_n = y_n, then x>y if x_{m-1} > y_{m-1} and so on. Of course, x_m, y_N are non-zero. Using this comparison relation, we see that the entries keep decreasing. We know that x_0 is decremented at each step, so a finite number of steps. It will thus become 0 in a finite number of steps (precisely x_0 steps). Thus x_1 will be decremented in a finite number of steps and thus reaches 0 in a finite number of steps. Thus for any fixed i, x_i will be decremented in a finite number of steps, and reaches 0. Thus the largest x_n is set to 0 in a finite time. By induction, x_{n-1} is also set to 0 in a finite number of steps, and thus the entire tuple becomes (0,0,...,0,0) in finite time. Of course, inventing this machinery for the sake of this one proof fails to give any insight, the number of steps, etc, and the tuple construction is basically identical to a transfinite ordinal form. So the transfinite ordinal proof is prettier and more informative.

[@SheafificationOfG]

This argument only addresses ordinary base b expansions, which is provable in PA. However, Goodstein sequences are based on *pure* (or hereditary) base b expansions, meaning that the exponents are recursively expanded in pure base b as well. For example, 42 = 2^5 + 2^3 + 2^1 would actually expand to 2^(2^2+1) + 2^(2+1) + 2^1, and the next step of the Goodstein sequence would be 3^(3^3 + 1) + 3^(3+1) + 3^1 - 1. In particular, you can't really represent these hereditary expansion shapes using mere tuples of numbers, and this structure significantly complicates the proof. This is the main reason for introducing ordinals in Goodstein's original proof!

[@VaradMahashabde]

@@SheafificationOfG oh right, forgot about the exponents Edit : so infinite ordinals effectively "compresses" the exponential indexing to not move, while the tuple system still uses finite numbers for indexing inside the ordinal, so can't capture the decreasing nature of the ordinals properly? Of course we could more tuples to index the position inside the main tuples, but that just removes the problem to exponents inside exponents, and infinite ordinals compress all of that.

[@SheafificationOfG]

Exactly, the role of ordinals in the proof is to serve as a beautifully compact encoding of the tree-like "shape" of these nested exponentials, while also giving us exactly the kind of "ordering" we need to observe that these shapes descend to zero.

[@pyrogenic]

This video was very interesting, but I'll admit that I might need to train for another thousand years to claim the understanding of the content as my own

[@pacificll8762]

Merci pour cette vidéo géniale !

[@SheafificationOfG]

Merci !

[@rafaelaraujo-wt6ek]

Really cool!

[@God-gi9iu]

So cool 👌

[@cosmic4716]

cool video!

[@SheafificationOfG]

Thanks!

[@duncanw9901]

Wainer's theorem on the indeterminacy of termination of some member of the fast-growing hierarchy floored me more than the main result did---might we expect a video on that one sometime?

[@SheafificationOfG]

Just to clarify: all fast-growing functions (indexed by ordinals less than epsilon_0) provably terminate. The result is more that PA-provably terminating computable functions are necessarily bounded in growth by something in the fast-growing hierarchy (which implies the unprovability of Goodstein's theorem in PA). As for whether I'll make a video on it, we'll have to see! Ordinals have been getting a lot of my attention lately, and I want to diversify a bit to other topics I enjoy, but we'll see! In the meantime, you can always try giving Wainer's original paper a read: "A Classification of the Ordinal Recursive Functions" (though it's a 1970 paper, so it's not necessarily a walk in the park to parse).

[@duncanw9901]

@@SheafificationOfG I really should know to specify what something is provable relative to by now, lol. Yeah, thanks for the clarification and pointer, and no pressure! Great videos.

[@duncanw9901]

Oh I should also ask---first-order PA or (based and antifoundationalist-pilled) second-order PA? I would be much more surprised if it were the latter, as my intuition is basically that the latter entails everything "non-exotic and worth saying" about N.

[@SheafificationOfG]

@@duncanw9901 PA as in first-order. Second-order is strong enough to define representations of ordinals!

[@monsterhunter8595]

Nice!

[@yk-il6dn]

Awesome video series! Was wondering what book you'd suggest to get further into the topics

[@SheafificationOfG]

Thanks! I'm not sure about references pursuing this particular topic, but Jech's book on set theory is a good place to lay the necessary groundwork for anything else you look at, I think! (Alternatively, you can also look at the OG papers, like Kirby-Paris, Cichon, or Caicedo.)

[@yk-il6dn]

@@SheafificationOfG Thanks for taking the time to give a detailed answer, I really appreciate it!

[@maxmustermann5590]

Please more on oridals and the fast growing hierachy. Also could you recommend a textbook om this topic for someone with engibeering math background?

[@SheafificationOfG]

I always recommend Jech's book on set theory. I don't remember if it talks about fast-growing hierarchies, but if you understand the fundamentals of the book, then you're already in a good place for learning other stuff on your own.

[@joeeeee8738]

I wonder what is the inflection point (since it grows and then comes back to 0). Or if there are multiple inflection points? As in a roller-coaster

[@joshuaidugboe214]

I know this is not related to the video but it just came to mind, is a set containing all combinations of the natural numbers larger than the set of real numbers?

[@SheafificationOfG]

If by "set of all combinations" you mean "set of all subsets" (i.e., the power set), then the answer is no: the power set of the natural numbers is the *same size* as the set of real numbers.

[@palamedez]

The Power Set of the naturals P(ℕ) has the same cardinality as ℝ. You can for example take a map φ: ℝ -> P(ℕ) that maps a Real number to the Set of the decimal places of the number that have a 1. If you then take any M∈P(ℕ), you can just construct a real number by putting 1s at the decimal places given by the elements of M and 0s otherwise. So φ is surjective and therefore |ℝ|≥|P(ℕ)| You can show the converse statement by a simular Argument with the binary representation of a Real number.

[@michaelsheard4522]

Excellent video! Minor correction: Stan Wainer is British; his last name is pronounced in the obvious English way, not German.

[@SheafificationOfG]

@michaelsheard4522 crap, thank you. I should've just looked him up before assuming haha

[@LarsHHoog]

Would you consider to please remove the noise from the sound making it really hard to stay focused. Any kind of audio processing software with dignity has such functionality.

[@SheafificationOfG]

Since the audio is actually a lot better than my earlier videos (can you imagine), I didn't actually notice the poor audio quality! I'll keep working on fixing the audio more as the videos roll out.

[@WoolyCow]

bro i didnt understand any of this but it good yes video words thank you.

[@DanDart]

Remember people: you can't address an ordinal number of things

[@orterves]

1:41 I'll watch it after this one ok? KZbin brought me here first is all

[@Canadian_Teemo]

I see Saiki Kusuo no Psi Nan meme, I like

[@ModusTollendoTollens]

GODstein . +10, like y a favoritos

[@finxy3500]

If it's impossible to prove from first-order Peano axioms that every Goodstein sequence terminates, wouldn't that mean, by Gödel's completeness theorem, that there's a Model of the naturals in which they don't? What am I missing here?

[@SheafificationOfG]

You're not missing anything! There are nonstandard models of the naturals where some numbers have infinite Goodstein sequences!

[@finxy3500]

@@SheafificationOfG What axiom did we add to be able to prove Goodstein's theorem? The existence of infinite ordinals? That seems wrong to me, how would their existence change anything about the finite ordinals? I suppose you could just construct a model of the naturals in ZFC, prove this, and call it a day, but I am curious what axiom was implicitly used in this proof...

[@japanada11]

The implicit axiom used IS the axiom of infinity (existence of infinite ordinals). Even if the theorem says nothing about infinite ordinals, there is no proof without this axiom (or at least an axiom that's at least as strong). Basically, we live in one of two possible worlds: 1) Peano+infinity is consistent. In this case Goodstein's theorem is true, but no Peano arithmetic proof exists. 2) Peano+infinity is inconsistent. Then it's possible that there is a counterexample to Goodstein's theorem somewhere out there that we just haven't found yet. Unfortunately, by Gödel's second incompleteness theorem, we can never be 100% certain that we aren't in the second world.

[@finxy3500]

@@japanada11 *true in the standard model that is. I currently think the critical part is transfinite induction. If you want to forgo the whole set theoretical framework I think just defining an element ω satisfying φ(ω) := ∀n((is_finite(n)) → ω > n), where is_finite is some predicate to which induction can be applied, and ∀ω' ≠ ω(φ(ω') → ω' > ω) and including transfinite induction as an axiom could work. (I assume TFI would need to be an axiom here, but I don't know) EDIT: upon further reflection I think ω needs to be outside of PA because it needs to be outside of reach of regular induction. So we'd need to define a sort of natural numbers using a predicate "ℕ∋" (think as this as a symbol only, not bound by the axioms of set theory) or you could call it is_finite where regular induction only applies when is_finite(n)

[@SheafificationOfG]

Good question! I'm not sure how you're representing "transfinite induction" in this language of PA + omega, but if it's capable of encoding all of the natural operations up to exponentiation with omega, then that should be enough.

[@sequentiacyclica]

goodstin :)

[@BalthazarMaignan]

I didn't understand anything, but nice video nontheless

[@trifonmag4205]

And thats the weak Goodstein sequence. The stronger one actually reaches ε0 in FGH

[@SheafificationOfG]

This video actually covers the strong Goodstein sequences! The weak Goodstein sequence generated by 4 only has 21 terms. As shown in the theorem, the lengths of Goodstein sequences outgrow all functions in the fast-growing hierarchy indexed by ordinals less than epsilon_0. On the other hand, iirc, the weak Goodstein sequences grow at a rate comparable to f_omega.

[@trifonmag4205]

@@SheafificationOfG That's a massive jump from the weak function to the strong one lmao

[@paulfoss5385]

Great video, I love seeing the content on your channel, but one thing I don't love is seeing pewdiepie's face because of his antisemitism, homophobia and toxic fanbase. But other than that I loved the video. I love nice proofs and interesting mathematical structures, but there's also a part of my brain that's tickled by "number get big", it's nice when both can be satisfied.

[@SheafificationOfG]

Yikes, I'm ngl I don't actually know the first thing about pewdiepie (I'm only aware of the meme), but I'll keep that in mind in the future, thanks for letting me know. Glad you liked the rest, though!

[@barigamb]

I understood like... maybe 40% of this... I'm gonna stick to number theory thank you very much this infinite ordinal stuff is confusing. Great video tho

[@SheafificationOfG]

The video relies a good bit on its prequel, so 40% ain't bad!

[@zuperdude7701]

Bro what are you talking about

[@EntergeticalakaBot]

You can’t handle this can you

[@zuperdude7701]

@@EntergeticalakaBot im afraid not 😭. I tried to watch this casually but maybe in a few years

[@EntergeticalakaBot]

@@zuperdude7701 don’t worry i felt the same with another g++ video lol

[@zeta3341]

​@@zuperdude7701ngl I'm completely lost in the very first minute when a seemingly growing sequence goes to zero? Wat????

[@its_lucky252]

this isn't for middle schoolers lil bro

[@zokalyx]

sir, this is a wendy's

[@lyricalcarpenter]

all of my code finishes in O(f_ω(n)) time ;-;