Proofs of Existence - Existence and Definitions

Mathematical Writing - Vivaldi Franco 2014

Proofs of Existence
Existence and Definitions

Franco Vivaldi1

(1)

School of Mathematical Sciences, Queen Mary, University of London, London, UK

Franco Vivaldi

Email: f.vivaldi@qmul.ac.uk

In this chapter we take a closer look at existence statements. These statements assert that there exists a quantity $$x$$ that has a certain property $${\fancyscript{P}}$$. In symbols:

$$\exists x\in X,{\fancyscript{P}}(x)$$

where $$X$$ is a set and $${\fancyscript{P}}$$ is a predicate over $$X$$. For example, the statement

The integer $$10^9$$ is the sum of two primes

asserts the existence of a pair of prime numbers with a given sum (what are $$X$$ and $${\fancyscript{P}}$$ in this case?).

We shall discuss proofs of existence and the connection between existence and definitions.

9.1 Proofs of Existence

To prove that something exists it is not necessary that the object in question be constructed explicitly. For example, Euclid’s proof of the infinitude of primes (Sect. 7.5) establishes the existence of infinitely many things without producing any of them. By contrast, we proved that Euler’s polynomial $$n^2+n+41$$ is composite for infinitely many values of $$n$$ by exhibiting such values explicitly (Eq. 7.8).

Accordingly, existence proofs are said to be constructive if an explicit construction is given, and non-constructive if no explicit construction is given. The constructive method may be described as a two-stage process :

(WHAT?) Identify an element $$x$$ of $$X$$.

(WHY?) Show that $${\fancyscript{P}}(x)$$ is TRUE.

The format of the proof should make clear which part is the WHAT and which part is the WHY.

·  We begin with a constructive existence proof [31, p. 13]:

Theorem

There is a real number $$\alpha $$ such that $$\alpha ^{2} = 2$$.

PROOF Draw a square of side 1.

(WHAT?)

Let $$\alpha $$ be the length of a diagonal of the square.

(WHY?)

Then by Pythagoras, $$\alpha ^2 = 2$$. $$\square $$

This minimalist proof takes for granted that the length of a diagonal of the unit square is a real number. A justification of this step requires the tools of analysis.

Let us re-visit the counterexample (7.8) concerning Euler’s polynomial.

Theorem

There are infinitely many integers $$n$$ for which $$p(n)=n^2+n+41$$ is composite.

PROOF

(WHAT?)

Let $$n=41k$$, for $$k\in \mathbb {N}$$.

(WHY?)

Then $$p(41k)=41(41k^2+k+1)$$, not a prime. $$\square $$

In this proof the WHAT part identifies an infinite sequence of integers.

Theorem

If two integers are the sum of two squares, then so is their product.

This statement is an implication; the existence statement in the deduction is conditional to another existence statement in the hypothesis. We give a concise constructive proof, where an eloquent formula supplies at once the WHATs and the WHYs.

PROOF This statement follows from the algebraic identity

$$ (j^2+k^2)(m^2+n^2)=(jm+kn)^2+(km-jn)^2. $$

$$\square $$

Many non-constructive existence proofs employ contradiction. One assumes that the object being defined does not exist, and derives a false statement. It is not surprising that an argument of this kind could fail to provide information about the object in question.

However, not all non-constructive existence proofs use contradiction.

Theorem

There is an irrational number $$a$$ such that $$a^{\sqrt{2}}$$ is rational.

PROOF Consider $$\sqrt{2}^{\sqrt{2}}$$. We have two cases:

CASE I: $$\sqrt{2}^{\sqrt{2}}$$ is rational. Then $$a=\sqrt{2}$$ is as required.

CASE II: $$\sqrt{2}^{\sqrt{2}}$$ is irrational. Then

$$ \left( \sqrt{2}^{\sqrt{2}}\right) ^{\sqrt{2}} = (\sqrt{2})^{\sqrt{2}\sqrt{2}} = (\sqrt{2})^2 = 2, $$

so $$a = \sqrt{2}^{\sqrt{2}}$$ is as required. $$\square $$

This is a proof by cases—see Sect. 7.2. We note that we aren’t given a WHAT. There are two different WHATs, and we have no idea which of them works for the WHY.

Our next example is a well-known existence statement, Dirichlet’s box principle (or the pigeon-hole principle) .

Theorem

Given $$n$$ boxes and $$m$$ objects in them, if $$m>n$$, then at least one box contains more than one object.

The proof of this rather self-evident implication is necessarily non-constructive. We use contradiction, namely the both ends method described in Sect. 7.5. It’s easy to predict where contradiction will lead us.

