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\) for the set of integers.

Definition 3.1.1 .

Definition 3.1.2 .

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.

Example 3.1.3 . Even or Odd.

Activity 3.1.1 . Always, Sometimes, or Never Even.

Let \(a, b\) be integers. Determine if each of the following are always even, always odd, or sometimes even/ sometimes odd.

(a)

(b)

(c)

(d)

(e)

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

Example 3.1.4 . Method of Exaustion.

Prove for all \(n\in \mathbb\text\) if \(n\) is even and \(4\leq n\leq 16\text\) then \(n\) can be written as the sum of prime numbers.

Proof .

We can find all the integers that are even and \(4\leq n\leq 16\text<.>\) This is the set \(\\text<.>\) For each of these numbers we can demonstrate a way to write them as the sum of primes: \(4=2+2, 6=3+3, 8=3+5, 10=3+7, 12=5+7, 14=7+7, 16=11+5\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 .

Method of Direct Proof.

To prove statements of the form “for all \(x\in D, P(x)\rightarrow Q(x)\) ” using the method of direct proof we use the following process.

Example 3.1.5 . Direct Proof.

Proof .

Let \(x\) be even. Then by definition, \(x=2k\) for some \(k\in \mathbb\text<.>\) Then \(x+1=2k+1\) where \(k\in \mathbb\text<.>\) Which means \(x+1\) is odd.

Example 3.1.6 . Sum of Even Numbers.

Note, this statement is not obviously in the form of an if. then. We often have to translate statements into more formal statements before proving them.

Proof .

Let \(a, b\) be even. Then by definition, \(a=2k\) for some \(k\in \mathbb\) and \(b=2j\) for some \(j\in \mathbb\text<.>\) (Note, we cannot use \(k\) for both \(a\) and \(b\) as they likely are two different numbers.) Then \(a+b=2k+2j=2(k+j)\) where \(k+j\in \mathbb\text<.>\) Which means \(a+b\) is even.

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

Disproving by Counterexample.

To disprove statements of the form “for all \(x\in D, P(x)\rightarrow Q(x)\) ” we find a counterexample.

Find \(x\in D\) making, \(P(x)\) true and \(Q(x)\) false. Note, this step may happen as scratchwork, not part of your counterexample.

Example 3.1.7 . Counterexample.

Activity 3.1.2 . Proving a Statement is False.

Give a counterexample to show the following statement is false: for all \(a, b\in \mathbb\) if \(a^2=b^2\) then \(a=b\text<.>\)

Make the proof self-contained. Try not to reference many other mathematical facts. Many proofs in this course will rely entirely on definitions.

Use complete sentences. Even equations have a sentence structure. Your proof should be able to be read in sentences.

Include words. Often using a word is better that using a symbol. Many proofs have no symbols in them at all.

The audience for your proofs is not the instructor. Think of the audience as being your peers in the course or even yourself in a few weeks (or months) when you might have forgotten the specific content. Write so you will know what you meant later.

The goal of a proof is to write a clear, easy to follow argument--not to just get to the end. The “answer” is the proof itself. Use space, start a new line, set equations on their own line.

Never feel that you have to be able to know what the end of the proof will look like before you can start. Write proofs one step at a time. Start with what you know. See if you can do one thing. See if you can do another thing. Look at where you want to go. Do not try to see the whole picture at once. This is also good advice for reading a proof.

Using an example for a proof. If you need to prove a statement for all \(x\text<,>\) it is not enough to show it for an example.

Jumping to conclusions. Giving inadequate reasons. This often occurs if you rely on additional mathematical ideas or don't connect your ideas to each other.

Assuming what you need to prove. This is a big one. This most often occurs when there is confusion about conditional statements. Be careful about identifying the “if” and the “then” in a statement.

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.

Definition 3.1.8 .

An integer, \(n\text<,>\) is if \(n>1\) and, for all positive integers \(r, s\text<,>\) if \(n=rs\) then \(r=1\) or \(s=1\text<.>\)

Definition 3.1.9 .

An integer, \(n\text<,>\) is if \(n>1\) and \(n=rs\) for some positive integers \(r, s\) with \(r\neq 1\) and \(s\neq 1\text<.>\)