I am reading Herbert Enderton's book "A Mathematical Introduction to Logic".
I have the problem with the following theorem meaning.
Induction principle If $S$ is set of wffs containing all the sentence symbol and closed under all five formula-building operations, then $S$ is the set of all wffs.
Some notes; wffs are well-formuled formulas, the formula-building operations are operation which construct from two wffs $\alpha, \beta$ for example a wff $\alpha \wedge \beta$. Moreover, we have the next four building operation ($\neg,\vee, \rightarrow, \leftrightarrow$).
I have problem with following sentence
"If $S$ is set of wffs containing all the sentence symbol ..."
I suppose that we have a set $A = \{A_1, A_2, A_3\}$ of the all sentence symbols. I think that the set $S$ can be $S = \{A_1, A_2, A_3\}$.
But I do not see any reason why the set $S$ cannot be $S = \{(A_1 \vee A_2), (A_2 \wedge A_3)\}$.
And this is valid because the S is set of wffs, which contain all sentence symbols. But now the theorem is nonsense because we cannot construct from any building operation, for example $\delta = (\neg A_1)$.
Can you tell me, where is the restriction in theorem, which does not allow construct the set $S$ as above ($S = \{(A_1 \vee A_2), (A_2 \wedge A_3)\}$).
Ad1.:
We define a construction sequnce to be a finite sequence $(\epsilon_1, \dots, \epsilon_n)$ of expressions such that for each $i \leq n$ we have at least one of
- $\epsilon_i$ is a sentence symbol
- $\epsilon_i = \neg(\epsilon_j)$ for some $j < i$
- $\epsilon_i = (\epsilon_j * \epsilon_k)$ for some $j < i, k < i$, where * is one of the binary connectives $\vee, \wedge, \rightarrow, \leftrightarrow$.
Then the wffs can be characterized as the expressions $\alpha$ such that some construction sequence end with $\alpha$
Proof (induction principle): Proof is by strong induction.
Base case: suppose that $\alpha$ contains only one sentence symbol, its construction sequence is $(\epsilon_1)$, by use rule 1.
Induction hypotheses: consider a arbitrary wff $\alpha$, its construction sequence is ($\epsilon_1, \dots, \epsilon_n$), where $\epsilon_n = \alpha$. We suppose that all $\epsilon_i$, $i < n$ are wff. We need show that $alpha$ is also wff. We have five five options how construct $\alpha$.
- $\alpha$ is a sentence symbol
- $\alpha = (\neg \epsilon_i)$
- $\alpha = (\epsilon_i \vee \epsilon_j)$
- $\alpha = (\epsilon_i \wedge \epsilon_j)$
- $\alpha = (\epsilon_i \rightarrow \epsilon_j)$
- $\alpha = (\epsilon_i \leftrightarrow \epsilon_j)$ where $j < n, k < n$
in every option we get wff. Thus $\alpha$ is wff.