Strictly Increasing Sequence induces Partition
Theorem
Let $\left \langle {r_k} \right \rangle_{0 \mathop \le k \mathop \le n}$ be a strictly increasing finite sequence of natural numbers.
Let:
- $\forall k \in \left[{1 \,.\,.\, n}\right]: A_k := \left[{r_{k-1} + 1 \,.\,.\, r_k}\right]$
Then:
- $\left\{{A_k: k \in \left[{1 \,.\,.\, n}\right]}\right\}$ is a partition of $\left[{r_0 + 1 \,.\,.\, r_n}\right]$.
Proof
First we show that the elements of $\left\{{A_k: k \in \left[{1 \,.\,.\, n}\right]}\right\}$ are disjoint.
Let $j \in \left[{1 \,.\,.\, n}\right]$.
We have that:
- $\left \langle {r_k} \right \rangle_{0 \mathop \le k \mathop \le n}$ is strictly increasing
and:
- $0 \le j - 1 < j \le n$
Thus by Sum with One is Immediate Successor in Naturally Ordered Semigroup:
- $r_0 \le r_{j-1} < r_j \le r_n \implies \left({r_0 + 1}\right) \le \left({r_{j-1} + 1}\right) \le r_j \le r_n$
So:
- $\varnothing \subset A_j \subseteq \left[{r_0 + 1 \,.\,.\, r_n}\right]$
Because $\left \langle {r_k} \right \rangle_{0 \mathop \le k \mathop \le n}$ is strictly increasing:
- $1 \le j < k \le n \implies A_j \cap A_k = \varnothing$
So the elements of $\left\{{A_k: k \in \left[{1 \,.\,.\, n}\right]}\right\}$ are disjoint, as we were to show.
It remains to be established that:
- if $m \in \left[{r_0 + 1 \,.\,.\, r_n}\right]$
then:
- $m \in A_k$ for some $k \in \left[{1\,.\,.\, n}\right]$.
Let $m \in \left[{r_0 + 1 \,.\,.\, r_n}\right]$.
Consider the set:
- $J = \left\{{j \in \left[{0 \,.\,.\, n}\right]: m \le r_j}\right\}$
Clearly $j \ne \varnothing$ as $n \in J$.
Let $k$ be the smallest element of $J$.
Then because $r_0 < m$:
- $k \ne 0$
Thus:
- $k \in \left[{1 \,.\,.\, n}\right]$
By its definition:
- $r_{k-1} < m \le r_k$
Thus, by Sum with One is Immediate Successor in Naturally Ordered Semigroup:
- $r_{k-1} + 1 \le m \le r_k$
Therefore $m \in A_k$.
$\blacksquare$
Sources
- 1965: Seth Warner: Modern Algebra ... (previous) ... (next): $\S 18$: Theorem $18.3$