25
$\begingroup$

Gödel's original proof of the First Incompleteness theorem relies on Gödel numbering. Now, the use of Gödel numbering relies on the fact that the Fundamental Theorem of Arithmetic is true, and thus the prime factorization of a number is unique, and thus we can encode and decode any expression in Peano Arithmetic using natural numbers.

My question is, how can we use a non-trivial result like the Fundamental Theorem of Arithmetic in the meta-language that describes Peano Arithmetic, when, the result actually requires a proof from within Peano Arithmetic itself, not like other trivial things we believe to be true (i.e. existence of natural numbers and the axioms for addition and multiplication which we want to interpret in the natural way - Platonism)?

I understand we could instead use a different way of enumeration, e.g. a pairing function and the Chinese Remainder Theorem or simply string concatenation, but then the need for a proof of uniqueness when encoding and decoding remains and in general, I am interested in the structure of Gödel's original proof.

Basically, I have two ideas of how it might be possible to resolve this:

  1. Prove the Fundamental Theorem of Arithmetic within a different sound (?) system.

  2. Maybe there is nothing needed to be done to 'resolve' this, because I am just misinterpreting something and it is actually acceptable to use provable sentences of PA in the meta-language.

Any ideas about this?

EDIT: I have realized how to make my question less confusing:

Say PA proves FTA. Then, if we only assume PA is consistent, that does not rule out the possibility of FTA being false. Now, if FTA is false, then PA and the meta-language also include a false statement and thus the whole proof is useless.

How is this resolved? Is it maybe related to the fact that originally we actually assume $\omega$-consistency, and obviously, for each natural number $n$ separately, its unique prime factorization can simply be found algorithmically?

Improve this question
$\endgroup$
16
  • 4
    $\begingroup$ The theorem states that your theory cannot be both consistent and complete, so it's a win-win. I don't see the problem. $\endgroup$ Commented Jan 29, 2011 at 4:28
  • 13
    $\begingroup$ Why are number theorists allowed to use numbers? Shouldn't they first establish that it is safe to use them? $\endgroup$ Commented Jan 30, 2011 at 8:32
  • 7
    $\begingroup$ The point of my question is this: if all other mathematicians are allowed to take numbers for granted, why isn't Gödel? All he does is apply the mathematical method to the study of a certain system for manipulation of symbols known as "first order logic" and "Peano arithmetic". The subject of his study is no less mysterious, magical, or "fundamental" as all the other subjects of study in mathematics. $\endgroup$ Commented Jan 30, 2011 at 18:49
  • 11
    $\begingroup$ And I am sure Gödel knew how to prove the fundamental theorem of arithmetic. Perhaps I should have been more precise: when Gödel does mathematics is allowed to use whatever mathematics is considered "standard" by his peers. My pet peeve is this: why do "ordinary" mathematicians think that "logicians" must secure the ground on which they stand, when those same mathematicians stand on the same ground together with logicians? $\endgroup$ Commented Jan 31, 2011 at 13:40
  • 5
    $\begingroup$ @AndrejBauer Russell yes, but also Hilbert's program to prove the consistency of mathematics, and the semantic and set-theoretic paradoxes of the early 20th century all contributed to the notion that the purpose of foundations is to demonstrate that mathematical reasoning is immune from contradiction. $\endgroup$ Commented Jun 28 at 15:46

6 Answers 6

Reset to default
12
$\begingroup$

Just like most mathematical theorems, you can formalize Gödel's Theorems in some first order language (with some "standard" interpretation under which the formalization means what it's supposed to mean), turn the proof into a purely syntactic string of formulas, and figure out which formulas in that first order language are needed as axioms. I'm embarrassed to say I don't know exactly how strong the assumptions we need are to carry out the proof of Gödel's Theorems, but there will be some weak fragment of ZFC probably not much stronger than PA which will do. So we would be using a theory slightly stronger than PA to establish the incompleteness of PA, but why should that be a problem?

