Talk:ω-consistent theory

lowercase

Samuel Wantman left an edit summary asking why "Omega" shouldn't be capitalized. I'm not claiming it's completely clear-cut, but here's my argument: Ideally the article should be at ω-consistent theory, with the lower-case ω. If we use the Greek letter, then the capitalization is very important; the phrase "Ω-consistent theory", though (as far as I know) having no standard meaning, could imaginably be taken to mean "consistent in Woodin's Ω-logic", an immensely stronger notion.

The part that's a little less than clear-cut is the association "Omega/Ω :: omega/ω". This is standard, though, to anyone who uses TeX. --Trovatore 17:05, 31 August 2006 (UTC)

I've changed the note to reflect that ω-consistent theory is the ideal name. -- Samuel Wantman 18:49, 31 August 2006 (UTC)

No, it isn't. Gene Nygaard 02:05, 3 December 2006 (UTC)

move request

ω-consistent theory is the standard name used in the literature. The reason I didn't use it when I started this article is that it would have rendered "Ω-consistent theory", which is quite wrong. However {{lowercase}} now provides a javascript hack to render the title correctly in javascript-enabled browsers. --Trovatore 06:59, 25 November 2006 (UTC)

This does not look controversial to me, so I moved the article. -- Jitse Niesen (talk) 08:19, 25 November 2006 (UTC)

Can a similar hack work for the talk page? It's kind of weird that they don't match now. -GTBacchus^(talk) 08:26, 25 November 2006 (UTC)

Answered my own question: it seems to work. -GTBacchus^(talk) 08:27, 25 November 2006 (UTC)

Still rendered as "Ω-consistent theory" when I click 'history' or when I'm editing this page now. Confusing like woah. Haukur 09:05, 25 November 2006 (UTC)

Yes, that is unfortunate. I'm trying to gather support for a developer change that would turn off the automatic uppercasing when the first letter of an article name is non-Latin (or, at the very least, if it's Greek). Haven't seen much movement yet. Maybe you'd like to comment at Wikipedia:Village pump (technical)#Uppercasing of non-Latin letters. --Trovatore 05:26, 26 November 2006 (UTC)

Moving the page for the sole purpose of making the wrongly placed "lowercase" template justified is sheer nonsense. Gene Nygaard 02:06, 3 December 2006 (UTC)

And, lest anybody is dumb enough to be fooled by the Java-script shenanigans with the display on this articles page, just go follow the links to the one real non-stub category in which this article can be found, and come back and tell us exactly what sort of nonsense you see when you get there. Not only what you see for the article name, but also what letter you find it listed under.

Just where the fuck do you find it, anyway? Off in oblivion, somewhere after the Z.

I'll hold off on fixing the sort key properly until at least a few of you get a chance to see how you are squirreling away this information, hiding it so that is is unfindable. Gene Nygaard 02:13, 3 December 2006 (UTC)

Thanks for the reminder about search keys, Gene. Those are way too often overlooked, and it's good that you're conscientious about it. -GTBacchus^(talk) 02:37, 3 December 2006 (UTC)

One of the biggest problems is that users of this template get hoodwinked into some erroneous belief that it is something other than a gimmick that just works on the display of this one page at the most, and often not even that. Gene Nygaard 02:51, 3 December 2006 (UTC)

The purpose of the move was not at all to justify the "lowercase" template. I don't like that template at all when it's unnecessary, and even when it is necessary, it's still a hack.

Rather, the purpose was to put the article at its correct name. Using "omega", spelled out in Latin letters, is just wrong. I challenge you to find any logic text with the phrase "omega-consistent" or "omega-consistency" in its index. You won't find it. --Trovatore 02:40, 3 December 2006 (UTC)

I have a better idea. I challenge you to show me any index from any book which indexes this concept after the Z's. Gene Nygaard 02:48, 3 December 2006 (UTC)

Ok, what we learn from this pair of challenges is that we don't have the ideal situation here, so something has to give. Is it worse to have the article titled and indexed as "omega-consistent theory", which is wrong, or to have the title show up correctly while it's indexed as "Ω-consistent theory", which is also wrong? I prefer having a correct title show up at the top of the page, by whatever kind of shenanigans. Either way, it should certainly be indexed under the letter 'O', but I don't believe anybody's arguing that it should come after 'Z'. That was the result of carelessness, and we're lucky to have Gene here to catch us on that. -GTBacchus^(talk) 02:55, 3 December 2006 (UTC)

It would be trivial to index it under "O" by using the piping trick, if that were the correct thing to do. I'm not convinced that it is; I think non-Roman starting characters such as ω should be indexed separately. —David Eppstein 04:58, 3 December 2006 (UTC)

I agree. In many cases, if you wanted to interleave Greek letters with the Latin ones, it's not clear which one you would use, or the correct result is non-obvious. An article that starts with φ would go under F, I suppose, but where do you put one that starts with χ? Under H, seems to be the most defensible answer, but not too many people will think of looking there. And there's simply no letter that corresponds to Ψ or θ. --Trovatore 05:18, 3 December 2006 (UTC)

I don't know. My analysis books index "σ algebras" under 's', "ε-close mappings" under 'e', "ν*-measurable sets" under 'n', etc. I'd like to see a book that indexes concepts beginning with Greek letters separately from those starting with Roman letters. As for Ψ and θ, they're alphabetized as "Psi" and "Theta". -GTBacchus^(talk) 09:37, 3 December 2006 (UTC)

Of course they are. Trovatore's suggestion of φ under f rather than under p or χ under H rather than under c is silly. And even if he/she doesn't "find any logic text with the phrase 'omega-consistent' or 'omega-consistency' in its index" but does somehow find "ω-consistent" or "ω-consistency" in the index, the latter will be found in the very same place in the index that the former would be found. Gene Nygaard 11:41, 3 December 2006 (UTC)

"He" of course -- otherwise I'd be Trovatrice, obviously. On looking through a couple of indices, it does seem that Gene is correct about how these things are usually indexed. I don't think it's the most logical way, as it seems to give undue weight to the Latin spellings of the letters, but it does have the advantage of being easy to remember, I guess. We should probably have a WP-wide discussion as to how these things should be indexed (or at least math- and physics-wide; it seems unlikely to come up in the rock album and pornstar categories). --Trovatore 18:17, 3 December 2006 (UTC)

