Why is a recursive definition of well-formed formulas (wffs) necessary, rather than simply providing a comprehensive list of valid formulas?
AListing all valid formulas is possible in principle but the list would be very long, so recursion is used for convenience
BThe recursive definition enables structural induction and makes semantics compositional — the meaning of any compound formula is determined by the meanings of its parts and their connective
CA recursive definition allows logic to handle self-referential formulas and circular definitions
DListing all valid formulas would produce ambiguous parsings, whereas recursion avoids this
There are infinitely many wffs, so enumeration is impossible. But more fundamentally, the recursive definition does two things no list can: it enables structural induction (proofs about all wffs reduce to base cases and inductive steps), and it makes semantics compositional — the truth conditions of (φ ∧ ψ) are determined by the truth conditions of φ and ψ and the meaning of ∧. Without compositional structure, semantics cannot be defined for formulas not yet seen. The recursion is the bridge between syntax and semantics.
Question 2 Multiple Choice
In the formula ∀x (P(x) → Q(x, y)), which correctly describes the variable occurrences?
ABoth x and y are bound, since the entire formula is governed by ∀x
Bx is bound (governed by ∀x throughout its scope) and y is free (no quantifier governs y)
Cx is free in the antecedent P(x) and bound in the consequent Q(x, y)
Dy is bound because it appears within the scope of ∀x, which governs the whole subformula
The scope of ∀x is the entire formula (P(x) → Q(x, y)). All occurrences of x fall within this scope, so x is bound everywhere it appears. The variable y has no governing quantifier anywhere in the formula — no ∃y or ∀y appears — so every occurrence of y is free. Binding requires a *matching* quantifier: ∀x only binds x, not y. Free variables are the 'parameters' of the formula — this formula expresses a property of y. The wff definition tracks this distinction precisely through its recursive scope rules.
Question 3 True / False
Every theorem about all well-formed formulas can in principle be proved by structural induction, because the recursive definition of wffs specifies exactly the construction cases that must be handled.
TTrue
FFalse
Answer: True
Structural induction mirrors the recursive structure of wffs directly. To prove property P holds for all wffs: prove P for all atomic formulas (base case), then show that if P holds for wffs φ and ψ, it holds for ¬φ, (φ ∧ ψ), (φ ∨ ψ), (φ → ψ), ∀x φ, and ∃x φ (inductive steps). Since these cases exhaust all possible wffs by the recursive definition, the proof covers everything. The soundness theorem, completeness theorem, and compactness theorem for first-order logic are all proved by structural induction on the formula.
Question 4 True / False
In the formula ∀x (P(x) → Q(x, y)), both x and y are bound variables, since x appears under the quantifier ∀x which governs the entire formula.
TTrue
FFalse
Answer: False
Only x is bound; y is free. The quantifier ∀x binds x throughout the formula's scope — every occurrence of x is bound by it. But binding is variable-specific: ∀x only binds x, not any other variable. Since no ∀y or ∃y appears anywhere, y has no governing quantifier and every occurrence of y is free. The rule is precise: a variable occurrence is bound if and only if it falls within the scope of a quantifier *for that specific variable*. Free variables are the parameters of the formula — it expresses a property about them, not about bound placeholders.
Question 5 Short Answer
Explain why the recursive definition of wffs is described as 'the contract between syntax and semantics.' What would be lost without a recursive definition?
Think about your answer, then reveal below.
Model answer: The wff definition specifies exactly which expressions the semantics is obligated to interpret, and it provides the compositional structure needed to define truth conditions. The semantics can define the meaning of (φ ∧ ψ) in terms of the meanings of φ and ψ because the recursive definition guarantees φ and ψ are themselves wffs with their own meanings. Without recursion, we could only assign meanings to explicitly listed formulas, leaving infinitely many others undefined. We also lose structural induction as a proof technique.
The 'contract' metaphor captures a mutual commitment: the wff definition commits the semanticist to interpret every formula the grammar generates (no new formulas that the semantics hasn't handled), and the grammar commits to generating only formulas with the compositional structure the semantics requires. Without recursion, proofs about all formulas would be impossible — you'd have no way to enumerate the cases. Nearly every major result in logic (soundness, completeness, compactness) would have no proof technique available. The recursive definition is the architectural foundation the rest of the subject rests on.