# Can conjectures be proven?

Conjectures are unproven proposition that are believed to be true. But how can one believe something without actually proving it? Why can't conjectures be proven? Also, why do we just take axioms to be true? Why do we constructs proofs by using axioms without actually proving axioms are true and by simply believing it to be true? Is it because we need to make some sort of assumptions in order to actually prove something, thus we assume these axioms are true?

Thanks

• -1 for the assumption in the title: "why can't conjectures be proven" sounds like "why can't children grow up". Nov 11, 2013 at 21:24
• The answer to your question "how can one believe something without actually proving it," is very simple... faith! If you have faith on another person (regardless of how that happens), you will believe that whatever that person tells you is the truth. Since your belief would be based on the trust you have on another person, it is irrelevant whether the "something" is proven or not. The only other option you have, is to believe everything is false, except those things that you can prove (to) yourself. Nov 12, 2013 at 1:09
• To elaborate on Michael's point, if you had a conjecture and then proved it, it would cease to be a conjecture and would subsequently be a theorem. Arguably in mathematics, it always was a theorem - we just called it a conjecture because we didn't know whether it was a theorem or not. But your concern about axioms and assumptions in mathematics still has philosophical interest. Nov 12, 2013 at 12:02
• Reverting the downgrade since the edited question now makes sense and is, in fact, interesting. Nov 12, 2013 at 23:21
• Conjectures can be proven. When it is proved, it's not a conjecture anymore. Nov 13, 2013 at 9:40

## 6 Answers

Conjectures are based on expert intuition, but the expert or experts are not [hopefully yet] able to turn that intuition into a deduction from axioms to theorem. Sometimes much is predicated on conjectures; for example, modern public key cryptography is based on the conjecture that prime factoring is a prohibitively computationally expensive operation. If this conjecture is false, the global financial system could be dealt a huge blow by a genius—not to mention other infrastructure which is hooked up to accessible networks and protected by encryption vulnerable to prime factoring.

By definition, axioms are givens and not proved. Consider: a proof reasons from things you believe to statements that 'flow from' those beliefs. If you don't believe anything, you can't prove anything1. So you've got to start somewhere—you've got to accept some axioms that cannot be proved within whatever formal system you're currently using. This is argued by the Münchhausen trilemma (Phil.SE Q). So, I argue that the best we can do is find facts which are true, as defined by my answer to What is the difference between Fact and Truth?

1 more formally: If you won't start from any axioms, you cannot prove any theorems, for the laws of logic do not allow you to construct something out of nothing.

• Your "if you don't believe anything, you can't prove anything" view depends on a psychologistic account of what mathematical proofs are. I'm not convinced this is a good enough foundation for an argument that you can't prove axioms, because that suggests that the notion of an Axiom is also psychologistic, and that much is very much in dispute. Nov 12, 2013 at 18:39
• @PaulRoss: Does your criticism hinge on my use of 'belief'? I was trying to be a bit colloquial; a more precise statement would replace 'belief' with '[tentatively] accept'. There is, of course, a huge difference between consistent formal systems and the claim that a given formal system is a good match to reality. Hence my reference to the Fact vs. Truth Q. Nov 12, 2013 at 19:48
• But the same issue was there in your Fact/Truth answer! You can't assume that what's essentially going on in maths or metaphysics is anything to do with psychology, even if you want to talk about acceptance or perception instead of belief. Maybe there are proofs that we might not with our cognitive capacities be able to find or formulate. That doesn't make those proofs invalid! Nov 13, 2013 at 1:30
• @PaulRoss: Proofs which we could verify but not find or formulate would be considered valid; if we couldn't verify the proof, we wouldn't accept it, would we? This would seem to get into the realm of believing based on authority. In terms of the Fact/Truth answer, you left me hanging in the comments. I'm still not really clear on the main thrust of your criticism—are you arguing that there might be ways of thinking/reasoning which are inaccessible to humans? If so, I'll happily posit that, but what would we do with such a claim other than to merely acknowledge it and then move on? Nov 13, 2013 at 3:22
• Yes, I am arguing that it's possible that there are valid arguments not humanly capturable, and that your reasoning only counts as valid in the assumption that it is impossible. And the force with which your claims are presented needs that assumption to get off the ground, since you're appealing to ideas like "Cannot be proven" and "axioms being possibly wrong" in the face of a domain of facts in possible worlds. Nov 13, 2013 at 15:13

The label conjecture is only used for proposition that might one day be decided to be true, false or undecidable. The proposition P≠NP is considered to be a conjecture, but the consistency of ZFC is not considered to be a conjecture. The reason why we believe that both propositions are true is that we haven't found efficient algorithms for NP complete problems, despite intense efforts, and we haven't found a contradiction in ZFC, despite making heavy use of it. We found unpleasant properties of ZFC like the Banach-Tarski paradox, but being an unsuitable model of physical reality is different from a mathematical inconsistency.

