Introduction to Proofs: An Active Exploration of Mathematical Language

Before starting proof techniques, we introduce a few mathematical definitons. Keep in mind, mathematical definitions are constructed to provide a common language for proofs. They are intended to provide rigor and precision. They are NOT intended to provide conceptual understanding. You need to develop conceptual understanding of the terms apart from the definition. However, we need to rely on definitions to provide structure for our proofs.

We defined the integers in Definition 1.1.1. Recall from Section 2.1, we use \(\mathbb{Z}\) for the set of integers.

You are probably familiar, generally, with even numbers such as 2, 4, 6, 8, and odd numbers such as 3, 5, 7, 9. But the next example uses the definitions to look at more examples.

We've now seen several examples of even/ odd integers. Are there integers which are both even and odd? Can an integer be neither even nor odd? The answer to both questions is no. However, proving that every integer is even or odd (and not both), is pretty challenging, and we won't try to do it, yet. But for the moment we will assume if we know an integer is NOT even, then it must be odd, and vice versa.

We start our proof techniques by looking at how to prove universal conditional statements, which we studied in Section 2.3. Recall, a universal conditional statement has the form “For all \(x\in D\text{,}\) if \(x\) has property \(P\) then \(x\) has property \(Q\text{.}\)” We can restate this using symbolic notation: For all \(x\in D, P(x)\rightarrow Q(x)\text{.}\) Although we saw how to write “for all” using the symbol \(\forall\text{,}\) in this book we will generally avoid the quantifier symbols in our proofs. This just helps with clarity for the reader and is fairly standard in mathematical writing. However, the techniques for understanding and negating quantified statements from Section 2.2 still apply.

One very limited method for proving universal conditional statements is the method of exhaustion: for each specific \(a\in D\) where \(P(a)\) is true, show \(Q(a)\) is true. In other words, we check if \(P(a)\) then \(Q(a)\) for each \(a\in D\text{.}\)

The method of exhaustion only works if we can show the statement for every \(x\in D\text{.}\) But if \(D\) is infinite, we need to use a more general method. We saw the limitations of this method in Section 1.1. Although this method won't result in a proof if our set is infinite, it can be a helpful first stab at a proof in that generating examples can lead to more general insight into the problem. Our first more general technique is the method of direct proof.

A counterexample is used to disprove a universal conditional statements. If we have a universal conditional statement of the form “for all \(x\in D, P(x)\rightarrow Q(x)\)”, we show it is false with the following process.

Often in math we need to identify whether a statement is true or false, so that we know whether we need to prove the true statement or disprove the false one. In order to practice, we give a few more definitions.