The axioms needed for the proofs of Gödel's Theorems are probably pretty natural, probably pretty close to PA, and probably have a natural interpretation. If you believe these axioms have this interpretation, then you would have no problem with Gödel's proofs or the interpretation of the theorems. If not, then you're probably pretty close to believing PA is inconsistent, in which case you would probably:

  1. Accept that the formalized versions of Gödel's Theorems follow from whatever axioms are used, but only because you believe those axioms are inconsistent.
  2. Deny that the formalized versions of Gödel's Theorems mean what they're supposed to mean, and just regard what's happening in point 1 as a valid string of symbolic manipulations.
  3. Accept the natural language meaning of Gödel's Theorems, in spite of point 2, for trivial reasons, since they say, "if PA is consistent, ..."

EDIT: (in response to your edit) So we're assuming PA proves FTA, PA is consistent, and FTA might be false? What do you mean by "false," you mean false in the standard intepretation? In that case, PA would be false in the standard interpretation. Now if we take Gödel's first theorem to say, "If PA is consistent, then there is a true formula in the standard interpretation which is not provable from PA," then this meta-theorem is certainly true.

EDIT: Ignas requested an explanation of some of the basics to make sense of my claim, "If PA proves FTA, and FTA fails in the standard model, then so does PA." It's too big to fit in a comment so I'm adding it to my response:

Let $\mathcal{L}$ denote the first order language of number theory, we'll have lower case Greek letters vary over sentences of $\mathcal{L}$, upper case Greek letters vary over sets of sentences of $\mathcal{L}$, and upper case Roman letters vary over $\mathcal{L}$ structures. We write $M \vDash \varphi$ to denote that $\varphi$ is true in the model $M$, i.e. when its symbols are interpreted according to $M$. Tarski's definition of truth for a sentence in a given model is by recursion on the complexity of the sentence. We write $M \vDash \Sigma$ if every member of $\Sigma$ is true in $M$. We write $\Sigma \vDash \varphi$ if for every $M$, $M \vDash \Sigma$ implies $M \vDash \varphi$, i.e. if every model of $\Sigma$ is also a model of $\varphi$.

For provability, we write $\Sigma \vdash \varphi$ to say that there is a (finite) proof of $\varphi$ using (finitely many) sentences from $\Sigma$ as axioms.

The Soundness Theorem states that for all $\Sigma ,\ \varphi$, if $\Sigma \vdash \varphi$ then $\Sigma \vDash \varphi$. It's this theorem, with PA in place of $\Sigma$ and FTA in place of $\varphi$, that I'm using to establish the claim you're asking about. The converse of this theorem is also true; it's Gödel's Completeness Theorem. Putting these two theorems together, they say that the relations $\vdash$ and $\vDash$ are the same relation between sets of sentences and sentences. One (perhaps not immediately obvious) way to rephrase this is, "being true in every model is the same as being provable from no axioms." Contrast this to Gödel's Incompleteness Theorem, which says that "being true in the standard model of number theory is not the same as being provable from PA."

Improve this answer
$\endgroup$
10
  • 3
    $\begingroup$ I am pretty sure that the incompleteness theorems can be proved in PA. I.e., you can prove something like "if ZFC is consistent then so is ZFC+$\neg$Con(ZFC)" in PA (the same for ZFC replaced by weaker theories such as PA itself). $\endgroup$ Commented Jan 29, 2011 at 5:58
  • 2
    $\begingroup$ I guess it depends on how you word Godel's Theorem. Take the first one for instance. If it says something like, "if basic arithmetic is consistent, then there's a formula that's true in $\mathbb{N}$ but not provable from basic arithmetic" then to express this you need some theory capable of expressing "true in $\mathbb{N}$." PA can't even talk about $\mathbb{N}$. I suppose there may be equivalent formluations of Godel's Theorem which sidestep the need to talk about $\mathbb{N}$, but then the question becomes: What axioms do you need to prove that equivalence? $\endgroup$ Commented Jan 29, 2011 at 6:09
  • $\begingroup$ I see. This is not a problem if you formulate the first incompleteness theorem as something like "if T is r.e. axiomatizable, consistent, and allows representations of recursive functions and relations, then T is incomplete". This gets you that PA is incomplete (if consistent, which we all believe to be the case) and once you are in a theory that allows it to talk about $\mathbb N$ in any reasonable way, then you get the theorem in the form that you quote. $\endgroup$ Commented Jan 29, 2011 at 6:23
  • $\begingroup$ @Amit Kumar Gupta: whatever metatheory you formalize the proof in can talk about $\mathbb{N}$, though. $\endgroup$ Commented Jan 30, 2011 at 23:14
  • $\begingroup$ Regarding your edit: Yes, I meant false under standard interpretation. What do you mean by "PA would be false"? Inconsistent? Well, it does not have to be as long as PA does not prove $\neg$FTA. What am I misunderstanding here? $\endgroup$ Commented Jan 31, 2011 at 0:32
