10.21 Proof
Axioms are assumed to be true and (theorem, proposition, lamma, corollary,...) need a proof.
- Each theorem should be deduced the axioms.
- In a proof, we assume previous knowledge.
Two kind of Proof
Theorem: \(P\)
Direct Proof
We produce a chain of statement with end \(P\).
Each statement is the chain should follow from the predecessors and from assumed knowledge.
Example
\((-1)(-1)=1\)
Proof
We know \(1+(-1)=0\) by definition of \(-1\)
We multiply by \(-1\) and get \((-1)(1+(-1))=(-1)\cdot 0=0\)
Then \(-1+(-1)(-1)=0\)
We add \(1\) to both sides and obtain \(1+(-1)+(-1)(-1)=1+0\)
Then \(0+(-1)(-1)=1\), then \((-1)(-1)=1\)
Proof by Contradiction
We assumed that \(P\) is false and need to incorporate \(\neg P\) to sour previous knowledge.
We now apply the direct proof to get \(Q\wedge\neg Q\) for some proposition \(Q\).
This is a contradiction.
Therefore, \(P\) must be true.
Example
\(1>0\)
Proof
Assume \(1\leq 0\), by axiom \(1\neq 0\)
Thus by trichotomy, \(1<0\)
We apply the sign rules: \(1<0\) and \(1<0\) \(\Rightarrow\) \(1\cdot 1>0\cdot 1\Rightarrow 1>0\)
We obtain \(1>0\) and \(1<0\) which is a contradiction,
Therefore \(1>0\)
Other form proof
Proofs for \(P\Rightarrow Q\)
Direct method
| \(P\) | \(Q\) | \(P\Rightarrow Q\) |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Since if \(P\) is false, then \(P\Rightarrow Q\) must be true.
We only need to prove that \(P\Rightarrow Q\) is true when \(P\) is true. In that case we need to show that \(Q\) is also true.
Proof
Assume \(P\) is true
Then ..... to prove \(Q\) is true (use previous knowledge)
Hence \(Q\) is true
Example
Let \(x,y\in \R\), if \(x<-4\) and \(y>2\) (\(P(x,y)\)), then the distance from \((x,y)\) to \((1,-2)\) (\(Q(x,y)\)) is at least \(6\).
The question is the form like \(P\Rightarrow Q\), then we can apply the above method.
\(Q(x,y)=\sqrt{\left(x-1\right)^2+\left(y+2\right)^2}\geq6\equiv\left(x-1\right)^2+\left(y+2\right)^2\geq36\)
Proof
Assume \(x<-4\) and \(y>2\) is true.
Then \(x-1<-5\) and \(y+2>4\) \(\Rightarrow\) \((x-1)^2>25\) and \((y+2)^2>16\)
Then \((x-1)^2+\) \((y+2)^2>41> 36\)
Hence \(\sqrt{\left(x-1\right)^2+\left(y+2\right)^2}>\sqrt{41}>6\)
Then the distance from \((x,y)\) to \((1,-2)\) is at least \(6\).
Proof by contrapositive
Recall: \(P\Rightarrow Q\equiv\neg Q\Rightarrow\neg P\), thus we can prove \(P\Rightarrow Q\) by proving \(\neg Q\Rightarrow \neg P\) (direct method)
Proof
Assume that \(Q\) is false, then prove \(P\) is false (use previous knowledge)
Hence \(P\) is not true
Example
Let \(n\in \N\). If \(m^2\) is even then \(m\) is even.
The form is like \(P\Rightarrow Q\).
Instead of proving \(P\Rightarrow Q\), we try to use contrapositive.
Proof
Assume \(m\) is odd, then we need to prove \(m^2\) is odd
Since \(m\) is odd, so \(m=2k+1\) for some \(k\in \Z\)
Now, \(m^2=(2k+1)^2=4k^2+4k+1=2\left(2k^2+2k\right)+1\)
Since \(2k^2+2k\) is an integer, we get that \(m^2\) is odd.
Thus we complete the proof.
Proofs for \(P\wedge Q\)
Proof: We first prove \(P\)...
We now prove \(Q\)....... (use \(P\) as part of previous knowledge)
Proofs for \(P\vee Q\)
Recall \(P\vee Q\equiv \neg P\Rightarrow Q\) (can be proved by truth table)
Proof: Assume that \(P\) is false.
Then we prove \(Q\)......... (use \(\neg P\) as a part of previous knowledge)
Proof for \(P\vee Q\Rightarrow R\)
We use \(P\vee Q\Rightarrow R\equiv\left(P\Rightarrow R\right)\wedge\left(Q\Rightarrow R\right)\)
Proof: We first prove \(P\Rightarrow R\) .....
We now prove \(Q\Rightarrow R\) ........
Example
Let \(M\in \Z\). Then \(m(m+1)\) is even.
The question is equivalent to: If \(m\) is even or \(m\) is odd, then \(m(m+1)\) is even.
Proof
We first prove that if \(m\) is even then \(m(m+1)\) is even.
If \(m\) is even, then \(m=2k\) for some \(k\in\Z\).
Then \(m(m+1)=2k(2k+1)=2(k(2k+1))\) is even
If \(m\) is odd, then \(m=2k+1\) for some \(k\in \Z\)
Then \(m(m+1)=(2k+1)(2k+2)=2(2k+1)(k+1)\) is even
Thus \(m(m+1)\) is even for \(m\in\Z\)
Proof for \(P\Leftrightarrow Q\)
Recall \(P\Leftrightarrow Q\equiv\left(P\Rightarrow Q\right)\wedge\left(Q\Rightarrow P\right)\)
Proof: We first prove \(P\Rightarrow Q\) ...
Now we prove \(Q\Rightarrow P\)
Proof 2: \(P\) iff \(P_2\) iff \(P_3\) iff ..... iff \(P_n=Q\).
Example
Given a right triangle with hypotenuse \(c\) if and only if \(c^2=a^2+b^2\)
We use \(c^2=a^2+b^2-2ab\cos\theta\)
Proof: The triangle is a right triangle with hypothenuse \(c\) iff \(\theta=\frac{\pi}{2}\) iff \(cos\theta =0\) iff \(c^2=a^2+b^2\)
Proofs for \(\exists xP(x)\)
By construction: We exhibit some \(a\) in the universe such that \(P(a)\) is true.
Existential: We show that there exists some \(a\) for which \(P(a)\) is true, but we don't tell what \(a\) is
By contradiction: Assume that \((\forall x)\neg P(x)\) or assume that \(P(x)\) is false for all \(x\in U\)
Example
-
\(\exists n \in \N\) such that \(n^2-3n+43\) is composed.
Proof
Let \(n=43\). Then for this \(n\), we have \(43^2-3\cdot 43+43=43\cdot 41\)
-
\(\exists x\in (0,1)\) such that \(x^2+x-1=0\)
Proof
Let \(f(x)=x^2+x-1\). This function is continuous and satisfies \(f(0)=-1\) and \(f(1)=1\)
By the Intermediate Value Theorem, there is some \(\xi\in(0,1)\) such that \(f(\xi)=0\)
Therefore \(\xi^3+\xi-1=0\)
-
Theorem: 1. \(\neg ((\exists x)P(x))\equiv (\forall x)(\neg P(x)\)
Proof
Let \(U\) be a universe for \(P(x)\)
\(\neg((\exists x)P(x))\) is true iff \((\exists x)P(x)\) is false iff the true set for \(P(x)\) is empty iff \(P(x)\) is false for any \(x\in U\) iff \(\neg P(x)\) is true for any \(x\in U\equiv (\forall x)\neg P(x)\) is true.
Theorem: 2. \(\neg ((\forall x)P(x))\equiv (\exists x)(\neg P(x))\)
Proof
\(\neg((\forall x)P(x))\) is true iff \((\forall x)P(x)\) is false iff there is a \(x\) such that \(P(x)\) is false iff \(\exists x \neg P(x)\) is true
Proof for \((\forall x)P(x)\)
Direct method: We prove for any \(x\in U\), \(P(x)\) holds
By contradiction: Suppose \((\exists x)\neg P(x)\) and get a contradiction
Definition (counter examples)
How to show that \((\forall x)P(x)\) is false?
\((\forall x)P(x)\) is false iff \(\neg(\forall x)P(x)\) is true iff \((\exists x)\neg P(x)\) is true iff there is some \(a\) such that \(P(a)\) is false.
Such element is called a counter example(反例).