34 2. Background
allowing you to extend the set of basic objects. We give some simple
Example 2.5.8. The natural numbers may be defined recursively as
• 0 ∈ N.
• If n ∈ N, then n + 1 ∈ N.
Example 2.5.9. The well-formed formulas (wffs) in propositional
logic are a recursively defined class.
• Any propositional symbol P , Q, R, etc., is a wff.
• If ϕ and ψ are wffs, so are the following:
(i) (ϕ & ψ)
(ii) (ϕ ∨ ψ)
(iii) (ϕ → ψ)
(iv) (ϕ ↔ ψ)
The important fact, which gives the strength of this method of
definition, is that we may apply the closure operators repeatedly to
get more and more complicated objects.
For example, ((A&B) ∨ ((P &Q) → (¬A))) is a wff, as we can
prove by giving a construction procedure for it. A, B, P , and Q are
all basic wffs. We combine them into (A&B) and (P &Q) by operation
(i), obtain (¬A) from (v), ((P &Q) → (¬A)) from (iii), and finally our
original formula by (ii).
Exercise 2.5.10. (i) Prove that ((A ∨ (B&C)) ↔ C) is a wff.
(ii) Prove that (P → Q(∨ is not a wff.
Exercise 2.5.11. (i) Add a closure operator to the recursive defi-
nition of N to get a recursive definition of Z.
(ii) Add a closure operator to the recursive definition of Z to get a
recursive definition of Q.
Exercise 2.5.12. Give two different recursive definitions of the set
of all positive multiples of 5.