# From Mathematics to Generic Programming (2011)

### 9. Organizing Mathematical Knowledge

*All the truths of mathematics are linked to each other,and all means of discovering them are equally admissible.*

Legendre

Now we’re going to look at some of the building blocks for organizing knowledge, particularly mathematical knowledge. We’ll start by exploring the notion of proofs and the introduction of the idea of theorems. Then we’ll examine some important examples of attempts to build up bodies of knowledge from axioms.

Mathematicians have been thinking about how to organize knowledge for thousands of years. As programmers, we will use their organizational principles in our domain of algorithms and data structures.

**9.1 Proofs**

People had been discovering and using mathematical results long before they started proving them. Yet mathematical proofs are also a surprisingly old invention. For centuries mathematicians relied on *visual* proofs. The ancient Greeks realized that they could use our innate spatial reasoning to prove algebraic facts.

Here are some examples of visual proofs.

*Commutativity of addition: a* + *b* = *b* + *a*

If we have two strips of paper and tape them together to make one strip, we get the same length regardless of which one is on the left and which one is on the right. We can see this because the figure on the right is a mirror image of the figure on the left.

*Associativity of addition:* (*a* + *b*) + *c* = *a* + (*b* + *c*)

If we have three strips of paper and we tape the pieces together to make one long strip, it doesn’t matter if we tape the first two pieces together and then tape the third one to the result, or if instead we tape the last two and then the first. Either way we’ll end up with a strip of the same length in the end.

*Commutativity of multiplication: ab* = *ba*

A rectangle has a certain length and a certain width. If you turn it sideways, you’ve reversed length and width, but you obviously still have the same rectangle. In fact, this essential argument appears in a 19th-century book by Dirichlet, who says that whether you arrange soldiers in rows or columns, you still have the same number.

*Associativity of multiplication:* (*ab*)*c* = *a*(*bc*)

Whether you slice this rectangular prism along one axis or along another, when you put the slices back together, you still have the same volume.

(*a* + *b*)^{2} = *a*^{2} + 2*ab* + *b*^{2}:

It’s clear just by looking that the rectangle on the lower left is the same area as the rectangle on the upper right: not only do both have area *ab*, but you could literally cut one out, turn it sideways, and lay it on the other.

π *>* 3:

Here we’ve inscribed a regular unit hexagon (one whose sides are all of length 1) in the circle. It’s evident that the perimeter of the hexagon is shorter than the circumference of the circle, because whenever we have two intersection points between the two figures, the shortest path from one point to the next is along the hexagon, not the circle. Since the triangles that make up the hexagon are equilateral, all their sides are length 1, so the diameter of the circle is length 2. So the ratio of the circle’s circumference to its diameter (i.e., π) must be greater than the ratio of the hexagon’s perimeter (6) to its diameter (2).

**Exercise 9.1.** Design visual proofs for the following:

**Exercise 9.2.** Using a visual proof, find an upper bound for π.

* * *

As useful as visual proofs are, this technique isn’t sufficient to prove every type of proposition in mathematics, and some of the proofs are no longer considered rigorous enough. Modern mathematicians have a variety of proof techniques available to them, some of which we’ve used throughout this book, and which are summarized in *Appendix B*. Proofs show connections between different truths. But what exactly constitutes a proof? Today, we use the following definition:

**Definition 9.1.** A **proof** of a proposition is

• An argument

• Accepted by the mathematical community

• To establish the proposition as valid

The second point is often overlooked: proof is fundamentally a social process, and one that changes over time. Our confidence in a proof increases as more people understand and agree with it. At the same time, what is considered a valid proof today might not be considered a valid proof 300 years from now, just as some proofs that were viewed as valid by Euler—the greatest 18th-century mathematician—are frowned upon today.

Now we’ll turn to another building block of mathematical knowledge, theorems.

**9.2 The First Theorem**

As we discussed in *Chapter 2*, ancient Mediterranean civilizations believed that the Egyptians were the source of mathematical knowledge. When Greek civilization was just starting, Egyptian civilization had already existed for thousands of years, so it is not surprising that the leading thinkers of ancient Greece would travel to Egypt to study with their priests and learn their wisdom. The first such person known to us is Thales of Miletus. Thales learned geometry from the Egyptians, but he went beyond their work. While the Egyptians had algorithms, Thales had a theorem—in fact, he invented the very notion of a theorem, which is a proposition derivable from other propositions. Today Thales is regarded as the founder of Western philosophy, and might also be considered the first mathematician.

