Contradiction, counterexamples and proof by cases

Prepare to check a claim and its conditions

You will substitute exact numbers into expressions, compare signed numbers, and use the definitions of an integer, an even integer and an odd integer. Review the preparation links if calculating (1/2)², factoring n² − n or reading a strict inequality is unfamiliar. The final irrationality example also uses reduced fractions and the positive square root.

Statements, quantifiers, implication and direct proof supply the language for this chapter. Their needed rules are restated here: a universal claim concerns every allowed input, and an implication fails only when its hypothesis is true and its conclusion is false. On a first reading, follow the counterexample, parity and case arguments. Return to the √2 example after you can explain the square-even lemma and why a fraction can be reduced to coprime integers.

One allowed failure can settle a universal claim

Consider the claim: for every real x, if x > 0 then x² ≥ x. At x = 2 the comparison works, since 4 ≥ 2. But at x = 1/2 the hypothesis is still true and x² = 1/4 < 1/2. That one exact input refutes the claim. Several successful examples cannot cancel it.

A counterexample is more than a number written beside a claim. Here 1/2 is a real number, it satisfies x > 0, and its squared value makes the stated conclusion false. Equivalently, x² − x = −1/4 at this input. The graph places that exact negative difference below zero; the arithmetic establishes the failure without estimating a picture.

The word every is decisive. A valid proof of a universal claim must reach an arbitrary allowed input or exhaust its whole stated domain. A finite test can refute an infinite-domain claim when it finds a valid failure, but a finite list of successes does not prove that claim. For a genuinely finite domain, checking every element with justified calculations can be a complete proof.

Negate the whole claim before choosing an assumption

Write the domain before negating. The negation of “every x in D has property R(x)” is “there is an x in D for which R(x) is false.” The negation of “there is an x in D with R(x)” is “every x in D fails R(x).” The domain D does not change. If D is empty, its universal claim has no counterexample and its existence claim has no witness.

For statements P and Q, P ⇒ Q means “if P, then Q.” Its negation is P ∧ ¬Q: P is true and Q is false at the same input. It is not P ⇒ ¬Q, and it is not ¬P ⇒ ¬Q. Therefore the whole real-number claim in the opening is negated by “there exists real x with x > 0 and x² < x.”

Negating a strict comparison includes equality: not(x > 0) means x ≤ 0, whereas not(x ≥ 0) means x < 0. For compound statements, not(P and Q) means not P or not Q; not(P or Q) means not P and not Q. These rules follow from which truth combinations make the entire original statement fail.

Preserve the order of nested choices. Negating “for every x in D there exists y in E with R(x,y)” gives “there exists x in D such that every y in E fails R(x,y).” One fixed x must defeat every possible y. Reversing the choices would describe a different claim.

A counterexample has three obligations

To refute ∀x ∈ D, P(x) ⇒ Q(x), exhibit one specific x in D, verify P(x), and verify that the original defined Q(x) is false. Keep every restriction: integer versus real input, positive versus nonnegative input, nonzero denominators and any additional conditions. An excluded or undefined input does not become a counterexample merely because a calculation fails.

Changing the opening’s domain to integers changes the problem. The candidate 1/2 is no longer allowed. Negative integers and zero also fail the positive hypothesis, so they do not refute “for every integer n > 0, n² ≥ n.” That integer statement is true, and a general case argument below proves the stronger claim n² ≥ n for every integer n.

When the hypothesis is false, a defined implication is true under its usual truth-table meaning, but that row has not demonstrated the promised conclusion from the hypothesis. For example x = −2 cannot refute the opening’s positive-input implication, even though it is an allowed real input. Record “hypothesis not met” separately from a counterexample.

One failed candidate does not disprove existence

A witness proves an existence claim only when it belongs to the domain and satisfies every requested condition. To show there exists a real x with x² = 4, x = 2 is enough. Trying x = 3 and obtaining 9 does not refute existence: it only rejects that candidate.

To disprove “there exists real x with x² < 0,” show that every real x has x² ≥ 0. For x ≥ 0, multiplying nonnegative x by itself is nonnegative. For x < 0, write x² = (−x)², where −x > 0, so the product is positive. These cases cover all real x, including zero. This is universal evidence for nonexistence, rather than a list of failed guesses.

A contradiction must identify an impossibility

To prove a statement S by contradiction in ordinary classical mathematics, temporarily assume its whole negation ¬S. Keep the original domain and established assumptions. Deduce two incompatible conclusions, such as R and ¬R about the same object under the same conditions. Valid reasoning then rules out ¬S, so S follows. Name the incompatibility explicitly.

To prove a conditional P ⇒ Q, a contradiction proof assumes P and ¬Q together. To prove a universal conditional, suppose there exists an allowed input at which P holds and Q fails. The hypothetical input must keep all original restrictions. You cannot replace it with a convenient example and claim that the arbitrary failure is impossible.

