Why not both true and false?

Question

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$?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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.

Answer 9

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".

Answer 10

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.