**Thales of Miletus (flourished early 6th century BC)**

Some time around the year 750 BC a new society started to appear in different coastal regions of the Mediterranean and even as far north as the Black Sea. They called themselves Hellenes; we call them Greeks. They came from a small mountainous country where the geography prevented the emergence of a large unified kingdom as was common elsewhere. Greeks lived in small, independent city-states unified not by a central government, but by a common language and culture. Whenever a city’s population exceeded its resources, it would send some of its citizens to settle a colony, a new practically independent city on some conveniently located bay with a river. Within 200 years Greeks settled around the Mediterranean, as Plato put it, “like frogs around a pond.”

By somewhere around 600 BC, the Greek colonies in Asia Minor (what is now Turkey) were getting wealthy. Instead of spending all the extra money on luxuries, some of them started supporting intellectual pursuits. For the first time in history they looked beyond mythology for the answers to eternal questions such as what things were made of. The first person to do this in a fundamental way was Thales of Miletus. Thales was the originator of what ancient Greeks would eventually call philosophy and what we now call science. He wanted to find the natural, non-mythological explanation of reality. He proposed that all visible reality is made out of one single substance: water. Therefore, visible reality exists in one of three states—gas, liquid, or solid—and there are transitions between the states.

While in Egypt, Thales collected many geometric algorithms and, probably, some Babylonian astronomical knowledge. Herodotus reports that Thales was able to predict a total solar eclipse a year in advance. Aristotle—usually a reliable source—tells us that Thales was able to predict an exceptionally large harvest of olives by studying weather patterns and, by buying options on the use of all the olive presses in the region, made a fortune. There are many other stories about his accomplishments, such as his discovery of static electricity. While we do not know exactly which stories are true, Thales clearly amassed a large body of scientific knowledge and was able to apply it to practical problems. His knowledge did not perish with him; his students carried the program forward. But more important than any of his specific discoveries was his approach to understanding the world, which is still the basis of all science.

**Theorem 9.1 (Thales’ Theorem):** *For any triangle ABC formed by connecting the two ends of a circle’s diameter (AC) with any other point B on the circle, **∠**ABC = 90°.*

*Proof.* Consider the triangles formed by joining point *B* with the center of the circle, *D*:

Since *DA* and *DB* are both radii of the circle, they are equal and triangle *ADB* is isosceles. The same is true for *DB*, *DC*, and triangle *BDC*. Therefore

where we get the third equation by adding the previous two. It was also known that the angles of a triangle add up to 180°, and we can see that ∠*CBA* is the sum of ∠*DBA* and ∠*DBC*, so

∠*DAB* + ∠*DCB* + ∠*DBA* + ∠*DBC* = 180°

By substituting using the equality we established, we can write this as follows:

Why was Thales’ discovery so important? What he realized is that truths are connected. He saw that if you have one piece of knowledge, you can use it to find another. Furthermore, theorems are essential to the idea of abstraction, for the value of a theorem is that it applies to *all* entities that have certain properties.

**9.3 Euclid and the Axiomatic Method**

If we want to build up a system of knowledge, proofs and theorems are essential tools. But we also need to have a set of starting assumptions, or *axioms*, as a foundation for our system.

The first appearance of the *axiomatic method*, in which an entire mathematical system was built on the basis of a few formal principles, is in Euclid’s *Elements*. In fact, for centuries Euclid’s were the only known examples of axioms, and they applied only to geometry.

Euclid divided his principles into three groups: definitions, postulates, and common notions. He starts with his 23 definitions, which relate to geometric figures. Here are a few of them:^{1}

* ^{1}* As before, we use Sir Thomas Heath’s translation of Euclid’s

*Elements*.

**1.** A point is that which has no parts.

**2.** A line is a breadthless length.

**23.** Parallel straight lines are straight lines which, being in the same plane and being produced indefinitely in both directions, do not meet one another in either direction.

Next, he gave the following five “common notions”:

