2.4 Existence and uniqueness proofs

A proof of a proposition ∃x:p(x) is called an "existence proof". There are two well known methods for proving such propositions.

The first is called "a constructive proof" in which we look for an element a such that p(a) is true.

The second is called "a non constructive proofs" in such proof we do not look for an a such that p(a) is true but we prove the proposition in a different way. One common method of giving a nonconstructive existence proof is to use proof by contradiction and show that the negation of the existential quantification implies a contradiction.

2.4.1 Example

Show that there is a positive integer that can be written as the sum of cubes of positive integers in tow different ways.

Solution

We use “a constructive existence proof” using a calculator one can observe after some reasonable attempts that 1729 is the required positive integer since

2.4 Existence and uniqueness proofs

2.4.2 Example

Show that there exists irrational numbers x and y such that x y is rational.

Solution

We proved in example 2.2.4. that √2 is irrational.

If(√2)^√2 is rational then the assertion follows with x=√2 and y=√2. If(√2)^√2 is irrational then the assertion follows by taking x=(√2)^√2 and y=√2 (note that x^y = ((√2)^√2)^√2 =(√2)²=2 is rational).

This is of course an example of a nonconstructive existence proof.

We conclude this topic by giving an example of a uniqueness proof.

2.4.3 Example

Show that if a and b are real numbers and a≠0, then there is a unique real number r such that ar + b = 0

2.4 Existence and uniqueness proofs

Solution


Thus there exists a real number r such that ar+b=0.

Uniqueness: If q is another real number such that aq + b = 0. It follows that

aq + b = ar + b this implies aq = ar. Since a≠0 then dividing both sides by a gives q = r.

This proves the uniqueness of r.