Are mathematical proofs subject to the problem of induction?

Question

When I consider a proof, such as Euclid's proof of the infinitude of primes, it can give a sense that something necessarily true has been obtained.

I cannot remember where I got the idea, but a few years ago I encountered a notion that dispelled this feeling. It is not a complicated notion. All I considered was the possibility that my conclusion that the proof is correct was contingent on my experience of going through the proof. If I misperceived the proof, I could be wrong. If I misunderstood the proof, I could be wrong. If I misremembered a previous step of the proof, I could be wrong. It occurred to me that I had to have a basic trust in the accuracy of my experience to actually get through the proof and believe it.

I could go through Euclid's proof once, or a thousand times, and not be absolutely sure that I had not in some way gotten to the incorrect conclusion. If I look at my own reasoning as depending on, or being a type of, experience, then I don't see how I can be certain that what I believe from reasoning is necessarily correct. I'm quite satisfied with Euclid's proof, but I can't seem to rule out that in future I won't look at it differently and go "hang on, the proof actually doesn't work".

This is my subjective sense of things anyway. From the point of view of the many better-learned members of this community, are mathematical proofs subject to the problem of induction?

Answer 1

Here are some thoughts:

(a): "your conclusion that the proof is correct is contingent on your experience of the proof"- perhaps, but the proofs actual correctness is not, unless you believe your conclusion that the proof is correct and its actual correctness to be the same. but this is a very strong condition on the grounding of mathematical truth.

(b): perhaps you are interesting in exploring notions of certainty. there is psychological certainity, epistemic certainity, etc. One can have epistemic certainity- knowledge- even without psyschological certainity- or at least this is the conclusion of any reliablist.

(c) more generally, if one explains mathematical truth via some holist epistemology, say perhaps Quine- then mathematical proof may indeed be subject to problems of induction. Of course, holist epistemologies have their own issues.

(d): for mathematicians: note that the problem of induction has little to do with, say, the principle of induction for natural numbers (or any other mathematical structure) - that principle is typically formulated in a manner completely consistent with its use in a deductive logic.

Answer 2

There is a principle in engineering that is often referred to as "managing complexity." This is the idea that, for any given analysis (designing an aircraft, working out a chemical process, working out how much storage space is required at a container port, etc.) one of the main goals is to manage the complexity of the problem. This is so that the analyst can understand the solution and be confident of it. And so that the result can be presented to a client or a government regulator in a way that is transparently convincing.

This is usually accomplished using, among many methods, breaking down the analysis into small components with simple relationships. Then building up the full analysis using compound objects and ideas that, though compound, have simple relationships. For a straightforward example: A single container requires a certain amount of space in the storage area. So 1000 similar containers require more space, but not simply 1000 times as much. You need to know the means of stacking, the maximum height, the size of the alleyways between, and other stuff. Once you build the ability to make stacks, then the ability to store multiple stacks should be a comparatively simple relationship. (Nearly but not precisely linear.)

So the idea is, at each step and at each level of abstraction, you build the analysis in a way that the concepts, relationships, and behviors, are all simple enough that you can "hold them in your head."

So also with proofs of math theorems. The idea is to build the proof using layers of abstraction. At each level, the concepts and relationships are kept such that you can "do it in your head." This is done, among other methods, by using symbols to carry around collections of information. An example of such a symbol might be "triangle" or "point" or "line segment." Or, for theorems about primes "prime number" or "prime factor." These symbols allow you to concentrate on specific details, putting the other details into the background. You concentrate on the properties required for purposes of the proof, avoiding being innundated with detail of all of the other properies of a number.

The result is, you build up the proof step-by-step, and layer-of-abstraction by layer-of-abstraction. At each point in the proof, the information and concepts you need to hold "in your head" is relatively small and so, hopefully, achievable. Thus, the parts of the theorem you need to verify are relatively small and relatively easy to verify. This-tiny-part and that-tiny-part have this-simple-relationship. And so you can treat the two of them as yet-another-simple-part.

The goal is, you never have to hold the entire proof in your head at one time, only small digestible bits. So, you don't need to be comprehend the proof-as-a-whole but only each tiny step and the (hopefully very local) implications of that step.

If such a built-from-simple-parts type approach is possible, then to doubt the proof amounts to doubting your own ability to think clearly at a nearly-trivial level. And, if you are having those type of problems, then you are having them before you get to Euclid's proofs.

This is, of course, very different from the original creation of the proof in the first place. That often requires some unuaully clever thinking that leaps around to multiple abstraction levels and uncovers relationships not previously well understood.

Answer 3

≫ I'm quite satisfied with Euclid's proof, but I can't seem to rule out that in future I won't look at it differently and go "hang on, the proof actually doesn't work".