11
$\begingroup$

I am not absolutely sure I understand your problems with the meta-language and such.
You take your favorite base theory, let's say PA or something stronger like ZFC. But I am quite sure that PA is enough. You prove the fundamental theorem of arithmetic in PA (or rather, a la Goedel, you prove that the $\beta$-function does what it is supposed to do). This tells you that you can code finite sequences and hence that you can talk about strings, languages, and proofs.

Now you continue and define a formula Con(PA) that expresses that PA is consistent. In the same way you can define a formula Con(PA+$\neg$Con(PA)), that expresses the obvious thing. Note that the PA that appears in these formulas is not the meta-mathematical PA but the internal PA of the model that you are in. Anyhow. This is just the usual confusion that arises with the incompleteness theorems. Now you prove, still only using PA, the statement "Con(PA) implies Con(PA+$\neg$Con(PA))" and you are done.

This is a purely number theoretic proof.

Improve this answer
$\endgroup$
11
$\begingroup$

Stefan has explained the essential points well, but let me add some details and a reference. For the first incompleteness theorem, one can work with a very weak theory of arithmetic. One needs to be able to define the relevant recursive predicates and functions (in particular those that describe the coding process) and prove that these represent, in the theory under consideration, the intended functions and relations. Here "represent" is a rather weak requirement. A formula $\phi(x,y)$ represents a function $f$ in a theory $T$ if, for each natural number $n$, $T$ proves the formula $(\forall y)(\phi([n],y)\iff y=[f(n)])$, where the square brackets mean the numeral for the number inside. (Note that $T$ need not prove $\forall x\exists y\phi(x,y)$.) A weak theory like Robinson's Q suffices to represent all recursive functions and predicates, so the first incompleteness theorem applies to all theories with at least the strength of Q. For the second incompleteness theorem, on the other hand, one needs to prove, in the theory under consideration, some basic properties of the coding, for example that concatenations can always be coded. PA suffices for this (and so do some weaker theories; $\Sigma^0_1$ induction seems to suffice). So the second incompleteness theorem is usually stated for theories that have at least the strength of PA. The details of what needs to be proved, as well as most of the details of the proofs, can be found in Shoenfield's book "Mathematical Logic"; I believe they're also in Goedel's original paper. (I'm away from home and writing this on an unfamiliar computer, which I can't persuade to preview any of my TeX code, so I apologize if it contains errors.)

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ @Andreas , do you know of a reference that pursues the question of how little/much of PA is actually required? I seem to recall "Metamathematics of first order arithmetic" treats some of this, but don't recall the explicit suggestion that $\Sigma^0_1$ induction seems enough (I do not have the book with me, though, so I cannot currently check). $\endgroup$ Commented Jan 29, 2011 at 20:59
  • 4
    $\begingroup$ I learned only recently that Pudlak proved in 1985, by model-theoretic techniques, that Q does not prove Con(Q), along with finer results. This is in the paper "Cuts, consistency statements and interpretations" from the JSL volume 50. I don't think that anyone has proved a sort of reverse-mathematics result that characterizes the amount of induction required to verify the Hilbert-Bernays conditions. $Sigma^0_1$ induction is certainly enough, but I don't remember about weaker theories at the moment. $\endgroup$ Commented Jan 30, 2011 at 23:12
  • $\begingroup$ Feferman proves a version of the second incompleteness theorem in his system $FS_0$: Finitary inductively presented logics I don't think $FS_0$ is weaker than $\Sigma_1$ induction though. $\endgroup$ Commented Jan 31, 2011 at 15:58
