Note Sheet Quiz 4 (Proofs)

Definitions: Even

$De{f}^n$: An integer $n$ is said to be even if there exists an integer $k$ such that $n=2k$

Link to original

Odd

$De{f}^n$: An integer $n$ is said to be odd if there exists an integer $k$ such that $n=2k+1$

Link to original

Rational

$De{f}^n$: A real number $r$ is rational if there exists integers $p$ and $q$, where $q\ne 0$, $r=\frac{p}{q}$

Link to original

Absolute Value

$De{f}^n$: $|a|$ is the absolute value of $a$ and it equals $a$ when $a\ge 0$, and equals $-a$ when $a\le 0$.

Link to original

• Proof By Cases

  Definition

  $(p_1\vee p_2\vee \dots \vee p_n)\to q\equiv (p_1\to q)\wedge (p_2\to q)\wedge \dots (p_n\to q)$

  the original conditional statement wtih a hypothesis made up of a disjunction of propositions $p_1,p_2,\dots ,p_n$ can be proved by proving each of the $n$ conditional statements $p_i\to q$ individually.

  To prove $p\to q$, we can find $p_1\vee p_2\vee \dots \vee p_n\equiv p$ and then individually prove every case.

  Link to original

• Direct Proof

  Definition

  A direct proof of a conditional statement $p\to q$ is constructed by

  • Assume $p$ is true
  • Use rules of inferences, axioms, and logical (basic) equivalences to show that $q$ must follow

  Note: In some cases, you may want to use direct proof by contraposition

  Link to original

• Direct Proof by Contradiction

  $p\to q\equiv \neg q\to \neg p$ If we can prove that the negation

  Link to original

• Proof by Contradiction

  Definition

  For any statement $p$, either it is true or false. There is nothing in the middle.

  So, if i want to prove $p$, I can start by assuming $\neg p$ is true.

  Suppose from that I derive $F$ or any contradiction.

  Basically, proof by contradiction relies on you making an assumption (a negation of part of the statement) and then proving that the statement is false when that assumption is made, then you can say that the original is true.

  Link to original

• Uniqueness Proof

  Definition

  Recall what uniqueness looks like in terms of quantifiers:

  $(\exists x|x\in D:P(x)\wedge (\forall y|y\in D:P(y)\to y=x))$

  • Some theorems assert the existence of a unique element (aka only one element with a certain property)

  Uniqueness Proofs have two parts:

  1. Existence: We show that such an element $x$ with the desired property exists
  2. Uniqueness: We show that if $x$ and $y$ both have the property, then $x=y$ because its unique, so only one possible element.

  Link to original

• Vacuous Proof

  If we can show that $p$ is always false, then $p\to q$ is always true.

  Link to original

• Trivial Proof

  If we can show that $q$ is always true then we can say $p\to q$ is true.

  Link to original

• Existence Proof

  Definition

  • Many theorems are assertions that some object or element of some property/type is true
  • These theorems have the form $(\exists x|x\in D:P(x)).$
  • Proof of this type of theorem is called an existence proof
  • There are two ways theorems are written for this type:
    • Constructive: Find an element $a$, where $a\in D$ for which $P(a)$ is true. $a$ is called a witness
    • Nonconstructive: Do not look for a witness, but show that $(\exists x|x\in D:P(x))$ is true another way

  Link to original