Section 4.1 Direct Proof and Counterexample
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.
Definition 4.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 4.1.3. Even or Odd.
Is -5 even or odd?
Answer 1.
Is 0 even or odd?
Answer 2.
Answer 3.
Answer 4.
Activity 4.1.1.
Let \(a, b\) be integers. Determine if each of the following are always even, always odd, or sometimes even/ sometimes odd.
(a)
\(12ab^3\)(b)
\(3ab\)(c)
\(10b^2-4ab+1\)(d)
\(4b+3\)(e)
\(5a+3b\)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. We will use this fact, though, so if we know an integer is not even, then it must be odd, and vice versa.
Definition 4.1.4.
An integer, \(n\text{,}\) is prime if \(n>1\) and, for all positive integers \(r, s\text{,}\) if \(n=rs\) then \(r=1\) or \(s=1\text{.}\)
Definition 4.1.5.
An integer, \(n\text{,}\) is composite if \(n>1\) and \(n=rs\) for some positive integers \(r, s\) with \(r\neq 1\) and \(s\neq 1\text{.}\)
Example 4.1.6. Prime or Composite.
Is 1 prime?
Answer 1.
\(n>1\text{.}\)
Is 1 composite?
Answer 2.
\(n>1\text{.}\)
Is 121 prime?
Answer 3.
\(121=(11)(11)\text{.}\)
Answer 4.
Activity 4.1.2.
Consider the statement “for all positive integers \(r\) and \(s\text{,}\) if \(n=rs\) then \(r=1\) or \(s=1\)” from the definition for a prime number.
(a)
Write the statement symbolically using quantifiers and connectives.
(b)
Write the negation of the statement symbolically.
(c)
How is the negation related to the definition of a composite number? Is every integer either prime or composite?
We state our first proof technique.
Proving Existential Statements.
To prove \(\exists x\in D, Q(x)\)
-
Find \(x\in D\) making, \(Q(x)\) true. Note, this step may happen as scratchwork, not part of your proof.
-
For your proof, state \(x\text{.}\)
This type of proof is called a constructive proof of existence
Example 4.1.7. Existential Proof.
Example 4.1.8. Another Existential Proof.
Proof.
Activity 4.1.3.
Let \(r, s\in \mathbb{Z}\text{.}\) Prove there exists \(k\in \mathbb{Z}\) such that \(3k=12r+15s\text{.}\)
There are other ways to prove existence. One common way is a proof by contradiction, which we will see later in Section 4.5. There are several examples of existence proofs in calculus where it can be shown that something exists without constructing a specific value. For example, take a look at a proof of Rolle’s Theorem, the Mean Value Theorem, the Extreme Value Theorem, or the Taylor Remainder Theorem (Calc II).
Since the negation of a universal statement is an existential statement, we disprove a universal statements with a counterexample.
Counterexamples.
To disprove the statement \(\forall x\in D, P(x)\rightarrow Q(x)\)
-
Find the negation of the statement: \(\exists x\in D, P(x)\wedge \sim Q(x)\text{.}\)
-
Find \(x\in D\) making, \(P(x)\) true and \(Q(x)\) false. Note, this step may happen as scratchwork, not part of your counterexample.
-
For your counterexample, state \(x\text{.}\)
A counterexample is really just an existence proof of the negation. But since we are showing the original statement is false, we usually just call it a counterexample to the (original) statement.
Example 4.1.9. Counterexample.
Disprove the statement: Every prime number, \(p\text{,}\) is odd.
Activity 4.1.4.
Give a counterexample to show the following statement is false: For all \(a, b\in \mathbb{R}\) if \(a^2=b^2\) then \(a=b\text{.}\)
One of the most common mathematical statements is the universal conditional. We will see several techniques for proving \(\forall x\in D, P(x)\rightarrow Q(x)\text{.}\) The first method, method of exhaustion, is very limited, but worth mentioning.
Method of Exhaustion.
To prove \(\forall x\in D, P(x)\rightarrow Q(x)\text{,}\) where \(D\) is a finite set:
Example 4.1.10. Method of Exaustion.
Prove for all \(n\in \mathbb{Z}\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 \(\{4, 6, 8, 10, 12, 14, 16\}\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.
Method of Direct Proof.
To prove \(\forall x\in D, P(x)\rightarrow Q(x)\text{:}\)
-
Assume \(P(x)\) is true.
-
Show \(Q(x)\) is true.
Example 4.1.11. Direct Proof.
Proof.
Let \(x\) be even. Then by definition, \(x=2k\) for some \(k\in \mathbb{Z}\text{.}\) Then \(x+1=2k+1\) where \(k\in \mathbb{Z}\text{.}\) Which means \(x+1\) is odd.
Example 4.1.12. Sum of Even Numbers.
Prove the sum of two even integers is even.
Note, this statement is not obviously in the form of an if...then. We often have to translate statements into a more formal statement before proving them. Translation:
Proof.
Let \(a, b\) be even. Then by definition, \(a=2k\) for some \(k\in \mathbb{Z}\) and \(b=2j\) for some \(j\in \mathbb{Z}\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{Z}\text{.}\) Which means \(a+b\) is even.
Some proof writing advice:
-
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.
-
Give reasons. Connect your statements together.
-
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.
Some common proof-writing errors:
-
Using an example for a proof. If you need to prove a statement for all \(x\text{,}\) it is not nough to show it for an example.
-
Using the same variable to represent two different things.
-
Jumping to conclusions. Giving inadequate reasons. This often occur 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.
Example 4.1.13. Prove or Disprove.
Since we need to try to decide if the statement is true or false, first try some examples.
Answer 1.
\begin{gather*}
n=1; n^2+3n+2=6; \textrm{not prime}\\
n=5; n^2+3n+2=42; \textrm{not prime}\\
n=8; n^2+3n+2=90; \textrm{not prime}
\end{gather*}
After trying several examples, we might guess that it is false. If we want to disprove the statement then we need to prove the negation. Find the negation of the statement.
So we need to show that for a general \(n\) we can always write \(n^2+3n+2\) as a product of \(r, s\) with \(r, s\neq 1\text{.}\)
We can try to factor the expression: \(n^2+3n+2=(n+2)(n+1)\text{.}\)
Let \(r=n+2, s=n+1\text{.}\) We need to show that \(r, s\neq 1\text{.}\) Since \(n>0, n+2>2\) and \(n+1>1\text{.}\) Thus \(r, s\neq 1\text{.}\) Therefore, \(n^2+3n+2\) is not prime.
Activity 4.1.5.
Prove or disprove the following statements.
(a)
(b)
(c)
For all \(m, n\in \mathbb{Z}\text{,}\) if \(n\) and \(m\) are odd, then their product, \(nm\text{,}\) is odd.
Reading Questions Check Your Understanding
1.
True.
False.
True or false: \(\forall n\in \mathbb{Z}, 5n+3\) is odd.
2.
True.
False.
True or false: \(\forall n\in \mathbb{Z}, 5n+3\) is even.
3.
True.
False.
True or false: \(\forall n\in \mathbb{Z}, 2n+7\) is odd.
4.
True.
False.
True or false: \(\forall n\in \mathbb{Z}, 4n+12\) is even.
5.
True.
False.
6.
True.
False.
True or false: 99 is composite.
7.
True.
False.
True or false: -99 is composite.
8.
True.
False.
True or false: \(\forall n\in \mathbb{Z}, n^2+1\) is prime.
Exercises Exercises
1.
Use the definitions of even, odd, prime, and composite to justify your answer to each of the following questions. Let \(m\) and \(n\) be integers.
-
Is \(6m+8n\) even?
-
Is \(10mn +7\) odd?
2.
Prove there are integers \(m\) and \(n\) such that \(m>1\) and \(n>1\) and \(\frac{1}{n}+\frac{1}{m}\) is an integer.
3.
4.
Disprove by giving a counterexample: For all real numbers \(a\) and \(b\text{,}\) if \(a<b\) then \(a^2<b^2\text{.}\)
5.
Disprove by giving a counterexample: For all integers, \(m\) and \(n\text{,}\) if \(2m+n\) is odd then \(m\) and \(n\) are both odd.
6.
Find the mistakes in the following “proof.”
“Proof”: For \(k=2\text{,}\) \(k^2+2k+1=2^2+2\cdot 2 +1=9\text{.}\) But \(9=3\cdot 3\text{,}\) and so 9 is composite. Hence the theorem is true.
7.
Find the mistakes in the following “proof.”
Theorem: The difference between any odd integer and any even integer is odd.
“Proof”: Suppose \(n\) is an odd integer, and \(m\) is an even integer. By definition of odd, \(n=2k+1\) where \(k\) is an integer, and by definition of even \(m=2k\) where \(k\) is an integer. Then
\begin{equation*}
n-m=2k+1-2k=1.
\end{equation*}
Since 1 is odd the difference between an odd integer and and even integer is odd.
8.
Prove the difference of any even integer minus any odd integer is odd.
9.
Prove the sum of any two odd integers is even.
10.
Prove the following statement is false: There exists an integer \(n\) such that \(6n^2+27\) is prime.
11.
For the following problems determine if they are true of false. Prove the true statements and provide counterexamples for the false statements.
-
The product of any even integer and any integer is even.
You have attempted of activities on this page.
