The Nature of Proof

Introduction

In this dissertation we aim to look at the evolution of how things are proved in mathematics; ranging from ancient mathematics to modern times we will focus on the approaches to proof through looking at axiomatic systems. This dissertation has a chronological theme which is to help the flow of discussion around the evolution in the way that proof was approached.

Euclid’s Postulates

The Origins of Mathematics

The early roots of mathematics traces back to 3,000BC: this was the beginning of the Egyptian-Babylonian period (around 3,000BC – 300BC). During this period mathematical techniques were developed, predominantly for practical application. It seems remarkable the advances that were made by the Egyptians in particular, as they had nothing to resemble mathematical notation; that is to say there was no symbol for ‘plus’ or ‘minus’ and no zero, yet they were able to develop their civilisation and build such creations as the Pyramids!

On the other hand, the Babylonians were more ambitious with their use of mathematics in a sense. They were interested in the practical applications, as the Egyptians were, but they also demonstrated an interest in the theory of mathematics i.e. the ‘how’ and ‘why’. The Babylonians recognised a link between geometry and algebra although geometry was constructed as a way to facilitate the use of algebra, not as a ‘mathematical tool’ in its own right. Neither civilisation provided proofs or theorems in their work, but they did lay down the foundations for another civilisation that did.

The ancient Greeks are associated with the first golden age of mathematics, and our own civilisation owes a great debt to them: they began the process of proving theorems instead of just seeking practical applications. There was an overlap between the Egyptian-Babylonian period and the Greek period (around 600 BC – 300BC).

Axioms

The ancient Greeks introduced the idea of proving theorems by making use of axioms.

“Formally, we can define a theorem in the axiom system to be a statement about the terms of the system which is logically implied by the conjunction of the axioms.” ([6], page 106.)

Mathematics is founded upon axioms: a set of assumptions which cannot be proved but are required in order to prove theorems and propositions through logical deduction. Throughout this text we will look at some of the most important axiomatic systems but for now let us illustrate the problem with not observing the rigorous logic of mathematics. We use an interesting example which appears to ‘prove’ that 2=1. The‘proof’ is taken from appendix 7 of “Fermat’s Last Theorem” by S.Singh ([13], page 319).

“a = b

a2 = ab

a2+a2-2ab = ab+a2-2ab

2(a2-ab) = a2-ab

2 = 1”

So where did it all go wrong? The first step where we multiply both sides by a is perfectly legitimate. The second step of adding a2-2ab to both sides is also fine. In the third step all we have done is simplify each side. So the mistake must come from the fourth step where we divide by a2-2ab. Notice that initially we state that a = b: thus a2-ab = a2-a2 = 0. Division by 0 is not permitted and thus the final step is incorrect. This is obviously a contrived example to illustrate the point that illogical steps are, well, illogical! The key point is that mathematical work must come from logical deductions that adhere to the axioms on which mathematics is built. We will now look at a mathematician who is thought to be the first major contributor to this way of using mathematics.

Thales of Miletus

Thales of Miletus (around 300 BC) was the first prominent philosopher of which major contributions to mathematics were attributed to. Before him there were no axioms, i.e. foundations, to work from and so Thales came up with five theorems on which he would then develop and build upon. His five theorems were as follows:

  1. The angles at the base of an isosceles triangle are congruent;
  2. If two straight lines cut one another, the vertical angles are congruent;
  3. Two triangles are congruent if they have two angles and the included side of one congruent to two angles and the included side of the other (i.e. if they have a side and two angles the same, then they are equivalent);
  4. A circle is bisected by a diameter;
  5. An angle inscribed in a semi circle is a right angle.

([1], pages 145 & 146.)

Thales pioneered this approach to mathematics; this was the first step towards an axiomatic system (discussed in more detail later on). From his five theorems Thales developed existing mathematical knowledge while providing proof of its validity. Although this was a step towards an axiomatic system it can’t be called an axiomatic approach; this is because the theorems aren’t basic enough to be assumed. It was still extremely significant as Thales based his arguments upon logic, even in trivial cases, as opposed to taking ‘obvious’ properties for granted, as the Egyptians and Babylonians did when using mathematics for practical application.

Pythagoras of Samos

The next major contributor that we will discuss is Pythagoras of Samos (around 540 BC). He was the founder of the Pythagorean brotherhood that was perhaps the most influential in the first golden age of mathematics. Most people will recall Pythagoras’ theorem from school, regardless of their mathematical education, but few will appreciate its importance in the development of mathematics. The simple theorem stated by the brotherhood is as follows: a2 + b2 = c2: where a, b and c are the lengths of the sides of a right-angled triangle, with c being the length of the hypotenuse. That was over two thousand years ago and yet it is as profound now as it was then. Why? Because once something is proved to be true in mathematics, true it forever will be. Pythagoras’ Theorem was another brick in the wall, laying down the foundations for other theorems such as the trigonometric identity sin2x + cos2x = 1and Fermat’s Last Theorem to name but a few. This is only possible due to the concrete nature of proof.

We will now consider one of the more famous discoveries by the Pythagorean brotherhood; that is irrational. This contrasted with Pythagoras’ view of the ‘perfection’ of numbers and legend has it that he was so upset that he had the disciple who discovered this fact killed ([13], pages 53 & 54). The proof is as follows; and is adapted from pages 36 & 37 of [7]:

(We will use reductio ad absurdum, i.e. ‘reduction to the absurd’, to prove that is irrational. This amounts to assuming that is rational and proving that this can’t be true: i.e. that this is absurd!)

Assume that is rational and express it as p/q; where p and q are non-zero integers and have no common factors. Then is written in lowest terms.

So we take = p/q and multiply both sides by q therefore clearing the denominators. Now we have q = p. Squaring both sides gives us 2q2 = p2.

Notice that p2 must be even because it is equivalent to an integer multiple of 2. Therefore p must be even because any odd number squared is also odd. Write p = 2r and substitute this into the equation for p.

Now we have 2q2 = (2r)2 = 4r2. Dividing by 2 gives us p2 = 2r2. In the same way that we deduced that p must be even we can deduce that q must also be even. This means that p and q have a common factor of 2: this is a contradiction. Hence is irrational.

This is proof is attributed to Euclid, “the father of geometry”, who is the main focus for our discussion of proof in ancient mathematics.

Euclid of Alexandria

Euclid of Alexandria (around 300 BC) was a Greek philosopher and mathematician who made the first contribution to the axiomatic system; building upon the works of scholars such as Thales and Pythagoras.

“From a formal standpoint, mathematics operates according to something known as the ‘axiomatic method’. This was first introduced by Euclid over two thousand years ago and has subsequently evolved, particularly during the last one hundred fifty years, into the current modus operandi(i.e. ‘mode of operation’)of mathematics.” ([6], page 93.)

Euclid defined five postulates (axioms specific to geometry) to act as a foundation on which he could build up a structure of mathematics; recorded in his masterpiece The Elements.

Euclid’s five postulates;let the following be postulated:

  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 centre and distance.
  4. That right angles are congruent to one another.
  5. 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.

So what do these mean? (These postulates arefrompages 145 & 146 of[1]; where the authors provided a clearer version of Euclid’s postulates.):

  1. Through any two points, one straight line can be drawn.
  2. A straight line is infinite in extent.
  1. There are circles, and a circle is determined when we know its centre and radius.
  2. All right angles are congruent.
  3. (The parallel postulate) If two straight lines, l & m, are drawn so that they intersect a third in such a way that the sum of the inner angles on one side is greater than two right angles; then the two straight lines will never meet on this side. (This is an adjustment to the definition provided in [9], page 90.)

We shall illustrate the use of Euclid’s postulates by considering his proof of Proposition 47;Pythagoras’ Theorem.

Figure 1: A geometric construction of a right-angled triangle and the corresponding squares of each of the triangles' sides ([4], page 349).

In this proof, adapted from page 349 of [5], it will be necessary to refer to the relevant propositions, common notations and postulates outlined in Euclid’s elements. The proofs of the propositions used in the following proof are omitted.

Let ABC be a right-angled triangle with angle BAC right. We aim to show that the square on BC is equal to the sum of the squares on AB and AC.

Now describe the squares on the line BC as BCED, AB as ABFG and AC as ACKH[proposition 46, [5] page 347].Draw AL through A such that it is parallel to BD and CE; let AD and CF be joined[postulate 1]. The point A lies on AB; the lines AG and AC don’t lie on the same side and make the adjacent angles equal to two right angles. Then AG and AC are in the straight line CG [proposition 14, [5] page 276].Similarly, AB and AH are in the straight line BH.

Since the angles DBC and FBA are equal, each is a right angle, the angle DBA is equal to FBC by adding the angle ABC to each [common notion 2, [5] page 223].

Notice that BC equals BD, FB equals BA and AB, BD are equal to BF, BC respectively; thus angle ABD equals angle FBC, the line AD equals the line CF and the triangles ABD and FBC are equal [proposition 4, [5] page 247].

The parallelogram BDLP is twice the size of triangle ABD as their base is BD and they both lie in the parallels BD and AL [proposition 41, [5] page 338]. Similarly the square ABFG is twice the size of triangle FBC as their base is BF and they both lie in the parallels BF and CG. We can now logically deduce that the square ABFG and the parallelogram BDLP are equal; they are exactly twice the size of the equal triangles ABD and FBC respectively.

Now let AE and BK be joined. In the same way it can be proved that the parallelogram CELP is equal to the square ACKH. Therefore the whole square BCED is equal to the sum of the two squares ABFG and ACKH [common notion 2, [5] page 223].Therefore the square on BC is equal to the sum of the squares on AB and AC. QED.

It is clear that this proposition is proved using previous propositions that were first proved by Euclid and we know that this proposition was used by Euclid to prove more propositions. This is an example of how mathematics is built upon a set of foundations that expand and branch out into new areas. We can only build upon existing mathematics if we know it to be true beyond any shadow of a doubt. That means no assumptions and not accepting ‘this is obvious’ as sufficient reasoning. We must start with a set of axioms and make logical deductions from them to produce theorems and propositions; we can then use these theorems and propositions without having to re-prove them.