The consistency of Peano arithmetic is an even more interesting example: It seems to follow from Gödel's second incompleteness theorem that the consistency of Peano arithmetic cannot be proved by purely finitary means. This was indeed the opinion of von Neumann, expressed in a letter to Gödel before the publication of Gödel's results. Gödel himself explicitly rejected this conclusion in his paper1. Indeed, Gerhard Gentzen later proved by finitary means that Peano arithmetic is consistent. Especially on page 555-556 (~ page 64 of the proof), he proves that the ordinal numbers smaller than ϵ0 are well ordered by finitary means in a way which cannot be formalized in Peano arithmetic. The result is that we believe that Peano arithmetic is consistent, but (at least some mathematicians still believe) that its consistency can't be proved. Well, even mathematical proofs depend on general context, implicit assumption and explicit premises. Axioms are either part of the general context, or part of the explicit premises.

Edit I used Banach-Tarski paradox and Gentzen's consistency proof as examples for the unclear relationship between mathematical "conjectures" and real world "relevance", even so the actual examples I personally care about are much simpler and probably even "solvable", at least in theory. I did this, because these are well known and well investigated examples. The drawbacks are that there are unsettled controversies over them (like the criticism of Voevodsky's position regarding consistency), and that I'm not at all an expert on their details. I now read some of the original publications and parts of the controversy, and I have to admit that at least the historical account in my answer was misleading and unfair to Gödel. The least controversial modern "answer" to the consistency problem is probably given by the reverse mathematics program, which shows that Voevodsky's position is really quite questionable.

1. Gödel basically observed that it's not at all clear that finitary means can always by formalized in Peano arithmetic:

Es sei ausdrücklich bemerkt, daß Satz XI (und die entsprechenden Resultate über M, A) in keinem Widerspruch zum Hilbertschen formalistischen Standpunkt stehen. Denn dieser setzt nur die Existenz eines mit finiten Mitteln geführten Widerspruchsfreiheitsbeweises voraus und es ware denkbar, daß es finite Beweise gibt, die sich in P (bzw. M, A) nicht darstellen lassen.

• The idea that Con(ZFC) isn't considered a conjecture sounds interesting from an epistemological perspective. Do you think it's a kind of a "we've tried enough cases so are reasonably confident" kind of assessment? Or more of "it serves as a cognitively useful thing to think about ZFC and its status as a foundation so let's assume it metatheoretically for now and address problems as they show up"? Nov 12, 2013 at 18:32
• @PaulRoss It's definitively not the "we've tried enough cases so are reasonably confident" kind of assessment. The "address problems as they show up" is part of the reason, together with the fact that already the consistency of the much weaker Peano arithmetic system is known to be unprovable. Instead of trying to prove Con(ZFC), one proves facts like that ZFC is equiconsistent with ZF. But the impredicativity of ZFC makes it difficult to go much further in this direction. This is different from NF, which might be proved equiconsistent with “bounded Zermelo set theory”/“Mac Lane set theory”. Nov 13, 2013 at 0:34
• If ZFC weren't powerful enough to have properties which don't seem to represent physical phenomena, we would probably use a more powerful mathematical framework which did, rather than use ZFC. People like visual, physical intuitions, but they enjoy the idea of using abstract tools to do powerful and improbable things more. Nov 15, 2013 at 10:11
• I wonder what you mean by "heavily criticized"; IMO an interesting result came out of that criticism, as can be seen by reading all three articles in the series. Much math and philosophy involves criticizing unclear/seemingly contradictory statements, and coming up with better attempts. I should think we would celebrate such criticism? But maybe you're just pointing out that being prominent doesn't save you from criticism. :-) Nov 15, 2013 at 21:24
• @NieldeBeaudrap I used ZFC as a placeholder for C++, which is a foundation for my daily work, in a certain sense. I was thinking about properties like "abs(0x80000000) < 0", which might be unfortunate, but not strictly speaking an inconsistency. I tried to express the feeling that people know that current foundations are not perfect, but that it would be incredibly hard to fix or avoid such issues. And similar to C++, the costs of messing with the foundations without expected significant benefits are just too hight. Nov 16, 2013 at 12:39

In order to figure out how one can assume validity of axioms let's stand back from Mathematics for a moment and look at natural sciences.

