Discrete Mathematics and Proof

Existence proof

Is there one? How do you show that something exists without searching forever?

You need

There exists, and there is exactly oneDiscrete Mathematics and Proof

Unlocks

The pigeonhole principleDiscrete Mathematics and Proof

Where you are 14 in Proof techniques

Logic, proof and discrete math6

Proof techniques14

▴ 5 above Proving an if and only if Writing a proof as prose

Existence proof

Proof by cases Proof by contraposition ▾ Show all 14 (4 more)

Why this exists

Many questions in mathematics begin with “is there one?” Is there a real number whose cube plus itself equals 1? Is there a whole number that is a perfect square and a perfect cube? Is there, among any five whole numbers, a pair with some special property?

Searching is the obvious way to answer, and it has two weaknesses. When the collection is infinite the search never ends, and when a search comes up empty it proves nothing, because the thing may be just past where you stopped looking. An existence proof is an argument that settles the question in finitely many steps, whatever the size of the collection.

There is also a lopsidedness that makes existence the friendliest kind of claim to prove. To show that every whole number has a property, no list of examples is ever enough. To show that some whole number has it, a single example is the entire proof.

Definition

A statement that something exists has the form

\exists x \in S\;\; P(x)

read “there is an x in S such that P(x)”. Here S is the collection being searched and P is the property wanted. Every existence claim has a collection, stated or understood: “there is a number with x^2 = 2” means one thing among the real numbers and another among the fractions. The symbol \exists is the existential quantifier, and “exists” always means at least one: one object, ten, or infinitely many all make the statement true.

An existence proof is a proof of a statement of this form. There are two kinds.

A constructive proof names an object c, called a witness, and then checks two things: that c is in S, and that P(c) is true.

A non-constructive proof shows that something in S must have the property without naming one that does. It argues that the opposite, that nothing in S has it, would be impossible.

Intuition

Picture S as a room full of objects and P as a test each object either passes or fails. A constructive proof walks into the room, picks one object up and runs the test in front of you. A non-constructive proof never touches an object. It argues that the room cannot fail the test all the way through: there are more guests than chairs, so two must share a chair.

Both convince, and neither depends on luck. The first tells you more, since you leave holding the object. The second is sometimes the only kind anyone knows, and it is often all a larger argument needs, because knowing that two guests share a chair can be enough to finish a proof without knowing who they are.

Notice what a witness has to do. How c was found, by a guess, by algebra, by a computer search or by a long afternoon, does not appear in the proof. Only the check does, and a check is short even when the search was not.

Results

The witness principle. If c \in S and P(c) is true, then \exists x \in S\;\; P(x). One verified witness is a complete proof of an existence statement.

Existence and “for all” are opposites. The negation of “there exists” is “for all not”:

\neg\, \exists x \in S\;\; P(x) \quad\text{means}\quad \forall x \in S\;\; \neg P(x)

So to prove that nothing has a property, examples are useless and a general argument is needed. In the other direction, to disprove a “for all” claim it is enough to exhibit one counterexample, which is a witness to the negation.

A witness may depend on an earlier choice. A statement of the form \forall n\;\; \exists m\;\; P(n, m) says that whatever n you are handed, some m works. The proof gives a recipe for m in terms of n, or an argument that one exists for every n.

Three tools that prove existence without naming the object.

Pigeonhole principle. If more than n objects are put into n boxes, some box holds at least two of them. (A lesson of its own: The pigeonhole principle.)
Averaging. If n numbers have total T, then at least one of them is at least \dfrac{T}{n}, and at least one is at most \dfrac{T}{n}.
Intermediate value theorem. If f is continuous on [a, b] and f(a) and f(b) have opposite signs, then f(c) = 0 for some c between a and b. (See The intermediate value theorem.)

Why it is true

The witness principle is close to the meaning of the words. “There is an x with P(x)” asks for at least one x with P(x), and c is one.

The negation rule is the same idea from the other side. “Nothing in S has property P” says that each object fails, which is “for all x, not P(x)”.

Why a non-constructive argument counts. Such a proof often assumes that no object in S has the property and derives a contradiction. A statement that leads to a contradiction is false, so some object does have the property. Another form splits into cases that cover every possibility and finds a suitable object in each, as Example 7 does. Either way the proof has not said which object works, and it does not need to.

Pigeonhole. Suppose, for contradiction, that every one of the n boxes holds at most one object. Then there are at most n objects in all. But there are more than n, so some box holds at least two.

Averaging. Suppose every one of the n numbers is less than \dfrac{T}{n}. Adding the n inequalities gives

