# Induction principle (theorem meaning)

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

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.

• If $A = \{ A_1,A_2,A_3 \}$ then $S= \{ A_1,A_2,A_3, \lnot A_1,\lnot A_2,\lnot A_3, A_1 \lor A_1, A_1 \lor A_2,A_1 \lor A_3, \ldots \}$. The key-point is "closed under all five formula-building operations", that means that every possible finite combination of the elements of $S$ (and not $A$) must be in $S$. – Mauro ALLEGRANZA Feb 8 at 12:05
• @MauroALLEGRANZA Thank you, I maybe get it. So, check me please. In example above, i consider that $(A_1 \vee A_2)$, $(A_2 \wedge A_3) \in S$, beacuse wffs are closed under the five formula-building operations, then we know that $A_1, A_2, A_3 \in S$. And then how you said, in set $S$ are all possible finite combination of the elements of $S$. – Kapur Feb 8 at 12:19
• Yes; $A_1$ etc are sentence symbols but also wff (atomic formulas) thus they are in $S$ from the beginning and then you throw in (into $S$) all fi ite combinations (according to the formation rules) of elements already in $S$. Obviously, the process will be completed only "at infinity". – Mauro ALLEGRANZA Feb 8 at 12:25
• @Kapur If $A_1,A_,A_3$ are sentence symbols, then we know that $A_1\in S,A_2\in S, A_3\in S$. As $S$ is closed under the operations, $A_1\in S, A_2\in S$ implies $A_1\lor A_2\in S$. Similarly, $A_2,a_3\in S$ implies $A_2\lor A_3\in S$. Now knowing $A_1\lor A_2\in S$ and $A_2\lor A_3\in S$, closedness implies that also $(A_1\lor A_2)\land (A_2\lor A_3)\in S$. – Hagen von Eitzen Feb 8 at 12:28
• @MauroALLEGRANZA ungrammatical elements are already excluded because $S$ is assumed to be "a set of wffs" – Hagen von Eitzen Feb 8 at 12:29

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.

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