Direct Proof and Counterexample

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

An integer,

n,

is even if it has the form

n = 2 k

for some

k \in Z .

🔗

Definition 4.1.2.

An integer

n,

is odd if it has the form

n = 2 k + 1

for some

k \in Z .

🔗

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.

- 5 = 2 (- 3) + 1

- 3 \in Z .

Is 0 even or odd?

Answer 2.

0 = 2 (0)

0 \in Z .

Let

a, b \in Z .

6 a^{2} b

even or odd?

Answer 3.

6 a^{2} b = 2 (3 a^{2} b)

3 a^{2} b \in Z .

6 a^{2} b

Let

a, b \in Z .

20 a - 6 b + 1

even or odd?

Answer 4.

20 a - 6 b + 1 = 2 (10 a - 3 b) + 1

10 a - 3 b \in Z .

20 a - 6 b + 1

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)

12 a b^{3}

🔗

(b)

3 a b

🔗

(c)

10 b^{2} - 4 a b + 1

🔗

(d)

4 b + 3

🔗

(e)

5 a + 3 b

🔗

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,

is prime if

n > 1

and, for all positive integers

r, s,

n = r s

then

r = 1

s = 1 .

🔗

Definition 4.1.5.

An integer,

n,

is composite if

n > 1

and

n = r s

for some positive integers

r, s

with

r \neq 1

and

s \neq 1 .

🔗

Example 4.1.6. Prime or Composite.

Is 1 prime?

Answer 1.

n > 1 .

Is 1 composite?

Answer 2.

n > 1 .

Is 121 prime?

Answer 3.

121 = (11) (11) .

Let

a \in Z .

3 a

composite?

Answer 4.

a = 1

a > 1

3 a

Activity 4.1.2.

Consider the statement “for all positive integers

r

and

s,

n = r s

then

r = 1

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 .$
Show $x \in D$ and $Q (x)$ is true.

🔗

This type of proof is called a constructive proof of existence

🔗

Example 4.1.7. Existential Proof.

Prove

\exists n \in Z

such that

20 = 2 n .

Proof.

Let

n = 10 .

Then

n \in Z

and

2 (10) = 20 .

Example 4.1.8. Another Existential Proof.

Let

n \in Z .

Prove

\exists m \in Z

such that

m > n .

Proof.

Let

m = n + 1 .

Then

n + 1 \in Z

since

n \in Z

and

n + 1 > n .

Activity 4.1.3.

Let

r, s \in Z .

Prove there exists

k \in Z

such that

3 k = 12 r + 15 s .

🔗

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) \to Q (x)

🔗

Find the negation of the statement: $\exists x \in D, P (x) \land \sim Q (x) .$
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 .$
Show $x \in D,$ $P (x)$ is true and $Q (x)$ is false.

🔗

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,

is odd.

Let

p = 2 .

Then

2

is prime and

2

is not odd.

Activity 4.1.4.

Give a counterexample to show the following statement is false: For all

a, b \in R

a^{2} = b^{2}

then

a = b .

🔗

One of the most common mathematical statements is the universal conditional. We will see several techniques for proving

\forall x \in D, P (x) \to Q (x) .

The first method, method of exhaustion, is very limited, but worth mentioning.

🔗

Method of Exhaustion.

To prove

\forall x \in D, P (x) \to Q (x),

where

D

is a finite set:

🔗

For each specific $a \in D$ where $P (a)$ is true, show $Q (a)$ is true.

🔗

Example 4.1.10. Method of Exaustion.

Prove for all

n \in Z,

n

is even and

4 \leq n \leq 16,

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 .

This is the set

{4, 6, 8, 10, 12, 14, 16} .

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 .

The method of exhaustion only works if we can show the statement for every

x \in D .

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) \to Q (x) :

🔗

Let $x \in D$ (make sure this is a variable, or generic, $x,$ not a specific value).
Assume $P (x)$ is true.
Show $Q (x)$ is true.

🔗

Example 4.1.11. Direct Proof.

Prove for all

x \in Z,

x

is even, then

x + 1

is odd.

Proof.

Let

x

be even. Then by definition,

x = 2 k

for some

k \in Z .

Then

x + 1 = 2 k + 1

where

k \in Z .

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:

Prove for all

a, b \in Z

a

and

b

are even, then

a + b

is even.

Proof.

Let

a, b

be even. Then by definition,

a = 2 k

for some

k \in Z

and

b = 2 j

for some

j \in Z .

(Note, we cannot use

k

for both

a

and

b

as they likely are two different numbers.) Then

a + b = 2 k + 2 j = 2 (k + j)

where

k + j \in Z .

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,$ 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.

Prove or disprove there exists a positive integer

n

such that

n^{2} + 3 n + 2

is prime.

Since we need to try to decide if the statement is true or false, first try some examples.

Answer 1.

\begin{matrix} n = 1; n^{2} + 3 n + 2 = 6; not prime \\ n = 5; n^{2} + 3 n + 2 = 42; not prime \\ n = 8; n^{2} + 3 n + 2 = 90; not prime \end{matrix}

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.

Answer 2.

For all positive integers