Prove $\sup S \leq \inf T$, if $s \leq t$, $\forall s \in S$ and $\forall t \in T$

Question

I have the following exercise:

Prove $\sup S \leq \inf T$, if $s \leq t$, forall $s \in S$ and $t \in T$. Note that $S$ is bounded above and $T$ is bounded below.

This might seem too obvious, but for me it's more complicated to prove: In think always there's something that is wrong with my proof, or that I am not proving anything.

Ok, this is how I would go about proving this (and I have thought for a while):

By contradiction, suppose $\sup S > \inf T$.

By definition, $\sup S \geq s$, $\forall s \in S$, and $\inf T \leq t$, $\forall t \in T$.

Now, suppose $\sup S = \max S$ and that $\inf T = \min T$. This would mean that there's a $s \in S > t \in T$. But this contradicts the definition that $s \leq t$ for all $s \in S$ and for all $t \in T$. So, $\sup S \geq \inf T$.

Is my proof correct? If yes, can I do something to improve it?

Answer 1

Your proof is not ok cause you cannot assume $\sup S=\max S$ etc. Instead, based on the assumption $\sup S>\inf T$ let $a=\frac{\sup S+\inf T}{2}$. From $a<\sup S$ conclude that $s>a$ for some $s\in S$. Similarly conclude that $t<a$ for some $t\in T$. This gives the desired contradiction.

Answer 2

For infinite set "max" or "min" can be not well-defined, you can proceed as the following:

Claim: $\inf T\geq s$ for all $s\in S$. Otherwise, there is some $s\in S$ such that $s>\inf T$. By the definition of infimum, there is some $t\in T$ such that $s>t$, contradiction. Hence $\inf T$ is an upper bound for $S$, in particular, $\inf T\geq \sup S$.

Answer 3

No, your proof is not correct: you can't assume $S$ has a maximum or $T$ has a minimum.

I assume the sets $S$ and $T$ are non empty.

Let $x=\sup S$, which exists because $S$ is bounded above by $T$. If $x>t$, for some $t\in T$, consider $\varepsilon=x-t>0$. By the definition of supremum, there is $s\in S$ with $$ x-s<\varepsilon $$ that is $$ x-s<x-t $$ which translates into $s>t$: this is impossible.

Therefore $x\le t$, for all $t\in T$. In particular $x$ is a lower bound for $T$, so $$ x\le \inf T $$ because $\inf T$ is the greatest lower bound of $T$.

Answer 4

Earlier answers already explained why your proof is not correct, since $\;\text{min}\;$ and $\;\text{max}\;$ might not exist. Here is an alternative proof that might be helpful: more formal than many are used to, but (in my experience) easier to design since we're trying to let the shape of the formulas guide our proof design.$ \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)}} \newcommand{\sup}[1]{\text{sup }#1} \newcommand{\inf}[1]{\text{inf }#1} \newcommand{\then}{\Rightarrow} \newcommand{\when}{\Leftarrow} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}} $

The most important thing to do, for proofs like this, is to have explicit the definitions and properties that you are allowed to use. In this case, the simplest definitions I know for $\;\sup\;$ and $\;\inf\;$ are \begin{align} \tag{0} \sup S \leq z & \;\equiv\; \langle \forall s : s \in S : s \leq z \rangle & \\ \tag{1} z \leq \inf T & \;\equiv\; \langle \forall t : t \in T : z \leq t \rangle & \\ \end{align} for any $\;z\;$, any $\;S\;$ which is upper-bounded and non-empty, and any $\;T\;$ which is lower-bounded and non-empty.

---

Now, let us see how see how we can use these definitions in rewriting the desired conclusion: $$\calc \sup S \leq \inf T \op=\hints{using ordering property $\ref 2$, below} \hint{-- the only way I see to apply the above definitions} \langle \forall z : z \leq \sup S : z \leq \inf T \rangle \op=\hint{definition $\ref 1$} \langle \forall z : z \leq \sup S : \langle \forall t : t \in T : z \leq t \rangle \rangle \op=\hints{logic: exchange quantifications} \hint{-- to bring both $\;z\;$'s back together} \langle \forall t : t \in T : \langle \forall z : z \leq \sup S : z \leq t \rangle \rangle \op=\hint{simplify using ordering property $\ref 2$, below} \langle \forall t : t \in T : \sup S \leq t \rangle \op=\hint{definition $\ref 0$} \langle \forall t : t \in T : \langle \forall s : s \in S : s \leq t \rangle \rangle \endcalc$$ This completes the proof.

---

Note how we twice used the basic ordering property that $$ \tag{2} s \leq t \;\equiv\; \langle \forall z : z \leq s : z \leq t \rangle $$ Also, the above proof actually proves not just the $\;\when\;$ direction, but it proves both directions at the same time.