3
$\begingroup$

I am not quite sure what really is meant when talking about "arithmetics" in context of Gödel's incompleteness theorems.

How I so far understand it:

Gödel proved that every sufficiently powerful first-order theory is not both consistent and complete at the same time.

This is, you pick a first-order language (so the logical symbols are restricted to first-order) i.e. a signature. Pick a structure $S$ for this signature i.e. add a semantical interpretation. Pick a set $A$ of axioms which yields a suffieciently powerful theory. Then the incompleteness theorem states:

either we have incompleteness $$\text{exists } \varphi : \text{ neither } A \models_S \varphi \text{ nor } A \models_S \neg\varphi$$ or we have inconsistency $$\text{exists } \varphi : A \models_S \varphi \text{ and } A \models_S \neg\varphi$$

But now sometimes this is stated as "PA is incomplete assuming consistency", "ZF/ZFC is incomplete assuming consistency" or "Robinson arithmetic is incomplete assuming consistency".

Didn't Gödel originally pin down a signature and some axioms (Robinson axioms) which were the minimal prerequesites to allow recursion methods and Gödel numbering necessary to formulate the Gödel sentence and hence proof the incompleteness theorem?

Is this signature together with the Robinson axioms called "Robinson arithmetic"? Am I getting the term arithmetic right in the sense: signature + axioms?

How does this result then translate to Peano arithmetic and ZF/ZFC set theory, which have other signatures and other axioms?

$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$

"Gödel proved that every sufficiently powerful first-order theory is not both consistent and complete at the same time." No. First the incompleteness theorem is not especially about first-order theories (Gödel originally proved the theorem for a version of Principia's type theory). And it is crucial that the theory in question is recursively axiomatized. Also the version of the incompleteness that assumes consistency (rather than soundness or $\omega$-consistency) is due to Rosser. So rather better:

Gödel and Rosser proved that every sufficiently powerful recursively axiomatized theory is not both consistent and complete at the same time."

Being "sufficiently powerful" is a matter of being capable of representing the recursive functions.

"Didn't Gödel originally pin down a signature and some axioms (Robinson axioms) which were the minimal prerequesites to allow recursion methods and Gödel numbering necessary to formulate the Gödel sentence and hence proof the incompleteness theorem?" No. The minimal prerequisites were investigated some 20 years after Gödel's paper, by ... wait for it! ... Raphael Robinson.

"Is this signature together with the Robinson axioms called "Robinson arithmetic?". Historically, "Robinson Arithmetic" has been used as a term for two different theories, one finitely axiomatized the other not. These days, it is usually the finitely axiomatized one that is meant -- you specify the theory by, yes, fixing the language and giving the axioms.

"How does this result then translate to Peano arithmetic and ZF/ZFC set theory, which have other signatures and other axioms?" First-order Peano Arithmetic has the same signature as Robinson Arithmetic, and the theory includes RA, so Gödel's First Theorem directly applies. As for ZF(C), you show that you can interpret arithmetic in ZF(C), and -- with the appropriate renditions -- the axioms of Robinson Arithmetic are theorems of ZF(C), and so off you go again. You have a (primitively) recursively axiomatized theory which can represent all recursive functions (in virtue of including RA), so Gödel's theorem applies again.

$\endgroup$
7
  • $\begingroup$ Thanks. a. So it can be applied to any recursively axiomatized theory (this is a property of the axiomatization) and does not depend on which logic is used, say first-order or second-order logic? b. These minimal prerequesites pin down some minimal necessary axioms, do they also require the language to have certain properties to allow representing recursive functions? c. So one can say "since PA and ZF(C) can interpret arithmetic and render Robinsons axioms the incompleteness theorem holds for them, no matter if ZF(C)s signature being different"? $\endgroup$
    – logisches durcheinander
    Sep 10, 2013 at 14:07
  • $\begingroup$ (a) Yes. And doesn't require the logic to be classical either. (b) You require enough to be able to represent the recursive functions. There's no unique minimum axiomatization (neither of two theories called Robinson Arithmetic contains the other). $\endgroup$
    – Peter Smith
    Sep 10, 2013 at 14:10
  • $\begingroup$ And if you want to know more, try Ptr Smth's *Introduction to Gödel's Theorems. Or the notes, Gödel Without Tears at logicmatters.net/igt/further-notes $\endgroup$
    – Peter Smith
    Sep 10, 2013 at 14:13
  • $\begingroup$ Great pointer, I'll definetly have a look when I've again time to spent on this stuff! A question about a subtle detail: "you specify the theory by fixing the language and giving the axioms" -- does this mean I just have to fix the language/signature and not the structure $S$? $\endgroup$
    – logisches durcheinander
    Sep 10, 2013 at 14:16
  • $\begingroup$ I do not quite get one subtle detail: In your wrap-up ("Gödel and Rosser proved ...") it says "recursively axiomatized". Does it need to be "primitive recursively axiomatized" or can "primitive" be omitted? I do not quite get the difference; p.r. axiomazized -> three numbering properties being p.r., i.e. decidable by p.r. functions; axiomatized -> three numbering properties being decidable. -- is it just that the latter allows decidable to be different from p.r. decidable? $\endgroup$
    – logisches durcheinander
    Sep 12, 2013 at 11:30
0
$\begingroup$

Arithmetics in terms of (application) of Goedel's technique (and in extension Geodel's theorem) are formal systems which axiomatize these effective parts of arithmetic which make possible the Fundamental Theorem of Arithmetic (there are infinite prime numbers and each integer has a unique factorization in terms of those prime numbers)

Peano axiomatization of arithmetic is such a system.

ZF(C) set theory axiomatization can also produce Peano arithmetic so Goedel's result is also applicable (in its stated form)

This makes Goedel encoding (a major part of the proof of Goedel's theorem) possible and as a result the meta-theory system can be represented inside the formal system under study.

There are formulations of arithmetic which do not cover the above stated requirements and for these Godel's theorem is not applicable

NOTE: There are formulations of mathematics (like intuitionism) which do not need a meta-theorem like Godel's (in a sense it is already embedded in the formulation itself)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .