0
$\begingroup$

I want to prove or disprove $\min{S_1}=\min{S_2}\Longleftrightarrow\min{S_1}\in S_2\land\min{S_2}\in S_1$ but I don't know where to start.

Maybe take cases like $\min{S_1}<\min{S_2}$, $\min{S_1}>\min{S_2}$ and $\min{S_1}=\min{S_2}$ and see where it is true?

$\endgroup$
1
$\begingroup$

(1). If $\min S$ exists then for any $x$ we have $(x\in S\implies \min S\leq x).$ Hence with $x=\min S_1$ and $S=S_2$ we have $$\min S_1\in S_2\implies \min S_2\leq \min S_1.$$ Interchanging the subscripts we have $$\min S_2\in S_1\implies \min S_1\leq \min S_2.$$ $$\text {Therefore }\quad (\min S_1\in S_2\land \min S_2\in S_1)\implies$$ $$\implies (\min S_2\leq \min S_1\land \min S_1\leq \min S_2)\implies \min S_1=\min S_2.$$

(2). If $\min S_1=\min S_2$ then $(\min S_1=\min S_2\in S_2 \land \min S_2=\min S_1\in S_1).$

$\endgroup$
1
$\begingroup$

To show a proposition is true if and only if another one holds, you need to show it for both directions.

The forward direction is rather straightforward. If we assume that $minS_1 = minS_2$ then let's call it $k = min S_1 = min S_2$. Then by definition we know that $k \in S_1$ since it is the min of the set. Likewise, we know that $k \in S_2$ by the same rationale.

The other direction, namely that $min S_1 \in S_2$ and $min S_2 \in S_1$ is a little more difficult to show. Let's presume that $m_1 = min S_1 \neq min S_2 = m_2$. Then we must have that either $m_1 > m_2$ or vice versa.

Assume that $m_1 > m_2$: Since we have $m_1 > m_2$ and $m_1 = min S_1$ then it must be that $m_2 \not\in S_1$, for if $m_2 \in S_1$ then that would violate $m_1$ being the min of the set. However this is a contradiction, since we know that $m2 \in S_2$, so we must have that $m_1 <= m_2$.

If, however, we have $m_1 < m_2$ then we can see that $m_2 = min S_2$ so it must be that $m_1 \not\in S_2$ as otherwise we would have that $m_1 = min S_2$. But this of course also contradicts what we know to be true, namely that $m_1 \in S_2$. So we must have that $m_1 >= m_2$.

If $m2 <= m_1 <= m2$ we must have that $m_1 = m_2$. As neeeded.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.