MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
It's not clear to me what your question title has to do with the contents. – Ryan Budney Nov 28 '10 at 18:52
@Ryan: perhaps Tim means "generate" rather than "define" – Yemon Choi Nov 28 '10 at 19:05
what's x\dot{-}1? – Federico Poloni Nov 28 '10 at 20:18
@Federico: $x\dot{-}1=x-1$ if $x\ge1$ and $0\dot{-}1=0$. This is the predecessor function for natural numbers. – Guillaume Brunerie Nov 28 '10 at 20:22
I see 4 votes to close and no comments in support of closure. – Gerry Myerson Nov 28 '10 at 23:02
up vote 5 down vote accepted

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

share|cite|improve this answer

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

share|cite|improve this answer
These are expressed in terms of $f_1,\dots,f_4$ and $+$ and $-$, which is presumably not what is requested. – Gerald Edgar Nov 28 '10 at 20:52

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.

share|cite|improve this answer
@Michael Renardy: yes, Tim's definition of $f_{1}$ seems like something from computer programming, doesn't it? A conditionally executed function . . . – drbobmeister Nov 28 '10 at 20:23

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.