0.5: Proof Templates

From  DR. THI DINH'S PROOF WRITING HANDBOOK THIS BIBLE:

 

In the beginning...

Let $P$ and $Q$ be statement variables. When needed, suppose that P = P(x) depends on a variable x. The symbol "$\forall$" means "for all" or "for any". The symbol $\exists$ means "there exists". 

 

Type of statement	What must we do to prove that it is true
(1) If $P$, then $Q$ (2) $\forall P$, $Q$	Suppose that $P$ is true. Prove that $Q$ is true.
(3) $\exists x P(x)$ such that $Q$	Choose $x$ so that $P(x)$ is true. Prove that $Q$ is true. Note: You need not explain how you find $x$.

The first (and only) commandment

To prove that a statement is false, thou shalt write out the negation of the statement and prove that.

 

 

To prove injective relationship (ie prove one-to-one)

 

YES If  $f(x_1) = f(x_2)$ then you need to prove $x_1=x_2$.

Let $A$ be a set.   Let $x_1,x_2 \in A$ such that $f(x_1)=f(x_2)$.

    ⠇

Show $x_1=x_2$.

NO then you need to provide one counterexample where $x_1 \ne x_2$ when $f(x_1) = f(x_2)$.

 

 

Is there a surjective relationship (i.e. prove onto)?

YES Note we are starting from $f: A \rightarrow B$. Thus $f(A)\subseteq B$ by definition.

Let $A$ and $B$ be sets where $A$ is onto $B$ if and only if $f(A) \subseteq B$ and $B \subseteq f(A)$.

By definition, $f(A) \subseteq B$.  Next show $B \subseteq f(A)$.

Let $x \in B$.

       ⠇

Show $x \in f(A)$.

Conclude with:  Since $f(A) \subseteq B$ and $B \subseteq f(A)$  therefore $f$ is onto.◻

NO then need to find a counterexample where $b \in B$, but there is no $a \in A$ whereby $f(a)=b$.

 

• Reflexive, Symmetric, Anti Symmetric Transitive Property Proofs 

Need a non-empty set $A$ and a relation $R$.

• Reflexive

Let $a \in A$.  ← Starting point

       ⠇

Show $aRa$ ← Ending point

• Symmetric

Let $a, b \in A$ s.t. $aRb$.

       ⠇

Show $bRa$

• Antisymmetric

Let $a,b \in A$ s.t. $aRb$ and $bRa$

       ⠇

Show $a=b$.

• Transitive

Let $a,b,c \in A$ s.t. $aRb$ and $bRa$.

       ⠇

Show $aRc$.