Defining Natural Numbers

Next: Processing Natural Numbers of Up: Natural Numbers Previous: Natural Numbers

Defining Natural Numbers

People normally introduce natural numbers via enumeration: 0, 1, 2, etc. The abbreviation ``etc.'' at the end says that the series continues in this manner. Mathematicians and mathematics teachers often use dots for the same purpose. For us, however, neither the ``etc.'' nor the dots is good enough, if we wish to design functions on natural numbers systematically. So, the question is what it means to write down ``etc.,'' or put differently, what a complete, self-contained description of the natural numbers is.

The only way to remove the informal ``etc.'' from the enumeration is to describe the collection of numbers with a self-referential description. Here is a first attempt:

0 is a natural number.

If n is a natural number, then one more than n is one, too.

While this description is still not quite rigorous,

it is a good starting point for a Scheme-style data description:

A natural-number is either

0 or
(add1 n) if n is a natural number.

The operation add1 adds 1 to a natural number. Of course, we could use (+ ... 1) but add1 stands out and signals ``natural number,'' as opposed to arbitrary number, to the reader of a data definition and a function.

Although we are familiar with natural numbers from school, it is instructive to construct examples from the data definition. Clearly,

is the first natural number, so

(add1 0)

is the next one. From here, it is easy to see the pattern:

(add1 (add1 0))
(add1 (add1 (add1 0))) 
(add1 (add1 (add1 (add1 0))))

The examples should remind us of the lists construction process. We built lists by starting with empty and by constructing on more items. Now we build natural natural numbers by starting with 0 and by adding on 1. In addition, natural numbers come with century-old abbreviations. For example, (add1 0) is abbreviated as 1, (add1 (add1 0)) as 2, and so on.

A function on natural numbers must extract the number that went into positive natural number just like a function on lists must extract the list that went into a constructed list. The operation that performs this ``extraction'' is called sub1. It satisfies the law

(sub1 (add1 n)) = n

just as the rest operation satisfies the law

(rest (cons a-value a-list)) = a-list

Of course, (- n 1) would also work, but sub1 stands out and signals that the function processes natural numbers.

Next: Processing Natural Numbers of Up: Natural Numbers Previous: Natural Numbers

PLT