Skip to main content

Discrete Mathematical Structures

Dan Yasaki, Sebastian Pauli

Subsection 1.4.5 Existence proofs

Many theorems assert the existence of an object with certain properties. They are of the form \(\exists x \,P(x)\) . One way to prove such a statement is to find a witness \(a\) such that \(P(a)\) is true. This is called an constructive existence proof . . See Proof Technique 1.3.3.6 for details.
🔗

Example 1.4.5.1. Sum of cubes.

Prove there is an integer that can be written as the sum of cubes of positive integers in two different ways.
🔗
Answer.
There is an integer that can be written as the sum of cubes of positive integers in two different ways, for example,
\begin{equation*} 1729 = 10^3 + 9^3 = 12^3 + 1^3. \end{equation*}
🔗
🔗
Solution.
It suffices to provide a witness. We can find the a witness with Python script Listing 1.4.5.2, for example.
🔗
We look for an integer that can be expressed as the sum of cubes of two distinct positive integers in two different ways.
🔗
🔗
🔗
Listing 1.4.5.2. Python script to find witness for Example 1.4.5.1.
🔗
def witness_sum_of_cubes(bound):	
  ijs = {} # dictionary to store possible witnesses
  for i in range(bound):
    for j in range(i+1,bound):
      s = i**3 + j**3
      if s in ijs.keys():
        print("found witness")
        print(s,"=",i,"**3 +",j,"**3  and")
        print(s,"=",ijs[s][0],"**3 +",ijs[s][1],"**3")
        return True
      else:
        ijs[s] = [i,j]
  print("no witness found")
  return False

witness_sum_of_cubes(13)
There are some proofs of existence that do not produce a witness. These are called non-constructive proofs.
🔗

Example 1.4.5.3. Irrational power.

Prove there exist irrational numbers \(a\) and \(b\) such that \(a^b\) is rational.
🔗
Solution.
In our proof we distinguish two cases and use that we have already proven that \(\sqrt{2}\) is irrational in Example 1.4.4.3.
🔗
Case I: \(\sqrt{2}^{\sqrt{2}}\) is rational
🔗
If \(\sqrt{2}^{\sqrt{2}}\) is rational, then \(a = \sqrt{2}\text{,}\) \(b = \sqrt{2}\) is our witness, and we are done.
🔗
Case II: \(\sqrt{2}^{\sqrt{2}}\) is irrational
🔗
If \(\sqrt{2}^{\sqrt{2}}\) is irrational then
\begin{equation*} (\sqrt{2}^{\sqrt{2}})^{\sqrt{2}} = \sqrt{2}^2 = 2, \end{equation*}
which is rational, so \(a = \sqrt{2}^{\sqrt{2}}\) , \(b = \sqrt{2}\) is our witness.
🔗
🔗
🔗
Note that the proof of Example 1.4.5.3 does not tell us which case occurs, so it is non-constructive.
🔗
Figure 1.4.5.4. Proofs by Randal Munroe (https://xkcd.com/1724/). Next, let’s assume the decision of whether to take the Axiom of Choice is made by a deterministic process …
🔗
🔗
PrevTopNext