Re: A help with a formal proof for an "obvious" fact, please

In article <eoqlc5$29ph$1@xxxxxxxxxxxxxxxxxx>,
magidin@xxxxxxxxxxxxxxxxx (Arturo Magidin) wrote:

In article <1169212375.060946.227040@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
<nicegirl_130@xxxxxxxxx> wrote:
I'm 15, study some math on my own. I was asked to give a formal proof
to something that sounds kinda obvious, but to me a formal proof is not
easy at all:

Let A be a finite sub set of the reals. Then, sup A is in A (sup =
supremum).

It was suggested we should use induction, but I couldn't get there, so
I tried another reasoning. First, we see that if sup A is not in A,
then s = sup A is a limit point of A (assuming A is bounded above). My
proof: Since s is not in A, we have a < s for every a of A. For every
eps >0, s- eps < s. By the definition of supremum, it follows s - eps
is not an upper bound of A. Therefore, there exists a in A such that s
- eps < a < s. So, we see that, for every eps >0, the open ball
centered at s intersects A and contains an element of A different from
s. By the definition, it follows s is a limit (or accumulation) point
of A.

Now, back to the original problem. We know finite sets cannot have
limit points.

Well, that depends on your precise definition of "limit points". I
suspect most will agree with you, though.

So, since A is finite, it doesn't have limit points.
Since it's finite, it's bounded and, according to the least upper bound
principle, it has a supremum s. And since s is not a limit point of A,
s is in A.

But there's a flaw here, I'm implicitly assuming the "obvious" fact
that finite sets are bounded. It's clear that, if A is finite, we can't
find a bijection from A onto {1,2....n.....}, but I'm a bit confused
here.

You could prove that... by induction. In fact, the argument turns out
to be pretty much the same you need in order to prove your original
statement by induction, so here goes.

PROPOSITION. If A is a nonempty finite subset of the real numbers,
then: (i) A is bounded; and (ii) A contains its own supremum.

Proof. We do induction on the number of elements of A; call it n. In
this case, it turns out that we need to do the first two cases by
hand.

Case 1: n=1. That is, A = {x}, for some real number x. Then x itself
is an bound for A, and x is the supremum of A, so the result holds.

Case 2: n=2. That is, A = {x,y} and x is different from y. We either
have x<y or y<x. If x<y, then x is a lower bound, y is an upper bound,
and y is the supremum; if x>y, then x is an upper bound, y is a lower
bound, and x is the supremum. The results holds.

Induction:

Induction hypothesis. Assume the result we want to prove is true
whenever the set A has k elements, k>2.

We want to prove that the result also holds if A has k+1
elements. Write A = {x1,...,xk,y}.

This induction does not prove the case |A| = 3.
Replace `k>2' with `k>1'

By induction, we know that B = {x1,...,xk} is bounded and contains its
own supremum. So there is a number z which is smaller than or equal to
all xi, and one of the x's is the supremum of B; by reordering them if
necessary, we may assume that x1 is the largest element of B, its
supremum.

To show that A is bounded below, consider {z,y}. By the case n=2 we
know it is bounded below by some number, t; this t is smaller than or
equal to z, which is smaller than all xi, and also by construction
smaller than or equal to y. So t <= a for every a in A, hence t is a
lower bound for A. To show A contains its own supremum, consider
{x1,y}. By the case n=2 proven above, this set contains its own
supremum; if it is x1, then y<=x1, and since x1 is the supremum of B,
we know that x2,...,xn <= x1; hence a<=x1 for all a in A, and x1 is in
A, so A contains its own supremum. If the supremum of {x1,y} is y,
then y is the supremum of A by a similar argument. In either case, A
is bounded and contains its own supremum.

This finishes the induction. QED

--
Michael Press
.

Relevant Pages

  • Re: A help with a formal proof for an "obvious" fact, please
    ... sup A is in A (sup = ... It was suggested we should use induction, but I couldn't get there, so ... Since it's finite, it's bounded and, according to the least upper bound ... it has a supremum s. ...
    (sci.math)
  • Re: A help with a formal proof for an "obvious" fact, please
    ... sup A is in A (sup = ... It was suggested we should use induction, but I couldn't get there, so ... Since it's finite, it's bounded and, according to the least upper bound ... it has a supremum s. ...
    (sci.math)
  • Re: Dedekind Cuts, Fundamental Sequences: why?
    ... That is not a definition of least upper bound. ... It's a definition of completeness. ... bound" the very first hit was the wikipedia entry for "supremum", ... I just looked in textbooks which I know to be in common use at ...
    (sci.math)
  • Re: A help with a formal proof for an "obvious" fact, please
    ... sup A is in A (sup = ... It was suggested we should use induction, but I couldn't get there, so ... Since it's finite, it's bounded and, according to the least upper bound ... it has a supremum s. ...
    (sci.math)
  • Re: sup unique
    ... A better term for supremum is least upper bound, ... By definition, a is a lub, least upper bound, sup, ... What in vogue definition of lub is used in your class? ...
    (sci.math)