4 ms·

I love these anecdotes. Just an aside, but I was under the impression that Set Theory (these days) is regarded as not-necessarily-all-that-well-founded or, per

I love these anecdotes. Just an aside, but I was under the impression that Set Theory (these days) is regarded as not-necessarily-all-that-well-founded or, perhaps, not ideal for "foundations"? Is that hopelessly misguided? If it isn't already apparent, I'm pretty much a noob in formal verification, but I've read enough to hopefully have a very shallow understanding...?!? EDIT: I just thought I'd add what "makes math beautiful" for me: The mere difficulty of defining equality of 'things' and deciding what it should mean.

jtc1983 9y ago
Use of the phrase "not-necessarily-all-that-well-founded" is unfortunate since standard set theory studies the properties of extensional, well-founded objects in general. Though clearly you didn't have the technical understanding of well-foundedness in mind. Just might confuse ppl because there is a branch of set theory called "non-well-founded set theory" that is perfectly respectable -- I.e., and "well-founded" in the sense you intend -- but not about the same objects studied in the standard context. I believe what you have in mind regarding set theory as "not ideal for 'foundations'" (why is the word foundations in quote, btw?) is that there is a recent push to reexamine the prospects more intensional foundations based on type theory. The most promising and currently fashionable version of this push is Homotopy Type Theory (HoTT), which has been given press and prestige from the IAS at Princeton and interest from Fields Medalist Vladimir Vovodsky (sp?). There are plausible reasons given, though often polemical, for preferring some sort of type theoretical or category theoretical foundations over set theoretical ones. Perhaps most importantly, for readers of HN, the comparatively easy formalization into computer-checkable proof and computer-assisted proof (look up, for instance, Coq). That said, there is a long way to go before HoTT (or something like it) displaces traditional foundations and set theory. For one thing, there is no obvious axiomatization or way to confirm that HoTT is a suitable foundation for extant non-foundational mathematics. For one thing, standard type theory (MLTT) plus Vovodsky's univalence axiom is proof-theoretically equivalent to a subsystem of analysis. I would guess that, for instance, you can't prove that all Borel sets are measurable using MLTT plus univalence (but this is totally speculative and I would appreciate being corrected). Last -- I suspect the only mathematicians who find set theory proofs beautiful are set theorists. Most other mathematicians don't really give af about set theory.
- lomnakkus 9y ago
  Ok, I'm clearly lacking in fundamentals here. I've seen HoTT seem receiving quite a bit of attention, but after reading a few papers and texts it seems that it's just out of reach without additional introductory material. I got about 50% though TAPL, if that's any indication of (my lack of) sophistication in type theory. I really should pick that up... Any recommendations for introductory texts? As a practical matter, what do the mathematicians who don't give AF about set theory (as you say) do? Just assume other axioms that "do enough" adn then go from there?
  - jtc1983 9y ago
    Looking at TAPL, it seems like a good text coming at things from the theoretical computer science angle. I'm unsure how exactly to branch out from there, since my own background is more in math logic. So prob best to take my recommendations with that in mind (I think there's a ton of work in CS in the last 20 years that I'm just totally unfamiliar with). You could check out Lambek and Scott (1970s), which is excellent. Also Girard (citation for this one was in TAPL). I also think Martin Lof himself is pretty good for the feel of things, but he has always seemed kind of cryptic and mystical to me. There are also some good videos on YouTube that Steve Awodey (CMU) recorded for more intro/motivation. I'd also add Vovodsky's three Bernays lectures on YouTube for the general idea of using typed lambda calculus vs set theory as foundations. Sociologically, my impression is that most mathematicians trust that the usual axioms of set theory are consistent and safely ignore them. So, yes -- they choose axioms in their own field that are known to be derivable in set theory. Even in intro Analysis textbooks, where the role of set theoretic axioms themselves can be pretty easily extracted from the construction of the reals, I don't think you'd see set theoretic axioms explicitly appealed to (might be wrong about this). In constructive mathematics, it ends up mattering where Choice is used I guess. And it matters how these uses can be "constructivized." But constructive analysis is primarily motivated by foundational considerations. So it is not really an example of ordinary mathematics. Some axioms, like Regularity, are almost never even implicitly used outside of set theory itself except in very specific cases. Most every case where there is a question of whether a given bit of mathematics is derivable from the usual axioms of set theory arise only within set theory itself (CH, measurability of projective sets of reals, etc), and so such questions are easy to ignore for the vast majority of mathematicians. They simply don't care that much about logic and set theory aside from "just working" under the hood, as it were.
