The lattice of sets of natural numbers is rich (2021) (jdh.hamkins.org)
100 points by benmandrew 3 days ago
munchler 10 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 10 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 10 hours ago
The visualization is of the power set, which is uncountable.
michael0church 10 hours ago
aeneasmackenzie 6 hours ago
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.
__MatrixMan__ 6 hours ago
zaebal 10 hours ago
TREE(3) is unimaginably small, compared to ω
tromp 8 hours ago
zygentoma 9 hours ago
nphardon 6 hours ago
If the universe contains a finite amount of information, would that disprove the existence of an infinite set? I.e. if the representation of a number contained more information than the amount of information available in the entire universe.
layer8 41 minutes ago
You’d have to define what you mean by “existence” here. Clearly, there are infinite sets we can represent with a finite sequence of symbols. We can also imagine and reason about alternative universes with an infinite amount of information. You’d have to argue about how doing so would somehow be an incorrect thing to do.
amavect 3 hours ago
Not really. Math uses no physical observation, only axioms. Nothing can "prove" or "disprove" axioms. However, if observation supports the axiomatic theory, then we use the theory for physical prediction. If observation doesn't, then we don't use the theory. Does that count as "disproof"?
In practice, infinite sets never exist as enumerations of every element, but as ways to generate more elements along with descriptions for which elements to include. Infinite set theories allow for equivocating a finite description with the infinite enumeration. In contrast, programming languages usually make a distinction between data (always finite) and data generation (possibly infinite). I would think that counts as a "disproof" in a way.
benmandrew 6 hours ago
It's a very interesting idea; if you want to learn more about it, look up "ultrafinitism".
scythmic_waves 7 hours ago
> The power set lattice (P(N)) of all sets of natural numbers, not to scale, some sets omitted...
flobosg 11 hours ago
(2021)
genxy 8 hours ago
math is timeless
flobosg 6 hours ago
Blog entries, alas, are not.
gregw2 10 hours ago
What a great visualization!
Now can your favorite LLM make me a similar one for the Real #s?
stavros 10 hours ago
Why can't yours?
MarkusQ 7 hours ago
Nope.