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
Previous Page Next Page