Why is the set of well formed formulas are defined as the smallest set of strings

logicpropositional-calculus

Consider this definition of Well formed formulas in mathematical logic –
The set of all well formed formula is the smallest set of strings , WFF that satisfies

  1. All Boolean variables are in WFF, and so are the symbols Τ and F. We call
    such formulae atomic.
  2. If A and Β are any strings in WFF, then so are the strings (not A), (A and B),
    (A V β), (A —> β), (A = B)

Wouldn't there be exactly one such set of strings satisfying these properties of WFF ?
I don't understand the need for using the word smallest.

Best Answer

Consider first a simpler example:

The set of even numbers $E$ is the smallest $X\subseteq \mathbb{N}$ with the following two properties:

  • $0\in X$, and

  • if $n\in X$ then $n+2\in X$.

The two bulletpoints alone do not pin down $E$! For example, both $\mathbb{N}$ itself and $E\cup\{n\in\mathbb{N}: n\ge 17\}$ satisfy them. Basically, the minimality clause is required to make sure that no "unintended" elements enter the set we're defining.

Turning back to the example in the question, note that the set of all finite strings of symbols satisfies points $1$ and $2$ of your definition; it's only the minimality clause that tells us that that's not what we have in mind. See also here.

Related Question