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

Inductive Sets: Why a Table of Cases Is Not a Proof

IKey Formulas

Statement	In symbols	How to use it
$T \subseteq \mathbb{Z}$ is an inductive set	$(\forall k \in \mathbb{Z})(k \in T \to k + 1 \in T)$	Show that every member's successor is a member
$T$ is not an inductive set	$(\exists k \in \mathbb{Z})(k \in T \wedge k + 1 \notin T)$	Name one counterexample $k$
Negating a conditional	$\neg(P \to Q) \equiv P \wedge \neg Q$	Turns the definition into its negation
Checked, still unproved	$4 \mid (5^n - 1)$ and $1^2 + 2^2 + \cdots + n^2 = \dfrac{n(n+1)(2n+1)}{6}$	True for every $n$ tested; a table of cases is only evidence

Key Insight: Finitely many checked cases never prove a statement about every $n \in \mathbb{N}$ . Being inductive says nothing about where a set starts; it says the set never stops: from any member, the next integer is also a member.

IIFive Agreeing Cases, Then a Failure

Joining $n$ points on a circle by chords gives $1, 2, 4, 8, 16$ regions; doubling predicts $32$ for six points.

Points n 5

IIIInductive or Not? Test One Integer at a Time

A set fails to be inductive exactly when some integer $k$ in it has $k + 1$ missing from it.

Set k 5

IVFrom $1$ to $100$ , One Step at a Time

If $T \subseteq \mathbb{N}$ , $1 \in T$ and $T$ is inductive, each particular natural number is reached by finitely many steps.

Uses of the inductive property 0

💡 To cover every natural number at once, “and so on” would have to stand for infinitely many steps, which is itself a claim about every $n \in \mathbb{N}$ . The Principle of Mathematical Induction, in the next video, supplies that step.

VQuiz Questions

Problem 1 · Spot the Inductive Set

Recall: $T \subseteq \mathbb{Z}$ is an inductive set provided that for each integer $k$ , if $k \in T$ , then $k + 1 \in T$ . Which of these sets is inductive?

✅ Correct! If

k \ge -10

, then

k + 1 \ge -9 \ge -10

, so

k + 1

is in the set. Starting at

-10

instead of

1

does not matter.

❌ Not quite.

50

is in the set but

51

is not, so

k = 50

is a counterexample.

❌ Not quite.

7

is in the set but

8

is not, so

k = 7

is a counterexample. A set with no smallest element can still stop at the top.

❌ Not quite.

2

is in the set but

3

is not, so

k = 2

is a counterexample. The set never ends, yet it skips the integer right after each member.

Show solution

Check each set against the definition.

$\{1, 2, \ldots, 50\}$ : $50$ is in it and $51$ is not. Not inductive.
$\{n \in \mathbb{Z} \mid n \le 7\}$ : $7$ is in it and $8$ is not. Not inductive.
Even natural numbers: $2$ is in it and $3$ is not. Not inductive.
$\{n \in \mathbb{Z} \mid n \ge -10\}$ : let $k$ be an integer in the set, so $k \ge -10$ . Then $k + 1$ is an integer and $k + 1 \ge -9 \ge -10$ , so $k + 1$ is in the set. Inductive.

The answer is (d).

Problem 2 · Negating the Definition

Given: $T \subseteq \mathbb{Z}$ is inductive means $(\forall k \in \mathbb{Z})(k \in T \to k + 1 \in T)$ . Which statement says exactly that $T$ is not an inductive set?

✅ Correct! The negation of a universal statement is existential, and

\neg(P \to Q) \equiv P \wedge \neg Q

, so one integer in

T

whose successor is missing is enough.

❌ Not quite. Negating

\forall

gives

\exists

, not another

\forall

. The set

\{1, 2, \ldots, 20\}

is not inductive, yet this statement is false for it:

k = 1

is in the set and so is

2

❌ Not quite. This says some non-member is followed by a member, which is where a set starts, not where it stops.

\mathbb{N}

satisfies it with

k = 0

, and

\mathbb{N}

is inductive.

