Proof of Extraction of a Term from a Finite Sum or Product in a Field

Elementary facts about $\mathbb{N}$ used below — transitivity and totality of $\le$; that $k\le n$ implies $k\le S(n)$ and $S(k)\le S(n)$; that $l<S(m)$ implies $l\le m$; that $m<S(m)$; and that every natural number $l$ with $1<l$ is the successor of a natural number — are those of Order on the Natural Numbers and Properties of the Order on the Natural Numbers, together with the Peano structure of Natural Numbers, in which the successor map $S$ is injective.

Claim 1. The values of $g_{j}$ avoid $j$. If $k<j$ then $g_{j}(k)=k\ne j$. If $j\le k$ then $j\le k<S(k)=g_{j}(k)$, so again $g_{j}(k)\ne j$.

Injectivity. Let $k,k'\in[n]$ with $g_{j}(k)=g_{j}(k')$. If $k<j$ and $k'<j$ then $k=g_{j}(k)=g_{j}(k')=k'$. If $j\le k$ and $j\le k'$ then $S(k)=S(k')$, so $k=k'$ by injectivity of $S$. If $k<j\le k'$ then $g_{j}(k)=k<j\le k'<S(k')=g_{j}(k')$, contradicting equality; the remaining mixed case is symmetric.

Surjectivity onto the complement of $j$. Let $l\in[S(n)]$ with $l\ne j$; by totality, either $l<j$ or $j<l$. If $l<j$ then, since $j\le S(n)$, transitivity gives $l<S(n)$ and hence $l\le n$, so $l\in[n]$ and $g_{j}(l)=l$. If $j<l$ then $1\le j<l$, so $1<l$ and $l=S(k)$ for some natural number $k$; from $S(k)=l\le S(n)$ we get $k\le n$, so $k\in[n]$, and from $j<S(k)$ we get $j\le k$, so $g_{j}(k)=S(k)=l$.

Claims 2 and 3. We prove claim 2. Claim 3 is obtained by the same argument with the addition of $K$ replaced by its multiplication: the only properties of the operation used are commutativity and associativity, which hold for both operations of a field, and the recursion identity of claim 1 of Properties of Finite Sums, whose counterpart for products is claim 1 of Properties of Finite Products.

We argue by induction on $n$, using the induction principle for the natural numbers. Let $\mathcal{P}$ be the set of natural numbers $n$ such that the identity of claim 2 holds for every map $a:[S(n)]\to K$ and every $j\in[S(n)]$.

Base. Let $n=1$, so that $[S(1)]$ consists of $1$ and $S(1)$, and $[1]$ consists of $1$ alone. If $j=S(1)$ then $1<j$, so $g_{j}(1)=1$, and both sides equal $a_{1}+a_{S(1)}$ by claim 1 of Properties of Finite Sums. If $j=1$ then $j\le1$, so $g_{j}(1)=S(1)$, the right-hand side is $a_{S(1)}+a_{1}$ and the left-hand side is $a_{1}+a_{S(1)}$; these agree by commutativity of addition. Hence $1\in\mathcal{P}$.

Step. Suppose $n\in\mathcal{P}$, and let $a:[S(S(n))]\to K$ and $j\in[S(S(n))]$ be given; write $g_{j}$ for the gap map from $[S(n)]$ to $[S(S(n))]$ and $b$ for the restriction of $a$ to $[S(n)]$. By claim 1 of Properties of Finite Sums,

Suppose first that $j=S(S(n))$. For every $k\in[S(n)]$ we have $k\le S(n)<S(S(n))=j$, so $g_{j}(k)=k$ and $a_{g_{j}(k)}=b_{k}$. Hence the right-hand side of claim 2 equals the right-hand side of (i), as required.

Suppose now that $j\ne S(S(n))$, so that $j<S(S(n))$ and therefore $j\in[S(n)]$. Let $h_{j}:[n]\to[S(n)]$ be the gap map formed at level $n$ for this same $j$. For $k\in[n]$ the defining case distinction for $g_{j}$ and for $h_{j}$ is the same, so $g_{j}(k)=h_{j}(k)\in[S(n)]$ and hence $a_{g_{j}(k)}=b_{h_{j}(k)}$. Also $j\le S(n)$ gives $g_{j}(S(n))=S(S(n))$.

By the induction hypothesis applied to $b$ and $j$,

and by claim 1 of Properties of Finite Sums applied to the family $k\mapsto a_{g_{j}(k)}$ on $[S(n)]$,

Substituting the first of these into (i) and regrouping by commutativity and associativity of addition,

which is the identity of claim 2 at level $S(n)$. Hence $S(n)\in\mathcal{P}$, and by induction $\mathcal{P}$ contains every natural number.