Having mostly talked about mathematics, now is grand time to get going on our very first "proper" trail. Those who complete it will be able to not be impressed any more by sightings of abstract formalism, for we will introduce both the vocabulary and the grammar of mathematical language, and will therefore become apprentice mathematicians. Such a trail will also showcase how the mathematical cosmos is not a crystal world, as many would like to believe, made of eternal unchanging constructs, but a universe full of life and spirits.
Introduce then the base of the world, the equivalent of the Turtle which in Indian, Chinese and native American mythology bears the weight of the Earth: the concept of a set. Think of this as a pre-hike check about fundamentals. If you are already familiar with this feel free to jump right ahead and have a look at some of the life forms inhabiting this world.
Ground
A set is a collection of objects, called the elements of the set. Mathematicians usually represent it with a capital letter, enclosing the elements of the set between curly parentheses:
A = {1, 3, 7}
B = {green, 2, rabbit, 1}
C = {1, {3, 7}}
D = {3, 7, 1}
Here we have four sets, A and D have three elements, B has four and C has two: 1 and the set {3,7}. To say whether an element belongs or not to a certain set we use the symbols ∈ and ∉, so for example 1 ∈ A but 2 ∉ A, 3 ∈ A but 3 ∉ C,
{3, 7} ∉ D but {3, 7} ∈ C. Similarly we can talk about subsets of a given set, using the symbols ⊆ and ⊈. These are sets contained in bigger sets, so for example {1, 3} ⊆ A, {green} ⊆ B, {3, 7} ⊆ A but {3, 7} ⊈ C, rather {{3, 7}} ⊆ C. Conventionally, in addition to the "intuitive subsets" of a set, mathematicians add as subsets of any set the empty set Ø, which is the set with no elements, and the set itself: so that a complete list of the subsets of A is:
Ø, {1}, {3}, {7}, {1, 3}, {1, 7}, {3, 7}, A
The set containing these as elements is called the Power set of A.
Finally a set is completely specified by its elements, so in our example A and D are actually the same exact set, the order is not important.
Let us take a breather. This path has a steep initial incline, but it will be worth the efforts. In particular after the next stretch we will be done with the minimum instruments needed to advance.
All the sets above are rather small, but often we want to consider very large sets. If we wanted to consider the set of all the people in the UK it would be very impractical to list every single one of them, rather such a set is designated exactly by the way we talk about it: "the set of all the people in the UK".
Let us go for a more numerical example. Say we wish to consider the set of even numbers, an infinitely large set. Mathematicians would write it in such a way:
E = {2⋅n | n ∈ ℕ}
Here the vertical bar means "such that" or "for", and ℕ is the first of the numerical sets we will encounter on our journey: the set of natural numbers: these are the nonnegative whole numbers we use for counting and listing: 0, 1, 2, ... up to infinity. So the above reads as an implicit list: all the elements "2 times n" for natural numbers n. The multiples of 4 would then constitute a subset of this set for example.
The other important numerical sets are:
ℤ: this is the set of integers, positive and negative.
ℚ: This is the set of numbers that can be written as fractions of integers, 0.5 and 0.66666... are examples of elements of this set (respectively ½ and ⅔). Let us recall that multiplication and addition of rational numbers give again rational numbers:
whereas multiplication is straightforward, addition behaves as we expect to only when denominators are equal , e.g.: ½ + ⅔ = ³⁄₆ + ⁴⁄₆ = ³⁺⁴⁄₆ = ⁷⁄₆ = 1.16666...
ℝ: This is the set of all the numbers on the number line, from square roots of whole numbers to numbers like π. It forms a continuum.
There is a neat order to these sets:
ℕ ⊆ ℤ ⊆ ℚ ⊆ ℝ.
Of course this is not all there is, you may have heard of complex numbers, but there exist quaternions as well, and the list goes on, the ones on the left though will be sufficient for the time being.
This concludes the set theory fundamentals, now let us make chemistry with all these things. Introduce the concept of a proof.
Flora
What is a proof? Is it mere verification? We could start talking about it but often in nature, be it abstract or concrete, one should show, not tell.
Take a statement like "the square of every odd number is odd". Sure, we could start by listing: the square of 1 is 1, which is odd, the square of 3 is 9, which is odd, 5 is 25, 7 is 49, 9 is 81, 11 is 121, etc etc.
One could then ask what proving such a statement would bring us. Too often there are people, often beginning mathematicians, claiming that it is about rigour and never being "absolutely certain". This is, as we will see in a second, not nearly the whole story.
So here we are, discovering some of the flora of this world.
Let us see then a first kind of proof, so-called direct proof. This is a proof that starts from the premises and reaches the conclusion; the most natural but also most shapeshifting kind of proof.
An odd number can be written as 2n + 1 for some natural number n. Its square would then be (using the fact that multiplication is distributive):
(2n + 1)(2n + 1) = 4n² + 2n + 2n + 1 = 4n² + 4n + 1 = 4(n² + n) + 1
four times any number is an even number, hence we indeed obtain that this number is odd, but this is not all. Indeed, four times any number is, quite naturally, a multiple of 4; so we have proved that the square of an odd number is always one more than a multiple of four, more than what we bargained for!
This constitutes a first glimpse into the uses of proof-making: Proofs serve to discover new things! We shall come back to this facet later on. For now we will tour to see another couple species of proofs.
The second one we come across is the so-called proof by contradiction. Here to prove a statement we start by assuming it is false, if that leads to an absurdity then the initial statement must be true. We will see one of the most famous proofs in all of mathematics, one which every undergraduate student learns and one which was discovered as far back as the time of the Greeks.
This concerns the non-rationality of the square root of 2: the length of the diagonal of a square with side length equal to 1. The Pythagoreans believed that all numbers were ratios of natural numbers, hence the discovery of such a fact was in all effects a heresy, for which the discoverer was exiled.
The proof goes like this.
Suppose √2 is a rational number, then √2 = ⁿ⁄ₘ for some integer numbers n, m. In particular the fraction should be in minimal form, so that if the numerator and denominator had common factors we divided both until n and m, with no common divisors, remain (if it was ⁶⁄₈, the minimal form would be ¾ for example).
Hence for these numbers, squaring both sides of the equation and multiplying by m² both sides again we obtain that n² = 2m²; entailing that n² is an even number. Stop and check for a second that this is clear.
Now, we know from before that the square of an odd number is odd, so n cannot be odd, it must be even. Hence, it can be written as n = 2k for some integer number k, from which follows that n² = 4k². n² is equal both to 4k² and to 2m², hence we must have that 4k² = 2m². Dividing by 2, we obtain that m² = 2k², so m² is even. From the same reasoning above m must be even. But if n and m are both even their ratio was not in minimal form, contradiction.
In this case the proof seems to fit more the verification stereotype, but again we should be mindful of our assumptions, and take history somewhat seriously. Indeed, the rationals are dense in the reals, meaning that between any two rational numbers there exists a rational number (for example their average, which is again rational, as you might try to show), so one might expect all the reals to be rational, as the Pythagoreans believed. Instead, the mythical exile of the man points to the fact that knowledge of irrational numbers was not a given in ancient times; we are hence gazing at an instance of discovery.
Let us continue with a rather different third kind: the so-called disproof by counterexample. This is used when we wish to prove not that a statement is true, but that it is false. Take for example the statement:
"In any polygon the line joining any two points will lie inside the polygon"
I start by giving you several examples:
And maybe even start to get on proving such a statement.
But if then you come along and show me this:
Then I just know that the statement, as it is above, is false. This could lead me to give a name to polygons for which such a statement is true. This way, the statement will just become a definition, which will find its worth in whether it is a useful one or not. Later we will see how this business of deciding on definitions is all but trivial.
Introduce now the fourth, and for the time being last, species of proof: proof by induction.
Take the statement: "the sum of the first n odd numbers is equal to n² "
It is always good practice to check a few examples, to try and build an intuition for the problem, though one should be mindful, as shown above, that unintuitive counterexamples might be just around the corner.
1 = 1 1 + 3 = 4 1 + 3 + 5 = 9 1 + 3 + 5 + 7 = 16 1 + 3 + 5 + 7 + 9 = 25
Looks promising. The idea of induction is to have the statement depend on n so that we call the statement above P(n) and something like P(2) becomes the statement "the sum of the first two odd numbers is equal to 4" and P(5) that "the sum of the first five odd numbers is equal to 25". We then verify that it is true for the base case P(1), and we verify that if P(n) is true, then so is P(n+1). Checking these two boxes induces a "rippling effect" entailing that it is generally true.
We have checked above that the case P(1) is true, so let us deal with the second part: Assume P(n) is true so: 1 + 3 + .... + (2n - 1) = n² [Note that the nth odd number is indeed (2n-1)]
Then adding the next odd number we get:
1 + 3 + .... + (2n - 1) + (2n + 1) = n² + 2n + 1
The right hand side of the equation can be written as:
n² + n + n + 1 = (n + 1)(n + 1) = (n + 1)²
So that indeed P(n + 1) is true. Hence the statement is true for all n.
This time the charge of mere verification cannot be beaten, hence we shall make up for it with the best part of our voyage; a rather spectacular example of a proof by induction: the proof of the Euler conjecture. This will also show how and when a proof can be considered alive, and when it can be considered as having passed on to the other side.
AN OLD TREE
For a polygon it is quite evident that the number of vertices equals the number of edges, one only has to go back a little bit to see that the figures we considered before trivially satisfy such a condition. What about a polyhedron, i.e., a solid? Here there is another datum which feels relevant: faces. Is there a rule relating vertices (V) , edges (E) and faces (F)? In 1758 Euler, one of the most prolific mathematicians in history, considered a few examples like:
And probably a few more. He conjectured (such is the word when one is unsure about a statement but feels optimistic about it) that:
"All polyhedra satisfy V - E + F = 2"
Along came other mathematicians who attempted to prove it, we will follow an example very close to the historical proof given by Cauchy.
Take a solid and imagine one of the faces being transparent, what would we see?
For the prism, we would see this:
While for the cube/parallelepiped we would see this:
In both cases we have reduced the problem to a question about connected (meaning one can get from any place to any place) plane graphs. Now this effectively meant we removed a face, so if we can prove that for any connected plane graph v - e + f = 1 we will have proven Euler's conjecture.
Now let us prove this fact by induction, namely let P(n) be the statement:
"any connected plane graph with n edges satisfies v - e + f = 1"
This is a statement about quite a few plane graphs. while for both P(1) and P(2) there is only one such graph:
For P(3) there are three.
And the numbers keep going up. Now to prove this statement by induction we have to show that P(1) is true and that if P(n) is true, then so is P(n+1).
Looking at the examples above we indeed see that they're all true, P(1) included. What about the second (generally harder) part of the induction proof method?
Assume P(n) is true, and consider a connected plane graph with n + 1 edges. Say G has v vertices and f faces. We want to prove that G satisfies the formula.
v - (n + 1) + f = 1
Our idea consists in removing a carefully chosen edge from this graph, so as to leave a graph with n edges and use P(n). First though we have to prove a lemma. This refers to a "sub-theorem" needed in order to prove the main theorem. In this case the lemma is:
If a connected plane graph has no faces then it has an "end-vertex", meaning a vertex connected to only another vertex - see four of the five cases above. Expand for proof.
Proof: We reason by contradiction, for imagine that there is no face and that each vertex is connected to at least two other vertices. Then starting from one of these, we could trace a path, that goes to one of its neighbours. Once here we can continue without going back on our path since this vertex is connected to at least one other vertex, and so we continue without ever going back. From this moment on, the second the path passes by a vertex it had already visited we have a loop, which must necessarily enclose a face. Since there is a finite number of vertices the path will indeed loop on itself sooner or later, hence there must be at least a face, contradiction.
Consider G again, if G has a face then removing an edge from the face removes an edge and a face, not changing the supposed relation between vertices, edges and faces. Hence we will obtain an n-edged graph with v vertices, n edges and
f - 1 faces and by the (provisional) truth of P(n) it must be true that
v - n + (f - 1) = 1
So that the same must be true for G. If G has no faces then by our lemma we know it must have an end-vertex. Removing this vertex we remove an edge and a vertex, again leaving the relation between vertices, edges and faces unchanged. Here again P(n) will ensure that the same must be true for G. Hence P(n + 1) is true and all connected plane graphs have v - e + f = 1, entailing that V - E + F = 2 for any polyhedron.
Very neat, looks like we are done, and so Cauchy thought as well. But alas, in the following years chaos unfolded, starting what was to become a century long debate about the nature of polyhedra. Indeed, start by considering the solid obtained from removing a little cube from inside a bigger cube:
For this object V - E + F = 4. Is Euler's conjecture false then? Well what many people thought is that this does not constitute a fair counterexample, as it does not fit our intuitive idea of a polyhedron. Indeed, we never took care of defining just what a polyhedron is!
This would constitute a counterexample if, together with Euler himself, we were to define a polyhedron as:
DEF 1: A polyhedron is a solid delimited by polygonal faces.
But there are valid reasons to reject this definition, as a polyhedron is first and foremost a surface. With this in mind an alternative definition of a polyhedron suggested itself:
DEF 2: A polyhedron is a surface delimited by a system of polygons.
Above we see two surfaces, the outer and inner one, formed by two systems of polygons which, themselves, do satisfy Euler's conjecture. Now it looks like we're safe, if it wasn't for constructions with a single edge shared by more than two faces, like these:
For which V - E + F = 3 . The thing is, this also looks like it should not be a polyhedron. Hence a new definition was proposed.
DEF 3: A polyhedron is a surface delimited by a system of polygons such that for each edge two and only two of them meet.
I believe you can see what is coming up at this point, surprise:
For which V - E + F = 3 again
So one could come up with a new definition:
DEF 4: A polyhedron is a surface delimited by a system of polygons such that for each edge two and only two of them meet, and such that it is possible to pass from any one point to another crossing edges only and not vertices.
But one can just modify the above in ways such as:
for which again V - E + F = 3. As you probably started to get the feeling, this game of definitions and counterexamples could go on and on, ever more complicated definitions giving way to ever more elaborate counterexamples, ending by producing monstrosities like the definition of an "ordinary polyhedron" in the 1962 edition of the Encyclopedia Britannica, counting 45 lines of text.
There is a slim chance that such a definition indeed individuates a class of objects for which Euler's conjecture is true, but would such a definition really be that superior to saying that that a polyhedron is a surface delimited by a system of polygons and such that V - E + F = 2?
Before continuing let us look at one last couple of counterexamples: the picture-frame and the tower.
Both of these satisfy all the definitions above, but for the picture frame V - E + F = 0 and for the tower V- E + F = 3.
Here we might note that the peculiarities are the hole for the picture-frame and the face with a gap in the middle for the tower (the top of the bigger cube).
Guided by our intuition we might try and give definitions of a polyhedron without holes (call it a simple polyhedron) and with faces with no gaps (call it with simply connected faces). However, this might bring on a new slew of counterexamples, repeating the same mistakes.
Our error lies in forgetting what was arguably our point of departure: the proof! Indeed for all the counterexamples given here there must be a point where the proof breaks down for them. For the picture-frame and all the counterexamples before it it is not true that removing a face they can be deformed as to lie on the plane, while for the tower this can be done but the resulting graph is not connected! It looks instead like:
What does this mean? Technically that the proof was not correct. It contained a hidden assumption which was brought to light by adequate counterexamples. Despite this, the proof itself points to a constructive definition of a simple polyhedron, and of a polyhedron with simply connected faces.
DEF: a polyhedron is simple if, having removed a face, it can be deformed on the plane.
DEF: a face is simply connected if, having been deformed on the plane, it forms a connected graph.
[It should be noted that nowadays these concepts have "grown" and the standard definition of, for example, simple-connectedness transcends its use on solely faces.]
Hence, we finally arrive at a correct statement of Euler's conjecture:
"All simple polyhedra with simply connected faces satisfy
V - E + F = 2"
In this process it is the proof that helped us build the most appropriate concepts, but this is not all. Indeed, looking again at the proof, we can realise that the rigidity associated with polyhedra is not a requirement for the validity of the proof. i.e., instead of talking about simple polyhedra we could say that any polyhedron that can be continuously deformed into a sphere, with simply connected faces and even curvilinear edges, satisfies Euler's conjecture.
With a bit more effort one can also understand what happens for non-simple polyhedra (or surfaces not deformable into a sphere) like the picture-frame above.
If we were to glue two picture frames along the side, we would obtain two objects satisfying V - E + F = 0, hence together again satisfying V - E + F = 0 (think 0 + 0). However, we would be counting the 2 faces that have been glued, which now are inside the polyhedron, and hence are not faces any more. It follows that for the double picture frame: V - E + F = -2. Adding yet another one we would obtain that together they still satisfy V - E + F = -2 (-2 + 0), but we would have to again remove the two faces disappearing because of the gluing, obtaining V - E + F = -4.
Here one might feel a whiff of a proof by induction, but without being more explicit let us just say that more generally:
"if a surface has g holes (we say that the surface has genus g) then for any subdivision of it into polygonal faces V - E + F = 2 - 2g"
If Euler's conjecture initially looked like nothing more than a simple curiosity its proof unearthed a connection between the topology of a surface (those characteristics that do not vary when continuously deforming the surface, like the presence of holes) and the relation that any subdivision of it into polygons must satisfy. This constituted the beginning of one of the richest and most fascinating fields in mathematics today: algebraic topology.
To recap, not only we managed to get a glimpse into possibly the hardest topic an undergraduate student may encounter in his bachelor (if they do encounter it at all), we have also arrived at a point where we can understand just what was meant by the life of a proof.
A proof is alive when it is incomplete, when it is imperfect, when it is formally incorrect. It is in that state that a proof drives mathematical knowledge forward, helping in the creation of concepts and in the advance of understanding. Even set theory itself, our supposed "ground", arose because of the need for such grounding that early XXth century mathematics felt, when paradoxes and contradictions started popping up.
The fact that a proof has most value when not flawless is something that is often ignored in both schools and universities, where we are presented with the polished end-product and be made to believe that mathematics is all about formality and deductions, instead of intuition and trial-and-error.
Once a proof has exhausted its potential it passes away, living on as a spirit which can be brought back by (hopefully) capable mediums to serve once again in the advance of understanding of apprentice mathematicians. Hence, in every mathematics class students and adventurers are the cause of the continuous rebirth of the endemic flora, while professional mathematicians themselves are those who mingle with life itself, setting up camp in a part of the world even spirits have not yet reached.
Such an elucidation of the meaning of proofs was proposed under the form of an entertaining imaginary dialogue by the philosopher of mathematics Imre Lakatos, following the precise history of the Euler's conjecture. Equally, every definition that one sees in the learning of mathematics finds its motives in the history of the attempts to understand how each part of this abstract world relates to one another. Mathematics should never be about mere computation and verification, it is instead driven by childlike curiosity about patterns, and the secrets concealed in them.
Hence, no science deserves more the name of a human science than mathematics, and when deciding to chart a path through the abstract, the concreteness of practice, of what it means to be and to work as a mathematician, seems like the aptest starting point.
We hope that this trail was worthwhile, and that the creation of concepts through the posing of a question, together with the related process of discovery, is something that can be generalised to the arts and to any other discipline of the human spirit.
As announced before, each trail will be an offspring of the previous ones, birthing a web hard to predict in advance, spreading like a rhizome.
References:
"Proofs and Refutations", by Imre Lakatos, and its summary by Prof. Abbondandolo
"A Concise Introduction to Pure Mathematics" by Prof. Liebeck
Painting is "Children playing besides a stream" by impressionist Dorothea Sharp
Comments