**1.** Things which are equal to the same thing are also equal to one another.

**2.** If equals be added to equals, the whole are equal.

**3.** If equals be subtracted from equals, the remainders are equal.

**4.** Things which coincide with one another are equal to one another.

**5.** The whole is greater than the part.

Today we would express these notions as follows:

**1.** *a* = *c* ∧ *b* = *c* * a* = *b*

**2.** *a* = *b* ∧ *c* = *d* * a* + *c* = *b* + *d*

**3.** *a* = *b* ∧ *c* = *d* * a − c* = *b − d*

**4.** *a* *b* * a* = *b*

**5.** *a < a* + *b*

What’s interesting about these common notions is that, unlike the 23 definitions, the notions are not limited to geometry; they also apply to positive integers. In fact, these common notions, such as transitivity of equality, are essential to programming.^{2}

* ^{2}* The definition of regular types in

*Chapter 7*is derived from these Euclidean notions.

Finally, Euclid introduced his famous five postulates. These are stated in terms of allowable operations in the “computational machinery” of his geometric system. You can read the first three as being prefixed with a statement like “There is a procedure...”:

**1.** To draw a straight line from any point to any point.

**2.** To produce a finite straight line continuously in a straight line.

**3.** To describe a circle with any center and distance.

**4.** That all right angles are equal to one another.

**5.** That, if a straight line falling on two straight lines makes the interior angles on the same side less than two right angles, the two straight lines, if produced indefinitely, meet on that side on which are the angles less than the two right angles.

If we were writing Euclid’s system today, we would consider both “common notions” and “postulates” to be *axioms*—unprovable assumptions on which the rest of the system is built.

Euclid’s fifth postulate, which provides the basis for reasoning about parallel lines, is the most important axiom in the history of mathematics. Also known as the *parallel postulate*, it expresses the relation shown in the following diagram:

However, there are many equivalent ways to express the same notion:

• Given a line and a point not on it, at most one parallel to the given line can be drawn through the point.^{3}

* ^{3}* This formulation, which is often taught as “the parallel postulate” in secondary school geometry, was actually published by Scottish mathematician John Playfair in 1795, and is properly known as

*Playfair’s Axiom*.

• There exists a triangle whose angles add up to 180°.

• There exist two similar triangles that are not congruent.

**9.4 Alternatives to Euclidean Geometry**

Almost from the time Euclid stated his five postulates, mathematicians felt that there was something different about the fifth one. Intuitively, they felt that the first four postulates were somehow more fundamental; perhaps the fifth postulate could be derived from the others, and therefore was not a true axiom. Thus began a 2000-year search for a proof of the fifth postulate, one pursued by such luminaries as the astronomer (and mathematician) Ptolemy (90–168), the poet (and mathematician) Omar Khayyam (1050–1153), and the Italian priest (and mathematician) Giovanni Girolamo Saccheri, S.J. (1667–1733). Saccheri wrote a book called *Euclidus Vindicatus* (“Euclid Vindicated”) in which he constructed a whole geometrical system based on the the assumption that the fifth postulate is false, then claimed that the consequences would be so bizarre that the postulate must be true.

While most 18th-century mathematicians didn’t care about axioms, the mood shifted in the 19th century. Mathematicians started to focus on the foundations of their work. They revisited geometry, no longer taking Euclid for granted, but examining his assumptions.

Around 1824, Russian mathematician Nikolai Lobachevsky was working on the problem. At some point, he realized that the parallel postulate was just one possible assumption, and that the contrary assumption is equally valid. Instead of saying “there is at most one line through a point parallel to a given line,” Lobachevsky essentially explored the idea that “there are many lines....” Unlike Saccheri, Lobachevsky realized that the resulting system of geometry was entirely consistent. In other words, he invented an entirely new non-Euclidean geometry, sometimes called *hyperbolic* geometry.

In Lobachevsky’s geometry, there are no similar triangles except for congruent ones. By way of analogy, think of triangles on the surface of a sphere. For small triangles, the surface is almost planar, so the sum of the angles is close to 180°. But as the triangles get bigger, the angles need to get bigger because of the curvature of the surface. Lobachevsky’s model was similar, but with space curved in the opposite way, so that bigger triangles corresponded to smaller angles.

