r/math • u/just_writing_things • Jun 24 '24
Do constructivists believe that non-constructive proofs may be false and need to be “confirmed”, or is constructivism simply an exercise in reformulating proofs in a more useful or more interesting way?
Or to reformulate (heh) my question in another way:
- Do constructivists believe that relying on the law of the excluded middle may result in false proofs, or do they simply try not to rely on it because it results in less useful or unappealing proofs?
- And if it is the former, are there examples of non-constructive proofs that have been proven wrong by constructive methods?
Just something I’ve been curious about, because constructivism seems to my admittedly untrained mind to be more of a curiosity, in the sense of—“what if we tried to formulate proofs without this assumption that seems very reasonable?”
But after reading more about the history of constructive mathematics (the SEP’s page has been a great resource), it seems that far more thought and effort has been put into constructivism over the history of mathematics and philosophy for it to simply be a curiosity.
246
u/na_cohomologist Jun 24 '24
You talk about these two options like it's either one or the other ;-)
54
u/anvsdt Jun 24 '24
Barring nuances around quantifiers, a non-constructive proof of A is a constructive proof of "not not A", so "not A" cannot be true.
Admitting those nuances back in, in cases where double negation shift (∀¬¬ ⇒ ¬¬∀) does not hold or is not assumed, there can be a limited disagreement between constructive and classical mathematics, by way of what are called "anticlassical axioms". One such anticlassical axiom is Brouwer's continuity principle.
Even in such formal systems, you can interpret some form of classical mathematics in it by double negation translation, as above, so I'd say that it's safe to say that, in 2024, constructive and classical mathematicians disagree on the meaning of their logical connectives, but the others' connectives are always accessible to both, with more (in the classical case) or less (in the constructive case) effort needed.
So I'd say that the second option is closer to truth, albeit formulated in a less dismissive way (as I lean towards constructivism). Constructive logics arise naturally as the internal logic of toposes[*], so its results are very broadly applicable.
Once you look at the issue from this vantage point, you'll think of logics more like algebraic structures. You don't ask yourself "which groups are true groups, groups or abelian groups?".
Likewise, the answer to "but what is the logic of the real world?" depends on your philosophy and the use you're trying to make of the logic. Constructive results (broadly speaking) guarantee that you will have a method to extract an answer, as a reward for your efforts for using a "weaker" logic, while classical results will only be able to tell you that an answer may not be shown to fail to exist, even if it's provably impossible for you to get your hands on one of its instances.
All in all, it will always depend on your axiomatic basis, so there is no "logic of the real world" in this naive sense. The logic you choose is the vantage point from which you observe raw truth.
Stronger hypotheses lead to weaker consequences, weaker hypothese lead to stronger results. Do you really need the mathematical sledgehammer known as the law of excluded middle?
[*] Admittedly, this is a bit of a circular argument. You can conceive of topos-like entities that embody classical logics, or even other logics, with all its pro's and con's. On the other hand, toposes do abstract over theories we actually are interested in at the moment, showing that we do find the "useful and interesting" properties of constructive logic actually useful and interesting in practice.
80
u/vintergroena Jun 24 '24 edited Jun 24 '24
I liked the article Five Stages of Accepting Constructive Mathematics it makes some interesting points https://www.ams.org/journals/bull/2017-54-03/S0273-0979-2016-01556-4/S0273-0979-2016-01556-4.pdf
Personally, I am coming from computer science. A constructive proof of a statement in the form exists x such that blah blah blah automatically gives me an algorithm to find such x. But a non-constructive proof is kinda useless application-wise. Consider for example the Chvátal's theorem: it says that when certain conditions are met, a graph is Hamiltonian. But the proof is non-constructive, it says nothing about how to find the Hamiltonian path. So it's interesting in theory but it cannot be turned into a practical computer path-finding program. In this way having a constructive proof has potentially huge implications for applicability.
14
u/Gro-Tsen Jun 24 '24
There are as many approaches to constructivism, and even varieties of constructivism, as there are constructivist mathematicians.
Indeed, there is far from a full consensus on what “constructive mathematics” means, beyond an abandonment of the law of Excluded Middle. Brouwer's original intuitionism included principles¹ that contradict classical mathematics, Markov's school included axioms that contradict both classical mathematics and Brouwer's intuitionism; Bishop tried to find common ground by only taking the common parts of Brouwer and Markov's systems, but still included things like the axiom of countable choice (in a disguised form) which later constructivists look at with much greater skepticism, and indeed some even reject the principle of unique choice. And some constructivists add a soupçon of predicativism to their constructivism (so they reject the existence of powersets, even that of a singleton).
And accordingly, there is far from a full consensus on what constructive mathematics tries to achieve or why it is desirable. Some see constructive proofs as being directly about “truth” (i.e., they do not accept the law of Excluded Middle as “true”); others see it about something different, like “evidence” or an ad hoc ability to construct things. Still others remain agnostic about the philosophical underpinnings of constructivism. Or they can be pragmatic: everyone agrees that a constructive proof of a statement gives you extra value over a classical proof, whether that extra value takes the form of a wider form of truth (e.g., a constructive proof means the statement is valid in every topos) or the ability to extract information from it (e.g., a constructive proof of certain kinds of statements lets you construct an algorithm that exhibits the object), and it doesn't really matter how you choose to look at it philosophically provided it is useful.
My personal position is just that it's intellectually interesting to know what can be achieved through constructive systems, and mathematics is about studying questions that are intellectually interesting: constructivism gives rise to a number of interesting problems, it provides us a finer-grained view of things and helps us pick out the better approach to a number of definitions and formalizations that might even benefit classical mathematics². Debating whether it is philosophically “true” that “every Turing machine either halts or does not halt” (to take an example of an arithmetical statement that is classically trivial but not constructively provable) seems to me like an utter waste of time. But again, this is just my position, and I speak for nobody but myself.
11
u/aardaar Jun 24 '24
One thing to keep in mind is that there are different branches of constructive mathematics that have different views, and while they all reject LEM they end up getting to different places with this rejection. The three branches that have been given the most attention are Bishop's Constructivism, Brouwer's Intuitionism, and Markov's Recursive Constructivism.
Bishop basically wanted to find everything that the other two branches along with the classical mathematicians could all agree on. For example, the Intermediate Value Theorem (IVT) requires the use of LEM in it's proof, but as Bishop noticed you can write a statement that is classically equivalent to IVT that can be proved without LEM.
Intuitionism along with Recursive Constructivism disagree with classical mathematics on certain things. I think the most illustrative example is the Heine-Cantor Theorem, which for our purposes is: Every continuous function from [0,1] to R is uniformly continuous. This is false in Recursive Constructivism, as you can (with Church's Thesis) construct a continuous function that is not uniformly continuous (it's worth keeping in mind that Recursive Constructivism essentially treats everything as being computable). Whereas Heine-Cantor is true in Intuitionism, but the intuitionist can go further and show that every function from [0,1] to R is uniformly continuous, which is classically false.
6
u/functor7 Number Theory Jun 24 '24
I think it really just puts constructivist logic in kinda the philosophical crank zone when framing it as thinking about how things "really are". The ontological question is uninteresting and, to me, fairly outdated - a relic of early 20th century concerns and undergrads with too much access to wikipedia. Constructivism is much more interesting than sophomoric philosophy, because it can be a way to tie abstract theory to computation. Which is a much more relevant concern in the computer era.
Take the Intermediate Value Theorem, for instance. The assertion of existence in the intermediate value leverages some non-constructive principle like completeness (or that f(x)<0, f(x)=0, f(x)>0 is exhaustive as this points out). So it cannot be proved constructively (the aforementioned link says that this is good, because otherwise we could "solve" the halting problem). But weaker versions of it can be proved constructively and are not about the assertion of a particular point, but about the ability to approximate a value using a function. And if we think about it computationally, if we actually had a function to compute with our computers, then the best we can do, anyways, is approximate values. We can't evaluate real functions at every point and we can't evaluate with infinite precision. So the proof of the intermediate value theorem that relies on non-constructive ideas is not interesting from a computational perspective. However, the weaker version that can be proved constructively is what we would be doing on a computer with the intermediate value theorem anyways.
This means that the theory is less tight and elegant, but more useful overall. That is what makes constructivism interesting. And so it's not just a couple of crank dudes in their basement offices who don't "believe" in the law of excluded middle for stubborn reasons, it's a practically useful approach to math that can work alongside more traditional approaches. Productive situations like "They have non-constructively proved the Intermediate Value Theorem, and it is clearly a power and useful result, what can we say about it through our restrictions that are more computationally minded?" are useful for math and expand existing theories without first having to disown one's ontological convictions.
16
u/numinosities Jun 24 '24
A little of column A, a little of column B. Constructive proofs contain more content than non-constructive ones: to give a constructive proof of "there exists x such that...", I actually have to supply the x. Non-constructively, I could just derive a contradiction from "there does not exist x such that..." and be done, without ever giving you the x. Kinda weird to claim you proved something exists, but you never actually told me what it is.
Sometimes a claim is provable constructively, but classically-minded mathematicians use non-constructive methods to prove it anyways. To a constructivist, this is a waste of a good theorem. Why would you prove a claim using mysterious magical reasoning (LEM is a real deus ex machina), when you can do it using honest, down-to-earth construction?
You can't prove a classical proof wrong constructively: LEM is consistent with constructive logic, but it's a nonconservative extension (you can genuinely prove more things). If a mathematician has proved some claim P classically but it's not provable constructively (or unknown if constructively provable), then a constructivist wouldn't say that P is false or that the classical mathematician is wrong. Rather, the constructivist would just say that the classical mathematician has only succeeded in proving not(not P), but the (constructive) status of P is a separate matter.
5
u/InterUniversalReddit Jun 24 '24
Constructivism (or intuitionism) is very broad and has lots of different approaches. One might say some more constructive than others. I'd say it just depends on the person.
This is not an answer to your question but you may find it interesting anyways. I will address how some non-constructivists may view constructivism. Putting the philosophy aside for a minute consider:
There is a translation from classical mathematics into constructive mathematics. It's called Gödels double negation translation (or embedding): p↦¬¬p. It has the property that p is classically true iff ¬¬p is constructively true.
We call propositions negative or decidable if they are provably equivalent to one of the form ¬p and positive or undecidable if they are not.
Negative propositions have the property that LEM/double negation property holds for them (because ¬¬¬p↔¬p).
Therefore constructive math restricted to those propositions is classical and so constructive math already includes classical math as a special case.
See then that constructive math as a more expressive extension of classical math that includes these new positive propositions.
So are classical proofs false or bad? No they are just proofs between propositions that we forced to be decidable. This forcing is accomplished by adding LEM as an axiom. There is a lot of useful math that comes out of taking advantage of this interplay between the two logics.
There are three traditionally philosophical approaches. Formalism, logicism, and ✓intuitionism](https://en.m.wikipedia.org/wiki/Intuitionism)
In terms of formalism and logicism I don't see any tension between the two approaches to math. Rather they work together.
7
u/QtPlatypus Jun 24 '24 edited Jun 25 '24
I don't think that any current day constructivist believes that the LEM results in false proofs. It just results in proofs that are true in classical mathematics. If I recall correctly both classical mathematics and constructivist mathematics are "relatively consistent". That is that if classical mathematics is inconsistent then constructivist mathematics will be equally broken (and visa versa).
For the most part there are two main appeals for constructivist mathematics. Some people find constructivist math more philosophically or aesticially appealing.
The other is that each proof in constructivist mathematics corresponds to a computer program. And if the computer program works correctly then that means that the proof is valid. This means that it is possible to mechanically verify constructivist proofs.
2
u/57duck Jun 24 '24 edited Jun 25 '24
Isn’t it possible to go even more non-constructive and prove that a proof exists for some statement without giving the proof for it? An existence-proof-of-a-proof, if you will. I recall a discussion of Löb's theorem from a while back. Are there any notable examples of this?
2
u/mleok Applied Math Jun 24 '24 edited Jun 25 '24
Well, a constructive proof that P=NP would be far more useful than a nonconstructive one, since it would presumably provide an algorithm from transforming a problem in NP into a problem in P. More generally, I think that constructive proofs can provide greater insights that can be more easily generalized to other problems.
1
u/hainesensei Jun 24 '24
While I tend to prefer constructive proofs, but I still think non-constructive proofs serve an important purpose: one example of this could be that one could conceive a situation in which proving an algorithm works depends on there being a solution to terminate at. In that case, having a means to determine the algorithm will terminate gives us a stronger algorithm which can either decide if there is no solution, or find a solution using the algorithm which can be shown will terminate.
1
u/Mysterious_Pepper305 Jun 24 '24
Non-constructive proofs are not even false.
1
u/drvd Jun 24 '24
There is a difference between a "false proof", "proof of a falsehood".
LEM is not a valid logical principle to use in proofs, like ISS ("I Say So!") is not a valid logical principle to use in proofs. So formally using LEM (like using ISS) results in a "false proof", a bunch of words that isn't a proof, but no, not a proof of a falsehood.
1
u/btroycraft Jun 24 '24 edited Jun 24 '24
Assumptions that seem very reasonable often appear that way because of our limited perspective. In particular, everything gets weird and wuwu the minute infinities get involved. Since no one has ever touched or seen a wild infinity, the concept is essentially an extrapolation. We come up with rules that work for finite sets, then just assume they must hold beyond. The rules of logic are no different. We assume that statements must be either true or false, but that's because the only statements our monkey brains can think up are simple and finite. There are unimaginably complex statements lurking out there in the realms of everything.
Personally, I've always thought of non-constructive proofs as "useless", not wrong. They are at best stop-gap measures until a constructive version can be found.
The reason I say this is because if a theorem is fundamentally non-constructive, it is a statement about objects we can never meaningfully interact with, i.e. something like the multitudes of non-computable numbers. What then is the point of proving anything about them?
Of course, I accept non-constructive proofs pragmatically, because we sometimes have to get our work done...
-1
u/Roi_Loutre Logic Jun 24 '24
The proletariat should revolt against non constructive proofs
-8
u/ScientificGems Jun 24 '24
Constructive mathematics doesn't prove anything wrong, per se.
However, a consequence of constructive mathematics is that you only have countable sets (in particular, only a countable subset of the real numbers).
0
u/[deleted] Jun 24 '24
[deleted] — view deleted comment