$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

7.3: Existence Proofs; Existence and Uniqueness Proofs

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

Up until this point, we have dealt with proving conditional statements or with statements that can be expressed with two or more conditional statements. Generally, these conditional statements have form $$P(x) \Rightarrow Q(x)$$. (Possibly with more than one variable.) We saw in Section 2.8 that this can be interpreted as a universally quantified statement $$\forall x, P(x) \Rightarrow Q(x)$$.

Thus, conditional statements are universally quantified statements, so in proving a conditional statement—whether we use direct, contrapositive or contradiction proof—we are really proving a universally quantified statement.

But how would we prove an existentially quantified statement? What technique would we employ to prove a theorem of the following form?

$$\exists x, R(x)$$

This statement asserts that there exists some specific object x for which R(x) is true. To prove $$\exists x, R(x)$$ is true, all we would have to do is find and display an example of a specific x that makes R(x) true.

Though most theorems and propositions are conditional (or if-and- only-if) statements, a few have the form $$\exists x, R(x)$$. Such statements are called existence statements, and theorems that have this form are called existence theorems. To prove an existence theorem, all you have to do is provide a particular example that shows it is true. This is often quite simple. (But not always!) Here are some examples:

Proposition There exists an even prime number.

Proof. Observe that 2 is an even prime number.

Admittedly, this last proposition was a bit of an oversimplification. The next one is slightly more challenging.

Proposition There exists an integer that can be expressed as the sum of two perfect cubes in two different ways.

Proof. Consider the number 1729. Note that $$1^3 + 12^3 = 1729$$ and $$9^3 + 10^3 = 1729$$. Thus the number 1729 can be expressed as the sum of two perfect cubes in two different ways.

Sometimes in the proof of an existence statement, a little verification is needed to show that the example really does work. For example, the above proof would be incomplete if we just asserted that 1729 can be written as a sum of two cubes in two ways without showing how this is possible.

WARNING: Although an example suffices to prove an existence statement, a single example does not prove a conditional statement.

Often an existence statement will be embedded inside of a conditional statement. Consider the following. (Recall the definition of gcd on page 116.) If $$a, b \in \mathbb{N}$$, then there exist integers k and l for which $$gcd(a, b) = ak + bl$$.

This is a conditional statement that has the form

$$a,b \in \mathbb{N} \Rightarrow \exists k, l \in \mathbb{Z}, gcd(a,b) = ak+bl$$.

To prove it with direct proof, we would first assume that $$a, b \in \mathbb{N}$$, then prove the existence statement $$\exists k, l \in \mathbb{Z}, gcd(a, b) = ak+bl$$. That is, we would produce two integers k and l (which depend on a and b) for which $$gcd(a, b) = ak+bl$$. Let’s carry out this plan. (We will use this fundamental proposition several times later, so it is given a number.)

Proposition 7.1 If $$a, b \in \mathbb{N}$$, then there exist integers k and l for which $$gcd(a,b) = ak+bl$$.

Proof.(Direct) Suppose $$a, b \in \mathbb{N}$$. Consider the set $$A= \{ax+by : x,y \in \mathbb{Z}\}$$. This set contains both positive and negative integers, as well as 0. (Reason: Let $$y=0$$ and let x range over all integers. Then $$ax+by=ax$$ ranges over all multiples of a, both positive, negative and zero.) Let d be the smallest positive element of A. Then, because d is in A, it must have the form $$d = ak + bl$$ for some specific $$k, l \in \mathbb{Z}$$.

To finish, we will show $$d = gcd(a, b)$$. We will first argue that d is a common divisor of a and b, and then that it is the greatest common divisor. To see that $$d|a$$, use the division algorithm (page 30) to write $$a = qd+r$$ for integers q and r with $$0 \le r < d$$. The equation $$a = qd + r$$ yields

$$r = a−qd$$

$$= a−q(ak+bl)$$

$$= a(1 − qk) + b(−ql)$$.

