International Baccalaureate · DP 2: Analysis and Approaches HL

Reasoning and Proof

⌚ ~186 min ▢ 21 blocks ✓ 76 exercises

I Logical Connectives

I.1 Propositions

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.

Report an error

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

I.2 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

I.3 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.

Report an error

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.

Report an error

Definition — Necessary and Sufficient Conditions

Assume the implication $p \Rightarrow q$ is true.

$p$ is a sufficient condition for $q$: for $q$ to be true, it suffices that $p$ is true.
$q$ is a necessary condition for $p$: for $p$ to be true, $q$ must necessarily be true.

When $p \Leftrightarrow q$, we say that $p$ is a necessary and sufficient condition for $q$ ($p$ if and only if $q$).

When $p$ and $q$ describe properties of an object, the true implication $p \Rightarrow q$ means the set $P$ of objects satisfying $p$ is included in the set $Q$ of objects satisfying $q$: being in $P$ is enough to be in $Q$ (sufficient), and being in $Q$ is required to be in $P$ (necessary).

Report an error

Example

Let $p$: "$n$ is a multiple of $4$" and $q$: "$n$ is even". The implication $p \Rightarrow q$ is true, so:

being a multiple of $4$ is a sufficient condition for being even — but it is not necessary ($n=6$ is even without being a multiple of $4$);
being even is a necessary condition for being a multiple of $4$ — but it is not sufficient (again $n=6$).

So $p \Rightarrow q$ holds but $q \Rightarrow p$ fails: the condition is not necessary and sufficient.

Skills to practice

Identifying Related Implications
Writing Implications, Converses and Contrapositives
Identifying Necessary and Sufficient Conditions
Proving Necessary and Sufficient Conditions

I.4 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 and Negating Quantified Statements
Translating Statements into Quantified Form

II Writing a Proof

II.1 Structure of a Written Proof

Recappreviously studied — click to reread

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.

Equality and Identity: the Sign $\equiv$

An equation such as $2x + 1 = 7$ asks for which values of $x$ the equality is true (here only for $x = 3$); an identity is an equality true for every value of its variables for which both sides are defined. To mark an identity, one may write the sign $\equiv$, read “is identically equal to”: $$(x - 4)^2 + 3 \equiv x^2 - 8x + 19$$ means that $(x - 4)^2 + 3 = x^2 - 8x + 19$ for every real number $x$.
A proof that an equality holds (“show that…”) is laid out from one side to the other: start from one side, usually the more complicated one, transform it through a chain of equalities, each justified by a rule already established, and stop when the other side appears.
Do not start from the equality to be proved and transform both sides at once: unless every step is an equivalence, this only shows that the equality implies a true statement, which proves nothing. For instance, squaring both sides of the false equality $-1 = 1$ gives the true equality $1 = 1$.

Report an error

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

Structure of a Written Proof

II.2 Introducing a Variable

Recappreviously studied — click to reread

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.

Report an error

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

Introducing a Variable

II.3 Direct Proof

Recappreviously studied — click to reread

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

Direct Proof

III Methods of Proof

III.1 Proofs from Definitions

Definition — Even and Odd Integers

Let $n$ be an integer.

$n$ is even if there exists an integer $k$ such that $n = 2k$.
$n$ is odd if there exists an integer $k$ such that $n = 2k + 1$.

Every integer is either even or odd, and never both.

Proposition — The Square of an Odd Integer

If $n$ is an odd integer, then $n^2$ is odd.

Proof

Let $n$ be an odd integer: there is an integer $k$ such that $n = 2k + 1$. Then $$\begin{aligned}[t] n^2 &= (2k+1)^2 \\ &= 4k^2 + 4k + 1 && \text{(expanding the square)}\\ &= 2\,(2k^2 + 2k) + 1. && \text{(factoring out $2$)} \end{aligned}$$ The number $K = 2k^2 + 2k$ is an integer, and $n^2 = 2K + 1$: by definition, $n^2$ is odd.

Skills to practice

Proving Properties of Even and Odd Integers

III.2 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

III.3 Proof by Exhaustion

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.

Report an error

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. Every integer is either even or odd, so the two cases below cover all possibilities.

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

III.4 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.

Report an error

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$).

A Counterexample Must Be Checked

Naming a value is not enough: a counterexample is a proof, so it must be checked. To disprove “$\forall x\in E,\;P(x)$” with an element $c$:

check that $c$ belongs to $E$;
show, by a computation or an argument, that $P(c)$ is false.

For example, the statement “for every natural number $n$, the number $n^2 + 41n + 41$ is prime” is false. Take $n = 41$, which is a natural number: $$\begin{aligned}[t] 41^2 + 41 \times 41 + 41 &= 41 \times (41 + 41 + 1) && \text{(factoring out $41$)}\\ &= 41 \times 83. \end{aligned}$$ This number has the divisor $41$, with $1 < 41 < 41 \times 83$, so it is not prime.

Report an error

Skills to practice

Disproving Statements by Counterexample

III.5 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.

Report an error

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

III.6 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.

Report an error

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$.
Since every integer greater than $1$ has at least one prime divisor, 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 a Proof by Contradiction
Constructing Proofs by Contradiction

III.7 The Irrationality of $\sqrt{2}$

Recappreviously studied — click to reread

Proposition — Irrationality of $\sqrt{2}$

$\sqrt{2}$ is an irrational number.

Proof

Assume $\sqrt{2}$ is rational. Then $\sqrt{2} = \frac{p}{q}$ where $\frac{p}{q}$ is a fraction in lowest terms.
Squaring both sides: $2 = \frac{p^2}{q^2} \implies p^2 = 2q^2$.
This implies $p^2$ is even, so $p$ must be even — indeed, if $p$ were odd, its square would be odd. Let $p = 2k$.
Substitute back: $(2k)^2 = 2q^2 \implies 4k^2 = 2q^2 \implies 2k^2 = q^2$.
This implies $q^2$ is even, so $q$ must be even. If both $p$ and $q$ are even, they have a common factor of 2, contradicting that the fraction is in lowest terms.
Thus, $\sqrt{2}$ cannot be rational.

Skills to practice

The Irrationality of $\sqrt{2}$

IV Going further

Skills to practice

Solving Problems with Several Methods of Proof
Quiz