Finally, someone beats me to the convergence of all goodstein sequences theorem, super nais example. Really recommend the Kirby and paris paper where it is first proven indecidable in peano aritmethic, by generalizing with the hydra game.
arithmetical would have been a good word to add. the problem only involves finite natural numbers, nothing with an infinite decimal expansion, only numbers you can, in principle, reach by starting at 0 and then going from n to n+1 as may times as necessary.
Using strong induction to prove that ordinals are well-ordered seems backwards, cause usually you define the ordinals to be well-ordered and then use that fact to prove strong induction works. But I know these videos are more of an intuitive introduction to ordinals than a rigorous treatment
Absolutely (I even defined them to be well-ordered in my last video)! I figured since it's such a counterintuitive consequence, it was worth "reproving" with examples. But yeah, the argument isn't terribly *well-founded* 😏
Well, they defined ordinals to have the property "every non-empty set has a minimum" and then proved the equivalent "there is no infinite strictly decreasing sequence". But it's true that you don't need the intermediate step of strong induction for that.
I guess the largest mental barrier for the proof is the idea that "descending" implies you substract -1 every step. But subtracting -1 from omega will not get you to any specific number, so whenever you "jump" one omega lower, you actually leap over inifitely many numbers in between. Otherwise you could not define the descending sequence in the first place. So yes, you could "avoid zero" for as long as you want, but not with a strictly descending sequence of ordinals, as the definition forces you to take ridiculous leaps every now and then (but only finitely many ^^ ).
My hype moments where when you revealed that the -1 makes the sequence always converge, and when I realized the very definition of ordinals force every decreasing sequence to converge
THANK YOU I've been looking for a good series about infinite ordinals forever! Finally something to live for (If anyone else knows some good infinite ordinal videos/series, please let me know)
@@SheafificationOfG Thanks for the rec! Love that video, it's actually the one that got me into infinite ordinals and how I came across your videos when searching for them!
ever since i knew about goodstein sequences, their construction seemed so convoluted for me, compared to stuff like the primitive sequence system and kirby-paris hydras, systems that are much simpler, but equally strong (ε_0 level in the fast growing hierarchy). those deserve much more attention
The hydra would definitely lend itself better to visual media like a video, and I was considering it, but they're too much for my glorified slide show to handle (and Goodstein's Theorem was the first of these that I was exposed to, so it has a special place in my heart).
You have 3.14K subscribers right now and that makes me afraid that if I subscribe I miiight be the one to ruin that... But, I do like to gamble sometimes... lol, great video - I've seen a lot about ordinals recently and I really liked your visual representations for them!
sry @SheafificationOfG (creator) for inconvenience, but I got another discovery... (I PROMISE THERE IS NO EDITS AFTER THIS THOUGH) STAY TUNED??? found that this sequence and the Hardy Hierarchy (HH) are related... just realised that G(4) = (w^w) -1 (3) is literally (w^w)-1 in base 3 of the HH, aka e121M. (i play too much ordinal markup) also, G(10) when plugged into the HH Calculator is: w^(w+1)+2 (3) = w^(w+1) (5) = 10{{{{n}}}}10, where n is 10^^^10^^^10^^^10^^^10^^10^^10^^10^^eeee49.847 and HH is just fast-growing hierarchy minus an omega, so G(65539) =(w^w^w^w)+3 (2) = w^w^w^w (7) is {7,8 [1,2]2} This is how to calculate the upper bound: Calculate the starting number in base-2, switch all 2s for omegas, and calculate this in the HH with a base of 3. For bigger powers of omegas though, Fast Growing Hierarchy is basically the HH but remove the base of omega from any exponent. (for n less than or equal to 10, you can use the HH calculator for this) Also, for n larger than 10, search Hardy Hierarchy and find the Googology Wiki article. Here, there is a HH to BAN conversion. how i found this: i watched superspruce playing ordinal markup and saw numbers like 1e300 around the w^3 range, and I just thought: potentially there is a connection? And I was right, after using a calculator to prove my theory. also, the ordinal decreasing thing is also in Naviary's infinite chess vid, about the longest game possible. EDIT: also, the SG function (super-goodstein) is basically the Goodstein function but with two differences: 1) It starts at base 3. 2) The ordinals collapse even further. For example, 3^^^3 is {3,3,3} = {3,3 [2] 2}. Inputting E3#^^^#3 returns f [SVO] (4) steps. Inputting 3&3&3&3 (3&3&3 can't be condensed), we get f [LVO] (4) steps before termination. Inputting f [BHO] (3), however, only returns f [BHO] (4) steps, so this function limits at the BHO. (the OG Goodstein function has a growth rate of {n,m [2]2} for m being the amount of omegas in the power tower, and becomes obsolete around godgahlah, or {100,101 [2] 2}. note: beyond epsilon-nought, HH and FGH are practically the same :)
i have to look at it more closely.. but is the statement you said about strictly descending ordinals terminating in finitely many steps only true about ordinals below the ordinal epsilon_0? or is that the case for even the largest large cardinal?
Let's define pred as the inverse of succ, x = succ(pred(x)). If it's true that a descending sequence of ordinals always reaches 0 in finitely many steps what does this mean for the ordinal before w? What is pred(w)? If I start at some ordinal x s.t. w < x < w^2, and I construct a sequence by taking x_n = pred(x_n-1) (the nth x is the pred of n-1th x) then at some point x goes from being an infinite ordinal to a finite ordinal. Consider x = w, by definition of w pred(w) is finite. But succ(pred(w)) is also finite, or else there exists a finite ordinal s.t. its successor is not finite. So pred(w) =/= pred(w) because there exists an ordinal succ(pred(w)) that is not w. So the claim that a decreasing sequence of infinite ordinals terminates in finitely many steps seems to imply it's possible to find "the largest finite ordinal" or pred(w). When you go from w to 50 it seems like you're conveniently skipping infinitely many ordinals just due to laziness, like what if you picked 51, an ordinal larger than 50, you haven't shown this also goes to 0 in finitely many steps.
I've got a noob question: in other videos, I've seen "the numbers bigger than all numbers" being referred to as Aleph numbers (Aleph 0 is infinitely bigger than all natural numbers, Aleph 1 is infinitely bigger than Aleph 0, etc.). But what would the difference between Aleph numbers and ordinals be, then?
The aleph numbers are "caridnals" in the sense that they refer to a *quantity*. E.g., aleph_0 is the size of the set of natural numbers. On the other hand, ordinals refer to *order type*. E.g., omega is the order type of the natural numbers (where natural numbers are ordered in the obvious way), while omega+1 is the order type of the natural numbers with some new element that is bigger than all natural numbers added in.
@@SheafificationOfG ohhh, I _think_ I got it. Never actually seen of the term "order type", and the Wikipedia article on that seems to paint a really different picture of the ordinals from the one I've got from your explanations, but maybe that's just me... So one thing I've come to hypothesise is that for example, both of these concepts show that reals are, for the lack of a better way to phrase this, Very Different from integers - once in the Aleph sense, since you can't map all the reals to all the integers (there isn't enough of the latter), and once in the ordinals sense, since their order types differ. Unsure whether this is a meaningful observation, but in any case, thanks for answering! I'll keep watching your videos to hopefully deepen my understanding...
What I mean is that what I've just read about order types seems to match what you say in your comment, but I haven't (yet?) seen this connection between ordinals and order types in the videos
@pmmeurcatpics the cardinality of the real numbers is certainly a beast (cf. the continuum hypothesis). On the other hand, the order type of the reals doesn't correspond to any ordinal. One thing I didn't stress in my comment is that ordinals correspond to *well-orders* (in that every nonempty set has a minimum). What's interesting about ordinals is that the class of all ordinals is also well-ordered! While I never really stressed that ordinals correspond to well-order-types (only in passing in the first video in this mini-series), I use the well-orderedness of all ordinals extensively. Not sure if this really addresses your questions, but I hope this is helpful!
This is why I feel like infinity should be explored as a reflection of zero; You cant reach infinity by counting up from zero, but you can get finitely closer (that is to say, finitely further from zero); let’s say you similarly can’t reach zero by counting down from infinity, but you also can get finitely closer (that is to say, finitely further from infinity, such as infinity minus one) This probably makes more sense in the context of uncountable infinities, such as counting every number between 0 to 1 Let’s say that starting from zero, we then count the smallest non-zero sum as 0&1 , then the second smallest sum being 0&2, so on. You don’t reach one within a finite amount of steps, but I think it would be fair to say that by the time you’re ’halfway done’, you’ll have reached 0.5
Also, maybe we should think of Omega like an infinite chess board: if you moving x spaces prolongs the game by x turns, then if you have a rook or something, the turn timer becomes omega, then as soon as you move your rook, you basically “define” omega minus one to be whatever spot you moved to. Similarly, if we had two rooks in the same column at opposite ends of the chess board (uncountable far away), they can get finitely closer to each other, but never reach each other. Capture isn’t allowed here unless we change the rules to allow you to “snap to the target” We can define one rook as being at space 0, and the other as being at space ∞, and they can get closer, reaching spaces like 0+87,527 (AKA 87,527) and ∞-64
@@SheafificationOfG Idk (It's a good meme though). I guess something like proving induction is sound for natural numbers as we know them, or a similar philosophical meme along those lines
So are infinite ordinals just a vector space with a linear ordering? ((aω + b) ≤ (cω + d)) ⟺ ((a < c) or (a = c and b ≤ d))? I guess it's not really a vector space, it's an algebra-like-thing over a ring-like-thing (ℕ). And infinite-dimensional, too. Nasty.
Ordinals definitely don't define a vector space. Their algebraic structure is quite different from what you might expect, too. For example, there's a reason I keep the finite factors in a product on the right: omega*2 = omega + omega, but 2*omega = omega.
If you have, say, 1,000,000^1,000,000 at some step, and in the next step you break it and have to decrease the exponent, that exponent will no longer increase with each step. Easy way to think of it.
Hmm i wonder if you have to use infinities though. Like for this problem, if i follow what happens to 2, the idea seems to be that at one point the base exceeds the number after which the operation of replacing base b with base b+1 doesnt change the representation of the number. That is when the -1 really comes into play. I dont have an argument yet as to when or why this cross over would happen. But i think using infinites isnt really illuminating for this problem. It kind of obscures the reasoning. For that reason i dont feel like this is a fair example of a proof with infinities. Do u have any other examples? Apart from calculus ofcourse.
You should check out the paper by Kirby and Paris; making the intuition of the first half of the video precise is (in some sense) impossible to do using the language of natural numbers! More precisely, Goodstein's Theorem is not provable using first order Peano arithmetic, so we have to use ordinals (or something of equal expressive strength) to prove that all of these sequences eventually go to zero!
@@SheafificationOfG Huh, so when u say tha tfirst order peano axioms are not sufficient, you mean that all operations we do on natural numbers? Like base expansion, addition, multiplication, subtracton, exponentiation, etc? Hmm that is really weird.
Wait a minute. w is the smallest ordinal bigger than any finite number, so w-1 must be finite. But after any finite number, there is another finite number, like (w-1)+1. But it is equal to w. So w must be finite. But w is bigger than anything finite, and it can't be bigger than itself since it is equal to itself. So w mustn't exist. The only way to deal with it is axiomatically, what is the axiom that allows this? Is there an axiom like "there is a finite amount of natural numbers"?
I hope this helps: omega is the smallest ordinal bigger than any finite ordinal, so omega - 1 must be finite *if it exists*. In other words: IF there is an ordinal alpha such that alpha + 1 = omega, then [by the argument you summarised] omega would have to satisfy omega < omega, which is nonsense. By contradiction, we reject the premise, but t he premise is *not* that omega exists; the premise is that *alpha* exists... and therefore alpha (i.e., "omega - 1") doesn't exist. The existence of omega itself is fine (it's the order type of the natural numbers).
@@SheafificationOfG But at 6:20 next turn is 1 less then the previous one, shouldn't we be able to subtract 1 from w in order for this to work? How else did we get w³•3+w²•3+w•3+3 from w^w?
Right, we're not actually subtracting one from the ordinal shape directly! Rather, we're subtracting one from the corresponding finite number! Rather than subtracting 1 from w^w, we are subtracting 1 from something like 3^3, which gives 3^2*2 + 3*2 + 2 (and the shape of that is w^2*2 + w*2 + 2).
The proof you used that there is no infinite descending sequence relies on transfinite induction, but transfinite induction only works because there's no infinite descending sequence. You can't really prove it though. It's just part of the definition of ordinals.
You're right (as was mentioned by someone else, too), but since the result is pretty counterintuitive the first time you see it, I figured it wouldn't hurt to "demonstrate" it instead of just going with a "trust me; it's by definition!" In hindsight, maybe a more direct argument from well-foundedness would've been more appropriate, but what's done is done!
This is a nonsense comment. All mathematical theorems are true by definition. He was illustrating how the basic definition that omega is the smallest ordinal greater than all finite ordinals implies that all decreasing sequences of ordinals must terminate.
@@MichaelDarrow-tr1mn the theorems use the definition of the axioms to be true by definition themselves. You prove a theorem by taking the definition of the axiom and showing that the axiom being true requires the theorem to also be true. So by the definition of the axiom, the theorem is also true, hence the "true by definition". Also, ordinals being well ordered is required because they are well-ordered which how all nonempty subsets have a smallest element. what this means is that its required that as you start at any element, there is some subset of all elments less than that element, and this subset must terminate somewhere because it is a nonempty subset of the main set. this *requires* that given the set of infinite ordinals, there must be some smallest element which is omega. By the definition of there being infinite ordinals, it is required that all descending series of ordinals terminate somewhere by the reasoning given in the video.
We can prove it by using the well-ordering property for ordinals, which is a consequence of the set-theoretic definition of ordinals and the same property for sets, which is a consequence of the axiom of choice. I suppose you're partially right.
Nowadays it's because I'm no longer studying there (but before that, it was because of budget cuts, so grad students didn't get many teaching opportunities).
honestly your explanation is way more confusing than it needs to be. Here's how I thought it through: First, I couldn't understand what a pure base was so I had to go back. What I realized about them was that pure base representations have the property that all constants in the expression are less than or equal to the base itself. Only the numbers that are actually equal to the base itself are actually increasing during this. Just at 4:04, it's completely clear what's going on. The constants and coefficients(every number other than the base B) are strictly decreasing, and what that means is that eventually you'll run out. You don't need to spend 15 minutes descending into ordinal bullshit to illustrate that. I get that's the point of the video but it actually makes it harder to understand. The way you explained it is actually so bizarre that you made me second-guess that I even understood what was going on in the first place until I realized that you unironically spent 15 minutes explaining that regardless of the base increasing each iteration, everything that's not the base is constantly decreasing, and when the stuff that's not the base runs out, the the parts that include the base have to decrease to "refill", and then the base itself must eventually run out too since it needs to be depleted to replenish the constants
... if you can formalize your argument in Peano arithmetic (which it appears you're essentially trying to do), then it is wrong. (it's not a proof to look at the sequences and notice the pattern of decreasing constants. how do you know this pattern continues forever? for instance, in the sequence for 5, the third term has a sudden • 3. why couldn't this happen later in the sequence too?)
I want to build on @myca9322's comment. You have the right idea about the general approach (there is some sense in which the "shape" of a pure base-b expansion decreases as you progress along any Goodstein sequence). However, the devil's in the details: how do we make your argument precise? These shapes can be quite elaborate due to their highly recursive nature, so how do we accurately "measure" a shape's complexity (so that, in particular, we can say that successive terms of the Goodstein sequence are less and less complex)? As you say, the shape is really a kind of formal expression (where the base is replaced by some abstract symbol "b"), and a rough heuristic about complexity is "if the constants are smaller, the shape is less complex". However, we need to be more careful: the shape b^{b + 1} is "more complex" than b^{b*100} + b*1000, as you're probably already aware. But if we want to *prove* Goodstein's theorem, we need to spell out an actual way of comparing two of these "shapes" appropriately! Let's look at the shape "b" by itself (e.g., the shape of 5 in base 5). This shape is more complex than constants, so "b > 0", "b > 1", "b > 2", ... and so on. Inevitably, this makes "b" some kind of analogue of omega, even if you were trying to avoid infinite ordinals. Similarly, trying to explain the complexity of expressions like "b * 5" or "b^2" or "b^b" will inevitably lead to analogues of ordinal arithmetic in the same sense. Finally, there's one more question: why do these shapes that "decrease in complexity" *actually* run out? There are infinitely many shapes that are "less" complex than b^b (for example, b, b^2, b^3, b^4, b^5, ... are all less complex than b^b), so at least something needs to be said about this, too. As other comments remark, the finiteness of any decreasing sequence is automatic if we use ordinals; however, if you avoid ordinals, you would have to prove the inevitable finiteness of these decreasing-complexity sequences by structural induction on your shape! In any case, you'll find that formalising your proof may very well put you back in the position of the proof in this video. That's not to say that ordinals are the *only* way to do this (as you can use other recursive structures, such as tree-like structures), but a result of Kirby and Paris ensures that any proof is going to be as "strong" (in a proof-theoretic sense) as one using infinite ordinals.
@@myca9322 Did you actually read my comment or were you just yapping? the sudden 3 is because on the third iteration, it goes from 3^3 to 4^4 - 1, but we can't have negatives in pure base notation, so we need to break the 4^4 into 4^3 * 3 +..... This is *literally* the base being depleted like I was talking about. the 4^4 had to have its exponent turned into a 3(which will no longer grow) in order to replenish the +3 you talked about. eventually the +3 is depleted, and then the 7 * 3 must have its constant depleted when it becomes 8 * 3 - 1 and become 8 * 2 + 7 to replenish the standalone constant. formally, each -1 eats away at every term that doesn't include the base, until the base itself needs to be depleted.
@@SheafificationOfG okay. there are no negative digits in any ordinary base. any pure base representation has some term which corresponds to B^0 * N where N is strictly less than B. At 4:04 in the video, N is 1, 0, 3, 2, 1, 0, 7, 6, 5, 4, 3. What we'll notice that on each iteration, this value is unaffected by the B increases by 1 each time. This is because N is strictly less than B at all times. What we'll notice is that when N reaches 0 as in the 3rd and 7th iterations, on the very next iteration, it *would* become negative because this part of the value is unaffected by the increasing nature of our series. However, there is no such thing as a negative representation, so we must find the B^1*M term. this corresponds to 7 * 3 in iteration number 7. When we increase B and subtract 1, part of our equation must then be B^1 * M - 1, as M is strictly less than B. To reconcile, we must turn this into B^1 * (M-1) + B^0 * (B - 1). Notice that our coefficient associated with the B^0 term is strictly less than B and will no longer increase. Our B^1 coefficient will also not increase. On our next iteration, our B^0 coefficient has been frozen in place and will eventually be depleted because its a descending series of finite ordinals. Once that coefficient reaches 0, we run into the same problem where we must then do B^1 * (M-1) then becomes B^1 * (M-1) - 1, and to reconcile the fact that we cannot have a negative constant, we must break open the B^1 * (M-1) into B^1 * (M-2) + (B-1). This continues until the B^1 coefficient, denoted as M will also reach 0 because its a descending series of ordinals. Then we have to break open the B^2 thing. I hope that you see that this term's coefficient is also going to eventually reach 0 for the same reasons as listed above. Then, we must do B^3, and so on until we either run out or reach a special B^K term where K is greater than or equal to B. If we have no B^K term, it's pretty obvious through induction that our series will terminate just because all coefficients are decreasing and there are finitely many exponents that can be applied to B. Our inductive reasoning will eventually work its way through and deplete evry single exponent. If we have a B^K term, we know that K itself is some ordinal and even if its increasing, its only finite, and its composed of some assortment of Bs and constants strictly less than B as per our pure base requirement. The parts strictly less than B will decrease once all terms besides the B^K term are depleted in order to replenish them. Once all the constants strictly less than B are also depleted, the parts that include B must be depleted themselves. This will continue until K is less than B, and then all our previous induction will apply. This explanation is very similar to your infinite ordinal explanation but in my opinion, all this talk about shape and complexity ends up obfuscating away from the point to the point that its not even clear what you're talking about. I'm not saying that you're wrong, just that your explanation is very confusing and unnecessarily wordy whereas I think that the one I've presented here is something that could be explained in only a minute or two given visuals. Basically, our goodstein increasing of the base only affects the total quantity, but not the number of terms. The number of terms must eventually reach 0 because the -1 affects constants which are not affected by the goodstein increasing, and each time that these constants are depleted, the number of terms must come closer to decreasing, until it does, and it eats away the entire value.
@ethos8863 while your explanation works for a specific example, the issue is when trying to handle the theorem in full generality. The intuition is right, like I said, but the ordinals (or some equally powerful substitute) is necessary to explain why your intuitive process works (or even makes sense). Like was mentioned earlier, Goodstein's theorem is undecidable in first order Peano arithmetic, so an argument purely in terms of natural numbers is, in some weak sense, impossible. I would recommend consulting the paper by Kirby and Paris (or starting a discussion on this somewhere like MathStackExchange) where you might be able to get more insight about the matter. I won't say my explanation is the best or cleanest, but delving into ordinals is necessary for a complete argument. Anyway, I hope this is somewhat helpful, and I'm glad you've engaged critically with the content, and I hope you can find a satisfactory explanation elsewhere if not here 🙂
9:49 you can't be talking seriously, wtf like if a1 is some finite number, then a0 should be the next one, instead of omega? i see how a0 couldn't because it was DEFINED to be omega, but man give me a break i actually kinda like how we just ignore a search for truth and just use overpowered paradoxical machinery to prove normal theorems, it's like going to the past to clean the dishes while the faucet water wasn't freezing
He already gave an example of what would happen in that case. He first started off by giving an example of a_0 being a finite number and then a_1 being 1 less than it. Obviously, this would result in a finite sequence. What's more interesting is if a_0 had been an infinite ordinal. We already know that any descending sequence of finite ordinals is going to be finite.
> i actually kinda like how we just ignore a search for truth and just use overpowered paradoxical machinery to prove normal theorems ahh but you see mathematics isn't about the search for truth. Its about the discovery and use of semantic constructions of objects and documenting the properties those objects have in relation to each other. Truth is but a particular type of pattern in certain contexts of semantic objects! (i think)
