Bridge to Abstract Mathematics: Mathematical Proof and Structures

6.3 EXISTENCE AND UNIQUENESS (OPTIONAL) 217

advanced settings we often give a direct proof of existence with reference
to some abstract axiom asserting existence. We see a demonstration of this
approach in Example 10.
The other approach to proving existence is indirect and based on the
method of reductio ad absurdum. We begin such an argument with an as-
sumption of nonexistence and try to arrive at a contradiction. This approach
is demonstrated in Example 9.

EXAMPLE 7 A subset S of R is said to be bounded above in R if and only
if there exists a real number u such that x 5 u for all x E S. A number
u with this property is called an upper bound for S. Prove that the inter-
val [O,l] is bounded above in R.
Solution Note that a least upper bound of S (cf., Example 4) is, by virtue
of part (i) of its definition, an upper bound for S. Now clearly the real
number 2 has the property that x g 2 for all x E [0,1]. In fact, any real
number not less than 1 could be chosen as u. This is a case in which
an object of the desired type, whose existence we have just demonstrated,
is highly nonunique. 0

EXAMPLE 8 Let f be a function mapping real numbers to real numbers
and let A be a subset of the domain off. We say that a real number y
is in the image of A under f, abbreviated y E f(A), if and only if there
exists x E A such that y = f(x). Prove that 4 E f(A), where f(x) = x2
and A = [O,4].

Solution To prove 4 E f (A), we must produce x E [O, 41 such that 4 =
f (x) = x2. Since 22 = 4 and 2 E [O, 41, we let x = 2. Note that in this
case the, object we have produced to prove existence is also unique, as
you should verify. 0

A famous example of an indirect proof of existence is provided in Exam-

ple 9.

EXAMPLE 9 Prove that there exist infinitely many primes.

Solution If the desired result were false, we could list all the primes; suppose

that p,, p2,... , p, is such a listing. We arrive at a contradiction by con-

structing a number that is not in the list which must be prime. Namely,

let p = (plp2 .:. p,) + 1. Clearly each pi divides the product p,p, -. p,;

hence none of the pi can divide p. For if a certain pi divided both p and

plp2.. p,, then it would divide their difference, which is 1, and con-

sequently would equal 1, a contradiction since 1 is not prime. Since p

is not divisible by any prime, it must itself be prime, thus contradicting

the assumption that all primes had been listed.

Many of the more difficult and sophisticated (i.e., nonelementary) direct

proofs of existence are based on fundamental axioms asserting existence

that have been adopted as a part of the foundations of modern mathematics.