Minimal Element need not be Unique

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $\struct {S, \preccurlyeq}$ be an ordered set.

It is possible for $S$ to have more than one minimal element.


Proof

Proof by Counterexample:

Consider the set $S$ defined as:

$S = \N \setminus \set {0, 1}$

That is, $S$ is the set of natural numbers with $0$ and $1$ removed.

Let $\preccurlyeq$ be the ordering on $S$ defined as:

$\forall a, b \in S: a \preccurlyeq b \iff a \divides b$

where $a \divides b$ denotes that $a$ is a divisor of $b$.

From Divisor Relation on Positive Integers is Partial Ordering, $\struct {S, \preccurlyeq}$ is a partially ordered set.


Let $p \in S$ be a prime number.

Let $a \divides p$.

By definition of prime number, the only divisors of $p$ are $-p$, $-1$, $1$ and $p$.

Of these, only $p$ is an element of $S$.

Hence if $a \divides p$ it must be the case that $a = p$.

Hence $p$ is a minimal element of $S$ by definition.

Thus every prime number is a minimal element of $S$.

The result follows.

$\blacksquare$


Examples

Arbitrary Example $1$

Consider the set $S = \set {a, b, c, d, e}$ with the partial ordering $\preccurlyeq$ defined as:

${\preccurlyeq} := \set {\tuple {c, a}, \tuple {d, a}, \tuple {e, a}, \tuple {d, b}, \tuple {e, b}, \tuple {c, b}, \tuple {c, e} }$

This can be illustrated using the following Hasse diagram:

Hasse-Diagram-arbitrary-1.png

It can be seen by inspection that both $c$ and $d$ are minimal elements of the partially ordered set $\struct {S, \preccurlyeq}$.


Also see


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Minimal_Element_need_not_be_Unique&oldid=699029"