From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.io/gmane.science.mathematics.categories/611 Path: news.gmane.org!not-for-mail From: categories Newsgroups: gmane.science.mathematics.categories Subject: Challenge from Harvey Friedman Date: Fri, 23 Jan 1998 16:26:47 -0400 (AST) Message-ID: NNTP-Posting-Host: main.gmane.org Mime-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Trace: ger.gmane.org 1241017071 26502 80.91.229.2 (29 Apr 2009 14:57:51 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Wed, 29 Apr 2009 14:57:51 +0000 (UTC) To: categories Original-X-From: cat-dist Fri Jan 23 16:27:01 1998 Original-Received: (from cat-dist@localhost) by mailserv.mta.ca (8.8.8/8.8.8) id QAA14391; Fri, 23 Jan 1998 16:26:48 -0400 (AST) Original-Lines: 108 Xref: news.gmane.org gmane.science.mathematics.categories:611 Archived-At: Date: Fri, 23 Jan 1998 11:11:28 -0800 From: Vaughan Pratt I'm taking the liberty of forwarding to the categories mailing list the following challenge posted by Harvey Friedman to Steve Simpson's Foundations of Mathematics mailing list. This is the latest in a long-running engagement about sets vs. categories on the latter list, recent postings to which can be read at http://www.math.psu.edu/simpson/fom/postings/9801.html Postings with "categor{y,ical}" in their subject lines are the relevant ones. Information about the fom list (how to subscribe etc.) can be found at http://www.math.psu.edu/simpson/fom/fom-info As we were fond of saying quarter of a century ago, Peace Vaughan Pratt ------- Forwarded Message Date: Fri, 23 Jan 1998 00:54:20 +0100 To: fom@math.psu.edu From: Harvey Friedman Subject: FOM: Set Theory Axioms The point of this posting is to give some entirely conventional axioms for set theory that are a bit simpler than many that are normally given. They are fully formal. By comparison, look at the axioms of elementary topoi that are given in MacLane/Moerdijk, Sheaves in Geometry and Logic, A first Introduction to Topos Theory, Springer-Verlag, 1994, on p. 163. The difference in complexity is strikingly grotesque. I challenge anyone to write down their favorite fully formal axioms for topoi that are sufficient to do real analysis, so we can compare them side by side with the fully formal axioms I write down here. Topos theory with natural number object is insufficient to develop undergraduate real analysis - although many fom postings conceal this fact. One has to add to topoi: natural number object, well pointedness, and choice. The latter two are nothing more than slavish translations of set theory into the topos framework. The "idea" is to take a fatally flawed foundational idea and force it to "work" by transporting important ideas from set theoretic foundations. But the axioms of elementary topoi are already incomparably more complicated than the axioms for set theory presented here. Let me start with the dramatically simple axioms of finite set theory. These amazingly simple axioms are tremendously powerful. We work in the usual classical predicate calculus with equality and one binary relation symbol epsilon - which we abbreviate here by "in." It is also useful to use the constant symbol 0 (for the empty set), the unary function symbol { } (for singletons), and the binary function symbol U (for pairwise union). Note that axioms 2-4 amount to the most trivial of definitions. 1. (forall x)(x in a iff x in b) implies a = b. 2. (forall x)(not(x in 0)). 3. x in {a} iff x = a. 4. x in a U b if and only if (x in a or x in b). 5. [phi(0) & (forall x,y)((phi(x) & phi(y)) implies phi(x U {y}))] implies phi(x). Here phi(x) is any formula in the language in which y is not free. That's all! One ***derives*** pairing, union, power set, foundation, replacement, and choice, from these axioms alone!!! Also, when appropriately formalized, "every set is finite" and things like "every set has a transitive closure." These axioms are "practically" complete - an informal concept that I have alluded to before on the fom. Now for ZFC. We take a different tack and only use epsilon. 1. (forall x)(x in a iff x in b) implies a = b. 2. (therexists x)(a in x & b in x). 3. (therexists x)(forall y in a)(forall z in y)(z in x). 4. (therexists x)(forall y)((forall z in a)(z in y) implies y in x). 5. (forall x,y)(x in y implies (therexists z in y)(forall w in z)(w notin y)). 6. (therexists x,y)(x in y & (forall z in y)(therexists w in y)(z in w)). 7. (therexists x)(forall y)(y in x iff (y in a & phi)), where phi is any formula in the language in which x is not free. 8. (forall x in a)(therexists y)(phi) & (forall x,y,z)((phi(x,z) & phi(y,z)) implies x = y) implies (therexists w)(forall x in a)(therexists unique y in w)(phi), A novelty is the axiom of infinity, 6, is simpler than usual; and also choice and replacement are combined nicely by 8. This allows such a simple axiomatization in purely primitive notation. Try to right down the axioms of a topos with natural number object, well pointed, and choice, in simple primitive notation!! Good luck. As is well known, ZFC is "practically" complete. The version in the book on p.163 - which does not even include natural number object, well pointedness, or choice - requires a very substantial amount of preliminary abbreviations in order to formalize. ------- End of Forwarded Message