What a beautiful illustration. It makes intuitive the very abstract concepts discussed in the text. It’s fun to zoom in and browse around the structure.
It’s also genuinely surprising. We’re used to thinking of the countable as the small infinity, which it is, and yet a structure we feel like we can visualize contains so much complexity.
There is also, weirdly, a way in which massive finite numbers like TREE(3) “feel” larger than N, and large countable infinities “feel” larger than w_1, even though the opposite is clearly true.
Right. But because it’s the smallest structure of its type (speaking loosely) it feels like something we should have a grasp on, even though it contains more complexity than we could ever describe or compute with (since both of those are countable.)
All describable or recognizable complexity is part of the subcountable set of computable subsets of N. Higher infinities thus mostly contain fake elements about which nothing can be said, so they don’t feel any bigger.
> The power set lattice (P(N)) of all sets of natural numbers, not to scale, some sets omitted...
What a beautiful illustration. It makes intuitive the very abstract concepts discussed in the text. It’s fun to zoom in and browse around the structure.
It’s also genuinely surprising. We’re used to thinking of the countable as the small infinity, which it is, and yet a structure we feel like we can visualize contains so much complexity.
There is also, weirdly, a way in which massive finite numbers like TREE(3) “feel” larger than N, and large countable infinities “feel” larger than w_1, even though the opposite is clearly true.
The visualization is of the power set, which is uncountable.
Right. But because it’s the smallest structure of its type (speaking loosely) it feels like something we should have a grasp on, even though it contains more complexity than we could ever describe or compute with (since both of those are countable.)
TREE(3) is unimaginably small, compared to ω
Well, any natural number is unimaginably small, compared to ω …
TREE(3) is also unimaginably tiny compared to the normal form size of (λa.aaa(λbλcλdλe.ebbbcde)aaaa)(λfλx.f(fx)) [1].
[1] https://wiki.bbchallenge.org/wiki/Lambda_Calculus#Champions
All describable or recognizable complexity is part of the subcountable set of computable subsets of N. Higher infinities thus mostly contain fake elements about which nothing can be said, so they don’t feel any bigger.
(2021)
math is timeless
Blog entries, alas, are not.
What a great visualization!
Now can your favorite LLM make me a similar one for the Real #s?
Why can't yours?
Nope.