1
$\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$
  • 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$ – Mauro ALLEGRANZA Feb 8 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 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$ – Mauro ALLEGRANZA Feb 8 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$ – Hagen von Eitzen Feb 8 at 12:28
  • $\begingroup$ @MauroALLEGRANZA ungrammatical elements are already excluded because $S$ is assumed to be "a set of wffs" $\endgroup$ – Hagen von Eitzen Feb 8 at 12:29
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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.