The short answer#
A statement of the form ∃x P(x) says at least one object satisfies P. There are two ways to prove one.
| Constructive | Nonconstructive | |
|---|---|---|
| What you do | Produce a specific x and verify P(x) | Show that no x satisfying P is impossible |
| You end up with | An actual example in hand | Knowledge that one exists, and no example |
| Typical tools | A formula, an algorithm, a direct calculation | Contradiction, counting, pigeonhole |
1. Exhibit a witness — name a specific object.
2. Verify the predicate — show P actually holds for that object.
Skipping the second is the standard way to lose the marks. A witness on its own is a claim, not a proof.
The smallest possible example#
Claim. There exists an even prime.
Proof. Take n = 2. Then 2 is even, since 2 = 2·1, and 2 is prime, since its only positive divisors are 1 and 2. So n = 2 satisfies both conditions. ∎
That is a complete proof, and it is complete precisely because the verification sentence is there. "Take n = 2. ∎" is not a proof — it is an assertion that the reader is being asked to check on your behalf.
Existence proofs about functions#
Existence statements get harder to read when the witness is not a number but a quantity buried inside quantifiers. The procedure does not change.
Call a function f: ℝ → ℝ periodic if
∃T > 0 (∀x ∈ ℝ, f(x + T) = f(x)),
and call the smallest such T the period.
The existential quantifier is on T. So the witness you must produce is a number T, and the verification you must supply is the universally quantified statement that follows.
Claim. The fractional-part function f(x) = x − ⌊x⌋ is periodic.
Proof. Take T = 1, which is positive. Let x ∈ ℝ be arbitrary. The floor function satisfies ⌊x + 1⌋ = ⌊x⌋ + 1, because adding an integer to x shifts the greatest integer below it by exactly that integer. Therefore
f(x + 1) = (x + 1) − ⌊x + 1⌋ = (x + 1) − (⌊x⌋ + 1) = x − ⌊x⌋ = f(x).
Since x was arbitrary, f(x + 1) = f(x) for all real x, so T = 1 works and f is periodic. ∎
Two structural details are doing the work. The witness T = 1 is named in the first line. Then x is introduced as arbitrary — the inner ∀ has to be discharged honestly, not by checking a couple of values.
Finding the period is a second, different claim#
Showing some T works does not show which T is smallest. That is a separate statement and needs a separate argument, usually of the form "this one works, and nothing smaller does."
For the fractional part: suppose 0 < T < 1 were also a period. Evaluate at x = 0. Then f(0) = 0 − 0 = 0, while f(0 + T) = T − ⌊T⌋ = T − 0 = T, since 0 < T < 1. Periodicity would force T = 0, contradicting T > 0. So no smaller period exists and the period is exactly 1.
What a nonconstructive proof looks like#
Contrast the above with an argument that produces nothing you can hold.
Claim. There exist irrational numbers a and b such that ab is rational.
Proof. Consider √2√2. Either it is rational or it is not.
- If it is rational, take a = b = √2 and we are done.
- If it is irrational, take a = √2√2 and b = √2. Then ab = (√2√2)√2 = √22 = 2, which is rational.
Either way such a pair exists. ∎
The proof is valid and it never tells you which pair works. That is the defining feature: existence established, witness not produced. A question that asks specifically for a direct or constructive existence proof is ruling this style out.
Uniqueness is yet another claim#
∃!x P(x) — "there is exactly one x" — is two statements stapled together, and a complete proof does both halves:
- Existence. Produce a witness and verify P holds for it.
- Uniqueness. Assume P(a) and P(b) both hold, then show a = b.
The second half is the one people leave out. Note its shape: you do not assume a ≠ b and hunt for a contradiction unless you want to; the direct route — take two arbitrary objects satisfying P and prove they must be equal — is usually shorter and always sufficient.
Where these go wrong#
- Naming a witness and stopping. The verification is not optional and is not obvious. Write the line that checks P.
- Verifying at examples instead of in general. If the predicate contains a ∀, you must take an arbitrary element. Checking x = 0, 1, 2 proves nothing about all x.
- Proving existence when asked for the value. "Show f is periodic and find its period" is two tasks. The second needs a minimality argument.
- Treating a nonconstructive proof as constructive. If your argument ends by ruling out the alternative rather than producing an object, it is not constructive, whatever the heading says.
- Forgetting the side conditions on the witness. If the statement says ∃T > 0, then confirming T > 0 is part of the proof. A witness that fails the constraint is not a witness.
- Skipping uniqueness. ∃! is not ∃. Half a proof scores half.
Test yourself in the free Kestrel Exams app
Discrete Math practice is free and works offline — topic-selectable drills on proof methods, quantifiers, and induction.
Drill proof methods →Frequently asked questions#
What are the two parts of a constructive existence proof?
Exhibit a specific witness, and verify that the predicate actually holds for that witness. Naming the object is only the first half. A proof that says "take n = 2" without showing that 2 satisfies the conditions has asked the reader to do the verification instead of doing it.
What is the difference between a constructive and a nonconstructive existence proof?
A constructive proof produces an object you can hold and checks it. A nonconstructive proof establishes that an object must exist without producing one, typically by contradiction or by a counting argument. Both are valid, but a question asking for a direct or constructive proof is ruling the second one out.
How do you prove a function is periodic?
The definition is existential in the period, so you name a specific positive T and then prove the universally quantified statement f(x + T) = f(x) for an arbitrary x. For the fractional-part function x − ⌊x⌋, take T = 1 and use ⌊x + 1⌋ = ⌊x⌋ + 1 to show the values agree.
Is finding the period the same as proving periodicity?
No. Proving periodicity means showing some period exists. Identifying the period means showing your value works and that nothing smaller does. The second usually comes from evaluating at one well-chosen point and deriving a contradiction from any smaller candidate.