This reveals that what you are referring to is actually NOT what a true mathematical proof is. The kind of 'proof' that you read in most mathematical writings is technically not the true kind of proof that underlies the theorems. For you to understand that you first have to learn how to actually use a complete formal foundational system (e.g. this Fitch-style system) for mathematics, and then see that for every possible formal foundational system there must be a proof verifier program V, which means that for every strings p,x, when V is run on input (p,x) it will halt and output either "valid" or "invalid" that answers whether p is a valid proof of x or not.

All other kinds of 'proofs' you read are mere shadows of the true proofs; they are useful for people to communicate ideas and intuition, but if you want absolute mathematical rigour then you have to go to the formal proofs over a formal foundation system.

Note that the mere existence of a formal foundational system for all modern mathematics implies that the question of whether there is a mathematical proof of a sentence Q or not is a question that does not rely on your subjective experiences at all! Anyone could follow exactly the same objective procedure of running V on a true proof p of x and will come to exactly the same conclusion, namely that p is a valid proof of x. If they are lazy or the proof is too long, they can use a computer. There are production-scale formal proof assistants such as Mizar that support precisely such endeavours, but you should understand the linked system first before looking at Mizar, as Mizar is ≈ 10 times as complex as mine.

Answer 4

Without being a specialist on this topic, I would say that the concerns you are raising are aligned with intuitionism. Of particular interest for your question is the development of intuitionsitic logic

The intuitionistic approach pushes logic towards a "constructive" attitude, in which the development of mathematics is a mental activity, and proofs of theorems (say the existence of a given natural number) imply having the capacity of constructing one mathematical object (smaller numbers) after the other until an object (the said number) appears. Some inference rules are explicitly excluded, in particular the law of the excluded middle and double negation elimination. This has deep consequences because some of the theorems accepted in classical logics are rejected under the intuitionistic approach. In this introductory paper, the development of intuitionistic logic has been considered one of the three major crisis in mathematics [1], and highlights:

In fact, the intuitionistic attitude toward logic is precisely the opposite from the logicists' attitude: According to the intuitionists, whatever valid logical processes there are, they are all constructs; hence, the valid part of classical logic is part of mathematics! Any law of classical logic which is not composed of constructs is for the intuitionist a meaningless combination of words. It was, of course, shocking that the classical law of the excluded middle turned out to be such a meaningless combination of words. This implies that this law cannot be used indiscriminately in intuitionistic mathematics; it can often be used, but not always.

So regarding the specific problem you are asking I would say that indeed, to have a basic trust in the accuracy of my experience you need to construct the objects needed to prove the theorem. For example, I did a quick search looking for some paper talking about Euclides geometry under an intuitionsitic approach and I've found this one [2]. An article I particularly like connecting very explicitly philosophy and logic can be found here [3].

Hope it helps.

[1] Snapper, E. (1979). The three crises in mathematics: Logicism, intuitionism and formalism. Mathematics Magazine, 52(4), 207-216.

[2] Kellison, A., Bickford, M., & Constable, R. (2019). Implementing Euclid’s straightedge and compass constructions in type theory. Annals of Mathematics and Artificial Intelligence, 85(2), 175-192.

[3] Boniolo, G., & Valentini, S. (2012). Objects: A study in Kantian formal epistemology. Notre Dame Journal of Formal Logic, 53(4), 457-478.

Answer 5

Induction in the philosophy of science is supposed to be a process that somehow leads from observations to theories and then allows scientists to increase the degree to which those theories are justified. There is a common idea that mathematical knowledge doesn't come from observations and so can be more certain than inductive scientific knowledge.

There are many problems with this way of looking at the situation. One problem is that nobody has come up with a way of doing induction that survives even the most cursory attempt at criticism, as pointed out by Karl Popper. No scientific theory is entailed by or equivalent to any finite set of observations. Such a theory is an account of how part of the world works, not just a digest of observations. In addition, all observations are theory laden because we have to theorise about how measuring instruments work and about the interpretation of the observations. There are many other problems with inductivism, see for example "Objective Knowledge" by Popper, Chapter 1.

There is a related and more general problem. All arguments make assumptions and use rules to get from those assumptions to conclusions. There is a common idea called justificationism that arguments somehow make their conclusions more certain. But there is no way of guaranteeing the truth of the assumptions or the rules, or showing they are probably true or anything like that. If they have passed all the tests or criticisms they have been subjected to the next test or criticism might still refute them so justificationism is a non-starter, see "Realism and the aim of science" by Popper, Chapter I. Popper claims that all knowledge consists of guesses controlled by criticism, and there are no unanswered criticisms of that idea.

How does maths fit into this? Many people seem to think maths is more certain than scientific knowledge, but it is still subject to the criticisms of justificationism, so it also consists of guesses controlled by criticism. One issue is that all mathematical knowledge is created using physical systems, such as pieces of paper, pencils, computers and human brains. So all mathematical knowledge is dependent on our knowledge of how the laws of physics instantiate the mathematical operations we are referring to, see "The Fabric of Reality" by David Deutsch, Chapter 10 for a discussion of this issue.