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

Image

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)

Image

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

Image

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)

Image

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 = a2 + 2ab + b2:

Image

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:

Image

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:

Image

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.

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

Image

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

Image

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

Image

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:

Image
Image

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.

Image

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 = cb = c Image a = b

2. a = bc = d Image a + c = b + d

3. a = bc = d Image a − c = b − d

4. a Image b Image 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:

Image

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

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.

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 Image called the natural numbers:

1. ∃0 Image Image

2.n Image Image : ∃n′ Image Image - called its successor

3.ImageImage : (0 Image Image ∧ ∀n : n Image Image Image n′ Image Image) Image Image = Image

4.n, m Image Image : n′ = m′ Image n = m

5.n Image Image : 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 Image that contains zero and obeys the rule that the successor of every element is also in S, then S is the same as Image. 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.

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 264 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:

Image
Image

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:

Image

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:

Image
Image

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

Image

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

Image

Now we know how to add 1:

Image

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)

Image

inductive step:

Image

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

Image
Image

inductive step:

Image

Commutativity of Addition: a + b = b + a

Image

inductive step:

Image

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.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
3.146.105.137