Proof of The Diagonal Sets of the Cauchy Product and Re-indexing of Diagonal Sums

Elements of a segment $[n]$, $n\in\mathbb{N}_{0}$, are natural numbers by Elements of a Segment Are Natural Numbers, and Mixed Transitivity of the Order on the Natural Numbers (i), and lie in $\mathbb{N}_{0}$.

Proof of (i). Let $n\in\mathbb{N}_{0}$ and let $q$ be a set. If $q\in D_{n}$, the description of $D_{n}$ gives $i,j\in[n]$ with $q=(i,j)$ and $i+j=n+1$. Conversely, if $q=(i,j)$ with $i,j\in[n]$ and $i+j=n+1$, then $q\in[n]\times[n]$ by Membership in a Cartesian Product, and the Cartesian Product of Two Sets Is a Set (i), and so $q\in D_{n}$ by the same description.

Proof of (ii). Let $n\in\mathbb{N}_{0}$. The interval $[n]=\{1,\dots,n\}$ is finite by Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (vii), so $[n]\times[n]$ is finite by Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (v), and its subset $D_{n}$ is finite by Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (iv). If $q\in D_{n}$, then $q=(i,j)$ with $i,j\in[n]$ by (i); so $i,j\in\mathbb{N}$, and $q\in\mathbb{N}\times\mathbb{N}$ by Membership in a Cartesian Product, and the Cartesian Product of Two Sets Is a Set (i).

Proof of (iii). Let $m\in\mathbb{N}_{0}$ and $N=m+1$; then $N\in\mathbb{N}$, as $N$ is the successor of $m$ by Natural Numbers Are the Successors in Omega: One Is Least and Not a Successor of a Natural Number, the Successor Is Injective, and N Is Closed under Addition and Multiplication (v) and Natural Numbers Are the Successors in Omega: One Is Least and Not a Successor of a Natural Number, the Successor Is Injective, and N Is Closed under Addition and Multiplication (i). By Bijections between Intervals: the Gap Map and the Reversal (ii), the map $r:[N]\to[N]$, $r(a)=(N+1)-a$, is a bijection; for $a\in[N]$, $r(a)$ is the unique $j\in\mathbb{N}_{0}$ with $a+j=N+1$, by The Difference of Two Natural Numbers with Zero (i). By Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting (iv) with $0$, $m$ and $1$ in place of $m$, $n$ and $p$, and as $0+1=1$ by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (i), the map $k\mapsto k+1$ is a bijection from $\{0,\dots,m\}$ onto $\{1,\dots,m+1\}=[N]$.

Let $k\in\{0,\dots,m\}$. As $k\le m$, the difference $m-k\in\mathbb{N}_{0}$ is defined, with $k+(m-k)=m$ (The Difference of Two Natural Numbers with Zero (i)). Since $k+1\in[N]$ and $r(k+1)\in[N]$ with $(k+1)+r(k+1)=N+1$, (i) gives $(k+1,r(k+1))\in D_{N}$. Moreover, by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (iii) and Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order (iv),

$$(k+1)+\big((m-k)+1\big)=\big(k+(m-k)\big)+1+1=(m+1)+1=N+1,$$

and $(m-k)+1\in\mathbb{N}_{0}$, so the uniqueness of the difference (The Difference of Two Natural Numbers with Zero (i)) gives $r(k+1)=(m-k)+1$. Hence $(k+1,(m-k)+1)=(k+1,r(k+1))\in D_{N}$.

So there is a map $\sigma:\{0,\dots,m\}\to D_{N}$ with $\sigma(k)=(k+1,r(k+1))=(k+1,(m-k)+1)$, given by an expression in $k$ with the map $r$ as a parameter; it is the only map with these values, maps with equal values being equal. It is injective: if $\sigma(k)=\sigma(k')$, then $k+1=k'+1$ by The Characteristic Property of Ordered Pairs and Nested Tuples of Sets (i), so $k=k'$ as $k\mapsto k+1$ is injective. It is surjective: let $q\in D_{N}$. By (i), $q=(i,j)$ with $i,j\in[N]$ and $i+j=N+1$. As $k\mapsto k+1$ maps $\{0,\dots,m\}$ onto $[N]$, $i=k+1$ for some $k\in\{0,\dots,m\}$; and as $j\in\mathbb{N}_{0}$ with $i+j=N+1$, $j=r(i)$ by the uniqueness of the difference. So $q=(k+1,r(k+1))=\sigma(k)$. Hence $\sigma$ is a bijection.

Proof of (iv). Let $m$, $E$ and $g$ be as there, and let $\sigma$ be the bijection of (iii). As $\sigma(k)\in D_{m+1}\subseteq E$ for $k\in\{0,\dots,m\}$, there is a map $a:\{0,\dots,m\}\to\mathbb{R}$ with $a_{k}=g(\sigma(k))=g(k+1,(m-k)+1)$, given by an expression in $k$ with the maps $g$ and $\sigma$ as parameters, and it is unique, maps with equal values being equal. Let $f=g|_{D_{m+1}}:D_{m+1}\to\mathbb{R}$; then $f(\sigma(k))=g(\sigma(k))=a_{k}$ for every $k\in\{0,\dots,m\}$. The set $\{0,\dots,m\}$ is finite by Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (vii), and $D_{m+1}$ is finite by (ii); addition on $\mathbb{R}$ is associative and commutative with neutral element $0$. So Iterated Operations over Finite Sets: Singletons, Disjoint Unions, Reindexing, Products of Sets, Termwise Combination, Homomorphisms and Intervals (iii), applied to the bijection $\sigma$ from $\{0,\dots,m\}$ onto $D_{m+1}$ and to $f$, gives

$$\sum_{k\in\{0,\dots,m\}}a_{k}=\sum_{k\in\{0,\dots,m\}}f(\sigma(k))=\sum_{x\in D_{m+1}}f(x).$$

The left side is $\sum_{k=0}^{m}a_{k}$ by Sums and Products over a Finite Set and over an Interval (iv), and the right side is $\sum_{(i,j)\in D_{m+1}}g(i,j)$ by Sums and Products over a Finite Set and over an Interval (iii), the sum of $g$ over $D_{m+1}$ being that of its restriction $f$.