I'm trying to prove the answer to a question on one of Terence Tao's Java-based math quizzes, relating to suprema and infima. Below is the question, along with the answer:
Question: Let $A$ and $B$ be non-empty sets [of real numbers]. Which of the following statements would be equivalent to saying that $\sup(A) \le \sup(B)$?
Correct Answer: For every $a$ in $A$ and $\epsilon > 0$ there exists a $b$ in $B$ such that $a < b + \epsilon$.
Attempt at a proof:
I'll begin with two lemmas, the first of which is also the subject of another question on the same quiz:
Lemma 1: Let $A$ be a subset of $\mathbb{R}$, and let $L$ be a real number. If $\sup(A) < L$, then there exists an $\epsilon > 0$ such that every element of $A$ is less than $L - \epsilon$.
My (attempted) proof of this lemma (is this proof valid?):
Let $\delta=L-\sup(A)$. This quantity is positive by the hypothesis of the lemma. By the definition of supremum, we have $\forall a \in A$, $a \le \sup(A)=L-\delta$.
Now, this is close to what we are trying to show, but the lemma states that every element of $A$ is strictly less than $L-\epsilon$.
To remedy this, let $\epsilon = \frac{\delta}2$. Clearly (is it?), $0 < \frac{\delta}2 < \delta$, so $L-\delta < L-\epsilon $.
Thus, $\forall a \in A$, $a \le \sup(A)=L-\delta < L-\epsilon$, and therefore
$$ \forall a \in A, a < L-\epsilon. $$
Since such an $\epsilon$ can always be found (just let $\epsilon=\frac{1}{2}(L-\sup A)$), the proof is complete.
The second lemma states that the converse of Lemma 1 also holds:
Lemma 2: Let $A$ be a subset of $\mathbb{R}$, and let $L$ be a real number. If there exists an $\epsilon > 0$ such that every element of $A$ is less than $L - \epsilon$, then $\sup(A)<L$.
Attempted proof:
Since $L-\epsilon$ is greater than every element of $A$, $L-\epsilon$ is an upper bound for $A$, and therefore $L-\epsilon \ge \sup(A).$
Since $\epsilon>0$, we have that $L > L-\epsilon \ge \sup(A)$, which implies that
$$\sup(A) < L,$$
as desired.
Now, continuing with our main proof:
Let $A$ and $B$ be non-empty sets of real numbers.
Let $P$ denote the statement that $\sup(A)\le\sup(B)$.
Let $Q$ denote the statement that $(\forall a \in A)(\forall\epsilon > 0) (\exists b \in B)[a<b+\epsilon]$.
Instead of proving $P \iff Q$, I will instead try to show that $\neg P \iff \neg Q$. (Is this a valid way to show the original equivalence?)
Note the following symbolic representations for $\neg P$ and $\neg Q$: $$\neg P: \sup(B) < \sup(A) $$
$$\neg Q: (\exists a \in A)(\exists \epsilon > 0)(\forall b \in B)[a \ge b+\epsilon] $$
Finally, note that I will use U.B. to stand for upper bound.
First attempt:
\begin{align} \neg P &\iff \sup(B)<\sup(A)\\[1ex] &\iff (\exists \epsilon > 0)(\forall b \in B)[b < \sup(A) - \epsilon] && \text{(By Lemmas 1 and 2)} \\[1ex] &\iff (\exists \epsilon > 0)(\forall b \in B)[b + \epsilon < \sup(A)] \\[1ex] &\iff (\exists \epsilon > 0)(\forall b \in B)[\text{$b+\epsilon$ is not a U.B. for $A$}] && \text{(*)} \\[1ex] &\iff (\exists \epsilon > 0)(\forall b \in B)(\exists a \in A)[a>b+\epsilon] \end{align}
This is as far as I could get on this attempt.
The last equivalent statement is not equivalent to $\neg Q$, because of the difference in the order of quantifiers and the presence of a strong inequality as opposed to a weak inequality.
Additionally, I'm not sure that the fourth equivalence (marked with a (*)) is valid. I know that if $x < \sup(A) $, then $x$ is not an upper bound for $A$. I believe the converse also holds: If $x$ is not an upper bound for $A$, then there exists an $a \in A$ such that $x < a$, and since $a \le \sup(A)$, $x < \sup(A)$.
Second attempt:
\begin{align} \neg P &\iff \sup(B)<\sup(A)\\[1ex] &\iff \text{$\sup(B)$ is not a U.B. for $A$} && \text{(*)} \\[1ex] &\iff (\exists a \in A)[\sup(B)<a] \\[1ex] &\iff (\exists a \in A)(\exists \epsilon > 0)(\forall b \in B)[b < a-\epsilon] &&\text{(By Lemmas 1 and 2)} \\[1ex] &\iff (\exists a \in A)(\exists \epsilon > 0)(\forall b \in B)[a > b+\epsilon]\\[1ex] \end{align}
Again, I'm not fully sure that the second equivalence (marked with a (*)) is valid, for the same reason why I questioned the fourth equivalence in the first attempt above.
Putting that aside, we see that in this attempt, the last equivalent statement is closer to $\neg Q$, but they are still not equivalent, as the former still has a strong inequality instead of a weak one. However, this last statement does imply $\neg Q$, because if $a > b+\epsilon$, then certainly $a \ge b + \epsilon$. In other words, the steps above appear to show that $\neg P \implies \neg Q$. But it's not clear to me how one could begin at $\neg Q$ and arrive at $\neg P$, which is needed to establish the implication in the other direction.
The only idea that comes to mind is to do something similar to what I did in the proof of Lemma 1. In other words, start with the $\epsilon$ which, according to $\neg Q$, exists and satisfies the weak inequality, and then divide the value of $\epsilon$ by e.g. $2$ to obtain a new $\epsilon_0$ which satisfies the strict inequality. More concretely, if $a \ge b + \epsilon$ and $0 < \frac{1}{2}\epsilon =\epsilon_0 < \epsilon$, then
$$a \ge b+\epsilon > b + \epsilon_0,$$
so
$$a > b + \epsilon_0.$$
Does this modification "bridge the gap" and show that $\neg Q \implies \neg P$? I think so: \begin{align} \neg Q &\iff (\exists a \in A)(\exists \epsilon > 0)(\forall b \in B)[a \ge b+\epsilon] \\[1ex] &\iff (\exists a \in A)(\exists \epsilon_0 > 0)(\forall b \in B)[a > b+\epsilon_0] && \text{Let $\epsilon_0 = \frac{1}{2}\epsilon$} \\[1ex] \end{align}
The key change is that now we can go from the strict inequality to the weak one in both directions. Going from strict to weak, no changes are needed. Going from the weak one to the strict one, just let $\epsilon_0=\frac{1}{2}\epsilon$.
Revised attempt at the proof:
\begin{align} \neg P &\iff \sup(B)<\sup(A)\\[1ex] &\iff \text{$\sup(B)$ is not a U.B. for $A$} \\[1ex] &\iff (\exists a \in A)[\sup(B)<a] \\[1ex] &\iff (\exists a \in A)(\exists \epsilon > 0)(\forall b \in B)[b < a-\epsilon] && \text{(By Lemmas 1 and 2)} \\[1ex] &\iff (\exists a \in A)(\exists \epsilon > 0)(\forall b \in B)[a > b+\epsilon]\\[1ex] &\iff (\exists a \in A)(\exists \epsilon_1 > 0)(\forall b \in B)[a \ge b+\epsilon_1] && \text{Let $\epsilon_1 = \frac{1}{2}\epsilon$}\\[1ex] &\iff \neg Q \end{align}
Since $\neg P \iff \neg Q$, $P \iff Q$.
Does this final attempt constitute a valid proof? Is there an easier way of establishing the equivalence?