Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I read from somewhere that

Fact 1. PA, which refers to the first-order version, is not finitely axiomatizable.

At the same time, the second incompleteness theorem says that there is no proof in PA for Con(PA). This theorem takes for granted that Con(PA) can be expressed as a statement in first-order logic. (Here the language consists of the constant symbol 0, the unary successor function S and the binary functions + and $\times$.) The question is

Question 2. How to express Con(PA) as a first-order sentence?

You have to take care that Fact 1 does not become false as a result of your answer to Question 2. Actually I believe that

Conjecture 3. If you have a way to express Con(PA) as a finite statement, I can turn this into a finite representation of PA, thus violating Fact 1.

Proving or arguing against Conjecture 3 is highly appreciated, besides answering Question 2.

share|improve this question
add comment

1 Answer 1

Well, while $PA$ isn't finitely axiomatizable, it is recursively axiomatizable. That is, given an arbitrary formula, we can tell if it's an axiom of $PA$. So there exists a formula $Ax(x)$ which is true (in the standard model) if and only if $x$ is the Goedel number of an axiom of $PA$. It's enough to express $Th(x)$ (true if $x$ is the Goedel number of a $PA$ theorem) and so $Con(PA)$.

share|improve this answer
    
You see, your Ax() has to work in non-standard models. Yes, "given an arbitrary formula, we can tell if it's an axiom of PA." This assumes that the "arbitrary formula" is standard. But if Ax() is presented with a non-standard element of the model, how does it detect this? Won't this ability imply that we can define what's standard and what's non-standard? –  Zirui Wang Oct 17 '11 at 12:05
    
Of course in a nonstandard model Ax() will be true of some nonstandard numbers. But that's just (one of) reason(s) why Con(PA) may fail in these models and isn't provable in PA! When we say, "Ax(x) expresses 'x is the Goedel number of a PA axiom" or "Con(PA) expresses 'PA is consistent'", it is a statement about standard model, and their behavior in nonstandard models is irrelevant. –  Alexey Romanov Oct 17 '11 at 12:47
    
Wait. How do you define a formula? That is the $P()$ in the induction axiom $[P(0)\land\forall x(P(x)\to P(x+1))]\to\forall xP(x)$. –  Zirui Wang Oct 17 '11 at 13:08
    
In the normal way. Of course nonstandard numbers are not ever really Goedel numbers of axioms of PA: that's the point. –  Alexey Romanov Oct 17 '11 at 13:41
    
What is "the normal way"? I find definitions are the most important thing in studying logic, because logicians define things differently in their inexpressive language. Look at Godel's definition of a proof; it's not required to be finite. Yes, it works in the standard model. But the existence of non-standard models (incompleteness, etc) illustrates the badness of their definitions and nothing else. –  Zirui Wang Oct 18 '11 at 9:03
show 3 more comments

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.