Understanding Second Principle of Mathematical Induction (Strong Induction)

127 Views Asked by At

Background: I am self learning Number Theory and the proof is not obvious to me.

Reference Book: Elementary Number Theory and Its Application - Kenneth H. Rosen

Statement:

A set of positive integers which contains the integer 1,
and which has the property that if it contains all the positive integers
1, 2, ..., k, then it also contains the integer k + 1,
must be the set of all positive integers.

Proof:

Let T be a set of integers containing 1 and
containing k + 1 if it contains 1, 2, ..., k.   --- (1)

Let S be the set of all positive integers n such that
all the positive integers less than or equal to n are in T.   --- (2)

Then 1 is in S, and by the hypotheses,
we see that if k is in S, then k + 1 is in S.   --- (3)

Hence, by the principle of mathematical induction,
S must be the set of all positive integers,
so clearly T is also the set of all positive integers.   --- (4)

My Question: How does the Statement (2) implies that integer 1 belongs to Set S?

2

There are 2 best solutions below

0
On BEST ANSWER

$1$ is in T by Statement (1), and since $1$ is the only positive integer less than or equal to $1$, T contains all of the positive integers less than or equal to $1$. Therefore, $1$ is in S by Statement (2).

0
On

Statement 2 is just a definition of a set. But the first line of your original statement says that the set of integers (which we're now calling $T$) contains $1$. Therefore, $1$ is an element of $S$.