Proof of Sums over Finite Index Sets: Finite Unions, Disjoint Unions, Vanishing Terms, Dependent Pairs, Conjugation and the Modulus

We use the definitions Finite Set, Number of Elements of a Set, Bijection of Sets, Sum over a Finite Index Set, Finite Sum Notation in a Field, Cartesian Product of Two Sets, via Ordered Pairs, The Complex Numbers, Ordered Field and Total Order on a Set, the axiom Principle of Induction for the Natural Numbers, and the lemmas Basic Properties of Finite Sets, Peeling an Element off a Finite Set, and Unions of Finite Sets, Finiteness of Cartesian Products, Tuple Sets, and Permutation Sets, Basic Properties of Initial Segments of the Natural Numbers, Properties of the Order on the Natural Numbers, Injectivity, Composition, and Restriction of Bijections, Characteristic Property of the Ordered Pair, Properties of a Sum over a Finite Index Set, Properties of Finite Sums, Concatenation of Finite Sums, Zero Products and Elementary Identities in a Field and Properties of Complex Conjugation and Modulus.

Preliminaries. (P1) By Finite Set, a nonempty finite set $X$ has $k$ elements for some $k\in\mathbb{N}$, that is, by Number of Elements of a Set, there is a bijection $[k]\to X$. If $f$ is a map defined on a set containing a nonempty finite set $X$, then $\sum_{x\in X}f(x)$ denotes the sum over $X$ of the restriction of $f$ to $X$.

(P2) Sets with one element. If $\varphi:[1]\to X$ is a bijection, then $X=\{\varphi(1)\}$, because $[1]=\{1\}$ by claim 2 of Basic Properties of Initial Segments of the Natural Numbers.

(P3) Sums over a singleton. Let $y$ be an object and $g:\{y\}\to K$ a map. By claim 2 of Basic Properties of Finite Sets the set $\{y\}$ has $1$ element, and since $[1]=\{1\}$ (claim 2 of Basic Properties of Initial Segments of the Natural Numbers) the map $1\mapsto y$ is a bijection $[1]\to\{y\}$. By Sum over a Finite Index Set and the identity $\sum_{k=1}^{1}a_{k}=a_{1}$ in claim 1 of Properties of Finite Sums,

Claim 1 (finite unions). Let $P$ be the set of all $k\in\mathbb{N}$ with the following property: for every set $A$ with $k$ elements and every family of finite sets $B(a)$, $a\in A$, the union $\bigcup_{a\in A}B(a)$ is finite. We show that $P$ satisfies the two hypotheses of Principle of Induction for the Natural Numbers.

Step 1. $1\in P$: if $A$ has $1$ element, then $A=\{a_{0}\}$ for some $a_{0}$ by (P2), so $\bigcup_{a\in A}B(a)=B(a_{0})$, which is finite.

Step 2. Let $k\in P$ and let $A$ have $S(k)$ elements. By claim 2 of Peeling an Element off a Finite Set, and Unions of Finite Sets there are $A'\subseteq A$ with $k$ elements and $a_{0}\in A$ with $a_{0}\notin A'$ and $A=A'\cup\{a_{0}\}$. Then

where the first set is finite because $k\in P$ and $B(a_{0})$ is finite; so the union is finite by claim 3 of Peeling an Element off a Finite Set, and Unions of Finite Sets. Hence $S(k)\in P$.

By Principle of Induction for the Natural Numbers, $P=\mathbb{N}$. Since the nonempty finite set $A$ has $k$ elements for some $k\in\mathbb{N}$ by (P1), claim 1 follows.

Claim 2 (disjoint unions). By (P1) there are $n,m\in\mathbb{N}$ and bijections $\varphi:[n]\to F$ and $\psi:[m]\to G$. By claim 5 of Basic Properties of Initial Segments of the Natural Numbers, $[n]\subseteq[n+m]$, the set $[n+m]$ is the union of the disjoint sets $[n]$ and $[n+m]\setminus[n]$, and $j\mapsto n+j$ is a bijection from $[m]$ onto $[n+m]\setminus[n]$; so by Bijection of Sets, for each $k\in[n+m]\setminus[n]$ there is exactly one $j\in[m]$ with $k=n+j$. Define $\theta:[n+m]\to F\cup G$ by $\theta(k)=\varphi(k)$ for $k\in[n]$ and $\theta(n+j)=\psi(j)$ for $j\in[m]$.

