...

What Is Direct Proof?

Theory

Direct Proof

When you want to prove that

p \Rightarrow q

you must construct a proof of arguments that implies each other, such that

p \Rightarrow \dots \Rightarrow q

With a direct proof, you are supposed to make a logical chain of reasoning. You begin with $p$ . The claim $p$ needs to imply something, which then implies something else, and so on, until you end up implying $q$ , where $q$ is what you were supposed to prove from $p$ .

Example 1

Prove that if $a$ is an even number and $b$ is an odd number, then $a + b$ is an odd number:

When you are constructing a proof, it’s smart to make an expression you can work with. In this case you’ll need to make expressions for $a$ and $b$ . Since $a$ is an even number, it can be written as $a = 2 n$ , where $n$ is an integer. The number $b$ is an odd number, and can therefore be written as $b = 2 m + 1$ , where $m$ is an integer. You can insert these expressions into $a + b$ , and then you get

\begin{array}{l} a + b & = 2 n + (2 m + 1) \\ = 2 n + 2 m + 1 \\ = 2 (n + m) + 1 \\ = 2 k + 1, \end{array}

where $k = n + m$ is an integer, and so $a + b = 2 k + 1$ is an odd number.

Q.E.D

Example 2

You wish to prove that $p^{2} + p$ is always divisible by 2:

You know that all even numbers have a factor that is even. This is true because all even numbers can be divided by 2 given the definition of even numbers.

So now you see that you can factorize $p^{2} + p$ as $p (p + 1)$ . Then you see that $p$ and $p + 1$ are two integers that follow each other on the real number line (like 3 and 4, 4 and 5 $\dots$ ). You can now argue that no matter what $p$ is, one of the two factors has to be an even number, since every second integer on the real number line is even.

If $p = 2 k$ is an even number, then $p + 1 = 2 k + 1$ has to be an odd number. If $p = 2 k + 1$ is an odd number, then insert this expression for $p$ in $p + 1$ . Thus

\begin{array}{l} p + 1 & = 2 k + 1 + 1 \\ = 2 k + 2 \\ = 2 (k + 1) \\ = 2 l \end{array}

p + 1 = 2 k + 1 + 1 = 2 k + 2 = 2 (k + 1) = 2 l

where

l = k + 1

, must be an even number. Finally you know that since

p^{2} + p

always has a factor that is divisible by 2, then the expression itself must also be divisible by 2.

Mathematically, the proof looks like the one below, where the argument is constructed with implications:

\begin{matrix} p^{2} + p = p (p + 1) \\ ⇓ \\ p^{2} + p has a factor that \\ is an even number \\ ⇓ \\ p^{2} + p is even and \\ therefore divisible by 2 \end{matrix}

\begin{matrix} p^{2} + p = p (p + 1) \\ ⇓ \\ p^{2} + p has a factor that is an even number \\ ⇓ \\ p^{2} + p is even and is therefore divisible by 2 \end{matrix}

Q.E.D

Want to know more?Sign UpIt's free!

What Is the Difference Between Equivalence and Implication?

What Is Proof by Contrapositive?

Go back