News for hackers. Stuff that matters.
Re:A New Bridge Links the Math of Infinity to Computer Science by k_bx on Tuesday November 25, 2025 @04:52PM (#46051236)
> All of modern mathematics is built on the foundation of set theory, the study of how to organize abstract collections of objects

What the hell. What about Type Theory?

Re:A New Bridge Links the Math of Infinity to Computer Science by philipfweiss on Tuesday November 25, 2025 @05:50PM (#46051808)
Type theory is actually a stronger axiomatic system than ZFC, and is equiconsistent with ZFC+ a stronger condition.

See this mathoverflow response here https://mathoverflow.net/a/437200/477593

Re:A New Bridge Links the Math of Infinity to Computer Science by creata on Tuesday November 25, 2025 @11:35PM (#46054230)
> Type theory is actually a stronger axiomatic system than ZFC

I'm stating the obvious, but it depends which type theory.

Re:A New Bridge Links the Math of Infinity to Computer Science by BalinKing on Wednesday November 26, 2025 @12:23AM (#46054443)
To echo the sibling comment, that answer is specifically referring to the type theory behind Lean (which I’ve heard is pretty weird in a lot of ways, albeit usually in service of usability). Many type theories are weaker than ZFC, or even ZF, at least if I correctly skimmed https://proofassistants.stackexchange.com/a/1210/7.
Re:A New Bridge Links the Math of Infinity to Computer Science by zozbot234 on Tuesday November 25, 2025 @06:51PM (#46052318)
Regardless of the name, descriptive set theory does not seem to have all that much to do with "set theory" in a foundational sense; it can be recast in terms of types and spaces with comparative ease, and this can be quite advantageous. The article is a bit confusing in many ways; among other things, it seems quite obviously wrong to suggest that recasting a concept that seems to be conventionally related to mathematical "infinities" in more tangible computational terms is something deeply original to this particular work; if anything, it happens literally all the time when trying to understand existing math in type-theoretic or constructive terms.
Re:A New Bridge Links the Math of Infinity to Computer Science by rdlw on Tuesday November 25, 2025 @04:58PM (#46051291)
Is there a collection of type theory axioms anywhere near as influential as ZF or ZFC?
Re:A New Bridge Links the Math of Infinity to Computer Science by k_bx on Tuesday November 25, 2025 @05:10PM (#46051415)
Sure, but is discarding Type Theory and Category Theory really fair with a phrase like "All of modern mathematics"? Especially in terms of a connection with computer science.
Re:A New Bridge Links the Math of Infinity to Computer Science by anon291 on Tuesday November 25, 2025 @07:56PM (#46052839)
Arguably, type theory is more influential, as it seems to me all the attempts to actually formalize the hand-wavy woo mathematicians tend to engage in are in lean, coq, or the like. We've pretty much given up on set theory except to prove things to ourselves. However, these methods are notoriously unreliable.
Re:A New Bridge Links the Math of Infinity to Computer Science by umanwizard on Tuesday November 25, 2025 @04:55PM (#46051255)
"the study of how to organize abstract collections of objects" is not really a great explanation of set theory. But it is true that the usual way (surely not the only way) to formalize mathematics is starting with set-theoretic axioms and then defining everything in terms of sets.
Re:A New Bridge Links the Math of Infinity to Computer Science by k_bx on Tuesday November 25, 2025 @05:12PM (#46051440)
"Usual", "most common by far" etc. are all great phrases, but not "all of mathematics", esp when we talk about math related to computer science
Re:A New Bridge Links the Math of Infinity to Computer Science by umanwizard on Tuesday November 25, 2025 @05:26PM (#46051562)
Math related to CS is typically formalized starting with set theory, just like other branches of math.
Re:A New Bridge Links the Math of Infinity to Computer Science by A_D_E_P_T on Tuesday November 25, 2025 @06:09PM (#46051948)
What's important to note is that this is just a matter of convention. An historical accident. It is by no means a law of nature that math need be formalized with ZFC or any other set theory derivative, and there are usually other options.

As a matter of fact, ZFC fits CS quite poorly.

In ZFC, everything is a set. The number 2 is a set. A function is a set of ordered pairs. An ordered pair is a set of sets.

In ZFC: It is a valid mathematical question to ask, "Is the number 3 an element of the number 5?" (In the standard definition of ordinals, the answer is yes).

In CS: This is a "type error." A programmer necessarily thinks of an integer as distinct from a string or a list. Asking if an integer is "inside" another integer is nonsense in the context of writing software.

For a computer scientist, Type Theory is a much more natural foundation than Set Theory. Type Theory enforces boundaries between different kinds of objects, just like a compiler does.

But, in any case, that ZFC is "typical" is an accident of history, and whether or not it's appropriate at all is debatable.

Re:A New Bridge Links the Math of Infinity to Computer Science by jltsiren on Tuesday November 25, 2025 @06:46PM (#46052265)
In CS, types are usually a higher level of abstraction built on top of more fundamental layers. If you choose to break the abstraction, you can definitely use an integer as a string, a list, or a function. The outcome is unlikely to be useful, unless your construct was designed with such hacks in mind.

When I did a PhD in theoretical computer science, type theory felt like one niche topic among many. It was certainly of interest to some subfield, but most people didn't find it particularly relevant to the kind of TCS they were doing.

Re:A New Bridge Links the Math of Infinity to Computer Science by umanwizard on Tuesday November 25, 2025 @07:16PM (#46052555)
Sure, but it fits the rest of mathematics "poorly" for exactly the same reasons. No working mathematician is thinking about 3 as an element of 5.

The reason ZFC is used isn't because it's a particularly pedagogical way of describing any branch of math (whether CS or otherwise), but because the axioms are elegantly minimal and parsimonious.

Re:A New Bridge Links the Math of Infinity to Computer Science by k_bx on Wednesday November 26, 2025 @12:27PM (#46059954)
Sorry but if you try to prove 2+2=4 in ZFC versus Type Theory (HoTT-style) – nothing looks elegant about ZFC afterwards.
Re:A New Bridge Links the Math of Infinity to Computer Science by nathias on Tuesday November 25, 2025 @05:19PM (#46051505)
the empirical modern mathematics are build on set theory, type and category theory are just other possible foundations
Re:A New Bridge Links the Math of Infinity to Computer Science by A_D_E_P_T on Tuesday November 25, 2025 @05:38PM (#46051703)
Most modern mathematicians are not set theorists. There are certain specialists in metamathematics and the foundations of mathematics who hold that set theory is the proper foundation -- thus that most mathematical structures are rooted in set theory, and can be expressed as extensions of set theory -- but this is by no means a unanimous view! It's quite new, and quite heavily contested.
Re:A New Bridge Links the Math of Infinity to Computer Science by nathias on Wednesday November 26, 2025 @07:43AM (#46056866)
yes of course, I just mean that from the set of foundational mathematics, set theory is the strongest one empirically, but that there are other options (possibly better)
Re:A New Bridge Links the Math of Infinity to Computer Science by housecarpenter on Wednesday November 26, 2025 @08:48AM (#46057360)
My impression (as a dilettante programmer without relevant credentials) is that there isn't really any question about whether mathematical structures can be rooted in set theory, or can be expressed as extensions of set theory. Disputes about foundations of mathematics are more about how easy or elegant it is to do so. (And in fact my impression is they're mostly about subjective, aesthetic considerations of elegance rather than practical considerations of how hard it is to do something in practice, even though the discussion tends to be nominally about the practical side. Quite similar to disputes about programming languages in that respect.)