## Tuesday, 12 April 2011

### "How to write proofs: a quick guide"

• Show that the formula $P \rightarrow (P \rightarrow Q)$ is equivalent to $P \rightarrow Q$.
So, the student writes down a truth table with sentence letters $P$ and $Q$, and a column $P \rightarrow (P \rightarrow Q)$ and a column for $P \rightarrow Q$ and checks that the truth values of these two columns all match. Alternatively, a student might be asked to give a formal derivation of $P \rightarrow Q$ from $P \rightarrow (P \rightarrow Q)$ and vice versa.

• Suppose $S_0$ is $P \rightarrow Q$ and $S_{n+1}$ is $P \rightarrow S_n$. Show that, for all $n$, $S_n$ is equivalent to $P \rightarrow Q$