(*) 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$.The obvious proof uses induction (on $n$, as one says). We want to show that: every number $n \in \mathbb{N}$ has a certain property: namely, that the formula $S_n$ is equivalent to $P \rightarrow Q$. We can show this by induction. Induction says that if a property holds of $0$, and holds of $k+1$ whenever it holds of $k$, then it holds of all numbers. So, induction proofs proceed in three steps. First (the base step) show the property holds of $0$. Second (the induction step) show that, assuming it holds of $k$, it also holds of $k+1$. Finally, conclude that it holds of all numbers.

$\textbf{Base}$. I.e., when $n = 0$.

$S_0$ is $P \rightarrow Q$. This is obviously equivalent to $P \rightarrow Q$.

$\textbf{Induction Step}$. I.e., from $k$ having the property, we want to show $k+1$ has it too.

So, suppose $S_k$ is equivalent to $P \rightarrow Q$. (This is the

*Induction Hypothesis*.) We want to show that $S_{k+1}$ is equivalent to $P \rightarrow Q$ as well.

First, note that $S_{k+1}$ is

*defined*to be $P \rightarrow S_k$. The Induction Hypothesis tells us that $S_k$ is equivalent to $P \rightarrow Q$. But we can use the simple lemma that "the substitution of equivalents leads to equivalents". So, we can conclude that $S_{k+1}$ is equivalent to $P \rightarrow (P \rightarrow Q)$. We only then need to show that this is equivalent $P \rightarrow Q$. I.e., that $P \rightarrow (P \rightarrow Q) \equiv P \rightarrow Q$. This can be done with a truth table. So, that completes the induction step.

From the Base Step and the Induction Step, we can conclude, using the Induction Principle, that for all $n$, $S_n$ is equivalent to $P \rightarrow Q$, as required. $\sf{QED}$.

## No comments:

## Post a comment