Lobachevsky’s results, first published in 1826, were met with dismissal and scorn from the Russian mathematical community, and Lobachevsky himself was marginalized. One person who did recognize the validity of Lobachevsky’s work was Gauss, who learned Russian to read Lobachevsky’s book. But in general, it would take many years before his work became an accepted part of mathematics. Today, Lobachevsky’s discovery is considered to be a monumental turning point in the history of mathematics.

**Nikolai Ivanovich Lobachevsky (1792–1856)**

In the early 19th century, Russia was not a major center for mathematics (despite Euler spending much of his career in St. Petersburg). There were no great Russian mathematicians. Yet by the middle of the 20th century, Russia was a mathematical superpower. This transformation began with the first great Russian mathematician, Nikolai Ivanovich Lobachevsky.

Lobachevsky did not come from a major city, nor did he attend one of the two great universities (Moscow and St. Petersburg); he was not sent abroad to learn from the leading thinkers of Europe. He did not come from the aristocracy or even the upper middle class; he and his brother were charity students at their local school. He grew up in Kazan, a provincial city on the Volga river that did not even have a university until 1805. Lobachevsky entered the recently founded university in 1807. (Interestingly, Tolstoy and Lenin attended the same school decades later.)

When Lobachevsky started at the University of Kazan, there was no one to teach mathematics—students studied on their own. Fortunately, Martin Bartels, one of Gauss’s former professors, soon joined the faculty. After receiving a master’s degree and continuing to study privately with Bartels, Lobachevsky was appointed as an adjunct professor in 1814. He would go on to spend most of his career at the university, eventually being elected its rector (similar to president) in 1827.

Despite his humble origins, Lobachevsky was never afraid to challenge conventional opinions. His groundbreaking work on non-Euclidean geometry was submitted in 1826, but was not widely known until it was published as a book in 1832. The book was publicly ridiculed in a review by Ostrogradsky, an important Russian mathematician who studied with Cauchy.

Lobachevsky continued his work on non-Euclidean geometry for the rest of his life, refining it and publishing books about it in various languages. By the 1840s, Gauss recognized the importance of the work, even reading some of Lobachevsky’s books in the original Russian. Gauss nominated him for membership in the Göttingen Academy of Sciences, a great honor at the time. Yet Lobachevsky was still ostracized by the Russian mathematical establishment until the end of his career.

In his later years, Lobachevsky’s life took a tragic turn. He lost his job at the university, his house, and most of his property, suffered the deaths of two of his children, and then became blind. Even under these circumstances, he persisted in his work, dictating a major new book, *Pangeometry*, just before his death in 1856.

Often when a new idea emerges in math or science, it is discovered independently by multiple people at roughly the same time. This was the case with non-Euclidean geometry. At about the same time Lobachevsky was working in Kazan, a young Hungarian mathematician named János Bolyai made a similar discovery. A few years later, Bolyai’s father Farkas Bolyai, a well-known math professor and friend of Gauss, included the son’s results as an appendix to one of his own books. Farkas sent Gauss the book. Although Gauss privately remarked that young Bolyai was a genius, the letter he sent Farkas had a discouraging message:

If I commenced by saying that I am unable to praise this work, you would certainly be surprised for a moment. But I cannot say otherwise. To praise it would be to praise myself. Indeed the whole contents of the work, the path taken by your son, the results to which he is led, coincide almost entirely with my meditations, which have occupied my mind partly for the last thirty or thirty-five years.

The letter is typical of Gauss, both in his refusal to give credit to others and in his insistence that his own unpublished thoughts gave him priority. (We now know that Gauss had indeed discovered many of the same ideas, but had decided not to publish them because he was afraid of the reaction.) Why he acknowledged Lobachevsky’s work but dismissed Bolyai’s we will never know. But whatever the reason, the results were tragic. Bolyai was devastated by Gauss’s response and never attempted to publish in mathematics again. Even sadder, he became mentally unstable. When he came across Lobachevsky’s book sometime later, he was convinced that “Lobachevsky” was actually a pseudonym for Gauss, whom he believed had stolen his ideas.

* * *

