My Math Forum Simple Proof for using Induction
 User Name Remember Me? Password

 Abstract Algebra Abstract Algebra Math Forum

October 8th, 2014, 07:07 AM   #1
Newbie

Joined: May 2014
From: Singapore

Posts: 11
Thanks: 0

Simple Proof for using Induction

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

 October 8th, 2014, 07:30 AM #2 Math Team   Joined: Dec 2013 From: Colombia Posts: 7,470 Thanks: 2499 Math Focus: Mainly analysis and algebra It would be easier to comment if we knew what you were trying to prove. What are A and B? Thanks from topsquark and AspiringPhysicist
October 8th, 2014, 07:32 AM   #3
Senior Member

Joined: Jun 2013
From: London, England

Posts: 1,316
Thanks: 116

Quote:
 Originally Posted by AspiringPhysicist 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.... 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....
I assume you have the following:

$\displaystyle 1 \in A$

$\displaystyle n \in A \ \Rightarrow \ n + 1 \in A$ (*)

And, you're trying to show that $\displaystyle A = \mathbb{N}$, which is equivalent to $\displaystyle B = \emptyset$ where $\displaystyle B = A'$

Let's look at this informally first:

$\displaystyle 1 \in A \ \Rightarrow \ 2 \in A \ \Rightarrow \ 3 \in A \dots$ (by repeated application of (*))

So, intuitively, that should convince you that $\displaystyle A = \mathbb{N}$

(That's actually all there is to induction!)

Formally, however, you need the well-ordering principle. If $\displaystyle B \ne \emptyset$, then B has a least element b.

$\displaystyle b \ne 1$ as $\displaystyle 1 \in A$ as you saw

Now, $\displaystyle b -1 \notin B$ as b is the least element. So $\displaystyle b-1 \in A$

And, by (*) $\displaystyle b-1 \in A \ \Rightarrow \ b -1 + 1 \in A \ \Rightarrow \ b \in A$

And, this is a contracdiction, so $\displaystyle B = \emptyset$ and $\displaystyle A = \mathbb{N}$

 Tags induction, proof, simple

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Manueldo Applied Math 0 January 30th, 2013 07:02 AM BrainHurts Applied Math 11 April 26th, 2012 05:44 PM nicejelly Applied Math 2 December 9th, 2011 11:13 AM Airmax Applied Math 9 May 8th, 2009 12:02 PM symmetry Algebra 1 June 11th, 2007 12:13 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top