Actually, it is more likely to come up in rock album categories, at least. But that is not only the way it is done (and for that reason alone not something for Wikipedia to do differently), but it is the logical way to do it. Actually, this is a lot like "pascals" and their symbol "Pa". Just as many publications will use both "Pa" and "pascals", there are many which would use both "ω-consistent" and "omega-consistent". It isn't an either/or proposition. Gene Nygaard 19:12, 3 December 2006 (UTC)

Have we seen an example where a publication uses "omega-consistent"? At any rate, I've got a copy of Cohomology of Groups by Kenneth S. Brown in front of me, and I noticed something odd about its index. The regular index puts both ∂-functor and δ-functor (in that order) under 'D', which seems normal to me. Then, the index of symbols, which is also alphabetical, alphabetizes 'Γ' and 'γ' under 'G', 'ε' under 'E', 'ρ' under 'R', and 'Σ' under 'S', but... for some reason 'χ' is alphabetized as an 'X'. Odd, eh? -GTBacchus^(talk) 19:24, 3 December 2006 (UTC)

Leblanc, Roeper, Thau, Weaver, "Henkin's Completeness Proof: Forty Years Later", Notre Dame Journal of Formal Logic,, vol 32, no. 2, Spring 1991 [1] Gene Nygaard 19:46, 3 December 2006 (UTC)

OK, you got one. I think at any rate you'll find it's less common. Even Hofstadter uses "ω-consistent"; I checked. I thought he'd be among those more likely to say "omega-consistent", being a popularizer.

I disagree that alphabetizing by the Latin names for letters is the logical way to do it. The Latin equivalent of the letter φ is not the word "phi"; that's just the name for the letter. Rather, the Latin equivalent of the letter φ is the letter f. Most Greek letters have more-or-less equivalent Latin letters, but θ and ψ clearly don't, χ and ξ are problematic, ω and ο map to the same letter, and ι maps to two different letters (i and j). --Trovatore 20:05, 3 December 2006 (UTC)

But it isn't being used as a letter. It is being used as a symbol. The φ isn't pronounced "f"; it is spoken as "phi". The "omega" here is likewise spoken that way; it isn't merely a letter, a component used to construct words and being part of the pronunciation of those words, but rather a symbol. Gene Nygaard 20:26, 3 December 2006 (UTC)

Yes, of course it's being used as a symbol. But "omega" is not the symbol; it's the name for the symbol, the same way "zee" (or "zed" if you prefer) is the name for the letter z. You wouldn't write "the zee-axis", and similarly you shouldn't write "omega-consistent", not if you have a choice. --Trovatore 20:32, 3 December 2006 (UTC)

The difference with z is that it is itself an English letter. We do, however, write em dash and en dash, and delta-vee is quite common (13,100 google hits). That's just scratching the surface, of course. Gene Nygaard 03:51, 4 December 2006 (UTC)

And "wye delta" (43900 Google hits). There is, of course an inherent clash in mixing together symbols and spelled out words. It's like writing "coulombs/kg", something expressly against the rules of many style guides.[2] Gene Nygaard 04:07, 4 December 2006 (UTC)

The fact that z is itself an English letter makes no difference. We have Unicode now. Learn it, use it, love it. --Trovatore 06:39, 4 December 2006 (UTC)

Ok, so... I've got a reliable source that indexes Greek-letter words along with corresponding Roman letters, where the correspondence is in whatever logic puts 'chi' in the 'X' section. What other kind of examples have we got in sources regarding indexing of words beginning with Greek-letter symbols? Examples involving ω-consistentcy are preferable to the other kind. Smoryński's Self-reference and Modal Logic might be a good place to start, being the article's sole reference. -GTBacchus^(talk) 07:22, 4 December 2006 (UTC)

Yes, I know It's Weaker

That's why it was phrased so carefully, as a rule of thumb, not as an equivalent. The example on this page is then not an example of omega inconsistency, just of unsoundness. You should put a real example of omega inconsistency. I was going to put that up today, but you reverted my last, carefully written comments.Likebox 16:52, 16 October 2007 (UTC)

A rule of thumb for what: for recognizing ω-consistent theories? Then a suitable rule of thumb is "all decent theories are ω-consistent". [Unless they are theories of nonstandard analysis. 12:45, 18 October 2007 (UTC)] Your "rule of thumb" was not only inadequate (as it mixed together quite different consistency principles), but also significantly more complicated than the simple and perfectly clear definition of ω-consistency itself, which defeats the whole purpose of a rule of thumb. That's why I reverted it.

There is nothing wrong with the example, it is a good example of ω-consistency. $\Sigma _{1}$-ill theories are ω-inconsistent, it's the converse which breaks (badly). Nevertheless, I've added a $\Sigma _{1}$-sound example as well for comparison. I've also included more info on other soundness-based principles, as well as ω-logic, to make it more clear where ω-consistency stands. Like it or not, ω-consistency does not have any computational explanation, so please do not try to make one up by confusing it with other properties.

By the way, was 71.176.115.195 you, logged out by accident, or is it a coincidence? EJ 13:21, 17 October 2007 (UTC)

I meant, yes, 71.176.115.195 IS me...

No-- just bad internet service! Sorry, I think it's clear when it is me. The only reason I put it up is because I wanted to link to Godel's incompleteness theorem, and there the example is sigma-one-unsound, and that's the essential point. Since Godel introduced the concept, he had sigma-one-soundness in mind, not necessarily oracle-soundness. What you did is fine by me though.Likebox 18:59, 17 October 2007 (UTC)

Yes. I think it's best to use $\Sigma _{1}$-soundness directly when stating or explaining the first incompleteness theorem, and to avoid ω-consistency altogether (or to reduce it to a historical footnote). -- EJ 12:45, 18 October 2007 (UTC)

Wait a second, I just noticed you said that $\omega$ consistency does not have a computational explanation. That's not true. It's just that you need to add an oracle to your computer. That's the arithmetic-hierarchy/Turing hierarchy equivalence of Post. There's nothing in mathematics which does not have a computational explanation.Likebox 19:01, 17 October 2007 (UTC)

But you said that in the article too. Thanks. Wow. nice job!Likebox 19:07, 17 October 2007 (UTC)

Thanks.

I don't quite agree with the oracle business. If you reformulate "an arithmetical formula" as "a Turing machine (or whatever) with an oracle from the arithmetical hierarchy", it does not really explain anything. It merely shifts the complexity of the problem to the oracle, and wraps it in an additional layer of stuff. It may superficially look like computation, but the real thing is still happening in the oracle. It may be kind of useful to do this for restricted classes of formulas like $\Sigma _{n}$ (because the halting problem provides an existential quantifier for free, which reduces the complexity by one level), but in the general situation it is IMHO pointless. -- EJ 12:45, 18 October 2007 (UTC)

