
Abstract Algebra Abstract Algebra Math Forum 
 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:
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?

October 8th, 2014, 07:32 AM  #3  
Senior Member Joined: Jun 2013 From: London, England Posts: 1,316 Thanks: 116  Quote:
$\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 wellordering 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 b1 \in A$ And, by (*) $\displaystyle b1 \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  

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 