Bridge to Abstract Mathematics: Mathematical Proof and Structures

6.1 CONCLUSIONS INVOLVING V, FOLLOWED BY 3 193

chosen element of U and assuming, that r(x, y, z) is true. The final step

is to conclude from this assumption, and perhaps the hypotheses P, that

s(x, y, z) is true as well.

The descriptions in Example 6 may seem vacuous and, indeed, may
overly abstract at this point, but we predict that you will be drawn back
to this example after studying some actual proofs of this type and especially
in the course of attempting the exercises at the end of the article.
We now begin to consider some specific proofs.

EXAMPLE 7 Prove that if m, n, and p are integers such that m(n and m(p,

then ml(n + p).

Solution Let m, n, and p be integers satisfying the given hypotheses. Ac-

cording to the definition of "divides," we must produce an integer q such

that n + p = mq. The key to the choice of q lies in the hypotheses. Since

m( n, we know that there exists an integer q, such that n = mq,. Since

m ( p, there must exist an integer q, such that p = mq,. Let us look now

at the situation. How are we to arrive at the desired q that will relate

n + p to q? If we note that n + p = mq, + mq, which in turn equals

m(q, + q,), our choice is clear. Resuming the proof now, we make the

assertion "let q = q, + q,." Note first that since q, and q, are integers,

then q, + q, is an integer. Second, note that we have mq = m(q, + q,) =

mql + mq, = n + p, as desired.^0

Here are a few observations regarding the proof in Example 7. You may

object that, according to Example 6, we were to expect q to be defined in

terms of m, n, and p. Instead, q turned out to be defined in terms of q,

and q,. Is there any conflict here? No, because q, depended on n and m,

while q, depended on p and m, so that q ultimately did depend on m, n,

and p, as expected. Second, you should note and avoid a common error in

a proof such as this. In writing out what is known at the start of the proof,

it is easy, but mistaken, to write "since m(n and mlp, then there exists an

integer q such that n = mq and p = mq." There is nothing in the hypotheses

to indicate that the same q works for both of the pairs m, n, and m, p.

Accordingly, the proof must be set up with two different symbols q, and q,

being employed in the two applications of the definition of divides. Finally,

we rewrite the proof in a "final" form: "Assume m, n, and p are integers such

that mln and mlp. We must find an integer q such that n + p = mq. Since

m 1 n and m 1 p, there exist integers q, and q, such that n = mq, and p = mq,.

Let q = q, + q,. Clearly q is an integer and mq = m(q, + q,) = mq, +

mq, = n + p, as desired."

EXAMPLE 8 Let A and B be invertible n x n matrices. Prove that their

product AB is again invertible.