We can use the Cantor-intersection theorem and the Archimedean axiom to prove the Dedekind's theorem (source:Enrico Gregorio's answer).
Suppose $A,B\subseteq\Bbb R$ are non-empty s. t. $(\forall a\in A)(\forall b\in B)\quad a\le B$ and $A\cup B=\Bbb R$. Then $\exists ! c\in\Bbb R$ s. t. $a\le c\le b, \forall a\in A,\forall b\in B$.
Let's abbreviate the above with $A\le B$ and $A\le c\le B$.
Since $A\ne\emptyset\space\land\space B\ne\emptyset$, let's choose $a_0\in A$ and $b_0\in B$.
Now, we choose $c_0=\frac{a_0+b_0}2$.
If $A\le c_0\le B$, we're done. Otherwise, it is either
$$c_0<a,\text{for some }a\in A\space\text {or}\space c_0>b\text{ for some }b\in B.$$
If $c_0<a$, then let $a_1=a, b_1=b_0$.
If $c_0>b$, then let $a_1=a_0, b_1=b$.
In either case, $a_0\le a_1\space\land\space b_0\ge b_1\implies [a_0,b_0]\supseteq[a_1,b_1]$.
Let $d=b_0-a_0$. We have $b_0-c_0=c_0-a_0=\frac{b_0-a_0}2=\frac{d}2$.
If $c_0<a$, then $\frac{d}2=b_0-c_0>b_0-a=b_1-a_1$.
If $c_0>b$, then $\frac{d}2=c_0-a_0>b-a_0=b_1-a_1$.
We can repeat the procedure to build a sequence of nested closed intervals:
$$[a_0,b_0]\supseteq[a_1,b_1]\supseteq\cdots\supseteq[a_n,b_n]$$
If at some point $A\le c_n\le B$, we're done. Otherwise, we get a sequence of closed nested intervals $[a_n,b_n]$ with $a_n\in A,b_n\in B$ and $b_n-a_n\le\frac{d}{2^n}.$
By the Cantor-intersection theorem (now assumed as an axiom), there is $c\in\bigcap_n[a_n,b_n]$.
Now we want to prove $A\le c\le B$. Let's assume the opposite: there is either
$$a\in A\text{ with } c<a\space\text{ or }\space b\in B\text{ with } c>b.$$
Suppose $a>c$.
Let's take $\varepsilon=\frac{a-c}2$.
We can take $n\in\Bbb N$ s. t. $\frac{d}{2^n}<\varepsilon$. $(*)$
Then we obtain:
$b_n<a+\varepsilon\le c+\varepsilon=c+\frac{a-c}2=\frac{a+c}2\le a$ which contradicts $A\le B$.
Analogously in case of $c>b$.
$(*)$ As $2^n>n, n\in\Bbb N$, we have $\frac1{2^n}<\frac1n\implies\frac{d}{2^n}<\frac{d}n$. In order to make $\frac{d}{2^n}<\varepsilon$, we could take $n$ s. t. $\frac{d}n<\varepsilon$, which is guaranteed to hold true by the Archimedean axiom.
Now, we want to prove the Dedekind's theorem is equivalent to the axiom of completeness (like Henno Brandsma did here):
Every non-empty subset of $\Bbb R$ that is bounded above has a supremum in $\Bbb R$.
Direction $\boxed{\Rightarrow}$
Suppose Dedekind's theorem holds.
Let $S\subset\Bbb R$ with some upper bound $u$ and let's define:
$$A=\{x\in\Bbb R\mid\exists s\in S, x<s\}\\\text{and}\\ B=\{x\in\Bbb R\mid\forall s\in S, x\ge s\}$$
$B\ne\emptyset$ because $u\in B$.
Then our $c=\sup S$.
Direction $\boxed{\Leftarrow}$
Assume the axiom of completeness holds.
Then we take $c=\sup A$.
Best Answer
First of all, it is good that you are actively stress-testing the assumptions you've been told! That's exactly what you should be doing, and that instinct will serve you well throughout mathematics.
In this case, however, the issue is that you've misinterpreted one of the assumptions. Completeness says the following:
Both the bolded points are crucial:
$\emptyset$ has lots of upper bounds, but no least upper bound since there is no least real number.
No unbounded-above set of real numbers - such as $\mathbb{N}$ (as you observe) or $\mathbb{R}$ itself (more simply) - can have a least upper bound, obviously.
And it's the second point that's relevant to your question.