STEP-BY-STEP LESSON · §4.7

Indirect Argument: Contradiction and Contraposition

Choose contradiction or contraposition deliberately.

How to build an argument: methods and reasons

Before writing: assumptions, goals and established facts (§4.2)

Assumption: a stated hypothesis or an explicitly temporary premise. Identify its domain.
Goal: what remains to be shown. It is not available as a reason for a later step.
Established: a statement derived from hypotheses, definitions, earlier steps or an applicable theorem. Name that reason.
Introduce witnesses when their existence is justified; give different arbitrary quantities different variables. Finish by matching the result to the original goal.

Writing a proof · §4.2

Example: constructing the witness for an odd product

Assumption
$m=2a+1,\ n=2b+1,\quad a,b\in\mathbb Z$
Take arbitrary odd integers m and n.
Reason: Their representations follow from the definition of odd.
Goal
$\exists s\in\mathbb Z:\ mn=2s+1$
This is the goal, not something already known.
Reason: An existential conclusion requires constructing a witness.
Established
$mn=(2a+1)(2b+1)=4ab+2a+2b+1$
Expand before introducing s.
Reason: Substitution and the distributive law.
Established
$s=2ab+a+b\in\mathbb Z,\quad mn=2s+1$
The constructed integer s proves the product odd.
Reason: Closure of integers and the definition of odd; the goal was not assumed.

Direct proof

When to choose: Choose it when definitions turn the hypothesis into usable equations or properties.

For every x in D: P(x) implies Q(x). Given: an arbitrary x in D satisfying P. Goal: Q for that same x.

Start: Introduce the objects and their domains; assume only the stated hypotheses. Expand the relevant definition.

Finish: State Q and explain why arbitrariness gives the universal claim. Never use Q as a premise.

Worked example with reasons

Assumption
$a,b\in\mathbb Z,\quad a>0,\ b>0,\ a\mid b$
Take arbitrary positive integers a and b with a dividing b.
Reason: These are the hypotheses, not conclusions.
Goal
$a\le b$
We must establish this inequality.
Reason: Writing a goal does not establish it.
Established
$b=aq,\quad q\in\mathbb Z$
Introduce an integer q witnessing divisibility.
Reason: Definition of a dividing b; a is nonzero.
Established
$q=\frac ba>0$
The quotient is positive.
Reason: Both b and a are positive; division by a is allowed.
Established
$q\ge1$
A positive integer cannot lie strictly between 0 and 1.
Reason: This uses q being an integer, not positivity alone.
Established
$aq\ge a,\quad b\ge a$
Replace aq by b to obtain the goal.
Reason: Multiplication by a positive a preserves the inequality; b=aq was established above.

Source concepts · approved book access required

PDF 198 · p. 174, PDF 215 · p. 191

Counterexample

When to choose: Use it to refute a universal claim. A failed proof attempt alone does not refute anything.

To refute every x in D satisfying P also satisfies Q, find one x in D with P true and Q false.

Start: Write the exact claim and choose a permitted test object. Verify its hypotheses.

Finish: Show explicitly which conclusion fails; one valid counterexample refutes the universal claim.

Worked example with reasons

Goal
$\forall n\in\mathbb Z\ (n>1\Rightarrow \operatorname{Prime}(n))$
Test the claim that every integer greater than 1 is prime.
Reason: A universal statement can be disproved by one permitted instance.
Established
$n=9,\quad9\in\mathbb Z,\quad9>1$
The chosen value satisfies the domain and hypothesis.
Reason: A counterexample must meet every hypothesis.
Established
$9=3\cdot3,\quad1<3<9$
Nine has a positive divisor other than 1 and itself, so it is not prime.
Reason: Definition of prime. Composite means nonprime only within integers greater than 1.

Source concepts · approved book access required

PDF 185 · p. 161, PDF 198 · p. 174

Proof by cases

