3.3 Contradiction, Existence, and Uniqueness

Section 3.2 proved implications by moving directly, splitting cases, or proving a contrapositive. Another route begins by asking what would happen if the desired conclusion were false. If that assumption forces an impossible situation, the assumption must be wrong.

This section also distinguishes two phrases that are often merged too quickly:

• “there is at least one” is an existence claim;

• “there is exactly one” requires both existence and uniqueness.

A contradiction is an impossible pair of requirements

A contradiction is a statement that cannot be true under any assignment. Chapter 2 gave the logical form

In ordinary mathematics, contradictions may appear as:

Each pair demands incompatible conditions.

A proof by contradiction of a proposition $P$ follows this pattern:

1. Assume the negation $\neg P$.

2. Combine the assumption with definitions and known facts.

3. Derive a contradiction.

4. Conclude that $\neg P$ cannot hold, so $P$ is true.

The contradiction must result from the temporary assumption together with valid facts. Simply writing “this is a contradiction” without displaying the incompatible results does not complete the proof.

Worked proof: no integer is both even and odd

Theorem. No integer is both even and odd.

Assume for contradiction that some integer $n$ is both even and odd.

Because $n$ is even, there is an integer $a$ such that

Because $n$ is odd, there is an integer $b$ such that

Both expressions equal $n$, so

Rearranging gives

The left side is even because $a-b$ is an integer. The right side is odd. One integer cannot be both even and odd, so this equality is impossible. Our assumption produced a contradiction. Therefore no integer is both even and odd.

This proof may look circular because the contradiction mentions even and odd. It is not: the definitions show that the assumed object would force the concrete impossible equation “an even number equals $1$.”

Isolate the conflict rather than collecting assumptions

A contradiction proof should use only relevant assumptions. Adding unnecessary conditions can hide the true reason for impossibility.

Suppose we assume:

• $n$ is even;

• $n$ is odd;

• $n>0$;

• $3\mid n$.

The first two assumptions already conflict. Positivity and divisibility by $3$ do no work. Removing irrelevant assumptions creates a shorter, clearer proof and reveals the conflict core.

Load assumptions into the pressure chamber until no integer candidates remain. Then remove assumptions one at a time. The most informative result is the smallest active set that still creates impossibility, not the largest dramatic collection of conditions.

Existence asks for at least one witness

An existence statement has the form

To prove it constructively, provide a particular witness $a\in D$ and verify $P(a)$.

Example. There exists an integer $x$ such that

Choose $x=3$. It belongs to the integer domain, and

Therefore a solution exists.

Notice the two checks:

1. the witness belongs to the declared domain;

2. the witness satisfies the predicate.

If the domain were positive even integers, $x=3$ would not be a valid witness even though it satisfies the equation.

Some existence proofs are nonconstructive: they prove that an object must exist without identifying it explicitly. Proof by contradiction can sometimes do this. At this stage, constructive witnesses are easier to verify, so we prefer them when available.

Uniqueness forbids a second different witness

An existence proof does not automatically prove uniqueness. The equation

has witness $x=2$, but it also has $x=-2$. Showing one solution proves existence only.

The statement “there exists exactly one $x$ such that $P(x)$” is written

The symbol $\exists!$ means “there exists a unique.” A complete proof has two parts:

• existence: produce or establish at least one solution;

• uniqueness: assume $x$ and $y$ are both solutions, then prove $x=y$.

Worked existence-and-uniqueness proof

Theorem. There exists a unique real number $x$ satisfying $3x+2=11$.

Existence. The witness $x=3$ works because $3(3)+2=11$.

Uniqueness. Suppose real numbers $x$ and $y$ both satisfy the equation. Then

Therefore

Subtracting $2$ from both sides and dividing by $3$ gives

Any two solutions must be equal, so there cannot be two distinct solutions. Combined with existence, the solution is unique.

The uniqueness argument does not need to rediscover the value $3$. It shows that all possible solutions collapse to one value.

The locksmith separates three states: no witness, exactly one witness, and many witnesses. Try $a=0$ in $ax+b=c$. If $b\ne c$, no $x$ works; if $b=c$, every integer works. This boundary shows why existence and uniqueness require separate scanners.

Choose the claim before choosing the proof

The wording of the theorem determines the proof obligation:

A common error is proving “at most one” and then announcing “exactly one.” An empty solution set also has at most one element, so uniqueness without existence is insufficient.

Bridge to the next section

The methods so far prove one general statement by reasoning about an arbitrary object. Statements indexed by positive integers often have a repeating dependency: if one case holds, it supports the next. Section 3.4 turns this dependency into mathematical induction and then allows each new case to use all earlier cases through strong induction.