Animats 9y ago
Equality should at least have the property that ∀ f, x = y ⇒ f(x) = f(y) In a constructive theory like Boyer-Moore, all variables have a concrete representation, and functions can look into that representation. Thus, for EQUAL to have the property above, the representation must be the same. In Boyer-Moore theory, there's no "hiding", in the sense of an object with private members. One could define a "weak equality" for sets which were lists of values, true if the same values were in both lists. Weak equality would not require that the lists have the same order. But you couldn't hide the representation. Functions could peek into the list representation, and the property above would not hold. So "weak equality" would not be very useful in proofs. I once proposed a sort of "object oriented" extension to Boyer-Moore theory. The idea is that you create something like a set represented by lists, prove some theorems about such objects, and then "hide" the private functions that can look into the interior of the representation. Then you can define a weak equality function p. If you can prove ∀ f, p(x,y) ⇒ f(x) = f(y) for every non-hidden function, you have proven that p(x,y) ⇒ x = y. Then, p can be treated as equality. Proving this requires proving it for every function already defined. Any newly defined functions are composed from existing functions, so the equality still holds. There's trouble with newly defined types, though, because they come with some built-in functions such as the type predicate. If you pursue this, you probably get to some theory of types, but I didn't want to go there, so I gave this up.
- eru 9y ago
  I think the type system along Haskell's lines can give you something like that? (Or go all the way to Agda, Idris, Coq etc.)
- lomnakkus 9y ago
  > Equality should at least have the property that ∀ f, x = y ⇒ f(x) = f(y) My impression was that even that might be a bit contentious[1]. Well, maybe not contentious, but maybe... disputable? It also requires a theory of functions, or at least a syntax to derivation rules. That was just to be absurdly nitpicky, I think I understand what you're saying here, and it's much appreciated. [1] https://pdfs.semanticscholar.org/806a/92153c4b8d344edec45eece4ba105afd3dda.pdf https://pdfs.semanticscholar.org/806a/92153c4b8d344edec45eec...

jtc1983 9y ago

Use of the phrase "not-necessarily-all-that-well-founded" is unfortunate since standard set theory studies the properties of extensional, well-founded objects in general. Though clearly you didn't have the technical understanding of well-foundedness in mind. Just might confuse ppl because there is a branch of set theory called "non-well-founded set theory" that is perfectly respectable -- I.e., and "well-founded" in the sense you intend -- but not about the same objects studied in the standard context. I believe what you have in mind regarding set theory as "not ideal for 'foundations'" (why is the word foundations in quote, btw?) is that there is a recent push to reexamine the prospects more intensional foundations based on type theory. The most promising and currently fashionable version of this push is Homotopy Type Theory (HoTT), which has been given press and prestige from the IAS at Princeton and interest from Fields Medalist Vladimir Vovodsky (sp?). There are plausible reasons given, though often polemical, for preferring some sort of type theoretical or category theoretical foundations over set theoretical ones. Perhaps most importantly, for readers of HN, the comparatively easy formalization into computer-checkable proof and computer-assisted proof (look up, for instance, Coq). That said, there is a long way to go before HoTT (or something like it) displaces traditional foundations and set theory. For one thing, there is no obvious axiomatization or way to confirm that HoTT is a suitable foundation for extant non-foundational mathematics. For one thing, standard type theory (MLTT) plus Vovodsky's univalence axiom is proof-theoretically equivalent to a subsystem of analysis. I would guess that, for instance, you can't prove that all Borel sets are measurable using MLTT plus univalence (but this is totally speculative and I would appreciate being corrected). Last -- I suspect the only mathematicians who find set theory proofs beautiful are set theorists. Most other mathematicians don't really give af about set theory.