The question is: are Euclid’s postulates true? Euclid’s first four postulates are accepted as axioms: more specifically as geometric axioms. However Euclid’s fifth postulate, ‘the parallel postulate’, is only considered an axiom in Euclidean geometry. Perhaps Euclid’s postulates can’t be considered truths as they are not logically deduced from some other already accepted truths. Having said that we must start from somewhere and that is the purpose of axioms; they allow mathematics to be built upon assumptions that are the basics that cannot be proved. The problem with Euclid’s parallel postulate was that it was regarded as something which couldn’t be assumed and used as an axiom.

“To claim that this statement is self-evidently true is problematic; the problem lies in the word ‘never’ in the statement that the lines l and m never meet... There was enough doubt about this axiom for the mathematical community to spend some two thousand years attempting to show that it could be deduced from Euclid’s other axioms...Eventually, however, it was discovered that the axiom could not be deduced from the remaining Euclidean axioms.” ([6], page 96.)

The mathematical world was hesitant to accept Euclid’s parallel postulate as an axiom. There were two main directions mathematicians took to try and deal with this issue. Firstly, mathematicians tried to replace the parallel postulate with another axiom; one which didn’t rely upon other assumptions and could be accepted as true. Secondly, mathematicians tried to logically deduce the parallel postulate from Euclid’s first four postulates. Neither of these approaches worked despite centuries of effort. However, from these attempts a new field of mathematics was born: non-Euclidean geometry. This is a geometry based upon only the first four of Euclid’s postulates and therefore is a much more satisfactory ‘world’ for many mathematicians. Anything that was proved by Euclid without reliance upon the parallel postulate is obviously also true in non-Euclidean geometry; and these theorems are often referred to as ‘absolute theorems’ (this is discussed in more detail in [10]).

Peano Axioms

The Dark Ages, the Middle Ages and the Renaissance

With the demise of the Roman Empire and other ancient civilisations there was a loss in knowledge: both mathematical and otherwise. This period is known as the Dark Ages (roughly from the 5th century to the 10th century): an era in which little scientific advances were made and much of the foundations of both mathematics and other science were lost. The reason for the loss of knowledge was due to religious, cultural and political upheaval. For these reasons the Dark Ages are considered a time where mathematical proof stood still or in fact digressed (page 58, [13]). The period that followed was the Middle Ages (roughly from the 10th to 15th century) where similarly little progress was made.

Not until the Renaissance (around the end of the 15th Century) was there a reborn interest in science and philosophy; famously by the likes of Da Vinci and Michelangelo. During this time Italian mathematician Niccolò Fontana began to re-discover the works of Euclid and Archimedes whilst translating texts [24]. The nature of the Renaissance required more practical use for mathematics; therefore there were no considerable leaps in the fields of proof.

Giusepee Peano

Giusepee Peano (1858-1932) was an Italian Mathematician who is held in high regard, within both the mathematical and philosophical community, particularity due to his mathematical logic. Works for which Peano is recognised include:

  • Peano's existence theorem[25]– guarantees that solutions exist for specific initial value problems.
  • Formulario Mathematico[26] – a book that covers some fundamental theorems. The language in this book is a mathematical language using symbols developed by Peano himself.
  • Latino Sine Flexione [27] – an “auxiliary language” invented by Peano designed as a simplified version of Latin.

Up until the middle of the 19th Century there had not been any kind of formalisation in arithmetic. During the 1860s Hermann Grassmann showed that it was possible to produce facts in arithmetic based on very basic assumptions that relied on successor operators and induction. Later in 1881 Charles Sanders Pierce produced axioms based on natural number arithmetic. By 1888 Richard Dedekind proposed that a group of axioms should be produced to form foundations of the natural numbers. During the late 19th Century Peano produced a set of axioms which have come to be known as “Peano Axioms”. These axioms form a basis of specific number theory known as Peano arithmetic.Reduced down to a simplified form here are the axioms Peano produced [28]:

  1. 0 is a natural number.

Zero is the zero element of the set of natural numbers.

  1. For every natural number x:x=x. Equality is reflexive.

Every natural number is equal to itself.

  1. For all natural numbers x and y: if x=y, then y=x. Equality is symmetric.

That natural numbers are equal regardless of order.

  1. For all natural numbers x, y and z: if x=y andy=z, then x=z. Equality is transitive.

If two different natural numbers are equal to the same natural number then the two original natural numbers are also equal.

2, 3 & 4 show us that equality is an equivalence relation because it has the properties of reflexivity, symmetry and transitivity.

  1. For all a and b: if a=b and a is a natural number, then b is also a natural number. Natural numbers are closed under equality.

The group of natural numbers is closed under equality. This means that the natural numbers can only be equal to other natural numbers.

Now let the function S be defined as the ‘successor function’. This function takes a natural number and generates the next one: i.e. S(0) = 1, S(S(0)) = S(1) = 2, etc.