Pointless, meaning mathematically equivalent, I agree. Pointless meaning philosophically equivalent, not exactly. They are somewhat different sources of intuition about what kind of arguments to make in the future. You don't have to think of the oracle as a computer. The oracle can be approximated by a large random-access CD-ROM with imperfect data which has been previously computed by someone else. So if you want to look at the properties of finite computations you will have different ideas when thinking about oracles vs. thinking about classes of formulas. But, philosophical quibbles aside, I think all the article is very good now. I would like to translate your sigma-one sound omega-inconsistent statement into an oracle computation, though, even though it's "pointless".Likebox 14:51, 18 October 2007 (UTC)

Notation

The notation $\Sigma _{n}^{m}$ is used without definition. Can someone please provide one? -- Hairy Dude (talk) 18:02, 16 November 2007 (UTC)

There is a prominent link to the arithmetical hierarchy in the article. Just click it. -- EJ (talk) 10:05, 20 November 2007 (UTC)

The symbolism always be defined when first used, not later -- otherwise there's no associative relationship (as happened in my reading of this. So I came here to the talk page and found Hairy Dude's complaint). So I added a footnote. Maybe someone can word-smith it; put in the link right there, for example. Bill Wvbailey (talk) 13:28, 25 September 2008 (UTC)

Numerically insegregative

As currently phrased in the article, it would seem that the property of being "numerically insegregative" introduced by Quine is a synonym of "ω-inconsistent". But it is actually a stronger property, meant to address something Quine viewed as unsatisfactory with the concept of ω-inconsistency, which he considered misleading. The precise definition of Quine's revised concept is rather complicated, and implies that the logic underlying the theory cannot express, in some sense, the predicate "n is a natural number".

The result by Smoryński mentioned later on ceases to hold if "ω-consistent" is replaced by "numerically segregative". Thus the identification of the concepts is problematic.

Since Quine's revised concept appears not to have caught on – I can't find any references to it other than in Quine's publications or reviews of them – and is rather abstruse, I propose that the references to it be omitted. Alternatively, should someone (who really understands the issues involved!) feel inclined to produce the necessary prose, there could be a separate section stating something like that Quine considered the concept of ω-inconsistency misleading and came up with a stronger alternative.  --Lambiam 16:01, 20 May 2008 (UTC)

I would agree completely, were it not for your taking the opportunity to slight me. The term appears to have at least some life outside of reviews of Quine: link. It appears to be a consensus in the literature that this is a more appropriate term for this concept. If it actually describes a subtly different concept, then I would say that it doesn't need a separate article, but rather, as you say, there should be a section on it. Do you feel competent to that, or should I work on it?

Pontiff Greg Bard (talk) 20:45, 20 May 2008 (UTC)

Should I feel slighted by the ascription to me of taking opportunities to slight others? When I searched for "numerically segregative" on Google books, the Tymoczko book did not show up.[3]

I don't understand the reasoning behind Quine's complaint that the definition and concept of ω-inconsistency are misleading. In particular I don't get what he means by "failure of existence of needed classes". After all, whether the class comprised of precisely the natural numbers exists should be independent of any logical system. If it is the case that the logical characterization of N in a system "thus afflicted" can sometimes be repaired, as Quine suggests, how does this formal manipulation cause a class to pop into existence that failed to exist before? I think that if this is described in a separate section, it should be done by someone who does understand Quine's reasoning. I maintain, though, that the issue is abstruse and of minor importance.  --Lambiam 23:22, 21 May 2008 (UTC)

ω-rule

It looks to me that the ω-rule makes the theorems of T no longer recursively enumerable. E.g. suppose H is a Turing machine that does not halt, and $P_{H}(x)$ is the predicate "H does not halt at step x". Since P_H is a theorem at every x (provable by running H for that many steps), "H does not halt" is a theorem of T under the ω-rule. The ω-rule gives T a built-in halting oracle. Is this worth remarking on in the article? —Preceding unsigned comment added by 67.117.147.133 (talk • contribs) 19:38, 25 October 2008

Well, your argument doesn't seem to completely close the deal, since the true statements of the form "H halts" are in fact recursively enumerable. I think your conclusion is true; probably you just need to work a tiny bit harder to get it.

Oh, whoops, sorry, you're talking about "H does not halt". Sure, that sounds right. I think you can actually do quite a lot better. --Trovatore (talk) 20:49, 25 October 2008 (UTC)

I doubt this is the right place for detailed discussion of the ω-rule. Fundamentally ω-consistency is a lot weaker than consistency with the ω-rule or the property of having an ω-model (not sure of the relationship between the latter two — may not be very hard to figure out; I just don't know off the top of my head). --Trovatore (talk) 20:45, 25 October 2008 (UTC)

bad definition?

In the definition section, it says "T also proves that there is some natural number n such that P(n) fails." Shouldn't it simply say that $\exists x\,\neg P(x)$? After all, this x can't can't actually be a natural number due to the soundness theorem. And besides, "natural number" isn't expressible in first order logic anyway. --Jdvelasc (talk) 07:52, 10 February 2009 (UTC)

$\exists x\,\neg P(x)$ is a formalization of the statement "there is some natural number n such that P(n) fails". The two say the same thing. — Emil J. 10:50, 10 February 2009 (UTC)

Sorry for the delay. And no, as I stated in my note, $\exists x\,\neg P(x)$ is most definitely not a formalization of "there is some natural number n such that P(n) fails" since that statement cannot be formalized in first order logic. The formalized sentence merely says that something in the domain fails to have P. As I stated, it can't be a natural number because of the soundness theorem (since we can prove of each natural number that it does have the property P, then in fact each natural number does have the property P in any model of the theory). So the element that fails to have P must be a non-standard element. By the incompleteness theorems, there is no first order theory of arithmetic that prevents non-standard elements from being in the model of the theory. —Preceding unsigned comment added by Jdvelasc (talk • contribs) 00:22, 1 March 2009 (UTC)

The paragraph in question begins with, "If T is a theory that interprets arithmetic (that is, there is a way to understand some of its objects of discourse as natural numbers), then...". Thus, for the rest of the paragraph, the objects in the domain can reasonably be called "natural numbers." I am very used to seeing this sort of abuse of language in prose on nonstandard models of arithmetic.

Of course you are right there is no standard model of an ω-inconsistent theory... which is why it is called ω-inconsistent. Under the intended interpretation of its syntax, the theory proves that a number with a certain property must exist, while individually proving that each particular number is not an example.

I don't like the idea of replacing the prose with a formula (the rest of that section is in natural language). Would it satisfy you if we replace "natural number" with just "number"? — Carl (CBM · talk) 04:15, 2 March 2009 (UTC)

Yes, Jdvelasc, it's a little hard to figure out what your objection actually is here. If this sentence is not a formalization of what it's asserted to be a formalization of, then there just is no such thing as a formalization in first-order logic. No first-order sentence can fix its interpretation.

Your original claim is that "x can't be a natural number due to the soundness theorem". But that's not so — the soundness theorem says only that there is really no such natural number x. It does not refute the possibility that the theory T happens to prove that there is such a natural number. T may prove false things (and, if it's omega-inconsistent, must prove false things). The soundness theorem does not refute that, because the soundness theorem applies only if all the axioms are true, and some of the axioms of T may (in fact, in this case, must) be false. --Trovatore (talk) 07:50, 2 March 2009 (UTC)

