International Baccalaureate · DP 2: Analysis and Approaches SL

Reasoning and Proof

⌚ ~242 min ▢ 28 blocks ✓ 99 exercises ➣ Prerequisites : Properties of Integers

Master the foundations of mathematical logic and formal proof. This module covers logical connectives, quantifiers, and De Morgan’s laws. Explore rigorous methods including direct proof, contrapositive, exhaustion, contradiction, and mathematical induction through diverse exercises.

I Proposition

Definition — Proposition and Truth Value

A proposition is a declarative statement that has a definite truth value: it is either true or false (but not both). We typically denote propositions by letters such as $p,q,r$.

Note

Unless stated otherwise, any proposition or theorem presented in a mathematical text is asserted to be true. The goal of a proof is to demonstrate this truth.

Example

$p$: "The number 9 is a prime number." (False)
$q$: "3 is a divisor of 12." (True)

Skills to practice

Determining Truth Values
Deducing Truth Values

II Negation

Definition — Negation

The negation of a proposition $p$, denoted $\neg p$, is the proposition "not $p$". The truth value of $\neg p$ is the opposite of the truth value of $p$.

Example

$p$: "The integer $4$ is an even number." (True)
$\neg p$: "The integer $4$ is not an even number." (False)

Skills to practice

Finding the Negation of a Proposition
Deducing Truth Values

III Compound Propositions

Definition — Conjunction

The conjunction of $p$ and $q$, denoted $\boldsymbol{p \wedge q}$, is the proposition "$p$ and $q$". It is true only when both $p$ and $q$ are true.

Example

Let $p$: "$n$ is a multiple of $2$" and $q$: "$n$ is a multiple of $3$".
The conjunction $p \wedge q$ is "$n$ is a multiple of $2$ and $n$ is a multiple of $3$",which means that $n$ is a multiple of both $2$ and $3$ (for example, $n = 6, 12, 18, \dots$).

Definition — Disjunction

The disjunction of $p$ and $q$, denoted $\boldsymbol{p \vee q}$, is the proposition "$p$ or $q$". It is true if at least one of $p$ or $q$ is true. This is an inclusive or.

Example

Let $p$: "$n$ is a multiple of 2" and $q$: "$n$ is a multiple of $3$".
The disjunction $p \vee q$ is true if $n$ is a multiple of 2, or a multiple of 3, or both (e.g., for $n=2, 3, 4, 6, 8, 9, \dots$).

Proposition — De Morgan's Laws

The negation of a conjunction or a disjunction follows a specific pattern known as De Morgan's Laws.

Negation of a Conjunction: $\boldsymbol{\neg(p \wedge q) \Leftrightarrow (\neg p \vee \neg q)}$
To negate an "and" statement, you negate each part and change the "and" to an "or".
Negation of a Disjunction: $\boldsymbol{\neg(p \vee q) \Leftrightarrow (\neg p \wedge \neg q)}$
To negate an "or" statement, you negate each part and change the "or" to an "and".

Example

Find the negation of the statement "$x \le 1$ or $x > 4$".

Answer

Let $p$ be "$x \le 1$" and $q$ be "$x > 4$". The statement is a disjunction, $p \vee q$. We use the second of De Morgan's Laws: $\neg(p \vee q) \Leftrightarrow (\neg p \wedge \neg q)$.First, we find the negation of each part:

The negation of $p: x \le 1$ is $\neg p: x > 1$.
The negation of $q: x > 4$ is $\neg q: x \le 4$.

Now, we combine them with an "and":$$ (\neg p \wedge \neg q) \text{ is } (x > 1) \wedge (x \le 4). $$This can be written more simply as the interval $\boldsymbol{1 < x \le 4}$.

Skills to practice

Evaluating Compound Propositions
Negating Conjunctions and Disjunctions

IV Implication and Equivalence

Implications capture deduction: from $p$ we may conclude $q$. If $p\Rightarrow q$ and $p$ is true, then $q$ must be true.

Definition — Implication

An implication, denoted $\boldsymbol{p \Rightarrow q}$, is the proposition "if $p$, then $q$". It is false only when $p$ is true and $q$ is false.

Definition — Converse, Inverse, Contrapositive

For the implication $p \Rightarrow q$:

The converse is $q \Rightarrow p$.
The contrapositive is $\neg q \Rightarrow \neg p$.
The inverse is $\neg p \Rightarrow \neg q$.

Example

"If $x=1$ then $x^2=1$" is true. The converse "If $x^2=1$ then $x=1$" is false (since $x=-1$ also satisfies $x^2=1$).

Definition — Equivalence

An equivalence, denoted $\boldsymbol{p \Leftrightarrow q}$, is the proposition "$p$ if and only if $q$". It is true only when $p$ and $q$ have the same truth value. It is the conjunction of an implication and its converse: $(p \Rightarrow q) \wedge (q \Rightarrow p)$.

