Least Upper Bound of 2 Sets 
Let $A+B = \{a+b | a \in A, b \in B\}$ and denote the least upper
  bound of a set $X$ as $lub(X)$.
Show that $lub(A+B) = lub(A) + lub(B)$.

I'm finding this problem a little confusing. I've been provided with a proof below, but it's still not really clear to me. Can anyone elucidate this for me?

Proof: since $a \leq lub(A), b \leq lub(B)$, we have $a +b \leq lub(A) + b$ and $b +lub(A) \leq lub(B) + lub(A)$, so $a+b \leq lub(B)
 + lub(A)$, so $lub(A)+lub(B)$ is an upper bound for $A+B$. Now suppose $x < lub(A)+lub(B)$. Then $\epsilon = lub(A) + lub(B) -x > 0$. Then
   $\frac{\epsilon}{2} > 0$. Since $lub(A) - \frac{\epsilon}{2} <
 lub(A)$, there exists $a_0 \in A$ s.t. $lub(A) - \frac{\epsilon}{2} <
 a_0$. Similarly, since $lub(B) - \frac{\epsilon}{2} < lub(B)$, there
   exists $b_0 \in B$ s.t. $lub(B) - \frac{\epsilon}{2} < b_0$.
Then $x = lub(A)+lub(B)-\epsilon = lub(A) - \frac{\epsilon}{2} +
 lub(B) - \frac{\epsilon}{2} < a_0 + b_0$. So $x$ is not an upper bound
   for $A + B$. Therefore, $lub(A) + lub(B)$ is the least upper bound.

I'm confused specifically by the last step: how does our statement imply that $x$ is not an upper bound for $A+B$?
 A: 
I'm confused specifically by the last step: how does our statement imply that $x$ is not an upper bound for $A+B$?

