Search
StudyWell
  • Home
  • Maths
    • AS Maths
    • A2 Maths
    • Pure Maths
    • Statistics
    • Mechanics
  • Study Resources
    • Questions by Topic
    • Past & Practice Papers
    • AS Pure Maths Videos
  • Shop
  • My Account
  • Home
  • Maths
    • AS Maths
    • A2 Maths
    • Pure Maths
    • Statistics
    • Mechanics
  • Study Resources
    • Questions by Topic
    • Past & Practice Papers
    • AS Pure Maths Videos
  • Shop
  • My Account

Proof by Contradiction

StudyWell > Proof – mathematical logic and reasoning > Proof by Contradiction

Proof by Contradiction is a method of proof that involves making an assumption that turns out to be incorrect. We start by making an opposing assumption which is usually heavily hinted in the question. For example, to prove that root 2 is irrational, we assume that it is rational. If in the steps that follow we find a contradiction, it suggests that the original assumption is actually incorrect.

Proof by Contradiction that $\sqrt{2}$ is irrational

Proof by contradiction usually starts with an assumption that opposes the statement in the question. Going from there, we hope to meet a contradiction so as to rule out original assumption. In this question, we assume that $\sqrt{2}$ is rational. We express a rational number as $\frac{a}{b}$ where $a$ and $b$ are integers with no common factors. It follows that

$\sqrt{2}=\frac{a}{b}\hspace{10pt}\Rightarrow\hspace{10pt} 2=\frac{a^2}{b^2}\hspace{10pt}\Rightarrow\hspace{10pt}a^2=2b^2$

From this last expression we can see that 2 is a factor of $a^2$  and so it must be a factor of $a$ (the factors of $a$ will appear in factors of $a^2$ in pairs). We can write $a=2m$ and so $a^2=4m^2=2b^2$ or $b^2=2m^2$. It follows that 2 is also a factor of $b^2$ and also $b$.  So 2 is factor of both $a$ and $b$. The original assumption that $\sqrt{2}$ can be written as a rational number $a/b$ where $a$ and $b$ are integers with NO COMMON FACTORS has been violated. Our original assumption must be wrong. We may conclude that $\sqrt{2}$ is irrational.

Proving that there are infinitely many prime numbers is also a common proof that uses proof by contradiction. You will be required to know this proof (see Example 2) as well as the proof that $\sqrt{2}$ is irrational as above. Exam questions may also deviate slightly from these examples where you will have to apply this knowledge to prove other statements by contradiction.

Examples

Example 1

Prove that there is no greatest even integer.

Show Solution

We begin by making the assumption that there exists a greatest even integer and like all contradictory proofs we will end up breaking that assumption.

Let $n$ be the greatest even integer. We can add 2 to it and, since $n$ is an integer, $n+2$ is also an integer. We also have that $n+2$ is even because EVEN+EVEN=EVEN. Hence, $n+2$ is an even integer greater than $n$, and so our original assumption that $n$ is the greatest even integer must be untrue. In conclusion, there is no greatest even integer. 

Example 2

Prove that there are infinitely many prime numbers.

Show Solution

We begin by making the assumption that there exists a finite number of prime numbers and like all contradictory proofs we will end up breaking that assumption.

If there are finitely many prime numbers, i.e. there are precisely $n$ prime numbers, then we can list them:

$p_1, p_2, p_3, …, p_{n-1}, p_n$.

Consider the number

$p=p_1\times p_2\times p_3\times …\times p_{n-1}\times p_n+1$

Dividing $p$ by any of the prime numbers listed, the remainder is 1. This means that none of these prime numbers are a factor of $p$ (see polynomials). It follows that either $p$ is prime or $p$ has another prime factor that is not in the list (every number has a unique prime factorisation). Either way, there is another prime not originally stated, breaking the original assumption. Hence, by proof by contradiction, there are infinitely many prime numbers.

Videos

Coming soon…

Check out our Proof (by Deduction, Exhaustion and Disproof by Counterexample) exam-style questions in the meantime.

About

StudyWell is a website for students studying A-Level Maths (or equivalent. course). We have lots of resources including A-Level content delivered in manageable bite-size pieces, practice papers, past papers, questions by topic, worksheets, hints, tips, advice and much, much more.

Quick Links

  • CONTACT US
  • REGISTER
  • Edexcel Exam Timetable
  • Edexcel Formula Booklet
  • Edexcel Grade Boundaries
  • Edexcel Large Data Set
  • Edexcel Specification

Top Pages

  • A2 Maths (second year of A-Level Maths)
  • AS Maths (first year of A-Level Mathematics)
  • Blog
  • My account
  • Practice Papers
  • Questions by Topic
  • Shop
  • Membership Levels

Useful Websites

  • DESMOS
  • GeoGebra
  • Maths Challenges
  • STEP papers
  • UCAS
  • Wolfram Alpha
  • Friend of StudyWell: Elite Locksmiths
Footer logo
Copyright © 2022 StudyWell
MENU logo
  • Home
  • Maths
    • AS Maths
    • A2 Maths
    • Pure Maths
    • Statistics
    • Mechanics
  • Study Resources
    • Questions by Topic
    • Past & Practice Papers
    • AS Pure Maths Videos
  • Shop
  • My Account