Page 20 - DMTH403_ABSTRACT_ALGEBRA

Unit 1: Generating Sets

Theorem 6: Let S  N such that Notes
(i) 1  S, and

(ii) if m  S V m < k, then k  S.
Then S = N
We will not prove the equivalence of the well-ordering principle and Theorems 5 and 6 in this
course, since the proof is slightly technical.
Let us rewrite Theorems 5 and 6 in the forms that we will normally use.
Theorem 5: Let P(n) be a statement about a positive integer n such that

(i) P(1) is true, and
(ii) if P(k) is true for some k  N, then P(k + l) is true.
Then, P(n) is true for all n  N.
Theorem 6: Let P(n) be a statement about a positive integer n such that

(i) P(1) is me, and
(ii) if P(m) is true for all positive integers m < k, then P(k) is true.
Then P(n) is true for all n  N.
The equivalent statements given above are very useful for proving a lot of results in algebra.
As we go along, we will often use the principle of induction in whichever form is convenient.
Let us look at an example.

2
n (n 1) 2

Example: Prove that 1 + 2 + ............... + n = for every n  N.
3
3
3
4
n (n 1) 2
2

Solution: Let S = 1 + ............ + n , and let P(n) be the statement that S  .
3
3
n n 4
2
1  2 2
Since S  4 , P(I) is true.
1
(n 1) n 2
2

Now, suppose P(n – 1) is true, i.e., S n 1  4

Then, S, = 1 + ............ + (n – 1) + n 3
3
3
= S + n .
3
n–1
(n 1) n 2
2

=  n , since P(n – 1) is true.
3
4
2
2


n (n 1)  4n 

=
4
n (n 1) 2
2

=
4
Thus, P(n) is true.
LOVELY PROFESSIONAL UNIVERSITY 13