Is it possible to express the functions $S(x)=x+1$ and $Pd(x)=x\dot{-}1$ in terms of the functions $f\_1$, $f\_2$, $f\_3$ and $f\_4$, where $f\_1(x)=0$ if $x$ is even or $1$ if $x$ is odd, $f\_2(x)=\mbox{quot}(x,2)$, $f\_3(x)=2x$ and $f\_4(x)=2x+1$? For example, $S(x)=f\_4(f\_2(x))$ if x is even. Is there a similar formula if $x$ is odd?



Other ways to define naturals
I assume that the problem is: does there exists a sequence $(u\_1,\dots,u\_n)\in{}\{1,2,3,4\}$ such that for all $x\in\mathbb{N}$, $S(x) = f\_{u\_n}(\dots (f\_{u\_1}(x))\dots)$ (and similarly for $Pd$)


Let’s prove by induction on $n$ that every such function either is of the form $f(x)=2^kx+l$ where $k\ge 0$ and $0\le l<2^k$ or $f(2)=f(3)$ or the image of $f$ contains only two elements.


If there is an $f\_1$ somewhere, then the image of $f$ contains only two elements, and this is preserved by composition. We suppose now that there is no $f\_1$.


* If $n=0$, $f(x) = x$ ok.
* If $f(2)=f(3)$ then $f\_i(f(2)) = f\_i(f(3))$
* If $f(x) = 2^kx+l$, $f\_3\circ f$ and $f\_4\circ f$ are of the form $2^{k+1}x+l'$ with $0\le l'< 2^{k+1}$, and $f\_2\circ f$ is also of the same form if $k\ge 1$, and if $k=0$ we have $f\_2(f(3))=f\_2(f(2))=1$.


This proves that neither $S$ nor $Pd$ can be written as a composition of the functions $f\_i$.


