The proof of existence of supremums that I saw relied on the completeness of the real numbers, and not much else. Basically, we constructed a Cauchy (and thus convergent) sequence of real numbers that was always an upper bound of the set, and got infinitely close to the set.
Here's an outline:
Theorem. Let $U \subset \mathbb{R}$ be a bounded set of real numbers. Then there exists $s \in \mathbb{R}$ such that for all $u \in U$, $s \geq u$, and for any $\varepsilon > 0$, $s - \varepsilon$ is not an upper bound of $U$.
Let $M > 0$ be the upper bound for $U$ (for example, if $U = (0,1)$, we could say $M = 1000000000$, and it would be fine).
Take $T_1 := M$, and $B_1$ to be some number that is not an upper bound for $U$.
Now, we given $T_i$ and $B_i$, we will define $T_{i+1}$ and $B_{i+1}$ as follows:
We take the midpoint of $T_i$ and $B_i$ to be called $m_i$, and see if $m_i$ is an upper bound for $U$. If it is, then we'll take $T_{i+1} := m_i$ and $B_{i+1} := B_i$. We define $a_i$ to be $m_i$
If $m_i$ is not an upper bound for $U$, then we define $a_i := a_{i-1}$, and $T_{i+1} := T_i$, and $B_{i+1} := B_i$.
The distance between $T_i$ and $B_i$ halves for each iteration, so since $a_i$ is contained in the interval, it is squeezed into convergence. Its limit $a$ must be an upper bound, and the claim (I will leave for you to play with) is that $a$ is the least upper bound of the set $U$. $\Box$