(Actually, I was making some unstated assumptions in the above; namely, that P is quantifier-free or has only bounded quantifiers, and that T proves only true formulas of that sort. Without some such assumptions, the soundness theorem does not say even what I attributed to it, and Jdvelasc's claim is still harder to figure out. But let's make those assumptions for the sake of argument, because the points to be made are easier to elucidate then.) --Trovatore (talk) 08:23, 2 March 2009 (UTC)

I think that Jvdelasc's objection should be taken seriously — there is a non-trivial difference between the two definitions. My recollection of the definition of omega-inconsistency is that the theory doesn't have $\exists n.\phi (n)$ and then for each natural number $n$ also have $\neg \phi (n)$, which essentially equivalent to Jvdalesc's formulation. We should maybe look at a few canonical texts to see what how they define it. I pulled down five volumes from my bookshelf, and was surprised that none of them contained definitions. I have a PDF of Schütte's Proof theory somewhere, surely he will not let me down... — Charles Stewart (talk) 12:31, 2 March 2009 (UTC)

The definition is not the issue. Everybody agrees that the definition asks for provability of $\exists n\,(N(n)\land \phi (n))$ in the theory. The only issue is that Jvdalesc does not understand the standard terminology in logic, where objects dealt with in a theory of arithmetic are routinely called "natural numbers" in the theory, and insists that this label be only used for natural numbers of the metatheory. If you say that "T proves that there is some natural number n such that <foo>", it is clear from this context that "natural numbers" refers to natural numbers of the theory T, not of the metatheory, because otherwise the statement does not make sense, and likewise any other concept appearing in <foo> refers to a formal concept in the language of T, not in the metatheory. "T proves that there is some natural number n such that P(n) fails" is a perfectly standard way of expressing $T\vdash \exists n\,(N(n)\land \neg P(n))$ in words. And to reply to Carl: no, replacing "natural number" with "number" won't do, because the language of the theory T may also include other kinds of numbers, such as rational, real, or ordinal numbers. — Emil J. 12:57, 2 March 2009 (UTC)

Thanks, I was just looking at Charles' suggestion farther down and realize that the article is written in such a way that T could be very general. I don't think there would be much chance of confusion between "number" and "natural number", but I would also have written "natural number" if I had written that part myself.

Re Charles, I do take the suggestion seriously; I just don't like to replace the prose with a formula. I will look at the text in a little while and see if I can copyedit it some, taking EmilJ's note into account. — Carl (CBM · talk) 13:05, 2 March 2009 (UTC)

Definitions of omega-consistency

Found one! George Boolos, in his "Fundamental theorems of provability logic" afterword to Logic, Logic and Logic, says:

one can define n-consistency to mean that all $\Sigma _{n}^{0}$ closed formulas that are provable are true, and omega-consistency to mean n-consistency for all n.

It would be nice to know what Gödel's original definition was. Anyone have access to the collected works? — Charles Stewart (talk) 12:40, 2 March 2009 (UTC)

Now that's a completely different (and rather nonstandard) meaning of omega-consistency, which is normally called arithmetical soundness. It is inconsistent with both the article and Jdvelasc's suggestion, so it is irrelevant to the discussion. — Emil J. 13:01, 2 March 2009 (UTC)

I will look at a few books once I am in the office today. However, the "standard" definition I am used to is the one presented in the article – a theory is ω inconsistent if it proves that there is a natural number with a specific definable property, while simultaneously proving (individually) that each particular number does not have the property. — Carl (CBM · talk) 13:05, 2 March 2009 (UTC)

I looked at Boolos' book, and it really is just an idiosyncratic definition. — Carl (CBM · talk) 15:15, 3 March 2009 (UTC)

Just to reiterate for those who are apparently confused about what my objection actually is, my objection is that the definition given in the text is not actually the definition of w-consistency. I would argue that it should not be the definition since then it would mean that any w-consistent theory must actually be inconsistent since any model of the theory would have to have all the natural numbers having some property P and at least one of them not having it.

If you are wondering about printed definitions of omega-consistency, there are almost certainly going to be formalized and not written in English. In Godel "On formally undecidable..." (page 173 of collected works volume 1) omega consistency is defined in purely formal terms that requires a large number of definitions to understand. It starts: k is said to be w-consistent if there is no CLASS SIGN a such that (n)..." It means that there is a particular sentence which is not a consequence of the theory. Nothing like "natural number" (or the predicate "N" suggested by Emil) is anywhere in sight. For an easily readable definition, look at Boolos "The Logic of Provability". I don't have it in front of my right now, but I am about 99% positive it says exactly what Charles Stewart suggests which is there is a formula phi with one free variable such that for each natural number n, phi(n) is a theorem, but that $\exists x\,\neg \phi (x)$ is also a theorem. The only thing I am not positive about is whether the negation is on the individual phi(n)s or on the existential sentence. And that may be the opposite of the Godel anyway though they are obviously equivalent. Tarski (1933 on "some observations on the concepts of w-consistency...") also defines w-consistency, but in a different way than Godel though he claims it is equivalent. Again, nothing like "natural number" in sight.