❌ Not quite. The negation of

P \to Q

P \wedge \neg Q

, not

P \to \neg Q

\mathbb{N}

satisfies this statement with

k = 0

, because a conditional with a false hypothesis is true, and

\mathbb{N}

is inductive.

Show solution

Negate the universally quantified conditional in two moves:

\neg(\forall k \in \mathbb{Z})(k \in T \to k + 1 \in T) \equiv (\exists k \in \mathbb{Z})\,\neg(k \in T \to k + 1 \in T)

\equiv (\exists k \in \mathbb{Z})(k \in T \wedge k + 1 \notin T).

So $T$ is not inductive provided there is an integer $k$ with $k \in T$ and $k + 1 \notin T$ . The answer is (a).

Problem 3 · Name the Counterexample

Given: $T = \{1, 2\} \cup \{n \in \mathbb{Z} \mid n \ge 5\}$ . Which integer $k$ shows that $T$ is not an inductive set?

✅ Correct!

2 \in T

but

3 \notin T

, so

k = 2

satisfies

k \in T \wedge k + 1 \notin T

❌ Not quite.

1 \in T

and

2 \in T

, so the condition holds at

k = 1

❌ Not quite.

3 \notin T

, so a counterexample cannot be

k = 3

: the conditional

3 \in T \to 4 \in T

has a false hypothesis and is true.

❌ Not quite.

4 \notin T

while

5 \in T

; that is where the second piece of

T

starts. A counterexample must be a member of

T

whose successor is missing.

Show solution

The members of $T$ are $1, 2, 5, 6, 7, \ldots$ We need an integer $k$ with $k \in T$ and $k + 1 \notin T$ .

$k = 1$ : $1 \in T$ and $2 \in T$ . The condition holds.
$k = 2$ : $2 \in T$ and $3 \notin T$ . This is a counterexample.
$k \ge 5$ : $k + 1 \ge 6 \ge 5$ , so $k + 1 \in T$ . The condition holds.

Every other integer is not in $T$ , so it cannot be a counterexample. The only counterexample is $k = 2$ , and $T$ is not inductive. The answer is (b).

Problem 4 · Forty Agreeing Cases

Given: the open sentence $P(n)$ : $n^2 - n + 41$ is prime. The first values are $41$ , $43$ , $47$ , $53$ , $61$ , all prime. What is the smallest natural number $n$ for which $P(n)$ is false?

✅ Correct!

41^2 - 41 + 41 = 41^2 = 41 \cdot 41

is not prime, while

P(1)

through

P(40)

are all true: forty agreeing cases, and the statement is still false.

❌ Not quite. At

n = 41

the last two terms cancel:

41^2 - 41 + 41 = 41^2

, which is not prime. Many true cases are evidence, not a proof.

❌ Not quite.

40^2 - 40 + 41 = 1601

, and

1601

is prime: no prime up to

40

divides it, and

40^2 = 1600 \lt 1601 \lt 41^2

❌ Close.

P(42)

is false, since

42^2 - 42 + 41 = 1763 = 41 \cdot 43

, but a smaller natural number already makes

P(n)

false.

Show solution

For $n = 1, 2, \ldots, 40$ the values $n^2 - n + 41$ run $41, 43, 47, 53, 61, \ldots, 1601$ , and every one of them is prime. A table of these forty cases would agree everywhere.

At $n = 41$ the last two terms cancel:

41^2 - 41 + 41 = 41^2 = 41 \cdot 41,

which is not prime. So $P(41)$ is false, and $n = 41$ is the smallest natural number where $P(n)$ fails. The answer is (c). The proposition "for each $n \in \mathbb{N}$ , $P(n)$ " is false even though its first forty cases are true.

Solved: 0 / 4

Inductive Sets: Why a Table of Cases Is Not a Proof

IKey Formulas

IIFive Agreeing Cases, Then a Failure

IIIInductive or Not? Test One Integer at a Time

IVFrom 111 to 100100100, One Step at a Time

VQuiz Questions

IVFrom $1$ to $100$ , One Step at a Time