3.2 Counterexamples, Proof by Contradiction, and Existence: Knowing Whether to Find One or Rule Out All

Proving that "all inputs are safe" and disproving it are vastly different in effort. A universal claim requires examining the entire domain; to disprove it, you only need to find a single input that satisfies the premise but violates the conclusion. Choosing the wrong proof objective can turn a simple problem into a complex one.

Quantifiers Determine the Shape of Evidence

Proposition	Proof Requires	Refutation Requires
∀x P(x)	A general proof for arbitrary x	A x such that ¬P(x)
∃x P(x)	A specific witness	A proof that no x satisfies P
∃!x P(x)	Existence plus uniqueness	Nonexistence, or at least two distinct witnesses

After seeing a proposition, first circle the quantifiers, then decide whether to construct a specific object or establish general reasoning.

Counterexamples Must Hit the Premise

Claim:

For any integer n, if n is prime, then n is odd.

Counterexample n=2: It satisfies the premise "is prime" but fails the conclusion "is odd."

n=4 is not a counterexample because it does not satisfy the premise. In program testing, the same principle applies: to refute the statement "all valid requests return a 200 status," you must provide a valid request that results in a 500 error. A 500 response from an invalid request only indicates a potential issue with a different property.

A counterexample must also operate within the domain specified by the original statement. A claim that holds for all real numbers is not equivalent to one that holds for all integers.

Constructive Existence Proof: Providing a Witness

Proof: There exists a square of an even prime number greater than 10.

We can provide the square of 4, namely 16, and verify:

4 is even;
4 is not prime.

This witness fails to satisfy the condition of being an even prime, so the proof fails. The only even prime is 2, and its square is 4, which is not greater than 10. Thus, the original statement is actually false.

This deliberately failing example illustrates that a witness must satisfy each condition in the formula individually, merely appearing close is insufficient.

Now consider a valid proposition: There exist two irrational numbers a,b such that a^b is rational. A classic non-constructive approach involves considering:

x = (√2)^(√2)

• If x is rational, then take a=b=√2;
• If x is irrational, then take a=x, b=√2, in which case a^b=2.

This case-based proof demonstrates the existence of a witness, but does not specify which branch it falls into. If an actual computational object is required, a constructive proof is typically more useful.

Uniqueness Split in Two

Prove that "there exists a unique x such that P(x)" by:

1. Existence: Construct an x₀ and verify that P(x₀);
2. Uniqueness: Assume both P(x) and P(y) hold, and derive x=y.

For example, the linear equation ax+b=0 has a unique real solution when a≠0:

• Existence: x₀=-b/a satisfies the equation when substituted in;
• Uniqueness: If ax+b=0 and ay+b=0 both hold, subtracting them yields a(x-y)=0. From a≠0, we conclude x=y.

Database unique constraints follow a similar principle: a record must first exist, and the constraint only guarantees "at most one", it does not ensure existence.

Proof by Contradiction: Assume the Conclusion is False and Derive a Contradiction

Prove that √2 is irrational. Suppose, for the sake of contradiction, that there exist coprime positive integers p,q such that:

√2 = p/q

Squaring both sides gives:

p² = 2q²

Thus, p² is even, and therefore p is even. Let p=2k, and substitute back:

4k² = 2q²
q² = 2k²

Hence, q is also even, contradicting the assumption that p,q are coprime. Therefore, the initial assumption must be false.

The real contradiction lies in the simultaneous truth of "p,q are coprime" and "both share a common factor of 2", not in the result appearing unreasonable.

When to Use Contraposition, When to Use Proof by Contradiction

To prove p→q:

• Use contraposition by assuming ¬q and deriving ¬p;
• Use proof by contradiction by assuming p∧¬q and deriving a clearly evident contradiction.

If ¬q can naturally be expressed as structural information, contraposition is typically more direct. When the conclusion involves a negation of existence, irrationality, or impossibility, proof by contradiction is often more effective. There is no hierarchy between the methods, choose the one that gives your assumption the most informative content.

Common Invalid Reasoning

Affirming the Consequent

p→q
q
Therefore, p          // Invalid

A service outage triggers an alert; the presence of an alert does not mean the service is down, it could simply be a probe failure.

Denying the Antecedent

p→q
¬p
Therefore, ¬q         // Invalid

Caching improves response time; if we didn’t use caching, that doesn’t mean the response was necessarily slow.

Circular Reasoning

Rephrasing a conclusion as a premise. For example, "This function has no side effects because it's a pure function" is invalid if "pure function" is itself the property being proven, no new evidence is provided.

Inferring a Universal Conclusion from a Finite Sample

Running a thousand successful tests can build confidence and cover key scenarios, but it does not logically establish that "all inputs work" unless the entire input domain has been exhaustively tested. Conversely, a single valid failure is sufficient to invalidate a universal claim.

Implicit Division by Zero or Array Bounds Violation

In algebraic derivations, before dividing both sides by x-y, you must first prove that x≠y is not zero. In program proofs, before reading a[i], you must establish boundary conditions. Unchecked operations like division by zero or out-of-bounds access render subsequent reasoning invalid.

Shrink Failures

After identifying a failing input, strive to reduce it to the smallest possible example that still triggers the issue:

• Remove irrelevant fields;
• Shorten sequences;
• Lower numerical values;
• Decrease the number of concurrent participants;
• Fix random seeds and execution order.

A minimal failing example reveals the underlying error condition and is far more suitable for inclusion in regression tests. The shrinking feature in property-based testing tools automatically performs this reduction.

Completion Checklist

1. Refute the claim that "the sum of two irrational numbers is always irrational";
2. Provide two witnesses demonstrating that "there exists an integer whose square equals itself";
3. Prove that equation 3x+6=0 has a unique real solution;
4. Use proof by contradiction to demonstrate that no largest integer exists;
5. Construct a minimal counterexample for a production failure and explain how it satisfies all the premises of the property being refuted.

References

• Open Logic Project