Skip to main content

Introduction to Proofs: An Active Exploration of Mathematical Language

Jennifer Firkins Nordstrom

Section 5.1 Existence and Uniqueness Proofs

In this section we will look at existential statements which have the form “There exists \(x\) such that \(P(x)\text{,}\)” and “There exists a unique \(x\) such that \(P(x)\text{.}\)” We first studied existence statements in Section 2.2.
Recall how to show an existential statement, \(\exists x\in D, P(x)\text{,}\) is true/false:
  • To show an existential statement is true, you just need to find one value in \(D\) which makes \(P(x)\) true.
  • To show an existential statement is false, you need to show all values in \(D\) make \(P(x)\) false, or no values make it true. If your set is small, you can do this just by showing \(P(x)\) is false for each \(x\text{.}\) If \(D\) is infinite, however, we will need more general techniques.
In Section 2.2, we were generally able to find a specific \(x\) in order to show a existential statement was true.
  1. Let \(D=\mathbb{Z}\text{.}\) Determine whether the statement “there exists \(x\in D\) such that \(x+3/2=4\)” is true or false.
    Answer.
    Since \(x=5/2\) is the only value satisfying the equation, but \(x\notin \mathbb{Z}\text{,}\) the statement is false.
  2. Let \(D=\mathbb{R}\text{.}\) Determine whether the statement “there exists \(x\in D\) such that \(x+3/2=4\)” is true or false.
    Answer.
    Since \(x=5/2\) is the only value satisfying the equation, and \(x\in \mathbb{R}\text{,}\) the statement is true.
  3. Let \(D=\{5/2\}\text{.}\) Determine whether the statement “there exists \(x\in D\) such that \(x+3/2=4\)” is true or false.
    Answer.
    Since \(x=5/2\) is the only value satisfying the equation, and \(x\in D\text{,}\) the statement is true.
However, many existence statements in mathematics require us to find a more general solution.

Proving an Existential Statement.

To prove there exists \(x\in D\) such that \(P(x)\text{:}\)
  1. Produce a candidate. This means you state an \(x\in D\) which makes \(P(x)\) true. You may need to do work to find \(x\text{,}\) but that work is not part of the actual proof.
  2. Show the candidate works. In other words, show \(P(x)\) is true.
Let \(r, s \in \mathbb{Q}\) with \(r < s\text{.}\) Prove there exists \(x\in \mathbb{Q}\) such that \(r < x < s\text{.}\)
Before proving the statement, we need to find an \(x\) that is between \(r\) and \(s\text{.}\) We need to find a general one, one that depends on \(r\) and \(s\text{.}\) There are lots of choices, but to guarantee it is in between \(r\) and \(s\text{,}\) we might want to take the midpoint, which is also the average of the two numbers, \(\frac{r+s}{2}\text{.}\)
Let \(r, s\in \mathbb{Q}\) with \(r < s\text{.}\) Let \(x=\frac{r+s}{2}\) (this is stating the candidate). Then \(x\) is rational (see Exercise 3.2.3.5 or prove this as an exercise). Furthermore,
\begin{equation*} r=\frac{2r}{2}=\frac{r+r}{2} < \frac{r+s}{2} < \frac{s+s}{2} =\frac{2s}{2}=s. \end{equation*}
Thus, \(r < x < s\text{.}\) (We showed that \(x\) satisfied all the necessary properties.)

Activity 5.1.1. A Bigger Integer.

Prove for \(n\in \mathbb{Z}\) there exists an integer \(m\) with \(n < m\text{.}\)

(a)

Given a general integer \(n\text{,}\) find an interger that will always be larger that \(n\text{.}\) This is your candidate for \(m\text{.}\)

(b)

Verify that \(n < m\) and \(m\in \mathbb{Z}\text{.}\)

(c)