When to choose: Choose cases when a definition or remainder changes the calculation. First show the cases cover every allowed object.

Given P, cover all possibilities C₁,…,Cₖ and prove Q in each.

Start: Derive the case split from a definition or theorem; do not merely list convenient examples.

Finish: Conclude Q because every allowed object belongs to a handled case.

Worked example with reasons

Assumption
$n\in\mathbb Z,\quad 2\nmid n$
Let n be an arbitrary odd integer.
Reason: The hypothesis fixes the domain but does not yet provide the required m.
Goal
$n^2=8m+1\quad m\in\mathbb Z$
We need to construct an integer m.
Reason: The conclusion is existential: both the equation and integrality must be shown.
Established
$n=4q+r,\quad q\in\mathbb Z,\quad r\in\{0,1,2,3\}$
Only r=1 or r=3 is possible for odd n.
Reason: Quotient–remainder theorem 4.5.1; residues 0 and 2 make n even. This proves completeness.
Established
$(4q+1)^2=16q^2+8q+1=8(2q^2+q)+1$
Case 1: set m=2q²+q.
Reason: Expand the square and factor 8. Sums and products of integers are integers.
Established
$(4q+3)^2=16q^2+24q+9=8(2q^2+3q+1)+1$
Case 2: set m=2q²+3q+1.
Reason: Expansion, 9=8+1, then factor 8; the constructed m is an integer.
Established
$\exists m\in\mathbb Z:\ n^2=8m+1$
Both possible cases give the required integer; it may depend on the case.
Reason: Exhaustive cases establish the original claim for arbitrary odd n.

Source concepts · approved book access required

PDF 230 · p. 206, PDF 231 · p. 207

Contraposition

When to choose: Use it when negating the conclusion gives a more useful starting definition.

To prove P⇒Q, prove ¬Q⇒¬P. Given ¬Q; goal ¬P.

Start: Write the contrapositive and introduce an arbitrary object satisfying ¬Q.

Finish: Establish ¬P, then invoke equivalence with the original implication.

Worked example with reasons

Goal
$2\mid n^2\Rightarrow 2\mid n$
Prove the statement for every integer n.
Reason: This is Proposition 4.7.4.
Assumption
$2\nmid n$
Instead prove: if n is odd, then n² is odd.
Reason: P⇒Q is equivalent to ¬Q⇒¬P. For integers, not even means odd. We do not assume n² even here.
Established
$n=2k+1,\quad k\in\mathbb Z$
Introduce an integer k.
Reason: Definition of odd.
Established
$n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1$
The square is odd.
Reason: Algebra and closure of integers show 2k²+2k is an integer; then use the definition of odd.
Established
$2\mid n^2\Rightarrow 2\mid n$
The original implication follows from the proved contrapositive.
Reason: Logical equivalence of a conditional and its contrapositive.

Source concepts · approved book access required

PDF 246 · p. 222, PDF 247 · p. 223, PDF 248 · p. 224

Contradiction

When to choose: Use it when the negation creates incompatible established facts.

Assume the hypotheses and the negation of the desired conclusion; derive a contradiction.

Start: State exactly what is temporarily assumed for contradiction.

Finish: Name the conflicting statements and discharge the assumption.

Worked example with reasons

Goal
$2\mid n^2\Rightarrow 2\mid n$
Prove the statement for every integer n.
Reason: This is Proposition 4.7.4.
Assumption
$2\mid n^2,\quad 2\nmid n$
Assume a counterexample: n² is even but n is not even.
Reason: Negating the universal conditional gives one integer satisfying the hypothesis and negating the conclusion. Every integer is either even or odd.
Established
$n=2k+1,\quad k\in\mathbb Z$
Introduce an integer k.
Reason: Definition of odd.
Established
$n^2=(2k+1)^2=4k^2+4k+1=2(2k^2+2k)+1$
The square is odd.
Reason: Algebra and closure of integers show 2k²+2k is an integer; then use the definition of odd.
Established
$2\mid n^2\ \land\ 2\nmid n^2$
This is impossible; the assumed counterexample cannot exist.
Reason: No integer is both even and odd (Theorem 4.7.2). Discharging the contradictory assumption proves the original claim.

