Formal Languages and Well-Formed Formulas

To study deduction mathematically, one builds a formal language precise enough that follows logically becomes a statement about strings of symbols rather than about meaning. Sentential logic is the first and simplest such language. It fixes a handful of connectives — not, and, or, if–then, if-and-only-if — and asks what can be said and deduced using only those, with the internal structure of the sentences they join left opaque.

A natural language such as English carries meaning but tolerates ambiguity. A formal language reverses the priorities: it is defined by exact formation rules, and meaning is assigned only afterward, as a separate act. To describe a formal language, Enderton gives three pieces of information.¹

• The alphabet. The set of symbols out of which everything is built.
• The formation rules. Which finite strings of symbols count as grammatically correct. These strings are the well-formed formulas, or wffs.
• The intended translations. How wffs correspond to English sentences. Only this third part assigns any meaning; the first two are pure syntax.

A person who knew only the alphabet and the formation rules could carry out much of what follows in complete ignorance of meaning, shuffling symbols by rule. Syntax and semantics stay separate. Meaning enters with truth assignments; the syntax comes first.

The alphabet

Fix an infinite sequence of distinct objects called symbols. We give them names but stay neutral about what they are: sets, numbers, or marbles would all serve. The one structural demand is that no symbol is a finite sequence of other symbols, so that a string of symbols decomposes in exactly one way into its constituent symbols.²

The symbols fall into two groups.

The two parentheses are punctuation. The five sentential connective symbols have fixed intended readings.

The connectives together with the parentheses are the logical symbols: their translation to and from English never changes. The sentence symbols$A_1,A_2,\dots$ are the parameters, or nonlogical symbols. Their translation is not fixed. In one context $A_5$ might stand for the evidence is admissible; in another, for wishes are horses. Some authors call $A_n$ the $n$th proposition symbol and speak of propositional logic; the reading is the same.

There are infinitely many sentence symbols. A more frugal alphabet would use a single symbol $A$ and a prime, writing $A,A^{\prime },A^{\prime \prime },\dots$ for the sequence, which brings the total number of distinct symbols down to nine. A less frugal choice would allow an arbitrary set of sentence symbols, countable or not. Most of this chapter survives either change; the exception is compactness, where countability of the symbol set is used.

An expression is any finite sequence of symbols. We name an expression by concatenating the names of its symbols: $(\neg A_1)$ names the four-symbol sequence $(,\neg ,A_1,)$. If $\alpha$ and $\beta$ are expressions, $\alpha \beta$ is their concatenation. So if $\alpha =(\neg A_1)$ and $\beta =A_2$, then $(\alpha \to \beta )$ is the expression $((\neg A_1)\to A_2)$.

Translating English

Let $A,B,\dots ,Z$ abbreviate the first twenty-six sentence symbols. Then compound English sentences translate by rendering not as $\neg$, and as $\wedge$, or (inclusive) as $\vee$, if–then as $\to$, and if and only if as $\leftrightarrow$.

• The evidence is inadmissible $⇝(\neg E)$.
• The evidence is admissible, and the suspect need not be released$⇝(E\wedge (\neg R))$.
• Either the evidence is admissible or the suspect must be released, but not both $⇝((E\vee R)\wedge (\neg (E\wedge R)))$.

We always read $\vee$ inclusively, as and/or. A caution: an English sentence and its translation are different objects. Roses are red is presumably true or false; the expression $R$ is just a string of symbols, true or false only once interpreted, and interpretable differently in different contexts.

Some expressions translate no English sentence and are mere nonsense, such as $((\to A_3$. The formation rules exist to exclude exactly these.

Well-formed formulas

We want the well-formed formulas to be the grammatical expressions. The definition should have three consequences: every sentence symbol is a wff; applying a connective to wffs yields a wff; and nothing is a wff except by force of those two clauses. The third clause — the demand that wffs be only what the first two compel — is what needs care.

The five connectives correspond to five formula-building operations on expressions:

Each takes one or two expressions and returns a longer expression: it wraps its inputs in parentheses and inserts a connective. Note that every operation inserts exactly one matched pair of parentheses.

For example, $((A_1\wedge A_{10})\to ((\neg A_3)\vee (A_8\leftrightarrow A_3)))$ is a wff, built from four sentence symbols by five applications of the operations. At the other extreme, a lone sentence symbol $A_3$ is a wff, built by zero applications. The empty sequence is not a wff; a wff has at least one symbol.

Formation trees

The construction of a wff is displayed by its formation tree (Enderton's ancestral tree): the wff sits at the root, each internal node is an application of one operation, and the leaves are sentence symbols. Reading the tree from the leaves up reconstructs the wff one operation at a time.

An equivalent linear record of the same construction is a construction sequence: a finite sequence ${\epsilon }_1,\dots ,{\epsilon }_n$ of expressions in which each ${\epsilon }_i$ is either a sentence symbol or the result of applying an operation to earlier entries. An expression $\alpha$ is a wff if and only if some construction sequence ends with $\alpha$. A construction sequence is a formation tree flattened into a list.

The set of wffs as a least closed set

The definition says a wff is anything built by applying the operations a finite number of times. That phrase is made precise by the notion of a least closed set, the pattern developed in full in induction and recursion.

Call a set $S$ of expressions closed under the formula-building operations iff whenever $\alpha ,\beta \in S$, every ${\mathcal{E}}_{\square }(\alpha ,\beta )$ (and ${\mathcal{E}}_{\neg }(\alpha )$) is again in $S$. Many sets are closed — the set of all expressions, for one. The set of wffs is the smallest set that both contains the sentence symbols and is closed. Equivalently, it is the intersection of every such set: an expression is a wff iff it belongs to every set that contains the sentence symbols and is closed under the operations.

The induction principle

Every least-closed-set construction comes with a proof technique. To show a property holds of all wffs, it suffices to show it holds of the sentence symbols and is preserved by each operation.

The reason is immediate from the least-closed-set definition: such an $S$ is a closed set containing the symbols, so it includes the smallest one, which is the set of all wffs.³ The argument reads two ways.

• Up the tree. An arbitrary wff $\alpha$ has a formation tree. Every leaf is a sentence symbol, hence in $S$. Working upward, each node's expression is built from children already in $S$ by an operation $S$ is closed under, so it too lies in $S$. The root $\alpha$ therefore lies in $S$.
• Along the sequence. $\alpha$ ends some construction sequence ${\epsilon }_1,\dots ,{\epsilon }_n$. By strong induction on $i$, each ${\epsilon }_i\in S$: it is either a sentence symbol or built from earlier entries, all in $S$ by hypothesis. So $\alpha ={\epsilon }_n\in S$.

A worked application

The induction principle is the standard tool for proving expressions ill-formed, by exhibiting a property that all wffs share and the target expression lacks.

This is the shape of every ill-formedness proof: find an invariant the operations preserve, check the target expression violates it.

Formulas build upward

A structural feature of these particular operations will matter repeatedly: they build up and never down. The expression ${\mathcal{E}}_{\square }(\alpha ,\beta )$ contains all of $\alpha$ and all of $\beta$ as consecutive segments, plus a connective and two parentheses, so it is strictly longer than either. Every constituent of a wff appears verbatim inside it.

One consequence: if a wff $\phi$ does not contain the symbol $A_4$, then $\phi$ can be built without ever using $A_4$. The symbol cannot appear in an intermediate stage only to vanish, because nothing is ever deleted. This no material is thrown away property makes the parentheses recoverable, and it underlies the parsing algorithm and the unique readability theorem.