Proof

Direct proof

Direct proofs use assumptions to show something is true. Consider the statement "If $2^A \subseteq 2^B$ then $A \subseteq B$.". To prove this, we can take an arbitrary $x \in A$. It can then be said that $\{x\} \in 2^A$, as $\{x\}$ must be part of the power set of $A$. Since $2^A \subseteq 2^B$, $\{x\} \in B$, so $x \in B$. This shows that $A \subseteq B$ as $x$ is in both. This proof made use of assumption $2^A \subseteq 2^B$ to show $A \subseteq B$.

Using cases

Another way to prove something is by considering all the cases. Take the statement "$1+((-1)^n)(2n-1)$ is a multiple of 4 $\forall n \in \mathbb{Z}$". The value of $(-1)^n$ depends on whether the number is even or odd.

1. In the case the number is even, $(1+1(2n-1) = 2n$. As $n$ is even, we can substitute $n = 2k, k\in \mathbb{Z}$. This gives $4k$, which is divisible by 4.

2. In the case the number is odd, $(1-1(2n-1) = 1-2n+1 = 2-2n$. As $n$ is odd, $n = 2k-1$. This gives $2-2(2k-1) = 2-4k+2 = 4-4k = 4(1-k)$, so it's divisible by 4 when $n$ is odd.

As all $n\in \mathbb{Z}$ must be either odd or even, it has been shown that $1+((-1)^n)(2n-1)$ is a multiple of 4 $\forall n \in \mathbb{Z}$.

Proof by contrapositive

Proof by contrapositive uses the opposite of the statement to show that it isn't true, therefore the original statement was true. Consider "If $7x+9$ is even, then $x$ is odd." Assuming $x$ is even (opposite of the original statement), $x = 2m$. This gives $7(2m)+9 = 14m + 9 = 2(7m+4)+1$ which is always odd, so $7x+9$ is not even when $x$ is even. Therefore $x$ must be odd. Note this could also be proven by direct proof.

Proof by contradiction

Proof by contradiction assumes the opposite of something. Take the statement $\sqrt{2} \notin \mathbb{Q}$. Assuming $\sqrt{2} \in \mathbb{Q}$ (the opposite), it can be defined as a fraction of two integers in it's simplest form. $\sqrt{2} = \frac{m}{n}, m,n \in \mathbb{N} \setminus \{0\}$. Squaring both sides gives $2 = \frac{m^2}{n^2}$, so $2n^2 = m^2$. This means $m$ must be even, so let $m=2k$. $2n^2 = (2k)^2, 2n^2 = 4k^2, n^2 = 2k^2$. This means $n^2$ must be even, therefore $n$ must be even. If both $n$ and $m$ are even, then the fraction is not in it's simplest form. This contradicts $\sqrt{2} \in \mathbb{Q}$, so $\sqrt{2} \notin \mathbb{Q}$.

Whereas proof by contrapositive only takes the opposite of the last part of the statement, proof by contradiction takes the opposite of the whole statement.

Non-constructive proof

Theorem: "$\exists \: x,y \in \mathbb{R} \setminus \mathbb{Q}:x^y \in \mathbb{Q}$" (There exists an $x$ and $y$ which belong to the set of irrational numbers such that $x^y$ is rational.)
Consider $a = \sqrt{2}^{\sqrt{2}}$ and $b = \sqrt{2}$. Therefore $a^b = (\sqrt{2}^{\sqrt{2}})^{\sqrt{2}}=\sqrt{2}^{\sqrt{2}\times \sqrt{2}} = \sqrt{2}^2 = 2$. This presents two cases:

1. If $a,b \in \mathbb{R} \setminus \mathbb{Q}$, then $x=a, y=b$. (If $a$ and $b$ are irrational, then it has been shown that $a^b$ is rational)

2. If $a \in \mathbb{Q}$ then $x=\sqrt{2}, y=\sqrt{2}$. (If $a$ turns out to be rational, then it is equal to $\sqrt{2}^{\sqrt{2}}$, where both are irrational)

Only one of the two cases can be true, 1 fails if 2 is true and vice versa, but both show that $x^y$ is rational when $x$ and $y$ are irrational, so the theorem is still proven regardless of which is true.

Logic in proof

Example 1

$$ \begin{aligned} x \wedge (\neg x \vee y) &\equiv x \wedge y \\ x \vee (\neg x \wedge y) &\equiv x \vee y \end{aligned} $$

Proof:

$$ \begin{aligned} \text{1. For all } x, y \in \{T, F\}^2, x \wedge (\neg x \vee y) &= (x \wedge \neg x) \vee (x \wedge y) & \text{(Distributivity)}\\ &= F \vee (x \wedge y) & \text{(Excluded middle)}\\ &= (x \wedge y) \blacksquare & \text{(Identity)}\\ \text{2. For all } x, y \in \{T, F\}^2, x \vee (\neg x \wedge y) &= (x \vee \neg x) \wedge (x \vee y) & \text{(Distributivity)}\\ &= T \wedge (x \vee y) & \text{(Excluded middle)}\\ &= (x \vee y) \blacksquare & \text{(Identity)}\\ \end{aligned} $$

Example 2

Let $A \to (B \to C)$, $\neg D \vee A$ and $B$ be given. Show that $D\to C$.

We want to show $P \to Q$ will always hold, where P is the conjunction of the first 3 propositions and Q is $D \to C$. This will only not hold when $P \wedge \neg Q$ is true. To show $P \to Q$ always holds, we have to find the value of $P \wedge \neg Q$. If this is shown to be false, then $P \to Q$ will always hold. Replacing $P$ and $Q$ with their values gives $(A \to (B \to C)) \wedge (\neg D \vee A) \wedge B \wedge \neg (D \to C)$
$A \to (B \to C) = A \to (\neg B \vee C) = \neg A \vee (\neg B \vee C)$ and $D \to C = \neg D \vee C$.
The equation is now $(\neg A \vee (\neg B \vee C)) \wedge (\neg D \vee A) \wedge B \wedge \neg(\neg D \vee C)$.
Simplifying a little gives $(\neg A \vee \neg B \vee C) \wedge (\neg D \vee A) \wedge B \wedge D \wedge \neg C$.
Using $x \wedge (\neg x \vee y) \equiv x \wedge y$ from earlier, we can eliminate $\neg B$, $C$ and $\neg D$: $(\neg A) \wedge A \wedge B \wedge D \wedge \neg C$.
$A \wedge \neg A$ is always false, so the whole statement is false. Therefore $P \wedge \neg Q$ is always false. This means $P \to Q$ always holds. This means $D \to C$ can never be false, so must hold. $\blacksquare$