Simple Proof for using Induction

[PcumP_Ravenclaw]

Dear All,
I am trying to understand this proof for using induction. Please help me!

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...

 

[mathman]

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

 

[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.

 

[HallsofIvy]

Dear All,
I am trying to understand this proof for using induction. Please help me!

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.

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

As before, b ≥ 2

"As before"?? Was there something you didn't tell us? You hadn't said, before that 1 was in A.

, so that now {1, . . . , b − 1} ⊂ A. With the new hypothesis,
this implies that b ∈ A which is again a contradiction.

Because, if n is in A then so is n+1.

Thus (as before) B = ∅,and A = N.
Questions??

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

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

b - 1 is 1 rhight??

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

therefore it should be in A??

Then...

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

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

so how does b become an element of A??

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

Danke...

 

[mathman]

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.

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.