192 METHODS OF MATHEMATICAL PROOF, PART ll Chapter 6
EXAMPLE 6 Let q(x, y), r(x, y, z), and s(x, y, z) be propositional functions,
where x, y, z come from a common domain of discourse U. Discuss the
basic approach to a proof in each of the following cases, where P rep-
resents a set of hypotheses throughout.
(a) Given P, prove (Vx)(3y)q(x, y)
(b) Given P, prove (Vx)(Qy)(3z)r(x, y, z)
(c) Given P, prove (Vx)(3y)(3z)r(x, y, z)
(d) Given P, prove (Vx)(3y)(Vz)[r(x, y, z) -, s(x, y, z)]
Discussion (a) As we did repeatedly in Chapter 5, we note here that, in
setting up a proof, we should focus on the desired conclusion, with the
hypotheses brought into play only as the proof progresses. In the first
case, the proof should begin "let x E U be given" or "let x be an arbitrary
element of U," or simply "let x E U." Now what must we prove? We
must prove that there exists a corresponding y E U such that q(x, y) is
true; in essence, we must produce a y that, in combination with the given
x, makes the predicate q(x, y) into a true statement. The key in every
such proof (and here is generally where the hypotheses P are used) is to
determine the relationship between y and x, or more accurately, the
dependence of y on x. Proceed in such a proof with the expectation
that the y you are looking for (which may or may not be unique-we
will pursue that issue in Article 6.3) will be defined in terms of x, or pos-
sibly defined in terms of some other quantity that is defined in terms of x.
Specific examples will soon follow, starting with Example 7. After y is
selected, the proof concludes with the (sometimes anticlimactic) verifica-
tion that q(x, y) is true for the arbitrary x and this corresponding y.
(b) Start the proof with the statement "let x E U and y E U be given.
We must produce z E U such that r(x, y, z) is true." In general, it must
be expected that z will depend on both x and y, and that the key to the
choice of z will lie somewhere among the hypotheses P. After z, which
often will be an expression involving x and y explicitly, is selected, the
proof is completed by verifying r(x, y, z).
(c) Start with "let x E U be given. We must produce y E U z E U
such that r(x, y, z) is true." In this case the burden of proof is to produce
two quantities, each of which should be expected to depend on the given
x. The key to the choice of y and z must again be contained in the
hypotheses P.
(d) This is by far the most complicated case, arising in undergrad-
uate mathematics almost exclusively in connection with various limit
concepts. Such a proof should begin "let x E U be given. We must pro-
duce y E U (with y expected to depend on x and perhaps to be defined
in terms of x) having the property that, for any z E U, if r(x, y, z) is true,
then s(x, y, z) is true." Especially critical in this type of proof is the
choice of y. Once y has been designated, the proof concludes (not quite
so anticlimactically as in parts (a)(b)(c)) by letting z be an arbitrarily