34 2. Background

allowing you to extend the set of basic objects. We give some simple

examples.

Example 2.5.8. The natural numbers may be defined recursively as

follows:

• 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) (ϕ ↔ ψ)

(v) (¬ϕ)

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.