Theorem For every non-empty set E of real numbers that is bounded above, there exists a unique real number sup E such that
  1. sup E is an upper bound for E
  2. if y' is any upper bound for E, then y' >= sup E
Translation There exists one and only one smallest upper bound for any non-empty set of real numbers.

Proof Let y1 be a bound for E. Pick a number x1 in E. Since y1 is an upper bound for E, x1 <= y1. Now consider the midpoint, (x1+y1)/2. If it's an upper bound for E, call it y2. If it's not an uppper bound, there exists a number in E greater than (x1+y1)/2. Let that number be x2 and let y2 = y1.

We now have x2 and y2 such that |x2-y2| <= |x1-y1|/2. Repeat the previous steps to get two sequences, {xn} and {yn} with |xn-yn| <= |x1-y1|/2n. These are equivalent Cauchy sequences and therefore converge to the same limit, y.

y is an upper bound for E since x <= y for all x in E.

y is the least upper bound of E. Suppose there is another upper bound, y'. xj <= y' since xj is in E and y' is an upper bound of E. However, y = limj->inf. xj, so y <= y'.

Translation Pick a bound for E and pick a number in E. If their midpoint is a bound, let that be your new bound. If their midpoint is not a bound, that's because we have a number in E greater than the midpoint. Let that be the new number in E. Keep doing this until you're bored out of your wits. You have constructed two sequences of numbers that converge to the same point, the least upper bound.

P.S. for krimson: The convergence of Cauchy sequences comes from the density of the rationals and the fact that a real number is constructed from an equivalence class of Cauchy sequences of rational numbers. In other words, the completeness of the reals. It does not depend on the existence of the supremum. (It should be noted, I am constructing the real numbers from equivalence classes of Cauchy sequences of rationals, not from Dedekind cuts.)