UMBC CMSC203, Discrete Structures, Fall 2010

⇐ Proof by Cases Equivalence Proofs ⇒

Uniqueness Proofs

A uniqueness proof makes a stronger claim than an existence proof --- not only does the object in question exist, it must be the only one to exist. The quantifier ∃! is sometimes used to indicate unique existence and we will adopt it here.

There are two general methods for showing that an object is unique. Suppose that P(x) is some predicate and we wish to establish that ∃! x, P(x). Both methods start by establishing that P(x) holds for some particular x. In the first method, uniqueness is proven by showing that all y, y ≠ x, P(y) is false. In the second method, we show that for all y such that P(y) is true, y is actually equal to x. Which method works better depends on the situation at hand. Let us consider an example of each method.



Example 1: Consider this numerical example using the second method.

Claim: Let a and b be two odd integers such that a ≠ b. Then, there exists a unique integer c such that
| a − c | = | b − c |.
Proof: First we need to show that such a c exists. Without loss of generality assume that a < b. Now, let c = (a + b)/2, that is, c is the average of a and b. Since a and b are both odd, a + b must be even, which makes (a + b)/2 an integer.

The arithmetic below shows that | a − c | = | b − c |.

c − a = (a + b)/2 − a = (a + b − 2a)/2 = (b − a)/2.
Since (b−a)/2 > 0, | a − c | = c − a = (b − a)/2.

Similarly,

b − c = b − (a + b)/2 = (2b − a − b)/2 = (b − a)/2.
Again (b−a)/2 > 0, so | b − c | = b − c = (b − a)/2. Thus, | a − c | = (b − a)/2 = | b − c |.

Now, we want to show that c is unique. So, suppose that for some other integer c' that | a − c' | = | b − c' |. We will show that c' is, in fact, equal to c.

Case 1: Suppose that c' < a < b.

Then | a − c' | = a − c' and | b − c' | = b − c'. So, we have

| a − c' | = | b − c' |
⇒ a − c' = b − c'
⇒ a = b
But, this contradicts the hypothesis in the claim that a ≠ b. So, Case 1 cannot occur.

Case 2: Suppose that a < b < c'.

Then | a − c' | = c' − a and | b − c' | = c' − b. So, we have

| a − c' | = | b − c' |
⇒ c' − a = c' − b
⇒ a = b
Again, this contradicts the hypothesis in the claim that a ≠ b. So, Case 2 also cannot occur.

Case 3: Suppose that a ≤ c' ≤ b.

Then | a − c' | = c' − a and | b − c' | = b − c'. So, we have

| a − c' | = | b − c' |
⇒ c' − a = b − c'
⇒ 2 c' = b + a
⇒ c' = (b + a)/2
But, then both c and c' are equal to (b + a)/2. Thus, c = c'.
QED



Example 2: Here's a graph theory example using the first method. We show that x is unique by showing that for all y where y ≠ x, P(y) does not hold. This is done by contradiction. That is, we show that if there exists a y such that y ≠ x and P(y), then we can arrive at a contradiction.

Claim: Let G be a connected undirected graph without any cycles. Then, for every pair of vertices u and v in G, there is an unique path from u to v.

Proof: First, since the graph G is connected, we know there is a path from u to v. Call this path π1. Suppose that there is a different path π2 from u to v:
Consider π1 and π2 as they go from vertex u to vertex v. Since π1 and π2 are different paths, at some point the two paths must diverge. That is, from some common vertex x, π1 proceeds to vertex y, but π2 goes to a different vertex z. (If such vertices y and z do not exist, then π1 and π2 must be identical paths.) The vertex x might be actually be u, but we won't need to assume that x ≠ u so this does not matter. After y and z, the two paths will eventually converge, since they both eventually reach the vertex v. Let w be the first vertex on π1 after y that also appears on π2 after z. (It might be the case that w = v, but this does not matter.)

So, there exists a path from x to y then to w along path π1. The path can continue from w to z in the reverse direction of π2 and finally from z back to x. This path forms a cycle from x to w and then back to x. This contradicts the hypothesis that the graph G has no cycle. Therefore, the assumption that there exists a second path π2 from u to v must be false and π1 is the unique path from u to v.

One final note: it is possible that w = x. This does not invalidate our proof. The cycle traced out will simply go back to x twice.

QED

⇐ Proof by Cases Equivalence Proofs ⇒

Last Modified: 22 Jul 2024 11:29:46 EDT by Richard Chang
to Fall 2010 CMSC 203 Homepage