Proposition — Contrapositive Equivalence

An implication and its contrapositive are logically equivalent: $\boldsymbol{(p \Rightarrow q) \Leftrightarrow (\neg q \Rightarrow \neg p)}$.

Assume that the implication “If it is raining, then the ground is wet.” is true. Because an implication and its contrapositive are logically equivalent, we can deduce that the contrapositive is also true:

Implication: “If it is raining, then the ground is wet.”
Contrapositive: “If the ground is not wet, then it is not raining.”

However, we cannot deduce that the converse “If the ground is wet, then it is raining.” is true. The ground might be wet for another reason (for example, the gardener watered it), so the converse is not logically equivalent to the original implication.

Skills to practice

Identifying Related Implications
Writing the Converse and Contrapositive
Translating Statements into Implications

V Quantifiers

Definition — Quantifiers

The universal quantifier $\forall$ means “for all”. “$\forall x\in S,\;P(x)$” asserts that $P(x)$ holds for every $x\in S$.
The existential quantifier $\exists$ means “there exists”. “$\exists x\in S,\;P(x)$” asserts that there is at least one $x\in S$ for which $P(x)$ holds.

Example

Let $S = \{1, 2, 3\}$.

$\forall x \in S, x < 4$ is a true statement, since $1<4$, $2<4$ and $3<4$.
$\exists x \in S, x \text{ is even}$ is a true statement, since $2$ is even.
$\forall x \in S, x \text{ is odd}$ is a false statement, since $2$ is not odd.

Proposition — Negation of Quantifiers

The negation of "$\forall x \in S, P(x)$" is "$\exists x \in S, \neg P(x)$".
The negation of "$\exists x \in S, P(x)$" is "$\forall x \in S, \neg P(x)$".

Example

The negation of the statement “All integers are even”$$\forall n \in \mathbb{Z},\; n \text{ is even}$$is “There exists at least one integer that is odd”$$\exists n \in \mathbb{Z},\; \neg(n \text{ is even}) \quad\text{that is,}\quad \exists n \in \mathbb{Z},\; n \text{ is odd}.$$

Skills to practice

Evaluating Quantified Statements
Negating Quantified Statements
Translating Statements into Quantified Form

VI Structure for Written Proofs

Method — Structure for Written Proofs

A clear, well-structured proof generally follows these steps:

Statement: Clearly state the proposition you intend to prove and, if relevant, the method you will use.
Assumptions: Explicitly state your initial hypotheses. For direct proofs, this means assuming the premise $p$ of the implication $p \Rightarrow q$.
Logical Steps: Present a sequence of clear, logical deductions, justifying each step with definitions, axioms, or previously proven theorems.
Conclusion: State the final conclusion, explicitly linking it back to the original proposition.

Example

Direct proof: the sum of two even integers is even.

Claim:
We prove by direct proof: if $a,b$ are even integers, then $a+b$ is even.
Assumptions:
Let $a,b$ be two even integers. By definition of even numbers, there exist $k,\ell\in\Z$ such that$$ a=2k \quad\text{and}\quad b=2\ell. $$
Logical Steps:
$$\begin{aligned}a+b &= 2k + 2\ell \\ &= 2(k+\ell).\end{aligned}$$Since $k+\ell\in\Z$, the sum $a+b$ is a multiple of $2$.
Conclusion:
By definition of even numbers, $a+b$ is even.

Method — Advice for Writing Proofs

Write down the hypotheses and the desired conclusion first; they guide your route. It can help to work backward from the conclusion on scratch paper.
Proof in progress: the left “hand” is the hypothesis, the right “hand” the conclusion—meet in the middle.
Use a draft. Explore freely on scratch paper before composing the final, clean argument.
The great mathematician Maryam Mirzakhani working intently on a draft.
Iterate. Get feedback, revise, and don’t expect a perfect proof on the first try.
Feedback loop with Dr. Tariel and a CommeUnJeu Academy student.

Skills to practice

Analyzing Proof Structures

VII Introducing a Variable

To reason about all elements of a set $E$, introduce a generic element with “Let $x\in E$.” It then stands for an arbitrary element throughout the proof.

Method — Introduce a Variable

Let $x\in E$.
$\vdots\quad\quad \quad\quad$ (reason about $x$)
Therefore, the statement holds for all $x\in E$.

Skills to practice

Structuring a Proof

VIII Direct Proof (Proof by Deduction)

Method — Direct Proof

To prove $p \Rightarrow q$, a direct proof assumes $p$ is true and uses a sequence of logical deductions to show that $q$ must also be true.$$\begin{aligned}&\text{Assume } p \text{ is true.} && (\text{Hypothesis})\\ &\quad\vdots\quad && (\text{Logical steps})\\ &\text{So, } q \text{ is true.}&& (\text{Conclusion}).\end{aligned}$$

