My Math Forum  

Go Back   My Math Forum > College Math Forum > Abstract Algebra

Abstract Algebra Abstract Algebra Math Forum


Thanks Tree5Thanks
  • 2 Post By v8archie
  • 3 Post By Pero
Reply
 
LinkBack Thread Tools Display Modes
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....
AspiringPhysicist is offline  
 
October 8th, 2014, 07:30 AM   #2
Math Team
 
Joined: Dec 2013
From: Colombia

Posts: 7,342
Thanks: 2465

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?
v8archie is offline  
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 View Post
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}$
Pero is offline  
Reply

  My Math Forum > College Math Forum > Abstract Algebra

Tags
induction, proof, simple



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Simple induction and structural Manueldo Applied Math 0 January 30th, 2013 07:02 AM
Proof By Induction BrainHurts Applied Math 11 April 26th, 2012 05:44 PM
Help with a simple induction nicejelly Applied Math 2 December 9th, 2011 11:13 AM
proof by induction Airmax Applied Math 9 May 8th, 2009 12:02 PM
Proof By Induction symmetry Algebra 1 June 11th, 2007 12:13 AM





Copyright © 2018 My Math Forum. All rights reserved.