Proof Machine

Arun Ram
Department of Mathematics and Statistics
University of Melbourne
Parkville, VIC 3010 Australia
aram@unimelb.edu.au

A talk at University of Melbourne
7 March 2014

toggle mathjax on/off       medic

Assume the ifs

To show: the thens

Proof type II:    To show: If   A   then   B  .

The next lines are

• Assume   A  .
• To show:   B  .

Let $f:S\to T$ be a function. Show that $f$ is invertible $⟺\text{<em>if and only if</em>}\forall \epsilon >0\exists \delta >0\ni x\in ℝ\&\left|x\right|<\delta \Rightarrow |e^x-1|<\epsilon$ $f$ is a bijection.

		Proof.
	To show: (a) If $f$ is invertible then $f$ is a bijection. $\phantom{\text{To show:}}$ (b) If $f$ is a bijection then $f$ is invertible. $\phantom{T}$ (a) Assume $f$ is invertible. $\phantom{\text{(a)}}$ To show: $f$ is a bijection. $\phantom{T}$ $\phantom{\text{(a)}}$ We know: There exists $g:T\to S$ such that $$g\circ f={\mathrm{id}}_S\text{and}f\circ g={\mathrm{id}}_T.$$ $\phantom{T}$ $\phantom{\text{(a)}}$ To show: (aa) $f$ is injective. $\phantom{\text{(a)}}$ $\phantom{\text{To show:}}$ (ab) $f$ is surjective. $\phantom{T}$ $\phantom{\text{(a)}}$ (aa) To show: If $s_1,s_2\in S$ and $f\left(s_1\right)=f\left(s_2\right)$ then $s_1=s_2$. $\phantom{T}$ $\phantom{\text{(a)}}$ $\phantom{\text{(aa)}}$ Assume $s_1,s_2\in S$ and $f\left(s_1\right)=f\left(s_2\right)$. $\phantom{\text{(a)}}$ $\phantom{\text{(aa)}}$ To show: $s_1=s_2$.               (proof type I) $\phantom{T}$ $$s_1={\mathrm{id}}_S\left(s_1\right)=g\left(f\right(s_1\left)\right)=g\left(f\right(s_2\left)\right)={\mathrm{id}}_S\left(s_2\right)=s_2.$$ $\phantom{\text{(a)}}$ So $f$ is injective. $\phantom{T}$ $\phantom{\text{(a)}}$ (ab) To show: $f$ is surjective. $\phantom{T}$ $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ To show: If $t\in T$ then there exists $s\in S$ such that $f\left(s\right)=t$. $\phantom{T}$ $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ Assume $t\in T$. $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ To show: There exists $s\in S$ such that $f\left(s\right)=t$.               (proof type III) $\phantom{T}$ $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ Define $s=g\left(t\right)$. $\phantom{\text{(a)}}$ $\phantom{\text{(ab)}}$ To show: $f\left(s\right)=t$. $\phantom{T}$ $$f\left(s\right)=f\left(g\right(t\left)\right)={\mathrm{id}}_T\left(t\right)=t.$$ $\phantom{T}$ $\phantom{\text{(a)}}$ So $f$ is surjective. $\phantom{T}$ So $f$ is bijective. $\phantom{T}$ $\phantom{T}$ (b) To sh.... . . . . $\square$

Proof type I:   LHS = RHS.

The next lines are

  LHS = ⋯ = ⋯ = ⋯ = ⋯ = $\text{blah}$   .

  RHS = ⋯ = ⋯ = ⋯ = ⋯ = $\text{blah}\text{EXACTLY THE SAME blah}$   .

Prove that $e^{x+y}=e^x{e}^y$.

		Proof.
	$$\begin{array}{rcl}{e}^{x+y}& =& 1+(x+y)+\frac{(x+y{)}^2}{2}+\frac{(x+y{)}^3}{3!}+\cdots \\ \phantom{T}\\ & =& \begin{array}{c}1+\\ x+y+\\ \frac{x^2}{2}+\frac{2xy}{2}+\frac{y^2}{2}+\\ \frac{x^3}{3\cdot 2}+\frac{3x^{2}y}{3\cdot 2}+\frac{3x{y}^2}{3\cdot 2}+\frac{y^3}{3\cdot 2}+\\ ⋮\end{array}\\ \phantom{T}\\ & =& e^x+e^{x}y+e^x\frac{y^2}{2}+e^x\frac{y^3}{3\cdot 2}+\cdots \\ & =& e^x(1+y+\frac{y^2}{2}+\frac{y^3}{3!}+\cdots )\\ & =& e^x{e}^y.\end{array}$$ $\square$