Therefore r has form $$r = ax+by$$, so it belongs to A. But $$0 \le r < d$$ and d is the smallest positive number in A, so r can’t be positive; hence $$r = 0$$. Updating our equation $$a = qd+r$$, we get $$a = qd$$, so $$d|a$$. Repeating this argument with $$b = qd+r$$ shows $$d|b$$. Thus d is indeed a common divisor of a and b. It remains to show that it is the greatest common divisor.

As $$gcd(a, b)$$ divides a and b, we have $$a = gcd(a, b) \cdot m$$ and $$b = gcd(a, b) \cdot n$$ for some $$m, n \in \mathbb{Z}$$. So $$d = ak+bl$$ $$= gcd(a, b) \cdot mk+gcd(a,b) \cdot nl = gcd(a,b)(mk+nl)$$, and thus d is a multiple of $$gcd(a, b)$$. Therefore $$d \ge gcd(a, b)$$. But d can’t be a larger common divisor of a and b than $$gcd(a, b)$$, so $$d = gcd(a, b)$$.

We conclude this section with a discussion of so-called uniqueness proofs. Some existence statements have form "There is a unique x for which P(x)." Such a statement asserts that there is exactly one example x for which P(x) is true. To prove it, you must produce an example $$x = d$$ or which P(d) is true, and you must show that d is the only such example. The next proposition illustrates this. In essence, it asserts that the set $$\{ax + by : x, y \in \mathbb{Z}\}$$ consists precisely of all the multiples of $$gcd(a, b)$$.

Proposition Suppose $$a, b \in \mathbb{N}$$. Then there exists a unique $$d \in \mathbb{N}$$ for which: An integer m is a multiple of d if and only if $$m = ax+by$$ for some $$x, y \in \mathbb{Z}$$.

Proof. Suppose $$a, b \in \mathbb{N}$$. Let $$d = gcd(a, b)$$. We first show that an integer m is a multiple of d if and only if $$m=ax+by$$ for some $$x,y \in \mathbb{Z}$$. Let $$m = dn$$ be a multiple of d. By Proposition 7.1 (on the previous page), there are integers k and l for which $$d=ak+bl$$. Then $$m = dn = (ak+bl)n = a(kn)+b(ln)$$, so $$m = ax+by$$ for integers $$x = kn$$ and $$y = ln$$.

Conversely, suppose $$m = ax+by$$ for some $$x, y \in \mathbb{Z}$$. Since $$d=gcd(a,b)$$ is a divisor of both a and b, we have $$a = dc$$ and $$b = de$$ for some $$c, e \in \mathbb{Z}$$. Then $$m = ax+by = dcx+dey = d(cx+ey)$$, and this is a multiple of d.

We have now shown that there is a natural number d with the property that m is a multiple of d if and only if $$m=ax+by$$ for some $$x, y \in \mathbb{Z}$$. It remains to show that d is the unique such natural number. To do this, suppose d′ is any natural number with the property that d has:

m is a multiple of d′ $$\Leftrightarrow m= ax+by$$ for some $$x, y \in \mathbb{Z}$$. (7.1)

We next argue that $$d′ = d$$; that is, d is the unique natural number with the stated property. Because of (7.1), $$m=a \cdot 1+b \cdot 0=a$$ is a multiple of d'.

Likewise $$m = a \cdot 0+b \cdot 1=b$$ is a multiple of d'. Hence a and b are both multiples of d′, so d′ is a common divisor of a and b, and therefore $$d′ \le gcd(a, b) = d$$.

But also, by (7.1), the multiple $$m = d′ · 1 = d′$$ of d′ can be expressed as $$d′ =ax+by$$ for some $$x, y \in \mathbb{Z}$$. As noted in the second paragraph of the proof, $$a = dc$$ and $$b = de$$ for some $$c, e \in \mathbb{Z}$$. Thus $$d′ =ax+by = dcx+dey = d(cx+ey)$$, so d′ is a multiple d. As d′ and d are both positive, it follows that

$$d \le d'$$.

We’ve now shown that $$d' \le d$$ and $$d \le d'$$, so$$d = d'$$. The proof is complete.