Discrete Mathematics: An Open Introduction, 3rd edition

We have considered logic both as its own sub-discipline of mathematics, and as a means to help us better understand and write proofs. In either view, we noticed that mathematical statements have a particular logical form, and analyzing that form can help make sense of the statement.

At the most basic level, a statement might combine simpler statements using logical connectives. We often make use of variables, and quantify over those variables. How to resolve the truth or falsity of a statement based on these connectives and quantifiers is what logic is all about. From this, we can decide whether two statements are logically equivalent or if one or more statements (logically) imply another.

When writing proofs (in any area of mathematics) our goal is to explain why a mathematical statement is true. Thus it is vital that our argument implies the truth of the statement. To be sure of this, we first must know what it means for the statement to be true, as well as ensure that the statements that make up the proof correctly imply the conclusion. A firm understanding of logic is required to check whether a proof is correct.

There is, however, another reason that understanding logic can be helpful. Understanding the logical structure of a statement often gives clues as how to write a proof of the statement.

This is not to say that writing proofs is always straight forward. Consider again the Goldbach conjecture:

We are not going to try to prove the statement here, but we can at least say what a proof might look like, based on the logical form of the statement. Perhaps we should write the statement in an equivalent way which better highlights the quantifiers and connectives:

What would a direct proof look like? Since the statement starts with a universal quantifier, we would start by, ``Let \(n\) be an arbitrary integer." The rest of the statement is an implication. In a direct proof we assume the “if” part, so the next line would be, “Assume \(n\) is greater than 2 and is even.” I have no idea what comes next, but eventually, we would need to find two prime numbers \(p\) and \(q\) (depending on \(n\)) and explain how we know that \(n = p+q\text{.}\)

Or maybe we try a proof by contradiction. To do this, we first assume the negation of the statement we want to prove. What is the negation? From what we have studied we should be able to see that it is,

Could this statement be true? A proof by contradiction would start by assuming it was and eventually conclude with a contradiction, proving that our assumption of truth was incorrect. And if you can find such a contradiction, you will have proved the most famous open problem in mathematics. Good luck.