Welcome to MathOverflow

Question

4

1

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?

flag	asked Jun 14 2010 at 20:17 Marc Alcobé García 979●2●12

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 2010 at 1:04

1

math.wisc.edu/~kunen/notes_post.ps – Halfdan Faber Jun 15 2010 at 4:52

Carl Mummert · Accepted Answer · 2010-06-15 11:22:51Z UTC

4

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.

answered Jun 15 2010 at 11:22

Carl Mummert

community wiki

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 2010 at 13:18

1

In other words, we avoid circularity at the expenses of precisely stating what we'd like to mean. – Marc Alcobé García Jun 15 2010 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 2010 at 13:31

Harald Hanche-Olsen · Answer 2 · 2010-06-14 22:22:03Z UTC

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:

0 is a natural number,
the successor of any natural number is a natural number, and
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.

Breaking the circularity in the definition of N

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

2 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.