lomnakkus 9y ago
Ok, I'm clearly lacking in fundamentals here. I've seen HoTT seem receiving quite a bit of attention, but after reading a few papers and texts it seems that it's just out of reach without additional introductory material. I got about 50% though TAPL, if that's any indication of (my lack of) sophistication in type theory. I really should pick that up... Any recommendations for introductory texts? As a practical matter, what do the mathematicians who don't give AF about set theory (as you say) do? Just assume other axioms that "do enough" adn then go from there?
- jtc1983 9y ago
  Looking at TAPL, it seems like a good text coming at things from the theoretical computer science angle. I'm unsure how exactly to branch out from there, since my own background is more in math logic. So prob best to take my recommendations with that in mind (I think there's a ton of work in CS in the last 20 years that I'm just totally unfamiliar with). You could check out Lambek and Scott (1970s), which is excellent. Also Girard (citation for this one was in TAPL). I also think Martin Lof himself is pretty good for the feel of things, but he has always seemed kind of cryptic and mystical to me. There are also some good videos on YouTube that Steve Awodey (CMU) recorded for more intro/motivation. I'd also add Vovodsky's three Bernays lectures on YouTube for the general idea of using typed lambda calculus vs set theory as foundations. Sociologically, my impression is that most mathematicians trust that the usual axioms of set theory are consistent and safely ignore them. So, yes -- they choose axioms in their own field that are known to be derivable in set theory. Even in intro Analysis textbooks, where the role of set theoretic axioms themselves can be pretty easily extracted from the construction of the reals, I don't think you'd see set theoretic axioms explicitly appealed to (might be wrong about this). In constructive mathematics, it ends up mattering where Choice is used I guess. And it matters how these uses can be "constructivized." But constructive analysis is primarily motivated by foundational considerations. So it is not really an example of ordinary mathematics. Some axioms, like Regularity, are almost never even implicitly used outside of set theory itself except in very specific cases. Most every case where there is a question of whether a given bit of mathematics is derivable from the usual axioms of set theory arise only within set theory itself (CH, measurability of projective sets of reals, etc), and so such questions are easy to ignore for the vast majority of mathematicians. They simply don't care that much about logic and set theory aside from "just working" under the hood, as it were.

Animats 9y ago

Equality should at least have the property that ∀ f, x = y ⇒ f(x) = f(y) In a constructive theory like Boyer-Moore, all variables have a concrete representation, and functions can look into that representation. Thus, for EQUAL to have the property above, the representation must be the same. In Boyer-Moore theory, there's no "hiding", in the sense of an object with private members. One could define a "weak equality" for sets which were lists of values, true if the same values were in both lists. Weak equality would not require that the lists have the same order. But you couldn't hide the representation. Functions could peek into the list representation, and the property above would not hold. So "weak equality" would not be very useful in proofs. I once proposed a sort of "object oriented" extension to Boyer-Moore theory. The idea is that you create something like a set represented by lists, prove some theorems about such objects, and then "hide" the private functions that can look into the interior of the representation. Then you can define a weak equality function p. If you can prove ∀ f, p(x,y) ⇒ f(x) = f(y) for every non-hidden function, you have proven that p(x,y) ⇒ x = y. Then, p can be treated as equality. Proving this requires proving it for every function already defined. Any newly defined functions are composed from existing functions, so the equality still holds. There's trouble with newly defined types, though, because they come with some built-in functions such as the type predicate. If you pursue this, you probably get to some theory of types, but I didn't want to go there, so I gave this up.

eru 9y ago
I think the type system along Haskell's lines can give you something like that? (Or go all the way to Agda, Idris, Coq etc.)
lomnakkus 9y ago
> Equality should at least have the property that ∀ f, x = y ⇒ f(x) = f(y) My impression was that even that might be a bit contentious[1]. Well, maybe not contentious, but maybe... disputable? It also requires a theory of functions, or at least a syntax to derivation rules. That was just to be absurdly nitpicky, I think I understand what you're saying here, and it's much appreciated. [1] https://pdfs.semanticscholar.org/806a/92153c4b8d344edec45eece4ba105afd3dda.pdf https://pdfs.semanticscholar.org/806a/92153c4b8d344edec45eec...