_{Disclaimer: this is a summary of section 3.6 from the book A Gentle Introduction to the Art of Mathematics: by Joe Fields, the content apart from rephrasing is identical, most of the equations are screenshots of the book and the same examples are treated.}

Proofs and Disproofs of Existential Statements

---

If we are proving an existential statement we are disproving some universal statement. Similarly, if we are trying to disprove an existential statement, then we are actually proving a related universal statement.

Proofs of existential questions come in two basic varieties:

1. Constructive existence proof: conceptually the easier of the two – you actually name an example that shows the existential question is true.
   • Examples: There is an even prime.
     The number 2 is both even and prime. Q.E.D.
2. Non-constructive existence proof: a lot trickier. One approach is to argue by contradiction – if the thing we’re seeking doesn’t exist that will lead to an absurdity. A particularly neat approach is to argue using dilemma.

Many existential proofs involve a property of the natural numbers known as the well-ordering principle (WOP). 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.

There are instances when we need to prove statements involving the unique existence quantifier. In such instances, we need to do just a little bit more work.

1. We need to show existence – either constructively or non-constructively
2. We also need to show uniqueness

To illustrate this concept of unique existence quantifier one has to get back to the idea of the Euclidean algorithm, where we calculated the greatest common divisor of two integers a and b (gcd(a,b)).

Halting problem

---

One interesting question regarding algorithms is given by the following question:

Does the program eventually halt, or does it get stuck in an infinite loop?

In our case, we know that Euclidean algorithm halts because we know the following unique existence result.

To prove this result, we need a precise definition for gcd(a,b). This is given by the following:

The greatest common divisor, or gcd, of two positive integers a and b is a positive integer d such that d|a and d|b and if c is any other positive integer such that c|a and c|b then c|d.

Unique existence

---

First and foremost, we are going to prove the unique existence of the gcd (it's easier). We argue by contradiction.

• suppose 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'|d.
• similarly, we can deduce that d|d' and if two numbers each divide into the other, they must be equal; that, d|d' and d'|d, then d = d'.

Existence

---

To start with existence, we need to introduce a new set - known as Z-module generated by a and b - that consists of all numbers of the form xa+ yb where x and y range over the integers.

Z-module plane generated by 21 and 15.

Every element of a Z-module generated by two numbers corresponds to a point in the Euclidean plane. As seen in the figure, there is a dividing line between the positive and negative elements in a Z-module. It is also easy to see that there are many repetitions of the same value at different points in the plane. In addition, the smallest positive number in the plane is 3.

The general results can actually be expressed as:

Source
where the proof is given as follows:

Source

References

1. A Gentle Introduction to the Art of Mathematics by Joe Field

---

Thank you for reading ...