a_1 + a_2 + \cdots + a_n < n \cdot \frac{T}{n} = T

but the numbers add to exactly T. That is a contradiction, so at least one number is not less than \dfrac{T}{n}. The claim about “at most” follows the same way with every inequality reversed.

Intermediate value theorem. This one is deeper. Its proof rests on the completeness of the real numbers, the fact that the number line has no gaps, and it is not proved here. It is used in Example 6 as a statement that has already been proved.

Worked examples

Example 1

One example is the whole proof

Show that there is a positive integer n for which n^2 - n + 41 is not prime.

Solution

Try small values first:

n	n^2 - n + 41
1	41
2	43
3	47
4	53
5	61
6	71
7	83

Every entry is prime, and in fact the values stay prime all the way up to n = 40. A search could easily make you believe the expression never fails. The statement to prove is only that it fails for some n, so go on to n = 41:

41^2 - 41 + 41 = 41^2 = 41 \cdot 41 = 1681

The number 1681 is a product of two integers larger than 1, so it is not prime. The witness is n = 41, and that is the whole proof. The forty values that came out prime before it neither help nor hurt: one failure is all that “there exists” asks for.

Example 2

A witness that took a genius to find

Show that 2^{32} + 1 is not prime.

Solution

The witness here is a divisor. The number 641 divides 2^{32} + 1, because

\begin{aligned} 641 \times 6\,700\,417 &= 4\,294\,700\,000 + 267\,297 \\ &= 4\,294\,967\,297 \end{aligned}

where 641 \times 6\,700\,000 = 4\,294\,700\,000 and 641 \times 417 = 267\,297. And 2^{32} = 4\,294\,967\,296, so 2^{32} + 1 = 4\,294\,967\,297. The two match.

So 2^{32} + 1 is a product of two integers larger than 1, and it is not prime.

This example shows the lopsidedness in a striking way. Finding 641 was a real discovery, made by Euler in the eighteenth century, and before it the numbers 2^{2^k} + 1 had looked as though they might all be prime. Checking 641 takes two lines of arithmetic. A witness can be very hard to find and still very easy to verify, and only the verifying belongs in the proof.

Example 3

A witness found by algebra

Show that there are real numbers a and b with a + b = 6 and ab = 7.

Solution

Some scratch work finds candidates. From a + b = 6 we get b = 6 - a, so the second condition reads a(6 - a) = 7, which rearranges to a^2 - 6a + 7 = 0. The quadratic formula gives \displaystyle a = 3 \pm \sqrt{2}.

The scratch work is not the proof. The proof is the check. Take \displaystyle a = 3 + \sqrt{2} and \displaystyle b = 3 - \sqrt{2}. Both are real numbers, and

\begin{aligned} a + b &= 6 \\ ab &= 3^2 - (\sqrt{2})^2 = 9 - 2 = 7 \end{aligned}

Both conditions hold, so such a pair exists.

Had the problem asked for ab = 10, the same algebra would give a^2 - 6a + 10 = 0, whose discriminant is 36 - 40 = -4. That is negative, so no real numbers qualify. Whether a witness exists depends on the collection S as well as on the property.

Example 4

Five integers and division by four

Show that among any five integers there are two whose difference is divisible by 4.

Solution

The claim is about every set of five integers, so no list of examples will prove it. Sort the integers by their remainder on division by 4. The possible remainders are 0, 1, 2 and 3: four boxes.

Figure 1Five numbers sorted by their remainder on division by 4. Two land in one box, here 6 and 30.

Five integers go into four boxes, so by the pigeonhole principle some box holds two of them. Call them a and b, with the same remainder r. Then a = 4p + r and b = 4q + r for some integers p and q, and

a - b = 4p + r - 4q - r = 4(p - q)

which is a multiple of 4.

Figure 1 shows one set of five, 6, 11, 17, 24, 30, and the pair the argument finds, 6 and 30, with difference 24 = 4 \cdot 6. The proof is non-constructive: it guarantees a pair in every set without saying which pair, and for a given set you would look at the boxes to find it.

Example 5

Twenty-five students and a pile of books

Twenty-five students have read 130 books between them, counting each book once for each student who read it. Show that some student has read at least 6 books.

Solution

Suppose, for contradiction, that every student has read at most 5 books. Then the total is at most

25 \times 5 = 125

But the total is 130, and 130 > 125. This is a contradiction, so some student has read at least 6 books.

The average is 130 \div 25 = 5.2, and averaging says some student is at or above that. Book counts are whole numbers, so “at least 5.2” means “at least 6”. The proof does not identify the student. The argument used only the total, so it could not.

