The lattice of sets of natural numbers is rich (2021)

munchler 1 hour 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 1 hour 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.

zaebal 1 hour ago | | |

TREE(3) is unimaginably small, compared to ω

tromp 4 minutes 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].

[1] https://wiki.bbchallenge.org/wiki/Lambda_Calculus#Champions

zygentoma 23 minutes ago | | |

Well, any natural number is unimaginably small, compared to ω …

voidmain 1 hour ago | | |

The visualization is of the power set, which is uncountable.

michael0church 1 hour 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.)

gregw2 1 hour ago |

What a great visualization!

Now can your favorite LLM make me a similar one for the Real #s?

stavros 1 hour ago | |

Why can't yours?

flobosg 2 hours ago |

(2021)