Free your mind: the Peano axioms
Free your mind: the Peano axioms
Warning: this article can make you feel dizzy.
My son is almost four years old, that age when children push the limits all the time. He asks for a candy, and we say "ok, just one, after the lunch!". Then he thinks, looks at his hands' fingers, and replies "just three" or "just four". Sometimes, he smiles and cheerfuly says "just ten!".
Then I grew curious: how does he grasp numbers? For example, the number three; what does he think when he asks "three" candies? A sweet aftertaste that is longer than usual? Three fingers? Or perhaps one candy in each hand and another in mouth?
But, thinking over it, what is the real meaning of "three"? Three oranges, three apples. Why do we say that there are three fruits in the basket, instead of four, five, or two?
What is this important for? What's the difference, anyway? Why count things? Animals don't count and do well, and may be happy in spite of that. Is "three" something that really exists in Nature, or is it a product of human imagination, like fairy tales?
Another wrinkle in this subject: if the set of natural numbers is infinite, how does God handle this? Does He know every integer number? Would that be possible, even for Him? (Now that's something that Christians should spend time on, instead of debating if the sexual position XYZ is sinful.)
We learn that 2 + 3 = 5. Is that really true? If we can't define precisely what "two" or "three" mean, the sum operation does not make sense either. The teacher said that we can't add oranges and apples. But, perhaps, "two" and "three" could be unique and incompatible entities as well, and they can't be added.
Ok, before I go forward on this way, I will challenge another thing: the way we employ to represent numbers. For example, why "three" is 3? Or, more to the point, why "twenty" is 20?
Twenty fingers I can visualize, giving a number to each finger from 1 to 20. If a hammer hits any finger of my hand or my foot, I know which one it is, I would know even if I were blind. But "2" and "0" put together mean the same thing?
Well, it is just the decimal system, or more precisely the decimal positional system. It is "positional" because the digit position changes its meaning. A "2" left of "0" means "two sets of hands full of fingers". It is a practical way to represent big quantities, like the public deficit.
Computer programmers learn other systems, all positional: hexadecimal, binary, elder colleagues have learnt octal. People exposed to pure computer science might have had contact with the ternary system.
Even the binary system has two digits: 1 and 0. Would it be possible a system with just one digit? Common sense says no, because then we'd have only the 0, and any string of zeros is worth zero, no matter how long.
But the unary system does exist, and its only digit is "1". Common sense is wrong because every numeric system has the digit 0, but unary is the exception. This is because unary is not positional.
Well, how do unary numbers look like? Three is 111, five is 11111, one is 1, ten is 1111111111. Unary really exists and people do use it (without knowing) when they e.g. use tally marks.
Remember the prisioner stereotype? Scratching tally marks on cell walls to mark time served. When you were a child, you learnt to count in unary, using the fingers.
The zero, or nil quantity, is represented in unary by the absence of symbols. This may be a problem because there is no distinction between "zero" and "no value". A cell with no tally marks in walls may have been recently painted, or may be a cell where prisoners never spend a whole day.
An "antidote" for the lack of zero is to add a bias. Every prisoner scratches a tally mark as soon as it is thrown in the jail, effectively adding a bias of 1. Future prisoners will know how many other people spent at least a fraction of a day in there.
Roman numerals are essentialy unary. The only "improvement" is compression. For example, you write IV instead of IIII, and X instead of IIIIIIIIII. But it is not wrong to write four as IIII; some old clocks actually use IIII.
Being a unary system, roman numerals don't have a symbol for zero, and are terrible for pencil-and-paper arithmetic as well.
Anyway, we saw that the unary system exists, it is pervasive and it is a perfectly valid device for some cases. More: it is easier to see the real meaning of a number like "three" in unary.
More: unary numbers have the interesting property of being palatable to regular expressions. This is more of scientific/theoretical value than practical (in the current state of technology). You can do arithmetic operations and find if a number is prime with nothing more than regular expressions, provided that numbers fed into them are expressed in unary.
Back to our existential angst: what is "three"? Why two plus two equals four? Perhaps these are all things that we are force-fed in school to distract us and kill time, while our parents go to work.
At the same time, we "smell" some actual, practical meaning in numbers. It is even hardwired in our brains, even more than reading and writing. I've seen many illiterate persons, and everyone of them could count money!
Very well, a mathematician called Giuseppe Peano sweated on these questions, and managed to find a small set of definitions, or axioms, that perfectly define what is a number, what is a sum, etc.
First off, zero (0) is defined as being a number, but no hint about its actual value is given. The realization that zero is nil will come later.
Then, we have the definition of the successor function, that I will express as S(x):
Number is an object that has a successor. This is the essence of a number.
On top of this, we can define what is "three": it is the successor of "two". Nothing more! Sure, we now have to define what is "two". But that's easier: "two" is the successor of "one", and "one" is the successor of zero.
So, the grounds-up definition of "three" is S(S(S(0))). The label "three" is just a label that we stamped on the third successor of zero.
Someone could say that the alphabet is equivalent to a number set, because most letters have successors (B succeeds A and so on). But Z has no successor, and one missing link in the chain is enough to disrupt the equivalence. So, letters are not numbers!
Now, let's see the axioms of addition and multiplication.
x + 0 = x x + S(y) = S(x + y)
Finally we can assert that zero is nil, because, accordingly to the definition above, adding zero to a number does not change it at all. (Isn't that curious that we can only assert the value of zero in terms of the addition operation?)
In order to add non-nil numbers, the definition must be applied recursively, as shown in the following example:
2 + 3 2 + S(2) S(2 + 2) S(2 + S(1)) S(S(2 + 1)) S(S(2 + S(0))) S(S(S(2 + 0))) S(S(S(2))) 5 2 + 3 = 5
It is easy to see that adding 1 to a number is equivalent of finding its successor:
x + 1 x + S(0) S(x + 0) S(x) x + 1 = S(x)
Similarly to addition, multiplication is defined in two axioms:
x . 0 = 0 x . S(y) = x + (x . y)
The curious thing is, the multiplicative neutral — the number one — emerges naturally, but it is not explicitly mentioned in the axioms.
Starting with these basic rules we can define the whole arithmetic, including complicated things like the definition of a prime number.
And, of course, it is a bit clearer (for me, at lest) how God handles the set of natural numbers. He just laid out those simple rules... or created Peano for that purpose :)
Another source of our ordinary arithmetic is the group, invented by Evariste Galois. It is said that Galois put all his math works on paper just the night before he engaged in a duel, that he lost. He died only 20 years old.
A group is a coupling of two things: a set of numbers G, and some binary algebraic operation i.e. a function that takes two numbers and yields one result. Addition and multiplication are such operations; I will use addition as example.
For a group to deserve this name, it neds to fulfill some requisites:
The set of integers (Z) is a group over addition, since it fulfills all requisites. Such group can be expressed by notation (Z,+). In the other hand, natural numbers (N) are not a group over (N,+), since we don't have inverses without negative numbers.
The set (N,+) is actually a semi-group because addition is still associative, and it also a monoid because there is a neutral element.
Neither (Z,×) nor (N,×) are groups (they lack inverses) but the set of rational numbers (Q) is a group over (Q,+) and (Q,×).
Subtraction and division operations don't form groups since they are not associative and don't have a neutral element for the first operand. "Groups" like (Z,-) or (Q,÷) are actually grupoids since the operations are closed. On the other hand, (N,-) is not even closed (the result of 4-5 does not belong to natural numbers).
We have not mentioned commutativity until now (a+b=b+a). An operation does not have to be commutative to form a group. Example of non-commutative operations: matrix multiplication and vector product. They are groups (e.g. the product of two vectors is always a vector).
But it is certain that commutative operations are more usual, and should have special status. Commutative groups like (Z,+) are named abelian groups.
The arithmetic as we know it emerges from three abstract objects:
Any disturbance on the sensitive equilibrium of this tripod, and we end up with some freak new "arithmetic", unrelated to our "natural reality".
Let's start slowly. Consider the finite set of hours in a wall clock (numbers from 0 to 11). In clock's arithmetic, 11+4=3 and 3-8=7. The arithmetic operations are still closed, but the results are strange if compared to natural numbers. Once you associate them with the act of setting a clock, they feel "natural" again.
Instead of numbers, we could employ sets of any kind of object (polynomials, sea shells, whatever) and form groups. We just need to define the result of every addition (and/or multiplication) of any two elements.
And the results don't even need to be congruent to "ordinary" arithmetic; the result table just needs to abide to the group properties: associativity, neutral element, etc.
Actually, if you try to invent a group from scratch, you soon discover that the group rules will leave their mark on result table.
Consider a set of three "objects": [A,B,C], that I intend to make a group over "addition". I need to build an addition table that fulfills the requisites of neutral and inverse elements.
+ A B C ------------ A . . . B . . . C . . .
First off, we need to choose the neutral element, that could be "A":
+ A B C ------------ A A B C B B . . C C . .
This single choice already binds five out of nine positions of the table. If you thought we had absolute freedom to build the table... this freedom already looks very restricted.
Now we are left to define the operations between B and C. We can't make B+B=B, otherwise B+B=B+A and we would have two neutral elements. So, B+B=C is enforced. The same rationale holds for C+C.
+ A B C ------------ A A B C B B C . C C . B
Now we need to define B+C and C+B. Since every element of a group must have an inverse, we have no other option than defining B and C as inverses of each other, that is, B+C=C+B=A.
+ A B C ------------ A A B C B B C A C C A B
We can see now that the group has an iron fist over the form of our "arithmetic".
And Galois does the same with the conventional arithmetic. Have you ever wondered why two negative numbers yield a positive result under multiplication? This fact emerges directly from the concept of group.
Imagine a group with only two numbers, +1 e -1, over multiplication. The neutral element is obviously +1, and this fact already takes 75% of the table:
× 1 -1 ------------ 1 1 -1 -1 -1 ??
To complete the group, we need to find an inverse element for -1. And it can only be -1 itself, since +1 is neutral. This implies that (-1)×(-1)=+1.