Example 6

A sign change and the intermediate value theorem

Show that the equation x^3 + x - 1 = 0 has a real solution between 0 and 1.

Solution

Let f(x) = x^3 + x - 1. A polynomial is continuous everywhere, so the intermediate value theorem applies on [0, 1]. Evaluate the ends:

\begin{aligned} f(0) &= -1 < 0 \\ f(1) &= 1 + 1 - 1 = 1 > 0 \end{aligned}

Figure 2The curve starts below the axis and ends above it, so it crosses the axis somewhere between.

The values have opposite signs, so the curve starts below the axis and ends above it. By the theorem there is a number c between 0 and 1 with f(c) = 0.

No formula for c came out of this, and none is needed for the claim. The same idea can still close in on c as far as you like. Since f(0.68) = -0.005568 < 0 and f(0.7) = 0.043 > 0, the number c lies between 0.68 and 0.7, and repeating the step narrows it further.

The theorem says there is at least one solution. That there is only one is a separate argument, the subject of There is exactly one.

Example 7

Two irrational numbers with a rational power

Show that there exist irrational numbers a and b such that a^b is rational.

Solution

We use the fact, proved in The square root of 2 is irrational, that \displaystyle \sqrt{2} is irrational. Consider the number

t = \sqrt{2}^{\,\sqrt{2}}

Either t is rational or it is not, and the proof goes through in both cases.

Case 1: t is rational. Take \displaystyle a = \sqrt{2} and \displaystyle b = \sqrt{2}. Both are irrational, and a^b = t is rational.

Case 2: t is irrational. Take a = t and \displaystyle b = \sqrt{2}. Both are irrational, and

a^b = \left(\sqrt{2}^{\,\sqrt{2}}\right)^{\sqrt{2}} = \sqrt{2}^{\,\sqrt{2}\cdot\sqrt{2}} = \sqrt{2}^{\,2} = 2

which is rational.

In either case a suitable pair exists. This is a proof that an object exists without a witness being named: the argument does not say which case is true, so it does not say which pair works.

A witness can be named with more work. Take \displaystyle a = \sqrt{2} and b = 2\log_2 3. Then a^b = 2^{\log_2 3} = 3. The number b = \log_2 9 is irrational, because if b = \dfrac{p}{q} with positive integers p and q, then 2^p = 9^q, and the left side is even while the right side is odd. The first proof was quicker, and the second tells you more.

Example 8

A witness that depends on n

Show that for every positive integer n there are n consecutive integers that are all composite, meaning not prime.

Solution

The claim is of the form \forall n\;\; \exists\,\text{a run}, so the witness will depend on n. Consider the n numbers (n+1)! + k, for k = 2, 3, \ldots, n+1. Here (n+1)! is the product 1 \cdot 2 \cdots (n+1). They are consecutive, and there are n of them.

Take one of them, (n+1)! + k, where k is any integer from 2 to n+1. The factor k divides (n+1)!, because k is one of the numbers multiplied together to make it. It also divides k. So k divides the sum (n+1)! + k. That number is larger than k, and k \ge 2, so the sum has a divisor that is neither 1 nor itself. It is composite.

For n = 5 the run is 722, 723, 724, 725, 726, since 6! = 720:

\begin{aligned} 722 &= 2 \cdot 361 & 723 &= 3 \cdot 241 \\ 724 &= 4 \cdot 181 & 725 &= 5 \cdot 145 \\ 726 &= 6 \cdot 121 \end{aligned}

This shows that the gaps between one prime and the next can be as long as you like, which is the first fact in the study of gaps between primes.

Boundaries

An existence proof says “at least one”, and nothing more. It does not say how many, and it does not say which. Whether there is exactly one is a separate question with its own argument, taken up in There is exactly one and There exists, and there is exactly one. A proof that one object exists does not show that it is the only one, and a proof that there is at most one does not show that there is any.

The collection matters. “There is a solution of x^2 = 2” is true among the real numbers and false among the fractions. “There is a real x with x^2 + 1 = 0” is false, though there are two complex ones. A witness has to belong to the collection the statement names.

A failed search proves nothing. “No such object exists” is a statement about every object in the collection, so it needs a general argument. Nobody has found an odd perfect number, and nobody has proved there is none. A witness can settle a claim that something exists; the absence of one settles nothing.

Existence cannot be assumed along the way. An argument that begins “take the smallest positive real number” has already gone wrong, because there is none: if s were the smallest, then \dfrac{s}{2} would be smaller. Before reasoning about an object, the existence of that object has to have been proved.

