How to Write Proofs, 2
In the earlier post, "How to Write Proofs, A Quick Guide", I gave the example of a simple kind of result that one might come across (and should know how to prove) in intermediate logic:
$\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}$.
(*) 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}$.
Comments
Post a Comment