Is your choice for \(m\) unique? Could you find a different \(m\) that works? If you can find another choice for \(m\text{,}\) write a second proof of existence with your new \(m\text{.}\)
Existence statements are common in mathematics. You probably came across several in calculus, for example, Rolle's Theorem and the Mean Value Theorem. Although their proofs are beyond the scope of this course, you are encouraged to look up a proof and see how the techniques we've been studying are applied. In many contexts, it can be very difficult to find a candidate. If you are stuck, it might be worth trying proof by contradiction. In this case, you assume there does not exist \(x\) satisfying \(P(x)\text{.}\) Symbolically this statement is \(\neg \exists x, P(x)\text{.}\) The negation is equivalent to \(\forall x, \neg P(x)\text{.}\) You can then use \(\forall x, \neg P(x)\) for your assumption and try to reach a contradiction.
Now we want to look at statements where the \(x\) that exists is actually unique. Meaning, there is only one possible \(x\) that will work. First we show \(x\) exists, then we show it is unique.

Proving Uniqueness.

To prove there exists a unique \(x\in D\) such that \(P(x)\text{:}\)
  1. Produce a candidate. This means you state the \(x\) that makes \(P(x)\) true. You may need to do work to find \(x\text{,}\) but that work is not part of the actual proof.
  2. Show the candidate works. In other words, show \(P(x)\) is true. This shows existence.
  3. Assume \(P(x)\) is true and \(P(y)\) is true. Show \(x=y\text{.}\) This shows uniqueness.
The idea behind a uniqueness proof is that if the necessary property holds for \(x\) and \(y\text{,}\) then they must have been the same thing, so there can only be one solution. It is important to note that you just need to show \(x=y\) in general. If there was a specific solution for \(x\) in the existence part, you do not need to show that \(y\) equals that specific \(x\text{.}\)
In Example 5.1.1 we said that the solution to \(x+3/2=4\) was unique. This may seem obvious since if we solve for \(x\text{,}\) there is only one possible solution. But just to practice with the form of a uniqueness proof, we show how to prove uniqueness without showing \(x=5/2\text{.}\)
Let \(x\) and \(y\) be solutions to \(x+3/2=4\text{.}\) Then \(x+3/2=4\) and \(y+3/2=4\text{.}\) Thus,
\begin{equation*} x+3/2=y+3/2 \end{equation*}
\begin{equation*} x=y \end{equation*}
Hence, the solution is unique.

Activity 5.1.2. A Unique Root.

Assume \(x^3+37=0\) has a solution. Show the solution is unique.
Hint.
You do not need to find the actual solution to do this proof.
In Section 3.3 we stated the Division Algorithm, Theorem 3.3.3. We restate it for convenience.
This is a classic example of an exstence and uniqueness statement in mathematics. We need to prove \(q, r\) exist and are unique. Before we do that we need the Well-Ordering Principle, which we will state without a proof.
To check that the Well-Ordering Principle applies, you need to check three things:
  1. \(\displaystyle S\neq \emptyset.\)
  2. \(\displaystyle S\subseteq \mathbb{Z}.\)
  3. Every element of \(S\) is greater than some fixed integer.
First note that the Well-Ordering Principle does not apply if the set is not integers. For example,
\begin{equation*} \{1/n : n\in \mathbb{Z}, n\geq 1\}. \end{equation*}
This is not a subset of the integers and does not have a least element, even though every element is greater than 0.
Now consider \(S=\{2k+1 : k\in \mathbb{Z}, k\geq 0\}\text{.}\) Check each of the conditions.
  1. \(S\neq \emptyset\) since \(1\in S\text{.}\)
  2. \(S\subseteq \mathbb{Z}\) since \(2k+1\in \mathbb{Z}\text{.}\)
  3. Every element of \(S\) is greater than some fixed integer since \(2k+1\geq 1\) when \(k\geq 0\text{.}\)
