Maximal Element need not be Greatest Element

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Let $M \in $ be a maximal element of $S$.


Then $M$ is not necessarily the greatest element of $S$.


Proof

Proof by Counterexample:

Let $S = \set {a, b, c}$.

Let $\preccurlyeq$ be defined as:

$x \preccurlyeq y \iff \tuple {x, y} \in \set {\tuple {a, a}, \tuple {b, b}, \tuple {c, c}, \tuple {a, b}, \tuple {a, c} }$

A straightforward but laborious process determines that $\preccurlyeq$ is a partial ordering on $S$.


We have that:

$c \preccurlyeq x \implies c = x$

and:

$b \preccurlyeq x \implies b = x$

and so by definition, both $b$ and $c$ are maximal elements of $S$.


Suppose $b$ is the greatest element of $S$.

Then from Greatest Element is Unique it follows that $c$ can not be the greatest element of $S$.

Hence the result.


In fact, from the definition of the greatest element of $S$:

$x$ is the greatest element of $S$ if and only if $\forall y \in S: y \preccurlyeq x$

it can be seen directly that neither $b$ nor $c$ is the greatest element of $S$.

$\blacksquare$


Also see


Sources