Numerical Systems

Introduction Positional Notation Converting Between Bases Binary Addition Binary Multiplication Challenges (Python) Challenges (Java)

Modular Arithmatic

Introduction The Modulus Operator Cyphers Modular Arithmetic Modular Inverse Challenges (Java)

Algorithms

Introduction Algorithms Time Functions Asymptotic Complexity Summation Challenges

Propositional Logic

Introduction Propositional Logic Conjunction and Disjunction Implication and Equivalence Bitwise Operators Challenges

Set Theory

Introduction Sets Subsets and Supersets Set Operations Challenges

Graph Theory

Introduction Graphs Directed Graphs Structure of Language Search Trees Neural networks Game Object Trees Challenges Graph Question Generator

Proof

Introduction Proof Proof by Cases Proof by Contradiction Proof by Induction Challenges

Maths to Code

Maths to Code Challenges Question Generator

Descriptive Statistics

Introduction Statistics Measures of Central Tendency Measures of Spread Data Visualisation Correlation Challenges

Probability

Introduction Probability Basics Combinatorics Probability Trees Law of Total Probability Bayes Rule Challenges

Inferential Statistics

Introduction Probability Distributions Samples and Populations Hypothesis Testing Z Scores Student's T-Test Challenges

Proof by Contradiction

In a proof by contradiction, we assume the negation of the statement we are trying to prove. Then we try and demonstrate a contradiction, showing that our original statement must have been true after all.

Watch the video and then answer the questions below.

Five-minute video

You can also view this video on YouTube

You can find the slides here and also as .odp.

Key Points

Proof by contradiction has the following form: We want to prove a proposition P. We assume ¬P, and from this attempt to find a contradiction Q ∧ ¬Q (or any other situation that is logically impossible). This shows that ¬P must be false, and therefore P must be true.

Example Proof

Theorem: The square root of 2 is an irrational number.

Proof: Assume that sqrt(2) is rational. Therefore sqrt(2) = a/b (where a, b is in lowest terms, i.e. can’t be reduced any further, no common terms)

2 = a² / b²

2b² = a² Therefore, because a² is equal to two times something, a² must be even. Therefore a is even (if you’re not convinced, feel free to prove this step yourself). If a is even, the there is some k such that a = 2k.

Therefore, 2b² = (2k)²`

2b² = 4k²

b² = 2k² Therefore b² is even. Therefore, just like as showed with a above, b must be even.

If a and b are even, then a/b is not a fraction in lowest terms, as both top and bottom could be divided by 2. This contradicts our assumption that a/b is in lowest terms.

By assuming sqrt(2) is rational we conclude by contradiction that sqrt(2) is not rational, therefore sqrt(2) is irrational. ■

Questions

On paper

Prove some stuff

Using a proof by contradiction, show that if a >= 2 and b are integers, either a does not divide b or a does not divide b + 1. (Remember from the questions in part 1 that if n divides a then a = ni)
Using a proof by contradiction, show that there exists no positive integer n such that 2n < n² < 3n

Summary

In this section we have learned about proof by contradiction.

You should know how proof by contradiction works, and be able to use it for simple proofs.

In the next section, we will look at another kind of proof, proof by induction.

Improve this page

Getting Started

Introducing Mathematics