11
$\begingroup$

(Putting aside for the moment that Wikipedia might not be the best source of knowledge.)

I just came across this Wikipedia paragraph on the Peano-Axioms:

The vast majority of contemporary mathematicians believe that Peano's axioms are consistent, relying either on intuition or the acceptance of a consistency proof such as Gentzen's proof.

And then went back to the article on mathematical induction:

The principle of mathematical induction is usually stated as an axiom of the natural numbers; see Peano axioms.

I'm not a math person, but I'm curious - how can something which sounds like it is believed to be consistent, be the base of such widely used proof technique?

(The Wikipedia article on Peano-Axioms also states: "When the Peano axioms were first proposed, Bertrand Russell and others agreed that these axioms implicitly defined what we mean by a "natural number".)

  • 3
    In broad strokes: You can't prove a set of axioms consistent without other axioms. Thus we must *always* assume that some set of axioms is consistent in order to do anything. The problem is unavoidable.2012-08-24
  • 3
    The vast majority of people in number theory are too busy exploring the properties of the integers and related structures to even give a thought about somebody's axioms.2012-08-24
  • 3
    You might enjoy [this paper by Peter Smith on "Induction and Predicativity"](http://www.logicmatters.net/resources/pdfs/InductionAndPredicativity2.pdf).2012-08-25

2 Answers 2

18

The answer is relatively simple, but complicated.

We cannot prove that Peano axioms (PA) is a consistent theory from the axioms of PA. We can prove the consistency from stronger theories, e.g. the Zermelo-Fraenkel (ZF) set theory. Well, we could prove that PA is consistent from PA itself if it was inconsistent to begin with, but that's hardly helpful.

This leads us to a point discussed on this site before. There is a certain point in mathematical research that you stop asking yourself whether foundational theory is consistent, and you just assume that they are.

If you accept ZF as your foundation you can prove that PA is consistent, but you cannot prove that ZF itself is consistent (unless, again, it is inconsistent to begin with); if you want a stronger theory for foundation, (e.g., ZF+Inaccessible cardinal), then you can prove ZF is consistent, but you cannot prove that the stronger theory is consistent (unless... inconsistent bla bla bla).

However what guides us is an informal notion: we have a good idea what are the natural numbers (or what properties sets should have), and we mostly agree that a PA describes the natural numbers well -- and even if we cannot prove it is consistent, we choose to use it as a basis for other work.

Of course, you can ask yourself, why is it not inconsistent? Well, we don't know. We haven't found the inconsistency and the contradiction yet. Some people claim that they found it, from time to time anyway, but they are often wrong and misunderstand subtle point which they intend to exploit in their proof. This works in our favor, so to speak, because it shows that we cannot find the contradiction in a theory: it might actually be consistent after all.

Alas, much like many of the mysteries of life: this one will remain open for us to believe whether what we hear is true or false, whether the theory is consistent or not.

Some reading material:

  1. How is a system of axioms different from a system of beliefs?
  • 0
    Thanks for your very comprehensible answer! - I think I might imagine where this is headed.2012-08-24
  • 0
    @miku: You're welcome!2012-08-24
  • 0
    My only objection to your answer is that you seem to expect it to be intuitively obvious that we can't prove consistency except in a stronger theory. Since this isn't even always true, I don't think it's so intuitively obvious. For example, Tarski proved that the first-order theory of Euclidean geometry was consistent, and he did it without using a stronger theory; this was possible because the theory doesn't describe enough arithmetic to be subject to Godel's incompleteness theorem.2012-08-25
  • 0
    "The answer is relatively simple, but complicated." I know this is slightly pedantic, but simple and complex are antonyms, so it's rather hard for something to be both simple and complex. Rich Hickey explains the difference between 'easy', 'simple', 'hard' and 'complex' in the beginning of this video: http://www.infoq.com/presentations/Simple-Made-Easy2012-08-25
  • 0
    @Ben: I can't find the place where I say this is intuitive. The answer is simple because we have a theorem describing the result exactly. I didn't write a technical answer and the OP seemed to have understood it... I do agree that incompleteness is probably one of the deepest results in modern mathematics.2012-08-25
  • 1
    @kahen: Those are antynoms? Really? So the oxymoron I was trying to add to make my answer less technical and more reasonably accessible to the non-mathematician is in fact an oxymoron? As I told Ben, this is a simple answer because it is simple and not very technical, but incompleteness itself is complicated, it is deep and takes time to grok.2012-08-25
  • 1
    @Ben: Tarski could not have proved his first-order geometry consistent without using _some_ foundation for his meta-level work. And since that foundation was, evidently, able to speak about consistency _at all_, it must have been stronger than the theory he proved to be consistent. The very fact that Tarski's geometry cannot even express arithmetic means that the metatheory he used must have been stronger, as far as my intuitive understanding of that word goes.2012-08-25
  • 2
    @HenningMakholm A metatheory that talks about the consistency of a theory $T$ surely needn't be outright stronger than $T$. For example, Gentzen's proof of PA's consistency is informative precisely because the relevant meta-theory's assumptions are weaker in some respects and stronger in others that those of PA.2012-08-25
  • 1
    @PeterSmith: Not for arbitary $T$'s, but I do think a metatheory that talks about consistency has to be stronger (in some appropriately fuzzy sense) than Tarski's first-order axiomatization of geometry _in particular_.2012-08-25
  • 0
    @HenningMakholm: I see your point. The issue here is probably what is meant by "stronger." I think the normal usage is that theory B is stronger then theory A if B consists of A plus one or more additional axioms. This is, for example, the way Asaf used the term in the answer, where A=ZF and B=ZF+Inaccessible cardinal. But if A is first-order Euclidean geometry, and B is the metatheory used by Tarski, then there is no such relationship between A and B.2012-08-26
  • 1
    @BenCrowell mathematical logic provides us with a number of different, but mathematically precise ways of calculating whether a theory $T$ is stronger than a theory $S$. They include consistency strength, (several flavours of) interpretability, reverse mathematical strength and the height of the respective proof theoretic ordinals. These different ways of cashing out the notion of a stronger theory often give different answers, so the question of which is the appropriate notion will depend on the circumstances.2013-01-06
  • 0
    You can prove PA is consistent from PRA + epsilon-naught is well founded. The point is that there is a single principle that determines proof consistency, which is the well-foundedness of larger and larger computable ordinals. This process exhausts mathematical systems, and does not make reference to any noncomputable structure.2013-12-12
  • 0
    @Ron: Yes, but that theory cannot prove its own consistency, nor can PA. So you are again trapped. You can also decide that you do not believe first-order logic is consistent and therefore there are no adequate framework to formulate the questions about PA or its consistency in, that would be another way of "answering" Hilbert's problem.2013-12-12
  • 0
    You are NOT trapped--- you iterate axiom systems by adding "This is consistent" again and again, and the range of computable ordinals. The framework for formulating the consistency of PA or ZF is PRA plus axioms regarding the well-foundedness of ordinals in the Church Kleene scheme. It has worked to establish consistency of PA by Gentzen and of Kripke-Platek set theory by others, and it would work for ZF if only people didn't think that this simple observation in Godel's theorem makes it impossible. The method of non-algorithmic extension can be as simple as randomness.2013-12-18
  • 0
    @Ron: Yes, you iterate it, over and over and over. It's not well-founded and this is a witness for that. So you need another theory to prove that you can do all that, and this theory needs another to prove that it is consistent and so on and so forth. This is what I mean by being "trapped" in this context.2013-12-18
  • 0
    @AsafKaragila: You are using technical terms incorrectly. The process is well founded by definition, and "witness" means something different than what you think. The theory that proves the previous theory is consistent is simply the previous theory plus the axiom "previous theory is consistent". This, plus a description of large countable computable ordinals, is the only thing needed to prove the nonhalting of any computer program, as established by Turing in 1938. This solves Hilbert's problem in another way, once you have a method of naming ordinals, and it can establish consis(ZFC) today.2013-12-20
  • 0
    @Ron: With all do respect, I don't think that a man who claimed that the only reason there is an inaccessible cardinal in the consistency proof of "all sets are Lebesgue measurable" is to have a model of $\sf ZFC$, and that this assumption can be dispensed, is in any position to comment on how I use set theoretical terms.2013-12-20
  • 0
    That statement I made that you are criticizing is correct. The only use of the inaccessible in Solovay's paper is to produce a set which is a model of ZFC, I read the paper. The assumption CANNOT be dispensed with, I didn't say this, but it should not be controversial in any way, as it is the simplest reflection of set theory, and it is basically equivalent to saying "ZFC is consistent" (it says a little bit more, but not much). The only purpose is to have a full model of ZFC, that's all it's used for.2013-12-23
  • 0
    @Ron: Then you certainly didn't understand the paper. In fact we use a model in which there is an inaccessible, not just a model of $\sf ZFC$. Please refer yourself to Shelah's paper from 1984 in which he proves that you cannot remove the requirement of an inaccessible if you wish to obtain Solovay's result.2013-12-23
  • 0
    I read that paper too, dude. I never said the assumption can be dispensed with, I said it CANNOT be dispensed with, but it is not a controversial assumption, it is the simplest extension of set theory in which you have a set which transitively models ZFC, and there is no way to sanely accept the consistency of ZFC and to reject weakly inaccessible cardinals.2013-12-23
  • 1
    @Ron: But that is **WRONG**. The assumption that there is a transitive model of $\sf ZFC$, in fact even assuming that this model is of the form $(V_\alpha,\in)$ for some $\alpha$; in fact even assuming that this $\alpha$ has an uncountable cofinality; all those assumptions are **INSANELY WEAKER THAN AN INACCESSIBLE CARDINAL**.2013-12-23
  • 0
    @AsafKaragila: You are right it is vastly weaker than the arithmetic statement "there is a set which models ZFC", but not "insanely weaker", the thing you get from a weakly inaccessible cardinal is an iteration of the ZFC tower above the inaccessible, so that you have the power-set of the inaccessible, the power-set of that, and so on, and even when you well-order the inaccessible, the inaccessible-th power-set of the inaccessible, and so on, until the limit. It's stronger for sure, but it is the smallest extension of ZFC that allows all the ZFC operations plus a natural model somewhere.2013-12-24
  • 0
    ... you want to be able to use all the axioms of ZFC on the resulting model, so you want the model to look like a big set, and so on. But this procedure cannot be controversial, because it is just using a model for ZFC plus the usual ZFC methods of increasing model sizes to go up, it's the "second step", the way Godel put it, after "infinity" (zeroeth step) and "power set" (first step), and I cannot see how you can accept the consistency of ZFC and reject this mildest set-theoretic extension. All the ordinal/cardinal generating operations are the same, except for adding the inaccessible.2013-12-24
  • 0
    ... the only thing that Solovay is using this for is to produce a ZFC like tower where there is a point in the middle somewhere where the set models ZFC, so you can throw away all the big crap and reduce to a model of ZFC. Then you can force the reals to the inaccessible, and be left with a non-well-orderable set of reals. It's not super deep, and I think it is wrong to call this procedure suspect, it is political, there is nothing wrong with weak inaccessibles, they are tiny non-controversial statements of the form of the simplest post-ZFC reflection principle.2013-12-24
4

Mathematicians believe in "the" induction principle for natural numbers not because of set theory or PA or their consistency, they believe in "the" induction principle because of their intuition about natural numbers. Axioms are means for expressing these intuitions.

Mathematicians believe that PA is consistent and in fact sound because it satisfies the standard model of natural numbers (0 and its successors). If you believe in natural numbers then the induction principle would follow automatically for all well defined "properties".


One should be careful here because "the induction principle" is used for various things, e.g. the informal intuition that

if a "property" $P$

  • holds for 0, and
  • if it holds for natural number $n$, then it holds for its successor $n+1$,

then it holds for all natural numbers.

Here "property" is an informal concept.

Induction is also used to refer to various formal axioms that try to capture this informal intuition e.g. the first-order induction axiom in the theory of arithmetic, the second-order induction axiom of Peano, etc.