TheoremBase

The reversing map is an involution of the initial segment, hence a bijection, and the sum identity is the permutation invariance of finite sums.

Proof

Each result cited is universally quantified over the data in its own statement. Throughout, SS is the successor map of Natural Numbers, so that N+1=S(N)N+1=S(N).

Claim 1. Let a∈[N]a\in[N], so that a≀Na\le N, which by Order on the Natural Numbers means a<Na<N or a=Na=N.

Existence and uniqueness of kk. We first show a<N+1a<N+1. One has N<S(N)=N+1N<S(N)=N+1 by claim 5 of Properties of the Order on the Natural Numbers. If a=Na=N this is a<N+1a<N+1. If a<Na<N, then a<Na<N and N<N+1N<N+1 give a<N+1a<N+1 by the transitivity of << in claim 1 of Properties of the Order on the Natural Numbers. Hence, by claim 7 of Properties of the Order on the Natural Numbers applied with m=am=a and y=N+1y=N+1, there is exactly one k∈Nk\in\mathbb{N} with N+1=a+kN+1=a+k.

The number kk lies in [N][N]. By claim 4 of Arithmetic of Addition on the Natural Numbers, k+a=a+k=N+1=S(N)k+a=a+k=N+1=S(N), and k<k+ak<k+a by claim 6 of Properties of the Order on the Natural Numbers; so k<S(N)k<S(N). Hence k≀S(N)k\le S(N) by claim 1 of Properties of the Order on the Natural Numbers, and kβ‰ S(N)k\ne S(N), since k=S(N)k=S(N) would give k<kk<k, which is excluded by claim 2 of that lemma. Therefore k≀Nk\le N by claim 5 of Properties of the Order on the Natural Numbers, that is, k∈[N]k\in[N]. This defines the map ΟƒN:[N]β†’[N]\sigma_{N}:[N]\to[N].

Involution. Let a∈[N]a\in[N] and put k=ΟƒN(a)k=\sigma_{N}(a), so that a+k=N+1a+k=N+1. By definition ΟƒN(k)\sigma_{N}(k) is the unique kβ€²βˆˆNk'\in\mathbb{N} with k+kβ€²=N+1k+k'=N+1. Since k+a=a+k=N+1k+a=a+k=N+1 by claim 4 of Arithmetic of Addition on the Natural Numbers, uniqueness gives kβ€²=ak'=a, that is, ΟƒN(ΟƒN(a))=a\sigma_{N}(\sigma_{N}(a))=a.

Bijection. Let b∈[N]b\in[N]. The element a=ΟƒN(b)a=\sigma_{N}(b) of [N][N] satisfies ΟƒN(a)=ΟƒN(ΟƒN(b))=b\sigma_{N}(a)=\sigma_{N}(\sigma_{N}(b))=b. If aβ€²βˆˆ[N]a'\in[N] also satisfies ΟƒN(aβ€²)=b\sigma_{N}(a')=b, then aβ€²=ΟƒN(ΟƒN(aβ€²))=ΟƒN(b)=aa'=\sigma_{N}(\sigma_{N}(a'))=\sigma_{N}(b)=a. Thus for every b∈[N]b\in[N] there is exactly one a∈[N]a\in[N] with ΟƒN(a)=b\sigma_{N}(a)=b, which is the defining property of a bijection in Bijection of Sets.

The reading in an ordered field. Let FF be an ordered field with canonical map ΞΉF\iota_{F}, let a∈[N]a\in[N] and k=ΟƒN(a)k=\sigma_{N}(a). By claim 4 of Properties of the Canonical Map from the Natural Numbers to an Ordered Field, ΞΉF(a)+ΞΉF(k)=ΞΉF(a+k)=ΞΉF(N+1)\iota_{F}(a)+\iota_{F}(k)=\iota_{F}(a+k)=\iota_{F}(N+1), and ΞΉF(N+1)=ΞΉF(N)+1\iota_{F}(N+1)=\iota_{F}(N)+1 by claim 1 of that lemma. Adding βˆ’ΞΉF(a)-\iota_{F}(a) to both sides gives ΞΉF(k)=ΞΉF(N)+1βˆ’ΞΉF(a)\iota_{F}(k)=\iota_{F}(N)+1-\iota_{F}(a).

Claim 2. By claim 1, ΟƒN\sigma_{N} is a bijection from [N][N] to [N][N], so claim 1 of Invariance of Finite Sums and Products under Reindexing by a Permutation, applied to the map hh and the bijection ΟƒN\sigma_{N}, gives βˆ‘a=1NhΟƒN(a)=βˆ‘a=1Nha\sum_{a=1}^{N}h_{\sigma_{N}(a)}=\sum_{a=1}^{N}h_{a}.

Citations

Loading…

Dependencies

Uses0

Loading…

Comments

Log in to comment.

Loading…