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\rightarrow 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 $\neg (p\rightarrow q)$ ($p$ is true and $q$ is false) and try to arrive at a conflict (contradiction)

Examples

Definitions

• $n$ is even: $\exists k(n=2k)$
• $n$ is odd: $\exists k(n=2k+1)$
• $x$ is rational: $x={\frac {p}{q}}$ for some $p,q\in \mathbb {Z} ,\ q\neq 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{aligned}3n+5&=3(2k+1)+5\\&=6k+8\\&=2(3k+4)\end{aligned}}$

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\neq 0$. We will assume without loss of generality that $p$ and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} have no common factors (are coprime). Thus we have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{p^2}{q^2} = 2} , giving Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p^2=2q^2. <math>p^2} is even, so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} must be even: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p=2k} for some integer Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} . Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p^2 = (2k)^2 = 4k^2 = 2q^2} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2k^2=q^2} , so $q^{2}$—and therefore Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} —must be even. Since $p$ and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} are even, they would have a common factor of 2, which contradicts our generality that Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} and Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} are coprime.

Q.E.D.

Example 7

Proposition. If Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x > 0} , then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x + \frac{1}{x} \ge 2}

Scratch sheet. (Working backwards) Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^2+1 \ge 2x} , so Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^2-2x+1 = (x-1)^2 \ge 2x} , which is true.

Proof. Assume Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x>0} . We also have Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (x-1)^2 \ge 0} . Then Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x^2-2x+1 \ge 0} by expansion, and can be simplified to Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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