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.

The statement that 'PA is consistent' is absolutely falsifiable (a term I just made up), in the sense that if it is false, then we can demonstrate its falseness independently of any metatheory (just deduce a contradiction within PA).

Can something similar be said of the statement that 'PA is sound'? I think not, because to even make sense of the claim that PA is sound, we need a metatheory (although see here).

Clarification. Let me attempt to clarify what I mean by "absolutely falsifiable." If we're given a formal system with a recursively ennumerable set of axioms, then if someone claims that "the string $\phi$ is not deducible in the system," well this is a falsifiable claim. In the sense that, if the claim is false, in other words if $\phi$ is deducible in the system, then we can verify this within the rules of the system, simply by deducing $\phi$.

For instance, if I claim that "ZFC cannot prove that the Ackermann function is defined for all inputs," well this is falsifiable: because, if it is a falsehood, then you can confirm that its a falsehood by using ZFC to prove that the Ackermann function is, in fact, defined for all inputs. In fact, since its already known that ZFC proves that the Ackermann function is total, you already know the claim is a falsehood.

On the other hand, if I simply claim that "the Ackermann function is not defined for all inputs" without reference to a foundational system, well this is a more problematic claim. If its true, we can never confirm this, because we have to check infinitely many inputs to make sure the program halts. If its false, then for some input, we'll have to wait an infinite amount of time before we can verify that, indeed, its not going to halt. So the claim that "the Ackermann function is not defined for all inputs" is not falsifiable (and neither is its negation).

share|improve this question
1  
One hour is not a long time to judge interest, especially depending on what time zone you're in. Give it a day or so. But if you're taking suggestions: can you be more specific about what you mean by "absolutely falsifiable"? What are some examples of things that are and aren't absolutely falsifiable? –  Qiaochu Yuan May 19 '13 at 7:33
    
PA is a theory and not a system of logic. What do you mean by soundness then? –  Michael Greinecker May 19 '13 at 7:34
1  
@MichaelGreinecker, the obvious example is that $\mathrm{PA} + \neg\mathrm{Con(PA)}$ certainly isn't sound, although it might be free of contradiction. –  user18921 May 19 '13 at 7:40
1  
@Michael Greinecker: soundness of a theory means that all of its theorems are true. –  Carl Mummert May 19 '13 at 12:36
2  
@user18921: most theories have intended interpretations, but we treat them just as theories within first-order logic rather than as entirely separate logical systems. The definition of soundness for a logic is not the same as the definition of soundness for a theory, and you want the definition of soundness for a theory. If we take PA + first-order logic to be a separate logic $L$ then this is indeed sound for first-order semantics: a sentence is provable in $L$ if and only if the sentence is true in every structure satisfying the axioms and inference rules of $L$. –  Carl Mummert May 19 '13 at 12:38
show 3 more comments

2 Answers

up vote 3 down vote accepted

There is indeed a significant difference between proving a theory is consistent, and proving that all of its theorems are true, which is what the question calls "soundness".

The consistency of a theory is a universal statement that can be concretely disproved by giving a counterexample. Soundness cannot be disproved in that way. The argument that it cannot is necessarily heuristic.

The first key point is that any consistent theory of arithmetic which is sufficiently strong will be sound for atomic sentences - so it will not prove anything like "$2 + 2 = 5$" that could be used to concretely see the theory is unsound. This is because any is strong theory already proves every true atomic sentence, so it can only prove a false one if it is inconsistent.

So if PA is consistent and unsound, the false sentence $\phi$ that it proves would have to involve at least one quantifier. But then, to show PA is unsound, we would have to show that $\phi$ is true. In general, $\phi$ might have a very large number of nested quantifiers; it is known that for each $n$ there is a theory that is unsound but is sound for all formulas that have no more than $n$ quantifiers. So there is no reason to think that the falsity of $\phi$ would be intuitively clear or obvious. In general we would need to give an argument in some (meta)theory that $\phi$ is false.

Wrapping up point 1: if $\phi$ is provable in PA, that can be demonstrated concretely by giving a proof of it in PA. But, to argue PA is unsound, we also need to argue that $\phi$ is false. That additional step is what distinguishes proving unsoundness from merely proving inconsistency.