Example

Prove that if an integer $a$ divides both integers $b$ and $c$, then $a$ divides their sum $b+c$.

Answer

Let $a, b,$ and $c$ be integers.
Suppose that $a$ divides $b$ and $a$ divides $c$.
By the definition of divisibility, there exist integers $k$ and $m$ such that$$ b = ak \quad \text{and} \quad c = am. $$Now, consider the sum $b+c$:$$\begin{aligned}b + c &= ak + am \\ &= a(k+m).\end{aligned}$$By definition, this means that $a$ divides $b+c$.

Skills to practice

Writing Direct Proofs in Arithmetic
Constructing Direct Proofs in Various Contexts
Constructing Direct Proofs: Proving a Statement is True

IX Proof by Contrapositive

Method — Proof by Contrapositive

To prove the implication $p \Rightarrow q$, we can instead prove its logically equivalent contrapositive, $\neg q \Rightarrow \neg p$.$$\begin{aligned} &\text{Assume } \neg q \text{ is true.} && (\text{Hypothesis})\\ &\quad\vdots\quad && (\text{Logical steps})\\ &\text{Therefore, } \neg p \text{ is true.}&& (\text{Conclusion}).\end{aligned}$$

Example

Prove that if $a^2$ is even, then $a$ is even.

Answer

We will prove the contrapositive: "If $a$ is odd, then $a^2$ is odd."
Assume $a$ is an odd integer.
Then there exists an integer $k$ such that $a=2k+1$.$$\begin{aligned} a^2 &= (2k+1)^2\\ &= 4k^2+4k+1\\ &= 2(2k^2+2k)+1.\end{aligned}$$So $a^2$ is of the form $2m+1$ and is therefore odd.
Since we have proved the contrapositive, the original statement is true.

Skills to practice

Constructing Proofs by Contrapositive

X Proof by Exhaustion (Cases)

A proof by exhaustion involves breaking down a statement into a finite number of distinct cases and proving that the statement holds true for every one of those cases. It is crucial to demonstrate that the chosen cases cover all possibilities.

Method — Proof by Exhaustion (Cases)

To prove a proposition $P$, identify a finite set of cases $\{C_1, C_2, \dots, C_n\}$ that are exhaustive (cover all possibilities).

Prove that $P$ is true for Case $C_1$.
Prove that $P$ is true for Case $C_2$.
...
Prove that $P$ is true for Case $C_n$.

Example

Prove that for any integer $n$, $n(n+1)$ is even.

Answer

Let $n$ be any integer.

Case 1: $n$ is even.
There exists an integer $k$ such that $n=2k$. $$ \begin{aligned} n(n+1) &= 2k(2k+1)\\ &= 2[k(2k+1)]. \end{aligned} $$ So $n(n+1)$ is even.
Case 2: $n$ is odd.
There exists an integer $k$ such that $n=2k+1$. $$ \begin{aligned} n(n+1) &= (2k+1)((2k+1)+1)\\ &= (2k+1)(2k+2)\\ &= 2\left[(2k+1)(k+1)\right]. \end{aligned} $$ So $n(n+1)$ is even.

So, $n(n+1)$ is even.

Skills to practice

Constructing Proofs by Exhaustion

XI Disproof by Counterexample

To prove that a universal statement is false, one only needs to find a single case for which it does not hold. For example, to prove the statement "All students in my class are boys" is false, I only need to find one student who is a girl. In logical notation, saying that “$\forall x\in E,\;P(x)$” is false is equivalent to saying that “$\exists x\in E,\;\neg P(x)$” is true.

Method — Disproof by Counterexample

To disprove the statement "$\forall x\in E,\;P(x)$", it is sufficient to find one element $c \in E$ for which $P(c)$ is false. This element $c$ is called a counterexample. In other words, we show that the existential statement "$\exists x\in E,\;\neg P(x)$" is true.

Example

Disprove “All odd numbers are prime numbers.”

Answer

Counterexample: $9$ is odd but not prime (since $9 = 3 \times 3$).

Skills to practice

Disproving Statements by Counterexample

XII Proof by Equivalence

To prove $p\Leftrightarrow q$, either prove both directions ($p\Rightarrow q$ and $q\Rightarrow p$) or transform $p$ step by step into $q$ using known equivalences.

Method — Proof by Equivalence

To prove $p \Leftrightarrow q$, two methods are possible:

Double Implication:
1. Prove the forward direction: Assume $p$ is true and show that $q$ must be true ($p \Rightarrow q$).
2. Prove the reverse direction: Assume $q$ is true and show that $p$ must be true ($q \Rightarrow p$).
Chain of Equivalences: Start with statement $p$ and construct a sequence of logically equivalent statements that ends with $q$. $$ p \quad \Leftrightarrow \quad s_1 \quad \Leftrightarrow \quad s_2 \quad \Leftrightarrow \quad \dots \quad \Leftrightarrow \quad q. $$