PROOF Let $$m$$ and $$n$$ be integers, and let $$m_j$$ be the number of objects in the $$j$$th box. Assume that $$m>n$$ but $$m_j\leqslant 1$$, for $$j=1,\ldots ,n$$. Then

$$ m=\sum _{j=1}^n m_j\leqslant \sum _{j=1}^n 1 =n $$

giving $$m\leqslant n$$, contrary to the assumption. $$\square $$

In this proof we are not given the WHAT, and hence there cannot be a WHY step either. The proof begins by introducing the symbol $$m_j$$; this simple but important step makes the rest immediate.

The non-constructive proof of the following statement employs Dirichlet’s box principle.

Theorem

In any set of integers with more than $$n$$ elements there must be two integers whose difference is divisible by $$n$$.

PROOF Let $$n$$ be given, and let $$S$$ be a set of $$m$$ integers, with $$n<m$$. We divide each element of $$S$$ by $$n$$, obtaining $$m$$ integer remainders. These remainders can assume at most $$n$$ distinct values, and therefore two elements of $$S$$, say $$x_i$$ and $$x_j$$, must have the same remainder, by Dirichlet’s box principle. But then $$x_i-x_j$$ gives reminder zero when divided by $$n$$, as desired. $$\square $$

Solving equations is a quintessential mathematical task. In some cases we may be looking for a particular number, which means that we are after a constructive existence proof. In other cases we may be satisfied by a proof that a solution exists at all, or that it exists in a specified range of values of the argument. Let us examine a constructive and a non-constructive existence proof of the same statement.

Proposition

The equation $$x^4-10x^2+1=0$$ has four distinct real solutions.

CONSTRUCTIVE PROOF Let $$f(x)=x^4-10x^2+1$$.

(WHAT?) Let $$x_\pm =\sqrt{3}\pm \sqrt{2}$$; then $$x_\pm $$ are real numbers.

(WHY?) We compute, using the binomial theorem

$$\begin{aligned} f(x_\pm )&=(\sqrt{3}\pm \sqrt{2})^4-10(\sqrt{3}\pm \sqrt{2})^2+1\\&=9\pm 12\sqrt{6}+36\pm 8\sqrt{6}+4-30\mp 20\sqrt{6}-20+1\\&=0 \end{aligned}$$

where the top and bottom signs in $$\pm $$ and $$\mp $$ match. The above calculation shows that $$x_\pm $$ are roots of $$f$$. Since the real numbers $$x_\pm $$ are positive and distinct, and $$f$$ is an even function, we conclude that $$-x_\pm $$ are also roots of $$f$$. $$\square $$

This constructive existence proof involved ’guessing’ the solutions, and then verifying that the guess was correct.1

NON-CONSTRUCTIVE PROOF Let $$f(x)=x^4-10x^2+1$$. The computation

$$ f(0)=1\qquad f(1)=-8 \qquad f(4)=97, $$

shows that $$f$$ changes sign twice in the interval $$(0,4)$$. Because $$f$$ is continuous, there exist two distinct real numbers $$x_-, x_+$$ in the open intervals $$(0,1)$$ and $$(1,4)$$, respectively, at which the function $$f$$ vanishes. The real numbers $$-x_\pm $$ are also roots of $$f$$, because $$f$$ is even. The four numbers $$\pm x_\pm $$ are clearly distinct.$$\square $$

The key argument in the proof was inferring the existence of a root from a change of sign of a continuous function. This is the intermediate value theorem, a non-constructive existence theorem of real analysis [26, Theorem 4.4]:

Theorem

Any real-valued continuous function $$f$$ on a closed interval $$[a,b]$$ assumes every value between $$f(a)$$ and $$f(b)$$.

Our non-constructive proof provides some information about the solutions, in the form of bounds. These bounds can be sharpened by doing some extra work; e.g., with $$f$$ as above we have

$$ f\left( \frac{7}{22}\right) =\frac{-503}{234256} \qquad f\left( \frac{6}{19}\right) =\frac{1657}{130321} $$

and hence

$$ \frac{6}{19}<x_-<\frac{7}{22}. $$

Considering that $$7/22-6/19< 3\times 10^{-3}$$, our knowledge of the solution $$x_-$$ has increased markedly. We see that the distinction between a constructive and a non-constructive proof is blurred.

A non-constructive existence statement that provides some information about an object—typically a number—in the form of bounds, is said to be effective.2 The above non-constructive proof is effective. Likewise, the estimate of the size of the $$n$$th prime number given by Theorem 8.1 (Sect. 8.4) may be characterised as an effective version of Euclid’s theorem.

In the mathematics literature the meaning of ’constructive proof’ is sometimes extended to include methods that, while not providing an actual object, provide an algorithm for constructing the object.