How would set theory research be affected by using ETCS instead of ZFC? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T20:32:12Z http://mathoverflow.net/feeds/question/116701 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/116701/how-would-set-theory-research-be-affected-by-using-etcs-instead-of-zfc How would set theory research be affected by using ETCS instead of ZFC? Stxmqs 2012-12-18T13:49:35Z 2013-01-07T13:46:27Z <p>In "Rethinking Set Theory", Tom Leinster argues in favor of teaching axiomatic set theory via Lawvere's Elementary Theory of the Category of Sets with 10 axioms (but phrased in a way that requires no knowledge of category theory) which uses sets and functions as primitive elements compared to ZFC which uses sets and elements as primitives. (although if you really insist you can reintroduce elements as primitives at the expense of more clauses). This is weaker than ZFC but can be made equivalent to ZFC (or equiconsistent according to François G. Dorais) with the addition of a hardly ever needed 11th axiom.</p> <p><a href="http://golem.ph.utexas.edu/category/2012/12/rethinking_set_theory.html" rel="nofollow">http://golem.ph.utexas.edu/category/2012/12/rethinking_set_theory.html</a></p> <p>How would set theory research be affected by using ETCS instead of ZFC?</p> <p>Is ETCS less cumbersome than ZFC or more, or does it not matter? Does it make proofs longer/shorter or easier/harder?</p> <p>Would automated theorem provers work better with ETCS?</p> <p>To clarify, the question is not about the strength of ETCS: assume whatever is needed to bring ETCS up to strength with ZFC. The question is about practicalities of working with the ETCS axioms. I guess most mathematicians don't directly work with axioms of set-theory at all. So the question is: if your work does involve working directly with such axioms then what difference (if any) does it practically make to you as a set-theory researcher to use a different set of axioms that have equal strength. If I understand correctly the goal of Tom Leinster's paper was to reflect actual (non-set-theoretical)-mathematical practice but my question is about what set-theorists would do if they used these axioms. Assume also that for the purposes of this question ETCS refers specifically to the rephrasing used in this paper that is free of category and topos terminology. Perhaps this rephrasing should be renamed ETS. Adding replacement would give the name ETSR.</p> http://mathoverflow.net/questions/116701/how-would-set-theory-research-be-affected-by-using-etcs-instead-of-zfc/116705#116705 Answer by Andreas Blass for How would set theory research be affected by using ETCS instead of ZFC? Andreas Blass 2012-12-18T14:21:31Z 2012-12-18T14:21:31Z <p>Much of set theory research (for example, a paper I'm currently working on, concerning certain ultrafilters over the natural numbers) would work just fine in ETCS. But much of set theory research uses the axiom of replacement in ways that cannot be imitated in ETCS. Tom Leinster's paper gives the example of the existence of the union of $\mathbb N$, its power set $\mathcal P(\mathbb N)$, the power set of that, and so on, iterated for countably many steps. To put it another way, ETCS cannot prove that there is a cardinal number $\kappa$ with infinitely many infinite cardinals below it. Such $\kappa$'s and far larger ones are certainly involved in a great deal of research-level set theory, so a foundation having the strength of ZFC (or even more) is needed there.</p> http://mathoverflow.net/questions/116701/how-would-set-theory-research-be-affected-by-using-etcs-instead-of-zfc/116711#116711 Answer by Todd Trimble for How would set theory research be affected by using ETCS instead of ZFC? Todd Trimble 2012-12-18T14:53:53Z 2012-12-18T14:53:53Z <p>I like the fact that you asked this question, but I'm a little worried that it will be seen as "subjective and argumentative". </p> <p>For the second question, I think a lot of set theorists (trained since childhood in ZFC) have gone on record saying they do find ETCS not easy to work with or not user-friendly, and I find this quite understandable. There is a critical hump of lemmas to get over in the beginning when working with ETCS, because unlike ZFC or some variation thereof, there is no ready-made comprehension scheme in ETCS (at least as it is ordinarily presented). Rather, a stock of instances of comprehension (where one builds up an "internal logic" by hand, as it were) have to proven before one is ready to fly. But after some point, with enough of these beginning lemmas under the belt, the development of mathematics, say of the core undergraduate curriculum involving basic results of real analysis, algebra, topology, etc., proceeds pretty much the same way as what one is used to. So in that sense, I'd say "it does not matter" for the needs of working mathematicians. </p> <p>In developing his new set theory <a href="http://ncatlab.org/nlab/show/SEAR" rel="nofollow">SEAR</a> (Sets, Elements, And Relations), Mike Shulman recognized this cumbersome aspect of ETCS, quoting an analogy I made once about ETCS on the now-moribund "Todd and Vishal's blog": </p> <blockquote> <p>[Trimble] "with ZFC it’s more as if you can just hop in the car and go; with ETCS you build the car engine from smaller parts with your bare hands, but in the process you become an expert mechanic, and are not so rigidly attached to a particular make and model."</p> <p>[Shulman] Using this metaphor, SEAR can be thought of as an ETCS-car which comes preassembled with a nice slick control panel. Or, using an alternate metaphor, ZFC is like Windows, ETCS is like UNIX, and SEAR is like OS X (or maybe Ubuntu). With SEAR you get a nice familiar interface with which it is easy to do standard things, there is less cruft than you get with ZFC, and behind the scenes you have all the power of ETCS (and more). (Of course, if you like Microsoft products, then this metaphor probably does not appeal to you.) </p> </blockquote> <p>So SEAR aims to combine the advantages of ETCS (as a truly "structural" set theory, where the aspects of sets we truly care about are isomorphism-invariant, and carry less "cruft") with the advantages of ZFC (where comprehension principles, etc. are built right in; see his axiom 1). SEAR will probably look more home-y and familiar to those used to traditional naive set theory; there is none of this intimidating "well-pointed topos with NNO and choice" business to wade through at the outset. </p> http://mathoverflow.net/questions/116701/how-would-set-theory-research-be-affected-by-using-etcs-instead-of-zfc/116741#116741 Answer by David Roberts for How would set theory research be affected by using ETCS instead of ZFC? David Roberts 2012-12-18T22:58:49Z 2012-12-18T22:58:49Z <p>Well, one would just add a just strong enough instance of replacement, or the consequence one actually needs, to the assumptions of the theorem one was proving. For instance, one could take the existence of $\aleph_\omega$ as an assumption (like a large cardinal) rather than proving it exists. There are models of ETCS in which this exists and in which it doesn't. In this instance, one is just lowering the level at which one considers a cardinal 'large'.</p> <p>I'm reminded of McLarty's recent work on weak set theories, and doing algebraic geometry in them. One can prove strong results about cohomology, but can't prove the existence of an uncountable ring like $\mathbb{R}$ or $\mathbb{C}$. He says you can just simply posit the existence of such a thing on top of the weak set theory, and then all the theorems go through.</p> <p>Of course, in set theory there are a whole stack of results that rely on the strength of ZFC beyond ETCS, and it would entail a whole lot of reverse mathematical effort to find out what is <em>actually</em> necessary for swathes of theory, that many would say it is easier to just assume what ZFC gives you. But it isn't <em>strictly</em> necessary, just a lot easier.</p> http://mathoverflow.net/questions/116701/how-would-set-theory-research-be-affected-by-using-etcs-instead-of-zfc/116862#116862 Answer by Goldstern for How would set theory research be affected by using ETCS instead of ZFC? Goldstern 2012-12-20T13:10:20Z 2012-12-20T13:10:20Z <p>There are several relatives (typically: subtheories and supertheories) of ZFC that are used in set-theoretic research. If somebody wants to do set theory based on ETCS or a related base theory, these theories would have to be translated to this new base (or, in the case of theories that are not so canonical, such as ZFC*, substitutes would have to be found). </p> <p>Such a translation seems to be rather straightforward in the case of supertheories; a good translation would of course use the idioms of the target language. </p> <ul> <li>Examples of supertheories:<br> <ul> <li>ZFC plus large cardinals</li> <li>ZFC plus definable determinacy (e.g., projective determinacy, or some consequences thereof - related to large cardinals). </li> <li>ZF plus AD, or ZF + $V=L(\mathbb R)$ (supertheory of ZF only)</li> <li>ZF(C) plus "V is a certain inner model". Weaker versions include: <ul> <li>ZFC plus cardinal arithmetic assumptions (GCH, SCH)</li> <li>ZFC plus combinatorial principles ($\diamondsuit$, etc)</li> </ul></li> <li>ZFC plus forcing axioms (MA, PFA etc)</li> <li>others, including combinations (conjunctions) of the above</li> </ul></li> <li>Examples of subtheories <ul> <li>KP and related theories, which do not have full comprehension. (I think they are usually associated with proof theory rather than set theory)</li> <li>ZFC minus infinity (this is more closely associated with arithmetic than with set theory)</li> <li>ZF, or ZF plus weak versions of choice</li> <li>ZFC minus power set (plus instances of power set). Typical models are of the form $H(\chi)$. </li> <li>ZFC minus replacement (plus finitely many instance of replacement). Typical models are $V_\delta$. </li> <li>ZFC*, an often unspecified finite subset of ZFC, used to get around the "undefinability of truth", or to apply the reflection theorem. (Morally the same as the previous item.) </li> <li>ZFC minus Foundation, reflecting the fact that Foundation is hardly used outside set theory. </li> <li>Others, including combinations (intersections) of the above</li> </ul></li> <li>Other relatives: <ul> <li>ZF(C) with atoms, perhaps closer to mathematical practice than ZFC itself. </li> <li>NBG. The relation between NBG and ZFC is very well understood, as are the advantages and disadvantages: On the plus side, NBG can naturally talk about classes, and is finitely axiomatized (which might make it more amenable to automated theorem proving). On the other hand, the fact that not every subclass of $\mathbb N$ is a set can be inconvenient. </li> <li>MK and others. </li> <li>NF and NFU, sometimes claimed to be more natural than ZFC. While ZFC makes it awkward to talk about classes, NFU has problems with the function <code>$x\mapsto \{x\}$</code>. </li> </ul></li> </ul> http://mathoverflow.net/questions/116701/how-would-set-theory-research-be-affected-by-using-etcs-instead-of-zfc/118009#118009 Answer by François G. Dorais for How would set theory research be affected by using ETCS instead of ZFC? François G. Dorais 2013-01-04T01:14:35Z 2013-01-04T01:22:05Z <p>In principle, nothing would be lost by working in ETCS+R instead of ZFC since the two theories are very nicely interpretable in each other. However, after talking it through with Mike Shulman (whom I thank very much) <a href="http://dorais.org/archives/1135" rel="nofollow">here</a>, I came to the conclusion that much would be lost in practice.</p> <p>The problem lies with the notion of wellfoundedness. Recall that a binary relation $R$ on a set $A$ is wellfounded if every nonempty subset $B$ of $A$ has an $R$-minimal element (an $x \in B$ such that $y \not\mathrel{R} x$ for all $y \in B$); this is a $\Pi_1$ statement in the <a href="http://en.wikipedia.org/wiki/L%C3%A9vy_hierarchy" rel="nofollow">Lévy hierarchy</a>. In ZFC, an equivalent statement is that there is an ordinal valued rank function for $R$ on $A$ (a function $r:A \to \mathrm{Ord}$ such that $x \mathrel{R} y \Rightarrow f(x) \lt f(y)$ for all $x,y\in A$). This is a $\Sigma_1$ statement in the Lévy hierarchy due to the fact that being an ordinal is $\Delta_0$. In ETCS+R, there is no suitable equivalent to ordinals: two wellorderings of the same type are indistinguishable from each other. Because of this, in ETCS+R, the equivalent rank function statement is much more complex since one must explicitly say that the codomain of the rank function is a wellordering (for which we must use the $\Pi_1$ definition).</p> <p>Since wellfoundedness is $\Delta_1$ in ZFC, it is <a href="http://en.wikipedia.org/wiki/Absoluteness_%28mathematical_logic%29" rel="nofollow">absolute</a> for <a href="http://en.wikipedia.org/wiki/Transitive_set" rel="nofollow">transitive models</a> (of a small fragment) of ZFC. In other words, transitive embeddings between models of ZFC preserve wellfoundedness. (An embedding $f:M \to N$ is transitive if $f$ maps the elements of $x$ in $M$ onto the elements of $f(x)$ in $N$ for every $x \in M$; so the range of $f$ is a transitive substructure of $N$ isomorphic to $M$.) For models of ETCS+R, there is no natural equivalent to transitive embeddings so if one wants to preserve wellfoundedness then one must explicitly require that. In practice, it is very difficult to check that an embedding preserves wellfoundedness, especially when compared to checking that an embedding is transitive.</p> <p>Therefore, ETCS+R does not have a very good grasp of wellfoundedness compared to ZFC. Since the study of wellfoundedness is so central to modern set theory, the framework of ZFC is much more appropriate than ETCS+R for set theorists to work with. To rephrase an analogy I used elsewhere, asking a set theorist to work in ETCS+R instead of ZFC is like asking a ring theorist to work with ternary relations $A(x,y,z)$ for addition $x+y = z$ and $M(x,y,z)$ for multiplication $x \cdot y = z$: it's essentially the same, in principle, but it's simply not the right thing to do!</p> http://mathoverflow.net/questions/116701/how-would-set-theory-research-be-affected-by-using-etcs-instead-of-zfc/118227#118227 Answer by unknown (yahoo) for How would set theory research be affected by using ETCS instead of ZFC? unknown (yahoo) 2013-01-06T21:59:10Z 2013-01-06T21:59:10Z <p>Some quotes:</p> <p>"I hope the math community has reached the point of realizing that we really need not one foundation of mathematics, but many, together with clearly described relations between them. Indeed at this point the word ‘foundation’ is perhaps less helpful than something else… like maybe ‘entrance’." , John Baez <a href="http://golem.ph.utexas.edu/category/2012/12/rethinking_set_theory.html#c042716" rel="nofollow">http://golem.ph.utexas.edu/category/2012/12/rethinking_set_theory.html#c042716</a></p> <p>"There are some problems with this sort of compromise where material and structural set theories cohabitate as equal alternative foundations. ... this kind of cohabitation model is actually not the best possible way to accommodate both the material and the structural perspective at the foundational level. ... what we end up doing is moving all the annoyances from both sides into the translation between the two ... it would be much more satisfactory to have a greater overarching foundation similar to Cantor’s universe that comprises both the material and structural views.", François G. Dorais <a href="http://dorais.org/archives/1135" rel="nofollow">http://dorais.org/archives/1135</a></p> <p>"if you care about internalizing mathematics in nonstandard models — not only in order to prove formal independence results, as set theorists do, but because you care about the nonstandard models in their own right and you want to use internalization to prove things about them — then ETCS is your friend and ZFC is your enemy. Structural set theory — and its sister, type theory — is very well adapted to internalizing in many different contexts" , Mike Shulman <a href="http://golem.ph.utexas.edu/category/2012/12/rethinking_set_theory.html#c042933" rel="nofollow">http://golem.ph.utexas.edu/category/2012/12/rethinking_set_theory.html#c042933</a></p> <p>"with ZFC is that it allows things like ⟨0,1⟩⊆3 which make no sense mathematically. I can assure you, though, that after you write one piece of code in x86 assembler which rewrites itself as it runs that manipulating all objects as binary and manipulating all objects as sets make perfect sense. This is what annoys me, in some sense, that people have an issue that in a system which allows you to encode everything as sets you can write some weird junk. Equivalently, this would be baffling to those people that if you write a piece of code in Common Lisp then the code itself is just a list and the program can manipulate itself (easier than to do that in assembler, I have to admit).", Asaf Karagila <a href="http://boolesrings.org/asafk/2013/on-leinsters-rethinking-set-theory/#comment-789" rel="nofollow">http://boolesrings.org/asafk/2013/on-leinsters-rethinking-set-theory/#comment-789</a></p> <p>"I don’t like the hard line that certain things are meaningless, simply because this depends on the setting. I don’t object to the idea of saying that an expression is, for your current purposes, well-typed, since this just means you say nothing about non-well-typed expressions. I would say not “meaningless”, but rather “does not have an intended meaning”. There are expressions, such as 0∈1 that do not have an intended meaning. If they have a meaning in a certain setting, then so be it.", Walt <a href="http://golem.ph.utexas.edu/category/2012/12/rethinking_set_theory.html#c042992" rel="nofollow">http://golem.ph.utexas.edu/category/2012/12/rethinking_set_theory.html#c042992</a></p> <p>"ETCS is one, but apparently not one that is very congenial to many traditional set theorists, for a variety of reasons, maybe one being that many set theorists “don’t like categories” (well, okay, but again I think that’s a pity). Maybe some set theorists don’t like the privileging of functions over elements (although one take is that functions are generalized elements).", Todd Trimble, <a href="http://boolesrings.org/asafk/2013/on-leinsters-rethinking-set-theory/#comment-798" rel="nofollow">http://boolesrings.org/asafk/2013/on-leinsters-rethinking-set-theory/#comment-798</a></p> <p>"The same arrows aimed at ZFC can be easily turned at ETCS. It is equally easy to ask about “senseless things” which happen in ETCS but not in general mathematics. And this is not a critique against ETCS, but rather against the critique aimed at ZFC.", Asaf Karagila <a href="http://boolesrings.org/asafk/2013/on-leinsters-rethinking-set-theory/#comment-815" rel="nofollow">http://boolesrings.org/asafk/2013/on-leinsters-rethinking-set-theory/#comment-815</a></p> <p>"the issue is that first-order logic is not “type safe”, and I would suspect that people who have had exposure to first-order logic take this for granted, while those who have not may find it surprising. The reason is that syntax, in first-order logic, is defined independently of semantics, so that whether a formula is well-formed (syntactically correct) is independent of what the formula means. ... This issue of “type safety” arises also in programming languages. Some languages, such as C, have little run-time type checking. I can take a 64 bit integer and treat it as an array of eight 8-bit characters – with implementation-defined results. ... In working mathematics we have humans to check that the formulas we actually write make sense – nobody accidentally writes 1∈sin in an analysis paper – so it is not clear that there is any real advantage to stronger “type checking” in the foundations.", Carl Mummert <a href="http://boolesrings.org/asafk/2013/on-leinsters-rethinking-set-theory/#comment-794" rel="nofollow">http://boolesrings.org/asafk/2013/on-leinsters-rethinking-set-theory/#comment-794</a></p> http://mathoverflow.net/questions/116701/how-would-set-theory-research-be-affected-by-using-etcs-instead-of-zfc/118248#118248 Answer by Mike Shulman for How would set theory research be affected by using ETCS instead of ZFC? Mike Shulman 2013-01-07T07:42:05Z 2013-01-07T07:42:05Z <p>No one has really addressed the question about automated theorem provers. I'm going to take this to refer more generally to computer-assisted mathematics, since fully automated theorem provers are still of very limited usefulness to a mathematician. There are a lot of good arguments that the best foundational system for these is neither ZFC (or its relatives) nor ETCS (or its relatives), but some variety of <em>type theory</em>.</p> <p>This is mainly because type theory is so closely connected with programming and has good computation behavior, thus meshing very well with computers. Since the question is not about type theory, I won't say much about it; I just want to point out that ETCS is more like type theory than ZFC is. So although I kind of doubt that actually <em>using</em> ETCS in a computer proof assistant would be much better than using ZFC, learning to think in ETCS and do mathematics therein will probably stand you in better stead when you try to use a proof assistant based on type theory.</p>