Question

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?

Answer 1

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$.

Answer 2

It depends what "express in terms of" means. Are the following allowed?

$$S(x)=x+f_1(f_4(x)),$$ $$Pd(x)=x-f_1(f_4(x)).$$ Or perhaps something like: $$S(x)=f_2(f_4(x)+f_1(f_4(x))).$$

Answer 3

As I recall from reading and classes in mathematical logic, the natural numbers are "defined"--postulated might be a better word--more or less as follows:

A.) There is a set $N$;

B.) $N$ has a "preferred element" called $0$;

C.) There is a function $s:N \to N$, such that i.) $0$ is not in the range of $s$; ii.) every $n \in N$, $n \ne 0$, is in the range of $s$; $s$ is injective, meaning $s(n) = s(m)$ implies $n = m$.

D.) The principal of mathematical induction holds: if for a "statment" $P(n)$ depending on $n$ (I'm not going into the fully nuanced logical definition of a proposition containing a variable here.) $P(0)$ holds and "$P(n)$ implies $P(s(n))$" holds, $P(n)$ holds for all $n \in N$.

The equation $s(n) = n + 1$ then just defines a shorthand for $s(n)$. From this point of view, taking your functions as definitive is complicated, since for example we don't even know what "even" and "odd" mean at this point in the logical development, much less $quot(x, 2)$ (by which I assume you mean the quotient of $x$ divided by $2$). To set up a system for the natural numbers using your functions seems a lot more complex than the above (which I believe is Peano's) formulation. For example, you'd have to postulate $N$ as being decomposable into two sets (the evens and the odds), and postulate the relationship between them, and then figure out how to axiomatize $2x$ etc. From the Peano axioms, all this stuff can be defined and/or proved in a relatively straightforward way. Finally, I don't readily see how you would talk about the relationship between the evens and the odds without using something which for all the world looks an awful lot like $s(n)$. Also worth noting is that your expression for $s(x)$ really involves a conditional (is $x$ even or odd?), whereas the standard postulate does not.

Response to Ryan Budney's comment: it seems to me that Tim's use of the term $S(x)$ indicates a context of the successor function from Peano arithmetic, whence his use of the word "define" in the title, though "axiomatize" or "postulate" might be more on point.

Response to Yemon Choi's comment: "generate" might be what Tim wants to do, but he gives no starting point, leaving the question "generate from what?" hanging.