Proofs

Why do we exist, just to suffer?

Propositions

A proposition is a statement that is either true or false, ie:

• 6 < 10 (true)
• 4 - 1 = 7 (false)

This translates to: “for all $n$ in $\mathbb{N}$, $n^2 + n + 41$ is a prime number”

This translates to: “in $mathbb{N}$, there exists a number $n$ such that $n^2 + n + 41$ is a prime number”

Similarly, the following are not propositions:

• $n^2 + n + 41$ is a prime number
• $n^3 + 2n + 17$ is an even number
• $p$ is a prime number

These are predicates - statements whose truth depends on variables

Proposition logic

NOT

AND

OR

Implies

Equivalence

Axioms

Axioms are propositions that are assumed to be true
When something is being proven, a set of axioms used are declared.

Examples of axioms:

• Axioms of Euclidian geometry
• Peano axioms
• Axiomatic definition of real numbers
• Zermelo-Fraenkel set theory (with axiom of choice).

Ideally, axioms should be consistent (we cannot prove that false is true) and complete (every true proposition can be proved).
By Gödel’s incompleteness theorems, we cannot have both

Logical Deductions

If statements $P$ and $P \textrm{ implies } Q$ are true, then we can conclude that $Q$ is true
If statement $P \textrm{ implies } Q$ is true and $Q$ is false, we can conclude that $P$ is false

Direct Proof

Most theorems can be viewed as a form of $P \rightarrow Q$ (P implies Q)
In a direct proof, you start with the statement Assume $P$ is true
Then you produce a series of steps to reach $Q$

Example

Let $a, b, c \in \mathbb{N}$
If $a | b$ and $b | c$ then $a | c$ (that is to say, if $a$ divides $b$ and $b$ divides $c$ then $a$ divides $c$) (divides relation on natural numbers is transitive)

• Suppose that $a | b$ and $b | c$
• Hence there are $q, r \in \mathbb{N}$ such that $aq = b$ and $br = c$
• Define $k = qr$, observe that $k \in \mathbb{N}$
• Then $ak = a(qr) = (aq)r = br = c$
• Since $ak = c$ we know $a | c$

Example

Let $n \in \mathbb{N}$ then $n | 0$

• Observe $n \cdot 0 = 0$
• Hence $n | 0$

Example

Let $n \in \mathbb{N}$, if $n$ is odd, then $n^2$ is odd

• Then $n = 2k + 1$ for some $k \in \mathbb{N}$
• So, $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1$
• So, $n^2 = 2q + 1$ where $1 = 2k^2 + 2k$
• Since $k \in \mathbb{N}$, then $q = 2k^2 + 2k$ is a natural number
• $n^2$ is odd

Proof by Contrapositive

When proving $P \rightarrow Q$, we observe that it is the same as $\overline{Q} \rightarrow \overline{P}$ (if $Q$ is false, then $P$ has to be false)
"We prove the contrapositive [insert contrapositive here]"
We then give a direct proof for the contrapositive

Example

Let $n \in \mathbb{N}$ if $n^2$ is even, then $n$ is even.

We prove the contrapositive $n \in \mathbb{N}$ is $n^2$ is not even, then $n$ is not even

• Assume $n$ is not even
• $n = 2k + 1$ for some $k \in \mathbb{N}$
• $n^2 = (2k + 1)^2 = 4k^2 + 4k + 1$
• $n^2 = 2q + 1$ where $q = 2k^2 + 2k$
• We showed that if $n$ is odd, $n^2$ is odd
• Therefore, if $n^2$ is even, so is $n$

Proof by Contradiction

When proving $P \rightarrow Q$, we assume it is false
That is, we assume $P$ is true and $Q$ is false.
We derive a clearly false statement (often in the form of $R \wedge \overline{R}$)
We conclude our assumption was wrong and $P \rightarrow Q$ is true

Example

Prove that the number $\sqrt{2}$ is irrational