Step 1. $\theta$ is a bijection. Every $x\in F$ equals $\varphi(k)=\theta(k)$ for some $k\in[n]$, and every $x\in G$ equals $\psi(j)=\theta(n+j)$ for some $j\in[m]$; so each element of $F\cup G$ has a preimage. Suppose $\theta(k)=\theta(k')$. If $k,k'\in[n]$, then $\varphi(k)=\varphi(k')$ and $k=k'$ by claim 1 of Injectivity, Composition, and Restriction of Bijections. If $k=n+j$ and $k'=n+j'$ with $j,j'\in[m]$, then $\psi(j)=\psi(j')$, so $j=j'$ by the same claim, and $k=k'$. If $k\in[n]$ and $k'=n+j'$, then $\theta(k)\in F$ and $\theta(k')\in G$, impossible since $F\cap G=\emptyset$; the symmetric case is the same. Hence each element of $F\cup G$ has exactly one preimage, and $\theta$ is a bijection by Bijection of Sets. In particular $F\cup G$ has $n+m$ elements.

Step 2. Let $a\in K^{n+m}$ be the tuple $a_{k}=f(\theta(k))$. Its restriction $a'$ to $[n]$ has components $a'_{k}=f(\varphi(k))$, and the tuple $b\in K^{m}$ with $b_{k}=a_{n+k}$ has components $b_{k}=f(\psi(k))$. By Sum over a Finite Index Set (with the bijections $\theta$, $\varphi$, $\psi$) and Concatenation of Finite Sums,

Claim 3 (vanishing terms). Step 1. Suppose $f(x)=0$ for every $x\in F$. Then $f(x)=0=0\cdot f(x)$ for every $x\in F$ by claim 1 (annihilation) of Zero Products and Elementary Identities in a Field, so by claim 4 (homogeneity, with $\lambda=0$) of Properties of a Sum over a Finite Index Set and annihilation again,

Step 2. Let $G\subseteq F$ be nonempty with $f=0$ on $F\setminus G$. If $G=F$ there is nothing to prove. Otherwise $H=F\setminus G$ is nonempty; $G$ and $H$ are finite by claim 3 of Basic Properties of Finite Sets, $G\cap H=\emptyset$ and $G\cup H=F$. By claim 2 and Step 1 (applied to the restriction of $f$ to $H$),

the last step by axiom 2 of Field.

Claim 4 (dependent pairs). Step 1 (finiteness). Let $U=\bigcup_{a\in A}B(a)$, finite by claim 1. Then $T\subseteq A\times U$ by Cartesian Product of Two Sets, via Ordered Pairs, the set $A\times U$ is finite by claim 1 of Finiteness of Cartesian Products, Tuple Sets, and Permutation Sets, and so $T$ is finite by claim 3 of Basic Properties of Finite Sets. Choosing $a\in A$ and $b\in B(a)$ gives $(a,b)\in T$, so $T\neq\emptyset$. The same argument shows that for every nonempty subset $A_{1}\subseteq A$ the set $T_{1}$ of pairs $(a,b)$ with $a\in A_{1}$, $b\in B(a)$ is nonempty and finite. For $a\in A$ write $g(a)=\sum_{b\in B(a)}f((a,b))$.

Step 2 (one block). Let $a_{0}\in A$ and $T_{0}=\{a_{0}\}\times B(a_{0})$; this is the set of pairs $(a,b)$ with $a\in\{a_{0}\}$ and $b\in B(a)$, and $T_{0}\subseteq T$. By claim 1 of Finiteness of Cartesian Products, Tuple Sets, and Permutation Sets the map $b\mapsto(a_{0},b)$ is a bijection $B(a_{0})\to T_{0}$, so by (P3) and claim 2 (reindexing) of Properties of a Sum over a Finite Index Set,

Step 3 (induction). Let $Q$ be the set of all $k\in\mathbb{N}$ such that for every subset $A_{1}\subseteq A$ with $k$ elements, $\sum_{a\in A_{1}}g(a)=\sum_{t\in T_{1}}f(t)$, with $T_{1}$ as in Step 1. We have $1\in Q$: a subset with $1$ element is $\{a_{0}\}$ by (P2), and Step 2 applies. Let $k\in Q$ and let $A_{1}\subseteq A$ have $S(k)$ elements. By claim 2 of Peeling an Element off a Finite Set, and Unions of Finite Sets, $A_{1}=A'\cup\{a_{0}\}$ with $A'$ having $k$ elements (so $A'\neq\emptyset$, as $[k]\neq\emptyset$ by claim 1 of Basic Properties of Initial Segments of the Natural Numbers) and $a_{0}\notin A'$. Let $T'$ be the set of pairs over $A'$ and $T_{0}=\{a_{0}\}\times B(a_{0})$. Then $T_{1}=T'\cup T_{0}$, and $T'\cap T_{0}=\emptyset$: a pair $(a,b)$ in both would have $a\in A'$ and $a=a_{0}$ by Characteristic Property of the Ordered Pair. The sets $A'$, $\{a_{0}\}$, $T'$, $T_{0}$ are nonempty and finite (Step 1 and claim 2 of Basic Properties of Finite Sets). By claim 2 twice, the hypothesis $k\in Q$, and Step 2,

So $S(k)\in Q$, hence $Q=\mathbb{N}$ by Principle of Induction for the Natural Numbers. Since $A$ has $k$ elements for some $k$ by (P1), taking $A_{1}=A$ gives claim 4.

Claim 5 (conjugation). By (P1) let $\varphi:[n]\to F$ be a bijection. By Sum over a Finite Index Set (applied to $f$ and to $x\mapsto\overline{f(x)}$) and claim 4 (conjugation) of Properties of Finite Sums,

Claim 6 (modulus). Let $\varphi:[n]\to F$ be a bijection, $a_{k}=f(\varphi(k))\in\mathbb{C}$ and $r_{k}=|a_{k}|\in\mathbb{R}$ for $k\in[n]$. For $j\in[n]$ let $\sigma(j)=\sum_{k=1}^{j}a_{k}$ (finite sum in $\mathbb{C}$) and $\rho(j)=\sum_{k=1}^{j}r_{k}$ (finite sum in $\mathbb{R}$). By Sum over a Finite Index Set, $\sum_{x\in F}f(x)=\sigma(n)$ and $\sum_{x\in F}|f(x)|=\rho(n)$. Below $\le$ between real numbers is the total order of the ordered field $\mathbb{R}$ (Ordered Field); sums of real numbers formed in $\mathbb{C}$ agree with those formed in $\mathbb{R}$ by condition 1 of The Complex Numbers.

Let $Q$ be the set of $j\in\mathbb{N}$ such that $j\le n$ implies $|\sigma(j)|\le\rho(j)$.

Step 1. $1\in Q$: by claim 1 of Properties of Finite Sums, $\sigma(1)=a_{1}$ and $\rho(1)=r_{1}=|a_{1}|$, and $|a_{1}|\le|a_{1}|$ by reflexivity (axiom 1 of Total Order on a Set).

Step 2. Let $j\in Q$ with $S(j)\le n$. By claim 5 of Properties of the Order on the Natural Numbers, $j<S(j)$, so $j\le S(j)$ and $j\le n$ by claim 1 of Properties of the Order on the Natural Numbers; hence $|\sigma(j)|\le\rho(j)$. By the recursion in claim 1 of Properties of Finite Sums (valid as $S(j)\in[n]$), $\sigma(S(j))=\sigma(j)+a_{S(j)}$ and $\rho(S(j))=\rho(j)+r_{S(j)}$. By claim 7 (triangle inequality) of Properties of Complex Conjugation and Modulus, $|\sigma(S(j))|\le|\sigma(j)|+r_{S(j)}$; by axiom 1 of Ordered Field, $|\sigma(j)|+r_{S(j)}\le\rho(j)+r_{S(j)}=\rho(S(j))$; by transitivity (axiom 3 of Total Order on a Set), $|\sigma(S(j))|\le\rho(S(j))$. So $S(j)\in Q$.

By Principle of Induction for the Natural Numbers, $Q=\mathbb{N}$. As $n\le n$ (claim 1 of Properties of the Order on the Natural Numbers), $\bigl|\sum_{x\in F}f(x)\bigr|=|\sigma(n)|\le\rho(n)=\sum_{x\in F}|f(x)|$. $\blacksquare$