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!
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?
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).
@@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.
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.
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.
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!
@@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.
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.
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
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.
Also, for the sequence for 5, it looks like the 1s term for the first number in the term doubles and subtracts 1 every time it reaches the next chunk. So 1,3,7,... does this pattern hold?
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.)
even though I already know about the Goodstein sequence, ordinal arithmetic, fundamental sequences, and the fast growing hierarchy this video feels impossible to follow. If this was a lecture, there would be some solace in knowing the teacher has to write all this notation down, giving me time to think, instead, you have so much of it appear and disappear so quickly and with so little attention given to it, (at points you literally say "it becomes this", and move on) it becomes nearly impossible to follow.
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?
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.
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.
All of these and we still haven't been able to prove Collatz conjecture. It'd be awesome if it's actually false but we need fastest growing hierarchy to prove that
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.
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.
6:37 Why does this not work for epsilon_0? Intuitively (naively), if you take {epsilon_0}_k = a k-high power tower of omega, it seems like epsilon_0 should be the limit of that as k goes to omega.
@@rtg_onefourtwoeightfiveseven It's a deficiency of the definition I give: since epsilon_0 = omega^(epsilon_0)---which is then its Cantor normal form---my definition reduced to {epsilon_0}_k = omega^({epsilon_0}_k), which would just give {epsilon_0}_k = epsilon_0, at least as a minimal solution. For ordinals less than epsilon_0, we're guaranteed that the exponents in Cantor normal form are strictly smaller than the original ordinal, which makes the definition work.
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 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...
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.
@@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)
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.
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.
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
jfc, I thought "sheafification" (and your channel's about section) was something you made up as a joke to make fun of how teaching/learning mathematics is usually accompanied by frequent situations where you have a bit of confidence until you enter a class that starts using terms and definitions you're unfamiliar with as if you're supposed to know and understand them... And that you, the channel owner, felt comfortable making that joke because of all the math classes you've been through, taking note of the commonly hellish scenario... but... no. "Sheafification" is an actual thing... I've been bamboozled by the very situation I thought was intentional.
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.
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!
![BabyChiefDoit - Too Slow (feat. STAR BANDZ) [Official Music Video]](http://i.ytimg.com/vi/zayaxws7RPg/mqdefault.jpg)
![The most beautiful equation in math, explained visually [Euler’s Formula]](/img/1.gif)
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!
you are a monster
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
Fast growing hierarchy my beloved
YİNE KARŞILAŞTIK!
Sen matematik okuyor musun ya?
vay be deniz abem
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
You almost experienced your own fast-credit ending! Glad you survived
Good to see transfinite induction repped on YT so well.
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?
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).
@@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.
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.
@@duncanw9901 PA as in first-order. Second-order is strong enough to define representations of ordinals!
That was a genius way to end the video!
This was so enjoyable to watch. 😂 Finding the perfect spot between inflrmative and just trolling your viewers is not easy, chapeau!
Now I hope one day you get ω-th subscriber, so your statement at the end is false
it would also be false if he had 0 subscribers
If he makes it to ε_0, and even base-k borrows will not make sense.
@@viliml2763 You forgot his desk fan
I never thought I would see Psaiki K in a Googology video. 2024 is both amazing and terrible.
This single video has better memes than all of /r/mathmemes combined
Well, I'm almost finished watching all of your videos. I can only say this: if you make more, I'll gladly watch it :)
Love this channel ! Very good work man
Thanks fam!
your feelings are irrational
“teal DW” really tickled my funny femur
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.
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!
@@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.
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.
I appreciate the subtitles ❤
Merci pour cette vidéo géniale !
Merci !
"Well you probably looked it up on Wikipedia" So who did the calculation that even allowed Wikipedia to have that number?! /lighthearted
Awesome video ❤
bro i didnt understand any of this but it good yes video words thank you.
1:41 I'll watch it after this one ok? RUclips brought me here first is all
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
The videos are so good
Please more on oridals and the fast growing hierachy. Also could you recommend a textbook om this topic for someone with engibeering math background?
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.
Please less on oridnals and the fast growing hierarchy.
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
cool video!
Thanks!
Also, for the sequence for 5, it looks like the 1s term for the first number in the term doubles and subtracts 1 every time it reaches the next chunk. So 1,3,7,... does this pattern hold?
Really cool!
Awesome video series! Was wondering what book you'd suggest to get further into the topics
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.)
@@SheafificationOfG Thanks for taking the time to give a detailed answer, I really appreciate it!
So cool 👌
I see Saiki Kusuo no Psi Nan meme, I like
even though I already know about the Goodstein sequence, ordinal arithmetic, fundamental sequences, and the fast growing hierarchy
this video feels impossible to follow.
If this was a lecture, there would be some solace in knowing the teacher has to write all this notation down, giving me time to think, instead, you have so much of it appear and disappear so quickly and with so little attention given to it, (at points you literally say "it becomes this", and move on) it becomes nearly impossible to follow.
Just pause the video when necessary.
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?
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.
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.
All of these and we still haven't been able to prove Collatz conjecture. It'd be awesome if it's actually false but we need fastest growing hierarchy to prove that
Excellent video! Minor correction: Stan Wainer is British; his last name is pronounced in the obvious English way, not German.
@michaelsheard4522 crap, thank you. I should've just looked him up before assuming haha
17:14 what if every one unsubscrives?
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.
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.
Nice!
6:37 Why does this not work for epsilon_0? Intuitively (naively), if you take {epsilon_0}_k = a k-high power tower of omega, it seems like epsilon_0 should be the limit of that as k goes to omega.
My definition doesn't account for epsilon_0, but what you suggest is the canonical way of making it work!
@@SheafificationOfG What stops the definition from accounting for epsilon_0 like it accounts for the ordinals below it?
@@rtg_onefourtwoeightfiveseven It's a deficiency of the definition I give: since epsilon_0 = omega^(epsilon_0)---which is then its Cantor normal form---my definition reduced to {epsilon_0}_k = omega^({epsilon_0}_k), which would just give {epsilon_0}_k = epsilon_0, at least as a minimal solution.
For ordinals less than epsilon_0, we're guaranteed that the exponents in Cantor normal form are strictly smaller than the original ordinal, which makes the definition work.
@@SheafificationOfG Makes sense, thanks!
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?
You're not missing anything! There are nonstandard models of the naturals where some numbers have infinite Goodstein sequences!
@@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...
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.
@@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)
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.
amazing ++++
Bro what are you talking about
You can’t handle this can you
@@EntergeticalakaBot im afraid not 😭. I tried to watch this casually but maybe in a few years
@@zuperdude7701 don’t worry i felt the same with another g++ video lol
@@zuperdude7701ngl I'm completely lost in the very first minute when a seemingly growing sequence goes to zero? Wat????
this isn't for middle schoolers lil bro
Remember people: you can't address an ordinal number of things
GODstein . +10, like y a favoritos
And thats the weak Goodstein sequence.
The stronger one actually reaches ε0 in FGH
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.
@@SheafificationOfG That's a massive jump from the weak function to the strong one lmao
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
The video relies a good bit on its prequel, so 40% ain't bad!
jfc, I thought "sheafification" (and your channel's about section) was something you made up as a joke to make fun of how teaching/learning mathematics is usually accompanied by frequent situations where you have a bit of confidence until you enter a class that starts using terms and definitions you're unfamiliar with as if you're supposed to know and understand them... And that you, the channel owner, felt comfortable making that joke because of all the math classes you've been through, taking note of the commonly hellish scenario... but... no. "Sheafification" is an actual thing... I've been bamboozled by the very situation I thought was intentional.
goodstin :)
I didn't understand anything, but nice video nontheless
sir, this is a wendy's
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.
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!
all of my code finishes in O(f_ω(n)) time ;-;