Assume we get the set of natural numbers $\mathbb{N}$ from any model of the Peano axioms.

We're given the symbols: $0,1,2,3,4,5,6,7,8,9$, or rather, we're given $0$ and we choose to use the symbols $1,2,3,4,5,6, 7, 8,9$.

Of course $0$ is the same from the model.

Then we'll have, by definition, $1=S(0)$, $2=S(1)$, $3=S(2)$, $4=S(3)$, $5=S(4)$, $6=S(5)$, $7=S(6)$, $8=S(7)$ and $9=S(8)$.

But how do we represent the rest of the natural numbers the way we expect them to be represented?

I understand that $1, 2, 3, 4, 5, 6, 7, 8, 9$ are just shorthand representations for the entities written above.

I guess my question can be particularized by: how do you know that the short hand notation for $S(999)$ is $1000$?

I'm assuming the way to get a representation for each natural number starts the way I write it. If that's not the case, please do it from the top.

  • $\begingroup$ What's wrong with the inductive definition $S(n+1)=S(S(n))$? $\endgroup$ – Asaf Karagila Jan 19 '13 at 21:57
  • $\begingroup$ My problem is not with the definition per se, but rather how to represent each number. Intuitively you know $10$ will be $S(9)$, but why? Did I make it clearer? $\endgroup$ – Git Gud Jan 19 '13 at 21:58
  • $\begingroup$ I don't think it is "intuitively" but only a matter of choosing some base wrt which write the numbers: $\,S(9)=10\,$ because we usually use the decimal base to write numbers, but I think it may as well be $\,S(9)=101\,$ if we choose base $\,3\,$ (and, of course, it probably is more logical to write $\,S(100)=101\,$ in base $\,3\,$ ...) $\endgroup$ – DonAntonio Jan 19 '13 at 22:04
  • $\begingroup$ @DonAntonio What's that about base wrt? Never heard of it. I know we choose to use the decimal base do represent numbers. But how do you know that, in base $10$, $1000=S(999)$? And what is $999$? $\endgroup$ – Git Gud Jan 19 '13 at 22:10
  • $\begingroup$ @GitGud , wrt = with respect to . And again: I know that $\,S(999)=1000\,$ because I choose (or we choose) to represent the numbers in decimal base, that's all. If we chose not to work with bases at all then we could use the successor function and work just with that, though it would be extraordinarily cumbersome: "What time is it?" " It is$\,S(S(S(S(\emptyset))))\, $ minutes before $\,S(S(\emptyset))\,$ " ...pretty annoying, uh? There's where bases kick in. $\endgroup$ – DonAntonio Jan 19 '13 at 22:17

Given a PA number, to translate it back into a string of digits is by the following recursive function:

  • $f(x) = d(x)$ where $x < 10$
  • $f(x \hat + SSSSSSSSSS0 \hat \times y) = f(y)"d(x)"$ where $x < 10$ and $y > 0$.

Justifying this recursion principle 9that a function defined in this way is well defined and total) is by Euclid's Division algorithm.

  • $\begingroup$ I think I'm getting the gist of it. Can you tell me where to read about this and find some proofs? $\endgroup$ – Git Gud Jan 19 '13 at 23:03
  • $\begingroup$ @GitGud, what do you like proofs of? $\endgroup$ – user58512 Jan 19 '13 at 23:08
  • $\begingroup$ "Justifying this recursion principle 9that a function defined in this way is well defined and total) is by Euclid's Division algorithm." I wouldn't wanna bother you with that, I can probably do it myself. But I'd rather read it, so if you know where I can read about it, I'd appreciate it. Thanks. $\endgroup$ – Git Gud Jan 19 '13 at 23:14

There is an obvious function from strings of digits to natural numbers:

  • $f("") = 0$

  • $f("3534") = 3 + 10\cdot f("534") = 3 + 10 \cdot (5 + 10 \cdot f("34")) = \ldots = 3 + 10(5 + 10(3 + 10(4 + 0))))$

