What an Existence Claim Requires
In Proof by Cases, we divided possible situations into cases and established a conclusion in each one. An existence proof has a different target: it must establish that at least one object in a stated domain has a specified property. The key question is not whether every candidate works, but whether we can establish one suitable candidate.
The logical form of an existence claim is \(\exists x\in D,\ P(x)\). Here \(D\) is the domain of permitted objects, and \(P(x)\) is the condition the object must satisfy. To prove the claim, we can identify an object \(c\), verify that \(c\in D\), and then prove \(P(c)\). Such an object \(c\) is called a witness to the existential statement.
The order of the work matters. First identify what the variable is allowed to be; then choose a candidate; finally check it against the entire predicate. A number that satisfies the equation but is outside the specified domain is not a witness. Nor is it enough to say that a solution “can be found” if the argument never establishes that one exists.
The quantifier also determines how much must be proved. An existential statement asks for at least one successful object. A universal statement, such as “every real number has property \(P\),” requires the conclusion for an arbitrary object. An existence proof does not need to classify all objects that work, and it does not assert that the witness is the only one.
| Claim form | What the proof must establish |
|---|---|
| \(\exists x\in D,\ P(x)\) | At least one \(x\in D\) satisfies \(P(x)\). |
| \(\forall x\in D,\ P(x)\) | Every \(x\in D\) satisfies \(P(x)\). |
| There is exactly one \(x\in D\) with \(P(x)\) | Existence of a witness and, separately, that no other object works. |
The last row includes two logically different tasks. This tutorial focuses on establishing existence. Whether a witness is unique is a separate question; a proof that supplies one witness has not, by itself, ruled out additional witnesses.
Choosing and Checking a Witness
Sometimes the witness is apparent from the statement. For an equation, solving or factoring may suggest a candidate. For an inequality, a simple expression such as a given number plus \(1\) may be enough. For a claim involving two given real numbers, an expression built from both may be more useful than a fixed constant.
After choosing the candidate, substitute it into the condition and show the required conclusion explicitly. This verification is the proof; the act of naming a candidate alone is not. If the claim has several requirements joined by “and,” all of them must be checked. A witness satisfying only one part does not establish the conjunction.
Worked Example: An Integer Solving a Linear Equation
Claim. There exists an integer \(n\) such that \(3n+2=17\).
Proof. Choose \(n=5\). Since \(5\in\mathbb Z\), the candidate belongs to the required domain. Substitution gives $$ 3n+2=3(5)+2=15+2=17. $$ Thus \(n=5\) is an integer satisfying the equation, so the claimed integer exists.
The domain check is part of the argument: the claim asks for an integer solution, not merely a real solution. The equality check then verifies the predicate for the proposed witness.
Worked Example: One Number Meeting Two Conditions
Claim. There exists a real number \(t\) such that \(|t-3|<1\) and \(t>0\).
Proof. Choose \(t=3\). This is a real number. Moreover, $$ |t-3|=|3-3|=0<1 $$ and \(t=3>0\). The same candidate satisfies both conditions, so it witnesses the stated existence claim.
It would not be enough to show that one real number satisfies the absolute-value inequality and a different real number is positive. The predicate requires both conditions of one and the same \(t\).
These examples use a fixed numerical witness. In many useful statements, the witness must be selected from the input data. In that situation, the proof gives a rule for building the witness and then verifies why the rule works for every permitted input.
A Witness Constructed from the Hypotheses
Suppose two real numbers \(a\) and \(b\) satisfy \(a<b\). The claim that another real number lies strictly between them is existential: the candidate may depend on both \(a\) and \(b\). The midpoint is a natural construction because it treats the endpoints symmetrically.
Proof. Let \(a,b\in\mathbb R\) and suppose \(a<b\). Define $$ c=\frac{a+b}{2}. $$ Since the real numbers are closed under addition and division by the nonzero real number \(2\), \(c\in\mathbb R\). From \(a<b\), adding \(a\) to both sides gives \(2a<a+b\). Dividing by the positive number \(2\) preserves the inequality, so $$ a<\frac{a+b}{2}=c. $$ Also, adding \(b\) to both sides of \(a<b\) gives \(a+b<2b\). Dividing by \(2>0\) yields $$ c=\frac{a+b}{2}<b. $$ Therefore \(c\) is a real number satisfying \(a<c<b\), as required.
This proof makes the witness visible: \(c\) is not an unspecified number whose existence is merely asserted. It is an expression formed from the inputs. The proof then checks the domain and both strict inequalities. If the hypothesis were only \(a\leq b\), the same construction would not always work: when \(a=b\), it gives \(c=a=b\), which is not strictly between the endpoints.
Worked Example: Finding a Number Between Two Endpoints
Claim. There exists a real number strictly between \(-4\) and \(7\).
Proof. The endpoints satisfy \(-4<7\), so use their midpoint as the witness: $$ c=\frac{-4+7}{2}=\frac{3}{2}. $$ This is real. To verify that it is strictly between the endpoints, note that $$ -4=-\frac{8}{2}<\frac{3}{2}<\frac{14}{2}=7. $$ Thus \(c=\frac32\) has the required property.
The general construction supplies a method, while this calculation checks one particular instance directly. Both inequalities are needed; verifying only that \(c\) exceeds the left endpoint would not establish that it lies below the right one.
Existence from a General Construction
An existential statement can also have the form “for every input, there exists an output.” Its quantifiers are ordered: $$ \forall x\in D,\ \exists y\in E,\ P(x,y). $$ For each permitted \(x\), the proof must give an eligible \(y\) that satisfies the condition for that \(x\). The witness may vary with \(x\). A useful technique is to define \(y\) directly in terms of \(x\), then verify the desired property using an earlier result.
Worked Example: A Number Larger Than an Absolute Value
Claim. For every real number \(x\), there exists a positive real number \(y\) such that \(y>|x|\).
Proof. Let \(x\in\mathbb R\) be arbitrary, and choose $$ y=|x|+1. $$ The absolute value of a real number is real, so \(y\in\mathbb R\). By the definition of absolute value, \(|x|=x\geq0\) if \(x\geq0\), and \(|x|=-x>0\) if \(x<0\); hence \(|x|\geq0\). Consequently \(y=|x|+1\geq1>0\), so \(y\) is positive. Also, $$ y=|x|+1>|x|, $$ because \(1>0\). For this arbitrary \(x\), the constructed \(y\) is a positive real number larger than \(|x|\). Therefore the claim holds for every real \(x\).
A fixed choice such as \(y=1\) would not prove the statement for every \(x\): if \(x=2\), then \(1\) is not greater than \(|x|=2\). The expression \(|x|+1\) adapts to the input and makes the required inequality immediate.
The proof establishes the needed fact \(|x|\geq0\) directly from the definition of absolute value. This is a common pattern in a sequence of proofs: identify an appropriate witness, then apply an established result to verify that the witness meets the condition.
Existence, Cases, and Contradiction
Direct construction is often the clearest approach, but it is not the only possible proof structure. A case argument can establish existence if every case provides at least one witness satisfying the required condition. The cases must cover the inputs allowed by the hypotheses, just as in any proof by cases. If witnesses differ from case to case, specify which witness works in each branch.
An existence proof can also use proof by contradiction, the method introduced in Proof by Contradiction. The negation of an existential statement is a universal statement that denies the property at every candidate, as established in Negating Existential Statements. One may assume that no witness exists and derive a contradiction. That approach can prove existence even when it does not identify a concrete witness, but the assumption and the contradiction must be linked to the exact domain and predicate in the claim.
When a construction is available, it often makes the proof easier to inspect: the reader can see the candidate and test each requirement. When no direct candidate is apparent, another valid proof method may be needed. In either case, the final obligation is unchanged: establish that at least one object in the stated domain satisfies the stated property.
Determine what kind of object is required and what properties it must have.
Use the equation, inequality, definitions, or input data to identify a plausible witness.
Check that the candidate really belongs to the set named in the claim.
Substitute the candidate or apply established results to verify each part of the predicate.
State explicitly that the verified candidate is a witness and therefore the existential claim holds.
Common Gaps to Avoid
One gap is giving a candidate without checking it. For instance, proposing a solution to an equation does not establish that it solves the equation until substitution or an equivalent argument verifies the equality. Another gap is overlooking the domain: a real solution does not automatically give an integer solution. The witness must be admissible as well as successful.
A further mistake is proving too little. If the predicate requires an equation and two inequalities, each condition must hold for the same candidate. And when the claim begins “for every \(x\), there exists \(y\),” choosing a witness for just one value of \(x\) is insufficient. Begin with an arbitrary allowed input, construct a corresponding witness, and verify the condition for that input.
The best existence proofs are neither longer nor more complicated than the claim requires. A short explicit construction is fully rigorous when it checks the domain and the predicate. If the witness is built from arbitrary inputs, explain why the construction works for all such inputs rather than relying on a single numerical illustration.
Check Your Understanding
For each question, identify the domain and the property that a witness must satisfy. Verify every condition in your argument.
- Prove that there exists an integer \(m\) such that \(4m-1=11\). State your witness and check that it is an integer.
- For every real \(x\), construct a real number \(y\) such that \(y>x\). Verify the strict inequality for your choice.
- Let \(a,b\in\mathbb R\) with \(a<b\). Use \(c=(a+b)/2\) to verify that there is a real number satisfying \(a<c<b\).
- A claim says there exists a real \(t\) satisfying \(t^2=9\) and \(t>0\). Give one witness and verify both conditions. Does your proof need to show that it is the only witness?
- Explain why finding a real number satisfying an equation does not by itself prove that an integer satisfying the same equation exists.
- In the claim \(\forall x\in\mathbb R,\ \exists y\in\mathbb R,\ y>|x|\), explain why the witness may depend on \(x\), and verify the construction \(y=|x|+1\).