36 2. Background

Example 2.5.16. Consider the class of wffs, defined in Example

2.5.9. We may prove by induction that for any wff ϕ, the num-

ber of positions where binary connective symbols occur in ϕ (that

is, &, ∨, →, and ↔) is one less than the number of positions where

propositional symbols occur in ϕ.

Proof. For any propositional symbol, the number of propositional

symbols is 1 and the number of binary connectives is 0.

Suppose by induction that p1 = c1 + 1 and p2 = c2 + 1 for p1,

p2 the number of propositional symbols and c1, c2 the number of

binary connectives in the wffs ϕ, ψ, respectively. The number of

propositional symbols in (ϕQφ), for Q any of ∨, &, →, and ↔, is

p1 + p2, and the number of connective symbols is c1 + c2 + 1. By the

inductive hypothesis we see that

p1 + p2 = c1 + 1 + c2 + 1 = (c1 + c2 + 1) + 1,

so the claim holds for (ϕQψ).

Finally, consider (¬ϕ). Here the number of binary connectives

and propositional symbols has not changed, so the claim holds.

Exercise 2.5.17. The length of a wff is the number of symbols it

contains, including parentheses. Suppose ϕ is a wff not containing

negation (that is, it comes from the class defined as in Example 2.5.9

but without closure operation (v)). Prove by induction that for each

such ϕ, there is some k ≥ 0 such that the length of ϕ is 4k+1 and the

number of positions at which propositional symbols occur is k + 1.

If we are careful, we can perform induction on N to get results

about other recursively defined classes. For wffs, we might induct on

the number of propositional symbols or the number of binary connec-

tives, for instance.

Exercise 2.5.18. Recall from calculus that a function f is continuous

at a if f(a) is defined and equals limx→a f(x). Recall also the limit

laws, which may be summarized for our purposes as

lim

x→a

(f(x) g(x)) = (lim

x→a

f(x)) (lim

x→a

g(x)), ∈ {+, −, ·,/},

as long as both limits on the right are defined and if = / then

limx→a g(x) = 0. Using those, the basic limits limx→a x = a and