Counting and Peano’s axioms

Leopold Kronecker once famously remarked, “God made the integers; all else is the work of man.”

If we look closely at the set of integers viz. {. . ., -4, -3, -2, -1, 0, 1, 2, 3, 4, . . .}, we observe that it’s made up of three subsets in all:

  1. the counting numbers viz. {1, 2, 3, 4, . . .}
  2. the number zero viz. {0}
  3. the negative counting numbers {. . ., -4, -3, -2, -1}

We know intuitively that a counting number denotes presence of objects of a kind, while the number zero denotes absence of objects of a kind. (The negative counting numbers can be seen as a mere reflection of the counting numbers at 0, to introduce numbers ‘less’ than 0, to indicate presence of objects opposite to the kind being considered.)

Thus the whole game of integers boils down to two simple ideas, viz. presence and absence. We explore the counting numbers {1, 2, 3, 4, . . .} here.

To denote the counting numbers, we use ten symbols, viz. the ten digits ‘0,’ ‘1,’ ‘2,’ ‘3,’ . . ‘9.’ This choice of the number of symbols to use, however, is arbitrary — in fact, we could use any number of symbols and still end up with the same set of counting numbers. For example, if we used the symbols ‘0,’ ‘1,’ . . . ‘9’ along with the alphabets ‘A,’ ‘B,’ . . . ‘F’ (sixteen symbols in all), we could still enumerate the same set of counting numbers as {1, 2, 3, . . . 9, A, B, . . . F, 10, 11, 12, . . . 19, 1A, 1B, . . . 1F, 20, . . .} (The way of counting just demonstrated is called counting to base sixteen, or the hexadecimal number system. For more information, see Hexadecimal.)

Now, what if we used just one symbol, viz. ‘1’ or ‘|’? Well, we would count as follows:
{|, ||, |||, ||||, |||||, . . .} It may be observed intuitively that, starting with the symbol ‘|’ any counting number may be obtained by adding the ‘|’ to the previous number. If we refer to two adjacent counting numbers (e.g. ‘|||’ and ‘||||’), we can refer to the latter as being the ‘successor’ of the former, such that the whole set of counting numbers may be obtained from just two ideas:

  • the symbol ‘|’
  • the successor function which appends ‘|’ to a given number to obtain a new number (the successor of the given number)

This system of defining the counting numbers is due to the Italian mathematician Giuseppe Peano who first presented it. It is based on an arbitrary symbol for the first counting number, say ‘|’, a successor function S(n) which stands for the successor of the natural number n (obtained by appending ‘|’ to n), together with nine facts that are intuitively assumed to be true, and called Peano axioms.

The first axiom states that the constant ‘|’ is a counting number. Axioms 2 through 5 define the equality relation on the counting numbers. Axioms 6 through 8 define the arithmetic properties of the counting numbers. Axiom 9 states that there is no counting number except ‘|’ that isn’t the successor of another counting number, thus covering the whole of counting numbers.

Formally, the axioms may be stated as follows:

  1. ‘|’ is a counting number.
  2. For every counting number x, x = x. (Equality is reflexive.)
  3. For all counting numbers x and y, if x = y, then y = x. (Equality is symmetric.)
  4. For all counting numbers x, y, and z, if x = y and y = z, then x = z. (Equality is transitive.)
  5. For all x and y, if x = y and x is a counting number, then y is a counting number too. (The counting numbers are closed under equality.)
  6. For every counting number x, S(x) is a counting number.
  7. For all counting numbers x and y, x = y if and only if S(x) = S(y).
  8. For every counting number x, S(n) = | is false. (i.e. There is no counting number whose successor is |.)
  9. If K is a set that contains |, such that for every counting number x, x being in K implies S(x) being in K, then K contains all counting numbers.

The above definition is based on the idea of recursion, which is a fundamental aspect of human reasoning: to define any counting number, we may write it as the successor of the number ‘previous’ to it, and so on upto the ‘first’ counting number |. For example, |||| may be rewritten as S(S(S(|))).

This is indeed how counting numbers are defined in modern mathematics. At the time when it was proposed, Bertrand Russell and others agreed that it was an intuitive definition of the counting numbers. However, Henri Poincaré was more cautious, saying they only defined natural numbers if they were consistent; if there is a proof that starts from just these axioms and derives a contradiction such as | = ||, then the axioms are inconsistent, and don’t define anything. David Hilbert posed the problem of proving their consistency using only finitistic methods as the second of his twenty-three problems. Kurt Gödel proved his second incompleteness theorem, which shows that such a consistency proof cannot be formalized within Peano arithmetic itself.

We will subsequently discuss Gödel’s incompleteness theorems.

(This post is inspired by the post Finding Recursion in Inheritance.)