Recall that we define + and * for peano arithmetic:

  • $0 \hat + y = y$
  • $Sx \hat + y = S(x \hat + y)$

  • $0 \hat \times y = x$

  • $Sx \hat \times y = x \hat + x \cdot y$

therefore, define

  • $g("") = 0$

  • $g("dssss") = p(d) \hat + SSSSSSSSSZ\hat \times g("ssss")$

and the gives the peano arithmetic number or a digits expression.

(p is the function that gives $p(2) = SSZ$ for the first 10 digits for example, that you already mentioned)

  • $\begingroup$ I think this is on the right track to satisfy me. But I have to define $10$ before applying your process, right? $\endgroup$ – Git Gud Jan 19 '13 at 22:49
  • $\begingroup$ @GitGud, the first part with $f$ is just for intuition - it's not used later. Also I posted a new answer to your question: How to do the reverse operation: Getting a string of digits from a peano number. $\endgroup$ – user58512 Jan 19 '13 at 22:51

first you must define the "remain" and "quotient" of one natural number to another then you can represent any natural number by its "quotient" and "remain" to the powers of ten

Actually in set theory you don't represent numbers like 10 or 11 or something like that, number 3 in set theory is S(S(S(0))), but because you are already familiar with this representation of natural numbers, you use 3, actually using "3" in set theory is wrong


You need to notice that the standard decimal representation of the natural numbers is not a representation from inside the Peano model. The language only contains a constant symbol for $0$. Then one introduces $1=S(0)$ as shorthand notation not as a new symbol. Then comes $2=S(1)=s(S(0))$ again as shorthand notation, not a new symobol, and so on.

So, whenever you write something in PA and you use $0$ then you mean the constant symbol in the language. When you write $1$, $2$, and so on mean that this is shorthand notation that you use just because you are lazy to write out an expression of the form $S(S(0))$.

I hope this helps.

  • 1
    $\begingroup$ I understand everything you said, but it doesn't answer what I want to know. Why do you make $10$ short for $S(S(S(S(S(S(S(S(S(S(0))))))))))$? $\endgroup$ – Git Gud Jan 19 '13 at 22:02
  • 1
    $\begingroup$ it's just introducing shorthand notation for strings in the language. You could have used "banana" as shorthand for S(S(S(S(S(S(S(S(S(0)))))))))) if you want. But it makes more sense for us humans (who like numbers and use the decimal notation regularly) to call it something a bit more meaningful. We work with the model of PA from outside of it. We are not in the model so we are free to study it by means of things we have outside as well. It makes life easier. $\endgroup$ – Ittay Weiss Jan 19 '13 at 22:09
  • $\begingroup$ I wouldn't say 47 is short for $S(S(S(\ldots(S(0)))))$ any more than it is short for XLVII. Decimal numerals, Roman numerals, successor numerals belong to three different ways of representing natural numbers. $\endgroup$ – Peter Smith Jan 19 '13 at 22:13
  • $\begingroup$ @IttayWeiss How do you rigorously introduce the shorthand notation that we're used to? That's my question. $\endgroup$ – Git Gud Jan 19 '13 at 22:16
  • $\begingroup$ @GitGud recursively: n+1 is shorthand notation for S(n), where 0 is shorthand for "0". It works since you believe that for the models of the naturals that you have in your head, recursion works. $\endgroup$ – Ittay Weiss Jan 19 '13 at 22:21

Suppose you have $9$ stones in a pile and you add another stone to make a pile of $S(9)$ stones. Rather than invent a new symbol, the convention is to give a pile of this size its own name. Henceforth, any pile of exactly $S(9)$ stones will be called a "ten". So, the successor of $9$ is a ten and no other stones. This is denoted by placing a $1$ in the ten column and a $0$ in the single stone column, which gives $S(9) = 10$. The process is similar for larger piles of stones: "hundred", "thousand", etc.

  • $\begingroup$ My problem is with "that process is similar". That's just an intuitive way of doing things. That's like what we were taught when we were kids. How do you make a computer understand that $10$ is just $S(9)$? You can't tell the computer what symbol will represent each natural number. $\endgroup$ – Git Gud Jan 19 '13 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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