Once non-Euclidean geometry was discovered, many mathematicians wrestled with what they considered to be an important question: which geometry is actually correct, Euclid’s or Lobachevsky’s? Gauss took the question quite seriously, and proposed an ingenious experiment to test the theory.

First, find three mountains forming a triangle that are some distance apart, but close enough so that a person standing on top of each with a telescope can see the others. Then set up surveying equipment on each peak to accurately measure the angles of the triangle. If the angles add up to 180°, then Euclid is right; if their sum is less than 180°, then Lobachevsky is.

The actual experiment was never conducted. But over time, the question became moot. Other mathematicians would ultimately prove the independence of the fifth postulate, showing that if Euclidean geometry is consistent, then so is Lobachevskian geometry. Meanwhile, mathematicians began to treat questions of reality as irrelevant. While math was originally invented to understand aspects of the world we live in, by the end of the 19th century, it began to be seen as a purely formal exercise.

**9.5 Hilbert’s Formalist Approach**

One must be able to say “tables, chairs, beer-mugs” each time in place of “points, lines, planes.”

—David Hilbert

David Hilbert, perhaps the greatest mathematician of the early 20th century, was the leader of this formalist approach. In a view that eventually became standard throughout mathematics, he said that if a theory was consistent, it was true.

While all of Euclid’s theorems and proofs are correct, by modern standards the axioms are somewhat shaky. It took 2400 years before anyone tried to come up with a better foundation for geometry. Hilbert spent 10 years rethinking Euclid and constructing his own axiomatic system for geometry. As the quotation suggests, Hilbert believed that the validity of his axiomatic system should not rely on any intuitions about geometry. Hilbert’s system contained many more axioms than Euclid’s, making explicit many things that Euclid took for granted. Hilbert had:

• 7 axioms of connection (e.g., if two points lie on a plane, then all points on the line going through these points are on this plane)

• 4 axioms of order (e.g., there is a point between any two points on a line)

• 1 axiom of parallels

• 6 axioms of congruence (e.g., two triangles are congruent if side-angle-side...)

• 1 Archimedes’ axiom

• 1 completeness axiom

Hilbert’s geometric system is quite complex, and was the subject of several of his courses. Unfortunately, by the time he was done constructing the axioms, he had no energy left to prove many geometric theorems. Hilbert’s work on the axioms of Euclidean geometry was the last major work done on that subject.

**David Hilbert 1862–1943**

David Hilbert was born in the German city of Königsberg (now Kaliningrad, Russia). He studied mathematics at the the University of Königsberg, continued for a Ph.D., and eventually joined the faculty.

At age 33, he accepted an offer to become a professor at the University of Göttingen. He would stay there for the rest of his career. As we saw earlier (*Section 8.2*), Göttingen was the center of the mathematical universe, and Hilbert eventually became the leader of the mathematical community there during the pinnacle of the department’s fame.

It is difficult to convey the astounding variety of fundamental work done by Hilbert and the profound effect he had on all of mathematics.

In his initial work on invariant theory, Hilbert championed the use of nonconstructive proofs, which was a radical idea at the time. In fact, he initially became famous as much for the approach as for the actual result. Today, nonconstructive proofs are common.

When asked to summarize work on algebraic number theory (the area Dedekind had been working on), Hilbert wrote a 600-page volume called *Zahlbericht* (“Report on Numbers”). This book captured and explained all the major developments in the field. While he mostly summarized (and credited) the work of others, Hilbert’s unification drove the field forward, eventually leading to Noether’s work on abstract algebra.

For the next 10 years, while working on geometry, Hilbert went beyond Lobachevsky and examined the validity of *all* of Euclid’s axioms. His book *Foundations of Geometry* not only introduced his new axioms, but also taught people for the first time how to think about and rigorously analyze any axiomatic system.

Hilbert also worked on physics, co-inventing general relativity theory, largely independently and at roughly the same time as Einstein. His invention of *Hilbert spaces*—an extension of vector spaces to infinite dimensions—became an important building block in the mathematical foundation of quantum mechanics.

