Just point at one#
Someone claims: “There is a person in this room who owns a red car.” How would you prove it? Work it out before you read on.
Most people stop at “point at whoever owns one.” That is half an answer, and half is where the marks go.
You point at someone and you show the car, and the car is red. Both halves. Pointing on its own is a claim; the checking is what turns it into a proof.
That is a constructive existence proof, and it is the only kind of proof where pointing counts at all.
In symbols, a statement like ∃x P(x) — read “there exists an x with property P” — says at least one thing has that property. The thing you point at is called a witness.
The two jobs, and the one people skip#
| Constructive | Non-constructive | |
|---|---|---|
| What you do | Produce one specific thing and check it works | Show that having none is impossible |
| You end up with | An actual example in your hand | Knowing one exists, without having it |
| Usual tools | A formula, a recipe, a direct calculation | Contradiction, counting, pigeonhole |
1. Name a specific witness. Not “some number” — an actual one.
2. Verify it. Show the property really does hold for that thing.
Skipping the second is the standard way to lose marks here. A witness on its own is an assertion the reader is being asked to check on your behalf.
The smallest possible example#
Claim. There exists an even prime number.
Proof. Take n = 2. It is even, since 2 = 2·1. It is prime, since its only positive divisors are 1 and itself. So n = 2 satisfies both conditions. ∎
That is a complete proof, and it is complete because the second sentence is there. “Take n = 2. ∎” is not a proof.
When the thing you point at is not a number#
Existence claims get harder to read when the thing you must point at is buried inside other symbols. The job does not change.
A function f is called periodic if it repeats — like a wave that looks the same every time you slide it along by some fixed distance. Written out:
∃T > 0 (∀x ∈ ℝ, f(x + T) = f(x))
Read it: there is some slide distance T, bigger than zero, such that for every x, sliding by T leaves the value unchanged. Here T is an ordinary number — the size of the slide, called the period.
The “there exists” is attached to T. So T is what you point at, and everything after it is what you must verify.
Claim. The fractional-part function f(x) = x − ⌊x⌋ is periodic. (⌊x⌋ means “round down to a whole number”, so f keeps just the bit after the decimal point.)
Proof. Take T = 1, which is positive. Let x be any real number. Rounding down satisfies ⌊x + 1⌋ = ⌊x⌋ + 1, because adding a whole number shifts the rounded-down value by exactly that amount. So
f(x + 1) = (x + 1) − ⌊x + 1⌋ = (x + 1) − (⌊x⌋ + 1) = x − ⌊x⌋ = f(x)
Since x was arbitrary, this holds for every real x, so T = 1 works and f is periodic. ∎
Two structural things did the work. The witness T = 1 is named in the very first line. Then x is introduced as arbitrary — the “for every x” has to be honoured honestly, not by trying two values and shrugging.
“Smallest” is a different claim#
Showing that some T works does not show which T is smallest. That is a separate claim needing a separate argument, usually shaped like “this one works, and nothing smaller does.”
For the fractional part: suppose some T with 0 < T < 1 were also a period. Check at x = 0. Then f(0) = 0, while f(0 + T) = T − ⌊T⌋ = T, since T is between 0 and 1. Periodicity would force T = 0, contradicting T > 0. So no smaller period exists, and the period is exactly 1.
“There exists” and “the smallest such” are two different questions. Answer the one you were asked, and do not assume the first answer settles the second.
Proving one exists without finding it#
Some existence proofs never produce an example at all. They show that having none would be impossible, and stop there. These are called non-constructive.
The classic: there are infinitely many primes. The proof shows that any finite list of primes must be missing one. But it never hands you that missing prime. It never names a single specific large prime. You finish knowing they exist without holding one.
Both kinds are valid proofs. But if a question says “find” or “construct”, a non-constructive argument does not answer it, however correct it is.
“Exactly one” is another claim again#
“There is exactly one” asks for two things: that at least one exists, and that no two different ones do.
Prove existence by pointing, as above. Then prove uniqueness the direct way: take two objects that both have the property, and show they must be the same thing. You do not have to assume they are different and hunt for a contradiction — the direct route is usually shorter and is always enough.
Where these go wrong#
- Naming a witness and stopping. The verification is half the proof and it is the half people leave out.
- A vague witness. “Some large number” is not a witness. Name it.
- Forgetting the side conditions. If the claim says the thing must be positive, saying so is part of the proof. A witness that fails the constraint is not a witness.
- Checking a “for every” on a few examples. Once you have pointed, the rest is usually a universal claim and needs an arbitrary element, not samples.
- Answering “find” with a non-constructive argument. Correct, and still not what was asked.
- Treating “exists” as though it settled “smallest”. Two claims, two proofs.
- Proving uniqueness by contradiction out of habit. Taking two and showing they coincide is shorter and always works.
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 is a constructive existence proof?
One that proves something exists by producing a specific example and checking it works. The example is called a witness. Both halves are required — naming a witness without verifying it is an assertion, not a proof.
What is a witness in a proof?
The specific object you point at to settle a “there exists” claim. For “there is an even prime”, the witness is 2. For “this function is periodic”, the witness is the actual slide distance, such as T = 1.
What is the difference between a constructive and a non-constructive proof?
A constructive proof hands you an example. A non-constructive one shows that having no example would be impossible, without ever producing one — the proof that there are infinitely many primes is the classic case. Both are valid, but a question that says “find” is not answered by the second kind.
Does proving something exists prove it is the smallest?
No. Those are two separate claims needing two separate arguments. Showing some period works says nothing about which period is smallest; that needs its own proof, usually of the form “this one works and nothing smaller does.”
Something here not clear? A topic you wish we covered? Tell us. We read every message, and a request is the fastest way to get a guide written — several of these exist because somebody asked.