clarify the term "arithmetics" when talking about Gödel's incompleteness theorems

851 Views Asked by At

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?

1

There are 1 best solutions below

7
On BEST ANSWER

"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.