3
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ 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$. $\endgroup$ Feb 8, 2019 at 12:05
  • $\begingroup$ @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$. $\endgroup$
    – Kapur
    Feb 8, 2019 at 12:19
  • 1
    $\begingroup$ 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". $\endgroup$ Feb 8, 2019 at 12:25
  • 1
    $\begingroup$ @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$. $\endgroup$ Feb 8, 2019 at 12:28
  • $\begingroup$ @MauroALLEGRANZA ungrammatical elements are already excluded because $S$ is assumed to be "a set of wffs" $\endgroup$ Feb 8, 2019 at 12:29

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .