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
(f(x) g(x)) = (lim
f(x)) (lim
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