Proof of Bijections between Intervals: the Gap Map and the Reversal

Each result cited below is universally quantified over the data in its own statement, and is applied to the data named where it is cited.

Order facts. Expressions are read in $\mathbb{N}_{0}$ as in The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §overloading. The order $\le$ of $\mathbb{N}_{0}$ is a well-order by The Order on Omega Is a Well-Order with Membership as Its Strict Order, and Nothing Lies between n and Its Successor §well-order, hence a total order by Well-Orders on a Set §well-order, and $<$ is its associated strict relation by The Order on Omega Is a Well-Order with Membership as Its Strict Order, and Nothing Lies between n and Its Successor §strict. Let $u,v,w\in\mathbb{N}_{0}$. We use:

(O1) exactly one of $u<v$, $u=v$ and $v<u$ holds, by Uniqueness of Least and Greatest Elements, Properties of the Strict Order, and Trichotomy for Total Orders §trichotomy; $u\le v$ if and only if $u<v$ or $u=v$, by Uniqueness of Least and Greatest Elements, Properties of the Strict Order, and Trichotomy for Total Orders §weak-strict; $u<v$ implies $u\neq v$, by Uniqueness of Least and Greatest Elements, Properties of the Strict Order, and Trichotomy for Total Orders §strict-characterization; and if $u<v$ and $v<w$ then $u<w$, by Uniqueness of Least and Greatest Elements, Properties of the Strict Order, and Trichotomy for Total Orders §strict-transitive. In particular, if $u<v$ and $v\le w$, or $u\le v$ and $v<w$, then $u<w$, by the second and fourth of these.

(O2) $u<v+1$ if and only if $u\le v$, and $v<v+1$: by The Order on Omega Is a Well-Order with Membership as Its Strict Order, and Nothing Lies between n and Its Successor §successor, applied to $m=u$ and $n=v$, with $S(v)=v+1$ 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 §plus-one.

(O3) $u\le v$ if and only if $u+1\le v+1$, and $u<v$ if and only if $u+1<v+1$: by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §order, applied to $1$, $u$ and $v$ in place of $k$, $m$ and $n$, together with Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §commutative.

(O4) For $n\in\mathbb{N}_{0}$ and $u\in\mathbb{N}_{0}$: $u\in[n]$ if and only if $u\in\mathbb{N}$ and $u\le n$, since $[n]=\{k\in\mathbb{N}:k\le n\}$ by Intervals of Natural Numbers: Initial Segments, Adding One Element, Splitting and Shifting §segment.

Clause gap. Let $n\in\mathbb{N}_{0}$ and $j\in[n+1]$; by (O4), $j\in\mathbb{N}$ and $j\le n+1$. Let $B=[n+1]\setminus\{j\}$, a set by Sets and Maps: Ordinary Notation §sets. We apply Maps Defined by Cases §cases to $A=[n]$, this $B$, the property $P(k)$: $k<j$, and the expressions $t_{1}(k)=k$ and $t_{2}(k)=k+1$; its hypotheses hold as follows. Let $k\in[n]$, so $k\in\mathbb{N}$ and $k\le n$ by (O4).

If $k<j$: since $k\le n$ and $n<n+1$ by (O2), $k<n+1$ by (O1), so $k\le n+1$ by (O1) and $k\in[n+1]$ by (O4); and $k\neq j$ by (O1). So $t_{1}(k)=k\in B$.

If not $k<j$: then $k=j$ or $j<k$ by (O1), that is, $j\le k$. Now $k+1\in\mathbb{N}$ 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 §closed, and $k+1\le n+1$ by (O3), so $k+1\in[n+1]$ by (O4); and $j<k+1$ by (O2), so $k+1\neq j$ by (O1). So $t_{2}(k)=k+1\in B$.

Hence Maps Defined by Cases §cases gives exactly one map $g_{j}:[n]\to B$ with $g_{j}(k)=k$ for $k<j$ and $g_{j}(k)=k+1$ for the other $k\in[n]$, which by (O1) are those with $k\ge j$; this is the map $g_{j}$ of the statement.

