214 METHODS OF MATHEMATICAL PROOF, PART II Chapter 6
in particular, never proves existence of a solution. The reasoning under-
lying the two preceding derivations is that if x is a solution to the given
equation, then x must equal $ in the first case, and either 2 or 9 in the
second. That is, these numbers are the only candidates, or possible solu-
tions. Existence is proved in this situation only when it is verified
substitution that at least one of the candidates is an actual solution. In
our examples substitution of x = $ satisfies the first equation, while
substitution of x = 9 satisfies the second. On the other hand, the process
of solving an equation may prove uniqueness, as it did for our first equa-
tion. For the second equation, it was the process of solving the equation,
together with the results of the substitution of the two candidates, that
led to the conclusion of uniqueness.In Example 2 uniqueness is proved, in the concrete setting of an explicit
equation, by showing that only a specific "named" object (i.e., the specific
number x = $ in the first case; the number x = 9 in the second) may have
the desired property, namely, of solving the equation. In more abstract set-
tings there are three other possible approaches to a proof of uniqueness.
The most common is: Assume x, and x, are both objects satisfying the
property p(x).. ; prove that x, = x,. Another approach may be taken
when we are given that p(a) is true for some specific a and are asked to
prove that a is the only such object. In such a case we proceed by letting
x be any object satisfying p(x) and trying to prove x = a. A third approach
to proving uniqueness is argument by contradiction. Each of these three
approaches will be demonstrated in the following section.UNIQUENESS
Our next three examples illustrate proofs of uniqueness in an abstract set-
ting, that is, with no knowledge of a specific object a for which p(a) is true.
In each proof we adopt the approach: Assume that x, and x, are objects
such that p(xl) and p(x2) both hold, and try to prove x, = x,.EXAMPLE 3 Recall from Exercise 10, Article 3.3, that a set Y is called a
complement of a set X if and only if X u Y = U and X n Y = @. Prove
that every set has at most one complement.
Solution Note first that by using the words "at most one complement"
rather than "has a unique complement," we are completely avoiding the
question of existence in this example [see, however, Exercise 2(a)]. We
approach this proof as follows: Given a set X, suppose Y1 and Y, are both
complements of X. We claim Y, = Y,. Now, by our assumption, we have
XuY,=XuY,=U and XnY,=XnY,=@
We could prove Y, = Y, by proving mutual inclusion through the choose
method. Instead, we note that