## Maximal element

Math help in Numerical Analysis, Systems of Equations: Cholesky, LU factorization, Consistence, Differential Equations (ODE), Euler's Method, Approximation of Integrals: Simpson's method, Partial Differential Equations (PDE), Symbolic Computations, Latex, Game Theory, Graph Theory; Relations, Equivalence, Implication, Boolean values, True, False, or, and, xor, Predicates, First Order Logic, Second Order Logic, Decidability, Turing machine, P problems, NP problems, Axioms, Axiom of Choice; Paradoxes: Russel, Banach-Tarski; Goedel's Incompleteness Theorem, Foundations of Mathematics on My Math Forum.
Math problems on Numerical Series Geometry Other Topics

### Maximal element

Stuck on this problem , how do I prove

Every finite set of real numbers has a maximal element by induction
ag05
Newcomer

Posts: 3
Joined: Sat May 05, 2012 10:32 pm

### 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.
brangelito
King of Diamonds

Posts: 215
Joined: Mon Apr 26, 2010 7:11 am

### Re: Maximal element

thank sooooo much!
ag05
Newcomer

Posts: 3
Joined: Sat May 05, 2012 10:32 pm

### Re: Maximal element

Moved to Set Theory.

ag05 wrote: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?)
Pari/GP: this is the program I probably mentioned in my post. Windows users can get it at http://pari.math.u-bordeaux.fr/pub/pari ... -2-6-2.exe

CRGreathouse
Global Moderator

Posts: 12540
Joined: Sat Nov 25, 2006 9:52 am
Location: UTC -5

### 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!
johnr
Super User

Posts: 1498
Joined: Sun Apr 15, 2012 7:55 am

### Re: Maximal element

johnr wrote: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!
johnr
Super User

Posts: 1498
Joined: Sun Apr 15, 2012 7:55 am

### Re: Maximal element

johnr wrote: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.

johnr wrote: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!
Pari/GP: this is the program I probably mentioned in my post. Windows users can get it at http://pari.math.u-bordeaux.fr/pub/pari ... -2-6-2.exe

CRGreathouse
Global Moderator

Posts: 12540
Joined: Sat Nov 25, 2006 9:52 am
Location: UTC -5

### 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!
johnr
Super User

Posts: 1498
Joined: Sun Apr 15, 2012 7:55 am

### 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.
Pari/GP: this is the program I probably mentioned in my post. Windows users can get it at http://pari.math.u-bordeaux.fr/pub/pari ... -2-6-2.exe

CRGreathouse
Global Moderator

Posts: 12540
Joined: Sat Nov 25, 2006 9:52 am
Location: UTC -5