Mathematical-Reasoning · Unit 12 · Video 2 · Interactive Practice

The Principle of Mathematical Induction as an Axiom

IKey Formulas

Formula	Name	What it says
$(\forall k \in \mathbb{Z})(k \in T \to k + 1 \in T)$	$T$ is inductive	Membership passes from $k$ to $k + 1$ ; it puts no particular number into $T$
$T \subseteq \mathbb{N},\ 1 \in T,\ (\forall k \in \mathbb{N})(k \in T \to k + 1 \in T) \implies T = \mathbb{N}$	Principle of Mathematical Induction	Accepted as an axiom for the natural numbers, not proved
$(\forall n \in \mathbb{N})(P(n)) \iff T = \mathbb{N}$ , where $T = \{n \in \mathbb{N} \mid P(n) \text{ is true}\}$	Truth set	A "for all $n$ " statement is a claim that its truth set is all of $\mathbb{N}$
Basis: $P(1)$ . Inductive step: $(\forall k \in \mathbb{N})(P(k) \to P(k + 1))$	Proof by induction	The two conditions of the Principle, checked for the truth set

Key Insight: The inductive hypothesis assumes $P(k)$ for one arbitrary $k$ , never $P(n)$ for every $n$ ; the basis step supplies the first true case, $P(1)$ , so the argument is not circular.

IIVisualization 1 — Three Conditions Force $T = \mathbb{N}$

Only a set that contains $1$ , is inductive, and lies inside $\mathbb{N}$ is forced to equal $\mathbb{N}$ .

Start from

IIIVisualization 2 — True, False, or Can't Tell?

Each column is an inductive set; "can't tell" needs one column where the statement holds and one where it fails.

IVVisualization 3 — The Basis Step Starts the Chain

The basis step supplies the first true case; the inductive step passes truth from each $k$ to $k + 1$ .

Open sentence Hops 0

VQuiz Questions

Problem 1 · The Two Steps

Given: an open sentence $P(n)$ — which pair of results proves $(\forall n \in \mathbb{N})(P(n))$ by induction?

✅ Correct! These are the basis step and the inductive step: the two conditions of the Principle, applied to the truth set of

P(n)

❌ Not quite. Two checked cases are "and so on" — nothing about

P(1)

and

P(2)

forces

P(3)

. The inductive step must cover every

k \in \mathbb{N}

❌ Not quite. Without the basis step there is no first true case for the inductive step to pass on; the Principle needs

1 \in T

❌ Not quite.

P(k + 1) \to P(k)

is the converse: it passes truth backward, from

k + 1

k

, so from

P(1)

it reaches nothing new.

Show solution

Let $T = \{n \in \mathbb{N} \mid P(n) \text{ is true}\}$ . Then $(\forall n \in \mathbb{N})(P(n))$ is true exactly when $T = \mathbb{N}$ , which is the conclusion of the Principle of Mathematical Induction. Since $T \subseteq \mathbb{N}$ automatically, it remains to verify the Principle's two conditions:

$1 \in T$ , which means $P(1)$ is true (the basis step);
for each $k \in \mathbb{N}$ , if $k \in T$ then $k + 1 \in T$ , which means $P(k) \to P(k + 1)$ (the inductive step).

That is option (c). Option (b) drops the first condition, (a) replaces the second with a single case, and (d) replaces it with its converse.

Problem 2 · What Being Inductive Forces

Given: $T \subseteq \mathbb{Z}$ is inductive, meaning $(\forall k \in \mathbb{Z})(k \in T \to k + 1 \in T)$ , and $3 \in T$ — which statement must be true?

✅ Correct! Seven applications of the inductive property carry

3

forward to

10

❌ Not quite. That uses the converse,

k + 1 \in T \to k \in T

. Membership passes forward only: the inductive set

\{n \in \mathbb{Z} \mid n \ge 3\}

contains

3

but not

2

❌ Not quite. Nothing passes membership backward from

3

1

: the inductive set

\{n \in \mathbb{Z} \mid n \ge 3\}

contains

3

but not

1

❌ Not quite.

\{n \in \mathbb{Z} \mid n \ge 3\}

is inductive and contains

3

, yet it is not

\mathbb{Z}

; for example,