Look at that last line concerning $x$:
$$x = \ldots < a_{0}+b_{0}.$$
But $a_{0}$ and $b_{0}$ were chosen as members of $A$ and $B$ respectively (members within $\epsilon/2$ of $\textrm{lub}(A)$ and $\textrm{lub}(B)$). Since $a_{0}\in A$ and $b_{0}\in B$, it follows that $a_{0}+b_{0}\in A+B$.  
We have now exhibited a member of $A+B$ that is greater than $x$, (namely $a_{0}+b_{0})$, so we may conclude that $x$ cannot be an upper bound for $A+B$.  
Finally, since $x$ is an arbitrary number smaller than $\textrm{lub}(A)+\textrm{lub}(B)$, it follows that no upper bound for $A+B$ can be smaller than $\textrm{lub}(A)+\textrm{lub}(B)$, which in turn proves that 
$$\textrm{lub}(A)+\textrm{lub}(B)\leq \textrm{lub}(A+B).$$
I take it that you followed the first part of the proof, where it was established that 
$$\textrm{lub}(A)+\textrm{lub}(B)\geq \textrm{lub}(A+B).$$
so that covers the entire proof.
A: This is not a direct answer to the question, but it might still help someone.  
Here is a straightforward proof, based on another definition of $
\newcommand{\lub}[1]{\text{lub}(#1)}
\;\lub{\cdot}\;
$ which is the simplest one I know: $$
\tag{0}
\lub X \le z \;\equiv\; \langle \forall x : x \in X : x \le z \rangle
$$ for all $\;z\;$.
When using this definition, it is very helpful to know the following simple fact about ordering:
$$
\tag{1}
x = y \;\equiv\; \langle \forall z :: x \le z \equiv y \le z \rangle
$$
In other words: things which have the same upper bounds are equal.  So we can prove an equality by proving upper bounds the same.
And to prove a statement like $$
\tag{2}
\lub{A+B} = \lub A + \lub B
$$ it is often easiest to start at the most complex side (here: the right hand side), apply the definitions or basic properties, and then simplify working towards the other side.$
\newcommand{\calc}{\begin{align} \quad &}
\newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}}
\newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} }
\newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & }
\newcommand{\endcalc}{\end{align}}
\newcommand{\Ref}[1]{\text{(#1)}}
$

Therefore we calculate as follows, to see when an arbitrary $\;z\;$ is an upper bound of the RHS of $\Ref{2}$:
$$\calc
    \lub A + \lub B \le z
\op\equiv\hint{arithmetic: reorder -- to prepare for $\Ref{0}$}
    \lub A \le z - \lub B
\op\equiv\hint{by $\Ref{0}$}
    \langle \forall a : a \in A : a \le z - \lub B \rangle
\op\equiv\hint{arithmetic: reorder -- again, to prepare for $\Ref{0}$}
    \langle \forall a : a \in A : \lub B \le z - a \rangle
\op\equiv\hint{by $\Ref{0}$}
    \langle \forall a : a \in A : \langle \forall b : b \in B : b \le z - a \rangle \rangle
    \tag{*}
\op\equiv\hints{logic: bring $\;a,b\;$ together in quantification;}
         \hints{arithmetic: bring $\;a,b\;$ together in inequality}
         \hint{-- working towards the LHS of $\Ref{2}$}
    \langle \forall a,b : a \in A \land b \in B : a + b \le z \rangle
\op\equiv\hint{by definition of $\;A+B\;$ -- again, towards the LHS of $\Ref{2}$}
    \langle \forall x : x \in A + B : x \le z \rangle
\op\equiv\hint{by $\Ref{0}$}
    \lub{A+B} \le z
\endcalc$$
Since the above holds for any $\;z\;$, using $\Ref{1}$ we conclude that $\Ref{2}$ indeed holds.

Notice the goal-driven structure of the above calculation: it first expands the definition of $\;\lub\cdot$ up until $\Ref{*}$, then simplifies towards our goal, and finally reintroduces $\;\lub\cdot\;$ in the last step.
A: $\DeclareMathOperator\lub{lub}$ I also think the proof is a little tricky. There are three keys

(1) "$\lub(A)+\lub(B)$ is an upper bound for $A+B$."

and 

(2) "Suppose $x<\lub(A)+\lub(B)$." (for any $x$ in $X$ such that $A, B \subseteq X$.)

and

(3) "Then $x<a_0+b_0$." (for any $a_0 \in A$ and $b_0 \in B$, i.e., $a_0+b_0 \in A+B$.)

By (1), $A+B$ has a upper bound $S := \lub(A)+\lub(B)$. By (2) and (3), any $x$ less than the upper bound $S$ can not be a upper bound. That is, there is no another upper bound less than $S$. So $S$ is the least upper bound.

Bonus. Using the lemmas

Lemma 1. Let $a,x,y \in \mathbf R$. If
  $$a \le x \le a + y/n$$
  for every integer $n \ge 1$, then $x = a$.
Lemma 2. Let $h$ be a positive integer and let $S$ a subset of $\mathbf R$. If $S$ have least upper bound, then there exists a $x \in S$ such that
  $$x > \lub S - h.$$
Lemma 3. Let $E$ be a non-empty subset of $\mathbf R$. If $E$ has an upper bound, then it must have exactly one least upper bound.

We prove

Theorem 4 (Aditive property). Let $A, B$ be non-empty sets. Let $C = \{a + b : a \in A, b \in B\}$. If $A$ and $B$ have least upper bound, then $C$ has least upper bound and $\lub C = \lub A + \lub B$.

Proof. Let $c \in C$. The there exist $a \in A$ and $b \in B$ such that $c = a + b$. Suppose $A$ and $B$ have least upper bound. Since $a \le \lub A$ and $b \le \lub B$, we have $c = a + b \le \lub A + \lub B$. Thus $C$ has an upper bound and so $\lub C \le \lub A + \lub B$, by Lemma 3. (So far, the proof is identical to yours.)
Let $n \ge 1$ be a positive integer. By the Lemma 2 ($h = 1/n$), there exist $a \in A$ and $b \in B$ such that
$$a > \lub A - 1/n, \qquad b > \lub B - 1/n.$$
So
$$a + b > \lub A + \lub B - 2/n,$$
i.e.,
$$\lub A + \lub B < a + b + 2/n \le \lub C + 2/n.$$
Also, since $a + b \le \lub C$, we obtain
$$\lub C \le \lub A + \lub B < \lub C + 2/n$$
for every integer $n \ge 1$. By the Lemma 1, $\lub C = \lub A + \lub B$.
A: Above proofs feel boring.
Here I am giving a very easy proof:
Let$ \alpha=lub(A)$, $\beta=lub(B)$.
and $$A+B=\{x+y: x\in A,y\in B\}$$,
we have to prove that
$lub(A+B)=lub(A)+lub(B)=\alpha+\beta$.
Let $\alpha+\beta$ be upper bound of $A+B$.
For every $x\in A,y\in B$ ,$x+y\in A+B$.
Let $\gamma$ be another upper bound of $A+B$. We claim that $\alpha+\beta\leq \gamma$!
$\forall x\in A, y\in B$,
we have $x+y\leq \gamma$.
Fix $y\in B$, $\forall x\in A$, $x+y\leq \gamma\Rightarrow x\leq \gamma-y$.
Then $\gamma-y$ is upper bound of $A$. But we have $\alpha=lub(A)$.
Therefore , $\alpha\leq \gamma-y\Rightarrow y\leq\gamma-\alpha$,
which is true for every $y\in B$.
It follows that, $y\leq \gamma-\alpha$.
and $\gamma-\alpha$ is an upper bound of $B$.
Since $\beta$ is $lub(B)$ $\Rightarrow \beta\leq \gamma-\alpha\Rightarrow \beta+\alpha\leq \gamma$.
Hence $\alpha+\beta= lub(A+B)$.
This completes the proof.