Non-constructive proofs lean on one principle of logic. They use the fact that every statement is either true or false, so that a statement which leads to a contradiction is false and its opposite is true, and a split into “rational or not”, as in Example 7, misses no case. Nearly all of mathematics accepts this. A school of thought called constructivism does not, and accepts an existence claim only when a witness can be produced.

An empty collection has no witness. If S has no elements, then \exists x \in S\;\; P(x) is false for every property P.

Where this goes next

The pigeonhole principle, used above, turns into a whole branch of counting arguments in its own lesson. The intermediate value theorem is the standard way to show that an equation has a solution in calculus.

The harder companion is uniqueness. Proving that an object exists and that it is the only one are separate jobs, and There is exactly one and There exists, and there is exactly one take the second half. Finding a counterexample to a claim, as in the lesson on it, is an existence proof wearing a different label: it is a witness to the negation.

Existence also drives the great theorems about the primes. Euclid’s proof that there are infinitely many is the statement “for every list of primes there is a prime not on it”. Arguments that go by Proof by contradiction are often existence proofs in this non-constructive style.

Exercises

Exhibit a witness

Show that there is an integer n for which n^2 + n + 41 is not prime.
Show that there is a positive integer that can be written as the sum of two positive cubes in two different ways.
Show that there is a positive integer, other than 1, that is both a perfect square and a perfect cube.
Show that there is a real number x with x + \dfrac{1}{x} = \dfrac{5}{2}.

Find the witness by solving

Show that there are real numbers a and b with a + b = 8 and ab = 13.
Show that there are real numbers a and b with a + b = 5 and a^2 + b^2 = 13.
Is there a real number x with x^2 + 4x + 5 = 0? Is there a complex number? Explain.

Pigeonholes and averages

Show that among any eight integers there are two whose difference is divisible by 7.
Seven whole numbers add to 100. Show that at least one of them is at least 15.
Eleven different numbers are chosen from 1, 2, \ldots, 20. Show that two of the chosen numbers are consecutive.

Sign changes

Show that x^3 - 3x + 1 = 0 has a real solution between 0 and 1.
Show that \cos x = x has a solution between 0 and 1, where x is measured in radians.
Show that x^3 - 6x^2 + 9x - 2 = 0 has at least three different real solutions, by finding three intervals with sign changes.

A witness that depends on n

Show that for every positive integer n there are n consecutive positive integers, none of which is a perfect square.
Write down seven consecutive composite integers, and give a divisor of each.

Reasoning

Suppose you test the first thousand positive integers and none of them has a certain property. Explain why you may not conclude that no positive integer has it.
Write the negation of “there is a real number x with x^2 < 0”, and say which of the two statements is true.
True or false: for every real number a there is a real number b with ab = 1. Explain.
Prove that there are two irrational numbers whose sum is rational.
In the proof of Example 7, the argument never decides whether \displaystyle \sqrt{2}^{\,\sqrt{2}} is rational. Explain why the proof is still complete.
Prove that among any three integers there are two whose sum is even.
Prove that in any group of six people, there are three who all know each other or three who are all strangers to each other. (Assume that, for each pair, either they know each other or they do not.)

Answers

