For $\alpha,\beta\in \omega$ we set the *absolute difference* of $\alpha,\beta$ to be $$\lVert\alpha - \beta\rVert := |(\alpha\setminus\beta)\cup (\beta\setminus\alpha)|.$$ The absolute difference $\lVert g - h \lVert$ of two functions $g,h:\omega\to\omega$ is defined by $\lVert g - h \rVert (n) = \lVert(g(n) - h(n)\rVert$ for all $n\in \omega$.


**Question.** Are there bijections $\varphi\_{1,2}:\omega\to\omega$ such that $\lVert \varphi\_1 - \varphi\_2\rVert$ is again a bijection?



Can the absolute difference of bijections on $\omega$ also be a bijection?
Define two sequences $a\_n$ and $b\_n$ as follows:


1. $a\_0=b\_0=0 $
2. $a\_{2n+1}$ is the smallest positive integer not in $\{a\_0,\ldots, a\_{2n}\}$.
3. $b\_{2n+1}=a\_{2n+1}+2n+1$
4. $b\_{2n}$ is the smallest positive integer not in $\{b\_0,\ldots, b\_{2n-1}\}$.
5. $a\_{2n}=b\_{2n}+2n$.


Then by (2) the sequence $a$ viewed as a function from $\omega$ to $\omega$ is surjective, and likewise by (4) the sequence $b$ is surjective.


Also by (2) we have the inequalities $n \le a\_{2n+1} \le 2n+1$ and by (4) we have the inequalities $n \le b\_{2n} \le 2n$, so $b\_{2n+1} \ge 3n+1 > b\_{2n}$ and $a\_{2n} \ge 3n \ge a\_{2n-1}$. Furthermore both the even and odd subsequences of $a\_n$ and $b\_n$ are easily seen to be strictly increasing. Together this shows that $a$ and $b$ viewed as functions are injective.


So $a$ and $b$ are bijections and their difference is the identity function.