Example

For $n\in\Z$, the following statements are equivalent:$$n \text{ is even} \;\Leftrightarrow\; n^2 \text{ is even}.$$

($\Rightarrow$) Suppose $n$ is even. Then there exists $k\in\Z$ such that $n = 2k$. Hence$$n^2 = (2k)^2 = 4k^2 = 2(2k^2),$$so $n^2$ is even.
($\Leftarrow$) Suppose $n^2$ is even. By the result proved earlier (“If $a^2$ is even, then $a$ is even”), it follows that $n$ is even.

Skills to practice

Constructing Proofs of Equivalence
Constructing and Analyzing Proofs by Equivalence For Identities

XIII Proof by Contradiction

Proof by contradiction is based on the idea that if an assumption leads to a logical absurdity, the assumption must be false (e.g. $1=0$). The logical form can be summarised as: if assuming $\neg p$ leads to a contradiction, then $p$ must be true.

Method — Proof by Contradiction

To prove a proposition $p$ is true by contradiction:$$\begin{aligned} &\text{Assume } \neg p \text{ is true.} && (\text{Hypothesis})\\ &\quad\vdots\quad && (\text{Logical steps leading to a contradiction, e.g. } 1=0)\\ &\text{Contradiction! Therefore, the assumption } \neg p \text{ is false.} && \\ &\text{Thus, } p \text{ must be true.}&& (\text{Conclusion}).\end{aligned}$$

Example

Prove by contradiction that the number of prime numbers is infinite.

Answer

Suppose there are only a finite number $n$ of prime numbers, which we label $p_1, p_2, \dots, p_n$.
Every positive integer greater than 1 is either a member of this list, or is divisible by a member of this list.
Let $N = p_1 \times p_2 \times \dots \times p_n + 1$. Notice that:

$N > p_k$ for all $k=1, \dots, n$.
So, $N$ is not a member of the list.
If we divide $N$ by any $p_k$, $k=1, \dots, n$, then the remainder is $1$.
So, $N$ is not divisible by any $p_k$.

This contradicts our assumption that every integer greater than 1 is either in the list or divisible by a prime from the list. Hence our supposition is false, and there are infinitely many prime numbers.

Skills to practice

Analyzing the Structure of Proof by Contradiction
Constructing Proofs by Contradiction

XIV Proof by Mathematical Induction

Proof by induction is a powerful technique used to prove that a proposition $P(n)$ is true for all integers $n$ above a certain starting value. It is analogous to knocking over a line of dominoes: if you can knock over the first one, and you know that each domino will knock over the next, then all dominoes will eventually fall.

Method — The Principle of Mathematical Induction

To prove by induction that a proposition $P(n)$ is true for all integers $n \ge n_0$:

Base Case (Initialisation): Prove that $P(n_0)$ is true.
Inductive Step (Hérédité):
- Assume $P(k)$ is true for an arbitrary integer $k \ge n_0$ (this is the inductive hypothesis).
- Using this assumption, prove that $P(k+1)$ must also be true.

Example

Prove by mathematical induction that for all integers $n \ge 1$,$$1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}.$$

Answer

Let $P(n)$ be the proposition$$P(n): \quad 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}$$for integers $n \ge 1$.

Base case $n=1$:\$$0.2em]On the left-hand side, we have $1$. On the right-hand side,$$\frac{1(1+1)}{2} = \frac{2}{2} = 1.$$So $P(1)$ is true.\$$0.4em]
Inductive step:
Assume $P(k)$ is true for some integer $k \ge 1$, that is,$$1 + 2 + 3 + \dots + k = \frac{k(k+1)}{2}.$$We must show that $P(k+1)$ is true:$$1 + 2 + 3 + \dots + k + (k+1) = \frac{(k+1)(k+2)}{2}.$$Starting from the left-hand side of $P(k+1)$:$$\begin{aligned}1 + 2 + \dots + k + (k+1)&= \left(1 + 2 + \dots + k\right) + (k+1) \\ &= \frac{k(k+1)}{2} + (k+1) \quad &&\text{(by the inductive hypothesis)}\\ &= \frac{k(k+1)}{2} + \frac{2(k+1)}{2} \\ &= \frac{(k+1)(k+2)}{2}.\end{aligned}$$Thus $P(k+1)$ is true.

Since $P(1)$ is true and $P(k) \Rightarrow P(k+1)$ for all integers $k \ge 1$, by the principle of mathematical induction, $P(n)$ is true for all integers $n \ge 1$.

Skills to practice

Proving Inequalities by Induction
Proving Sums of Powers by Induction
Proving Sequence Properties by Induction
Proving Divisibility Properties by Induction

XV Review \& Beyond

Skills to practice

Quiz

Jump to section