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.

If I am not wrong, many mathematicians (I believe this is not only restricted to structuralists) agree that an inconsistent formal system does not have any model. By model I mean some kind of set whose structure (objects plus their properties and relations) is represented by the formal system. But I have not seen any complaint for unsound systems. To be more specific: why are non-standard models or arithmetic considered seriously if they are unsound? How is it that people cannot imagine inconsistent structures but can imagine unsound ones. For instance, an unsound system would predict that a Turing machine will halt even when an actual one will not. Am I wrong?

share|improve this question
    
To clarify: is it correct that by "unsound," you mean "proves theorems which are not actually true?" –  Nick Thomas Feb 1 '13 at 4:14
    
I believe I could say yes. The problem is that you can argue that the theorem is actually true in some structure (or non-standard model). –  julian fernandez Feb 1 '13 at 4:18
1  
I don't know what it would mean for a model to be "unsound". –  Hurkyl Feb 1 '13 at 4:25
    
it was short for a model (or structure, that for me is equivalent) that is defined by an unsound formal system –  julian fernandez Feb 1 '13 at 4:28
    
Continuation for Nick. However, by Post theorem any theorem is equivalent to stating that a Turing machine halts or doesn't. And Turing machines are very specific structures. –  julian fernandez Feb 1 '13 at 4:29
show 4 more comments

2 Answers

up vote 5 down vote accepted

One possible answer is this. Usually the reason nonstandard models of arithmetic are interesting is not that we think they really might be what we are trying to talk about when we talk about natural numbers. What's usually more interesting about them is that they show that first-order logic isn't strong enough to formulate a theory of the natural numbers which is definitely talking about the natural numbers.

The axioms of PA could be describing the natural numbers, but they could also be describing some other weird thing. We can't seem to get past this issue in first-order logic, and any attempt to "fix" the issue by adopting a stronger logic will provably run into even more weirdness. This basic conundrum is one of the major reasons that nonstandard models of arithmetic are interesting.

You write:

"My problem is that [nonstandard models] prove things that are not true about Turing machines, and they do talk about Turing machines, which are very specific objects."

One possible response begins by pointing out that a Turing machine $T$ in question is coded as a natural number, and the statement that $T$ halts is coded as a statement about natural numbers. If we plug that statement into a nonstandard model $M$ and it spits out that $T$ does not halt, we may say that the problem is that our coding of a Turing machine as a natural number, and the statement that $T$ halts as a statement about natural numbers, no longer has our intended meaning when the objects are not natural numbers but objects of $M$.

Our coding does not match our substrate (as if we were typing English on a Russian keyboard). In effect, then, we are no longer talking about Turing machines; we're talking about some other strange type of object which emerges from the interaction between our complicated arithmetical statement and our complicated nonstandard model.

For instance, it could be the case that in an arithmetically unsound system you can prove that a Turing machine that doesn't halt in the "physical" world, or rather, after a finite number of steps, would indeed halt after a transfinite number of steps (that is, for some non-standard number).

share|improve this answer
    
I understand that PA could be not strong enough to represent only the intended structure (the natural numbers), and that other structures non-isomorphic to N could satisfy PA. However, my problem is that these other structures do not have the same status than N, in the the sense that they can all be described by unsound systems (not the case of N). and I do not mean that they are unsound because they have properties that are not true in N (after all, they do not have to be isomorphic to N), and they are not a model of N. –  julian fernandez Feb 1 '13 at 4:56
    
continuation: My problem is that they prove things that are not true about Turing machines, and they do talk about Turing machines, which are very specific objects. To simplify: unsound systems are not talking about N, but about some other non-standard numbers. However, they all do talk about the same Turing machines. –  julian fernandez Feb 1 '13 at 4:58
    
julian: I see that I did not get to the heart of your question; thank you for expanding. I've edited my answer to give one possible response. –  Nick Thomas Feb 1 '13 at 5:12
    
Additionally, I would certainly agree (and I think most would) that nonstandard models do not have "the same status" as the standard model. Your question was why we consider them at all, and I think there are decent reasons for that; but I think nobody considers them to be "just as good" as $\mathbb{N}$. –  Nick Thomas Feb 1 '13 at 5:16
    
Nick, thanks for your expansion, your answer makes some sense but I would like to read again some material before continuing with this. The reason is that I am not sure that Post theorem allow to reinterpret Turing machines in some non-standard way. But I am probably wrong. I'll do it tomorrow, I need to get to sleep now. Thanks again –  julian fernandez Feb 1 '13 at 5:23
show 9 more comments

For the title question, after mulling it over, I would say that the reason we don't talk about unsound systems of deduction because we adapt the meaning of "interpretation" and "model" to fit the deductive system.

Inconsistency, on the other hand, is a drastic failure of classical logic due to the principle of explosion (and such theories have no models). (there are paraconsistent logics, however)

Since the other answer didn't say so explicitly or in the comments, non-standard models of arithmetic are not models of unsound systems. They are (generally) models of a consistent theory in ordinary first-order logic; in particular. They are non-standard because they are not isomorphic to the "intended" model the theory was designed for.

share|improve this answer
    
I agree with you on all you said. But my question was motivated because I saw a contradiction on the particular case of unsound extension of PA, which would prove untrue statements about Turing machines, which to me meant that such formal systems could not support meaningful models (structures). And I gave Turing machines a special status, because I could not imagine a non-standard interpretation or structure for a TM.... –  julian fernandez Feb 8 '13 at 2:03
    
CONTINUATION:...but with the transfinite explanation I realized I was wrong, that you can still think of a consistent structure that satisfies the statements about halting problems for standard TM's without introducing a contradiction. –  julian fernandez Feb 8 '13 at 2:04
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.