Take the 2-minute tour ×


No answer addresses the "bottleneck" question. It's not surprising to me because the question is vague. But I would like to know whether that is indeed the reason, or perhaps something else. The question is interesting to me and I would be grateful for any help with it.


Unfortunately, there will be a bit of vagueness in this question because of its nature and because of my limitations. I would like to ask for your understanding and help with the formulation, if they're possible.

I know (although without knowing the proof) that the consistency of ZF or ZFC cannot be proven within these theories, but their inconsistency can if they are inconsistent. I have read -- to my relief -- that it is considered unlikely that they are inconsistent. I would like to understand this statement better.

One simple argument that comes to mind is that no contradiction has been found so far, even though the theories have been extensively researched. But this alone seems a bit weak to me. The space of all provable statements in ZF or ZFC is clearly infinite. I have noticed that when mathematicians make statements about the likelihood of the truth of statements about elements of infinite classes, they usually give finer arguments than just the truth of the statement for the elements of some finite subclass. For example, many mathematicians seem to believe that Goldbach's conjecture is true, and they base their belief on theorems about the distribution of prime numbers in natural numbers.

Are there any arguments of this kind (unfortunately, I don't seem to be able to define what "this kind" means precisely here) for there not being a contradiction in ZF or ZFC? I've been thinking about how it could happen that there would actually be a contradiction in, say, ZF. I think we could define the "length" of a theorem in ZF to be the minimal number of symbols in a proof of the theorem. (Please tell me if there is something wrong with such a definition.) If we assume that ZF is inconsistent, then the proof of its inconsistency has a finite length, say $n$. For every natural number $k$ there is a finite number of theorems of length at most $k$, so we should be able to tell when we have proven all theorems of length at most $k$. The mathematical community has proven many theorems in ZF. Is it known how far we have gotten in this scale? For example, have we gotten past $k=10$? Let $m$ be the greatest natural number such that all theorems of length at most $m$ are known. Clearly, $n$ would have to be greater than $m$.

But I think many theorems must have been proven with length greater than $m$. Can we meaningfully talk about the chance of hitting the proof of the contradiction of ZF by making random correct reasonings of length $\geq n$? I've been trying to define an "inference bottleneck" that could cause the contradiction to be hard to hit, but I've failed. Since I haven't defined it, it may be difficult or impossible to understand what I mean by "inference bottleneck", but I hope it's not. I mean a theorem that can be proven by only a "small" number of reasonings, only I have trouble saying exactly in comparison to what it should be small.

I would like to ask if it actually is possible to define such "bottlenecks" and if so, would it be possible to prove that they cannot be too narrow? I'm thinking such a theorem could be a more convincing argument for there not being a contradiction in ZF.

And the more general question, to reiterate it, is what other arguments mathematicians (or philosophers?) give for ZF and ZFC being consistent. The belief in the consistency of those theories seems to me to be very strong among mathematicians, even though they tend to be very careful about saying things about other unproven statements. Why is that?

share|improve this question
You wrote "Let $m$ be the ... such that all theorems of length $m$ are known." Perhaps your first $m$ was an $n$. –  Patrick Da Silva Feb 22 '12 at 1:54
Thank you for the comment. I'm not sure what you mean though. $n$ must be strictly greater than $m$ because the inconsistency of ZF hasn't been proven yet. –  user23211 Feb 22 '12 at 2:05
@PatrickDaSilva I have corrected the definition of $m$. Is this what you had in mind? –  user23211 Feb 22 '12 at 2:08
I think this is an interesting question. Even though the consistency of ZFC can never be proven, unless it is inconsistent, perhaps some probalistic statement could be rigorously demonstrated. There are ways of error-checking proofs such that if an error exists, it is likely to be propagated throughout a special encoding of the proof, so maybe there is a way of producing an encoding of ZFC so that if a contradiction exists there is a significant likelihood that it will be propagated throughout the encoding. –  Grumpy Parsnip Feb 22 '12 at 3:19
We know it's unlikely that ZFC is inconsistent because Ed Nelson says he conducted an informal poll "among some students of foundations" and found that they put odds of about 100 to 1 against inconsistency of ZFC: math.princeton.edu/~nelson/papers/warn.pdf –  Ben Crowell Feb 22 '12 at 7:45
show 5 more comments

5 Answers

up vote 15 down vote accepted

ZFC is meant to capture a certain notion, the cumulative hierarchy of sets. For this justification to make sense you need to think of "well ordering" or "ordinal" as a pre-existing mathematical concept, not one based on ZFC. This justification is explained at more length in Shoenfield's article in the Handbook of Mathematical Logic from 1977, and elsewhere. It dates back to the early 20th century.

Assuming that we have a collection of "ordinals" $O$, which is downward closed and has minimal element $0$, we can define a collection $V^O$ as follows.

  • $V^O(0) = \emptyset$

  • If $\alpha + 1$ is in $O$ then $V^O(\alpha + 1)$ is the powerset $V^O(\alpha)$

  • If $\lambda$ is a limit ordinal in $O$ then $V^O(\lambda)$ is the powerset of $\bigcup_{\alpha < \lambda} V^O(\alpha)$

Finally, $V^O$ itself is $\bigcup_{\alpha \in O} V^O(\alpha)$. The informal way to put this is: think of the elements of $O$ as "stages". Then a set will be put into $V^O$ at stage $\alpha$ if all of its elements have already appeared at stages earlier than $\alpha$.

We can ask: which axioms of set theory does $V^O$ satisfy?

  • $V^O$ will contain the empty set as long as $O$ has at least two elements, because the empty set appears in $V^O(1)$.

  • $V^O$ will satisfy the separation axiom. To see this, assume $z \in V^O$ and that we want to prove that $y = \{x \in z : \phi(x)\}$ is in $V^O$. Well, $z$ was formed at some stage, so all the elements of $z$ were formed at earlier stages. But this means that all the elements of $y$ were also formed at stages earlier than the one where $z$ was formed, so $y$ will be formed no later than $z$.

  • Every subset of a set $z$ is formed at the same time that $z$ is formed. Therefore, the powerset of $z$ will be formed at the stage after $z$ is formed, assuming there is a next stage. So if $O$ has no maximal element then $V^O$ satisfies the axiom of power set.

These examples suggest that the axioms that are satisfied by $V^O$ will depend on how "long" $O$ is. Indeed, it turns out that if we assume sufficient properties about $O$ then we can argue in a similar way that $V^O$ satisfies all the ZFC axioms. In particular, if we let $O$ contain all the ordinals, then $V^O$ will satisfy ZFC, and we usually just write $V$ instead of $V^O$ in this case. This $V$ based on all the ordinals will be a proper class, not a set.

This argument cannot be captured in ZFC itself, although various properties of the cumulative hierarchy can be captured in ZFC. But the argument does give some motivation for why ZFC should be consistent, by giving a conception of sets (as elements of $V$) which seems intuitively reasonable. Indeed, it appears that all we need to have in order to form $V$ is a well-determined collection of ordinals, the ability to take powersets, the ability to take unions, and the ability to iterate these operations along the ordinals.

So where could ZFC be inconsistent, even if this argument is correct? One place is the separation axiom. In the argument above we assumed that $\{x \in z : \phi(x)\}$ actually does define a subset of $z$ whenever $\phi$ is a formula of set theory. If somehow there were formulas $\phi$ which do not determine subsets of $z$, our argument for why the separation axiom holds in $V$ would not go through. There is a certain sense in which the argument above is proving the consistency of second-order ZFC rather than first-order ZFC, just as the informal proof of consistency of Peano arithmetic that says "$\mathbb{N}$ is a model" is really a consistency proof for second-order PA rather than first-order PA.

share|improve this answer
Wouldn't the consistency of second-order ZFC imply the consistency of first-order ZFC? All I know about the meaning of "second-order" is that in second-order theories we allow quatification over the power set of the universe. At least I think this is what it means. But then the first-order theory is a subset of the second-order theory, isn't it? –  user23211 Feb 22 '12 at 18:40
@ymar: there is a slight difference in the way that things like separation are covered. In the second-order system we can have a single axiom for separation, while in the first-order system we have a scheme. Consistency of the second-order system only implies consistency of the first-order system if every instance of the first-order scheme is also an instance of the single second-order axiom. There isn't room in this box to go into depth. –  Carl Mummert Feb 23 '12 at 12:59
Thank you for the comment. Where can I find an in-depth explanation? (It wouldn't hurt if it were possibly simply put but I'll take anything. :)) –  user23211 Feb 23 '12 at 13:05
@ymar: if you ask it as a separate question on this site, you should be able to get a good explanation. Second-order ZFC is somewhat of a niche topic, and I don't know off the top of my head of any good first reference. But there are several set theorists active here, and I can say something as well. –  Carl Mummert Feb 23 '12 at 13:20
OK, thank you. If I can come up with a reasonably well-formed question, I'll ask it. –  user23211 Feb 23 '12 at 13:23
add comment

