Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Please forgive me if this question sounds too naive... Well, in mathematics a formal theory consists of a collection of axioms $T$ (such as Peano arithmetics, or Group Theory, or ZFC), which essentially are certain structured chains of symbols, and theorems can be derived from them by applying certain deduction rules (or "inference laws"). These deduction rules are themselves formalizable by some axioms $\Lambda$ (such as the Hilbert-Frege deduction system).

Gödel's second incompleteness theorem states, roughly, that we cannot prove (and, to be able to prove something, we leave some fixed inference laws $\Lambda$ as understood) the consistency of any set of axioms $T$ (working within $T$).

What about the consistency of the inference system $\Lambda$ itself alone? That is, does Gödel's theorem apply somehow also to $\Lambda$ so that nobody is able to "prove" that it will not lead to a contradiction?

share|improve this question
1  
What is the "Hilbert-Frege deduction system"? –  Ricky Demer Jun 22 '11 at 15:30
    
What do you mean by the consistency of the rules of inference? That from the empty theory you cannot derive a contradiction? –  Stefan Geschke Jun 22 '11 at 15:43
1  
@Ricky: a Hilbert–Frege deduction system is a proof system whose proofs are sequences (or trees, depending on the context) of formulas, where each formula in the sequence is an axiom, or is derived from previous formulas by an inference rule. There are also some conditions on how the inference rules may look like. In practice, Hilbert systems typically consist of a list of axiom schemata together with the rules of modus ponens and, in the first-order case, one or two generalization rules. The OP may have a concrete system in mind, but the choice does not really matter. –  Emil Jeřábek Jun 22 '11 at 15:48
add comment

4 Answers 4

First, Gödel’s theorem says only that the theory itself cannot prove its own consistency (under some assumptions). It’s perfectly possible (and not particularly difficult) to prove the consistency of, say, Peano arithmetic (in usual mathematics, i.e., in ZFC).

Likewise, we can prove the consistency of the predicate calculus without non-logical axioms (your $\Lambda$). One possibility is as follows: take a proof of contradiction, and show by induction on the length of proof that all formulas in the proof are valid in the one-element model which does not satisfy any predicates. (Note that satisfaction in a one-element model is easy to define, as it’s essentially just propositional logic: you can ignore quantifiers and terms.)

If you are more syntactically-minded, you can also regard this as a reduction of first-order logic to variable-free propositional logic: strip all quantifiers, and replace all atomic formulas with $\bot$ (or any fixed false formula, if you do not have $\bot$ in the basic list of connectives). Then it suffices to show the consistency of (the variable-free fragment of) propositional calculus.

share|improve this answer
add comment

A somewhat stronger property than mere consistency, which is universally desired in a proof system, is the property of soundness.

A formal system is sound, if whenever it proves a statement $\varphi$ from some axioms $T$, then indeed $\varphi$ is true in any model satisfying $T$. In particular, when $T$ is the empty theory, then we want every statement $\varphi$ proved in the system to be true in every structure. This is usually very easy to prove for a given formal system, usually by induction on the length of the proof, simply by observing that the inference rules are truth-preserving. In contrast, the formal system is complete if it succeeds in proving $\varphi$ from $T$ whenever $\varphi$ is true in all models of $T$, and this is the nontrivial part of the completeness theorem.

share|improve this answer
add comment

If I understand your question correctly, you're wondering whether the consistency of first-order logic without any axioms can be proved using first-order logic, without assuming any axioms.

The trouble is that if you don't allow yourself any axioms, then it's unclear how you would even express the statement "first-order logic is consistent." The reason that Goedel's incompleteness theorem applies to systems that encode at least a minimal amount of arithmetic is so that you can encode concepts such as "axiom" and "inference rule," without which we cannot even define what "consistency" means.

share|improve this answer
add comment

First, a remark. You formulate both Gödel's theorem and your question in a subjective way "we cannot prove", etc. However, this theorem is a mathematical one, therefore it is not about our ability to do something, but about the nonexistence of a mathematical object, namely a formal proof within the system concerned. You can draw some e.g. philosophical conclusions from this theorem, but this is a completely another matter.

Now, as far as your question concerned, it is almost certain that nothing analogous to Gödel's theorem can even be stated for the pure first order logic itself. The reason is simple. The analogous theorem would claim the unprovability of the formula expressing the the fact that a contradiction is unprovable within the pure first order logic. But, in the absence of the formal provability predicate, this theorem cannot even be stated. Actually, what we would like to show is that there is a formula $Pr(x)$ such that, on the one hand, it can be considered a provability predicate (that is, for any formula $\varphi$, $Pr(\ulcorner \varphi \urcorner)$ is true just in case $\vdash \varphi$ (here, of course, $\ulcorner \varphi \urcorner$ is the Gödel number of $\varphi$), on the other hand, the formula expressing the fact that a contradiction is unprovable is itself unprovable: $\not\vdash \lnot Pr(\ulcorner 0=1\urcorner)$. Now, the proof of the existence of a provability predicate seems to require much more than pure logic.

share|improve this answer
    
(By "we cannot prove" of course I meant "it's impossible to prove") –  Qfwfq Jun 22 '11 at 19:26
    
I don't understand your remark. From Goedel's incompleteness theorems it follows that we cannot prove consistency of arithmetic finitisticaly (there could be no such proof, therefore we cannot find it or in other words we cannot prove etc.) as well as the fact that we cannot formalize natural numbers completely(there is no complete formalization for naturals, therefore we cannot find it).The non-existence of some object implies that we cannot do something. Mathematics is connected with our practical life as well as with intellectual one. –  SNd Jun 23 '11 at 12:22
    
@unknowngoogle: The formulation 'so that nobody is able to "prove"' seemed to suggest that you think that the theorem is DIRECTLY about our possibilities. @SNd: The non-existence of some object DOES NOT imply directly that we cannot do something. This fact depends also on the interpretation of this mathematical result. –  Gyorgy Sereny Jun 23 '11 at 16:19
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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