In 1900, Hilbert gave a lecture at the Sorbonne in Paris where he listed 10 important unsolved problems in mathematics and challenged the community to work on them. The list was later expanded to 23 problems in a published paper. Work on these problems, which became known as *Hilbert’s problems*, defined much of mathematics in the 20th century. He also spent much of the last 25 years of his career working on mechanizing the foundations of mathematics, an effort known as “Hilbert’s program.” Although Hilbert’s program was shown to be flawed by the work of Kurt Gödel and Alan Turing, that same work led to the development of the modern theory of computation.

Hilbert was not only a great mathematician, but also a great mentor and supporter of younger colleagues. When his best friend Hermann Minkowski died, Hilbert spent several years editing and publishing Minkowski’s work. He championed the career of Emmy Noether (*Section 8.3*). He also collaborated with many researchers in several fields; his lectures on physics became the basis of a classic text co-authored by Richard Courant.

Hilbert’s one blind spot was his pride in German culture. With good reason, he saw mathematics in Germany as the culmination of 200 years of advances. He welcomed people from all over the world to join the German mathematical community. But he also believed that *only* the research in Germany was worthy of attention. Perhaps the most egregious example was his unwillingness to cite the work of Giuseppe Peano in Italy or recognize its seminal importance to the foundations of mathematics. At the same time, Hilbert was completely opposed to the views of the Nazis (who came to power a few years after his retirement in 1930), having spent much of his career promoting the work of many colleagues who happened to be Jewish, including his best friend Minkowski and his protegé Noether.

Sadly, Hilbert lived to see everything he cared about destroyed. His friends were driven into exile, his once-great department was reduced to mediocrity, and his beloved country embraced beliefs he despised. But his mathematical legacy was carried around the world by his many students and collaborators, and lives on today.

**9.6 Peano and His Axioms**

Certainly it is permitted to anyone to put forward whatever hypotheses he wishes, and to develop the logical consequences contained in those hypotheses. But in order that this work merit the name of Geometry, it is necessary that these hypotheses or postulates express the result of the more simple and elementary observations of physical figures.

—Giuseppe Peano

Even before Hilbert announced his program on formalizing mathematics, others had been working on similar ideas about formalizing mathematical systems. One of these was Italian mathematician Giuseppe Peano. As the quotation shows, Peano was still interested in the connections between mathematics and reality. In 1891, he began writing *Formulario Mathematico* (“Mathematical Formulas”), which would become a comprehensive work containing all essential theorems in mathematics expressed in a symbolic notation Peano invented. Much of his notation, such as the symbols for quantifiers and set operations, is still used today.

In 1889, Peano published a set of axioms that provided a formal basis for arithmetic. There were five, just like Euclid’s:

There is a set called the *natural numbers*:

**1.** ∃0

**2.** ∀*n * : ∃*n′ * - called its *successor*

**3.** ∀ ⊂ : (0 ∧ ∀*n* : *n * * n′ * ) =

**4.** ∀*n, m * : *n′* = *m′* * n* = *m*

**5.** ∀*n * : *n′* ≠ 0

In English, we might write them like this:

**1.** Zero is a natural number.

**2.** Every natural number has a successor.

**3.** If a subset of natural numbers contains zero, and every element in the subset has a successor in the subset, then the subset contains all natural numbers.

**4.** If two natural numbers have the same successor, then they are equal.

**5.** Zero is not the successor of any natural number.

The third axiom, known as the *axiom of induction*, is the most important. It says that if we take any subset *S* of that contains zero and obeys the rule that the successor of every element is also in *S*, then *S* is the same as . Another way to put this is “there are no unreachable natural numbers”; if you start with zero and keep taking the successor, you’ll eventually get to every natural number. Many modern texts put this axiom last, but we use Peano’s order.^{4}

* ^{4}* Modern texts often also start natural numbers with 1 rather than 0.

Peano’s axioms transformed arithmetic. In fact, he was building on earlier work by Richard Dedekind and Hermann Grassman, both of whom showed how to derive some basic principles of arithmetic. But Peano went further, and his contributions were so important that mathematicians since then talk about *Peano arithmetic*, not just arithmetic.

**Giuseppe Peano (1858–1932)**

Giuseppe Peano was born into a peasant family near Turin in the north of Italy, right around the time Italy became a unified country. He attended the University of Turin and eventually joined the faculty there. Later, he also began teaching at the Royal Military Academy. Among his best-known achievements was the discovery of the space-filling curve, known as a Peano curve, which provided a continuous mapping from a one-dimensional segment to every point on a two-dimensional square.

