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 reasoning that covers every object in its 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)	Establish existence; a constructive proof supplies a 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 "no valid request returns a 500 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; appearing close is insufficient.

A constructive example is: for every integer n, there is a larger even integer m. Choose m=2|n|+2. It is an integer multiple of 2, and m≥|n|+2>n, so the construction works for positive, zero, and negative inputs. Providing the witness still requires checking every relevant condition.

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.

A unique constraint on non-null keys permits at most one row per key value, without ensuring that a specified key exists. If nulls are allowed, check the database’s null and uniqueness rules. Adding UNIQUE does not directly express mathematical existence and uniqueness.

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. Choose the method that makes the assumptions most useful.

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; a failed probe could also cause the alert.

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 x≠y. 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 finding a failure, reduce the input while preserving its premises and the failing property:

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

Smaller counterexamples expose faulty rules and make useful regression cases. Property-test shrinking tries to simplify inputs, but irreducibility under one strategy need not mean global minimality under every size measure. Concurrency failures also depend on scheduling; fixing a random seed does not guarantee the same schedule.

This Python 3 standard-library example reduces a violation of “sorting preserves length” to two equal elements. Every input is a valid integer list:

def bad_sort(values):
    return sorted(set(values))

def violates_length(values):
    return len(bad_sort(values)) != len(values)

for values in [[8, 5, 5, 3], [5, 5], [0, 0]]:
    assert violates_length(values)
minimal = [0, 0]
assert all(not violates_length(minimal[:i] + minimal[i + 1:])
           for i in range(len(minimal)))
print(bad_sort(minimal))  # [0], although the input has two elements.

Deduplication has replaced rearrangement with retaining distinct values. Lists of length zero or one cannot trigger this length failure, so two elements are minimal for this property by length. A full sorting specification also constrains order and each value’s multiplicity; length preservation checks only one part.

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