Why is it OK to rely on the Fundamental Theorem of Arithmetic when using Gödel numbering? - MathOverflow

Why is it OK to rely on the Fundamental Theorem of Arithmetic when using Gödel numbering?

2011-01-29T03:23:21Z

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:

Prove the Fundamental Theorem of Arithmetic within a different sound (?) system.
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 too includes a false statement and thus the whole proof is useless.

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

Answer by Amit Kumar Gupta for Why is it OK to rely on the Fundamental Theorem of Arithmetic when using Gödel numbering?

2011-01-29T04:37:30Z

Just like most mathematical theorems, you can formalize Godel'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 Godel'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 Godel'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 Godel'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:

Accept that the formalized versions of Godel's Theorems follow from whatever axioms are used, but only because you believe those axioms are inconsistent.
Deny that the formalized versions of Godel'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.
Accept the natural language meaning of Godel'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 Godel'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 Godel'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 Godel's Incompletness Theorem, which says that "being true in the standard model of number theory is not the same as being provable from PA."

Answer by Michael Blackmon for Why is it OK to rely on the Fundamental Theorem of Arithmetic when using Gödel numbering?

2011-01-29T06:15:36Z

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.

Answer by Stefan Geschke for Why is it OK to rely on the Fundamental Theorem of Arithmetic when using Gödel numbering?

2011-01-29T06:16:14Z

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.

Answer by Andreas Blass for Why is it OK to rely on the Fundamental Theorem of Arithmetic when using Gödel numbering?

2011-01-29T08:03:16Z

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 strewngth 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.)

Answer by David Harris for Why is it OK to rely on the Fundamental Theorem of Arithmetic when using Gödel numbering?

2011-01-29T22:06:16Z

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.