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

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$


Also see


Sources