Unique Minimal Element may not be Smallest

From ProofWiki
Jump to navigation Jump to search

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