The relationship between a statement and a theorem

Question

I am reading through the book Understanding Mathematical Proof by Taylor and Garnier. The book says "A statement that has a proof is called a theorem." This I am fine with.

In the next paragraph, they say, "A statement may fail to be a theorem for one of two reasons. It might be false and therefore no proof is possible. For example, the statement '$2^{256}-1$ is prime' is false, so no matter how hard we try, we will not be able to find a proof. The other possibility is that we simply may not know whether or not the statement has a proof."

This last sentence, I get. However, the sentence "It [the statement] might be false and therefore no proof is possible" I feel goes against what is said before, "A statement that has a proof is called a theorem". First they are saying that a statement can become a theorem if it is either T of F. Then they are saying that a statement cannot become a theorem if it is F.

Does anyone else follow my logic, or am I mistaken?

Answer 1

A statement for which a valid proof exists is a theorem.

If it is known that the statement is false, then it cannot be a theorem.

If the statement is true but there is no known proof, then that statement is not a theorem.

Answer 2

You write:

First they are saying that a statement can become a theorem if it is either T or F

I highly doubt the book makes that claim. The book probably said that statements can be T or F, but only true statements can become theorems. So, if a statement is false, it can never become a theorem.

Answer 3

It would be clearer to say that a statement that is refutable, meaning its negation is provable, has no proof to indicate that scenario.

With this perspective, we can illustrate the three cases the authors referred to: either $\varphi$ is provable, or $\neg\varphi$ is provable, or neither is (or at least we don't yet know which, if either, is).

Answer 4

Let me give a more accurate explanation.

If the statement is meaningful enough to have a truth value, then either it is true or false. But what does "meaningful" mean? It is a philosophical issue. One may for example say that all arithmetical statements (first-order sentences about natural numbers) are meaningful, because of the apparent sound interpretation of Peano Arithmetic in terms of binary strings in some physical medium and the appropriate algorithms implementing addition and multiplication and comparison. Why do I specifically mention this? Because this notion of meaning (semantics) is not eliminable. (There is another approach, where "truth" is tied to some model, but that just pushes the problem one carpet deeper).

Also, if the foundational system $S$ for mathematics that you choose to use is sound for reality, then every meaningful statement that $S$ proves is true in the real world. The original goal of logic was in fact to capture sound logical deductions in a concrete way so that we can be certain that everything we deduce via logic is true in reality. So we do hope that $S$ is sound for reality (say for arithmetical sentences). To illustrate how it is really relevant to real life, HTTPS (which you are using now to access Math SE) depends on Fermat's little theorem; its truth implies that you can always decrypt the RSA-encrypted content, and there is no better explanation as to why HTTPS works.

So suppose we believe that our foundational system $S$ is sound for reality. Take any meaningful statement $X$. If (within $S$) we can prove $X$, namely we found a proof of $X$ over $S$, then by the definition of "theorem" $X$ is a theorem of $S$. Also, based on our belief we must also believe that $X$ is true in reality. Thus if $X$ is false in reality, we must believe that there is no proof of $X$ over $S$. On the other hand, if we cannot prove $X$, there are actually two possibilities:

1. There is a proof of $X$ (over $S$) but we are not clever or patient enough to find it.

2. There is no proof of $X$. Note that in this case it may still be that $X$ is true in reality. By Godel's incompleteness theorem, if $S$ can reason about basic arithmetic and is sound for reality, then $S$ does not prove its own consistency Con($S$), namely ( $S$ does not prove a contradiction ), despite Con($S$) being true in reality.

So be careful with case 2. Do not assume that if a statement has absolutely no proof over $S$ then it must be false. Intuitively, $S$ is 'not powerful enough' to prove all true statements.

By the way, I deliberately used the word "believe", because it cannot be removed. There can never be a way to prove without doubt that our foundational system is sound for reality. That is one of the reasons the claim in your book is not entirely accurate. For example, if we actually chose an unsound foundational system, then we would be able to prove some statement that is false. The claim crucially hinges on our belief.