# The relationship between a statement and a theorem

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?

• "A statement that has a proof is called a theorem." If a statement has a proof, it is true. Mar 24, 2018 at 2:02
• Where are they saying that a statement can become a theorem if it is either T or F? Mar 24, 2018 at 2:03
• In that case, the statement "$2^{256}-1$ is not prime" is true, and has a proof. The statement "$2^{256}-1$ is prime" is false, and does not have a proof. Mar 24, 2018 at 2:09
• @PatrickMcAtee in that case, the claim that "$2^{256}-1$ is not a prime" is a theorem. The claim that "$2^{256}-1$ is prime" is false, and is not a theorem. Mar 24, 2018 at 2:09
• @PatrickMcAtee the claim you then have proven is that "the claim that 2^{256}-1$is prime is false". And yes, that claim is a theorem. But the claim that "$2^{256}-1$is prime" is still false, and is still not, and never will be, a theorem. Mar 24, 2018 at 2:28 ## 4 Answers 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. • Ok, I think I am starting to get it now. I think I was confusing myself because I had this idea in my mind that a statement is roughly defined as "a claim that is either T or F", and so plugging that into the sentence "A statement that has a proof is called a theorem" gives "A claim that is either T or F that has a proof is called a theorem". Which begs the question, what is the definition of a statement? Mar 24, 2018 at 2:46 • @PatrickMcAtee Aha, yes, I figured that that was what was going on. and yes, a statement is typically indeed defined as a claim that is true or false. So, we may not know or be able to prove that a statement is true or false, but we do agree it has a truth-value. For example, rhe claim "there is intelligent life on other planets" is something that we agree has a truth-value, and is therefore a claim, even if we don't know whether it is in fact true or false. Mar 24, 2018 at 2:54 • Ugh. First, briefly, are statements in multi-valued logics not statements because they can be something other than true or false? What the phrase "a statement is a claim that is true or false" is poorly grasping at is that a statement is an expression for which asking whether it is true or not is not nonsensical on its face. This is to be contrasted to$2+3$or "sit up" which we can tell from the form alone that it makes no sense to ask are true or not. A statement is simply something with the right form to apply logic to. The formal rendition of this is the notion of a well-formed formula. Mar 24, 2018 at 8:40 • The comment dialogue between you and the OP, on the original question and this answer, add a lot of context to the answer. Would you mind editing it in? I think it would be a big improvement. Mar 24, 2018 at 10:52 • @DerekElkins I believe I addressed this in the OP comments when I said, "If we are working in a logical system where statements can only take on T or F..." Mar 24, 2018 at 16:31 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. 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. • You can talk about systems that aren't "your foundational system for mathematics". In fact, I would go further and say that identifying the systems one learns about in a logic class with "your foundational system" just creates unnecessary barriers and confusion. (And anyway, you're not learning about your "foundational system" but someone else's.) Mar 24, 2018 at 8:58 • @DerekElkins: I have honestly no idea what you intend to convey by your comment. I am explicitly pointing out that any kind of talk of "truth", in the manner done by the book that the asker quotes, is necessarily one that has to be very clearly informed about the two issues I mentioned, namely the issue of meaning of statements and the issue of the foundational system one chooses. Otherwise, it is just a recipe for a total misunderstanding of "truth" and provability. Mar 24, 2018 at 9:46 • @DerekElkins: Also, I specifically said "the foundational system S for mathematics that you choose to use", and that is exactly what the quoted book must be talking about when using the word "proof". Mar 24, 2018 at 9:46 • @PatrickMcAtee: You may see this post. – user170039 Mar 25, 2018 at 3:32 • @user21820: Well. That post was indeed an excellent post and your recommendations helped me too. – user170039 Mar 25, 2018 at 6:35 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).

• In fact now that you mention it, your answer does not address the issue in question, namely why the book says "It might be false and therefore no proof is possible.". It is very misleading to just say that "false" means "refutable", and I know you know that. Mar 24, 2018 at 10:02
• @user21820 I completely agree that saying "false" means refutable is a conflation, though I didn't say that. However, I suspect refutable is what the authors really intend. "Invalid" or "unsatisfiable" would be more precise words if they really wanted a semantic concept. If, as you suggest in your answer, they are talking about a "foundational system for mathematics", then, operationally speaking, refutable is what they want. If I can experience a counter-example, then arguably I can build a refutation from it. Everything else that I know is false, I can only know through proof. Mar 24, 2018 at 17:13