> The power set lattice (P(N)) of all sets of natural numbers, not to scale, some sets omitted...
munchler 3 hours ago [-]
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.
michael0church 3 hours ago [-]
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.
voidmain 3 hours ago [-]
The visualization is of the power set, which is uncountable.
michael0church 3 hours ago [-]
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.)
zaebal 3 hours ago [-]
TREE(3) is unimaginably small, compared to ω
tromp 2 hours ago [-]
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].
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.
[1] https://wiki.bbchallenge.org/wiki/Lambda_Calculus#Champions
Now can your favorite LLM make me a similar one for the Real #s?