I agree that a naive reader is easily confused by the English prose since it seems to imply that you can prove something that is false. This is definitely not the case. And by the way, I definitely do not qualify as a naive reader. Now, to counter a few of the comments above, yes, the text does say "some of the objects of discourse can be understood as natural numbers". This is correct. However, if the theory is w-inconsistent, not all of them can be. It is true that often logicians will talk about "natural numbers" having bizarre properties because a theory might prove they do, but this is not universal and other speakers/writers are much more careful. It is also common to talk about "non-standard elements" or "non-standard numbers". Usually, if a theory is w-inconsistent, it would not be called a theory of arithmetic anyway. As for the claim about soundness, given the context, it is not really appropriate to talk about a theory proving false things. Rather, the soundness theorem simply asserts that if you can prove A, then A will be true in any model of the theory (even if there are none). The soundness theorem doesn't apply only if the axioms "are true" by which I guess you must mean "true in the intended interpretation with the domain being the natural numbers, "+" meaning "plus", etc.". The soundness theorem is just fact about first order logic. It is true that I was using "natural number" to mean the actual natural numbers in the metatheory, and so it is not correct to say that T proves that there is such a number unless T is actually inconsistent (which from context, it is consistent). If we restrict "natural number" to any element in the domain of any model of the theory, then things are way to bizarre. But even so, if we make this restriction, it is simply not true that T proves anything that is false. After all, in that case there are natural numbers without the property P. But as I said, this is definitely the wrong way to interpret "natural number." For example, the first part of the definition says that for any natural number n, the theory proves P(n). But this would be false unless we are talking about the real natural numbers in the metatheory. So at the beginning of the definition, we are definitely talking metatheory, so how could the reference change mid-sentence?

And just a last comment, Emil mentioned that we can't replace "natural number" with "number" since the language of the theory may include other things like the reals. There are two ways to go here. The article indicates that the definition only applies to theories of arithmetic which I take the mean that the intended interpretation is the natural numbers. So no, no reals. But imagine a purely formal definition of a theory that allows for things like reals. Now we have the ordered field axioms or whatever being w-inconsistent. Great - but now it is really absurd to stick to saying that whatever T talks about can be called a natural number. The order field axioms most definitely do not say that there is a natural number which is the square root of two. Joel Velasco --Jdvelasc (talk) 20:02, 3 March 2009 (UTC)

As for a positive suggestion, if we want to avoid formalization and stick with metatheory, how about changing some of the instances of "natural number" like so: ... but T also proves that there is some element of the domain x such that P(x) fails. This may not lead directly to an outright contradiction, because T may not be able to prove for any specific value of n that P(n) fails, only that it fails for some element of the domain. --Jdvelasc (talk) 20:17, 3 March 2009 (UTC)

I apologize, but I still don't quite have a solution to your objection nailed down (for reasons I will explain). I am trying to figure it out, however. And I do agree that the definition in the article should be improved. I made a temporary patch by adding "standard" and "nonstandard", as I proposed above, but more large scale changes are needed.

We are having terminological problems here, so let me sketch a glossary that we can try to use. I use the term "theory of arithmetic" for any theory whose language is the language of arithmetic, and which includes some small fragment of PA (for example, which includes PA^-). A theory of arithmetic which happens to be satisfied by the standard model is a "true" theory of arithmetic. The standard natural numbers are the members of ω (in the metatheory). The term "natural number" can refer to either a standard natural number, or to any element of any model (standard or not) of a theory of arithmetic. Thus if a theory of arithmetic T proves $\exists xP(x)$, then it proves there is a natural number with property P, and vice versa, simply by linguistic convention that the objects in the domain of a theory of arithmetic are called "natural numbers". This does not necessarily mean that there is a closed term t such that T proves P(t). This linguistic convention is analogous to the natural-language handling of provability predicates: if T proves Bew(x), this means that T proves (formula) x is provable (trivially) – but it does not mean there is a closed term that T proves to be a derivation of x.

There are several things that are complicating the presentation of the article. First, the presentation in the article is not limited to theories of arithmetic; it is describing an arbitrary theory that interprets (a fragment of) arithmetic. Thus when I read in the article, "there is a way to understand some of its objects of discourse as natural numbers", I take this to mean there is a predicate N and any element of the domain satisfying N is regarded as a natural number, whether or not this element corresponds to a standard natural. However, you may be reading that quote to mean that only some of the elements satisfying N are regarded as (standard) natural numbers. So the handling of the interpretation ought to be cleaned up.

Second, the article does not explain the difference between standard and nonstandard natural numbers, which is the key point (in the end) about ω-inconsistent theories.

Third, if you object to the use of the term "natural number", you may object to other things in the article, such as "Con(PA) could be of the form "For every natural number n, n is not the Gödel number of a proof from PA that 0=1"." I think your argument would say that Con(PA) cannot actually say this because it cannot quantify over standard natural numbers.

Because of these things, I think we should come to some overall agreement on how to present things, and then I will be happy to make a try at doing the actual writing, which you can then clean up as desired. I want to think for a while and I will make a proposal later. — Carl (CBM · talk) 20:47, 3 March 2009 (UTC)

I'm sorry, I still don't get Jdvelasc's objection. I don't think adding standard and nonstandard helps anything. An ω-inconsistent theory does prove that there is a natural number such that yada yada yada; this is completely standard usage. What the theory proves, of course, is not true, but that doesn't change the fact that the theory proves it. --Trovatore (talk) 20:50, 3 March 2009 (UTC)

I empathize with the objection, I just want to think about how to rephrase things. Right now the article says,

"for some property P of natural numbers (defined by a formula in the language of T), T proves P(0), P(1), P(2), and so on (that is, for every standard natural number n, T proves that P(n) holds), but T also proves that there is some (necessarily nonstandard) natural number n such that P(n) fails."

At least I think this is an improvement over the previous text,

"for some property P of natural numbers ... for every natural number n, T proves that P(n) holds, but T also proves that there is some natural number n such that P(n) fails."

which is somewhat awkward. — Carl (CBM · talk) 20:58, 3 March 2009 (UTC)

No, I'm afraid I don't agree. The theory T doesn't know from standard or nonstandard. It proves that there's a natural number with a certain property. It happens to be wrong. Why can't we just say that? --Trovatore (talk) 21:16, 3 March 2009 (UTC)

I would be fine with something like

T proves that there is a natural number x satisfying P, but also proves $\lnot P({\dot {n}})$ for each n ∈ ω.

This is one of the several possible ways to fix things. Another difficulty I didn't mention, but J. Velasco has mentioned, is that the article presently doesn't distinguish between numbers and terms. — Carl (CBM · talk) 21:20, 3 March 2009 (UTC)

