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.

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2012 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.