# How do we prove a set axioms never lead to a contradiction?

How can we be sure that a set of axioms will never lead to a contradiction? If there's a contradiction, we will find it first or later. But if there's no one, how can we be sure we choosen reasonably the axioms so that no contradiction will ever arise?

Is there a general approach or for every known axiom set there was a specific proof? (In example, there exist such proof for Peano's Axioms)?

• I endorse your alternative spelling of "proove". Much more sensible than the official version. – Joffan Feb 2 '17 at 18:52
• Google "Gödel", and if this is the first time you've heard of him, prepare to have your mind blown. – RBarryYoung Feb 2 '17 at 22:51
• @Joffan I understand the endorsement but have corrected the spelling. Conventions (even ones that oughtn't be) make searching easier and offend fewer grumps like me. If you really want the "proove" edit it back in and I won't change it again. – Ethan Bolker Feb 3 '17 at 0:57
• – Ethan Bolker Feb 3 '17 at 1:01
• – symplectomorphic Feb 3 '17 at 2:16

Proofs presuppose axioms. In order to prove that "$T$ is consistent," we need to work within some other axiom system $S$; this, then means that our proof is only as convincing as our belief in the consistency of $S$. Note that even without Goedel's incompleteness theorem, we shouldn't be convinced by $S$ proving "I am consistent" - of course it would if it were inconsistent! So I actually think Goedel is a red herring, here.

That said, this doesn't kill the project of proving consistency, it just changes it. In order to prove that a theory $T$ is consistent, we want to find some theory $S$ for which we have good reason to believe that it is consistent, and then prove inside $S$ that $T$ is consistent. One standard example of this is ordinal analysis: the goal is to assign a linear order $\alpha_T$ to $T$ which is "clearly" well-ordered, and then show that the very weak theory PRA, together with "$\alpha_T$ is well-ordered", proves that $T$ is consistent (I'm skipping many details here). For $T=PA$, for instance, this was done by Gentzen; the relevant ordering is the ordinal $\epsilon_0$. This is, however, of dubious use for convincing us of the consistency of theories: for weak theories like $PA$, I find the consistency of $PA$ more "obviously true" than the well-orderedness of $\epsilon_0$, and for stronger theories the relevant $\alpha_T$s are incredibly complicated to describe.

EDIT: Symplectomorphic asked about the model-theoretic answer: we know a theory is consistent if we can exhibit a model. I did omit this above, so let me address it now. What I want to convince you of is that this is a bit more complicated than it sounds. I claim that - even if you have a model of your theory in hand - you're still going to need to do some work to convince me of the consistency of your theory, and ultimately my first paragraph above is still going to be relevant.

So suppose you have a theory $T$ you're trying to convince me is consistent, and you have a model $\mathcal{M}$ of $T$ "in hand" (whatever that means). What do you need to persuade me about?

First, you have to prove that having a model means your theory is consistent. This sounds trivial, but it's really a fact about our proof system - soundness. It's an extremely basic fact, but technically something that requires proof.

Second, when we exhibit a model, what we're really doing is describing a mathematical object. Well, you need to prove to me that it exists. There are really complicated mathematical objects out there, and theories we believe to be consistent which provably have no "simple" models (like ZFC), so this really isn't a silly objection in general.

Finally, even if I'm convinced that our logic is sound, and that the structure you've described for me exists, you need to convince me that it is in fact a model of your theory! And the more complicated your theory is, the more complicated your model will be, and hence the more difficult this task will be. In fact, this is super hard in general: is $(\mathbb{N}; +, \times)$ a model of the sentence, "There are infinitely many twin primes"? How about "ZFC is consistent"?

Now, the first obstacle is a rather silly one - I think it's fine to take the soundness of logic for granted. But the second and third aren't so trivial (and even the first isn't really completely trivial). What I'm saying is, there's no way to ground a claim of consistency as solidly as a claim of inconsistency. To show a theory is inconsistent, you exhibit a proof of a contradiction; and then I'm completely convinced. To show that a theory is consistent by exhibiting a model, you need to build a model and verify that it satisfies the theory, and each of those steps implicitly takes place in a background theory whose consistency I could in principle question.

• I find it curious that no one has yet mentioned models. My impression is that if you performed a behavioral psychology experiment and asked a bunch of mathematicians the OP's first question, most would say "you exhibit a model." (Of course this assumes our proof system is sound.) Could you comment on the model-theoretic answer? I ask only because I always learn from your answers. Cf. the link I posted in a comment to OP. – symplectomorphic Feb 3 '17 at 2:20
• (I suppose your answer contains the model-theoretical answer but allows for other approaches, too: one way to prove "inside S that T is consistent" is to use S to give a model of T, but your careful formulation of the point is meant to emphasize there may be other ways, too?) – symplectomorphic Feb 3 '17 at 2:23
• @symplectomorphic I've added a bit about models. Does this seem relevant? – Noah Schweber Feb 3 '17 at 2:58

By Gödel's Incompleteness Theorems it's known that any sufficiently powerful system of axioms cannot prove its own consistency (ie. that no contradiction arises). This applies to PA (the axiomatization of natural numbers) and ZFC (the widely used axiomatization of set theory).

So we must either assume consistency or prove it from a separate set of axioms, however that set of axioms will also be unable to prove its own consistency.

• I knew Gödel was in there somewhere, good answer. – Joffan Feb 2 '17 at 19:03
• So or either we can proof that in a sufficiently weak system or we got a Dog-Biting-Its-Tail :/ – CoffeDeveloper Feb 2 '17 at 19:11
• @Joffan and OP: I actually think Goedel is a red herring here: would we really trust a theory more if it proved its own consistency? "You should believe me, because I never lie!" – Noah Schweber Feb 2 '17 at 19:11
• @NoahSchweber We would, at minimum, have to admire its ingenuity and perhaps its chutzpah. Fortunately due to Gödel we know that the instant a system proves its own consistency, it also proves its own inconsistency - a very good reason not to trust such assertions :-) – Joffan Feb 2 '17 at 19:17
• @Noah: OTOH it's distinctly weird to contemplate working in a ZFC universe of sets that can prove ZFC is inconsistent! – user14972 Feb 2 '17 at 22:29

If a set of axioms leads to a contradiction, it means that the axioms are either wrong - you could say "not useful" - or represent entities or operations that are somewhat different to our intuition.

I don't think in general there will be a way to be absolutely certain in advance of such a problem; contradictions generally mean a need to revise the definitions embedded in the axioms, if not the axioms themselves, in order to avoid eg. the principle of explosion.

• Maybe I don't understand, so there's currently no proof that current axiom systems will never lead to a contradiction ? O_O – CoffeDeveloper Feb 2 '17 at 18:57
• Yep, there have been crises before where the foundations were looking a bit shaky. Generally though mathematics has been remarkably successful in staying consistent. – Joffan Feb 2 '17 at 18:59