Proving Existential Propositions

Recall, a statement in the form:

∃x ∈ D such that propositional function Q(x)

is true if, and only if,

Q(x) is true for at least one x in Domain D.

There are two ways to prove this:

1. To find an x that makes Q(x) true.

2. To give a set of direction for finding an x that makes propositional function Q(x) true.

Examples of Constructive Proofs of Existence:

Example 1: Prove the following existential statement:

∃ an even integer n that can be written in two ways as the sum of two prime numbers.

Proof of Existence:

Suppose n = 10. Then, we can certainly write:

                                    10 = 5 + 5

                                        = 3 + 9

Clearly, 3, 5 and 9 are all primes.

We have shown that a given statement Q(x) is true for 3, 5 and 7 in the set of primes.

Example 2: Prove the following existential statement:

∃ an integer k such that (22r + 18s = 2k), where r and s are integers.

Proof of Existence:

Suppose k = 11r + 9s. Then, clearly k is an integer (why? because it is a sum of product of integers.) and by substitution we have:

                                    2k = 2(11r + 9s)

                                        = 22 + 18s

We have shown that the given statement Q(x) is true for an integer (11r + 9s).

Example 3: Prove the following existential statement:

There is an integer n > 5 such that 2ⁿ - 1 is prime number.

Using quantifier i.e. a little more formally:

∃ an integer n > 5 such that 2ⁿ - 1 is prime.

Proof of Existence:

Suppose n = 7 (which is prime.) Then, we have

                                    2ⁿ - 1 = 2⁷ - 1

                                             = 128 - 1

                                            = 127

And 127 is a prime number.

We have shown that the given statement Q(x) is true for at least one n = 7 in the set of prime numbers.

Example 4: Prove the following existential statement:

There are positive integers the sum of whose reciprocals is an integer.

Using quantifier i.e. a little more formally:

∃ a positive integers m and n such that the sum of whose reciprocals is an integer.

Proof of Existence:

Suppose m = 2 and n = 2. Then

                                    1/m + 1/m = 1/2 + 1/2

Reciprocals:

                                          m + n = 1.

We have shown that the given statement Q(x) is true for m = 2 and n = 2 in the set of positive integers.

Non Constructive Proof of Existence

This method involves showing showing the following: