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.

Here is your first exercise:

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
peano_eq :: peano, peano -> bool Equality

Here are the rules of the game:

  1. All your functions must be recursively defined (no while, proc, whatever).
  2. No use of +, -, ==, <=, and so on, in your definitions. As long as it is not numerical comparison, == is allowed.

  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. ↩