For most of the 1890s, Peano worked on the foundations of mathematics and his great book *Formulario Mathematico. Formulario* was meant to be a compendium of all mathematical results, written formally. It was a masterpiece, not only providing a foundation for mathematics but also covering a variety of topics, together with references to the sources in their original languages. Peano gave a copy of the book to the British philosopher Bertrand Russell, and it strongly influenced Russell’s work with Whitehead, *Principia Mathematica*, which would come to play an important role in early theories of computation.

Initially, Peano published *Formulario Mathematico* in French, but he was frustrated by the ambiguity inherent in any natural language. Eventually, around 1900, he decided that the only solution was to invent an unambiguous universal language for science and mathematics, and to then use this for his writing.

The language Peano designed was called *Latine sine Flexione* (“Latin without Inflection”), later renamed “Interlingua.” His idea was to start with Latin, but to replace all its confusing declensions, conjugations, and irregular words with a simple, logical set of rules.

Peano rewrote *Formulario* in his new language, and this edition was published in 1908. Here’s what his famous axioms looked like in Interlingua:

**0.** *N*_{0} es classe, vel “numero” es nomen commune.

**1.** Zero es numero.

**2.** Si *a* es numero, tunc suo successivo es numero.

**3.** *N*_{0} es classe minimo, que satisfac ad conditione 0, 1, 2; [...]

**4.** Duo numero, que habe successivo aequale, es aequale inter se.

**5.** 0 non seque ullo numero.

Peano also started using his formal notation in his teaching, which probably did not endear him to his students. In addition, he turned every course he was supposed to be teaching into a discussion of the foundations of mathematics, which eventually caused him to lose his position at the military academy.

Peano’s dream was that other scientists would start publishing their work in Interlingua, but this did not happen. In fact, few people even attempted to read Peano’s book, and his work was largely ignored. Toward the end of his life, Peano spent much of his time trying to promote Interlingua, and he was mostly forgotten by the mathematical community; they were more interested in the work of Hilbert and others at Göttingen.

Even today, despite embracing Peano’s foundational axioms of arithmetic, most mathematicians have never read more than the first page of his monumental work. It has been out of print for years, and has never been translated into English.

To prove that every axiom is needed, we need to remove each one from the set and demonstrate that the remaining set has consequences that do not meet our intent—in this case, that they do not correspond to what we mean by natural numbers.

*Removing existence of 0 axiom.* If we remove this axiom, we are forced to drop all axioms that refer to zero. Since we have no elements to start with, the other axioms never apply and can be satisfied by the empty set, which is clearly not a model of natural numbers.

*Removing totality of successor axiom.* If we remove the requirement that every value have a successor, then we end up allowing finite sets like {0} or {0, 1, 2}. Clearly, no finite set satisfies our notion of natural numbers. (However, on computers, we give up this axiom, since all of our data types are finite; for example, a uint64 can express only the first 2^{64} integers.)

*Removing induction axiom.* If we remove the induction axiom, then we end up with the situation where we have more integer-like things than there are integers. These “unreachable” numbers are called *transfinite ordinals* and are designated by *ω*. So we could end up with sets like *{*0, 1, 2, 3,*..., ω, ω* + 1, *ω* + 2,*...}*, *{*0, 1, 2, 3,*..., ω*_{1}, *ω*_{1} + 1, *ω*_{1} + 2,*..., ω*_{2}, ω_{2} + 1, *ω*_{2} + 2,*...}*, and so on.

*Removing invertibility of successor axiom.* If we remove the requirement that equal successors have equal predecessors, then we’re allowing “ *ρ*-shaped” structures where an item can have multiple predecessors, some earlier in the sequence and some later, such as {0, 1, 1, 1,*...}*, {0, 1, 2, 1, 2,*...}*, or {0, 1, 2, 3, 4, 5, 3, 4, 5,*...}*. Since all of these structures are finite, they clearly do not include all natural numbers.

*Removing “nothing has 0 as its successor” axiom.* If we remove this axiom, then we’d allow structures that loop back to zero, like *{*0, 0,*...}* and *{*0, 1, 0, 1,*...}*. Again, these structures are finite, so they do not capture our notion of natural numbers.