Take n = 40. Then n^2 + n + 41 = 1681, since 1600 + 40 + 41 = 1681. And 1681 = 41 \cdot 41, which is not prime. (Other values also work, for example n = 41.)
1729. It equals 1^3 + 12^3 = 1 + 1728 and also 9^3 + 10^3 = 729 + 1000, two different ways.
64. It equals 8^2 and also 4^3. (729 = 27^2 = 9^3 also works.)
x = 2. Then 2 + \dfrac{1}{2} = \dfrac{5}{2}. (x = \dfrac{1}{2} also works.)
Take \displaystyle a = 4 + \sqrt{3} and \displaystyle b = 4 - \sqrt{3}. Then a + b = 8 and ab = 16 - 3 = 13. These come from a^2 - 8a + 13 = 0, where \displaystyle a = 4 \pm \sqrt{3}.
a = 2, b = 3. Then a + b = 5 and a^2 + b^2 = 4 + 9 = 13. To find them, note that (a + b)^2 = 25 gives ab = \dfrac{25 - 13}{2} = 6, and then a and b are the roots of t^2 - 5t + 6 = 0.
There is no real solution, but there is a complex one. Since x^2 + 4x + 5 = (x + 2)^2 + 1 and a real square is never negative, the left side is at least 1, never 0. For the complex number x = -2 + i, we have (-2 + i)^2 = 3 - 4i and 4(-2 + i) = -8 + 4i. Adding 5 gives 3 - 4i - 8 + 4i + 5 = 0.
Sort the integers by their remainder on division by 7. There are seven possible remainders, so seven boxes, and eight integers. Some box holds two of them, a = 7p + r and b = 7q + r, and then a - b = 7(p - q).
Suppose every one of the seven numbers is at most 14. Then the total is at most 7 \times 14 = 98, but it is 100. Contradiction, so some number is at least 15.
Make ten boxes: \{1, 2\}, \{3, 4\}, \ldots, \{19, 20\}. Every number from 1 to 20 is in exactly one box. Eleven chosen numbers go into ten boxes, so two share a box, and two numbers in one of these boxes are consecutive.
Let f(x) = x^3 - 3x + 1, which is continuous. Then f(0) = 1 > 0 and f(1) = 1 - 3 + 1 = -1 < 0. The signs differ, so by the intermediate value theorem f(c) = 0 for some c between 0 and 1.
Let f(x) = \cos x - x, which is continuous. Then f(0) = 1 > 0 and f(1) = \cos 1 - 1 \approx -0.46 < 0. The signs differ, so f(c) = 0 for some c between 0 and 1, and that c solves \cos c = c.
Let f(x) = x^3 - 6x^2 + 9x - 2. Then f(0) = -2, f(1) = 2, f(3) = -2 and f(4) = 2. There is a sign change on each of (0, 1), (1, 3) and (3, 4), so f has a root in each. These three intervals do not overlap, so the three roots are different. (In fact f(x) = (x - 2)(x^2 - 4x + 1), and the roots are \displaystyle 2 - \sqrt{3}, 2 and \displaystyle 2 + \sqrt{3}.)
Take n^2 + 1, n^2 + 2, \ldots, n^2 + n. There are n of them and they are consecutive. The nearest squares are n^2 and (n + 1)^2 = n^2 + 2n + 1, and all n numbers lie strictly between these two, so none is a perfect square. For example, n = 6 gives 37, 38, 39, 40, 41, 42, between 36 and 49.
One answer is 40322 to 40328, which is 8! + 2 to 8! + 8 with 8! = 40320. Each has a divisor: 40322 = 2 \cdot 20161, 40323 = 3 \cdot 13441, 40324 = 4 \cdot 10081, 40325 = 5 \cdot 8065, 40326 = 6 \cdot 6721, 40327 = 7 \cdot 5761 and 40328 = 8 \cdot 5041. (Example 8 gives the recipe. A run of smaller numbers also works: 90 to 96.)
“No positive integer has it” says that every positive integer fails, which is a claim about infinitely many numbers, and a thousand cases are a tiny part of them. The property might first appear at the thousand and first. Example 1 is a small version of this: the expression n^2 - n + 41 is prime for n = 1 up to 40, and then fails at n = 41.
The negation is “for every real number x, x^2 \ge 0”. The negation is true, since a real square is never negative, so the original statement is false.
False. The statement is \forall a\;\; \exists b\;\; ab = 1. Take a = 0: then ab = 0 for every b, and no b gives 1. A single counterexample, which is a witness to the negation, is enough.
Take \displaystyle \sqrt{2} and \displaystyle -\sqrt{2}. Both are irrational: if \displaystyle -\sqrt{2} were a fraction, then \displaystyle \sqrt{2}, its negative, would be one too. Their sum is 0, which is rational.
Every case of the argument ends with a valid pair. If \displaystyle t = \sqrt{2}^{\,\sqrt{2}} is rational, the pair \displaystyle \sqrt{2}, \sqrt{2} works, and if it is irrational, the pair \displaystyle t, \sqrt{2} works. Rational and irrational are the only two possibilities, so one of the two pairs works. To prove that a pair exists it is enough to know that at least one of these pairs works, and it is not necessary to know which.
Each integer is even or odd, so sort the three into two boxes by parity. By the pigeonhole principle, some box has two of them. Two even integers add to an even integer, and two odd integers add to an even integer, since (2p + 1) + (2q + 1) = 2(p + q + 1).
Pick one person, A. Each of the other five either knows A or is a stranger to A, which is two boxes. If each box held at most two people there would be at most four, so some box holds at least three people. Call three of them B, C and D. Suppose first that B, C and D all know A. If some two of them know each other, say B and C, then A, B and C all know each other. If no two of them know each other, then B, C and D are three mutual strangers. Suppose instead that B, C and D are all strangers to A. If some two of them are strangers to each other, say B and C, then A, B and C are three mutual strangers. If no two of them are strangers, then B, C and D all know each other. Every case produces three people who all know each other or three who are all strangers.