For integers, an even number has the form 2a with a an integer; an odd number has the form 2b + 1 with b an integer. Every integer is even or odd, by division with remainder 0 or 1 on dividing by 2. No integer is both: equality 2a = 2b + 1 would give 2(a − b) = 1. If the integer a − b is at most zero, its double is at most zero; if it is at least one, its double is at least two. Neither is one.

An unexpected answer, an awkward formula or a negative value is not automatically a contradiction. Nor may a proof create one by dividing by zero, reversing an inequality incorrectly or assuming its desired conclusion. The impossibility must follow through valid steps from the temporary negation and the retained facts.

Trace the incompatibility in a parity proof

We will prove: for every integer n, if n² is even then n is even. Suppose instead that an integer n has even n² and is not even. The even-or-odd classification then makes n odd, so n = 2k + 1 for some integer k. This is the whole negation of the conditional at one allowed input, not a change to its domain.

Squaring and factoring gives n² = (2k + 1)² = 4k² + 4k + 1 = 2(2k² + 2k) + 1. The number 2k² + 2k is an integer, so this equation makes n² odd. We now have n² even from the temporary assumption and n² odd from the calculation. The proved incompatibility of even and odd rules out that assumption, establishing the conditional for every integer n.

The same algebra proves the contrapositive directly: an odd integer has an odd square. In that version, begin only with n not even and finish with n² not even. In the contradiction version, the extra even-square assumption meets the derived odd-square result. The finite rows in the explorer help check the witnesses, including negative integers and zero; the arbitrary integer k supplies the full proof.

Cases must cover every permitted input

For a proof under assumptions H, choose case conditions C₁, …, C_r and justify that H implies at least one of them. Then prove the same required conclusion Q under H together with each case condition. The cases may overlap; what matters is that no allowed input falls outside all of them. A conclusion proved in only one branch is not yet the conclusion for the whole domain.

Order supplies the exhaustive real cases x < 0, x = 0 and x > 0. It also supplies the shorter split x < 0 or x ≥ 0. The split x < 0 or x > 0 misses zero unless the original domain excludes it. Put equality in a named branch instead of hoping it follows from nearby values.

For integer n, the split n ≤ 0 or n ≥ 1 is exhaustive because a positive integer is at least one. This split does not cover every real number: 1/2 belongs to neither branch. State why a case split covers its actual domain before using the algebra inside the branches.

The integer domain closes the apparent gap

Take an arbitrary integer n. We want n² ≥ n, equivalently n² − n = n(n − 1) ≥ 0. If n ≤ 0, both n and n − 1 are nonpositive, so their product is nonnegative. If n ≥ 1, both are nonnegative, so their product is nonnegative again. Every integer belongs to one of these cases, so the inequality holds for all integers.

The boundary values are covered and give equality: at n = 0 or n = 1, n(n − 1) = 0. Conversely, a product of real numbers is zero only if one factor is zero, so these are the only integer equality cases. Nothing in this proof allows a real input strictly between zero and one: there the first factor is positive and the second negative, explaining the opening’s counterexample.

Keep the boundary when using an absolute-value definition

For real x, define |x| = x when x ≥ 0 and |x| = −x when x < 0. These two branches cover every real number and assign zero to the first branch. They prove |x| ≥ 0: the first expression is nonnegative by its condition, and the second is positive because x < 0. At x = 0 the value is exactly zero.

Thus the stronger-looking claim “|x| > 0 for every real x” is false, with counterexample zero. The corrected strict claim “x ≠ 0 implies |x| > 0” is true: its allowed nonzero inputs split into x > 0 and x < 0. A missing boundary can invalidate a proposed proof or reveal that the proposed theorem itself needs correction.

Choose a method by its assumptions and target

For P ⇒ Q, a direct proof starts from P and derives Q. A contrapositive proof starts from ¬Q and derives ¬P. A contradiction proof starts from P and ¬Q and derives an impossibility. These three approaches establish the same conditional in classical logic, but their temporary assumptions differ. A proof of Q ⇒ P would establish the converse, a separate claim.

Case analysis can occur inside any of these methods. Use it when a definition or the domain naturally separates into possibilities. Choose contradiction when the negated claim gives a useful object or incompatible condition; choose direct reasoning when the definitions already lead to the conclusion. For the parity theorem, the contrapositive presents the key algebra with fewer assumptions.

Check what the argument actually establishes

Before accepting a counterexample, return to the exact original domain, hypothesis and conclusion. Before accepting a contradiction, point to the incompatible facts and check every operation that produced them. Before accepting cases, ask which branch contains each boundary and why the branches cover every allowed input.

Use the explorer to predict a failure, an excluded candidate or a case assignment, then reveal the exact result. Its four finite collections are illustrations. The general algebra and justified case coverage establish the infinite-domain theorems; only a valid allowed failure is needed to refute a universal claim.

Worked examples

Try it yourself

1. Negate “for every real x, if x > 0 then x² ≥ x.” Give a witness to the negation and check its three counterexample obligations.

   Show the answer and reasoning

   There exists real x with x > 0 and x² < x. The witness x = 1/2 is real, positive and has x² = 1/4 < 1/2.

   A universal negation supplies an allowed existential input; the implication negation keeps its hypothesis and negates its conclusion. The same input must satisfy both comparisons. Replacing the statement with “every positive x has x² < x” would be a different, false negation.

