Simple Proof for using Induction

1. Oct 8, 2014

PcumP_Ravenclaw

Dear All,

As per the book "Alan F beardon, Abstract algebra and geometry" The following....

Quote:
Proof: Let B be the set of positive integers that are not in A. Suppose that
B = ∅; then, by the Well-Ordering Principle, B has a smallest element, say b.
As before, b ≥ 2, so that now {1, . . . , b − 1} ⊂ A. With the new hypothesis,
this implies that b ∈ A which is again a contradiction. Thus (as before) B = ∅,and A = N.
Questions??

b is >= 2 because 1 is in A right?

b - 1 is 1 right?? therefore it should be in A??

Then....

b - 1 is an element of A so b is an element of A + 1??

so how does b become an element of A??

Danke....

2. Oct 8, 2014

mathman

It would help if you would include the statement of the theorem.

3. Oct 9, 2014

PcumP_Ravenclaw

Proof by Induction

The Principle of Induction II : Suppose that A ⊂ N, 1 ∈ A, and for every m,
{1, . . . ,m} ⊂ A implies that m + 1 ∈ A. Then A = N.

4. Oct 9, 2014

HallsofIvy

Staff Emeritus
You mean "suppose that B is NOT empty" don't you?

"As before"?? Was there something you didn't tell us? You hadn't said, before that 1 was in A.
Because, if n is in A then so is n+1.

Yes. "Induction" says that "if 1 is in A and, whenever, n is in A so is n+ 1, then A= N".

Not necessarily! But b- 1 is less than b and b is, by hypothesis, the smallest member of B.

I don't know what you mean by "A+ 1". A is a set and 1 is a number.

Because of the "induction hypothesis": "if n is in A then so is n+ 1".

5. Oct 9, 2014

mathman

Let k be the smallest integer not in A, (k must be >1). (1,. . .,k-1) are in A, therefore k is in A, contradiction.