• Assume that $\sqrt{2}$ is rational
• $\sqrt{2} = \frac{a}{b}$ where $a$ and $b$ do not have common divisors
• $2 = \frac{a^2}{b^2}$
• $a^2 = 2b^2$, and $a = 2k$ is even
• This means $2k^2 = b^2$, and $b = 2l$ is even
• This contradicts with $a$ and $b$ not having common divisors

Example

Let $A$, $B$ be finite sets and $f: A \rightarrow B$ a function.
If $|A| > |B|$, then $f$ is not injective

• Assume for contradiction, that $f$ is injective and $|A| > |B|$
• Then $|f(A)| = |{f(a) | a \in A }| = |A|$, therefore $|f(A)| > |B|$
• But $f(A) \subseteq B$, so $|f(A)| \leq |B|$
• So, $|f(A)| \leq |B| \lt |f(A)|$, which is a contradiction

Proof by Cases

When $P \rightarrow Q$ is more complex

• $P = A \vee B$
• We have a universal $\forall x…$ statement, without single argument for all $x$
• We split proof into separate cases
• For example, to proov $(A \vee B) \rightarrow Q$ we prove $A \rightarrow Q$ and $B \rightarrow Q$

Example

Let $A$, $B$, $C$ be sets. If $x \in A \cup (B \cup C)$ then $x \in (A \cup B) \cup C$

• Case 1 - $x \in A$
  • Since $x \in A$, $x \in A \cup B$, by definition of $\cup$
  • Since $x \in A \cup B$, $x \in (A \cup B) \cup C$ by definition of $\cup$
• Case 2 - $x \in B \cup C$
  • Case 2a - $x \in B$
    • $x \in B \Rightarrow x \in A \cup B \Rightarrow x \in (A \cup B) \cup C$
  • Case 2b - $x \in C$
    • $x \in C \Rightarrow x \in (A \cup B) \cup C$

Example 2

“Every collection of 6 people incudes 3 people that all know each other or a group of 3 strangers”

• Let $x$ be one of “people”
• Case 1 - $x$ knows set $X$ of at least $3$ of remaining $5$
  • Case 1a - $y, z \in X$ know each other
    • So $x, y, z$ all know each other
  • Case 1b - $X$ is a group of strangers
• Case 2 - $x$ does not know set $X$ of at least $3$ of remaining $5$
  • Case 2a - $y, z \in X$ do not know each other.
    • So, $x, y, z$ is a group of strangers
  • Case 2.2 - People in $X$ all know each other

Proof by example

Proof by example can only be used for statements of type $\exists x. P(x)$
This is because we only need to present one value of $x$ that satisfies $P(x)$
This can also be used to disprove propositions, however…

Example

“Show that the following statement is false: For all $n \in \mathbb{N}$”, the number $n^2 - n + 41$ is a prime

• Let $n = 41$
• $n^2 - n + 41 = 41^2$, which is not prime

Example

Show that the following statement is false:
For all sets $A$, $B$, and $C$, $(A \cap B) \cup C = A \cap (B \cup C)$

• Let $A = \emptyset, B = C = \mathbb{N}$
• Then $(A \cap B) \cup C = \mathbb{N}$ and $A \cap (B \cup C) = \emptyset$

Proofs of Universal Statements

• These are statements of type $\forall x P(x)$
• We choose an arbritrary $x$

Counter example

Prove that the relation $R = {(x, 2^x) | x \in \mathbb{N}}$ is a function $f : \mathbb{N} \rightarrow \mathbb{N}$

• Let $x \in \mathbb{N}$
• $(x, 2^x) \in R$ and if $y \neq x$, then $(x, y) \notin R$
• $2^x \in \mathbb{N}$
• Hence, for every $a \in \mathbb{N}$, there exists exactly one $b \in \mathbb{N}$ such that $(a, b) \in R$ and $R$ is a function