Constructive Versus Nonconstructive Proofs

Existence Claims and Witnesses

The previous tutorial combined existence and uniqueness: an exactly-one proof must first establish that an object exists and then show that any two objects with the required property are equal. This tutorial focuses on the first part. When a claim says that there exists an object with a property, a proof may establish that claim in different ways.

Let \(D\) be a domain and \(P(x)\) a condition on elements of \(D\). An existence claim has the form $$ \exists x\in D,\ P(x). $$ An element \(c\in D\) satisfying \(P(c)\) is called a witness for this claim. A familiar way to prove existence is to name a witness and check that it belongs to the domain and satisfies the condition.

This is the central idea of a constructive existence proof in its elementary use here: it supplies a witness, often by giving a formula or a procedure for finding one, and verifies that the witness works. The word “constructive” can have more technical meanings in other settings. For our purposes, the practical question is whether the argument identifies an object that can be checked against the stated property.

A nonconstructive existence proof, in the usual elementary sense, establishes that at least one suitable object exists without specifying which object it is or giving a direct way to produce it. Proof by contradiction is one common route: assume that no object in the domain has the property, derive an impossibility, and conclude that the assumption that none exists must be false.

The logical step is connected to the negation rules established earlier in Negating Existential Statements. The negation of \(\exists x\in D,\ P(x)\) is \(\forall x\in D,\ \neg P(x)\). Thus, when we assume that no witness exists, we assume that every element of the domain fails the property. A contradiction from that assumption rules out the claim that every element fails.

Two Routes to an Existence Proof

The distinction is about the information supplied by the proof, not about whether the conclusion is true. If a constructive proof exhibits a witness, that witness establishes existence. If a nonconstructive proof rules out the possibility that no witness exists, it also establishes existence. The two arguments can be equally valid while offering different answers to the practical question, “Which object works?”

This comparison should not be read as a ranking of good and bad proofs. A nonconstructive argument can be completely rigorous and can be the shortest or most natural way to establish a result. A constructive proof may be preferable when an application needs an actual value or when later arguments depend on how the witness was obtained. The right method depends on what the theorem asks for and what information will be useful.

Constructing a Witness from the Claim

A construction often comes from working backward from the desired property. First ask what an object must look like if it is to satisfy the condition. Then use the definitions or hypotheses to choose an object of that form. Finally, substitute the choice into the condition and check each equality or inequality. The proof should present the verification clearly, rather than leaving the reader to infer that the proposed construction works.

For a statement with a universal hypothesis followed by an existential conclusion, the witness may depend on the arbitrary input. For example, a claim of the form “for every \(n\), there exists \(k\)” does not generally ask for one fixed \(k\) that works for every \(n\). A construction may instead give \(k\) as a formula in \(n\). The domain of each variable and the dependency between them should be kept explicit.

Existence Without Naming the Witness

A proof can establish existence without beginning with a proposed object. In proof by contradiction, to prove that some object has a property, assume that no object has it. The assumption says that each object in the domain fails the property. If this leads to a contradiction, the assumption is false, so at least one object must satisfy the property.

Here is a small example. It uses only the sign rules for real numbers and shows how an argument can identify that a suitable pair exists without first naming which pair it is.

Proof. Suppose, for contradiction, that none of the three products is nonnegative. Since each product is real, this means $$ xy<0,\qquad xz<0,\qquad yz<0. $$ The inequalities \(xy<0\) and \(xz<0\) imply \(x\ne0\), and both \(y\) and \(z\) have sign opposite to \(x\). Hence \(y\) and \(z\) have the same sign. Because neither is zero, their product is positive, so \(yz>0\). This contradicts \(yz<0\). Therefore it is impossible for all three products to be negative, and at least one of them is nonnegative.

The proof guarantees a pair but does not single out one fixed product as the one that works. Its conclusion has the form “at least one of these alternatives holds.” This is a modest example of an existence argument that supplies less direct information than a proof that names a particular pair. If values for \(x,y,z\) are given, a separate check of their signs can determine which pair works.

Proof by Contradiction Is Not a Synonym for Nonconstructive

It is useful to keep two classifications separate. “Direct” and “by contradiction” describe the structure of an argument. “Constructive” and “nonconstructive” describe, in the elementary sense used here, whether the argument supplies a witness or a way to obtain one. These distinctions are related, but they are not identical.

A proof by contradiction can still reveal an explicit witness. Suppose we want to prove that there exists an integer \(k\) with \(k^2=16\). One could argue indirectly, but the direct choice \(k=4\) already verifies the claim. Even if an indirect proof is written, that does not make a witness disappear from the mathematics. Conversely, an argument using cases may establish that one of several candidates works without naming a single candidate that works in every case.

The three-number theorem illustrates a proof by contradiction whose conclusion is an existence claim: one of several products must be nonnegative. The proof is valid because assuming that every candidate fails produces an impossibility. It is not necessary to attach an absolute label to every proof of this kind. The useful question is more specific: what witness or information can be extracted from the argument as written?

This distinction matters in applications. If a theorem only guarantees that some real number or integer exists, that may be enough for a logical argument. If a later step needs the value, a bound, or a method for selecting the object, an existence guarantee alone may not supply enough detail. In that situation, look for a construction or a further result that identifies the witness.

Choosing and Assessing a Strategy

When you meet an existential claim, begin by asking whether its hypotheses suggest a candidate. An equation may suggest substitution; a definition may directly encode the needed form; a parity assumption may lead to separate formulas. If a candidate is available, verify it carefully. If no natural candidate appears, it may be productive to ask what would follow if every candidate failed. A contradiction can establish existence even when the witness is not immediately apparent.

In either approach, check the logical strength of the final sentence. If the proof verifies a candidate, it proves at least one exists. If it shows any two candidates must be equal, it proves at most one exists, as discussed in Uniqueness Proofs. If it only derives a contradiction from “no candidate exists,” it proves existence, but it does not by itself establish uniqueness. To claim exactly one, the two obligations treated in Existence and Uniqueness Proofs are still required.

A common mistake is to regard the absence of a displayed formula as a defect. It is not a defect if the stated goal is only to prove existence and the reasoning is complete. Another mistake is to treat an unverified candidate as a completed construction. The proof must show that the object is in the correct domain and satisfies every part of the property. A third mistake is to assume that a proof by contradiction is automatically nonconstructive. The proof’s actual content, rather than its label, determines what it tells us about a witness.

A reliable proof should make its information visible. When constructing a witness, state it and verify it. When proving existence indirectly, clearly identify the assumption that no witness exists and the contradiction that follows. When the conclusion requires exactly one object, keep the existence and uniqueness arguments separate, then combine them only after both have been proved.