As a second point: for any sound, effective theory $T$ of arithmetic, the theory $S = T + \lnot \text{Con}(T)$ is also consistent, and is "sound relative to $T$" in the sense that whenever $S$ proves a sentence, $T$ cannot disprove that sentence. So, if we had some effective way of listing all the "obvious" facts about the natural numbers, would could call that $T$, and there would be some other theory $S$ that is unsound although our "obvious" facts cannot verify the unsoundness.

As I said, these two points provide only a heuristic argument, but together they give a lot of evidence that there is no reason to expect that a concrete (finitistic) demonstration of the unsoundness of an unsound theory of arithmetic can always be provided. As usual, we cannot make that statement precise without formalizing the metatheory.


Here are two definitions, as mentioned in the comments.

A first-order theory $T$ is called sound if all the theorems of $T$ are true. Here "true" means "true in the intended interpretation of $T$", which is usually determined from context. For a theory in first-order logic, because the inference rules all preserve truth, soundness of a theory is equivalent to all the axioms of the theory being true in the intended interpretation. This sense of soundness is closely related to the traditional notion of a sound argument: an argument is sound if its form is valid and all of its premises are true. On the other hand one can present valid arguments that use false hypotheses; the difference is that sound arguments establish the truth of their conclusions, while valid arguments may not. Similarly, sound theories establish the truth of their theorems, while unsound theories do not.

Soundness of a logic is a more delicate matter. A general (two-valued) logic has a collection $\mathcal{L}$ of sentences, a collection $\mathcal{D}$ of inference rules, and a collection $\mathcal{I}$ of interpretations, where each interpretation includes a function from $\mathcal{L}$ to $\{T,F\}$ which tells whether each sentence is true or false in that interpretation. The logic $(\mathcal{L}, \mathcal{D}, \mathcal{I})$ is sound if, whenever a sentence $\phi \in \mathcal{L}$ is provable from some set $H$ of hypotheses, then every interpretation in $\mathcal{I}$ that makes every sentence in $H$ true also makes $\phi$ true.

The difference is that a general logic may have no sense of an "intended interpretation", so soundness of a logic merely states that the inference rules preserve truth in all the interpretations in $\mathcal{I}$. But in the case of foundational theories, such as Peano arithmetic, we already have an intended interpretation in mind, and so for soundness of a theory we focus on truth in the intended interpretation rather than truth in all interpretations.

share|improve this answer
    
With regards to your edit: it seems to me that the distinction between a "general logic" and a "theory" and is more sensibly viewed as a distinction between a "general logic" and a "logic with a unique intended interpretation." Wouldn't that make more sense? –  user18921 May 20 '13 at 1:04
    
Carl, I just reread your answer and found it very enlightening the second-time around. Thank you. –  user18921 Jul 21 '13 at 21:20
add comment

Suppose I say: "Here's my attempt to axiomatize the truths of arithmetic of successor, addition and multiplication over the natural numbers", and I start writing down some axioms. And for the sixth axiom I write down

(A6)$\quad\forall x\forall y(x \times Sy = x \times y + y)$

Then you could say "Hold on! That implies $2 \times 2 = 2 \times S1 = 2 \times 1 + 1 = 3$ so something has gone horribly wrong, for it's plain false that $2 + 2 = 3$! Surely what you meant to write was $\forall x\forall y(x \times Sy = x \times y + x)$."

Now note, would you in this little exchange, be deploying a fancy metatheory? Well, you would just be using plain old arithmetic (hey, $2 + 2 \neq 3$) in criticizing my attempt to axiomatize plain old arithmetic! (Call plain old arithmetic your metatheory if you must: but it certainly isn't fancy!)

Well back to the drawing board. I come up with a better axiomatization, our old friend PA. Now suppose, just suppose, you could again deduce a sentence $\varphi$ in this new theory which is clearly false as a sentence of plain old arithmetic. Then you would have shown that PA is as bad as my first failed attempt (it isn't a sound axiomatization of arithmetic). And again, you wouldn't be appealing to a fancy metatheory in saying this -- just to arithmetic again. Sure in criticising PA you are appealing to something -- but to nothing other than what PA is trying to axiomatize in the first place.

Of course, few of us think that the supposition is going to get realized, and you get to find a falsehood in PA -- but that's another story!

share|improve this answer
    
Is that meant to read: "Hold on! That implies $2×2=2×S1=\cdots$" –  user18921 May 19 '13 at 8:01
1  
ooops! it was indeed. –  Peter Smith May 19 '13 at 11:17
add comment

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.