**9.7 Building Arithmetic**

Now that we have established that all of Peano’s axioms are independent, and therefore necessary for our notion of natural numbers, we can build up arithmetic from first principles. We’ll do this now by defining exactly what it means to add and multiply two natural numbers.

*Definition of Addition:*

We are not *proving* these statements; we are defining addition to *be* these statements. All properties of adding natural numbers follow from this definition. For example, here’s how we prove that 0 is the left additive identity:

In the basis step, we assert that it’s true when *a* is zero. We know this because of *Equation 9.1* in the definition of addition. In the inductive step, we assume it’s true for any *a*. By *Equation 9.2*, we know that 0 + *a′* = (0 + *a*)*′*. But by the assumption of the inductive step, we can substitute *a* for 0 + *a*, so our result is *a′*, and therefore 0 + *a′* = *a′*.

*Definition of Multiplication:*

We can now prove that 0 · *a* = 0, much as we did for addition:

*Definition of 1*. We also define 1 as the successor of 0:

Now we know how to add 1:

We also know how to multiply by 1:

*a ·* 1 = *a · *0′ = *a · *0 + *a* = 0 + *a* = *a*

We can derive fundamental properties of addition as well; they follow from the axioms.

*Associativity of Addition:* (*a* + *b*) + *c* = *a* + (*b* + *c*)

inductive step:

To get commutativity, we’ll start by proving it for the special case:

inductive step:

*Commutativity of Addition: a* + *b* = *b* + *a*

inductive step:

**Exercise 9.3.** Using induction, prove:

• Associativity and commutativity of multiplication

• Distributivity of multiplication over addition

**Exercise 9.4.** Using induction, define total ordering between natural numbers.

**Exercise 9.5.** Using induction, define the partial function *predecessor* on natural numbers.

* * *

Do Peano axioms define natural numbers? No; as Peano put it, “number (positive integer) cannot be defined (seeing that the ideas of order, succession, aggregate, etc., are as complex as that of number).” In other words, if you don’t already know what they are, Peano’s definitions won’t tell you. Instead, they *describe* our existing idea of numbers, formalizing our notions of arithmetic, which helps provide a way to structure proofs.

In general, we can say that axioms explain, not define. The explanation may not be constructive; that is, it might not say how the result is achieved. Even if it does suggest an algorithm, the algorithm could be computationally very inefficient. No sane person would do addition by repeated application of the successor function. But these axioms still serve a useful purpose; they get us to think about which properties of natural numbers are essential and which are not.

This approach is a good attitude to take when studying the documentation for a programming interface. Why is that requirement imposed? What would the consequences be if it were not there?

**9.8 Thoughts on the Chapter**

We began the chapter by looking at the notion of proof, a formal—yet social—process for demonstrating the truth of a proposition. We saw how proofs show connections between truths; proof systems are a way to organize knowledge. We also looked at the discovery of theorems, and the important abstraction they provide.

Next we looked at a richer formalism for organizing knowledge, the axiomatic system, and saw how geometry and arithmetic could be built up from first principles. The critical role of axiomatic systems is their ability to reduce the complexity of knowledge. You don’t need to memorize all the true propositions, because you can derive them from a few axioms and inference rules.

However, it’s important to remember that historically, mathematicians did not really start with axioms and derive theorems from them. The axioms were proposed only after the interrelationships between the theorems were well understood and the assumptions underlying them identified. The same process holds for programming: designing good abstractions requires examining a large number of real algorithms and understanding their interrelationships.

While axiomatic systems allow us to organize knowledge, they presuppose that we already have some knowledge to organize. Discovery of a theorem is a more important thing than proving it—you cannot attempt to prove something unless you have reason to believe it is a truth.

Sometimes modern mathematicians forget the empirical origins of knowledge. In his book *The Method*, the great Greek mathematician Archimedes discussed how any means for acquiring mathematical knowledge was valid, including measurement and experimentation. Only after discovering mathematical truths should one attempt to derive a rigorous proof. The same principle applies to programming: before trying to prove a program correct, we should try to write correct programs—even if our attempts involve trial and error.