I am not a set theorist, so this is a slightly naive opinion.

1) As you say, many people have been exploring the consequences of ZF(C) for about 100 years, without having found a contradiction yet.

You mention this in your answer and add that you don't find it very convincing. I think it is in a certain sense very convincing, just not the usual sense of mathematics. If you think about it, strong inductive evidence is the most convincing evidence we have for most things outside of mathematics. Moreover, we are certainly willing to put our money where our mouths are for this kind of speculation: we believe, for instance, that factoring numbers is a computationally intractable problem. Why do we believe this? So far as I know, the best reason is that people have been trying really, really hard for hundreds of years to come up with efficient factoring methods and have not yet succeeded. I am not aware of any "programme" to prove this belief about factoring (It would be disproved, of course, if it turned out that $P = NP$, but very few people believe that!) But anyway, this belief is good enough for us to have made much of contemporary banking and government security depend on the difficulty of factoring!

2) Before ZF(C) axiomatic set theory people had intuitive ideas about sets, and by the way, we still do. If I interpret the axioms of ZF(C) set theory as axioms about the sets that I think about and use every day, then they are all assertions that I am quite sure hold true. Via Godel's Completeness Theorem any axiom system which is formally consistent can be proved such by exhibiting a model. In other words, when we worry that a formal system is inconsistent, we are precisely worried that it has no model. With ZF(C) we have an axiom system based on an informal model that most of us already have in our head. (In fact, to be honest, most working mathematicians know only the intuitive model of sets, not the ZF(C) axioms.) Now an "informal model" is not a model in the sense of mathematical logic: it's not even a mathematical object! But as intuition, it seems convincing: axiom systems that are chosen to model something that I already think exists are not the axiom systems where I'm worried about deriving a formal contradiction.

