Proof of Block Indices: Enumerating an Initial Segment of Length qN by Blocks and Positions

Each result cited is universally quantified over the data in its own statement.

Throughout, $\iota:\mathbb{N}\to\mathbb{R}$ is the canonical map $\iota_{\mathbb{R}}$ of clause 3 of The Real Numbers and Standard Notation, through which natural numbers are read as real numbers, as in Euclidean Space and Lebesgue Measure: Standing Notation §reals; thus $b(k,i)$ is the real number $(\iota(k)-1)\,\iota(q)+\iota(i)$. The claims of Properties of the Canonical Map from the Natural Numbers to an Ordered Field are applied with $F=\mathbb{R}$, and field identities in $\mathbb{R}$ are justified by the numbered axioms of Field.

Step 1 (Transfer of order). Let $m,n\in\mathbb{N}$. We show that $m\le n$ holds if and only if $\iota(m)\le\iota(n)$. If $m=n$ then $\iota(m)=\iota(n)$; if $m<n$ then $\iota(m)<\iota(n)$ by claim 6 of Properties of the Canonical Map from the Natural Numbers to an Ordered Field, so $\iota(m)\le\iota(n)$. Conversely suppose $\iota(m)\le\iota(n)$ but not $m\le n$. By claim 3 of Properties of the Order on the Natural Numbers then $n<m$, so $\iota(n)<\iota(m)$ by claim 6 of Properties of the Canonical Map from the Natural Numbers to an Ordered Field, and together with $\iota(m)\le\iota(n)$ claim 2 of Elementary Order Arithmetic in an Ordered Field gives $\iota(n)<\iota(n)$, which is impossible because $a<b$ requires $a\ne b$. Moreover $\iota(m)=\iota(n)$ implies $m=n$ by claim 7 of Properties of the Canonical Map from the Natural Numbers to an Ordered Field.

Step 2 (Each $b(k,i)$ is a natural number). Let $k\in[N]$ and $i\in[q]$. By claim 4 of Properties of the Order on the Natural Numbers, $1\le k$. If $k=1$, then $\iota(k)=1$ by claim 1 of Properties of the Canonical Map from the Natural Numbers to an Ordered Field, so $\iota(k)-1=0$ by axiom 3 of Field, and $b(k,i)=0\cdot\iota(q)+\iota(i)=\iota(i)$ by claim 1 of Zero Products and Elementary Identities in a Field and axioms 4 and 2 of Field; put $n(k,i)=i$. If $1<k$, then by claim 7 of Properties of the Order on the Natural Numbers there is $m\in\mathbb{N}$ with $k=1+m$; claims 4 and 1 of Properties of the Canonical Map from the Natural Numbers to an Ordered Field give $\iota(k)=1+\iota(m)$, so $\iota(k)-1=\iota(m)$ by axioms 4, 1, 3 and 2 of Field, and $b(k,i)=\iota(m)\iota(q)+\iota(i)=\iota(mq+i)$ by claims 5 and 4 of Properties of the Canonical Map from the Natural Numbers to an Ordered Field; put $n(k,i)=mq+i$. In both cases $b(k,i)=\iota(n(k,i))$ with $n(k,i)\in\mathbb{N}$, and by Step 1 $n(k,i)$ is the only natural number with this property. Following clause 3 of The Real Numbers and Standard Notation, $b(k,i)$ also denotes this natural number; this is the reading of $b(k,i)\in[qN]$ and of $a_{b(k,i)}$ in the statement. Note that the formula for $b(k,i)$ does not involve $N$.

In particular, for every $n\in\mathbb{N}$ and $i\in[q]$ we have $\iota(n+1)=\iota(n)+1$ by claim 1 of Properties of the Canonical Map from the Natural Numbers to an Ordered Field, hence $\iota(n+1)-1=\iota(n)$ by axioms 1, 3 and 2 of Field, and therefore $b(n+1,i)=\iota(n)\iota(q)+\iota(i)=\iota(q)\iota(n)+\iota(i)=\iota(qn+i)$ by axiom 8 of Field and claims 5 and 4 of Properties of the Canonical Map from the Natural Numbers to an Ordered Field. Thus

Step 3 (Claim 1). Let $k\in[N]$ and $i\in[q]$, so $k\le N$ and $i\le q$ by Initial Segment of the Natural Numbers, and $\iota(k)\le\iota(N)$, $\iota(i)\le\iota(q)$ by Step 1. Put $c=(\iota(k)-1)\iota(q)$. If $\iota(i)=\iota(q)$ then $c+\iota(i)=c+\iota(q)$; otherwise $\iota(i)<\iota(q)$ and claim 1 of Elementary Order Arithmetic in an Ordered Field with axiom 4 of Field gives $c+\iota(i)<c+\iota(q)$. In either case $c+\iota(i)\le c+\iota(q)$. By axioms 8, 6, 9, 1, 4, 3 and 2 of Field,

which is $\iota(qk)$ by claim 5 of Properties of the Canonical Map from the Natural Numbers to an Ordered Field. Hence $\iota(n(k,i))=b(k,i)\le\iota(qk)$, and $n(k,i)\le qk$ by Step 1. Next, $0<\iota(q)$ by claim 3 of Properties of the Canonical Map from the Natural Numbers to an Ordered Field, so $0\le\iota(q)$, and claim 5 of Elementary Arithmetic in an Ordered Field applied to $\iota(k)\le\iota(N)$ gives $\iota(q)\iota(k)\le\iota(q)\iota(N)$, that is, $\iota(qk)\le\iota(qN)$ by claim 5 of Properties of the Canonical Map from the Natural Numbers to an Ordered Field; so $qk\le qN$ by Step 1. By claim 1 of Properties of the Order on the Natural Numbers, $n(k,i)\le qN$, that is, $b(k,i)\in[qN]$ by Initial Segment of the Natural Numbers. This proves claim 1, for every $N\in\mathbb{N}$.