0

is not in it.

Show solution

From $3 \in T$ , apply the inductive property with $k = 3, 4, \ldots, 9$ :

3 \in T \to 4 \in T \to 5 \in T \to 6 \in T \to 7 \in T \to 8 \in T \to 9 \in T \to 10 \in T.

So $10 \in T$ must hold. The other options can all fail for the same inductive set $T = \{n \in \mathbb{Z} \mid n \ge 3\}$ : it contains $3$ , but $2 \notin T$ , $1 \notin T$ and $T \ne \mathbb{Z}$ .

Problem 3 · A Truth Set That Breaks

Given: $P(n)$ : " $n^2 - n + 41$ is prime", with truth set $T = \{n \in \mathbb{N} \mid P(n) \text{ is true}\}$ . For $n = 1, 2, \ldots, 40$ the number $n^2 - n + 41$ is prime, and $41^2 - 41 + 41 = 1681 = 41^2$ — which statement is correct?

✅ Correct! The basis step holds, but the inductive step fails at

k = 40

, so the Principle does not apply, and indeed

T \ne \mathbb{N}

❌ Not quite. Forty checked cases are still "and so on": the case

n = 41

gives

1681 = 41^2

, which is not prime, so

41 \notin T

❌ Not quite.

1^2 - 1 + 41 = 41

, which is prime, so

1 \in T

; the basis step holds.

❌ Not quite. Both parts are wrong:

1^2 - 1 + 41 = 41

is prime, so

1 \in T

, and

40 \in T

while

41 \notin T

, so

T

is not inductive.

Show solution

Basis: $1^2 - 1 + 41 = 41$ is prime, so $1 \in T$ .

Inductive property: it fails at $k = 40$ . Since $40^2 - 40 + 41 = 1601$ is prime, $40 \in T$ ; but

41^2 - 41 + 41 = 41^2 = 1681,

which is not prime, so $41 \notin T$ . Thus there is a $k$ with $k \in T$ and $k + 1 \notin T$ , which is exactly the negation of " $T$ is inductive". Since $41 \in \mathbb{N}$ and $41 \notin T$ , also $T \ne \mathbb{N}$ : checking many cases never replaces the inductive step.

Problem 4 · Another Counterexample to Statement 2

Given: Statement 2: "For each subset $T$ of $\mathbb{Z}$ , if $1 \in T$ and $T$ is inductive, then $T = \mathbb{Z}$ ." — which set is a counterexample?

✅ Correct! It contains

1

and is inductive, yet

-11

is not in it, so it is not

\mathbb{Z}

: the hypothesis holds and the conclusion fails.

❌ Not quite.

\mathbb{Z}

satisfies the hypothesis, but it also satisfies the conclusion

T = \mathbb{Z}

, so it is not a counterexample.

❌ Not quite. This set is inductive, but

1

is not in it, so the hypothesis fails and the conditional is true for it.

❌ Not quite. This set contains

1

but not

2

, so it is not inductive; the hypothesis fails.

Show solution

A counterexample is a subset $T$ of $\mathbb{Z}$ with $1 \in T$ and $T$ inductive, but $T \ne \mathbb{Z}$ .

Take $T = \{n \in \mathbb{Z} \mid n \ge -10\}$ . Since $1 \ge -10$ , $1 \in T$ . If $k \in T$ , then $k \ge -10$ , so $k + 1 > k \ge -10$ and $k + 1 \in T$ ; hence $T$ is inductive. But $-11 \notin T$ , so $T \ne \mathbb{Z}$ .

This is the video's set $S = \{n \in \mathbb{Z} \mid n \ge -3\}$ with a different starting point: the inductive property passes membership from $k$ to $k + 1$ , never from $k$ to $k - 1$ , which is why the Principle is stated only for subsets of $\mathbb{N}$ .

Solved: 0 / 4

The Principle of Mathematical Induction as an Axiom

IKey Formulas

IIVisualization 1 — Three Conditions Force T=NT = \mathbb{N}T=N

IIIVisualization 2 — True, False, or Can't Tell?

IVVisualization 3 — The Basis Step Starts the Chain

VQuiz Questions

IIVisualization 1 — Three Conditions Force $T = \mathbb{N}$