3
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I think Tarski and Lukasiewicz in a paper on propositional calculus defined the set of "meanginful expressions" (alternate term they used for wffs) as the intersection of all the sets that satisfy those properties. Any reason to talk about "the smallest set" instead of an intersection of sets? $\endgroup$ – Doug Spoonwood Jan 22 at 4:08
  • $\begingroup$ @DougSpoonwood Not too seriously. That said, in my opinion "smallest" is a bit more natural than "intersection of all" since it more pleasantly jibes with the from-below definition of such an object which one generally develops at around the same time (e.g. defining the class of Borel sets via the Borel hierarchy rather than as the smallest $\sigma$-algebra containing the opens). $\endgroup$ – Noah Schweber Jan 22 at 4:11
1
$\begingroup$

Noah has already answered your question, but let me also add a side remark.

Instead of the "smallest set / intersection of all sets"-presentation of WFF, you sometimes also encounter definitions of the following form:

WFF is the set of strings which are generated in the following way:

  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)

This "constructive" definition is also fine, and it is clear: I cannot see how two persons reading the above could possibly disagree about the object WFF which is being defined.

However, for some mathematicians nowadays the gold standard for rigorousness is formalizability in set theory; and here the "smallest set" definition is easier to state than the constructive one above.

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