Well, I disagree with User:Trovatore that it is standard to say that an w-inconsistent theory proves weird things about "natural numbers" but I accept that I may be wrong on this. But I have definitely read books and papers on non-standard models of arithmetic where it is common to distinguish between the elements of the model that are the natural numbers (reachable from zero by a finite number of applications of the successor function) and those elements that are non-standard. But maybe these are the rare ones and more common in philosophy than in mathematics. And again, I don't like saying that some w-inconsistent theory proves things that are not true. It proves things about the elements in any model of that theory. As for the claim about Con(PA) I do object to this since it is at best misleading for exactly the same reasons as the definition we are debating. The second incompleteness theorem entails that PA cannot prove Con(PA). But PA does prove of each natural number that n is not the godel number of a proof of 0=1. Assuming PA is consistent, it does not prove for all x, x is not the godel number of a proof of 0=1. That is a much better way of saying it. The second example is much better. The parallel option is to say that PA* proves that there is a natural number equal to c. Doesn't this sound crazy? PA* proves no such thing. Nor does it prove anything false. It merely proves that there is some element in the domain that is not equal to any natural number. --Jdvelasc (talk) 21:25, 3 March 2009 (UTC)

You don't like saying that ω-inconsistent theories prove things that are not true. Nevertheless, it is true that ω-inconsistent theories prove things that are not true. This is completely standard language.

The normal convention in mathematics is to talk like a Platonist whether you actually are or not; this just saves an immense amount of trouble. Readers may as well get used to this. In the case of the natural numbers in the context of proof theory, it's especially silly to be squeamish about this, because statements like "such-and-such is provable" have exactly the same status as statements like "there is a natural number such that...". --Trovatore (talk) 21:31, 3 March 2009 (UTC)

You are right and perhaps I said something stronger than I meant. Everybody that I know of talks about the true theory of arithmetic with statements about numbers that are true or false independent of any axioms. This is less true in Set Theory (where sometimes people say that there just is no fact about the Continuum hypothesis or whatever). But the natural thing to say then is that an w-inconsistent theory is just not a theory of arithmetic (it is ccording to User:CBM's definitions above but it is not a "true" theory of arithmetic). But I am a bit confused what this has to do with our debate now. Surely the Platonist doesn't think that PA* or whatever actually proves anything at all about natural numbers. Only true theories of arithmetic can prove anything about the natural numbers. It seems to me that it is an extreme conventionalist position which says that the natural numbers are just whatever this theory we happen to be looking at says they are. But even if I am wrong and it is perfectly correct and normal to say that T says blah blah about the natural numbers, isn't it also equally correct to say that T says blah blah about some element of the domain (or whatever fix somebody proposes) and isn't it correct that this might help some naive readers (and I think some more experienced users) understand the issues better? What exactly is bad about changing this to make it more clear? Or do you think it is less clear or actually wrong now? --Jdvelasc (talk) 22:47, 3 March 2009 (UTC)

Well, here's my point: There's no predicate in the language of arithmetic that says "n is a nonstandard natural", so it doesn't make sense to me to say "T proves that there is a nonstandard natural such that...". You can't even state that in the language of T.

I don't understand why you don't want to state forthrightly that such theories simply prove false things, that they are incorrect theories. Of course that doesn't make them useless; they may have applications. Nevertheless they have false axioms, so they prove false theorems, among which are that there is a natural number such that yada yada yada. --Trovatore (talk) 02:15, 4 March 2009 (UTC)

Metatheoretical, philosophical, and expositional issues aside, is there a problem with the article using exactly whatever definition Gödel actually used? That way, at least, we can give a nice, heavyweight source for the definition. — Charles Stewart (talk) 08:33, 4 March 2009 (UTC)

Well, I don't know — Goedel was hardly the last mathematician to use the notion. I would tend to favor definitions used in the contemporary literature. Goedel is one of my all-time mathematical heroes, but his notation could at times be a bit awkward (I don't know if that's the case for ω-consistency but it wouldn't surprise me).

That does bring up a side point. The surprising and unusual definition you found in Boolos should perhaps be mentioned somewhere, although with a clear warning that it is not how the terminology is used today. Otherwise readers who have read Boolos, but are not familiar with the contemporary literature, might have a hard time reconciling what they read. --Trovatore (talk) 08:46, 4 March 2009 (UTC)

Wrt. Gödel: Jvdalesc said earlier that Gödel's 1931 definition is long and complex. Section 2.6 of Martin Hirzel's translation gives it[4] and I think it is not too complex for the article given its historical importance, but it should certainly not be the first definition because the definition is internal to his numerical encoding and not equivalent to the usual notion. So how about a definitions section that can treat such rival concepts? It seems to be where Trovatore's side point is leading. — Charles Stewart (talk) 09:51, 4 March 2009 (UTC)

I don't think Gödel's definition is a "rival" concept, nor that there is much disagreement about what an ω-consistent theory is. The definition in Gödel's paper looks to me to be just the same as what is in the article, once you move to modern logical notation. I looked at several other references the other day (Handbook of Mathematical Logic, etc) and they were all very consistent about the definition.

Boolos uses the dual definition, but we have already covered this $\Sigma _{k}^{0}$-soundness in the article as well, and I don't think it's worth dwelling very long on a single idiosyncratic author. Indeed, just after his definition, Boolos tries (I think very cryptically) to explain how his definition is related to the ω-rule. — Carl (CBM · talk) 13:22, 4 March 2009 (UTC)

I don't care much about the Boolos definition, but there are two points outstanding. First, I want the article to give a reference for the precise definition it uses, and be explicit about differences that mathematicians don't tend to care about but logicians do, such as whether you need to appeal to soundness to show the equivalence of two formulations. Secondly, Gödel's definition is not equivalent to the article's since different theories of arithmetic have different $\Pi _{1}^{0}$-theories. — Charles Stewart (talk) 15:15, 4 March 2009 (UTC)

According to the link you provided above, Gödel's definition is as follows: a class of formulas κ is not ω-consistent iff there exists a class-sign a such that

${\Bigl (}\forall n.subst(a,v,number(n))\in Conseq(\kappa ){\Bigr )}\land not(forall(v,a))\in Conseq(\kappa ).$

To decipher the notation, a "class-sign" is defined as a formula with one free variable of the natural number sort, Conseq(κ) is the deductive closure of κ, number(n) is (the Gödel number of, the same for the other functions below) the numeral for n, subst(x,v,y) is the result of substitution of y for free occurences of v in x, not(x) is the negation of x, and forall(x,y) is the generalization of y by the variable x. In usual modern notation, this becomes