9
$\begingroup$

This is an old question, but I think it is worth upgrading my comment to an answer.

Implicit in the question seems to be the following presupposition, which I think is rather widespread, especially among students.

The purpose of metamathematical investigations is to justify mathematics, by showing that mathematical reasoning is reliable and free from contradiction. Therefore, in metamathematical discussions, we must refrain from using mathematical reasoning. It would be circular to justify the correctness of arithmetic by invoking arithmetic theorems, or to justify set theory by using set-theoretic reasoning.

The simplest response is to deny that the purpose of metamathematics is to justify mathematics. If we are not trying to justify mathematics, then there is no reason why we should tie one hand behind our backs when doing metamathematics. Indeed, in Gödel's paper, On the completeness of the calculus of logic, in which he proved his completeness theorem, he wrote:

In conclusion, let me make a remark about the means of proof used in what follows. Concerning them, no restriction whatsoever has been made.

He then went on to defend, in particular, his use of the law of the excluded middle. The details of that defense need not concern us here; the point is that Gödel certainly understood that the means of proof used in metamathematical investigations need to be understood if one wants to draw philosophical conclusions, but that does not mean that those means of proof always need to be restricted.

Still, you might object, didn't Hilbert's second problem, and more generally Hilbert's program, seek to justify mathematical reasoning? If Gödel's incompleteness theorems are supposed to be relevant to Hilbert's program, then don't they have to follow the rules of the game that Hilbert laid out? In particular, doesn't he have to "start from scratch" when proving his metamathematical results?

It is true that Hilbert was concerned with justifying mathematics, and so if we want our metamathematical investigations to be relevant to Hilbert's program, then we do need to pay some attention to the means of proof that we allow. However, even Hilbert understood that justifying mathematics "from scratch" makes no sense. If you're not allowed to assume anything, then you can't get off the ground. (See this MO answer for a particularly radical flavor of skepticism that you could adopt.) Hilbert proposed that we take finitary mathematical reasoning for granted. His original hope was that by using finitary reasoning, we could prove that set theory is consistent. The word finitary is not completely precise, but is often taken to mean "provable in primitive recursive arithmetic (PRA). So, returning to your original question about the fundamental theorem of arithmetic, the answer is that FTA is a theorem of PRA, so it's okay to invoke it.

There is one other remark worth making. Gödel's incompleteness theorem implies that

$(*)$ If PA is consistent, then PA does not prove that PA is consistent.

Sometimes people get confused about the significance of $(*)$. The thought process goes something like, "Well, who would ever have thought that the negation of $(*)$ would be of any interest anyway? Suppose that, per impossibile, PA did prove its own consistency; if we were doubtful about PA's reliability in the first place, then those doubts would certainly not be assuaged by a PA-proof of its own consistency! That would be circular. So why is Gödel's result interesting, if all it does is refute something that wouldn't have been interesting anyway?"

The point is that $(*)$ implies the following:

$(**)$ If PA is consistent, then PA does not prove that ZF is consistent.

And $(**)$ directly refutes (at least one form of) Hilbert's program to prove the consistency of set theory by finitary means. Even though $(**)$ is logically weaker than $(*)$, it is easier to see why it is interesting. The scenario is not that we don't trust PA; the scenario is that we do trust PA, and are wondering if we can "bootstrap" our way up to the consistency of ZF. And the answer is no; in fact, on the basis of PA, we can't even arrive at the consistency of PA, let alone the consistency of a stronger system.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ Which is why we should take on faith that the strongest systems we can find are consistent, until we find an inconsistency. ;^) $\endgroup$ Commented Jul 5 at 16:37
  • 1
    $\begingroup$ Agreed 100%, and let me add that it's also a common misconception about logic that the consistency of a theory is enough to justify its objective truth. The easy example is PA + “PA is inconsistent”, which is consistent but contains a false axiom, but there are many more interesting examples like ZFC + V = L which is consistent but which most people who understand the question don't believe. $\endgroup$ Commented Jul 6 at 10:13
  • 1
    $\begingroup$ @AlecRhea I think logicians would use other reasoning or justifications, and I'm pretty sure there is probably an existing literature on the philosophy of how and why mathematicians trust axiomatic systems that cannot be proved consistent. $\endgroup$ Commented Jul 8 at 4:27
  • $\begingroup$ @DavidRoberts Of course, we all have our own opinions on religious matters like this. (p.s. I'm aware of Maddy et. al.'s work on the subject) $\endgroup$ Commented Jul 8 at 4:30
