Intuitive and/or philosophical explanation for set theory paradoxes - MathOverflow

Intuitive and/or philosophical explanation for set theory paradoxes

2010-06-18T19:08:53Z

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.

Answer by Dan Piponi for Intuitive and/or philosophical explanation for set theory paradoxes

2010-06-18T20:15:55Z

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.

Answer by Michael Greinecker for Intuitive and/or philosophical explanation for set theory paradoxes

2010-06-18T20:16:49Z

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.

Answer by Timothy Chow for Intuitive and/or philosophical explanation for set theory paradoxes

2010-06-18T20:46:12Z

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.

Answer by Péter Komjáth for Intuitive and/or philosophical explanation for set theory paradoxes

2010-06-19T07:46:07Z

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.

Answer by Flash Sheridan for Intuitive and/or philosophical explanation for set theory paradoxes

2011-03-11T06:23:20Z

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.

Answer by Thomas Benjamin for Intuitive and/or philosophical explanation for set theory paradoxes

2012-04-15T07:54:04Z

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.

Answer by abo for Intuitive and/or philosophical explanation for set theory paradoxes

2012-04-15T11:09:58Z

I'm still partisan of my own explanation:

www.andrewboucher.com/papers/paradoxes.htm

Answer by Francis Adams for Intuitive and/or philosophical explanation for set theory paradoxes

2012-04-15T15:24:29Z

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.