Week 2 Summary Continued
Two Classic Results
These are classical proofs as they we’re proven by the Ancient Greeks. They are both proofs by contradiction.
Use proof by contradiction to show that there is no greatest prime number.
- 2, as the smallest prime number, is known as $P_1$. All following prime numbers are numbered sequentially.
- For each prime number that is identified any multiples are removed from the endless list of integers.
- This is continued for $P_2=3$ where all multiples of 3 are removed.
How do we know that at some point in the list all numbers are eliminated?
Proof
Assume for a proof by contradiction that there is a greatest prime number $P_n$.
Then $P_1, P_2, \ldots , P_n$ are all prime numbers.
Consider $P=P_1\times P_2\times \ldots \times P_{n+1}$
Consider cases:
Case 1
$P=P_1\times P_2\times \ldots \times P_{n+1}$ is prime. As $P>P_n$ we derive a contradiction.
Case 2
$P$ is not a prime. Then $P$ has a divisor (all numbers can be expressed as a product of primes).
Then $P$ has a prime factor.
So one of $P_1, P_2, \ldots , P_n$ must divide $P$. This number can be called $P_i$.
\[\begin{aligned} P&=P_i\times Q,\ Q\neq 1\\ P_1\times\ldots P_{n+1}&=P_i\times Q\\ P_1\times\ldots P_{i-1} \times P_i \times P_{i+1} \times\ldots P_{n+1}&=P_i\times Q\\ P_i \times Q - P_i (P_1 \times\ldots\times P_{i-1} \times P_{i+1} \times P_n)&=1\\ P_i(Q-P_1 \times\ldots\times P_{i-1} \times P_{i+1} \times\ldots\times P_n) &= 1 \end{aligned}\]This is a contradiction as one is not a product of two distinct integers.
As a result the statement that there is no greatest prime number.
Prove that $\sqrt{2}$ is not a Rational Number
Assume for a proof by contradiction that $\sqrt{2}$ is rational.
Then there exist integers $m,n$ such that $\sqrt{2}=\frac{m}{n}, n\neq 0, \frac{m}{n}$ is not reducible.
Then $(\sqrt{2})^2=(\frac{m}{n})^2$. Then $2=\frac{m^2}{n^2}$.
Then $2n^2=m^2$. So $m^2$ is even.
We already know that $m$ must be even.
By definition of even $m=2k$ for some integer $k$.
$2n^2=m^2, m=2k$
$2m^2=(2k)^2$. Then $2n^2=4k^2$. Then $n^2=2k^2$, so $n^2$ is even.
Then $n$ is even.
So we derive a contradiction as n and m have a common factor of $2$. As it is reducible it doesn’t follow the rule.
Indirect Proof of Existential Statements
Prove that there exist irrational numbers $q$ and $r$ such that $q^r$ is rational.
Consider Cases:
Case 1
If $\sqrt{2}^{\sqrt{2}}$ is a rational number then we are done and $q=\sqrt2, r=\sqrt2$.
Case 2
$\sqrt{2}^{\sqrt{2}}$ is not rational. Then:
$q=\sqrt{2}^{\sqrt{2}}, r=\sqrt2$
$q^r = (\sqrt2^{\sqrt2})^{\sqrt2}=\sqrt2^{\sqrt2\sqrt2}=\sqrt2^2=2$