$g_{j}$ preserves $<$. Let $k,k'\in[n]$ with $k<k'$. If $k'<j$, then $k<j$ by (O1), and $g_{j}(k)=k<k'=g_{j}(k')$. If $k<j$ and not $k'<j$, then $g_{j}(k)=k<k'$ and $k'<k'+1=g_{j}(k')$ by (O2), so $g_{j}(k)<g_{j}(k')$ by (O1). If not $k<j$, then $j\le k$ as above, so $j<k'$ by (O1) and hence not $k'<j$ by (O1); thus $g_{j}(k)=k+1<k'+1=g_{j}(k')$ by (O3). These cases are exhaustive.

$g_{j}$ is injective. Let $k,k'\in[n]$ with $k\neq k'$. By (O1), $k<k'$ or $k'<k$, so $g_{j}(k)<g_{j}(k')$ or $g_{j}(k')<g_{j}(k)$ by the previous paragraph, and in either case $g_{j}(k)\neq g_{j}(k')$ by (O1). So $g_{j}$ is injective by Injective, Surjective and Bijective Functions between Classes §injective.

$g_{j}$ is surjective. Let $m\in B$; so $m\in\mathbb{N}$, $m\le n+1$ by (O4), and $m\neq j$, whence $m<j$ or $j<m$ by (O1).

If $m<j$: as $j\le n+1$, $m<n+1$ by (O1), so $m\le n$ by (O2), and $m\in[n]$ by (O4); since $m<j$, $g_{j}(m)=m$.

If $j<m$: by Arithmetic and Order of the Natural Numbers §least, applied to $a=j$, $1\le j$, so $1<m$ by (O1) and $m\neq1$ by (O1). By Arithmetic and Order of the Natural Numbers §predecessor, applied to $a=m$, there is $k\in\mathbb{N}$ with $m=k+1$. From $j<k+1$, $j\le k$ by (O2), so not $k<j$ by (O1). From $k+1=m\le n+1$, $k\le n$ by (O3), so $k\in[n]$ by (O4). Hence $g_{j}(k)=k+1=m$.

So $g_{j}$ is surjective by Injective, Surjective and Bijective Functions between Classes §surjective, and a bijection from $[n]$ onto $[n+1]\setminus\{j\}$ by Injective, Surjective and Bijective Functions between Classes §bijective.

Clause reversal. Let $N\in\mathbb{N}$ and $a\in[N]$; so $a\in\mathbb{N}$ and $a\le N$ by (O4). As $N<N+1$ by (O2), $a<N+1$ by (O1), hence $a\le N+1$ by (O1). By The Difference of Two Natural Numbers with Zero §difference, applied to $m=a$ and $n=N+1$, the difference $N+1-a$ is the unique $j\in\mathbb{N}_{0}$ with $a+j=N+1$.

$N+1-a\in[N]$. Let $j=N+1-a$. If $j=0$, then $N+1=a+0=a$ by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §zero, contradicting $a<N+1$ by (O1); so $j\neq0$ and $j\in\mathbb{N}_{0}\setminus\{0\}=\mathbb{N}$ (The Natural Numbers and the Natural Numbers with Zero: Arithmetic, Order, Induction and Recursion §sets). By Arithmetic and Order of the Natural Numbers §least, applied to $a$, $1\le a$, so by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §order, applied to $j$, $1$ and $a$ in place of $k$, $m$ and $n$, $j+1\le j+a$; and $j+a=a+j=N+1$ by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §commutative. So $j+1\le N+1$, whence $j\le N$ by (O3), and $j\in[N]$ by (O4).

Hence, by Sets and Maps: Ordinary Notation §maps, $r:[N]\to[N]$, $r(a)=N+1-a$, is a map.

$r\circ r=\mathrm{id}_{[N]}$. Let $a\in[N]$ and $j=r(a)$, so $a+j=N+1$. By The Difference of Two Natural Numbers with Zero §difference, applied to $m=j$ and $n=N+1$, $r(j)=N+1-j$ is the unique $i\in\mathbb{N}_{0}$ with $j+i=N+1$; and $i=a$ satisfies this, as $j+a=a+j=N+1$ by Arithmetic of Addition on Omega: Recursion Rules, Associativity, Commutativity, Cancellation and Compatibility with the Order §commutative. So $r(r(a))=a$. By Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §composition, applied to $F=G=r$, $r\circ r$ is a map from $[N]$ to $[N]$ with $(r\circ r)(a)=r(r(a))=a$, and $\mathrm{id}_{[N]}(a)=a$ by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §identity. Both maps have domain $[N]$ and equal values, so $r\circ r=\mathrm{id}_{[N]}$ by Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §equality.

By Basic Properties of Functions: Equality, Composition, Identity, Inverse and Restriction §inverse-criterion, applied to $F=r$ and $G=r$ with $A=B=[N]$, $r$ is bijective and $r=r^{-1}$: $a\mapsto N+1-a$ is a bijection from $[N]$ onto $[N]$ and is its own inverse.