9. Direct and indirect proofs

Direct and indirect proofs

Direct Proofs

Used to prove theorems of the form $\forall x(A(x)\to B(x))$:

• We choose an arbitrary entity from the domain.
  • Must be arbitrary, not specific but in the domain.
  • We need to use a pointer to refer to it.
  • We can pick any symbol to refer to it.
• Then we prove the conditional statement $A(y)\to B(y)$ for the arbitrary $y$ by a direct proof:
  • Assume $A(y)$ is true, use axioms, definitions and previously proven theorems, with inferences, to show that then $B(y)$ must also be true.
• We can then apply the rule of universal generalisation.

For example, given the theorem “If $n$ is an odd integer, then $n^2$ is odd”, the proof is:

• Let $n$ be an arbitrary integer.
• Assume $n$ is odd.
• Since $n$ is odd, let $n=2k+1$.
• Hence, $\begin{array}{rl}{n}^2& =(2k+1{)}^2\\ & =4k^2+2k+2k+1\\ & =4k^2+4k+1\\ & =2(2k^2+2)+1\text{ which is odd }\because 2n(..)\text{ even and}+1\text{ makes it odd}\end{array}$
• $\therefore$ $n^2$ must be odd if $n$ is an odd integer.

Indirect Proof

For example, show that at least $4$ of any $22$ dates in the calendar must fall on the same day of the week. We can try a proof by contradiction, which does not prove a result ‘directly’.

• Let $p$ be “at least $4$ of $22$ chosen dates fall on the same day of the week”.
• Suppose that $\neg p$ is true, that means “at most $3$ of $22$ chosen dates fall on the same day of the week”.
• We know that there are 7 days of the week, this implies at most $21$ dates could have been chosen, as for each of the $7$ days of the week, at most $3$ of the chosen dates could fall on that day.
• So, if $q$ is the statement that ”$22$ dates are chosen” then we found that $\neg p\to \neg q$.
• Using $q$ as a premise, we reached a contradiction by showing $(q\wedge \neg p)\to (q\wedge \neg q)$.
• We find that $q\wedge \neg q$ is a contradiction, it will always be false.
• As $q$ is true (our premise), $q\wedge \neg p$ can only be false when $\neg p$ is false, hence $p$ is true.