Step 4 (The inductive set). Fix $q$. Let $A$ be the set of those $N\in\mathbb{N}$ for which both of the following hold: (B$_{N}$) for every $j\in[qN]$ there is exactly one pair $(k,i)$ with $k\in[N]$, $i\in[q]$ and $b(k,i)=j$; (S$_{N}$) for every family $(a_{j})_{j\in[qN]}$ of real numbers, $\sum_{j=1}^{qN}a_{j}=\sum_{k=1}^{N}\sum_{i=1}^{q}a_{b(k,i)}$, the summands on the right being defined by Step 3. We show $1\in A$ and $S(N)\in A$ for every $N\in A$; then $A=\mathbb{N}$ by Principle of Induction for the Natural Numbers, which proves claims 2 and 3.

Step 5 ($1\in A$). By identity 3 of Natural Numbers, $q\cdot1=q$, and $[1]=\{1\}$ by claim 2 of Basic Properties of Initial Segments of the Natural Numbers. By Step 2 (case $k=1$), $b(1,i)=i$ for $i\in[q]$. For (B$_{1}$), let $j\in[q]$: the pair $(1,j)$ satisfies $b(1,j)=j$, and if $k\in[1]$, $i\in[q]$ and $b(k,i)=j$, then $k=1$ and $i=b(1,i)=j$. For (S$_{1}$), let $(a_{j})_{j\in[q]}$ be real; with $c_{1}=\sum_{i=1}^{q}a_{b(1,i)}=\sum_{i=1}^{q}a_{i}$, claim 1 of Properties of Finite Sums gives $\sum_{k=1}^{1}c_{k}=c_{1}=\sum_{j=1}^{q}a_{j}$.

Step 6 (Preparation of the inductive step). Let $N\in A$. By identities 1 and 4 of Natural Numbers, $S(N)=N+1$ and $q\,S(N)=qN+q$. By claim 5 of Basic Properties of Initial Segments of the Natural Numbers (with $m=qN$, $t=q$), $[qN]\subseteq[qN+q]$ and the map $\varphi:[q]\to D$, $\varphi(i)=qN+i$, is a bijection onto $D=[qN+q]\setminus[qN]$. By claim 3 of Basic Properties of Initial Segments of the Natural Numbers, $[S(N)]=[N]\cup\{S(N)\}$ and $S(N)\notin[N]$. By $(*)$, $b(S(N),i)=\varphi(i)\in D$, so $b(S(N),i)\notin[qN]$, for every $i\in[q]$; and by Step 3 (applied with $N$), $b(k,i)\in[qN]$ for every $k\in[N]$ and $i\in[q]$. Call these two facts $(**)$.

Step 7 ((B$_{S(N)}$)). Let $j\in[qN+q]$. Existence: if $j\in[qN]$, (B$_{N}$) gives $(k,i)$ with $k\in[N]\subseteq[S(N)]$, $i\in[q]$ and $b(k,i)=j$; if $j\notin[qN]$, then $j\in D$, so $j=\varphi(i)=b(S(N),i)$ for some $i\in[q]$, and $S(N)\in[S(N)]$ by claim 1 of Basic Properties of Initial Segments of the Natural Numbers. Uniqueness: let $(k,i)$ and $(k',i')$ lie in $[S(N)]\times[q]$ with $b(k,i)=b(k',i')=j$. If $j\in[qN]$, then by $(**)$ neither $k$ nor $k'$ equals $S(N)$, so $k,k'\in[N]$, and (B$_{N}$) gives $(k,i)=(k',i')$. If $j\notin[qN]$, then by $(**)$ neither $k$ nor $k'$ lies in $[N]$, so $k=k'=S(N)$, and $\varphi(i)=j=\varphi(i')$ gives $i=i'$ since $\varphi$ is injective.

Step 8 ((S$_{S(N)}$)). Let $(a_{j})_{j\in[qN+q]}$ be real and let $a'$ be its restriction to $[qN]$. By Splitting a Finite Sum at an Index (with $m=qN$, $n=q$),

By (S$_{N}$) applied to $a'$, and since $a'_{b(k,i)}=a_{b(k,i)}$ for $k\in[N]$ by $(**)$, $\sum_{j=1}^{qN}a'_{j}=\sum_{k=1}^{N}\sum_{i=1}^{q}a_{b(k,i)}$. Let $c:[S(N)]\to\mathbb{R}$, $c_{k}=\sum_{i=1}^{q}a_{b(k,i)}$, defined by Step 3 applied with $S(N)$; by $(*)$, $c_{S(N)}=\sum_{i=1}^{q}a_{qN+i}$. Since $N<S(N)$ by claim 5 of Properties of the Order on the Natural Numbers, $N\in[S(N)]$, and claim 1 of Properties of Finite Sums shows that $\sum_{k=1}^{N}c_{k}$ equals the sum over $[N]$ of the restriction of $c$, which is $\sum_{k=1}^{N}\sum_{i=1}^{q}a_{b(k,i)}$, and that $\sum_{k=1}^{S(N)}c_{k}=\sum_{k=1}^{N}c_{k}+c_{S(N)}$. Combining, $\sum_{j=1}^{q\,S(N)}a_{j}=\sum_{k=1}^{S(N)}\sum_{i=1}^{q}a_{b(k,i)}$. Hence $S(N)\in A$, and Step 4 completes the proof.