3
$\begingroup$

It's a trick of encoding. You encode the formulas of the theory into a fixed collection of integers which have a certain form.

Now, you have defined somewhere in the background a natural notion of multiplication, addition, and equality of integers. So you are free to ask questions about whether or not two numbers are equal, and whether or not for some number $x$, there is a formula in the language of PA, for which $x$ is the encoding of, and this allows you to go backwards, in the metatheory. (that is take a number and see if it encodes a sentence)

That being said, you are never starting with a number and going backwards in the formal theory (that is to say turning it into the sentence it encodes, as this would require FTA), you are always going forward, taking the Gödel encoding of a given sentence.

It's this careful dance and intermingling of the syntax and semantics that makes the proof of this theorem so much fun to go over.

Hope this clears it up a little bit. I know it probably doesn't completely answer your question.

Improve this answer
$\endgroup$
3
$\begingroup$

Here is a way to think about it. When you use something like Fund Theorem of Arithmetic to prove Godel numbering, you are referring to the abstract set $\mathbf N$, which "exists". The Fundamental Theorem of Arithmetic is simply true about this set, irrespective of any logical system which one is constructing. If you like, you can prove the Fundamental Theorem of Arithmetic, more or less rigorously, in a metalanguage. But the proof in this metalanguage is completely orthogonal to any proofs one might construct in the logical system, such as Peano axioms.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ This may well be true, but it is not the issue at hand. The numbering of formulas and its reliance or not on the FTA happens inside the theory (as explained by the answers below). $\endgroup$ Commented Jan 29, 2011 at 22:14
  • 2
    $\begingroup$ Oh no no no, that would be pretty much the worst case, since claiming that FTA is "simply true" would render the whole proof rather vague and non-rigorous. And on the contrary, as Andres pointed out, the proofs in the meta-language are actually established within PA itself, since PA is the meta language too. $\endgroup$ Commented Jan 30, 2011 at 1:39
  • 1
    $\begingroup$ The Godel incompleteness theorem shows that $Th(\cal N)$ is undecidable. Any first-order statement, such as FTA, which is true on $\mathbf N$ is part of $Th(\cal N)$. Proving that it is part of $Th(\cal N)$ can be regarded as simply a fact (which one prove if one wishes). $\endgroup$ Commented Jan 31, 2011 at 23:24
  • $\begingroup$ -1, I believe some weak theories of arithmetic are counterexamples to the argument by Platonic truth of FLT. In the proof of the 1st incompleteness theorem, for a theory T we construct the Godel sentence G, which when unraveled is a long-winded statement about Godel-numbers that's written in T's language. Verifying this in T is important, or else we have just constructed a sentence G that may or may not have anything to do with actual consistency. $\endgroup$ Commented Dec 6, 2022 at 6:17
  • $\begingroup$ In an even more extreme case, a weak theory of arithmetic like Presburger's may not be able to formulate anything related to Godel-numbering at all! We cannot define × with the language at hand, with addition we have no way to write statements about a pairing function, let alone prove β's totality, prove uniqueness of Godel-numbers, etc. So we can't carry out the familiar construction of G w.r.t. Presburger arithmetic. Indeed Presburger arithmetic is consistent, complete and r.e., regardless of the fact FTA holds in the true naturals N. $\endgroup$ Commented Dec 6, 2022 at 6:17

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.