Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Every student of set theory knows that the early axiomatization of the theory had to deal with spectacular paradoxes such as Russel's, Burali-Forti's etc. This is why the (self-contradictory) unlimited abstraction axiom ($\lbrace x | \phi(x) \rbrace$ is a set for any formula $\phi$) was replaced by the limited abstraction axiom ($\lbrace x \in y | \phi(x) \rbrace$ is a set for any formula $\phi$ and any set $y$).

Now this always struck me as being guesswork ("if this axiom system does not work, let us just toy with it until we get something that looks consistent "). Besides, it is not the only way to counter those "set theory paradoxes" -there's also Neumann-Bernays-Godel classes.

So my (admittedly vague) question is : is there a way to explain e.g. Russel's paradox that does better than just saying, "if you change the axioms this paradox disappears ?" Clearly, I'm looking for an intuitive heuristic, not a technical exact answer.

EDIT June 19 : as pointed out in several answers, the view expressed above is historically false and unfair to the early axiomatizers of ZFC. The main point is that ZFC can be motivated independently from the paradoxes, and "might have been put forth even if naive set theory had been consistent" as explained in the reference by George Boolos provided in one of the answers.

share|improve this question
    
Are you asking for an explanation of why the paradox occurs, or an explanation of how it is avoided ? –  Carl Mummert Jun 18 '10 at 23:07

8 Answers 8

up vote 5 down vote accepted

George Boolos has a number of very readable (to the non-expert like me) essays on this subject. Try "The Iterative Conception of Set" in Logic, Logic and Logic. He tries to find a way to look at the axioms of ZF set theory from a perspective that makes them look natural and not simply contrived to avoid paradoxes. I don't know anything about how Boolos's views are seen by other Set Theorists.

share|improve this answer

Here is the argument that Lajos Posa gave me when I was at highschool. The short description of Russell's paradox is that let V be the set of all set, define $A=\{x\in V:x\notin x\}$ then argue that both $A\in A$ and $A\notin A$ are impossible. That is, we first assume that all sets are given in a final, unchangable form, in a nonextendable list, next we create a new set, specifically in such a way that it should differ from all sets given, then we are surprised that it indeed differs from all sets. The axiomatic way forbids looking at all sets given by one complete, unchangable list, we are only allowed to create sets with a limited collection of tools (the axioms), and so establish general properties of sets.

share|improve this answer
4  
What surprises me about this story is that the logic of sets is taken to be classical rather than intuitionistic. If you assume that the domain of quantification (eg, the universe of sets) can grow, and you want true propositions to remain true in future domains, then you get a Kripke model. So why isn't the logic of sets intuitionistic? Or at the very least, why don't sets have an open/closed distinction as in topology...? –  Neel Krishnaswami Jun 19 '10 at 10:34
2  
@Neel: I think there are two reasons. The first is that set theory was developed before semantics for intuitionistic logic were known. Kripke models were first studied in the 1950s, and the BHK interpretation was not widely known before the 1930s. Second, some set theorists I know feel that a key goal of set theory is to study the intended model, which consists of "all sets" (disquotationally). That model, from their point of view, cannot possibly grow larger. Let's leave the discussion on the validity of that view for another day; I'm just pointing out it's common among set theorists. –  Carl Mummert Jun 19 '10 at 12:14

There are two ideas for dealing with paradoxes that lead to essentially the same concepts and can motivate the same axioms.

