How many natural numbers are there?

In one sense, there are infinitely many of them. In this sense we think in particular objects like \(1,2,3,\ldots\). In another, more abstract, sense, number is a concept rather than a collection of entities. If you insist on concreteness, then it can be said that there is one and only one number. And one single number and a tiny one-argument function are all we need.

The set of natural numbers \(\mathbb{N}\) is defined as follows:1

  1. \(0 \in \mathbb{N}\).
  2. \(\forall x. x\in \mathbb{N} \to s(x) \in \mathbb{N}\).
  3. \(\neg\exists x\in\mathbb{N}. s(x) = 0\).
  4. \(\forall x,y\in\mathbb{N}. s(x) = s(y) \to x = y\).
  5. Let \(\phi\) be a unary predicate:
\[\begin{align*} [\phi(0)\land \forall x\in\mathbb{N}. \phi(x)\to\phi(s(x))] \to \forall y\in \mathbb{N}.\phi(y) \end{align*}\]

  1. This is a version of Peano Axioms that omits the axioms on equality and differs from the original by taking 0, rather than 1, as the base case. ↩

This gives all the non-negative whole numbers there are. Now we define two familiar operations:

  1. \(\forall x. x+0=x\).
  2. \(\forall x,y. x+s(y) = s(x + y)\).
  1. \(\forall x. x\cdot 0=x\).
  2. \(\forall x,y. x\cdot s(y) = x\cdot y + x\).

Our task is to do some arithmetic on computer. But we do not have numbers themselves as we are used to. For instance when you want to compute the value of \(2+5\), you will not be able to type 2+5 into Python console. The numeral 2 will just be a name for the value \(s(s(0))\). In this respect typing 2+5 will be like typing "two" + "five", which would not give what you expect (it gives “twofive”, by the way).

In constructing the system of numbers to be represented and processed by the computer, we agree that None is the object that the numeral 0 names. The return value of the successor function \(s\) will be represented by wrapping a pair of parentheses around its argument. To give you the initial feel for the system our naming scheme will be:

  1. 0 will name None
  2. 1 will name (None,)
  3. 2 will name ((None,),)

As Python’s int type, which represents the whole numbers, will already be in place, we need to be careful not to mix these two types. For this purpose, we define a new type peano as follows:

A Python object p is of type peano if,

  1. it is None, or,
  2. it is a 1-tuple whose sole member is of peano type.

Now some exercises.

Write a module1 peano which implements the following functions:

Name and type Description
zero :: -> peano Constructor for the zero of the system, i.e., returns None
succ :: peano -> peano Constructor for the rest
zerop :: peano -> bool Check whether the given peano object is zero (in the peano sense).2
peanop:: obj -> bool Check whether the argument is peano.
to_int :: peano -> int Conversion
from_int :: int -> peano ditto
peano_add :: peano, peano -> peano Addition
peano_mult :: peano, peano -> peano Multiplication

Here are the rules of the game:

  1. All your functions must be recursively defined (no while, proc, whatever).
  2. Defining to_int and from_int, and using +, -, ==, <=, and so on, for operations on peanos is NOT valid.

  1. If we are not already in the module business, “write a module” means create a peano.py file and define your functions there. Later on you can import your function names with from peano import peano_add, peano_mult, and so on. ↩

  2. We follow the LISP convention of naming predicates by attaching a p at the end of the corresponding property. The programmatic way to inquire about someone’s mood is to apply happyp to him/her. ↩

🗝️

All the exercises that follow are bound by the same criteria as above: use recursion and don’t cheat via ints.

Define functions peano_eq and peano_lt for equality and less-than comparison of peano objects.

🗝️

Define a function peano_power that raises its first argument to the power of the second, all in peano type.

🗝️

Define two function pred and sub for predecessor and subtraction, respectively. As we are modeling the natural numbers, the predecessor of zero is zero, and subtraction is truncated at zero. For example, sub(from_int(3), from_int(5)) should return from_int(0), not from_int(-2).

🗝️

Define a function divmod which takes two peano objects a and b and returns a pair of peano objects (q, r) such that q is the quotient of a divided by b and r is the remainder. You can assume that b is not zero.

🗝️