40
$\begingroup$

Why can't some mathematical statement (or whatever is the correct term) be both true and false?

For example we can prove (e.g. by induction) that $1+2+3+\cdots+n=\frac{n(n+1)}{2}$ for all positive integers $n$. But how can we be sure that no one will ever find a counter example? What if someone claims that $1+2+3+\cdots+1000$ equals (e.g.) 500567 and not 500500, which is what the above formula claims.

Another example: Why is it impossible for someone to come up with three integer $a$, $b$ and $c$, for which $a^3+b^3=c^3$ (contradicting Fermat's Last Theorem)? This bothers me even in the simple intuitive level.

Then I have heard about Gödel's incompleteness theorems, second of which says (at least this is how I have interpreted it) that an axiomatic system cannot prove its own consistency. So doesn't Gödel's second incompleteness theorem say basically that "anything is possible"? ...that there can be an integer $n$ for which $1+2+3+\cdots+n \neq \frac{n(n+1)}{2}$ or that there can be integers $a$, $b$ and $c$ for which $a^3+b^3=c^3$?

$\endgroup$
  • 18
    $\begingroup$ The downvotes mystify me. $\endgroup$ – user14972 Dec 25 '14 at 23:47
  • 9
    $\begingroup$ The possibility of statements being both true and false would lead to another (and probably useless) logic. Possibly better to redirect your enthousiasm towards logic systems that do not exclude a third possibility next to true and false, like "unprovable and not disprovable", or "unknown". Brouwer's Intuitionism framework is an example in case. It's very interesting - I suggest you have a look! $\endgroup$ – Maestro13 Dec 25 '14 at 23:55
  • 3
    $\begingroup$ No, I didn't mean that. I meant that if Peano is consistent, we will never know it. @someone $\endgroup$ – Thomas Andrews Dec 26 '14 at 0:21
  • 2
    $\begingroup$ @someone No one knows if it is possible to find a contradiction; thus far, no one has done so. We know that you can't prove that it's impossible in Peano arithmetic using only axioms of Peano arithmetic, but mathematicians nonetheless are pretty sure it's not possible (if it were possible to prove a contradiction, we would immediately drop that axiom system because everything is provable in it). $\endgroup$ – cpast Dec 26 '14 at 1:49
  • 11
    $\begingroup$ @ThomasAndrews Actually, we do in fact know the consistency of the Peano axioms, assuming only slightly stronger mathematical principles (essentially, the existence of $\epsilon_0$). Just because Peano Arithmetic can't prove their consistency itself doesn't mean that we can't. See e.g. en.wikipedia.org/wiki/Gentzen%27s_consistency_proof $\endgroup$ – Steven Stadnicki Dec 26 '14 at 2:50

11 Answers 11

12
$\begingroup$

I have two answers for you.

One has already been said so I will only say it briefly: if we exhaustively prove something to be true, there can be no counter example - ie, in the case of an induction argument like you provided.

Second, I will answer you with Godel as well. He is mainly known for his Incompleteness Theorems (because they are far more interesting), but his first famous work was for proving his Completeness Theorem. This tell us many things, among which is that consistent and sound system will not have the counter examples you suggest may exist (to quote Wikipedia, a more general formulation would be "It says that for any first-order theory T with a well-orderable language, and any sentence S in the language of the theory, there is a formal proof of S in T if and only if S is satisfied by every model of T (S is a semantic consequence of T).").

Further, you misunderstand his Incompleteness theorems. It does not say no theory is consistent, it simply says no consistent theory can prove its own consistency. Indeed, Godel proved the consistency of Peano Arithmetic using Type Theory which could not prove it's own consistency.

However, (depending on your level) all of the theorems you encounter can be assured to be true if proven because ZFC (the most common foundation of mathematics) had it's consistency proven by only assuming the existence of a Weakly Inaccessible Cardinal. I think this is widely accepted, so if you can accept the existence of that, you are safe.

EDIT: It has been made known to me in the comments that making the existance of a Weakly Inaccessible Cardinal an axiom creates a far stronger theory than needed to prove the consistency of ZFC. In any case, the point remains that any system of mathematics you're working with has likely been proven consistent by assuming something only slightly stronger - for whatever that is worth.

It also occurs to me that first order logic includes the Law of Noncontradiction (also known as the Law of Excluded Middle) as an axiom, where this is also know to be consistent by Godel's Completeness theorem. So, with this your more general question of "Why not both true and false?" is answered because we take it as axiomatic and show that including such an axiom is consistent.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Assuming the consistency of a weakly inaccessible cardinal is far far stronger than needed to prove the consistency of ZFC. $\endgroup$ – Asaf Karagila Dec 27 '14 at 11:35
  • $\begingroup$ Admittedly, that particular bit came from the small amount of research I did to make sure I wasn't misremembering things. If there is an easier way to prove the consistench of ZFC, I would love to hear it. $\endgroup$ – Logan Dec 27 '14 at 18:54
  • $\begingroup$ Probably none that are easily explainable; but you should edit to remove "only", or at least change it so it is clear that while unprovable from $\sf ZFC$ itself, it is not equivalent to the existence of an inaccessible cardinal. $\endgroup$ – Asaf Karagila Dec 27 '14 at 19:06
23
$\begingroup$

Gödel's theorem could be more accurately interpreted as saying that we can never be sure of the consistency of a sufficiently complex system. We can't be sure, for instance, that the Peano Axioms don't prove $1+1=3$. We sure hope this isn't the case, but no proof would convince us otherwise (and it's probably not, since the Peano Axioms have an intuitive model as being the natural numbers with addition and multiplication).

However, it's still true that $1+1=2$ even if the Peano Axioms say otherwise (indeed, if they proved $1+1=3$, they would also have to prove $1+1\neq 3$, and also every other statement you could possibly make within that system). In fact, we can say that, if a (suitably complex) system is inconsistent, then it admits both a proof and a disproof of every statement - this is the principle of explosion.

The difference is that there is an intended model of the Peano Axioms - the natural numbers with addition and multiplication. This is clearly well-defined and certain things are undeniably true of them. We would therefore expect that the Peano Axioms are, in fact, consistent (though we can't prove it) - and, if it is consistent, everything it proves is true and undeniably so. Even if PA were inconsistent, we would still expect proofs like the $1+2+\ldots+n=\frac{n(n+1)}2$ to be work since they are leveraging such simple properties of the structure of the natural numbers.

The point here is that "truth" and "proof" are distinct statements - but we tend to identify them because we assume our logical systems are consistent, or at least assume that the bits of them we actually use are consistent.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Great answer Meelo! But of course there is another problem: we are assuming that there is "truth" out there and that we can try to reach that truth. If happens to PA to be inconsistent we can just say the problem is the formal system we used and try another way. This goes back to the discussion about mathematics: it's discovered or created by humans? If it is created, then "truth" is only semantics and maybe it's also subject to have contradictions. $\endgroup$ – Integral Dec 26 '14 at 2:24
  • 11
    $\begingroup$ This feels to me a vast misinterpretation of Gödel. The second incompleteness theorem says only that a system cannot prove its own consistency; it says nothing about stronger systems proving the consistency of weaker ones. In fact, as I noted in a comment to the OP there are proofs of the consistency of PA; see en.wikipedia.org/wiki/Gentzen%27s_consistency_proof . $\endgroup$ – Steven Stadnicki Dec 26 '14 at 2:53
  • 2
    $\begingroup$ @Steven I had thought of mentioning that it is possible that a system $A$ proves that $B$ is consistent - which implies "$A$ is consistent implies $B$ is consistent." This is neat, showing that, in that case, if induction to $\varepsilon_0$ with primitive recursive arithmetic is consistent, then PA is. But of course that system can't prove its own consistency - and PA can't prove PRA's consistency (as it would then prove its own consistency) - so we end up seeing that "$A$ proves $B$ is consistent" is a (strict) partial order on axiomatic systems subject to Godel's theorem. $\endgroup$ – Milo Brandt Dec 26 '14 at 3:19
  • 1
    $\begingroup$ @StevenStadnicki The issue with such consistency proofs is that Godel's theorem ensures that the proof won't have the force we'd like it to. Even if a stronger system proves PA consistent, it still doesn't prove that PA doesn't prove $1+1=3$ - it only proves that this fact would also imply the inconsistency of the stronger system. Even the "obvious model" of PA doesn't help here, because the model is infinite, so the number of statements in it is also infinite and cannot be exhaustively checked. $\endgroup$ – Mario Carneiro Dec 27 '14 at 1:33
  • 1
    $\begingroup$ " In fact, we can say that, if a (suitably complex) system is inconsistent, then it admits both a proof and a disproof of every statement - this is the principle of explosion." This is flagrantly untrue; look up paraconsistent logic. What's really going on is that the principle of explosion is built into classical logic. $\endgroup$ – goblin Jan 19 '15 at 17:34
9
$\begingroup$

For example we can prove (e.g. by induction) that $1+2+3+\cdots+n=\frac{n(n+1)}{2}$ for all positive integers $n$. But how can we be sure that no one will ever find a counter example?

The answer to "how can we be sure that no one will ever find a counter example?" is that we can prove (e.g. by induction) that $1+2+3+\cdots+n=\dfrac{n(n+1)}{2}$ for all positive integers $n$.

P.S. "Counterexamples" of the kind whose existence is suggested by Gödel's incompleteness theorem are not in fact numbers in the sequence $1,2,3,\ldots$, that can be reached after some finite number of steps, like the number $1000$. Rather they are members of systems of "numbers" that satisfy all of the axioms within some system that admits algorithmic proof-checking.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ @someone Because the axioms on which the system is founded on force the proof to be valid $\forall n \in \mathbb{N}$ by their nature, it is a logical truth (i.e. a tautology). $\endgroup$ – Thomas Russell Dec 25 '14 at 23:42
  • 9
    $\begingroup$ So, you can prove that the Peano axioms (say) are consistent, Michael? You've basically jumped over the question at hand... $\endgroup$ – Thomas Andrews Dec 26 '14 at 0:17
  • 2
    $\begingroup$ Then you aren't answering the question. @MichaelHardy $\endgroup$ – Thomas Andrews Dec 26 '14 at 1:32
  • 2
    $\begingroup$ You have flagrantly disregarded the poster's question and it is hard to see this answer as anything other than insulting to the poster. $\endgroup$ – DanielV Dec 26 '14 at 1:44
  • 4
    $\begingroup$ @DanielV. That's a bit much, the post wasn't entirely clear, it could have been written by someone who didn't fully understand the basics of a proof. $\endgroup$ – user27182 Dec 26 '14 at 2:00
7
$\begingroup$

Truth is something specific to a particular structure, or a particular model of a theory. Sometimes, when a theory has a canonical model, we abuse the terminology and when we say "true" what we mean is "true in the canonical model". This is the case with the natural numbers and with the real numbers.

Now, the definition of truth in a structure as given by Tarski, is such that $\varphi$ is true if and only if $\lnot\varphi$ is false. Moreover, if $T$ is true in a structure $M$, then every provable from $T$ is true in that structure. And finally, Godel's completeness theorem tells us that indeed if $\varphi$ is true in every structure that $T$ is true, then $\varphi$ is provable from $T$.

So why can't there be a theorem which is both true and false? Because as long as we believe that first-order logic is consistent, theorems are either true or they are false but not both.

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

In consistent logic one single irreparable contradiction would ruin every carefully detailed proof of mathematical theorems, since any theorem would be trivially provable. In paraconsistent logic there are some damage control.

Mathematics don't pretend to be the absolute truth, build on absolute true premises, and therefore contradictions would most presumable be possible to repair by modifying the axioms. But until a contradiction is found, all observations favors the current theories.

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

We call theorems "true" after we've seen a proof of them (and it's not always even clear what exactly a "proof" is). But can we prove that our proof is correct? And if so, can we prove that this second proof is also correct? And if so, can we prove that this third proof is also correct? Do you see the pattern here? It is always possible to remain adamantly skeptical, and thus it's impossible for us to truly convince ourselves of absolute truth. (You can read more about epistemological arguments such as this if you Google the amusingly named "Münchhausen trilemma.")

So it is an abuse of language to call theorems "true," because we can't ever know if a statement really is true. But it's an incredibly useful abuse, so we stick with it -- for example, in the above paragraph I use the word "impossible," which is theoretically ridiculous because I cannot prove something is impossible, but nonetheless very useful in practice. Whether or not mathematics (indeed, all of human knowledge) is on shaky ground epistemologically, progress demands that we relinquish our desire for absolute truth and continue to be satisfied with what logic and empirical reasoning tells us. I can't show that 2 + 2 = 4 is an absolute truth of the universe, but I'm pretty damn sure it's right, so I might as well treat it like it is true, because I'd miss a lot of beautiful, fascinating mathematics if I didn't.

So, here's my answer to your question "how can we be sure that no one will ever find a counter example" to statements like $$1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}.$$ We can't! Proofs are amazingly convincing arguments that no one ever will, though, and that should be sufficient.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Theorems are, by definition, both true and proven. The real problem at hand is that, while we can prove the statement in your post, we cannot prove that its negation is false (without assuming that our axioms are consistent). $\endgroup$ – Dennis Dec 26 '14 at 20:03
3
$\begingroup$

If there was a proof of a statement and of its negation, i.e., if a contradicion was found in Mathematics, then Mathematics would be meaningless, since every statement and its negation would be correct. Actually, any statement whatsoever would be correct if a contradiction was found.

Besides, Mathematics is designed so that its methods , using logic in the background are truth-preserving , as shaktal points out.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Be careful. It wouldn't mean "mathematics is meaningless," only that we need a new axiom system. $\endgroup$ – Thomas Andrews Dec 26 '14 at 0:19
  • 1
    $\begingroup$ O.K, maybe I should say, "as laid-out in this particular moment", it is meaningless, since (as laid out) every thing we can say in Mathematics is true as well as it is false. $\endgroup$ – RikOsuave Dec 26 '14 at 0:21
  • $\begingroup$ Not even that. Most mathematicians probably don't even care about the correctness of foundations. Why do we need PA, say, to do geometry? $\endgroup$ – Kris Dec 26 '14 at 2:05
  • 1
    $\begingroup$ The problem is that if a contradiction was found, anything could trivially be proven in geometry and calculus and algebra and arithmetic and so on. Engineers could try to ignore it for a while but once the contradiction is well understood it could really mess with research, and possibly find holes in previous research. It is likely though the a lot of mathematics would be able to be salvaged on a new axiomatic system. $\endgroup$ – PyRulez Dec 26 '14 at 2:10
1
$\begingroup$

Mathematical proofs are based in logic, which is supposed to be indubitable. Each logical deduction should be so clear that you cannot doubt it, it is this that gives mathematics its apparent certainty.

It is simply a truism that if P(n) holds for all n, then there is no n that violates P(n). It is a real struggle to doubt that the above is true. As humans, this is just something that is utterly obvious to us, so it is a good candidate for certainty.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Why can't some mathematical statement (or whatever is the correct term) be both true and false? ...[H]ow can we be sure that no one will ever find a counter example?

We can't be sure. Logics are created by humans, and humans are not gods. Similar to any other scientific statement, we can show existence, but not universality. The existence of a mistake can be shown, but the universality of a logic never having a mistake will never be demonstrable, no matter what trickery is employed. It is a modern schtick to pretend that this issue can be bypassed with "model theory" (which is certainly a useful subject, and is a common context of Gödel's Theorems), but it is just pretend.

There are some things we can do to give us confidence though. We can reduce the complexity of axioma to the point where the assumptions are "obvious". Sometimes even obvious assumptions have problems and need to be improved though (such as unrestricted set comprehension, which led to Russell's Paradox).

Confidence can also be improved by a logic being used by many different people with many different purposes, without a problem ever being discovered. But it will never be 100% confidence. Eventually, actually finding an inconsistency in the logic would be more interesting than what you are working on anyway, so there is no need to worry. It's like worrying about finding something amazing.

We can, however, assert with 100% confidence that a logical system $A$ is no less correct than another system $B$ by encoding $A$ into $B$ and proving the consistency of $A$ with the assumptions of $B$.

Then I have heard about Gödel's incompleteness theorems, second of which says (at least this is how I have interpreted it) that an axiomatic system cannot prove its own consistency.

This is not an accurate interpretation of the theorem. It is easy to construct a logic that proves it's own consistency, just construct an inconsistent logic with vacuous implication. From an inconsistency follows the assertion of false, and from false follows anything, including consistency.

A better characterization of Gödel's Second Incompleteness Theorem (but still nowhere nearly as formal as the actual theorem) is:

  • A sufficiently interesting logic that can prove it's own consistency is inconsistent

So doesn't Gödel's second incompleteness theorem say basically that "anything is possible"?

If your logic is sufficiently interesting and contains a proof of its own consistency, then yes. Otherwise and more commonly, no.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

It actually might be both true and false at the same time in a way. For example

lim(x->0) f(x)/g(x) with f(0)=0 and g(0)=0 might be true or might be false depending on the speed f(x) and g(x) reach the zwero when x reaches zero. You might even get two results depending on the direction from which you reach the 0.

The computer algebra system maxima will return "undecided" in this case.

In other cases solve(f(x)=0,x); will return a list of results. This, too is an example where a question can neither be answered by "true" nor by "false".

| cite | improve this answer | |
$\endgroup$
-4
$\begingroup$

We would have hoped that in mathematics every reasonable statement is either true or false. As Gödel showed, that is not the case: In any mathematical system, there are two possibilities: Either most statements are either true or false but some are neither true or false. Or the system is contradictory, which means every statement is both true and false at the same time which means the whole system is useless.

Now you asked "Is it possible that a simple statement is both true and false"? We don't know which of the two kinds of systems we are using. We very very much hope that it is not contradictory. In that case, no, a simple statement can be either true, or false, or neither at all. If our system is contradictory, then yes, that simple statement will be both true and false. Actually, every statement will be both true and false.

In your example, suppose we have a proof that a certain sum is 500,500 but we also calculated correctly that the same sum is 500,567. Then every mathematical statement is both true and false: We have just shown that 500,500 = 500,567, therefore $0 = 17$, therefore $0 = 1$. Then as an example, for every $a, b, c > 0$ and $n \ge 3$,

$a^n + b^n = 1 \cdot (a^n + b^n - c^n) + c^n = 0 \cdot (a^n + b^n - c^n) + c^n = c^n$

So every possible tuple $(a, b, c, n)$ is a counterexample to Fermat's Last Theorem!

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ (1) You are confusing true and provable; (2) this is not what Gödel showed. $\endgroup$ – Asaf Karagila Dec 27 '14 at 11:33

Not the answer you're looking for? Browse other questions tagged or ask your own question.