Source concepts · approved book access required

PDF 246 · p. 222, PDF 247 · p. 223, PDF 248 · p. 224

Mathematical induction

When to choose: Use it for a claim indexed by every integer n from a starting value, when the next case relates to the previous one.

Prove P(n₀). For arbitrary k≥n₀, assume P(k) and derive P(k+1).

Start: State the indexed property and starting value; check the base without using the induction hypothesis.

Finish: Invoke induction only after both the base and the implication are established.

Worked example with reasons

Goal
$1+3+\cdots+(2n-1)=n^2,\quad n\ge1$
Prove the sum formula for every positive integer n.
Reason: The domain and indexed property specify what induction must cover.
Established
$n=1:\quad1=1^2$
The first case holds.
Reason: Direct evaluation establishes the base.
Assumption
$1+3+\cdots+(2k-1)=k^2,\quad k\ge1$
Fix an arbitrary integer k and assume only its case.
Reason: This temporary induction hypothesis is permitted to prove the implication P(k)⇒P(k+1).
Established
$1+3+\cdots+(2k-1)+(2k+1)=k^2+2k+1$
Separate the next term and replace the old sum by k².
Reason: This is the exact point where the induction hypothesis is used.
Established
$k^2+2k+1=(k+1)^2$
This is the required case k+1.
Reason: Algebra proves the implication. The base and induction principle now give all integers n≥1.

Source concepts · approved book access required

PDF 304 · p. 280

Negating quantified statements

When to choose: Use it to identify precisely what would make a quantified claim false, especially before a counterexample or contradiction.

Negate one outer quantifier at a time, preserving variable order, domains and the scope of the predicate.

Start: Mark the scope of each quantifier; move the negation inward one rule at a time.

Finish: Read the final statement and check that it describes failure of the original claim. Equivalence does not by itself prove either statement true.

Worked example with reasons

Goal
$\neg\forall x\in D\ \exists y\in E\ P(x,y)$
Rewrite the negation without changing its meaning.
Reason: The domains D and E remain fixed throughout.
Established
$\exists x\in D\ \neg\exists y\in E\ P(x,y)$
There is an x for which the inner existential statement fails.
Reason: Negation of a universal quantifier: ¬∀x R(x) ⇔ ∃x ¬R(x).
Established
$\exists x\in D\ \forall y\in E\ \neg P(x,y)$
For that same x, every y fails P.
Reason: Negation of an existential quantifier: ¬∃y P(x,y) ⇔ ∀y ¬P(x,y). The order ∃x∀y is preserved.

Source concepts · approved book access required

PDF 164 · p. 140

Theorem, proposition, lemma and corollary

Theorem / proposition

Both are statements established by proof. The name often signals how a text organizes or emphasizes a result, not a different degree of truth.

Lemma

A proved auxiliary result used in another argument. For example, −|r|≤r≤|r| for real r supports later bounds. If r≥0, |r|=r and −r≤r; if r<0, |r|=−r and r≤−r. These cases cover every real r.

Lemma 4.5.4, printed p. 207 / PDF 231

Corollary

A result derived from an established theorem. If r is rational, r+r is rational by closure of rational numbers under addition (Theorem 4.3.2); because 2r=r+r, its double is rational.

Example 4.3.4, printed p. 187 / PDF 211; printed box: Corollary 4.2.3

Keep the domain conditions

With Epp’s definition, d divides 0 for every nonzero integer d: 0=d·0. Do not omit d≠0.

Prime and composite classifications here concern integers n>1. “Not prime” alone does not make 0, 1 or a negative integer composite.

Before you begin

Conditional Statements

