Zermelo-Frankel axiomatization of set theory was introduced as "solution" of resolving the many antinomies (among which Russell's paradox is probably the most famous) that plagued Cantor's naive set theory.

While ZF takes care of the old paradoxes, is it known whether ZF itself is paradox free ? Could, in principle, someone come up with a "new" paradox that would wreck havoc in ZF, the same way "old" paradoxes wrecked havoc in the naive set theory?

  • $\begingroup$ I might be wrong here, but if one could prove that ZF is consistent then that would contradict Godel's second incompleteness theorem (which is a theorem in ZF), therefore ZF would be inconsistent. $\endgroup$ – vap Oct 1 '16 at 21:16
  • 1
    $\begingroup$ "Paradox" is not a mathematical term. What you probably want to know is whether ZF is consistent, which means that every time a statement is true then its negation is false. $\endgroup$ – Anon Oct 1 '16 at 21:17
  • $\begingroup$ @McFry Yes, I guess that is what I am asking :). Could, in theory, ZF be inconsistent the same way naive set theory was? $\endgroup$ – Markus Oct 1 '16 at 21:20
  • $\begingroup$ As McFry said ZF is proved to be consistent in "higher" formal systems, that's why I thought you wanted a proof "inside" ZF. $\endgroup$ – vap Oct 1 '16 at 21:23
  • $\begingroup$ I think I do want a proof "inside" ZF, the same way Russell's paradox was "inside" naive set theory. So what are you saying is that, from Godel's second theorem, the consistency of ZF cannot be proved or disproved inside ZF? $\endgroup$ – Markus Oct 1 '16 at 21:28

Yes, it is conceivable that there is a paradox in ZF. Indeed, by Godel's second incompleteness theorem, if ZF proves that ZF is consistent, then ZF is inconsistent! (Perhaps surprisingly, it is possible that ZF proves "ZF is inconsistent," and yet ZF is consistent!)

Now here's a very brief argument for the proposition "We'll never be certain that ZF is consistent": Since ZF cannot prove its own consistency (unless it is consistent), any proof of the consistency of ZF would have to take place in a stronger theory. This implies that we can basically never be certain that ZF is consistent: in order to believe a proposed proof that ZF is consistent, we would already have to believe that more-than-ZF is consistent in the first place.

Note that we don't need truth here, merely consistency: if ZF is inconsistent, then any theory proving the consistency of ZF must also be inconsistent, since that theory would be able to prove both "ZF is consistent" and "ZF is inconsistent" (by copying the assumed inconsistency in ZF).

But that argument's not exactly accurate! It is true that (assuming ZF is consistent) any proof of the consistency of ZF has to take place in some theory $T$ which is not a subtheory of ZF; however, $T$ itself might not contain ZF, either! $T$ and ZF could be incomparable theories. So this raises an interesting question:

Can ZF be proved consistent from a theory $T$, which is "uncontroversially consistent"?

OK, ignore for a second the phrase "uncontroversially consistent", which is pretty meaningless and really just pushes the problem back one step. There is an interesting idea here:

  • Take some very weak theory which we all agree is consistent (say, $I\Sigma_1$ - this is essentially a very weak subtheory of arithmetic).

  • Now, find some new axiom $\psi$ which, when added to $I\Sigma_1$, proves that ZF is consistent.

  • Finally, make an argument for the "obvious" truth of $\psi$.

This was historically the motivation for Gentzen's idea of proof-theoretic ordinals. The idea is as follows. Suppose we want to argue that a theory $S$ is consistent. Very vaguely, we can define a linear order $\alpha$, and show that the statement "$\alpha$ is a well-ordering", when added to $I\Sigma_1$, lets us prove (usually via some form of cut elimination) that $S$ is consistent. This statement, $\psi$, is then the uncontroversial axiom we're looking for . . .

. . . assuming we can look at $\varphi$ and say, "Yep, the linear order $L$ which $\varphi$ defines is obviously a well-ordering." So it all comes down to how confident we are that certain descriptions of linear orders actually correspond to well-orderings.

(Note: this is merely one kind of ordinal analysis which can be performed, the "$\Pi^1_1$ analysis" if I have my terminology straight. There are other analyses which are more useful in various different contexts. For simplicity, I'm sticking with this one.)

For example, Gentzen's original result was that the proof-theoretic ordinal of $PA$ is $$\epsilon_0=\omega^{\omega^{\omega^{...}}};$$ if you believe that's an ordinal, then you should believe that $PA$ is consistent. Now, $\epsilon_0$ is big, but with a bit of effort it's not too hard to get a good picture of what it looks like and an understanding of why it's well-founded. So this looks promising, right?

Well, I don't know about that. Personally, I already had more faith in the claim "$PA$ is consistent" than I did in the claim "$\epsilon_0$ is well-founded," and this discrepancy only gets worse as the theories in question get stronger (and in particular we're galaxies away from computing the proof-theoretic ordinal of ZF). Still, one's mileage may vary.

  • $\begingroup$ As an aside, re: my criticism of ordinal analysis as a means of convincing ourselves of the consistency of a theory: note that this is not the only reason to care about ordinal analysis! Personally, I think that we learn a lot by understanding the various proof-theoretic ordinals (and other ordinals) attached to theories of interest. So I don't mean to imply that ordinal analysis is uninteresting, or even not foundationally important; merely that this one aspect of it is limited. $\endgroup$ – Noah Schweber Oct 1 '16 at 21:44
  • $\begingroup$ How could ZF prove its inconsistency? $\endgroup$ – vap Oct 1 '16 at 21:47
  • $\begingroup$ @vap Well, it isn't known that it does, and indeed we hope it doesn't. :) But in principle, it could, and that would not mean that ZF is inconsistent. (It would, though, mean that ZF is wrong - either ZF isn't actually inconsistent, in which case it's wrong about its own inconsistency, or it is inconsistent, in which case it proves "every set is empty", which is wrong - and this would be bad.) $\endgroup$ – Noah Schweber Oct 1 '16 at 21:48
  • $\begingroup$ @NoahSchweber What would be the consequences for mathematics as a whole if ZF proved its inconsistency? Is the consistency of ZF an implicit assumption in all other fields of mathematics? $\endgroup$ – Markus Oct 1 '16 at 21:53
  • 1
    $\begingroup$ @Markus This has been addressed elsewhere on this network - see mathoverflow.net/questions/40920/… in particular, but there's other instances too (google "ZF inconsistency"). Basically, the short answer is: ZF is overkill! The rest of mathematics doesn't really use all of ZF, indeed only tiny fragments are generally relevant. ZF could be inconsistent, and most of mathematics would be unaffected. (BTW, the study of what axioms are actually needed for various theorems has a name - reverse mathematics.) $\endgroup$ – Noah Schweber Oct 1 '16 at 21:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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