When is minimal element $=$ least element?

240 Views Asked by At

Suppose $\langle S,\in\rangle$ is well-ordered and $A\ne \emptyset\subseteq S $

If $x\in A$ is a minimal element of $A$, does that mean it is also the least element of $A$ since $S$ is totally ordered?

1

There are 1 best solutions below

0
On BEST ANSWER

Let $(S,\le)$ be an ordered set. The following are equivalent:

  1. For all $x,y\in S$, either $x\le y$ or $y\le x$.

  2. For all $H\subseteq S$, for all $m\in H$, either $m$ is not minimal in $H$ or $m$ is the minimum of $H$.

Proof: $[(1)\Rightarrow (2)]$. Let $H\subseteq S$. If $H=\emptyset$, the conclusion is vacuously true. So, let $m\in H$. If $m$ is not minimal, there is nothing to prove. If $m$ is minimal, we want to prove that $\forall h\in H,\ m\le h$. Let $h\in H$; by $(1)$, $h\le m\vee m\le h$. If $m\le h$, there is nothing to prove. If $h\le m$, by minimality $m=h$, and thus $m\le h$, QED.

$[(2)\Rightarrow (1)]$. The conclusion is vacuously true if $S=\emptyset$. So, let $x\in S$ and $y\in S$. Apply $(2)$ to $H=\{x,y\}$. If $x$ is the minimum of $H$, then $x\le y$. If $x$ is not minimal in $H$, then $y\ne x$ and $y\le x$. Either way, at least one between "$x\le y$" and "$y\le x$" holds. QED

So, "Yes" to the question in the body.