Ordered Set may not have Maximal Element

From ProofWiki
Jump to navigation Jump to search

Theorem

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


It may be the case that $S$ has no maximal elements.


Proof

Consider the set $S$ defined as:

$S = \N \setminus \set 0$

That is, $S$ is the set of natural numbers with $0$ 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.


Aiming for a contradiction, suppose $S$ has a maximal element $m$.

Consider the natural number $n = 2 m$.

Then:

$m \divides n$

but:

$m \ne n$

and so by definition $m$ is not a maximal element of $S$.

Hence by Proof by Contradiction it follows that there exists no such $m$.

Hence the result.

$\blacksquare$


Sources