We now prove the existence part of the Division Algorithm.
Let \(S=\{n-dk : n-dk\geq 0, k\in\mathbb{Z}\}\text{.}\) Show \(S\) satisfies the Well-Ordering Principle. Clearly \(S\) is a set of integers, and by definition, every element is greater than or equal to 0. So we just need to show that \(S\neq\emptyset\text{.}\)
If \(n\geq 0\text{,}\) we can let \(k=0\text{.}\) Then \(n-dk=n\geq 0\text{.}\) Hence \(n\in S\text{.}\)
If \(n< 0\text{,}\) let \(k=n\text{.}\) Then \(n-dn=n(1-d)\text{.}\) But \(n< 0\) and \(1-d\leq 0\text{.}\) Thus, \(n-dn\geq 0\text{.}\) Hence \(n-dn\in S\text{.}\)
Thus, \(S\) is nonempty and satisfies the conditions of the Well-Ordering Principle. Hence, \(S\) has a least element. Call it \(r\text{.}\)
Since \(r\in S\text{,}\) \(r=n-dk\) for some \(k\in \mathbb{Z}\text{.}\) Let \(k=q\text{.}\) Then \(r=n-dq\text{,}\) and so \(n=dq+r\text{.}\)
We just need to show that \(0\leq r< d\text{.}\) Well, \(r\geq 0\) since \(r\in S\text{.}\)
We will use contradiction to show \(r< d\text{.}\) Assume \(r\geq d\text{.}\) Then
\begin{align*} n-d(q+1)&=n-dq-d\\ &=r-d\\ &\geq 0, \text{ since } r\geq d. \end{align*}
But then \(n-d(q+1)\in S\) and \(n-d(q+1)< n-dq=r\text{.}\) This contradicts that \(r\) was the smallest element of \(S\text{.}\) Therefore, \(r< d\text{.}\)
Although this is a fairly complex proof, it is a good example of how many different techniques can be used in one proof. We do not have a specific value for \(r\text{,}\) rather its existence (and hence existence of \(q\)) depends on existence in the Well-Ordering Principle. Now we prove \(q\) and \(r\) are unique.
Assume \(q_1, r_1, q_2, r_2\) exist and satisfy the conditions of the theorem. Then, \(n=dq_1+r_1\) and \(0\leq r_1 < d\) and \(n=dq_2+r_2\) and \(0\leq r_2 < d\text{.}\) This gives us
\begin{equation*} dq_1+r_1=dq_2+r_2. \end{equation*}
Rewriting,
\begin{equation*} r_1-r_2=dq_2-dq_1=d(q_2-q_1) \end{equation*}
We can assume \(r_1 \geq r_2\) (if they weren't, we could just rename them).
Thus, \(d\) divides \(r_1-r_2\text{.}\) But since \(0\leq r_1 < d\) and \(0\leq r_2 < d\text{,}\) \(0\leq r_1-r_2 < d\text{.}\) The only nonnegative integer \(d\) divides that is smaller than itself is 0. Thus \(r_1-r_2=0\text{.}\) Therefore, \(r_1=r_2\text{.}\)
Now
\begin{align*} dq_1+r_1&=dq_2+r_2\\ dq_1&=dq_2\\ q_1&=q_2 \end{align*}
Hence, \(r, q\) are unique.

Exercises Exercises

1.

Prove if \(a\) is a positive real number, then there exists a positive real number less than \(a\text{.}\)

2.

Prove for all real numbers \(x\text{,}\) if \(x\neq 2\) then there exists a unique \(y\) in \(\mathbb{R}\) such that \({2y\over y+1}=x\text{.}\)

3.

Prove there exists a unique integer \(a\) such that \(a+b=b\) for all integers \(b\text{.}\)

4.

Prove there exists a unique integer \(a\) such that \(ab=b\) for all integers \(b\text{.}\)

5.

Let \((1,4)\) and \((3,2)\) be points in the plane. Prove there is a unique line through \((1,4)\) and \((3,2)\text{.}\)
Hint.
First show the line exists. You can use scratchwork to find the equation of the line. Then you need to show your line passes through the two points in your proof. For uniqueness assume you have two general lines, \(y=mx+b\text{,}\) passing through \((1,4)\) and \((3,2)\text{.}\) Show the two lines are the same. Each point on each line gives one equation.

6.

Let \((a,b)\) and \((c,d)\) be points in the plane with \(a\neq c\text{.}\) Prove there is a unique line through \((a,b)\) and \((c,d)\text{.}\)
Hint.
First show the line exists. You can use scratchwork to find the equation of the line. Then you need to show your line passes through the two points in your proof. For uniqueness assume you have two general lines passing through \((a,b)\) and \((c,d)\text{.}\) Show the two lines are the same. Each point on each line gives one equation.
<Prev^TopNext>