Set of Integers Bounded Above by Integer has Greatest Element/Proof 1
Jump to navigation
Jump to search
Theorem
Let $\Z$ be the set of integers.
Let $\le$ be the ordering on the integers.
Let $\O \subset S \subseteq \Z$ such that $S$ is bounded above in $\struct {\Z, \le}$.
Then $S$ has a greatest element.
Proof
$S$ is bounded above, so $\exists M \in \Z: \forall s \in S: s \le M$.
Hence $\forall s \in S: 0 \le M - s$.
Thus the set $T = \set {M - s: s \in S} \subseteq \N$.
The Well-Ordering Principle gives that $T$ has a smallest element, which we can call $b_T \in T$.
Hence:
- $\paren {\forall s \in S: b_T \le M - s} \land \paren {\exists g_S \in S: b_T = M - g_S}$
So:
\(\ds \) | \(\) | \(\ds \forall s \in S: M - g_S \le M - s\) | ||||||||||||
\(\ds \) | \(\leadsto\) | \(\ds \forall s \in S: -g_S \le -s\) | Cancellability of elements of $\Z$ | |||||||||||
\(\ds \) | \(\leadsto\) | \(\ds \forall s \in S: g_S \ge s\) | ||||||||||||
\(\ds \) | \(\leadsto\) | \(\ds g_S \in S \land \paren {\forall s \in S: g_S \ge s}\) | which is how the greatest element is defined. |
So $g_S$ is the greatest element of $S$.
$\blacksquare$
Sources
- 1977: K.G. Binmore: Mathematical Analysis: A Straightforward Approach ... (previous) ... (next): $\S 3$: Natural Numbers: Exercise $\S 3.6 \ (3)$