0

The set of propositional formulas, $X$, is defined as the smallest set such that

  1. Every atomic formula is in $X$.
  2. If $F$ is in $X$ then $\neg F$ is in $X$.
  3. If $F$ and $G$ is in $X$ than $(F\land G ), (F\lor G) $ and $(F \rightarrow G)$ is in $X$.

Now, assume that we have the set $X$ and I look at a random element. Now I want to prove that the element is either an atomic formula, or is $\neg F$ where $F$ is a propositional formula, or it is of the form $(F\land G )$ or $(F\lor G) $ or $(F \rightarrow G)$, where $F$ and $G$ are propositional formulas.

This almost follows from the definition, the problem is that we have defined $X$ as the "smallest set", so in theory there could be that some other variations sneak into $X$(I know that this doesn't happen, but I want to prove it). Do you see how to prove it?

user394334
  • 1,230

1 Answers1

1

The proviso "the smallest set" actually substitutes the closure (exclusion) clause of inductive definition that states in some proper wording the following idea:

Nothing else is a . . . [or "in the set S"] except those that are admitted by the basis clause or the inductive clause.

setting down that there is no syntactical ambiguity. This clause is often omitted because of its obviousness.

The formation rules specifies that the string that conforms to the rules are wffs (well-formed formulas), but not the reverse. To put symbolically, the formation rules of inductive definition asserts by themselves that

$\forall x(Defn(x)\rightarrow Form(x))$,

but leaves open

$\forall x(Form(x)\rightarrow Defn(x))$.

A helpful idea to unfold the closure clause is the time-honoured maxim that if some statement seems too obvious, assume its negation and try to derive a contradiction. In the present case, we shall assume $\exists x(Form(x)\wedge\neg Defn(x))$, that is, there is a string of symbols $\psi$ claimed to be a member of the set of wffs. Then, we shall show that either $\psi$ is not a formula or identical to a wff build up as inductively defined.

To this purpose, the unique readability theorem for the language of the logical system in work can be invoked. Unique readability theorem states that the wffs of the language is built up by the rules in a unique way and any string of symbols that is claimed to be a member of the set of wffs is either identical to a wff build up by the rules or not a formula in the language.

I shall give a sketch of a proof of a unique readability theorem.

We use structural induction on length of the strings throughout. We make the following observations:

  • Each wff is either atomic or compound. If it is not an atomic formula, it starts with a left bracket or negation symbol.
  • Every wff $\phi$ has an equal number of left and right brackets: $l(\phi) = r(\phi)$.
  • Any proper prefix (initial segment) $\alpha$ of a wff has more left brackets than right brackets: $l(\alpha) > r(\alpha)$.

and prove the lemma

  • No proper prefix of a wff is a wff.

As the last step, we take a wff $\phi$ and a string $\psi$ assumed to be a wff. We show that either $\psi$ be a proper prefix of formula $\phi$, $l(\psi) > r(\psi)$, then it is nt a wff, or $\psi$ is itself a formula, $l(\psi) = r(\psi)$, identical to $\phi$.

It should be remarked that there are a lot of variations of the proof both with respect to the details of rigour presented and to the approach taken up. See, for instance, H. B. Enderton's A Mathematical Introduction to Logic (2nd edition, pp. 40–41 for propositional calculus, pp. 107-108 for the terms and formulas of predicate logic).

Tankut Beygu
  • 2,331