# Are mathematical proofs subject to the problem of induction?

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?

• Normally for homework like math problems and exercises your concern won’t happen since its foundations and deductive logic including mathematical induction is tight enough to avoid real confusion/concern. Only when you create your own math theory or system in the unstable phase, your own proposed proofs might get confused. One deeper philosophical could be the Kripekenstein rule following paradox… Commented May 21, 2022 at 1:56
• @Galen Which problem of induction? Do you mean Hume's problem of induction? Commented May 21, 2022 at 3:40
• The problem of induction is the problem of inferring universal laws from specific instances. That isn't the issue that you are dealing with here. I'm not sure what to call what you are discussing except an extreme form of Cartesian skepticism. You are worried about the general problem of the universal possibility of error. There is a sense in which every single belief you have is subject to revision. It is an issue that I've sometimes thought about, but never seen addressed in the literature. Commented May 21, 2022 at 5:20

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.

• +1 for suggesting these different aspects, some I will need to look up to understand the references. On (a) I can try to clarify right away that the proof may have an actual correctness regardless of what I believe, but I don't know how to decide if a proof is correct except by means of checking it (which is an experience). Commented May 20, 2022 at 23:49
• @galen it is arguable that you accept scientific truth on the basis of testimony from other scientists. why not do the same with mathematical truth- surely you do not verify every scientific experiment with your own eyes? Commented May 20, 2022 at 23:52
• You're right, I overstated the uniqueness of the conditions of belief. In that second-hand case it is necessary for me to trust that the experience of others is reliable, and that my experience of others relaying information to me is reliable. Commented May 20, 2022 at 23:53
• What I would say about others' checking a proof vs myself checking a proof is more-or-less exchangeable mutatis mutandis. Maybe they will someday think "hang on, the proof actually doesn't work" just as I might. Commented May 20, 2022 at 23:59

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.

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.

• Aside from potentially barring most historical proofs, I'm not sure this addresses the core concern: how can one be sure after reviewing <formal proof> that they haven't missed something? Or that there's not a subtle bug in the automated system you used to check it? Ultimately I think one cannot -- but the chances get quite low as steps are made smaller and more people/systems review it. Commented May 21, 2022 at 17:04
• @ctwardy: Regarding historical proofs, I already said "they are useful for people to communicate ideas and intuition". The formal rigorous proofs are really important, otherwise you get things like fake proofs that are accepted by other mathematicians for a decade. In absence of formal proofs, all you have are intuitive recipes that typically can be translated by a logician into a rigorous proof. I'll just say that I'll be convinced of the overall correctness of any theorem (relative to the chosen foundations) that professional logicians have reviewed and are fully confident of them. Commented May 21, 2022 at 17:21
• @ctwardy Regarding subtle slips in checking a formal proof, and subtle bugs in the execution of a proof verifier program on a computer, you are correct that we can never be absolutely sure they do not exist. However, that was not the point of my post. It was very clear that the asker did not even realize there is such a thing as formal proofs, so they (wrongly) thought there was a possibility that it relies on their intuitive grasp of whether each part of the proof 'works' or not. If you don't believe me, feel free to ask the asker whether they know what an FOL theory is! Commented May 21, 2022 at 17:24
• This answer ignores the core substance of my question, which is accurately inferred in @ctwardy's comment, and it also makes unnecessary accusations about my knowledge at the time of asking that are false. I had thought that an example like that which can be found in Principia Mathematica or similar wasn't necessary to get the point across. Rather, as this poster suggests themselves, historical proofs "are useful for people to communicate ideas and intuition". The example of Euclid's proof was a prompt to get people thinking about problems of proof, and this poster didn't find that useful. Commented Feb 15, 2023 at 20:13

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.

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.

• Yes in some roundabout way the laws of physics may be responsible for us knowing set theory, but no known physical system requires set theory. It’s not empirical induction unless its mathematicians keeping studying set theory because it’s interesting or potentially scientifically applicable. And that’s the data. But that is far from knowing the scientific reason for set theory. Too far to it may be hard to justify that is how mathematical knowledge comes about Commented May 23, 2022 at 14:32
• It's not empirical induction because induction is impossible. Commented May 23, 2022 at 14:34
• If induction is impossible, how do we have the knowledge math comes from physical instantiations? Commented May 23, 2022 at 14:36
• Guessing controlled by criticism, as explained in the stuff I referred to in the answer. Commented May 23, 2022 at 14:41
• Then everyone should be a physicalist in regards to math, but they aren’t. Most are platonist and some are fictionalsits. I can use a pen and paper to write down fairy tales. Does that mean fairy tales are physical? Only in a trivial sense. Commented May 24, 2022 at 12:19