8.13 Quantifiers
1.\(\forall\): universal quantifier
Just a counterexample can invalidate the statement.
2.\(\exists\): existential quantifier
Only one of them is enough to prove existence.
3.Equivalences
a.
b.
c.
Note
(a) (b) and (c) can be proved by contradiction easily.
Self study
-
Why cannot use contrapositive?
Because this will cause a new equivalence which is not helpful to prove it
Example
-
to explain (c): \(p(x)="x^{2}+1>0"\ \ q(x)="x-2>0"\)
-
Consider the statement: \(r=" \text{Some rectangles are squares~有些矩形是正方形}"\)
Proposition: \(r=\exists x~p(x)\) (True), \(\neg r=\forall x~(\neg p(x))\) (False)
In English: All rectangles are not squares
4.Methods of proof
a. Direct proof
First version
If \(p\) is true and \(p\Rightarrow q\) is true. Then, \(q\) has to be true
Example
We use polynomials
\(\begin{aligned}&f(x)=\sum_{k=0}^na_kx^k=a_0+a_1x+a_2x^2+...+a_nx^n\\&\end{aligned}\)
Consider a polynomial \(r\in\mathbb{R}\)
\(\begin{aligned}&p\left(r\right)="f\left(r\right)=0"\\&q\left(r\right)="f\left(x\right)"="\left(x-r\right)h\left(x\right)"\end{aligned}\)
We know that \(p(r)\Rightarrow q(r).\forall r\in\mathbb{R}\)
Now consider \(\begin{aligned}&f(x)=x^4-3x^3+x^2+1\\&f(1)=0\end{aligned}\)
Then since, \(p(1)\) is true, \(p(r)\Rightarrow q(r)\)
We conclude that \(f(x)\) can be factored
\(x^4-3x^3+x^2+1=(x-1)h(x)\)
Second version
If \(p\Rightarrow q\) is true and \(q\) is false, then \(p\) has to be false
Example
We use something about continuous functions and derivatives (导数)
$\begin{aligned} &p(f)=~f~\text{is differentiable} \ &p'(f)=~f'~\text{exists} \ &q(f)=~f~\text{is continuous} \end{aligned} $
Domain: All possible functions
We know that \(p(f)\Rightarrow q(f)\) for all functions \(f\).
Now consider
\(f(x)=\begin{cases}1 & (x\geq0)\\ -1 & (x<0)\end{cases}\)
Since \(f\) is not continuous (\(q(f)\) is false), then the derivatives \(f' (0)\) does not exist
Self study
-
Continuous function: If \(\lim_{{x \to a}} f(x) = f(a)\), then the function is continuous at the point \(a\)
If function is continuous at every point within an interval(区间), a function is continuous over that interval.
-
So why that function is not continuous
Prove it by the definition of continuous function: we need to prove \(\lim_{{x \to 0^-}} f(x)=\lim_{{x \to 0^+}} f(x)\), then we can calculate the limit
Since \(~~~\lim_{{x \to 0^-}} f(x)=-1~~~~and ~~~~~~~\lim_{{x \to 0^+}} f(x)=1\)
So the limit does not exist
Hence it is not continuous.
-
Differentiable function: If \(f'(a) = \lim_{{h \to 0}} \frac{f(a+h) - f(a)}{h}\) exists, then the function is differentiable at the point \(a\).
If function is differentiable at every point within an interval(区间), a function is differentiable over that interval.
-
Theorem:
\(\text{If } f \text{ is differentiable at } a, \text{ then } f \text{ is continuous at } a\)Proof:
\(\begin{aligned}&\lim_{x \to a} f(x) = \lim_{x \to a} \left( \left( f(x) - f(a) \right) + f(a) \right)&\end{aligned}\)
\(\begin{aligned}&= \lim_{x \to a} \left( \frac{f(x) - f(a)}{x - a} \cdot (x - a) + f(a) \right)&\end{aligned}\)
\(\begin{aligned}&= \lim_{x \to a} \frac{f(x) - f(a)}{x - a} \cdot \lim_{x \to a} (x - a) + \lim_{x \to a} f(a)&\end{aligned}\) \(= f'(a) \cdot (a - a) + f(a)\)
\(= 0 + f(a) = f(a)\)
-
So, while all differentiable functions are continuous, not all continuous functions are differentiable.
For example, the function \( $f(x) = |x|$ \) is continuous at \( x = 0 \), but it is not differentiable at \( x = 0 \) because the slope from the left does not equal the slope from the right (the function has a sharp corner at \( x = 0 \)).
So, the differentiability contain continuity and smooth(no sharp)
Summary on direct proof
| we know | we conclude |
|---|---|
| \(p \Rightarrow q\) true, \(p\) is true | \(q\) is true |
| \(p \Rightarrow q\) true, \(q\) is false | \(p\) is false |
b. Proof by contra
Proof by contrapositive(逆否命题证明)
Sometimes we need to prove \(p \Rightarrow q\)
One possible approach: Proof by contrapositive(逆否命题证明)
we use the equivalence \(p \Rightarrow q\) \(\equiv\) \(\neg q \Rightarrow \neg p\)
Example
\(\begin{aligned}&\mathrm{p(m)="m^2~is~odd"}\\&\mathrm{q(m)="m~is~odd"~}\end{aligned}\)
Prove that \(\mathrm{p(m)\Rightarrow q(m)}\). \(\forall m\in\mathbb{N}\)
We will prove \(\neg q(m) \Rightarrow \neg p(m)\)
\(m\) is even \(\Rightarrow\) \(m^2\) is even
Proof:
Assume that \(m\) is even. Then there exists an integer, \(k \in\mathbb{N}\)
Such that \(m=2k\)
Then, \(m^2 = 4k^2 = 2(2k^2)\)
Then, \(m^2\) is even
Proof by contradiction(反证法)
We want to prove that \(p\) is true
1.Assume that \(p\) is false
2.Get to a contradiction
3.Then the assumptions is false
4.Therefore \(p\) is true
Example
\(p=\sqrt{2}\) is a irrational number
\(\text{Equivalently: p= “}\sqrt{2}\notin\mathbb{Q}^{\prime\prime}\quad\text{(}\sqrt{2}\text{~is not a fraction of the form }\frac ab~~a,b\in\mathbb{N})\)
\(\text{Let's assume the exact opposite: Assume }\sqrt{2}\in\mathbb{Q}\)
\(\text{Let's~assume~that }~\sqrt{2}=\frac p q\mathrm{~with~}p,q~\in\mathbb{N}\mathrm{~~with~}(p:q)=1\) 最大公因数
(\(p\) and \(q\) with no common factors)互素
\(2 = \frac{p^{2}}{q^{2}}\)
\(\mathrm{Then~}2q^2=p^2\)
\(~\ \begin{aligned}p^2&\mathrm{~is~even}\\p&\mathrm{~is~even}\end{aligned} \Rightarrow p = 2k\)
Then \(2q^2=4k^2\)
\(q^{2}=2k^{2}\Rightarrow q^{2}\mathrm{~is~even}\) , Again q is even, And,(p:q)=2
Contradiction!!!
Corollary(Self study)
The Fundamental Theorem of Arithmetic can well solve the problem "prove xxx is irrational number", because the factors is unique
For example, \(2q^2=p^2\). We know that the factor of \(p^2\) must have at least one 2.
But due to the square, after \(p\) has the square, its exponent will double.
So, \(p^2\) must have evenly 2, then the right side must have evenly 2. And \(q^2\) is the same.
But the left side has another 2, so the left side has oddly 2.
It is a contradcition.