Unfortunately intuition -- especially, naive or untested intuition -- in mathematics often turns out to be wrong, which takes me back to my first point. If something that I deeply believe is true has held up to a century of formal attacks, then yes, I feel pretty good about it. It would be better if we could prove it, but apparently that's not how it works...

share|improve this answer
"Via Godel's Completeness Theorem any axiom system which is formally consistent can be proved such by having a model, and here we have a system which was developed out of an intuitively true model that most of us already have in our head." Wait a sec here. A model in this context is a specific, well-defined thing. An "intuitively true model that most of us already have in our head" is not such a thing. A "model" in model theory isn't just "my idea of what I mean." –  Ben Crowell Feb 22 '12 at 7:37
@Ben: I modified my answer in response to your comment. I agree that it could be read as equivocating over (very) different meanings of "model", and that was certainly not my intent. –  Pete L. Clark Feb 22 '12 at 8:16
@PeteL.Clark Just a correction "a consistent theory has a model" follows from the soundness theorem for first order logic, not the completeness theorem: if a inconsistent theory would have a model in that model the absurd should be true and that's impossible by the definition of the semantic for first order theories. –  Giorgio Mossa Feb 22 '12 at 12:39
@Ineff: I usually identify "soundness" with the theorem "If $T$ has a model then $T$ is consistent", and "completeness" with the converse. Your first sentence seems to have reversed things. For example, we have a soundness theorem for second-order logic but it is false that every syntactically consistent theory in second-order logic has a model. –  Carl Mummert Feb 22 '12 at 13:54
@ineff: Well, I actually call the fact that a theory is consistent $\iff$ it has a model the Completeness Theorem. But in fact "a consistent theory has a model" is the nontrivial direction. "An inconsistent theory has no model" (or equivalently, "If a theory has a model, it is consistent") is the soundness part. –  Pete L. Clark Feb 22 '12 at 13:56
show 5 more comments

There's plenty of time for issues to show up. You have to remember that the history of mathematics preceding set theory existed over numerous millenia and a series of abstractions over time led to Cantor's set theory. Soon after that we got Russell's paradox, and thus the need for something like ZFC, which has only been around for about 100 years. It's believed that it is consistent for numerous reasons: it captures pretty much all the preceding mathematics in a single formal language (ZFC), which is quite a feat, and we have numerous "relative consistency" results showing the consistency of numerous weaker systems imply the consistency of ZFC. Unfortunately due to results of Gödel, we can't prove the consistency of ZFC within ZFC, so this is the best we can do.

