MATH 302 Lecture 6

« previous | Wednesday, September 14, 2011 | next »

Proofs

Know terminology on pages 81 and 82

Main goal is to support the claim $p\to q$

Three main methods of proofs:

1. Direct: assume $p$ is true and show that $q$ is also true
2. Proof by Contraposition: assume $q$ is false and show that $p$ must be false.
3. Proof by Contradiction: assume that $\mathrm{\neg }(p\to q)$ ($p$ is true and $q$ is false) and try to arrive at a conflict (contradiction)

Examples

Definitions

• $n$ is even: $\mathrm{\exists }k(n=2k)$
• $n$ is odd: $\mathrm{\exists }k(n=2k+1)$
• $x$ is rational: $x=\frac{p}{q}$ for some $p,q\in \mathbb{\mathbb{Z}},q\ne 0$

Example 1

Proposition. If $n$ is odd, then $n^2$ is odd.

Proof. Let

$n$

be an odd integer. By definition, there exists some integer

$k$

such that

$n=2k+1$

. Then

$n^2=(2k+1{)}^2=4k^2+4k+1=2(2k^2+2k)+1$

, where

$2x^2$

is an integer. Hence by definition,

$n^2$

is odd.

Q.E.D.

Example 2

Proposition. If $n$ is even, then $3n+5$ is odd.

Proof. Let

$n$

be an even integer. By definition, for some integer

$k$

,

$3n=3(2k)=6k$

is an even number.

$6k+5=6k+4+1=2(3k+2)+1$

must be an odd number by definition, where

$3k+2$

is an integer. Therefore

$3n+5$

is odd for an even integer

$n$

.

Q.E.D.

Example 3

Proposition. If $a$ and $b$ are rational, then $a\cdot b$ is rational.

Proof. Let $a$ and $b$ be rational numbers. Then $a=\frac{p_a}{q_a}$ and $b=\frac{p_b}{q_b}$ for some integers $p_a$,

Example 4

Proposition. If $n^2$ is odd, then $n$ is odd.

Proof by contraposition. Let

$n$

be even. Then

$n=2k$

for some integer

$k$

, so

$n^2=4k^2=2(2k^2)$

, which is even.

Q.E.D.

Example 5

Proposition. If $3n+5$ is odd, then $n$ is even.

Proof by contraposition. Assume $n$ is odd. Then $n=2x+1$ for some integer $k$.

$\begin{array}{rl}3n+5& =3(2k+1)+5\\ & =6k+8\\ & =2(3k+4)\end{array}$

Hence

$3n+5$

is even.

Q.E.D.

Example 6

Proposition. $\sqrt{2}$ is irrational

Proof by contradiction. Assume

$\sqrt{2}$

is rational. Therefore,

$\sqrt{2}=\frac{p}{q}$

for some integers

$p$

and

$q$

, where

$q\ne 0$

. We will assume without loss of generality that

$p$

and

$q$

have no common factors (are coprime). Thus we have

$\frac{p^2}{q^2}=2$

, giving

$p^2=2q^2.<math>p^2$

is even, so

$p$

must be even:

$p=2k$

for some integer

$k$

.

$p^2=(2k{)}^2=4k^2=2q^2$

, then

$2k^2=q^2$

, so

$q^2$

—and therefore

$q$

—must be even. Since

$p$

and

$q$

are even, they would have a common factor of 2, which contradicts our generality that

$p$

and

$q$

are coprime.

Q.E.D.

Example 7

Proposition. If $x>0$, then $x+\frac{1}{x}\ge 2$

Scratch sheet. (Working backwards) $x^2+1\ge 2x$, so $x^2-2x+1=(x-1{)}^2\ge 2x$, which is true.

Proof. Assume

$x>0$

. We also have

$(x-1{)}^2\ge 0$

. Then

$x^2-2x+1\ge 0$

by expansion, and can be simplified to

$x+\frac{1}{x}\ge 2$

Q.E.D.

Methods and Strategies of Proofs

proof by exhaustion (proof by cases)

given a finite number of possibilities, just check the proof's validity by checking all of the possibilities

existence proofs

construct an example of a case that satisfies the proposition

uniqueness proofs