How does one come up with Laws of Physics? Why does one assume that, say, energy is conserved quantity? The answer is that physicists don't make any such assumptions. Physicists experiment with a variety of mathematical models, compute what predictions these models would make, and decide whether tentatively to accept those models based on the quality of their fit to the empirically observed reality.

For example, physicists observe that the law conservation of energy holds true in all known circumstances, despite earnest effort to refute it. More importantly, the assumption that the law holds in unknown circumstances leads to valuable insight into the nature and new discoveries, and the law's predictions always prove true when the new techniques make direct experimentation with new circumstances possible. Based on that, physicists accept conservation of energy as a fundamental law; however, they remain open to review that law if new discoveries would disagree with it.

Something similar happens with the foundations of Mathematics. Despite the popular belief imposed by the castrated presentation of mathematics in American schools, mathematicians don't apriori assume the validity of axioms. Instead, mathematicians experiment with a variety of sets of axioms and figure out which minimal set would lead to better understanding of mathematical objects.

According to V.I. Arnold, "Mathematics is part of physics. Physics is an experimental science, a part of natural science. Mathematics is the part of physics where experiments are cheap." Axioms are not apriori assumptions; in Kant's language they are analytic aposteori propositions.

To put it more succinctly, axioms to mathematics are what fundamental laws are to physics. And, just as physicists are open to review of their fundamental laws if new evidence would lead to doubt of their validity, mathematicians are open to review the axioms if new consideration would prompt them to do so. Perhaps the best known case the revision of the Euclid's 5th axiom that led to development of spherical and hyperbolic geometries and later to Riemannian geometry that has become the foundation of General Relativity. Another major revision was done to set theory when Russell has shown that the naive set theory axioms led to contradictions.

The strength of axioms is not in that they are assumed true; on the contrary, their strength is in they have been virtually proven to be true by the overwhelming amount of powerful conclusions that can be made on the basis of their assumption as well as continuous earnest attempt to undermine them and willingness to review them if necessary.

Michael is certainly correct, and I would take his final paragraph just a little further. Some axioms are observable phenomena. Here's an example:

I informed my young son, without substituting a's and b's for numbers, that for any two numbers (natural numbers in this case) a and b, a*b = b*a. I demonstrated my assertion by constructing rectangles out of 12 pennies. 12 pennies can be displayed as 6 rows of 2, and that can be seen as 2 rows of 6. Similarly, 4 rows of 3 pennies can be seen as 3 rows of 4 pennies. Both perspectives (3*4 and 4*3) consist of 12 pennies arranged in precisely the same way. 3*4 and 4*3 are two ways of viewing the same thing.

A set of axioms which includes this associative property of multiplication as an axiom has, I am told, been shown to be equivalent to the Peano axioms. Kaye, Richard, 1991. Models of Peano arithmetic. Oxford University Press. ISBN 0-19-853213-X. I approve of the associative property being an axiom or being derivable from our axioms because I plainly see it in the pennies on the table.

We don't necessarily "believe" the axioms or arithmetic or set theory are true. It's more a matter of arbitrarily stating that they are going to be the unshakable truths upon which further investigation will rest. Are there such things as infinite sets? The basic axioms cannot prove they exist, nor can they prove that they don't exist. It makes computation more streamlined to add an axiom stating that infinite sets exist; and the Haskell programming language is more elegant by virtue of its infinite lists, arrays, and sets (they come with lazy evaluation).

I gather from the article at http://en.wikipedia.org/wiki/Finitism that there are some people who seriously believe some axioms and disbelieve others, rather than taking the pragmatic approach that seems, to me, to be much more sensible. I think most of the mathematicians who eschew the use of infinite objects aren't doing so out of a belief that they "really" don't exist.

"The princess and the prince discuss what's real and what is not. It doesn't matter inside the gates of Eden" - Bob Dillon "It isn't either" - LaoTsu and Kurt Gödel

• Can you better explain why you've thrown two quotations on to the end? (we don't do taglines on se). May 28, 2014 at 23:47
• I have degrees in chemistry, mathematics, and law. I am currently developing a web application in the Haskell programming language. Logical thinking is second nature for me. I consider it a tool and an amusement, but not a path toward having any confidence when my it comes my time to die, that I have the slightest clue as to what just happened. Jun 19, 2014 at 1:29
• I have no idea how that responds to anything I said... Jun 19, 2014 at 1:36
• It surely doesn't respond to anything you said. It was the lead-in to a long answer that was rejected for being too long. I thought I had erased the comment by substituting a blank box as an edit. If you tell me your email address I'll keep it to myself and send you the answer I wrote. Jun 19, 2014 at 2:30

At the risk of being a bit of a 'wag', conjectures can never be proven, because once their assertions have been proven, they aren't conjectures anymore, they are theorems. ;->