The Central Idea
An existence statement has the logical form
\[ \exists x\in S\text{ such that }P(x). \]To prove it, we must establish that at least one object \(x\) in the permitted domain \(S\) satisfies the required property \(P(x)\).
There are two broad approaches:
- constructive: produce or describe such an \(x\);
- nonconstructive: prove that such an \(x\) must exist without explicitly producing one.
What Is a Constructive Proof?
A constructive proof establishes
\[ \exists x\in S\text{ such that }P(x) \]by identifying a specific witness \(x\) or by giving a procedure that generates one.
The proof has the practical structure:
- choose or construct a candidate \(x\);
- verify that \(x\in S\);
- verify that \(P(x)\) is true.
The Witness
In an existential statement,
\[ \exists x\,P(x), \]an object that satisfies \(P\) is called a witness.
A constructive proof usually provides such a witness explicitly.
A First Constructive Example
Prove that there exists an even prime number.
Choose
\[ 2. \]The number \(2\) is even and prime.
Therefore,
\[ \boxed{\text{there exists an even prime number}.} \]Example: An Integer between Two Integers
Prove that there exists an integer strictly between \(10\) and \(20\).
Choose
\[ 15. \]Then
\[ 10<15<20. \]Therefore \(15\) is a witness.
Construction Does Not Have to Be Numerical
A witness can be any mathematical object:
- a number;
- a set;
- a function;
- a graph;
- a sequence;
- a geometric configuration;
- an algorithm;
- a path or arrangement.
The construction must match the type of object claimed to exist.
Example: Constructing a Set
Prove that there exists a finite set containing exactly three even integers.
Choose
\[ A=\{2,4,6\}. \]The set \(A\) is finite, contains exactly three elements, and every element is even.
Thus \(A\) is a witness.
Example: Constructing a Function
Prove that there exists an injective function
\[ f:\mathbb Z\to\mathbb Z. \]Define
\[ f(n)=2n. \]If
\[ f(a)=f(b), \]then
\[ 2a=2b, \]so \(a=b\).
Therefore \(f\) is injective, and the desired function exists.
Example: Constructing a Graph
Prove that there exists a simple graph with four vertices in which every vertex has degree \(2\).
Construct the cycle
\[ C_4. \]It has four vertices connected in a closed loop.
Every vertex has exactly two neighbors.
Therefore such a graph exists.
A Formula Can Be a Construction
A constructive proof need not list every object individually.
A formula may generate the required object.
For example, to produce an even integer larger than any integer \(n\), define
\[ m=2(|n|+1). \]Then \(m\) is even and
\[ m>n. \]An Algorithm Can Be a Construction
Sometimes existence is established by describing a finite procedure.
If the procedure is guaranteed to terminate and return an object satisfying the required property, then the algorithm itself constitutes a constructive existence proof.
Example: Constructing the Greatest Common Divisor
For positive integers \(a\) and \(b\), the Euclidean algorithm computes
\[ \gcd(a,b). \]Because the remainder decreases and the process terminates, the algorithm eventually produces the greatest common divisor.
This gives more than existence: it provides a method for finding the object.
Constructive Existence Often Gives Extra Information
A constructive proof may provide:
- an explicit example;
- a formula;
- an algorithm;
- a bound on the object;
- a method for generating many examples;
- information about complexity or efficiency.
Thus construction can be mathematically and computationally valuable.
What Is a Nonconstructive Existence Proof?
A nonconstructive proof establishes
\[ \exists x\,P(x) \]without explicitly identifying a particular \(x\).
The proof may rely on:
- contradiction;
- pigeonhole reasoning;
- counting;
- extremal arguments;
- logical alternatives;
- general existence theorems.
A Simple Nonconstructive Pattern
Suppose we know that a finite collection contains more objects than available categories.
Pigeonhole reasoning guarantees that two objects share a category.
The proof may establish that such a pair exists without identifying which pair it is.
Example: Shared Birth Month
Among \(13\) people, at least two share a birth month.
There are only \(12\) months.
The pigeonhole principle guarantees a repeated month.
But unless the actual birthdays are known, the proof does not identify the pair.
This is an existence proof without explicit construction.
Existence by Contradiction
To prove
\[ \exists x\,P(x) \]by contradiction, assume the negation:
\[ \forall x,\;\neg P(x). \]If this assumption leads to a contradiction, then at least one \(x\) satisfying \(P(x)\) must exist.
Example Pattern: Some Object Must Have a Property
Suppose a theorem claims:
\[ \exists x\in S\text{ such that }P(x). \]Assume no element of \(S\) has property \(P\):
\[ \forall x\in S,\;\neg P(x). \]If the hypotheses force an impossibility under that assumption, then the existential claim follows.
Constructive versus Nonconstructive
Both proof styles can establish the same logical conclusion:
\[ \exists x\,P(x). \]The distinction is whether the proof provides enough information to produce a witness.
Constructive:
\[ \boxed{\text{Here is an }x\text{ satisfying }P.} \]Nonconstructive:
\[ \boxed{\text{Some }x\text{ satisfying }P\text{ must exist}.} \]Existence Does Not Mean Uniqueness
The statement
\[ \exists x\,P(x) \]says at least one witness exists.
It does not say there is exactly one.
For example, there exists an even integer greater than \(10\), but many such integers exist.
Existence and Uniqueness
A stronger statement is
\[ \exists!x\,P(x), \]read:
“There exists exactly one \(x\) such that \(P(x)\).”
A proof of existence and uniqueness usually has two parts:
- prove that at least one witness exists;
- prove that any two witnesses must be equal.
Example: Unique Additive Identity
In the integers, \(0\) is an additive identity because
\[ n+0=n \]for every integer \(n\).
Thus existence is constructive: the witness is \(0\).
For uniqueness, suppose \(e\) and \(f\) are both additive identities.
Then
\[ e+f=e \]because \(f\) is an identity, while
\[ e+f=f \]because \(e\) is an identity.
Therefore
\[ e=f. \]Constructive Proofs of Universal-Existential Statements
Many statements have the form
\[ \forall x\in A,\;\exists y\in B\text{ such that }P(x,y). \]A constructive proof starts with an arbitrary \(x\) and gives a rule for producing \(y\).
Example: A Larger Integer Always Exists
Prove:
\[ \forall n\in\mathbb Z,\;\exists m\in\mathbb Z\text{ such that }m>n. \]Let \(n\in\mathbb Z\) be arbitrary.
Define
\[ m=n+1. \]Then \(m\in\mathbb Z\) and
\[ m>n. \]Therefore the statement is proved constructively.
Example: An Even Integer Larger Than Any Integer
Prove:
\[ \forall n\in\mathbb Z,\;\exists m\in\mathbb Z \]such that \(m\) is even and \(m>n\).
Choose
\[ m=2(|n|+1). \]Then \(m\) is even.
Also,
\[ |n|\ge n, \]so
\[ m=2(|n|+1)>n. \]Thus the construction works for every integer \(n\).
Constructive Proofs and Bounds
A proof may establish not only that a witness exists but also where it can be found.
For example, a theorem may prove
\[ \exists x\in[a,b]\text{ such that }P(x). \]A constructive version might provide an explicit formula or search procedure that locates such an \(x\).
Finite Search as a Constructive Method
If the domain is finite, exhaustive search can sometimes serve as a constructive existence proof.
A valid search-based proof must establish:
- the search checks every candidate in the finite domain;
- the search finds at least one valid witness.
The method may be inefficient, but it is still constructive.
Construction by Cases
A witness may depend on which case applies.
Suppose we want to prove
\[ \forall x\in S,\;\exists y\text{ such that }P(x,y). \]We may divide the possible \(x\)-values into cases and define a different witness \(y\) in each one.
Example: Constructing a Nonnegative Number
For every real number \(x\), there exists a nonnegative real number \(y\) such that
\[ y^2=x^2. \]Construct
\[ y=|x|. \]Then
\[ y\ge0 \]and
\[ y^2=|x|^2=x^2. \]Constructive Proofs from Definitions
Definitions often suggest witnesses directly.
For example, if
\[ a\mid b, \]then by definition there exists an integer \(k\) such that
\[ b=ak. \]The integer \(k\) is an existential witness supplied by the definition of divisibility.
Example: Divisibility Gives a Witness
Suppose
\[ 5\mid n. \]Then by definition there exists an integer \(k\) such that
\[ n=5k. \]The proof does not necessarily know the numerical value of \(k\), but the hypothesis guarantees its existence.
This is different from proving an entirely new existential statement.
Implicit versus Explicit Witnesses
A proof may establish a witness indirectly through an equation or property.
An explicit witness might be
\[ x=7. \]An implicit description might be:
“Let \(x\) be the least positive integer satisfying \(P\).”
The second approach requires a separate existence argument showing that such a least element exists.
Extremal Existence Proofs
Extremal arguments often prove existence of a special object.
For example, every nonempty finite set of real numbers has a maximum.
The proof may not begin by naming its numerical value, but finiteness guarantees that one of the listed elements is at least as large as all the others.
Existence from Pigeonhole Reasoning
Pigeonhole arguments often establish statements of the form:
\[ \exists x\ne y\text{ such that }R(x,y). \]The collision is guaranteed by counting.
The proof may not reveal which pair \(x,y\) works.
Example: Divisible Difference
Among any \(9\) integers, there exist two whose difference is divisible by \(8\).
There are only \(8\) residue classes modulo \(8\).
Two integers share a residue class.
Thus there exist distinct \(a,b\) such that
\[ a\equiv b\pmod8, \]so
\[ 8\mid(a-b). \]Existence from Averaging
Average-value arguments can also prove existence.
If the average of finitely many numbers is \(A\), then at least one of the numbers is at least \(A\), and at least one is at most \(A\).
Otherwise the average itself would be forced above or below \(A\).
Example: Some Value Is at Least the Average
Let
\[ x_1,x_2,\ldots,x_n \]have average
\[ \bar x=\frac{x_1+\cdots+x_n}{n}. \]If every \(x_i<\bar x\), then
\[ x_1+\cdots+x_nTherefore,
\[ \boxed{\exists i\text{ such that }x_i\ge\bar x.} \]Probabilistic Existence: The Basic Idea
In more advanced discrete mathematics, probability can prove existence.
If a random construction has positive probability of producing an object with property \(P\), then at least one such object must exist.
Symbolically, if
\[ \Pr(P)>0, \]then
\[ \exists x\text{ with property }P. \]The argument may not explicitly construct the successful object.
Why Positive Probability Implies Existence
If no object with property \(P\) existed, then the probability of obtaining one would be
\[ 0. \]Therefore any proof that the probability is positive establishes that at least one successful object exists.
Existence Is Not the Same as Finding
A proof can establish that an object exists even if no efficient method for locating it is known.
This distinction appears throughout mathematics and computer science:
\[ \boxed{\text{existence}\ne\text{efficient construction}.} \]A constructive proof may still produce an impractically slow algorithm.
Construction Is Not the Same as Example Checking
If a theorem claims
\[ \exists x\,P(x), \]one valid example is enough.
But if the theorem claims
\[ \forall x\,P(x), \]checking one or several examples is not enough.
The quantifier determines the required proof structure.
Universal versus Existential Claims
Compare:
\[ \forall x\in S,\;P(x) \]with
\[ \exists x\in S,\;P(x). \]A universal proof must cover every permitted object.
An existential proof needs only one valid witness.
Negating an Existence Statement
The negation of
\[ \exists x\,P(x) \]is
\[ \boxed{\forall x\,\neg P(x).} \]This transformation is essential when proving existence by contradiction.
Negating a Universal-Existential Statement
The negation of
\[ \forall x\,\exists y\,P(x,y) \]is
\[ \exists x\,\forall y\,\neg P(x,y). \]In words:
there is some input \(x\) for which no valid witness \(y\) exists.
Common Error: Giving a Candidate without Verification
A constructive proof does not end when a candidate is named.
The proof must verify:
\[ x\in S \]and
\[ P(x). \]A proposed witness that fails either requirement proves nothing.
Common Error: Proving Only Possibility
Saying
“It is possible that such an object exists”
is not an existence proof.
Mathematical existence requires a logical guarantee:
\[ \boxed{\exists x\,P(x).} \]Common Error: Confusing Existence with Uniqueness
Producing one witness proves existence.
It does not prove that no other witnesses exist.
Uniqueness requires a separate argument unless it follows immediately from the construction.
Common Error: The Witness Depends on an Unproved Assumption
Suppose a proof says:
“Let \(x\) be the smallest object with property \(P\).”
This is valid only after proving that:
- at least one object has property \(P\);
- a smallest such object exists under the relevant ordering.
Common Error: A Construction Leaves the Domain
If the theorem requires
\[ x\in S, \]the constructed witness must actually belong to \(S\).
For example, a real-valued witness does not prove an existence claim that requires an integer.
Common Error: Using an Example for a Universal Claim
To prove
\[ \forall n\in\mathbb Z,\;\exists m\in\mathbb Z\text{ such that }m>n, \]choosing \(m=100\) proves the claim only for integers \(n<100\).
A correct construction must depend on arbitrary \(n\), such as
\[ m=n+1. \]Common Error: A Nonconstructive Proof Is Called Incomplete
In ordinary classical mathematics, a logically valid nonconstructive proof can fully establish an existence claim even without naming a witness.
The absence of an explicit construction does not by itself make the proof incomplete.
It simply provides a different kind of information.
Common Error: Construction without Termination
If a proposed constructive method is an algorithm, the proof must justify that the procedure actually terminates.
An endless procedure that never returns a witness does not provide an effective construction.
Choosing a Proof Strategy
When facing an existential claim, ask:
- Can I guess a simple witness?
- Can I derive a formula for one?
- Can I build one algorithmically?
- Can I force existence by counting?
- Can I use an extremal object?
- Would contradiction prove that nonexistence is impossible?
A Reliable Procedure for Constructive Existence Proofs
- Write the existential claim clearly.
- Identify the required domain and properties.
- Propose a witness or construction.
- Verify that the witness belongs to the required domain.
- Verify every required property.
- If the construction is algorithmic, prove termination when needed.
- Conclude that the required object exists.
A Reliable Procedure for Nonconstructive Existence Proofs
- State the existential claim.
- Identify a principle that can force existence.
- Use contradiction, counting, pigeonhole reasoning, averaging, extremality, or another theorem.
- Show that assuming no witness exists is impossible, or that the available structure forces at least one witness.
- Conclude existence without claiming more than the argument provides.
Example: Full Constructive Workflow
Prove:
\[ \forall n\in\mathbb Z,\;\exists m\in\mathbb Z \]such that \(m\) is odd and \(m>n\).
Step 1: Start with arbitrary input.
Let \(n\in\mathbb Z\).
Step 2: Construct a witness.
Define
\[ m=2|n|+1. \]Step 3: Verify the domain.
Since \(|n|\in\mathbb Z\),
\[ m\in\mathbb Z. \]Step 4: Verify oddness.
\[ m=2|n|+1 \]has the form \(2k+1\), so \(m\) is odd.
Step 5: Verify size.
Since \(|n|\ge n\),
\[ 2|n|+1>n. \]Therefore,
\[ \boxed{\forall n\in\mathbb Z,\;\exists\text{ an odd integer }m>n.} \]Example: Full Nonconstructive Workflow
Prove that among any \(101\) integers, there exist two whose difference is divisible by \(100\).
Step 1: Identify the categories.
There are \(100\) residue classes modulo \(100\).
Step 2: Apply pigeonhole reasoning.
The \(101\) integers are distributed among \(100\) residue classes.
Therefore two distinct integers \(a,b\) share a residue:
\[ a\equiv b\pmod{100}. \]Step 3: Translate the collision.
\[ 100\mid(a-b). \]The proof guarantees that such a pair exists, although it does not identify the pair without additional data.
Practice 1: Explicit Witness
Prove constructively that there exists a positive integer divisible by both \(4\) and \(6\).
Practice 2: Construct a Larger Integer
Prove constructively:
\[ \forall n\in\mathbb Z,\;\exists m\in\mathbb Z\text{ such that }m>n. \]Practice 3: Construct an Even Integer
Prove that for every integer \(n\), there exists an even integer \(m\) with
\[ m>n. \]Practice 4: Construct a Function
Give a constructive proof that there exists a surjective function
\[ f:\mathbb Z\to\mathbb Z. \]Practice 5: Pigeonhole Existence
Explain why the proof that \(13\) people contain two sharing a birth month is generally nonconstructive if no birthday data are supplied.
Practice 6: Existence versus Uniqueness
Does constructing one integer larger than \(10\) prove that there is a unique integer larger than \(10\)? Explain.
Practice 7: Negation
Negate:
\[ \exists n\in\mathbb Z\text{ such that }n^2=2. \]Practice 8: Universal-Existential Construction
Prove:
\[ \forall n\in\mathbb Z,\;\exists m\in\mathbb Z \]such that
\[ m=n+5. \]Practice 9: Domain Check
A theorem requires an integer witness, but a student constructs
\[ x=\frac12. \]What must be checked before this can prove the theorem?
Practice 10: Algorithmic Construction
A student gives a procedure intended to find a witness but does not prove that the procedure terminates.
Explain the problem.
Practice Answers
Practice 1
Choose
\[ \boxed{12}. \]Since
\[ 4\mid12 \]and
\[ 6\mid12, \]the required positive integer exists.
Practice 2
Let \(n\in\mathbb Z\).
Choose
\[ m=n+1. \]Then \(m\in\mathbb Z\) and \(m>n\).
Practice 3
One valid construction is
\[ m=2(|n|+1). \]This is an even integer and
\[ m>n. \]Practice 4
Define
\[ f(n)=n. \]This identity function maps \(\mathbb Z\) onto \(\mathbb Z\).
For every \(y\in\mathbb Z\), choose \(x=y\). Then
\[ f(x)=y. \]Therefore \(f\) is surjective.
Practice 5
The counting argument proves that some pair shares a month, but without the actual birth-month data it does not identify which pair.
Thus the argument establishes existence without an explicit witness.
Practice 6
No.
One witness proves only that at least one such integer exists.
In fact, infinitely many integers are larger than \(10\).
Practice 7
The negation is
\[ \boxed{\forall n\in\mathbb Z,\;n^2\ne2.} \]Practice 8
Let \(n\in\mathbb Z\) be arbitrary and define
\[ m=n+5. \]Since integers are closed under addition,
\[ m\in\mathbb Z. \]Therefore the required \(m\) exists for every integer \(n\).
Practice 9
The student must verify that the proposed witness belongs to the required domain.
Since
\[ \frac12\notin\mathbb Z, \]it cannot serve as an integer witness.
Practice 10
A procedure that might continue forever does not guarantee that a witness will ever be produced.
To count as an effective construction, the proof must justify that the procedure reaches a valid output.
What to Remember
An existence statement has the form
\[ \boxed{\exists x\in S\text{ such that }P(x).} \]- a constructive proof provides a witness, formula, or procedure;
- the witness must belong to the required domain;
- every required property must be verified;
- nonconstructive proofs can establish existence without identifying a specific witness;
- pigeonhole reasoning, contradiction, averaging, and extremal arguments can force existence;
- existence does not imply uniqueness;
- universal-existential statements usually require a construction depending on an arbitrary input;
- algorithmic constructions should include a termination argument when necessary.
The strategic question is: Can I actually build the object being claimed, or is it easier to prove that the surrounding structure makes its existence unavoidable?
Where We Go Next
Existence proofs establish that at least one object satisfies a condition. The final lesson in this proof family turns the perspective around: universal claims can often be disproved by producing just one object that fails the stated property.
The next lesson, Counterexamples, develops that method and shows how a single carefully chosen example can refute an incorrect universal claim.