5
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ "A statement that has a proof is called a theorem." If a statement has a proof, it is true. $\endgroup$ – Air Conditioner Mar 24 '18 at 2:02
  • 2
    $\begingroup$ Where are they saying that a statement can become a theorem if it is either T or F? $\endgroup$ – Bram28 Mar 24 '18 at 2:03
  • 2
    $\begingroup$ 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. $\endgroup$ – Air Conditioner Mar 24 '18 at 2:09
  • 2
    $\begingroup$ @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. $\endgroup$ – Bram28 Mar 24 '18 at 2:09
  • 2
    $\begingroup$ @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. $\endgroup$ – Bram28 Mar 24 '18 at 2:28
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – pmac Mar 24 '18 at 2:46
  • $\begingroup$ @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. $\endgroup$ – Bram28 Mar 24 '18 at 2:54
  • $\begingroup$ 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. $\endgroup$ – Derek Elkins left SE Mar 24 '18 at 8:40
  • $\begingroup$ 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. $\endgroup$ – Matthew Leingang Mar 24 '18 at 10:52
  • $\begingroup$ @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..." $\endgroup$ – pmac Mar 24 '18 at 16:31
2
$\begingroup$

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.

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

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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.) $\endgroup$ – Derek Elkins left SE Mar 24 '18 at 8:58
  • 1
    $\begingroup$ @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. $\endgroup$ – user21820 Mar 24 '18 at 9:46
  • 1
    $\begingroup$ @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". $\endgroup$ – user21820 Mar 24 '18 at 9:46
  • 1
    $\begingroup$ @PatrickMcAtee: You may see this post. $\endgroup$ – user170039 Mar 25 '18 at 3:32
  • 1
    $\begingroup$ @user21820: Well. That post was indeed an excellent post and your recommendations helped me too. $\endgroup$ – user170039 Mar 25 '18 at 6:35
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – user21820 Mar 24 '18 at 10:02
  • $\begingroup$ @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. $\endgroup$ – Derek Elkins left SE Mar 24 '18 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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