Induction principle (theorem meaning)

Question

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

1. $\epsilon_i$ is a sentence symbol
2. $\epsilon_i = \neg(\epsilon_j)$ for some $j < i$
3. $\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.

Answer 1

There is no restriction in the theorem. The theorem holds quite regardless of what the sentence symbols are; the problem you point to isn't one, really.

Enderton probably (I don't have the book) defines the set of sentence symbols as the set containing exactly $A_1$, $A_2$ and so on (or $p_0$ and $p_1$ and so on; how he writes them doesn't matter much). So he has some set -- one single set, throughout the book -- of sentence symbols. Let's call that set $\mathrm{Sym}$. And let's call the set of all wffs $\mathrm{Wff}$.

Now what the theorem says is: if you have a set $S \supset \mathrm{Sym}$ which is closed under formula-building operations, then $S \supset \mathrm{Wff}$.

If you decide you don't like Enderton's $\mathrm{Sym}$, you can define your own. So let's replace $\mathrm{Sym}$ by the set $\mathrm{Sym'} := \{(A_1 \lor A_2)\}$, and not change any other definition. Then we have defined a new language. $\mathrm{Wff}$ depends on $\mathrm{Sym}$: it contains exactly the things we can build up from the things in $\mathrm{Sym}$. When we change $\mathrm{Sym}$, we change $\mathrm{Wff}$. Our new set of formulas $\mathrm{Wff'}$ will contain $(A_1 \lor A_2)$ and $\neg (A_1 \lor A_2)$ (and things like $\neg (A_1 \lor A_2) \lor ((A_1 \lor A_2) \lor \neg (A_1 \lor A_2))$), but it won't contain $\neg A_1$ nor, for instance, $A_3$, because we can't build those from (the only thing in) $\mathrm{Sym'}$.

Now when we do this, the theorem will still hold: it does not really depend on $\mathrm{Sym}$. When we define our new $\mathrm{Sym'}$, we will be able to prove, exactly in the way Enderton proves his theorem, that whenever $P \supset \mathrm{Sym'}$ is closed under formula-building operations, $P \supset \mathrm{Wff'}$. $P$ might not contain $\neg A_1$ -- but, again, that is no longer a formula.

Answer 2

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\}$.

While the set $S_1=\{A_1, A_2, A_3\}$ does contain all the sentence symbols from $A$, it is not closed under the five formula-building operations. In fact, $S_1$ is not closed under any of the operations: It doesn't contain $\neg A_1$, $A_1\wedge A_2$, $A_1\vee A_2$ etc.

Hence the set $S_1$ does not fit the requirements to apply the induction principle. That is, we can't conclude that it contains all well-formed formulas.

But I do not see any reason why the set $S$ cannot be $S = \{(A_1 \vee A_2), (A_2 \wedge A_3)\}$.

The set $S_2=\{(A_1 \vee A_2), (A_2 \wedge A_3)\}$ satisfies even less of the assumptions: It does not contain all the sentence symbols to begin with. Yes, for each sentence symbol there is some element of $S$ that is a formula mentioning it, but the symbol itself is not contained in $S$, for example $A_1\notin S$. Furthermore it is also not closed under the five formula-building operations: for example $(A_1\vee A_2)\in S$ but $\neg(A_1\vee A_2)\notin S$.