3
$\begingroup$

So I am learning about the successor function $S(n)$ where we have $S(n) = n+1$ basically. So $S(0) = 1, S(1) = 2, S(2) = 3, S(3) = 4$, etc.

But are we explicitly mapping $0$ through $9$ "by hand" and then using some other rule for base 10? Are we explicitly defining $S(9) = 10$ or is there some other rule we use for defining how natural numbers are represented in a given base system?

Also does the successor function imply knowledge of subtraction? For instance if I wanted to define addition for something like $2+3$ I'd use the rule $a + 0 = a$ and $a + S(b) = S(a + b)$. So for instance:

$2 + 0 = 2$

$2 + 1 = 2 + S(0) = S(2 + 0) = S(2) = 3$

$2 + 2 = 2 + S(1) = S(2 + 1) = S(3) = 4$

$2 + 3 = 2 + S(2) = S(2 + 2) = S(4) = 5$

When evaluating something like $2 + 3$ I had to know that $3$ was the same as $S(2)$ which requires subtraction by one. Or is this seen as more of a substitution and mapping? As in, "in our set of relationships, $3$ is equivalent to $S(2)$"?

Are these expressions really being treated like a nested function of sorts? In other words it seems like something like this is actually going on (Python code), i.e. there's some other function or mapping taking place, not just the successor function:

def S(n):
    return n + 1

successors = {}
for i in range(0, 100): #ideally we have this to infinity
    successors[S(i)] = i

def add(a, b):
    if b == 0:
        return a
    else:
        return S(add(a, successors[b]))   # note the use of add() inside S() here

print(add(2, 3))
$\endgroup$
2
  • 5
    $\begingroup$ When evaluating something like 2+3 ... By the axioms alone, you are just evaluating $S(S(0))+S(S(S(0)))\,$. The $2$ and $3$ are merely artifacts of the notation you chose to use. $II + III = V$ is just as true if you used roman numerals to write it, instead. $\endgroup$
    – dxiv
    Mar 4, 2018 at 7:19
  • 4
    $\begingroup$ Don't confuse the number with its numerical representation. $\endgroup$
    – Asaf Karagila
    Mar 4, 2018 at 8:58

3 Answers 3

6
$\begingroup$

I think you are confused about two different things. (I sympathise, I shared the confusion for many years!)

Firstly, addition of natural numbers is not defined by the algorithm we use to calculate $(a+b)$ in base 10, or any other base. We can add two numbers, irrespective of how they are represented.

But more importantly, we build up the arithmetic of natural numbers slowly. Stage one is the definition of successor, your $S$ function.

Then we define some notation:

$$ 1:=S(0); 2:=S(1); 3:=S(2); \dots ; 10:=S(9); \dots $$ and so on. This is just a convenience, we can just as well work with $SSS(0)$ and so on.

Only once that is done can we define addition: it is not sitting there already. As you say, we define it as $$\begin{array}{3} a &+ 0 &:=a\\ a & +S(b) &:=S(a+b). \end{array} $$ Note that this isn't just an algorithm for calculating $+$, it is the definition of what $+$ is.

$\endgroup$
4
  • $\begingroup$ So is $2+3$ more like saying $S(S(S(0)) + S(S(0))) = S(S(S(S(0)) + S(0))) = S(S(S(S(S(0)) + 0))) = S(S(S(S(S(0))))) = 5$ $\endgroup$
    – user537069
    Mar 4, 2018 at 16:31
  • $\begingroup$ @user537069. Except that you have calculated $3+2$ and not $2+3$. (It is not too hard to prove $x+y=y+x$ but it needs to be done as part of the programme of developing arithmetic). $\endgroup$ Mar 4, 2018 at 17:14
  • $\begingroup$ How is commutativity proven usually? How do we prove $x+y=y+x$? $\endgroup$
    – user537069
    Mar 4, 2018 at 17:46
  • $\begingroup$ By induction. (Motto: facts about things defined recursively are proved inductively.) $\endgroup$ Mar 5, 2018 at 7:29
3
$\begingroup$

In the context of Peano arithmetic, there is simply no such thing as "10". There is only $SSSSSSSSSS0$. However, humans are not very good at counting long strings, so we define a convenient shorthand "10", in the knowledge that if we really had to, we could write out a string of "S" instead.

$\endgroup$
1
$\begingroup$

There are a few reasonable developments, which all have equivalent results, so it doesn't really matter which one you personally use.


Explicit definition, cautious version

  • Definition $\mathbf T$: Let $10=S(9).$
  • Definition $\mathbf C$: For digits $a$ and $b$, if $ab$ has not already been defined, then let $ab=(10\times a)+b.$

Explicit definition, cavalier version

  • Definition $\mathbf T'$: Let $\color{blue}{10}=S(9).$
  • Definition $\mathbf C'$: For digits $a$ and $b$, let $\color{red}{ab}=(\color{blue}{10}\times a)+b.$

Then we should carefully prove:

  • Theorem: Definition $\mathbf C'$ is compatible with $\mathbf T'$.
    Proof: $\color{red}{10}=(\color{blue}{10}\times1)+0=\color{blue}{10}$.

With that out of the way, we will suppress the irrelevant colors on two-digit numbers in the future. For example, we will write $10$ without distinguishing which definition is in use.


Using $9$ to avoid prematurely defining $10$

  • Definition $\mathbf N$: For digits $a$ and $b$, let $ab=(S(9)\times a)+b.$

We then prove:

  • Theorem: $S(9)=10$.
    Proof: compute $10=(S(9)\times1)+0=S(9)$.

Using only the native constant $0$

  • Definition $\mathbf L$: For digits $a$ and $b$, let $ab=(S(S(S(S(S(S(S(S(S(S(0))))))))))\times a)+b.$

We then prove:

  • Theorem: $S(9)=10$.
    Proof: Recall from an earlier definition of single digits that $9=S(S(S(S(S(S(S(S(S(0)))))))))$. Then $10=(S(S(S(S(S(S(S(S(S(S(0))))))))))\times 1)+0=(S(9)\times1)+0=S(9)$.

Each development has its virtues and drawbacks.

$\endgroup$

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.