Skip to main content
\(\newcommand{\versionNum}{$4.0$\ } \renewcommand{\tabcolsep}{2.4pt} \def\savedlnot{\lnot} \renewcommand{\arraystretch}{.63} \renewcommand{\arraystretch}{1} \renewcommand{\Naturals}{{\mathbb Z}^{\mbox{\tiny noneg}} } \renewcommand{\arraystretch}{.9} \renewcommand{\arraystretch}{.77} \newcommand{\hint}[1]{ } \newcommand{\inlinehint}[1]{ } \newcommand{\sageprompt}{ \texttt{sage$>$} } \newcommand{\tab}{} \newcommand{\blnk}{\rule{.4pt}{1.2pt}\rule{9pt}{.4pt}\rule{.4pt}{1.2pt}} \newcommand{\suchthat}{\; \;} \newcommand{\divides}{\!\mid\!} \newcommand{\tdiv}{\; \mbox{div} \;} \newcommand{\restrict}[2]{#1 \,_{\,#2}} \newcommand{\lcm}[2]{\mbox{lcm} (#1, #2)} \renewcommand{\gcd}[2]{\mbox{gcd} (#1, #2)} \newcommand{\Naturals}{{\mathbb N}} \newcommand{\Integers}{{\mathbb Z}} \newcommand{\Znoneg}{{\mathbb Z}^{\mbox{\tiny noneg}}} \newcommand{\Zplus}{{\mathbb N}} \newcommand{\Enoneg}{{\mathbb E}^{\mbox{\tiny noneg}}} \newcommand{\Qnoneg}{{\mathbb Q}^{\mbox{\tiny noneg}}} \newcommand{\Rnoneg}{{\mathbb R}^{\mbox{\tiny noneg}}} \newcommand{\Rationals}{{\mathbb Q}} \newcommand{\Reals}{{\mathbb R}} \newcommand{\Complexes}{{\mathbb C}} \newcommand{\relQ}{\mbox{\textsf Q}} \newcommand{\relR}{\mbox{\textsf R}} \newcommand{\nrelR}{\mbox{$\not${\textsf R}}} \newcommand{\relS}{\mbox{\textsf S}} \newcommand{\relA}{\mbox{\textsf A}} \newcommand{\Dom}[1]{\mbox{Dom}(#1)} \newcommand{\Cod}[1]{\mbox{Cod}(#1)} \newcommand{\Rng}[1]{\mbox{Rng}(#1)} \DeclareMathOperator{\caret}{$\scriptstyle\wedge$} \renewcommand{\arraystretch}{.77} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section3.6Proofs and disproofs of existential statements

From a certain point of view, there is no need for the current section. If we are proving an existential statement we are disproving some universal statement. (Which has already been discussed.) Similarly, if we are trying to disprove an existential statement, then we are actually proving a related universal statement. Nevertheless, sometimes the way a theorem is stated emphasizes the existence question over the corresponding universal — and so people talk about proving and disproving existential statements as a separate issue from universal statements.

Proofs of existential questions come in two basic varieties: constructive and non-constructive. Constructive proofs are conceptually the easier of the two — you actually name an example that shows the existential question is true. For example:

Exercise3.6.2

The Fibonacci numbers are defined by the initial values \(F(0)=1\) and \(F(1)=1\) and the recursive formula \(F(n+1) = F(n)+F(n-1)\) (to get the next number in the series you add the last and the penultimate).

\(n\) \(F(n)\)
0 1
1 1
2 2
3 3
4 5
5 8
\(\vdots\) \(\vdots\)

Prove that there is a Fibonacci number that is a perfect square.

A non-constructive existence proof is trickier. One approach is to argue by contradiction — if the thing we're seeking doesn't exist that will lead to an absurdity. Another approach is to outline a search algorithm for the desired item and provide an argument as to why it cannot fail!

A particularly neat approach is to argue using dilemma. This is my favorite non-constructive existential theorem/proof.

Many existential proofs involve a property of the natural numbers known as the well-ordering principle. The well-ordering principle is sometimes abbreviated WOP. If a set has WOP it doesn't mean that the set is ordered in a particularly good way, but rather that its subsets are like wells — the kind one hoists water out of with a bucket on a rope. You needn't be concerned with WOP in general at this point, but notice that the subsets of the natural numbers have a particularly nice property — any non-empty set of natural numbers must have a least element (much like every water well has a bottom).

Because the natural numbers have the well-ordering principle we can prove that there is a least natural number with property X by simply finding any natural number with property X — by doing that we've shown that the set of natural numbers with property X is non-empty and that's the only hypothesis the WOP needs.

For example, in the exercises in Section 3.5 we introduced vampire numbers. A vampire number is a \(2n\) digit number \(v\) that factors as \(v=xy\) where \(x\) and \(y\) are \(n\) digit numbers and the digits of \(v\) are the union of the digits in \(x\) and \(y\) in some order. The numbers \(x\) and \(y\) are known as the “fangs” of \(v\). To eliminate trivial cases, pairs of trailing zeros are disallowed.

This is quite an interesting situation in that we know there is a smallest 6-digit vampire number without having any idea what it is!

Exercise3.6.5

Show that \(102510\) is the smallest 6-digit vampire number.

There are quite a few occasions when we need to prove statements involving the unique existence quantifier (\(\exists !\)). In such instances we need to do just a little bit more work. We need to show existence — either constructively or non-constructively — and we also need to show uniqueness. To give an example of a unique existence proof we'll return to a concept first discussed in Section 1.5 and finish-up some business that was glossed-over there.

Recall the Euclidean algorithm that was used to calculate the greatest common divisor of two integers \(a\) and \(b\) (which we denote \(\gcd{a}{b}\)). There is a rather important question concerning algorithms known as the “halting problem.” Does the program eventually halt, or does it get stuck in an infinite loop? We know that the Euclidean algorithm halts (and outputs the correct result) because we know the following unique existence result. \begin{equation*} \forall a, b \in \Integers^+, \, \exists ! \, d \in \Integers^+ \; \mbox{such that} \, d=\gcd{a}{b} \end{equation*}

Now, before we can prove this result, we'll need a precise definition for \(\gcd{a}{b}\). Firstly, a gcd must be a common divisor which means it needs to divide both \(a\) and \(b\). Secondly, among all the common divisors, it must be the largest. This second point is usually addressed by requiring that every other common divisor divides the gcd. Finally we should note that a gcd is always positive, for whenever a number divides another number so does its negative, and whichever of those two is positive will clearly be the greater! This allows us to extend the definition of gcd to all integers, but things are conceptually easier if we keep our attention restricted to the positive integers.

Definition3.6.6

The greatest common divisor, or gcd, of two positive integers \(a\) and \(b\) is a positive integer \(d\) such that \(d \divides a\) and \(d \divides b\) and if \(c\) is any other positive integer such that \(c \divides a\) and \(c \divides b\) then \(c \divides d\). \begin{equation*} \forall a,b,c,d \in \Integers^+ \; d=\gcd{a}{b} \; \iff \; d \divides a \, \land \, d \divides b \, \land \, (c \divides a \, \land \, c \divides b \implies c \divides d) \end{equation*}

Armed with this definition, let's return our attention to proving the unique existence of the gcd. The uniqueness part is easier so we'll do that first. We argue by contradiction. Suppose that there were two different numbers \(d\) and \(d'\) satisfying the definition of \(\gcd{a}{b}\). Put \(d'\) in the place of \(c\) in the definition to see that \(d' \divides d\). Similarly, we can deduce that \(d \divides d'\) and if two numbers each divide into the other, they must be equal. This is a contradiction since we assumed \(d\) and \(d'\) were different.

For the existence part we'll need to define a set — known as the \(\Integers\)-module generated by \(a\) and \(b\) — that consists of all numbers of the form \(xa+yb\) where \(x\) and \(y\) range over the integers.

\(\Integers\)\(\Integers\)\(21\)\(15\)\(21x+15y\)\((x,y)\)

This set has a very nice geometric character that often doesn't receive the attention it deserves. Every element of a \(\Integers\)-module generated by two numbers (\(15\) and \(21\) in the example) corresponds to a point in the Euclidean plane. As indicated in <<Unresolved xref, reference "fig_zmodule"; check spelling or use "provisional" attribute>> there is a dividing line between the positive and negative elements in a \(\Integers\)-module. It is also easy to see that there are many repetitions of the same value at different points in the plane.

Exercise3.6.7

The value \(0\) clearly occurs in a \(\Integers\)-module when both \(x\) and \(y\) are themselves zero. Find another pair of \((x,y)\) values such that \(21x+15y\) is zero. What is the slope of the line which separates the positive values from the negative in our \(\Integers\)-module?

In thinking about this \(\Integers\)-module, and perusing <<Unresolved xref, reference "fig_zmodule"; check spelling or use "provisional" attribute>>, you may have noticed that the smallest positive number in the \(\Integers\)-module is 3. If you hadn't noticed that, look back and verify that fact now.

Exercise3.6.8

How do we know that some smaller positive value (a \(1\) or a \(2\)) doesn't occur somewhere in the Euclidean plane?

What we've just observed is a particular instance of a general result.

Subsection3.6.1Exercises

  1. Show that there is a perfect square that is the sum of two perfect squares. \hint{Can you say "Pythagorean triple"? I thought you could.}

  2. Show that there is a perfect cube that is the sum of three perfect cubes. \hint{Hint: \(6^3\) can be expressed as such a sum.}

  3. Show that the WOP doesn't hold in the integers. (This is an existence proof, you show that there is a subset of \(\Integers\) that doesn't have a smallest element.) \hint{How about even integers? Is there a smallest one? That's my example! You come up with a different one!}

  4. Show that the WOP doesn't hold in \(\Rationals^+\). \hint{Consider the set \(\{ 1, 1/2, 1/4, 1/8, \ldots \}\). Does it have a smallest element?}

  5. In the proof of Theorem 3.6.9 we weaseled out of showing that \(d \divides b\). Fill in that part of the proof. \hint{Yeah, I'm going to keep weaseling…}

  6. Give a proof of the unique existence of \(q\) and \(r\) in the division algorithm. \hint{Unique existence proofs consist of two parts. First, just show existence. Then, show that if there were two of the things under consideration that they must in fact be equal.}

  7. A digraph is a drawing containing a collection of points that are connected by arrows. The game known as scissors-paper-rock can be represented by a digraph that is balanced (each point has the same number of arrows going out as going in). Show that there is a balanced digraph having 5 points. \ifx\SetFigFont\undefined\gdef\SetFigFont#1#2#3#4#5{ \reset@font\fontsize{#1}{#2pt} \fontfamily{#3}\fontseries{#4}\fontshape{#5} \selectfont}\fi \hint{If at first you don't succeed… try googling “scissor paper rock lizard spock.”}