Proof type III:   There exists   C   such that   D  .

The next lines are

• Define   C = xxx  .
• To show:   D  .

Prove that $e^x$ is continuous at 0.

		Proof.
	To show: $\underset{x\to 0}{\lim }{e}^x=e^0$. $\phantom{T}$ To show: $\underset{x\to 0}{\lim }{e}^x=1$. $\phantom{T}$ To show: If $\epsilon \in {ℝ}_{>0}$ then there exists $\delta \in {ℝ}_{>0}$ such that if $|x-0|<\delta$ then $|e^x-1|<\epsilon$. $\phantom{T}$ Assume $\epsilon \in {ℝ}_{>0}$. To show: There exists $\delta \in {ℝ}_{>0}$ such that if $|x-0|<\delta$ then $|e^x-1|<\epsilon$. $\phantom{T}$ Define $\delta =\mathrm{?????}\frac{1}{2}\min (\frac{\epsilon }{2},\frac{1}{2})$. To show: If $|x-0|<\delta$ then $|e^x-1|<\epsilon$. $\phantom{T}$ Assume $\left|x\right|<\delta$. To show: $|e^x-1|<\epsilon$. $\phantom{T}$ $$\begin{array}{ccc}|e^x-1|& =& |(1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots )-1|\\ & =& |x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots |\\ & =& \left|x\right|\cdot |1+\frac{x}{2!}+\frac{x^2}{3!}+\cdots |\\ & \le & \left|x\right|\cdot |1+\frac{\left|x\right|}{2!}+\frac{{\left|x\right|}^2}{3!}+\cdots |\\ & \le & \left|x\right|\cdot |1+\left|x\right|+{\left|x\right|}^2+\cdots |\\ & \le & \left|x\right|\cdot (1+\left|x\right|+{\left|x\right|}^2+\cdots )\\ & <& \delta \cdot (1+\delta +{\delta }^2+\cdots )\\ & \le & \delta \cdot \left(1+\frac{1}{2}+{\left(\frac{1}{2}\right)}^2+\cdots \right)\\ & \le & \delta \cdot 2\\ & \le & \frac{\epsilon }{2}\cdot 2\\ & =& \epsilon .\end{array}$$ $\square$

Special kinds of proofs

1. Proofs of uniqueness    ($x_1=x_2$)
   $\phantom{T}$
2. Contradiction or contrapositive
   $\phantom{T}$
3. Proofs of presentations (generators and relations)
   $\phantom{T}$
4. Proofs by induction (the definition of ${\mathbb{Z}}_{>0}$!!!)
   $\phantom{T}$
5. Proof by intimidation (the most common and least rigourous)
   $\phantom{T}$

Definitions

1. Format:
1. A noun is an   object   such that condition.
   
   
2. An adjective noun is a       such that condition.
   
   
3. A   condition   or   statement   can only be in the form

 

If   A   then   B  

or

There exists   C   such that   condition  .

 

2. Definitions can change!
   $\phantom{T}$
1. "What's the definition of a Schur function?!?!!"
   $\phantom{T}$
3. The challenge of taking on a definition.
   $\phantom{T}$
1. "They're made out of meat"

Extra stuff

1. How did you come to formalise Proof Machine?
   $\phantom{T}$
2. My notes page: Google "Arun Ram Notes"

top

The medical doctor

Before you try Lindelöf we need to an $\text{ERA}\text{Excellence in Research for Australia}$ assessment on your $\text{ARC}\text{Australian Research Council}$ results to check that there is no underlying $\text{NSF}\text{National Science Foundation}$ in the $\text{IMU}\text{International Mathematical Union}$. Believe me, ending up Lipschitz is no fun for anyone.