98
Proofs, Induction, and Number Theory
S e c t i o n 2 . 1 Proof TeChniques
Theorems and Informal Proofs
The formal arguments of Chapter 1 have the form P S Q, where P and Q may
represent compound statements. The point there was to prove that an argument
is valid—true in all interpretations by nature of its internal form or structure,
not because of its content or the meaning of its component parts. However, we
often want to prove arguments that are not universally true but just true within
some context. Meaning becomes important because we are discussing a particular
subject—graph algorithms, or Boolean algebra, or compiler theory, or whatever—
and we want to prove that if P is true in this context, then so is Q. If we can do
this, then P S Q becomes a theorem about that subject. To prove a theorem about
subject XXX, we can introduce facts about XXX into the proof; these facts act
like additional hypotheses. Note that as we add more hypotheses, the universe of
discourse shrinks; we are no longer considering universally valid arguments, only
arguments that are true within the context in which the hypotheses hold.
1
It may not be easy to recognize which subject-specific facts will be helpful or
to arrange a sequence of steps that will logically lead from P to Q. Unfortunately,
there is no formula for constructing proofs and no practical general algorithm or
computer program for proving theorems. Experience is helpful, not only because
you get better with practice, but also because a proof that works for one theorem
can sometimes be modified to work for a new but similar theorem.
Theorems are often stated and proved in a somewhat less formal way than
the propositional and predicate arguments of Chapter 1. For example, a theorem
may express the fact that every object in the domain of interpretation (the subject
matter under discussion) having property P also has property Q. The formal
statement of the theorem would be (4x)[P(x) S Q(x)]. But the theorem would be
informally stated as P(x) S Q(x). If we can prove P(x) S Q(x) where x is treated
as an arbitrary element of the domain, universal generalization would then give
(4x)[P(x) S Q(x)].
As another example, we may know that all objects in the domain have some
property; that is, something of the form (4x)P(x) can be considered as a subjectspecific fact. An informal proof might proceed by saying, “Let x be any element
of the domain. Then x has property P.” (Formally, we are making use of universal
instantiation to get P(x) from (4x)P(x).)
Similarly, proofs are usually not written a step at a time with formal justifications for each step. Instead, the important steps and their rationale are outlined
in narrative form. Such a narrative, however, can be translated into a formal
proof if required. In fact, the value of a formal proof is that it serves as a sort of
insurance—if a narrative proof cannot be translated into a formal proof, it should
be viewed with great suspicion.
1 In the world of “pure predicate logic,” which is a correct and complete formal system, every true (valid)
argument is provable. But in these more restrictive contexts, not everything that is “true” is necessarily
provable, no matter how clever we are in adding additional hypotheses or “axioms.” In other words, these
systems may not be complete. At the age of 25, the German logician Kurt Gödel proved in 1931 that, using
reasonable hypotheses, even elementary arithmetic is an incomplete system. This result shocked the mathematical community of the time, which had been depending on axiomatic systems since the days of Euclid.
Proofs, Induction, and Number Theory
S e c t i o n 2 . 1 Proof TeChniques
Theorems and Informal Proofs
The formal arguments of Chapter 1 have the form P S Q, where P and Q may
represent compound statements. The point there was to prove that an argument
is valid—true in all interpretations by nature of its internal form or structure,
not because of its content or the meaning of its component parts. However, we
often want to prove arguments that are not universally true but just true within
some context. Meaning becomes important because we are discussing a particular
subject—graph algorithms, or Boolean algebra, or compiler theory, or whatever—
and we want to prove that if P is true in this context, then so is Q. If we can do
this, then P S Q becomes a theorem about that subject. To prove a theorem about
subject XXX, we can introduce facts about XXX into the proof; these facts act
like additional hypotheses. Note that as we add more hypotheses, the universe of
discourse shrinks; we are no longer considering universally valid arguments, only
arguments that are true within the context in which the hypotheses hold.
1
It may not be easy to recognize which subject-specific facts will be helpful or
to arrange a sequence of steps that will logically lead from P to Q. Unfortunately,
there is no formula for constructing proofs and no practical general algorithm or
computer program for proving theorems. Experience is helpful, not only because
you get better with practice, but also because a proof that works for one theorem
can sometimes be modified to work for a new but similar theorem.
Theorems are often stated and proved in a somewhat less formal way than
the propositional and predicate arguments of Chapter 1. For example, a theorem
may express the fact that every object in the domain of interpretation (the subject
matter under discussion) having property P also has property Q. The formal
statement of the theorem would be (4x)[P(x) S Q(x)]. But the theorem would be
informally stated as P(x) S Q(x). If we can prove P(x) S Q(x) where x is treated
as an arbitrary element of the domain, universal generalization would then give
(4x)[P(x) S Q(x)].
As another example, we may know that all objects in the domain have some
property; that is, something of the form (4x)P(x) can be considered as a subjectspecific fact. An informal proof might proceed by saying, “Let x be any element
of the domain. Then x has property P.” (Formally, we are making use of universal
instantiation to get P(x) from (4x)P(x).)
Similarly, proofs are usually not written a step at a time with formal justifications for each step. Instead, the important steps and their rationale are outlined
in narrative form. Such a narrative, however, can be translated into a formal
proof if required. In fact, the value of a formal proof is that it serves as a sort of
insurance—if a narrative proof cannot be translated into a formal proof, it should
be viewed with great suspicion.
1 In the world of “pure predicate logic,” which is a correct and complete formal system, every true (valid)
argument is provable. But in these more restrictive contexts, not everything that is “true” is necessarily
provable, no matter how clever we are in adding additional hypotheses or “axioms.” In other words, these
systems may not be complete. At the age of 25, the German logician Kurt Gödel proved in 1931 that, using
reasonable hypotheses, even elementary arithmetic is an incomplete system. This result shocked the mathematical community of the time, which had been depending on axiomatic systems since the days of Euclid.