MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Some days ago, I posted a question about models of arithmetic and incompleteness. I then made a mixture of too many scattered ideas. Thinking again about such matters, I realize that what really annoyed me was the assertion by Ken Kunen that the circularity in the informal definition of natural number (what one gets starting from 0 by iterating the successor operation a finite number of times) is broken “by formalizing the properties of the order relation on ω” ( page 23 of his “The Foundations of Mathematics”). What does actually “breaking the circularity” mean? Is there a precise model theoretic statement that expresses this meaning? And what about proving that statement? Is that possible?

share|cite|improve this question
If possible, could you please quote a couple of sentences to give us the context? This is a relatively new book and therefore many readers will not have access to it. Since "breaking the circularity" doesn't sound like a technical mathematical term, some more information is necessary to determine what Kunen means by it. – Timothy Chow Jun 15 '10 at 1:04
up vote 6 down vote accepted

Looking at the draft that was linked above, it's more clear what Kunen means. He is just saying that the informal "definition" of the natural numbers that you might think of in school is circular when examined closely. And it is, in the sense that you have to start with some undefined concept, be it "natural number", "finite set", "proof", etc., to capture finiteness.

However, Kunen does not dwell on that sort of philosohical point. He is simply saying that there is a formal and non-circular definition of ω in set theory, as the smallest infinite ordinal. This does give a rigorous definition, but it doesn't ensure that "finite" in an aribitrary model corresponds to our actual notion of finite. That is something that cannot be ensured in first-order logic.

share|cite|improve this answer
As Tim mentioned in his answer to my other post, sometimes model theorists studying nonstandad models of arithmetic refer to N as the standard model, and to Th(N) as "true arithmetic", i. e. the set of sentences in the language of PA true in that model. Then they prove things like that if M is a nonstandard model of PA then M contains an isomorphic copy of N (in fact an initial segment of M). When one thinks informally about the natural numbers one has in mind N, not omega, which as Harald says is but a formal definition not capable of capturing what N really is. Hence the confusion. – Marc Alcobé García Jun 15 '10 at 13:18
In other words, we avoid circularity at the expenses of precisely stating what we'd like to mean. – Marc Alcobé García Jun 15 '10 at 13:24
On notation: one convention in computability theory is to use ω to refer to the standard natural numbers and blackboard bold N to refer to an arbitrary model of (some fragment of) arithmetic. This is related to the use of the term "ω-model". But this convention is not universal; Kaye's book uses blackboard bold N for the standard model, and Kossak/Schmerl use both b.b. N and ω for the standard model. I have never seen a book that uses ω to refer to a nonstandard model, though. – Carl Mummert Jun 15 '10 at 13:31
@Carl, my impression was that $\omega$ is used when the emphasis is on the set or at most an ordered set and $\mathbb{N}$ is used when one wants to put emphasis on the structure of natural numbers usually including at least addition and multiplication and $N$ is used for possibly nonstandard objects in models satisfying those properties of $\mathbb{N}$ that are expressible in the language. – Kaveh Jul 15 '13 at 9:37
@Kaveh: in most of the reverse mathematics literature, $\mathbb{N}$ is used for an arbitrary, possibly nonstandard model and $\omega$ is used for the standard model. But although this is common in that field, it is not universal. – Carl Mummert Jul 15 '13 at 11:53

I don't have that book, but as far as I can understand, the “circularity” must mean this: in the phrase “iterating the successor operation a finite number of times”, we should mean a number of times corresponding to a natural number. But since the natural numbers are what we are defining, this is circular. So one has to define the natural numbers without reference to the concept of “finite”. Where the circularity is broken is if you rewrite your definition as follows:

  1. 0 is a natural number,
  2. the successor of any natural number is a natural number, and
  3. nothing is a natural number unless it must be, by 1 and 2.

(All this stated in more technical language, of course.)

There is no reference to the notion of “finite” here. Instead, number 3 above gives us, by definition, the principle of induction. For example, how do you show that some object X is not a natural number? Well, if for some property P, you can show P(0) and you can also show that ∀n: P(n)⇒P(n') where the prime denotes the successor function, but X fails property P, then you can know for sure that X is not a natural number.

Edit: I see I did not answer all your questions. I am not a logician, so take this with a grain of salt. But basically, in first order logic (in which ZFC is expressed) it is impossible to make circular definitions, and if you can't make one, you can't repair it. The circularity, as I see it, all exists on the meta-level, before you have even gotten around to formalizing the theory. So “breaking the circularity” must in essence happen in the transition between the informal and the formal.

Strictly speaking, first order theories don't even allow definitions at all! What you have to do is to notice that there is a complicated formula NN(x) that we interpret as “x is the set of natural numbers”, and a theorem ∃!x NN(x) in ZFC (where ∃! is short for “there exists a unique …”); then we create a new theory by adding the symbol ω and adding the axiom NN(ω). Now, any formula A(ω) in the new theory can be rewritten in the old theory as ∃x:NN(x)∧A(x), so nothing new has really happened, except for a great amount of simplification.

share|cite|improve this answer
Yes, that is the circularity. But the inductive definition doesn't really help, in first-order logic: there are still nonstandard models that satisfy all the same first-order induction axioms as the standard model. These nonstandard models think that all their nonstandard numbers "must be" obtained by rule 3. Maybe what Kunen means is that, once we have axiomatized enough of the true properties of the natural numbers, we can use those axioms to prove interesting theorems, and we don't have to worry too much about nonstandard models at that point. But I also don't have the book. – Carl Mummert Jun 14 '10 at 22:48
@Harald: I would guess that "circularity" refers to the fact that the following three concepts are all mutually dependent: "natural number", "string of symbols", "proof". All three of these rely on the same notion of "finiteness", so in the end if you are doubtful about whether "finite" is well defined you cannot use any of the three concepts to clarify the other two. But this assumes that you are doubtful about what "finite" means. If we simply accept "finite" as an undefined term, and axiomatize the properties that "finite" things have, this starts to sound more like Kunen's proposal. – Carl Mummert Jun 14 '10 at 22:53
@Carl: Yes, the existence of nonstandard models are indeed a fact of life and there is no way out of that. I think you're right on in your first comment. Re your second comment, now you are talking about the meta level and the formalization of things like well-formed formulas and proof, right? Lacking Kunen's book I cannot be sure, but I did not get the impression that this sort of question is at issue here. – Harald Hanche-Olsen Jun 14 '10 at 23:04

protected by François G. Dorais Jul 15 '13 at 15:12

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.