= Sparse-shift bijection between nonnegative and positive integers
{title2=$A=\{2^{k+1}-2:k\in\mathbb N\}$}
Take $X=\{0,1,2,\ldots\}$, the <nonnegative integers>, and $Y=\{1,2,3,\ldots\}$, the <positive integers>. Choose the <injections>
$$
f:X\to Y,\qquad f(n)=2n+2,
\qquad
g:Y\to X,\qquad g(m)=m.
$$
Here $g$ is an <inclusion map>, while $f$ reaches only the positive <even integers>. In particular, $f$ is not a <bijection>: it misses every positive <odd integer>. Simply using the <inverse function> of $g$ on its <image> misses input zero.
The remedy is to follow the alternating <injections> starting at the missing input zero:
$$
0_X\mathrel{\mathop{\longrightarrow}^{f}}2_Y
\mathrel{\mathop{\longrightarrow}^{g}}2_X
\mathrel{\mathop{\longrightarrow}^{f}}6_Y
\mathrel{\mathop{\longrightarrow}^{g}}6_X
\mathrel{\mathop{\longrightarrow}^{f}}14_Y
\mathrel{\mathop{\longrightarrow}^{g}}14_X\longrightarrow\cdots.
$$
The subscripts distinguish an input in $X$ from an output in $Y$, even when their numerical values agree. The resulting <subset> of $X$ is $A=\{0,2,6,14,30,\ldots\}$. Its <sequence> of members satisfies $a_0=0$ and $a_{k+1}=2a_k+2$, giving $a_k=2^{k+1}-2$ by <mathematical induction>. Define the <function>
$$
h(n)=\begin{cases}
2n+2,&n\in A,\\
n,&n\in X\setminus A.
\end{cases}
$$
\Image[/nonnegative-positive-integer-injection-chain.png]
{title=A <bijection> moves only the <sequence> $0,2,6,14,\ldots$}
{description=The upper row alternates the original <injections> $f$ and $g$. Solid blue arrows are the chosen <bijection> $h=f$ on $A$; dashed gray arrows only continue the chain. Below, examples outside $A$ use $h=g^{-1}$ and keep their numerical values. Every displayed number belongs to the explicitly constructed example.}
The <image> $h(A)=\{2,6,14,30,\ldots\}=A\setminus\{0\}$ covers all the positive members of $A$ exactly once. The other inputs cover $Y\setminus A$ exactly once by staying fixed. These output <sets> are disjoint and their <union> is $Y$, proving that $h$ is a <bijection>. In particular, $h(0)=2$, $h(2)=6$, $h(6)=14$, while $h(1)=1$ and $h(4)=4$.
For completeness, its <inverse function> is
$$
h^{-1}(m)=\begin{cases}
(m-2)/2,&m\in A\setminus\{0\},\\
m,&m\in Y\setminus A.
\end{cases}
$$
The familiar <bijection> $n\mapsto n+1$ also works, but this example shows something more specific: the two chosen <injections> can repair the missing zero by moving only a sparse <sequence> of inputs. The repair never has to shift the entire <set>.
Back to article page
