Imre Lakatos, Proofs and refutations:
The logic of mathematical discovery
Como objectivo geral, em cada aula deste curso teremos uma discussão relativamente curta sobre um texto proposto com antecedência. Na primeira parte do curso (provavelmente em todo o curso...) utilizaremos o livro Proofs and Refutations: The Logic of Mathematical Discovery, de Imre Lakatos (1922-1974). Neste livro, Lakatos discute a história longa das tentativas de demonstração da fórmula de Euler através da criação de uma aula imaginária em que um professor tenta fazer essa demonstração e encontra pela frente as objecções de uma turma particularmente atenta e activa... Enquanto no corpo do texto Lakatos recria essas tentativas com o diálogo entre o professor e os alunos, nas notas vai descrevendo a história real . A leitura das notas é portanto tão importante como a do próprio texto.
Os textos parciais com as respectivas notas irão sendo transcritos nesta página à medida que forem sendo propostos para discussão. Serão numerados Texto 1, Texto 2, etc. Poderão ter links para páginas da rede que possam auxiliar ou complementar a leitura do texto. Uma biografia de Lakatos encontra-se aqui. Pode consultar a tradução destes textos em português.
1. A Problem and a Conjecture
The dialogue takes place in an imaginary classroom. The class gets interested in a PROBLEM: is there a relation between the number of vertices V, the number of edges E and the number of faces F of polyhedra - particularly of regular polyhedra - analogous to the trivial relation between the number of vertices and edges of polygons, namely, that there are as many edges as vertices: V = E? This latter relation enables us to classify polygons according to the number of edges (or vertices): triangles, quadrangles, pentagons, etc. An analogous relation would help to classify polyhedra.
After much trial and error they notice that for all regular polyhedra V - E + F = 2.(1) Somebody guesses that this may apply for any polyhedron whatsoever. Others try to falsify this conjecture, try to test in many different ways - it holds good. The results corroborate the conjecture, and suggest that it could be proved. It is at this point after the stages problem and conjecture - that we enter the classroom.(2) The teacher is just going to offer a proof.
2. A Proof
TEACHER: In our last lesson we arrived at a conjecture concerning polyhedra, namely, that for all polyhedra V - E + F = 2, where V is the number of vertices, E the number of edges and F the number of faces. We tested it by various methods. But we havent yet proved it. Has anybody found a proof?
PUPIL SIGMA: I for one have to admit that I have not yet been able to devise a strict proof of this theorem ... As however the truth of it has been established in so many cases, there can be no doubt that it holds good for any solid. Thus the proposition seems to be satisfactorily demonstrated.(3) But if you have a proof, please do present it.
TEACHER: In fact I have one. It consists of the following thought-experiment. Step 1: Let us imagine the polyhedron to be hollow, with a surface made of thin rubber. If we cut out one of the faces, we can stretch the remaining surface flat on the blackboard, without tearing it. The faces and edges will be deformed, the edges may become curved, but V and E will not alter, so that if and only if V - E + F = 2 for the original polyhedron, V - E + F = 1 for this flat network remember that we have removed one face. (Fig. 1 shows the flat network for the case of a cube.) Step 2: Now we triangulate our map it does indeed look like a geographical map. We draw (possibly curvilinear) diagonals in those (possibly curvilinear) polygons which are not already (possibly curvilinear) triangles. By drawing each diagonal we increase both E and F by one, so that the total V-E+F will not be altered (fig. 2). Step 3: From the triangulated network we now remove the triangles one by one. To remove a triangle we either remove an edge - upon which one face and one edge disappear (fig. 3(a)), or we remove two edges and a vertex - upon which one face, two edges and one vertex disappear (fig. 3 (b)). Thus if V - E + F = I before a triangle is removed, it remains so after the triangle is removed. At the end of this procedure we get a single triangle. For this V - E + F = I holds true. Thus we have proved our conjecture.(4)
PUPIL DELTA: You should now call it a theorem. There is nothing conjectural about it any more.(5)
(1). First noticed by Euler [l758a]. His original problem was the classification of polyhedra, the difficulty of which was pointed out in the editorial summary: While in plane geometry polygons (figurae rectilineae) could be classified very easily according to the number of their sides, which of course is always equal to the number of their angles, in stereometry the classification of polyhedra (corpora hedris planis inclusa) represents a much more difficult problem, since the number of faces alone is insufficient for this purpose.
The key to Euler's result was just the invention of the concepts of vertex and edge: it was he who first pointed out that besides the number of faces the number of points and lines on the surface of the polyhedron determines its (topological) character. It is interesting that on the one hand he was eager to stress the novelty of his conceptual framework, and that he had to invent the term 'acies' (edge) instead of the old latus (side), since latus was a polygonal concept while he wanted a polyhedral one, on the other hand he still retained the term angulus solidus (solid angle) for his point-like vertices. It has been recently generally accepted that the priority of the result goes to Descartes. The ground for this claim is a manuscript of Descartes [c. 1639] copied by Leibniz in Paris from the original in 1675-6, and rediscovered and published by Foucher de Careil in 1860. The priority should not be granted to Descartes without a minor qualification. It is true that Descartes states that the number of plane angles equals 2F + 2V - 4 where by F he means the number of faces and by V the number of solid angles. It is also true that he states that there are twice as many plane angles as edges (latera). The conjunction of these two statements of course yields the Euler formula. But Descartes did not see the point of doing so, since he still thought in terms of angles (plane and solid) and faces, and did not like a conscious revolutionary change to the concepts of 0-dimensional vertices, 1-dimensional edges and 2-dimensional faces as a necessary and sufficient basis for the full topological characterisation of polyhedra.
(2). Euler tested the conjecture quite thoroughly for consequences. He checked it for prisms, pyramids and so on. He could have added that the proposition that there are only five regular bodies is also a consequence of the conjecture (demonstração). Another suspected consequence is the hitherto corroborated proposition that four colours are sufficient to colour a map.
The phase of conjecturing and testing in the case of V - E + F = 2 is discussed in Pólya ([I954], vol. 1, the first five sections of the third chapter, pp. 35-41). Pólya stopped here, and does not deal with the phase of proving though of course he points out the need for a heuristic of problems to prove (, p. I44). Our discussion starts where Pólya stops.
(3). Euler ([I758a], p. 119 and p. 124). But later ([1758b]) he proposed a proof.
(4). This proof-idea stems from Cauchy [18I3a].
(5). Deltas view that this proof has established the theorem beyond doubt was shared by many mathematicians in the nineteenth century, e.g. Crelle [1826-7], 2, pp. 668-7I, Matthiessen , p. 449, Jonquières [1890a] and [1890bl. To quote a characteristic passage: After Cauchys proof, it became absolutely indubitable that the elegant relation V + F = E + 2 applies to all sorts of polyhedra, just as Euler stated in 1752. In 1811 all indecision should have disappeared. Jonquières [1890a], pp. 111-12.
PUPIL ALPHA: I wonder. I see that this experiment can be performed for a cube or for a tetrahedron, but how am I to know that it can be performed for any polyhedron? For instance, are you sure, Sir, that any polyhedron, after having a face removed, can be stretched flat on the blackboard? I am dubious about your first step.
PUPIL BETA: Are you sure that in triangulating the map one will always get a new face for any new edge? I am dubious about your second step.
PUPIL GAMMA: Are you sure that there are only two alternatives - the disappearance of one edge or else of two edges and a vertex - when one drops the triangles one by one? Are you even sure that one is left with a single triangle at the end of this process? I am dubious about your third step.(1)
TEACHER: Of course I am not sure.
ALPHA: But then we are worse off than before! Instead of one conjecture we now have at least three! And this you call a 'proof'!
TEACHER: I admit that the traditional name 'proof' for this thought-experiment (2) may rightly be considered a bit misleading. I do not think that it establishes the truth of the conjecture.
DELTA: What does it do then? What do you think a mathematical proof proves?
TEACHER: This is a subtle question which we shall try to answer later. Till then I propose to retain the time-honoured technical term 'proof' for a thought-experiment - or 'quasi-experiment' - which suggests a decomposition of the original conjecture into subconjectures or lemmas, thus embedded it in a possibly quite distant body of knowledge. Our "proof ", for instance, has embedded the original conjecture - about crystals, or, say, solids - in the theory of rubber sheets. Descartes or Euler, the fathers of the original conjecture, certainly did not even dream of this.'
1. The class is a rather advanced one. To Cauchy, Poinsot, and to many other excellent mathematicians of the nineteenth century these questions did not occur.
2. Thought-experiment (deiknymi) was the most ancient pattern of mathematical proof. It prevailed in pre-Euclidean Greek mathematics (cf. A. Szabó [195 81).
That conjectures (or theorems) precede proofs in the heuristic order was a commonplace for ancient mathematicians. This followed from the heuristic precedence of 'analysis' over 'synthesis'. (For an excellent discussion see Robinson .) According to Proclos, '. . it is ... necessary to know beforehand what is sought' (Heath [I925], I, p. 129). 'They said that a theorem is that which is proposed with a view to the demonstration of the very thing proposed' - says Pappus (ibid I, P. 10). The Greeks did not think much of propositions which they happened to hit upon in the deductive direction without having previously guessed them. They called them porisms, corollaries, incidental results springing from the proof of a theorem or the solution of a problem, results not directly sought but appearing, as it were, by chance, without any additional labour, and constituting, as Proclus says, a sort of windfall (ermaion) or bonus (kerdos) (ibid. I, p. 278). We read in the editorial summary to Euler [1756-71 that arithmetical theorems 'were discovered long before their truth has been confirmed by rigid demonstrations'. Both the Editor and Euler use for this process of discovery the modern term 'induction' instead of the ancient 'analysis' (ibid.). T@e heuristic precedence of the result over the argument, of the theorem over the proof, has deep roots in mathematical folklore. Let us quote some variations on a familiar theme: Chrysippus is said to have written to Cleanthes: 'Just send me the theorems, then I shall find the proofs' (cf. Diogenes Laertius [C. 2,001, VIT. 179). Gauss is said to have complained: 'I have had my results for a long time; but I do not yet know how I am to arrive at them' (cf. Arber [19451, P. 47), and Riemann: 'If only I had the theorems! Then I should find the proofs easily enough.' (Cf. Hölder [I9241, P. 487.) Pólya stresses: 'You have to guess a mathematical theorem before you prove it' ([I9541, vOl. 1, P. Vi).
The term 'quasi-experiment' is from the above-mentioned editorial summary to Euler [I7531. According to the Editor: 'As we must refer the numbers to the pure intellect alone, we can hardly understand how observations and quasi-experiments can be of use in investigating the nature of the numbers. Yet, in fact, as I shall show here with very good reasons, the properties of the numbers known today have been mostly discovered by observation. . .' (P61ya's translation; in his [I9541, I, p. 3 he mistakenly attributes the quotation to Euler).