TREE vs. Graham’s Number [video] | Hacker News Reader

TREE vs. Graham’s Number [video]

numberphile.com

58 pointseindiran29 comments

I really need a video on transfinite cardinals and ordinals beyond Aleph_0 and Epsilon_0. The VSauce video [1] on the topic only made me more curious with an elusive tree diagram displaying a few, and PBS Infinite Series [2] [3] just barely touched it. The mention of the Veblen hierarchies really piqued my interest, but much of what I've found on them has been a bit too dense for me.

1. https://www.youtube.com/watch?v=SrU9YDoXE88

2. https://www.youtube.com/watch?v=uWwUpEY4c8o

3. https://www.youtube.com/watch?v=oBOZ2WroiVY

https://www.youtube.com/watch?v=QXliQvd1vW0&list=PL3A50BB9C3...

enjoy!

https://www.youtube.com/watch?v=vq2BxAJZ4Tc is also a very good series and gets into infinite collapsing ordinals towards the end.

Thanks!

Wait wait.

Transfinite induction uses ordinals ( https://en.wikipedia.org/wiki/Large_countable_ordinal )

To get large cardinals (beyond ZFC) you need large cardinal axioms. ( https://en.wikipedia.org/wiki/List_of_large_cardinal_propert... )

There's lots of things about Graham's number, but because I love the style I thought I'd add in here Wait But Whys "from 1 to Graham's number":

https://waitbutwhy.com/2014/11/from-1-to-1000000.html

https://waitbutwhy.com/2014/11/1000000-grahams-number.html

I love numberphile, but I cannot watch a single episode, because all the zooming and panning while someone writes on a sheet of paper makes me motion sick in no time.

WHY? How does this improve the quality of the video?

It's action-math. Not meant for teaching, but for showcasing math to the general public. The general public wants action cams and cute animations.

Numberphile isn't that great if you're already interested in math. They talk a lot about math words, but they hardly ever do any math. 3Blue1Brown is where the good math is.

A shout out to Mathologer too.

It isn’t a great way to learn the details, but it’s a great way to learn about topics you might not have come across.

This video is about the hierarchy of fast-growing functions indexed by ordinals, and it includes enough details for a competent mathematician to be able to work out the rigorous general definition. For someone unfamiliar with the topic, it’s an enjoyable and low-effort way to learn enough about it to recognise whether it’s interesting enough to learn about properly.

There are several examples of cutting-edge mathematical work having been directly inspired by numberphile videos, most recently the work of Andrew Booker and Drew Sutherland on expressing integers as sums of three cubes.

3blue1brown concentrates on giving clear, elegant, rigorous explanations of established subjects. So perhaps ironically, despite being typically more rigorous, I don’t know any examples of it inspiring new mathematical research.

> There are several examples of cutting-edge mathematical work having been directly inspired by numberphile videos, most recently the work of Andrew Booker and Drew Sutherland on expressing integers as sums of three cubes.

I don't know if this is why you made this comment or not, but Brady Haran (creator of Numberphile) gave a talk on this exact topic a week ago today at the MSRI in Berkeley.

Oh, interesting! I knew Brady Haran had given a talk at MSRI, but I didn’t know what the talk was about. Was it filmed?

I don't know if it was filmed. I was there but I didn't record it.

Don't insult them because they discuss topics at a more basic level than you prefer. There's always going to be higher levels (e.g., youtuber A < youtuber B < reading a text book < taking a university course < getting a degree < conducting novel research < conducting novel research published in journal A < journal B < journal C), which may be better suited for different audiences. Landing in one versus the other doesn't make you (or the instructors) better or worse. It's silly to say that the one you happen to prefer is where "good math" is.

Let t(n, i) be a function where n is the number of recursive TREE calls and i is an integer.

So t(1,3) = TREE(3)

t(2,3) = TREE(TREE(3))

etc.

Now you can do:

t(TREE(3), 3)

t(t(t(t(t(t(t(t(t(TREE(3),3),3),3),3...)

The way TREE grows it's very much possible that all these are inferior to simply f(n) = TREE(n+1).

Unlikely since we are piping the output of TREE back into TREE, which is much larger than n+1.

https://oeis.org/A028444 would grow faster right?

does it make sense to compare the growth rates of non-computable functions?

TREE(Graham's Number) is just comically inefficient Googology. It makes me wince just to look at. Graham's Number isn't even on the same plane of existence as TREE. You'd just use TREE(TREE(3)) if you wanted to move up in the world. Somebody needs to tell them about the fast-growing hierarchy and how Graham's Number lives around \omega+1 while TREE hangs out with the small Veblen ordinal.

I have absolutely no idea what you are trying to say.

The video is mostly about asking which series, TREE or Graham, grows quicker and how we can show it.

It does this by starting out asking, which is bigger, TREE(G(64)) or G(TREE(64)).

I fail to see how that is comically inefficient or how introducing TREE(TREE(3)) is what they should have done instead.

>Somebody needs to tell them about the fast-growing hierarchy and how Graham's Number lives around \omega+1 while TREE hangs out with the small Veblen ordinal.

Somebody should watch the video before speaking out about what the video should contain.

though the video actually didn't say why TREE grows faster than the epsilon function.

That’s actually a fair point, they don’t explain why TREE grows faster than anything in the f-series.

The argument for where in the f-series Graham’s series lies is also a bit hand-wavy.

> where in the f-series Graham’s series lies

that is actually explained - fω+1(n) is grahams, because of the way grahams defines as iterated versions of up-arrows.

Is it even known why?

Maybe I'm missing something obvious here, but that's what the video is about?

The video is a basic introduction to the fast-growing hierarchy. They do state where Graham's Number sits in the hierarchy, but the explanation doesn't go as far as to say where TREE sits.

It does actually. It says it grows faster than anything in the hierarchy.

Faster than anything in the Wainer hierarchy (which ends at $f_{\epsilon_{0}}(n)$. But it's reasonably easy to define a fast-growing hierarchy that uses the Veblen hierarchy of ordinals for the subscripts. Then TREE is $f_{svo}(n)$ where $svo$ is the limit of the finitary veblen sequence as the number of elements goes to $\omega$ (aka the small veblen ordinal).

Reply on news.ycombinator.com