Basic proof techniques

A proof is a finite sequence of steps which establishes the validity of a statement. When writing a proof, we assume the validity of a certain set of statements without proof (these statements are called axioms). So, roughly speaking, we start with a set of axioms (the most popular axioms in use is called Zermelo-Fraenkel (ZF) axioms), and apply a logical rule at each step, until we reach the desired statement; each such step is often called logical deduction.

📄️ Direct proof

The term direct proof is often used to denote the strategy of proving the statement $P\Rightarrow Q$ by first assuming that $P$ is true, then trying to derive the validity of $Q$. Let us see a simple example. For integers $a,b \in \mathbb$, we use the notation $a \mid b$ to denote the fact that $a$ divides $b$ (which is the same as saying $b = q \cdot a$ for some $q\in\mathbb{Z}$). We remark that this definition only concerns divisibility between two integers.

📄️ Contraposition

The contraposition of the statement $P \Rightarrow Q$ is $\neg Q \Rightarrow \neg P$. Despite being equivalent, we will often find that one statement is easier to prove than another. Let us look at some concrete examples. We say that $a \equiv b \pmod$ ("$a$ is congruent to $b$ modulo $m$") if $m \mid (a - b)$. For example, $12 \equiv 18 \pmod{-3}$ and $3 \equiv -4 \pmod{7}$. Notice, $x \equiv 1 \pmod{2}$ for odd integer $x$.

📄️ Contradiction

Another important proof strategy is called proof by contradiction. In particular, we assume that the statement we want to prove is false, and use logical deductions to derive something which is trivially false (e.g., $0 \neq 0$). This would then imply that the original statement must be true. Let’s again look at a concrete and classical example. We say that a positive integer $x$ is a prime if $1$ and $x$ are the only positive integers that divide $x$. We will use the following lemma (whose proof is deferred to the subsequent lectures).

📄️ Case analysis

Proving by considering different cases is often used when we are not sure about the truth of some statement, and the trick is that, often, we do not really need the knowledge about its validity. Let us look at a concrete example.