Contradiction and existence proofs

To prove a claim P by contradiction, temporarily assume its negation and derive a statement incompatible with the assumptions already in force. You may derive that an integer is simultaneously even and odd, that a positive number is nonpositive, or that an explicitly nonzero quantity is zero. The contradiction must concern the same object under the same hypotheses. Two different integers can have opposite parity without difficulty, so keep witness names and dependencies visible.

Do not label a surprising result a contradiction merely because it disagrees with an unproved intuition. A divergent series or a nonintuitive geometric construction may be perfectly valid mathematics. Identify the exact earlier fact that the derived statement violates. Also distinguish contradiction from contraposition: the latter directly proves a logically equivalent implication, while contradiction assumes the entire desired claim fails. Both can use negated hypotheses, but their proof obligations are not identical.

A constructive existence proof supplies an object and verifies every required property. To prove there is an integer between ten and twelve, give eleven and check both inequalities. In a parameterized claim, the witness may be a formula or an algorithm depending on the already chosen parameters. The proof must establish that the output belongs to the stated domain. A proposed rational witness for an integer existence claim cannot be rescued by satisfying only the equation.

An indirect proof may show that denying all possible witnesses is impossible, without singling out a witness by the proof’s end. For a finite set, one may establish that a maximum exists by comparing its elements, which is constructive; completeness arguments in analysis can establish existence without a finite search. “Nonconstructive” does not mean uncertain. It means the argument’s logical guarantee should not be confused with a procedure for computing the object at a desired cost.

The irrationality of the square root of two illustrates how an assumption creates a useful representation. If the number were rational, it could be written as a quotient of integers in lowest terms with positive denominator. Squaring yields an even numerator square, hence an even numerator. Substitution then forces an even denominator as well. This contradicts lowest terms, rather than contradicting the mere existence of an even numerator or denominator.

The lowest-terms condition must be introduced before using it. Every rational number admits such a representation by dividing numerator and denominator by their greatest common divisor. Without that reduction, discovering that both are even is completely compatible with rationality: two over four is an ordinary rational representation. This example shows why a proof’s setup is substantive reasoning. The final contradiction is only as strong as the exact properties you were justified in assuming about the objects.