We really haven't used too much of the cardinal hierarchy in terms of "common use". You don't need $\aleph_{\omega}$ to build a bridge! Does any "applied mathematics" ever go past using the cardinality of the continuum? Maybe the cardinality of the power set of the continuum is used in some functional analysis, but by that point it's already considerably less as well-explored as the lower cardinalities we're familiar with. My point is, there's a lot of ZFC left practically unexplored with which we may run into nasty problems that we can't begin to anticipate. Perhaps when we won't find any problems until we routinely need to think about and use $\aleph_{\epsilon_0}$!

share|improve this answer
Actually $\epsilon_0$ is such ordinal that $\epsilon_0^\omega=\epsilon_0$. This means that $\aleph_{\epsilon_0^{\omega^{\omega^{\omega}}}} = \aleph_{\epsilon_0}$. –  Asaf Karagila Feb 22 '12 at 11:29
Hah! Changed to just $\aleph_{\epsilon_0}$. Thanks –  tomcuchta Feb 22 '12 at 15:16
add comment

I'll turn your question to another one, do you belive in consistency of Peano Axioms (from here simply PA)? If the answer is yes, than you have to know that ZF without the axiom of infinity is logically equivalent to PA (meaning that there is an invertibile interpretation of ZF-infinity in PA). So ZF without axiom of infinity is consistent if and only if the PA is consistent, and if you belive in consistency of PA you have to belive in the consistency of ZF without the axiom of infinity. Clearly ZF without infinity lack of two fundamental axioms, namely the infinity axioms and the axiom of choice. Axiom of Choice has been proven to be independent by the other axioms of ZF, so if there was a contradiction in ZFC there would be one in ZF: meaning that Choice doesn't change the consistency. Thus the only axiom with could bring to inconsistency in ZF(C) should be the axiom of infinity, but if you want to use a set theory which uses all the other axioms and provides the existence of infinite sets, as the set of natural numbers, you have to add infinite axioms to your system. Observe that by itself axiom of infinity could be consistent (for instance if you belive in the existence of a model that contains the set of natural numbers, the problem if it is consistent with the other axioms of ZF(C), it seems very reasonable to me that this axiom if consistent with a lot of axioms of ZF(C) [extensionality, pairing, union, powerset,...] and so far I don't see any reason for the inconsistency of ZF(C).

share|improve this answer
The interpretation of (ZF with the axiom of infinity replaced by its negation) into Peano Arithmetic also verifies the axiom of choice. At the same time, it is not hard to produce for any natural number $k$ a list of $k+1$ axioms such that any $k$ of them are mutually consistent but the full list is not. –  Carl Mummert Feb 22 '12 at 12:00
add comment

Why is it considered unlikely that there could be a contradiction ZF/ZFC?
Why is it considered likely that ZF/ZFC is consistent?

This is because people have looked at the axioms, such as $a+b=b+a$, and found them representable of their intuitive platonic believes.

After all, if you put 5 apples into a bag and then 3 apples, you get the same as if you put 3 first and then 5, and the real world has no contradictions.

By the way there are several ways to make a sensible probabilistic argument for its consistency. If we assume that there is some (any will work) probability distribution on the length of the proof of the shortest contradiction, which cant be a uniform distribution, since this is not possible for the integers. Then we just proceed by checking all deductions up to some length k, and we are bound to exhaust some non-zero probability mass.

share|improve this answer
Of course, $a+b=b+a$ is not an axiom of ZFC. Whether or not the other axioms of ZFC represent intuitive platonic beliefs is subject to lots of debate. –  Quinn Culver Feb 22 '12 at 3:43
@QuinnCulver No, there is no debate about whether people believe it. Similar to how there is no debate about whether alot of people believe in God. –  user1708 Feb 22 '12 at 3:51
Could you please explain what the ways of making a sensible probabilistic argument for the consistence of ZF(C) are? –  user23211 Feb 22 '12 at 11:32
@ymar I addressed one, but there are more but they are hard to formulate, will think some. –  user1708 Feb 22 '12 at 14:01
add comment

Your Answer

