My Math Forum Maximal element

 Applied Math Applied Math Forum

 May 5th, 2012, 07:36 PM #1 Newbie   Joined: May 2012 Posts: 3 Thanks: 0 Maximal element Stuck on this problem , how do I prove Every finite set of real numbers has a maximal element by induction
 May 6th, 2012, 02:15 AM #2 Senior Member   Joined: Apr 2010 Posts: 215 Thanks: 0 Re: Maximal element Start with a set of 1: $\{a_1\}$, obviously $a_1$ is the maximal element. If we have a set of n: $\{a_1,a_2,...a_n\}$ with a maximal element $a_i$ for some i, then obviously the set $\{a_1,a_2,...a_n,a_{n+1}\}$ has a maximal element of $\max(a_i,a_n+1)$. By induction every set of finite n has a maxmial element.
 May 6th, 2012, 08:24 AM #3 Newbie   Joined: May 2012 Posts: 3 Thanks: 0 Re: Maximal element thank sooooo much!
May 6th, 2012, 11:21 AM   #4
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 931

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Maximal element

Moved to Set Theory.

Quote:
 Originally Posted by ag05 Every finite set of real numbers has a maximal element by induction
Bonus question: find a counterexample, then reformulate the proposition so it is true. (Hint: the proof above is correct. What does it actually prove?)

 May 7th, 2012, 04:59 AM #5 Math Team   Joined: Apr 2012 Posts: 1,579 Thanks: 20 Re: Maximal element This is what I find so strange about some proofs. To me, the fact that a set of two integers, ie the the set of the maximal element from the inductively antecedent set and whatever element is being added to the next set, has to have a maximal element is indeed obvious, because it is immediately obvious that ANY finite set has a maximal element. The case of a two member set strikes me as just as special case of the more general proposition ostensibly being proven. FWIW! Probably not much!
May 7th, 2012, 05:02 AM   #6
Math Team

Joined: Apr 2012

Posts: 1,579
Thanks: 20

Re: Maximal element

Quote:
 Originally Posted by johnr This is what I find so strange about some proofs. To me, the fact that a set of two integers, ie the the set of the maximal element from the inductively antecedent set and whatever element is being added to the next set, has to have a maximal element is indeed obvious, because it is immediately obvious that ANY finite set has a maximal element. The case of a two member set strikes me as just as special case of the more general proposition ostensibly being proven. FWIW! Probably not much!
Oh, I just noticed that this was about the reals, not the integers. I don't trust my sense of what is obvious one whit when it comes to the reals!

May 7th, 2012, 05:37 AM   #7
Global Moderator

Joined: Nov 2006
From: UTC -5

Posts: 16,046
Thanks: 931

Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms
Re: Maximal element

Quote:
 Originally Posted by johnr This is what I find so strange about some proofs. To me, the fact that a set of two integers, ie the the set of the maximal element from the inductively antecedent set and whatever element is being added to the next set, has to have a maximal element is indeed obvious, because it is immediately obvious that ANY finite set has a maximal element. The case of a two member set strikes me as just as special case of the more general proposition ostensibly being proven. FWIW! Probably not much!
To some extent, 'obvious' questions are sometimes asked because the point is learning how to write a proof itself rather than how to prove the proposition in question. But there are several issues going on here that make this not entirely obvious. First, the set needs to be totally ordered -- if it's partially ordered you might have {a, b} where neither a<= b nor b <= a. Second, the set must have at least one element.

Quote:
 Originally Posted by johnr Oh, I just noticed that this was about the reals, not the integers. I don't trust my sense of what is obvious one whit when it comes to the reals!
Right... though it turns out that it does work for reals, using only the property that they are totally ordered. But you're right in not trusting too heavily on intuition here, since many people don't understand the order on the real numbers!

 May 7th, 2012, 10:47 AM #8 Math Team   Joined: Apr 2012 Posts: 1,579 Thanks: 20 Re: Maximal element Thanks for the replies, CRG. On further refelctions, noting that >/= are binary relations, I realized that it's obvious that finite set of integers (which I incorrectly thought the question concerned) simply because it's easy to do the induction in one's head, almost automatically. So indeed, writing out the proof is a matter of making explicit and conscious the sort of automatic reasoning we do in simple cases. That's cool. As for the reals and their mysteries, I avoid them as much as I can, but you always eventually butt heads with them. I just know I have to tread extra, extra carefully when I find myself in the realm of the reals!
 May 7th, 2012, 11:04 AM #9 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 931 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Re: Maximal element I don't avoid the reals but I think it's wise to tread carefully with them. Most people don't, and you can eventually get into trouble that way.

 Tags element, maximal

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post lain86 Applied Math 0 April 2nd, 2013 01:14 PM cummings123 Abstract Algebra 1 February 27th, 2013 06:06 AM mathLover Algebra 0 April 17th, 2012 02:25 AM julien Abstract Algebra 1 November 19th, 2006 06:56 PM ag05 Number Theory 3 January 1st, 1970 12:00 AM

 Contact - Home - Forums - Top