Sum over Disjoint Union of Finite Sets
Theorem
Let $\mathbb A$ be one of the standard number systems $\N, \Z, \Q, \R, \C$.
Let $S$ and $T$ be finite disjoint sets.
Let $S \cup T$ be their union.
Let $f: S \cup T \to \mathbb A$ be a mapping.
Then we have the equality of summations over finite sets:
- $\ds \sum_{u \mathop \in S \mathop \cup T} \map f u = \sum_{s \mathop \in S} \map f s + \sum_{t \mathop \in T} \map f t$
Outline of Proof
We reduce to the case of indexed summations by choosing appropriate bijections in the definition of summation over finite set.
We thereby reduce the problem to Indexed Summation over Adjacent Intervals.
Proof
Note that by Union of Finite Sets is Finite, the union $S \cup T$ is finite.
Let $m$ be the cardinality of $S$ and $n$ be the cardinality of $T$.
Let $\N_{< m}$ denote an initial segment of the natural numbers.
Let $\sigma: \N_{<m} \to S$ and $\tau: \N_{<n} \to T$ be bijections.
Let $\alpha: \N_{< n} \to \closedint m {m + n - 1}$ be the mapping defined as:
- $\map \alpha k = k + m$
By Translation of Integer Interval is Bijection, $\alpha$ is a bijection.
By Composite of Bijections is Bijection and Disjoint Union of Bijections is Bijection, the union:
- $\sigma \cup \paren {\tau \circ \alpha} : \N_{<m} \cup \closedint m {m + n - 1} \to S \cup T$ is a bijection.
By Union of Integer Intervals, $\N_{<m} \cup \closedint m {m + n - 1} = \N_{< m + n}$.
We have:
| \(\ds \sum_{u \mathop \in S \mathop \cup T} \map f u\) | \(=\) | \(\ds \sum_{i \mathop = 0}^{m + n - 1} \map {f \circ \paren {\sigma \cup \paren {\tau \circ \alpha} } } i\) | Definition of Summation | |||||||||||
| \(\ds \) | \(=\) | \(\ds \sum_{i \mathop = 0}^{m - 1} \map {f \circ \paren {\sigma \cup \paren {\tau \circ \alpha} } } i + \sum_{i \mathop = m}^{m + n - 1} \map {f \circ \paren {\sigma \cup \paren {\tau \circ \alpha} } } i\) | Indexed Summation over Adjacent Intervals | |||||||||||
| \(\ds \) | \(=\) | \(\ds \sum_{i \mathop = 0}^{m - 1} \map {\paren {f \circ \sigma} } i + \sum_{i \mathop = m}^{m + n - 1} \map {\paren {g \circ \tau \circ \alpha} } i\) | Restriction of Union of Mappings to Component of Domain | |||||||||||
| \(\ds \) | \(=\) | \(\ds \sum_{i \mathop = 0}^{m - 1} \map {\paren {f \circ \sigma} } i + \sum_{i \mathop = 0}^{n - 1} \map {\paren {g \circ \tau} } i\) | Definition of $\alpha$, Indexed Summation over Translated Interval | |||||||||||
| \(\ds \) | \(=\) | \(\ds \sum_{s \mathop \in S} \map f s + \sum_{t \mathop \in T} \map g t\) | Definition of Summation |
$\blacksquare$