ASSIGN
Proof
Deductive proof and contradiction
Deductive proof and contradiction Practice
Deductive proof and contradiction Test
Mathematical induction
Mathematical induction Practice
Mathematical induction Test
CatalogueDPMathematicsMathematics: Analysis and Approaches HLNumber and algebra

Deductive proof and contradiction

Use definitions to make a general argument, or show that the opposite claim cannot hold.

  • AA HL
  • Papers 1 and 2
  • No GDC needed
  • About 20–30 min

By the end of this lesson

  • distinguish proof from evidence and counterexample
  • write a direct proof using arbitrary integers
  • build a contradiction with a precise assumption

Understand the idea

Testing several even integers may suggest that their squares are even. A proof must explain every allowed case at once. Writing an arbitrary even integer as $2k$, with k an integer, makes that possible without listing any cases.

Sometimes the direct route is awkward. Assume the opposite of the claim, keep the assumptions precise, and derive an impossibility. The contradiction tells us that the opposite assumption cannot hold.

Checkpoint

A statement holds for n = 1 through 50. What has been established?
Show explanation

A later permitted case may still fail.

Put the idea into notation

A universal claim has the form “for every x in a stated domain, P(x)”. A single valid counterexample disproves it; a list of successful examples does not prove it.

For integers k, even numbers have form $2k$ and odd numbers have form $2k+1$. For a nonzero integer d, divisibility by d means the number equals $dm$ for an integer m.

In contradiction, assume the negation of the desired conclusion. For “there is no smallest positive rational”, its negation is “there is a smallest positive rational”. Do not assume the conclusion you are trying to establish.

Example 1

Prove a statement for arbitrary inputs

Prove that the sum of two odd integers is even.

  1. Let the integers be $2m+1$ and $2n+1$, where m,n are integers.
  2. The sum is $2(m+n+1)$.
  3. Since $m+n+1$ is an integer, the sum is even.
Why use two different integer parameters?

Using different integer parameters allows the two numbers to be different. The final integer condition connects the algebra back to the definition.

Example 2

Refute rather than keep testing

Is $n^2+n+11$ prime for every nonnegative integer n?

  1. Try $n=11$: $121+11+11=143$.
  2. $143=11\times13$, so it is composite.
  3. The universal claim is false.
Why choose n = 11?

Choose n = 11 because every term in n² + n + 11 then has a factor 11. The resulting second factor is 13, so the value is composite. A counterexample need not be the first input where the claim fails.

Example 3

Create an impossible smaller value

Prove that there is no smallest positive rational number.

  1. Assume a smallest positive rational q exists.
  2. Then q/2 is rational and $0\lt q/2\lt q$.
  3. This contradicts the assumed minimality of q, so no such smallest number exists.
Why must the smaller value stay in the set?

The proposed smaller value must remain in the same set. This argument does not work for positive integers because half an integer need not be an integer.

In the exam

Quick check

Your score is not saved.

  1. Which expression represents any odd integer?
    Show explanation

    The integer condition makes the parity claim valid.

  2. Why is $3(2k+1)$ divisible by 3 when k is an integer?
    Show explanation

    Divisibility is exactly an integer-multiple statement.

  3. A claim is “n² is even for every integer n”. Which observation refutes it?
    Show explanation

    A counterexample needs an allowed input and a false conclusion.

  4. Assume there is a largest integer N. Which two facts must a contradiction establish?
    Show explanation

    The proposed counterexample must stay in the set and exceed the assumed largest member.

  5. Could the same “add 1” argument prove that the interval [0,1] has no largest real number?
    Show explanation

    The interval has largest member 1. The contradiction fails because 2 is outside the set.

Lesson Rewards
1
Experience points earned for the lesson 5

Rate this lesson

Feedback submitted. Thank you for helping us improve!

Comments

Get another hint

Having trouble? Use a hint

Correct! View the step-by-step solution

Correct! Incorrect
ASSIGN