Not every Non-Empty Subset of Natural Numbers has Greatest Element

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $S \subseteq \N_{>0}$.

Then, despite Non-Empty Subset of Initial Segment of Natural Numbers has Greatest Element, it is not necessarily the case that $S$ has a greatest element.


Proof

Let:

$S = \left\{{x \in \N_{>0}: x > 1}\right\}$

Then $S \subseteq \N_{>0}$.

Suppose $S$ has a greatest element.

Let the greatest element of $S$ be $k$.

But $\N_{>0}$ is an inductive set.

Therefore $k + 1 \in \N_{>0}$.

By definition of $S$:

$k + 1 \in S$

Therefore $k$ cannot be the greatest element of $S$.

By Proof by Contradiction it follows that $S$ has no greatest element.

It is not possible to apply Non-Empty Subset of Initial Segment of Natural Numbers has Greatest Element, because $S$ is not a subset of an initial segment of $\N_{>0}$.

$\blacksquare$


Sources