In p→q, p is the hypothesis and q the conclusion. The implication fails only when p is true and q false.

p→q≡¬p∨q

The equivalent contrapositive reverses and negates both parts: if not q, then not p. The converse q→p is not equivalent in general.

p→q≡¬q→¬p

More in lesson §2.2 Implication / if…then Biconditional / if and only if

Direct Proof and Counterexample I: Introduction

Integer n is even iff there is an integer k with n=2k. Evenness gives this representation, and the representation gives evenness.

n even ↔ ∃k∈ℤ: n=2k

For “every odd integer has an odd square”, testing 3,5,7 suggests a pattern but leaves infinitely many cases. Write an arbitrary odd integer as 2k+1 with integer k; no special value is assumed.

n=2k+1; k∈ℤ

Symbols

¬: negation
→: implication

Definitions and notation for this topic

Contrapositive

(p→q) ≡ (¬q→¬p)

The statement ¬q→¬p is equivalent to p→q and can be proved instead.

For the integer example, prove that an odd n has an odd square. The converse q→p and inverse ¬p→¬q are different statements and are not generally equivalent to p→q.

Separate glossary example

For integer n: if n² is even, then n is even.

Open glossary card

Proof by contradiction

Assumes the negation of the desired statement and derives a contradiction.

Then N+1 is an even larger integer, contradicting the assumption.

Separate glossary example

Suppose there is a greatest integer N.

Open glossary card

Assume / suppose

Take a condition as the starting point of a particular argument.

Identify its role: a hypothesis, a case assumption, or an assumption in a proof by contradiction.

Separate glossary example

Assume n is even. Then n=2k for some integer k.

Open glossary card

Step by step

Step 1 / 6

Contradiction

To prove S, temporarily assume ¬S and derive incompatible statements. The assumption ¬S is then rejected.

¬S ⇒ contradiction

The contradiction must follow from the assumptions, not merely seem surprising.

Worked example

Original trainer example. Let n be an integer. Prove that if n² is even, then n is even.

Prove the contrapositive: if n is odd, then n² is odd. Let n=2k+1 with k∈ℤ.
n²=(2k+1)²=4k²+4k+1=2(2k²+2k)+1.
2k²+2k is an integer, so n² is odd. The contrapositive, hence the original statement, is proved.

Make the contradiction explicit

To prove a claim by contradiction, assume its exact negation and derive a conflict with a stated fact. An unexpected answer alone is not a contradiction. For a conditional P→Q, the temporary assumption is P and not Q. Contraposition is a different presentation: prove not Q→not P, then use its equivalence to the original conditional.

Worked example

Prove that there is no least positive rational number.

Assume the negation: some positive rational r is the least one.
```
r ∈ ℚ, r>0; ∀s∈ℚ (s>0 → r≤s)
```
Why: This states the whole minimum property, not merely that a positive rational number exists.
Construct a new candidate s=r/2.
```
r=a/b ⇒ s=a/(2b); a,b∈ℤ, b≠0
```
Why: The numerator and denominator are integers and 2b≠0, so s is rational. Also r>0 gives s>0; the new object is in the required domain.
Compare the constructed number with r.
```
0 < r/2 < r
```
Why: Since s is positive and rational, the minimum assumption requires r≤s. But the construction gives s<r. Those two inequalities are incompatible.
Reject the assumption: there is no least positive rational number.
```
¬∃r∈ℚ (r>0 ∧ ∀s∈ℚ (s>0 → r≤s))
```
Why: The contradiction arose from assuming such a minimum. The argument works for any proposed minimum, not only for one trial value.

Self-review goal: Name the original target, its exact negation, the constructed admissible object and the two conflicting statements. When using contraposition instead, write both the original and equivalent conditional.

Optional self-check

Contrapositive of “if P, then Q”?

Show answer

If not Q, then not P.

Source / textbook · approved access required

Open source: printed p. 218 · PDF 242