2. A learner proposes x = 1/2 and x = −2 as counterexamples to “for every integer x > 0, x² ≥ x.” Why does neither work, and what establishes the actual claim?

   Show the answer and reasoning

   The half is outside the integer domain; −2 fails the positive hypothesis. The general integer proof of x² ≥ x, using x ≤ 0 or x ≥ 1, establishes the claim.

   A counterexample must satisfy all original restrictions, not merely make a related expression small. At 1/2 the real comparison fails, but integer membership fails first. At −2 the required positive hypothesis is false. The arbitrary-integer two-case argument covers every permitted positive integer in its second branch.

3. Negate “there exists an integer n with n² = −1” and prove the negation. Is testing n = 0 and n = 1 enough?

   Show the answer and reasoning

   For every integer n, n² ≠ −1. The square of any real number is nonnegative, so no integer square equals −1. Two failed candidates alone are insufficient.

   The domain stays integers and existence changes to a universal failure. The nonnegative-square argument covers n ≥ 0 and n < 0, so it applies to all integers. Its comparison with the negative number −1 rules out every possible witness.

4. For an integer n, write the starting assumptions for a contradiction proof and for a contrapositive proof of “if n² is even then n is even.” Identify the contradiction in the first method.

   Show the answer and reasoning

   Contradiction assumes n² even and n odd; it derives n² odd, incompatible with the even assumption. Contrapositive assumes n odd and derives n² odd.

   Not even is equivalent to odd for integers. From n = 2k + 1, the exact formula n² = 2(2k² + 2k) + 1 gives an odd square. The contradiction method also retained the even-square assumption. The contrapositive instead ends at the negation of the original hypothesis.

5. A proposed proof of “|x| > 0 for every real x” handles x < 0 and x > 0. What is missing, and how can the statement be corrected?

   Show the answer and reasoning

   Zero is missing and is a counterexample, since |0| = 0. Correct claims are |x| ≥ 0 for every real x, or x ≠ 0 implies |x| > 0.

   The stated domain includes zero, but neither strict sign branch contains it. Checking the boundary shows the original strict universal claim is false, so adding a zero branch cannot prove it. The nonnegative conclusion includes the boundary; the nonzero hypothesis legitimately removes it from the strict claim.

6. Prove |x| ≥ x for every real x using justified cases. State when equality occurs.

   Show the answer and reasoning

   If x ≥ 0, |x| = x. If x < 0, |x| = −x > x because −2x > 0. Thus the comparison holds for all real x, with equality exactly when x ≥ 0.

   The two sign conditions cover every real number and put zero in the first case. The second compares the two expressions through their difference (−x) − x = −2x, which is positive under x < 0. A proof using only strict positive and negative branches would leave equality at zero unaddressed.

7. Prove directly that every odd integer has an odd square. Does checking the odd inputs −3, −1, 1 and 3 prove the universal statement?

   Show the answer and reasoning

   For arbitrary integer k, n = 2k + 1 gives n² = 2(2k² + 2k) + 1, an odd integer. The four checks illustrate the rule but do not prove it for all odd integers.

   The expression 2k² + 2k is an integer by closure of integer arithmetic, so it is the required witness for the odd-square definition. The arbitrary k covers negative as well as nonnegative witnesses. This direct proof also supplies the contrapositive used in the square-even theorem.

8. Let a = b = 1. A calculation writes a² = ab, then (a − b)(a + b) = b(a − b), cancels a − b and obtains 2 = 1. Does this validly prove that a cannot equal b? Locate the fault.

   Show the answer and reasoning

   No. Cancelling a − b divides by zero because a = b. Before cancellation the equation is 0 = 0, so the alleged contradiction comes from an invalid operation.

   The subtraction and factorisation are valid and yield equal zero products. Cancellation requires a nonzero factor, which is unavailable under the very assumption being tested. A contradiction proof must preserve every operation’s domain; an impossibility produced by an invalid step cannot refute its starting assumption.

What to carry forward

• A valid counterexample to a universal conditional is an allowed input with a true hypothesis and a false defined conclusion. One such input is sufficient; finite successful checks do not prove an infinite-domain claim.
• Negate the whole claim while keeping its domain. A universal claim negates to an existential failure; an implication negates to its hypothesis together with the negated conclusion.
• A contradiction proof retains the original facts, assumes the whole negation and derives an explicit incompatibility through valid steps. For P ⇒ Q, the temporary assumption is P ∧ ¬Q.
• Existence needs one valid witness. Disproving existence needs a reason that excludes every allowed candidate, not one failed trial.
• Case conditions must cover every permitted input and lead to the same target in each branch. Include boundary values, and justify a split using its actual domain.
• Direct, contrapositive and contradiction proofs start differently. Cases can support any of them; the clearest method exposes the definitions and conditions doing the work.