For all n, $\ulcorner a({\dot {n}})\urcorner \in Thm(\kappa )$, and $\ulcorner \neg \forall v\,a(v)\urcorner \in Thm(\kappa )$.

If we further write T for κ, P for a, and $\vdash$ for Thm to dispense with the need for Gödel numbers, we get

For all n, $T\vdash P({\overline {n}})$, and $T\vdash \neg \forall v\,P(v)$.

As far as I can see, this is exactly the definition we have in the article, modulo the fact that variable v is implicitly restricted to the natural number sort in Gödel's usage, we have $\exists \neg$ instead of the equivalent $\neg \forall$, and we write the formula in words. So, could you elaborate (1) what do you find different in the two definitions, and (2) what do $\Pi _{1}^{0}$-theories have to do with anything? — Emil J. 16:41, 4 March 2009 (UTC)

[r Emil] So we have two definitions, the internal definition provided by Gödel, and the usual external one used here. The internal one codifies the theory being studied in the Conseq predicate, which is (implicitly) interpreted in the context of a base arithmetic, which is usually based on PRA or EFA, but may be much stronger. Gödel's formula is Pi-0-1 and, I think, semidecidable, so the strength of the base theory matters in terms of which theories it can prove omega-consistent. Whereas the external definition is (implicitly) not tied to any base theory, but is tied to the non-first-orderisable standard interpretation of arithmetic. I agree that the "(implicitly)"s do real work here, and if one changes the interpretations so they match up, then the equivalence becomes provable. But one does violence to the context of these definitions one does that.

Above is nonsense: I had read into Gödel's formula what wasn't there: a first-order relativisation of the definition, not the second-order definition he actually provides. I think Emil is right that my objection is wrong. I shall read Gödel's definition more carefully — Charles Stewart (talk) 19:41, 4 March 2009 (UTC)

Incidentally, you have given a nice explanation of Gödel's formalisation. I think it can be used in the article. — Charles Stewart (talk) 19:36, 4 March 2009 (UTC)

Emil is right, the Godel (in the translation provided) is exactly the same as the suggested formalization for the text which, except for "not for all" instead of "exists not", is exactly the same as Boolos as I pointed out earlier (in the Logic of provability - are you guys talking about some other Boolos?) The reason I said the Godel is too complicated is that I was thinking of the actual notation from Godel's 1931 paper which is exactly the same notation used in the collected works which is what I cited. The translation provided above is about halfway between original godel and more modern. I don't know how to type that notation using the math function, but the original uses Sb(a subscript Z(n) with a v above the Z), uses Neg(v Gen a), and uses Flg(k) instead of Conseq. But the meaning is exactly "For every natural number, Z(n) but not for all x (x not necessarily a natural number). The obvious direct English translation is to use the predicate "natural number" (or perhaps "numeral" in the first part of the definition and not in the second. Just as I have been suggesting.

And I should say that I am much more sympathetic to User:Trovatore's claims about truth and axioms after thinking about it than I was before. In cases where the interpretation is obvious (like set theory is about sets) of course we can have axioms that say false things about sets. If it is genuinely clear that we are dealing with a theory of arithmetic that is supposed to be saying things about the natural numbers, than yes, it is appropriate to say that the theory makes claims about the natural numbers and of course some of them might be false. I guess I still want to say that in most cases of actual theories that people talk about that are omega inconsistent, in my experience, the only reason to talk about these is not as a theory of the natural numbers, but for some other application. Certainly we can just stipulate "take PA and add that there is a square root of two and call this a theory of arithmetic) now we have an omega-inconsistent theory which says something false about the natural numbers. I guess I am just not in environments where this is common. In the case of sets of something else, you can imagine people not actually being sure if some axiom is true of sets or not, but this is (mostly) implausible in the case of arithmetic. --Jdvelasc (talk) 19:56, 5 March 2009 (UTC)

Definition of omega rule

The article currently formalises the omega rule:

If P(n) is a theorem for every natural number n, then $\forall x\,(N(x)\to P(x))$ is also a theorem.

I've only ever seen:

If P(n) is a theorem for every natural number n, then $\forall x\,P(x)$ is also a theorem.

What is role is the N(x) antecedent meant to play? To allow quantification over other domains? Well, that would be better handled using many-sorted first-order logic. Is it meant, somehow, to allow for non-standard models of qirthmetic? I can't begin to see how that would work. Or some other reason?

Assuming there is no good reason to prefer the current formulation, I propose what I've seen elsewhere. — Charles Stewart (talk) 12:02, 2 March 2009 (UTC)

The current article is written in a very general way in which T could be any theory - ZFC, for example - that interprets the natural numbers. So N(x) is the predicate which chooses the set of (possibly nonstandard) natural numbers out of the domain of all things in a model of T. So in ZFC, n(x) would be "x ∈ ω".

In this generalized context, it's clearly necessary to limit the ω rule to the things it is meant to describe.

What's really needed is for that section to be clarified about this issue. I can work on it today. — Carl (CBM · talk) 13:00, 2 March 2009 (UTC)

Right. And the reason for using the general context is that if you restrict yourself to the language of arithmetic, the concept of ω-logic trivializes: either T is sound, in which case it derives in ω-logic all true arithmetical statements, or it is unsound, in which case it in inconsistent in ω-logic (and thus derives every formula). — Emil J. 13:06, 2 March 2009 (UTC)

True, but the ω-rule is still of interest in those cases for its role in Gentzen-style consistency proofs, even if ω-logic is not so interesting. — Carl (CBM · talk) 13:16, 2 March 2009 (UTC)

Re. trivialisation in the language of arithmetic: among the subsystems of second-order arithmetic, I'm guessing that the omega-rule isn't going to force one to take any particular comprehension axiom. I see that the many-sorted marriage of arithmetic with ZFC might not be beautiful, though. Are omega-logics actively studied? What are the important theories? — Charles Stewart (talk) 13:52, 2 March 2009 (UTC)

When I say the language of arithmetic without further qualification, I mean the language of first-order arithmetic. The situation of second-order arithmetic is obviously quite different. There is nothing wrong with many-sorted theories, but that by itself is also a generalization of the usual first-order logic, and then if you want to formulate the ω-rule in a general context it is technically easier to require an extra predicate rather than introducing a new sort of variables. Also, you can consider (and a reasonable number of people do) two-sorted theories as being formally a shorthand notation for a usual one-sorted theory with predicates distinguishing objects of the various sorts, whereas I've never seen, say, ZFC, formulated in a two-sorted language with a separate sort for natural numbers. — Emil J.

