Questions: Existence Proofs

Question 1

A proof proceeds as follows: 'Either √2^√2 is rational (done — take a = b = √2), or it is irrational. If irrational, then (√2^√2)^√2 = √2² = 2 is rational. Either way, an example exists.' The proof never determines which case holds. This proof is best described as:

• A. Invalid — a proof of existence must identify and exhibit the specific witnessing object
• B. A valid non-constructive existence proof that establishes existence via a dilemma without pinpointing the witness
• C. Incomplete — it would become a valid proof once a calculation resolves which case holds
• D. A proof by induction, since it considers two cases and builds to a conclusion

Answer: (B)

This is the classic example of a non-constructive existence proof. It proves that at least one of two specific values is the witness, but never determines which one — and this uncertainty is irrelevant to validity. In mainstream mathematics, logical correctness is the standard, not the ability to compute or exhibit the object. Option A expresses the constructivist objection, which is a minority philosophical position, not a mainstream mathematical requirement.

Question 2

A constructive existence proof differs from a non-constructive one primarily in that:

• A. A constructive proof uses contradiction to derive the object; a non-constructive proof builds it directly
• B. A constructive proof is accepted in mainstream mathematics; a non-constructive proof is not
• C. A constructive proof explicitly exhibits an object satisfying the required property
• D. A constructive proof applies only to finite mathematical objects, not infinite sets

Answer: (C)

A constructive proof exhibits the actual witness: to prove a prime greater than 100 exists, exhibit 101. A non-constructive proof establishes existence indirectly — typically by showing that non-existence leads to a contradiction. Both are accepted in mainstream mathematics (option B is wrong). Option A reverses the typical association: contradiction is often used in non-constructive proofs, not constructive ones.

Question 3

In a non-constructive existence proof, it is possible to know that an object with property P exists while being unable to determine which specific object satisfies P.

• T. True
• F. False

Answer: True

The √2^√2 example demonstrates this precisely: the proof establishes that a rational number of the form a^b (with a, b irrational) exists, but leaves open which of the two candidates is the witness. Mathematical knowledge of existence and computational ability to identify the witness are distinct.

Question 4

Non-constructive existence proofs are considered invalid in mainstream mathematics because they fail to produce a concrete witnessing object.

• T. True
• F. False

Answer: False

This is the constructivist position, not mainstream mathematics. Constructivism (associated with Brouwer and others) holds that existence requires constructibility, but it is a minority philosophical view. Mainstream mathematics accepts non-constructive proofs fully — logical validity, not computability, is the criterion. Many important existence results in analysis and algebra are non-constructive.

Question 5

What is the philosophical objection to non-constructive existence proofs, and why does mainstream mathematics accept them anyway?

Model answer: Constructivists argue that mathematical existence should require the ability to construct or compute the object — a proof that something 'must exist' because its absence leads to contradiction is epistemically empty if you cannot exhibit it. Mainstream mathematics accepts non-constructive proofs because the standard of proof is logical validity, not computability. If assuming non-existence leads to a contradiction, classical logic guarantees the object exists. Whether this satisfies philosophical intuitions about 'real' existence is a separate question from mathematical correctness.

This debate matters practically: constructive proofs give you an algorithm; non-constructive proofs only guarantee existence. In computer science and applied mathematics, constructive existence is often more useful. But for pure mathematics, non-constructive proofs extend the range of provable results significantly — some truths can only be proven non-constructively.