One idea that goes back to Cantor (who wasn't as naive as is commonly believed) is that sets should be small, managable collections. This is the doctrine of limitation of size. All set theoretic paradoxes known stem from treating really large collections of sets as sets, as in "the set of all sets", "the set of all ordinals" etc. The replacement axioms is most easily motivated this way: If you can identify the elements of a large collection in a one-to-one manner with a set, then that collection is an actual set.

The other approach is that one creates the universe of sets in steps. You basically start with the empty set and form sets out of it by putting it between brackets "{" like "}", collecting all subsets in the powerset etc. Eventually one collects the sets thus obtained in an infinite set and continuous with these operations. Presumably, if the existence of a set is consistent, there is no reason why performing these operations on it should lead to a paradoxical set. Everything is build in stages. Since the empty set is certainly small and no operation increases the size of existing sets too fast for the taste of a set theorist, this goes well with the doctrine of limitation of size. It is possible to give an explicit axiomatizaion of ZFC along the approach of building sets in steps from sets that exist already. This has been done in a very readable paper by Dana Scott, "Axiomatizing Set Theory". Here is a teaser:

Zermelo answered the question by giving several construction principles for obtaining new a's from old. Fraenkel and Skolem extended the method, and von Neumann, Bernays and Gödel modified it somewhat. Actually this is a rather sad history-because set theory is made to seem so artificial and formalistic. The naive axioms are contradictory. We block the contradiction and thereby emasculate the theory. Therefore to get anywhere we reinstate a few of the principles we eliminated and hope for the best. Now it would be wrong to accuse any of the above men of holding such a simplistic view of the axiomatic process. Nevertheless it is a very widely held view and one that is easy to fall into when considering only the formal axioms without their intuitive justification. Let us try to see whether there is another path to the same theory more obviously based on the underlying intuition.

share|improve this answer
1  
Can you give a more precise reference to "Axiomatizing Set Theory", please? –  Andrej Bauer Jun 18 '10 at 21:38
    
Dana Scott, "Axiomatizating Set Theory," Proc. Symp. Pure Math., vol. 13, Part II, 1974, p. 207ff. –  Timothy Chow Jun 18 '10 at 21:58

The history of axiomatic set theory did not proceed in the way that you suggest here. Zermelo, for example, was motivated to form his axiomatic system primarily in order to give a careful proof of his well-ordering theorem, and not to avoid the set-theoretic antinomies. If trying to avoid contradiction were our primary goal, then we would almost surely scale way back and work with much weaker axiomatic systems such as those described in Simpson's book Subsystems of Second-Order Arithmetic, which suffice for a huge fraction of mathematics. Thus your "if this axiom system does not work, let us just toy with it until we get something that looks consistent" is a straw man. I don't know of anybody who has done serious work in foundations that has taken anything even remotely resembling that attitude.

That said, you can still ask for some justification for why we should expect, say, ZFC to be consistent. Michael Greinecker has given a good answer. I would like to add one key word to his account that you may find helpful if you want to do more reading on this subject: impredicativity. Intuitively, the set-theoretic paradoxes all arise because of "self-reference" in some sense. We define something by quantifying over a set that contains the thing being defined. The intuition is that if we avoid such "impredicative" definitions, by defining new sets only in terms of sets that we have already constructed, we should block the paradoxes.

I should note, however, that ZFC is generally regarded as being impredicative, so this doesn't fully answer your question in the case of ZFC. Nevertheless, the consistency of ZFC is typically justified by the describing the so-called cumulative hierarchy of sets, which is built from the ground up, and thus is based on the same intuition that if you define things in stages with each stage building on the previous stage, then self-referential loops should not have any way of arising.

share|improve this answer
    
The "cumulative hierarchy" justification seems a bit strange when you consider that axiom of foundation is pretty much never used. –  Harry Altman Jun 18 '10 at 20:52
1  
@Harry: You mean that foundation is never used in "ordinary mathematics"? The point is that the question being asked here is whether ZFC is consistent, not whether ZFC faithfully mimics every aspect of mathematical practice. And ZFC is consistent if and only if ZFC minus foundation is, so as far as consistency is concerned, it does no harm to throw in foundation if it helps you see more clearly that inconsistencies will not arise. –  Timothy Chow Jun 18 '10 at 21:53
    
@ Timothy : how do we know that "ZFC is consistent if and only if ZFC minus foundation is" ? –  Ewan Delanoy Jun 19 '10 at 5:05
1  
@Ewan: If ZFC minus foundation is consistent, then the well-founded sets form a model of ZFC. –  Harry Altman Jun 19 '10 at 10:45

To get back to the original question, I blame half-hearted Platonism for the paradoxes: If you’re enough of a mathematical Platonist to believe that the universal set is a completed totality, then it’s hypocritical to believe that you can later construct new sets via a comprehension scheme. That does of course leave open the question of what sets other than the universal set exist; the best answer I know of is Alonzo Church’s “Set Theory With a Universal Set,” which has an axiom of complements and a generalization of Frege-Russell cardinals as sets, and is equiconsistent with ZF.

Disclaimers: Church was cagey about the philosophical motivation behind his theory; Thomas Forster (in Oxford Logic Guides 20 & 31, also entitled Set Theory With a Universal Set,) likened my reasoning to “the grating sound of a virtue being made of necessity,” though I did come up with it before I discovered Church’s theory, in an essay which R.I.G. Hughes gave a D.

Church’s original paper is heavy going, and omits the consistency proof. There are some unpublished lecture notes of his proof for the case m=0, but they’re even heavier going, and the real challenge is for m>0. Forster’s book is probably the best place to start on Church’s theory (and related theories by Emerson Mitchell and me), though the first edition has more detail than the second; see also http://www.dpmms.cam.ac.uk/~tf/church2001.pdf.

share|improve this answer
1  
Would a Platonist ever "believe that you can later construct new sets"? Wouldn't the most you can do "later" be to notice and describe some sets that had actually been there all along? –  Andreas Blass Mar 11 '11 at 14:57
    
“Iterative” isn’t my metaphor, so I’m not sure I’m the right person to defend it, but even Gödel, in the classic Platonist defensive of the iterative conception, uses explicitly temporal language at least once: “immediately,” [footnote 12 of “What is Cantor’s Continuum Problem,” reprinted in Benacerraf & Putnam]. Boolos uses temporal language emphatically in “The Iterative Conception of Set,” e.g., “now” twice, once italicized, on page 491 of B&P. He does of course disclaim the metaphor for the formal exposition, but it’s the motivation we’re discussing now, not the formalism. –  Flash Sheridan Mar 11 '11 at 21:56
    
The discussion here has also been what I call “temporalist,” e.g., “Eventually,” “new a's from old” [quoting Scott], and “already.” One comment on the temporalist metaphor and predicativity, which is not original with me (I heard it from someone at Oxford in the 80’s): If you’re serious about the metaphor, why can sets at one stage be defined via quantification over later stages? –  Flash Sheridan Mar 11 '11 at 21:58
    
Admittedly the standard formalism does possess impressively unreasonable effectiveness, and the various programs of “Fixing Frege” (e.g., also as a basis for arithmetic) are still well short of the dominant paradigm. My own attempt to extend Church’s theory (with the singleton function as a set), though it’s equiconsistent with ZF as far as it goes, seems unlikely to be able to go far enough for the needs of category theory (e.g., Feferman’s “Enriched stratified systems for the foundations of category theory,” in What is Category Theory? [G. Sica 2006]). –  Flash Sheridan Mar 11 '11 at 21:59
1  
Platonists use temporal metaphors, but I doubt that they view sets as owing their existence (creation, construction, etc.) to the process described by such a metaphor. The sets are there anyway, and we (may) organize them into a hierarchy. –  Andreas Blass Mar 14 '11 at 14:59

I'm still partisan of my own explanation:

www.andrewboucher.com/papers/paradoxes.htm

share|improve this answer
    
Interesting. "Empty" is not the same thing as "vicious" indeed. –  Ewan Delanoy Apr 22 '12 at 14:39

A really interesting paper by Penelope Maddy called Believing the Axioms has a pretty substantial discussion about various justifications for axioms of set theory. Not only does it look at ZFC, but also higher axioms concerning large cardinals and determinacy. The paper doesn't really talk about why one might want to axiomatize set theory, but it does look at reasons why the axioms that currently exist can be justified, and how they reflect some intuition about how the set-theoretic universe "should" look.

It comes in two parts:

Part 1: http://www.cs.umd.edu/~gasarch/BLOGPAPERS/belaxioms1.pdf

Part 2: http://www.cs.umd.edu/~gasarch/BLOGPAPERS/belaxioms2.pdf

Even if this doesn't really answer your question, this is certainly an interesting read if you are curious about some philosophy of set theory.

share|improve this answer

Let V={x|x is a set and x is not a member of x}. Russell's Paradox only arises if one assumes that V is either a member of itself or its complement. The third alternative is that neither '_ is a member of V' nor not-'_ is a member of V' can be predicated of V. One does not need to invoke a cumulative hierarchy to get rid of the paradox.

share|improve this answer
    
Actually, Curry showed that a similar paradox arises even in minimal logic which doesn't even have negation! en.wikipedia.org/wiki/Curry's_paradox –  François G. Dorais Apr 15 '12 at 11:47
    
@Francois: your link does not lead where you want it to lead. –  Lee Mosher Apr 15 '12 at 14:25
    
Consider C={x|'x is a member of x' implies F} where F is any false sentence. if 'implies' is the material conditional and 'x is a member of x' is true then "'x is a member of x' implies F" is false. Can one say that there are x satisfying a falsehood? If yes then C is a legitimate set, although one would not want to derive anything from it. If 'implies' = '|--' (where relevancy might be considered) then " 'x is a member of x' implies F, where F is false implies not-'x is a member of x' and C={ }. Consider the set S={x| x is a colorless green idea}. Is S a set? –  Thomas Benjamin Apr 15 '12 at 22:36
    
Let H={x| x is a current student at Hogwarts}. Is H a set? Perhaps this thought will lead to a heuristic for dealing with the paradoxes in Naive Set Theory--Consider what can correctly be predicated of what, 'correctly' meaning so as not to lead to contradictions or falsehoods or being able to derive all possible well-formed formulas. –  Thomas Benjamin Apr 15 '12 at 22:44
    
@Lee: Francois’s URL works, but the MathOverflow parser mangled the link. en.wikipedia.org/wiki/Curry%27s_paradox may have better luck. –  Flash Sheridan Apr 16 '12 at 12:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.