Rendered at 23:42:41 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
gregfjohnson 1 hours ago [-]
Joel Hamkins is my new favorite mathematician :-)
There is a beautiful application of the power set of the Naturals to denotational semantics. I assume Prof. Hamkins's book will cover that topic, but it is not mentioned in the linked article.
Dana Scott (and apparently Gordon Plotkin independently) came up with a clever way to create a model of the lambda calculus that employs the power set of the Naturals.
The problem is that in lambda calculus, the formal language permits every expression to appear in the left-hand slot of the "Function_Application" operator. I.e., every term is simultaneously permitted to be given as an argument to a function, and also to be used as a function.
So we have the conundrum of finding some set "S" where every element of S is a function (not a problem so far), BUT, those functions all take elements of S as inputs and produce elements of S as outputs. So we need a set S that is isomorphic to the set of functions "S -> S". Cardinality arguments show that this is not possible: the function space for any non-trivial set has greater cardinality than the set itself.
So, Scott and Plotkin devised a "computationally sensible" way to interpret an arbitrary set of integers as a function over sets of integers.
By standard encodings, interpret any integer "n" as an ordered pair "<M,u>". Now, again via standard encoding, interpret M as a finite set of integers M_set.
The "function" defined by a singleton set { n } applied to some other set Q is:
{u} if M_set is a subset of Q, Empty_set otherwise.
Then for a set of more than one element, take the union of the outputs of each of the elements applied to Q as above.
One can define a topology over the power set of the Naturals, and the above functions turn out to be exactly the continuous functions relative to that topology. The continuous functions so defined have the same cardinality as the power set of the Naturals.
An interesting historical side-note: historically, mathematical structures were the starting point, and axiometized formal languages a la Frege, Russell & Whitehead, etc. were built later. In the case of lambda calculus, it was the other way around: the formal language came first, and it was a multi-decade riddle what actual mathematical structure (if any) this formal language actually described.
munchler 12 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 12 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 12 hours ago [-]
The visualization is of the power set, which is uncountable.
michael0church 12 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.)
aeneasmackenzie 8 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__ 8 hours ago [-]
"Fake elements," feels right to me. They're allegedly in there but we can't find any of them. It's funny that these elements comprise the majority of the "real" numbers.
zaebal 12 hours ago [-]
TREE(3) is unimaginably small, compared to ω
tromp 10 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].
Well, any natural number is unimaginably small, compared to ω …
nphardon 8 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 3 hours 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.
benmandrew 8 hours ago [-]
It's a very interesting idea; if you want to learn more about it, look up "ultrafinitism".
amavect 5 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.
d4ng 32 minutes ago [-]
There exist subsets of the natural numbers which are infinite, but which are not finitely definable in first-order arithmetic.
scythmic_waves 9 hours ago [-]
> The power set lattice (P(N)) of all sets of natural numbers, not to scale, some sets omitted...
flobosg 13 hours ago [-]
(2021)
genxy 10 hours ago [-]
math is timeless
flobosg 8 hours ago [-]
Blog entries, alas, are not.
gregw2 12 hours ago [-]
What a great visualization!
Now can your favorite LLM make me a similar one for the Real #s?
There is a beautiful application of the power set of the Naturals to denotational semantics. I assume Prof. Hamkins's book will cover that topic, but it is not mentioned in the linked article.
Dana Scott (and apparently Gordon Plotkin independently) came up with a clever way to create a model of the lambda calculus that employs the power set of the Naturals.
The problem is that in lambda calculus, the formal language permits every expression to appear in the left-hand slot of the "Function_Application" operator. I.e., every term is simultaneously permitted to be given as an argument to a function, and also to be used as a function.
So we have the conundrum of finding some set "S" where every element of S is a function (not a problem so far), BUT, those functions all take elements of S as inputs and produce elements of S as outputs. So we need a set S that is isomorphic to the set of functions "S -> S". Cardinality arguments show that this is not possible: the function space for any non-trivial set has greater cardinality than the set itself.
So, Scott and Plotkin devised a "computationally sensible" way to interpret an arbitrary set of integers as a function over sets of integers.
By standard encodings, interpret any integer "n" as an ordered pair "<M,u>". Now, again via standard encoding, interpret M as a finite set of integers M_set.
The "function" defined by a singleton set { n } applied to some other set Q is: {u} if M_set is a subset of Q, Empty_set otherwise.
Then for a set of more than one element, take the union of the outputs of each of the elements applied to Q as above.
One can define a topology over the power set of the Naturals, and the above functions turn out to be exactly the continuous functions relative to that topology. The continuous functions so defined have the same cardinality as the power set of the Naturals.
An interesting historical side-note: historically, mathematical structures were the starting point, and axiometized formal languages a la Frege, Russell & Whitehead, etc. were built later. In the case of lambda calculus, it was the other way around: the formal language came first, and it was a multi-decade riddle what actual mathematical structure (if any) this formal language actually described.
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
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.
Now can your favorite LLM make me a similar one for the Real #s?