[to Emil] I disagree with your claim that having additional quantifiers is more technically more complex than decorating every quantifier in every term with subordinate connectives, though I suppose technical complexity is in the eye of the beholder. But I raised this topic wondering whether we would be better off dropping the N(x) qualifier, which would be (a) formally simpler at least in the most common case, and I guess (b) the more common definition. I see the point about missing fine structure, but it doesn't apply in the many-sorted case.

Of course using the N(x) circumlocution might be prevalent in the omega-logic scholarship,which is why I asked the questions above about this research; my fumblings with Google Scholar didn't unearth a whole lot of that.

As to whether multi-sorted logic should be regarded as syntactic sugar for first-order logic, equally first-order logic might be seen as a special case of multi-sorted logic, and Manzano's arguments in her Extensions of First-Order Logic (2005) have convinced many people of the merits of the latter view. — Charles Stewart (talk) 16:15, 2 March 2009 (UTC)

The big advantage of the N(x) notation is that it is explicit. If you write just $\forall n\,P(n)$, it is impossible to tell from the formula that the quantifier is only supposed to run over natural numbers, so you have to explain that you are working in a potentially multi-sorted language, and either write something like "$\forall n\,P(n)$ where n is a variable of the natural number sort" whenever it is used, which is quite tiresome, or you have to invent and explain some ad hoc notation for indicating the sort in the formula. It is NOT an option to reserve lower-case letters for natural numbers as is the convention in second-order arithmetic, as lower-case is used by default for the generic all-encompassing sort in every other context.

I do not know anything special about research in ω-logic, I'm just presenting the stuff the way I learned it back in university.

I'm not opposed to using a different notation per se, but (1) it must make it crystal clear that the quantifier ranges only over natural numbers, whereas there are also other objects in the language of the theory, and (2) it must not apply only to special cases like second-order arithmetic. So far, your only proposal was just to drop the N(x) predicate, which fails both criteria, so I am firmly opposed to it.

What exactly do you find wrong with the latest formulation by Carl? It covers coherently both the general case, and the special case of arithmetic without the explicit N predicate. — Emil J. 16:36, 2 March 2009 (UTC)

[to Emil]Aha! I had only seen Carl's clarification of the scope of T — I am happy with Carl's formulation of two variants. Since we are on the topic, there's no standard way of indicating which variables range over which domain. IIRC Henkin used a complex scheme of superscripts on the variables; today one more often sees subscripts on the quantifiers (so, eg. $\forall _{V}x.\exists _{\mathbb {N} }n.\,|x|=n$ would be a way of saying every set has finite cardinality in such a notation). Further options would be to have a numeric superscript to indicate an n-ary relation over that sort, and an undecorated quantifier might be assumed to be of a given sort. And what sort could be more natural for a default sort than ${\mathbb {N} }$?

One could —though I should think you wouldn't like to— use different letters to indicate different sorts. — Charles Stewart (talk) 18:08, 2 March 2009 (UTC)

I am happy that you are happy. Yes, superscripts, subscripts, different fonts, etc. are all sensible possibilities for notation of sorts. However, the trouble is that none of them is quite standard, so whatever usage you choose would require an explanatory note.

As for the default sort: the choice obviously depends on the theory. It is natural for the natural numbers to be the default sort in a theory of arithmetic, but not in other theories. For instance, in set theories or class theories the natural default sort is the sort of sets. And since you seem to be interested in subsystems of second-order arithmetic and their proof theory, note that set theory does not just mean ZFC, it applies equally well to Kripke–Platek and its extensions. — Emil J. 12:44, 3 March 2009 (UTC)

Since I guess the relevance of this conversation to the article is now rather slight, I'll take it to your talk page — Charles Stewart (talk) 14:53, 3 March 2009 (UTC)

One actual issue with this section is that then the article says, "if P(n) is a theorem for every natural number n,...", it is referring to the natural numbers of the metatheory, not the natural numbers of T. I can see how this sort of thing could be very confusing for new readers. The usual fix here would be to say "for all standard natural numbers n"; would that be OK with everyone, or is there a better way to achieve it? I am afraid that using the word "standard" would necessitate adding a short "background" section to the article. I think this would be desirable anyway, to explain what we mean when we say T interprets arithmetic. — Carl (CBM · talk) 13:18, 2 March 2009 (UTC)

The universal quantifier is outside the scope of the "... is a theorem" predicate, hence it can only refer to numbers of the metatheory, but "standard natural number" is fine with me. Another way of clarification would be to distinguish the number n from its name ${\overline {n}}$ and write "$P({\overline {n}})$ is a theorem for every natural number n", but that might need an explanation too. — Emil J. 13:27, 2 March 2009 (UTC)

Yes. I have no trouble reading the statement and knowing immediately what is intended. I'm just looking for places where a naive reader might be confused. — Carl (CBM · talk) 14:38, 2 March 2009 (UTC)

This paper addreses some of the issues under discussion, I think:

A. Ignjatovic: Hilbert's Program and the omega-rule, The Journal of Symbolic Logic (JSL), vol. 59, Number 1, March 1994. pp. 322-343. [5]

Btw I'm a relatively naive reader but was able to understand the section with a bit of head scratching. 76.195.10.34 (talk) 15:56, 4 March 2009 (UTC)

Skolem

The page says, "Let T be PA together with the axioms c ≠ n for each natural number n, where c is a new constant added to the language. Then T is arithmetically sound (as any nonstandard model of PA can be expanded to a model of T), but ω-inconsistent (as it proves $\exists x\,c=x$, and c ≠ n for every number n)." Does this mean that Skolem's proof of existence of non-standard models of arithmetic provides an alternative proof of Goedel's theorem? Tkuvho (talk) 15:11, 15 August 2010 (UTC)

It doesn't. A theory can be complete and still have nonstandard models. In fact, the Lowenheim-Skolem theorem shows that every first-order theory with an infinite model has nonstandard models, whether the theory is complete or incomplete. So just showing that PA has nonstandard models doesn't show PA is incomplete. You could replace PA in the example above with the (complete) theory of the standard model $\mathbb {N}$. — Carl (CBM · talk) 19:40, 15 August 2010 (UTC)