Set of Integers Bounded Below by Integer has Smallest Element

From ProofWiki
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 below in $\struct {\Z, \le}$.


Then $S$ has a smallest element.


Proof

We have that $S$ is bounded below in $\Z$.

So:

$\exists m \in \Z: \forall s \in S: m \le s$

Hence:

$\forall s \in S: 0 \le s - m$

Thus:

$T = \set {s - m: 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 s - m} \land \paren {\exists b_S \in S: b_T = b_S - m}$

So:

\(\displaystyle \) \(\) \(\displaystyle s \in S: b_S - m \le s - m\)
\(\displaystyle \) \(\leadsto\) \(\displaystyle \forall s \in S: b_S \le s\) Cancellability of elements of $\Z$
\(\displaystyle \) \(\leadsto\) \(\displaystyle b_S \in S \land \paren {\forall s \in S: b_S \le s}\) Definition of Smallest Element

So $b_S$ is the smallest element of $S$.

$\blacksquare$


Also see


Sources