Unique Minimal Element may not be Smallest
Theorem
Let $\struct {S, \preccurlyeq}$ be an ordered set.
Let $\struct {S, \preccurlyeq}$ have a unique minimal element.
Then it is not necessarily the case that $\struct {S, \preccurlyeq}$ has a smallest element.
Proof
Let $S$ be the set defined as:
- $S = \Z \cup \set m$
where:
- $\Z$ denotes the set of integers
- $m$ is an arbitrary object such that $m \ne \Z$.
Let $\preccurlyeq$ be the relation on $\Z$ defined as:
- $\forall a, b \in S: a \preccurlyeq b \iff \begin {cases} a \le b & : a, b \in \Z \\ a = m = b & : a, b \notin \Z \end{cases}$
where $\le$ is the usual ordering on $\Z$.
Note that for all $x \in \Z$, we have that $x$ and $m$ are non-comparable.
Then $\struct {S, \preccurlyeq}$ is an ordered set such that:
- $m$ is the only minimal element of $\struct {S, \preccurlyeq}$
- $\struct {S, \preccurlyeq}$ has no smallest element.
This is shown as follows:
Let $x \in S$ such that $x \preccurlyeq m$.
Then by definition $x = m$.
Hence $m$ is a minimal element of $\struct {S, \preccurlyeq}$.
Aiming for a contradiction, suppose $y \in \Z$ is another minimal element of $\struct {S, \preccurlyeq}$.
Let $z = y - 1$.
By definition of $\Z$, we have that $z \in \Z$.
But $z \le y$ and so $z \preccurlyeq y$.
Hence for all $y \in \Z$, it is not the case that $y$ is a minimal element of $\struct {S, \preccurlyeq}$.
Hence by Proof by Contradiction it follows that the minimal element $m$ of $\struct {S, \preccurlyeq}$ is unique.
Aiming for a contradiction, suppose $x \in S$ is the smallest element of $\struct {S, \preccurlyeq}$.
Suppose $x \in \Z$.
Then because $x$ and $m$ are non-comparable, it is not the case that $x \preccurlyeq m$.
Hence $x$ cannot be the smallest element.
Suppose $x = m$.
Let $a \in S: a \ne m$.
Then $x$ and $a$ are again non-comparable.
Hence it is not the case that $x \preccurlyeq a$.
Hence $x$ again cannot be the smallest element of $\struct {S, \preccurlyeq}$.
So by Proof by Cases $x$ cannot be the smallest element of $\struct {S, \preccurlyeq}$.
It follows by Proof by Contradiction that there can be no smallest element of $\struct {S, \preccurlyeq}$.
$\blacksquare$
Sources
- 1996: Winfried Just and Martin Weese: Discovering Modern Set Theory. I: The Basics ... (previous) ... (next): Part $1$: Not Entirely Naive Set Theory: Chapter $2$: Partial Order Relations: Exercise $6 \ \text {(c)}$