Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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

How is it possible to define in a totally rigorous (i.e. from the axioms) was the functions $$h:\mathbb{N}\rightarrow \mathbb{N}, \ n\mapsto 1\cdot\ldots \cdot n$$ or $$ g:\mathbb{N}\rightarrow \mathbb{R}, \ n\mapsto x^n \ $$

without using the recursion theorem , that immediately tells us that these functions exist and are unique ?

Differently said: Do we really need a general statement like the recursion theorem to prove that these two specific functions exist and are unique ? Isn't there an easier proof just for these two functions (I'm thinking of somehow building the sets these functions correspond to directly out of $\mathbb{N}$ and $\mathbb{R}$ via the ZFC axioms, without resorting to the recursion theorem. My naive approach - I never had a course in set theory, so I don't know if this is correct - would be, for example for the second function, to directly build the set $$ \{ (n,r)\in\mathbb{N}\times \mathbb{R} \mid r=x^n \},$$ where $x \in \mathbb{R}$ is some fixed number, via the "axiom schema of separation", which gives me my function $g$, since it is its graph)

Side question: As far as I understood the recursion theorem, the important statement it makes is that these functions are unique (since existence seems to me to already be "given", since one can always define (using the terminology from Wikipedia) a function $F(n):= (f\circ \ldots \circ f)(n)$, where the composition was taken $n$ times, although again I don't really which axioms would let me do that, since this is just my intuition).

share|cite|improve this question
The definition of the set is weird. $n$ is quantified over twice. In one side it says "all $(n,r)$ such that..." and then it says "...exists $n$ ..." and where did $x$ come from? – Asaf Karagila Nov 5 '12 at 18:41
@AsafKaragila I made some changes; hopefully it's correct now. – temo Nov 6 '12 at 8:57
Well, the $x$ is still a free variable... :-) – Asaf Karagila Nov 6 '12 at 8:58
@AsafKaragila I don't understand, is that not allowed ? Isn't that set representing the graph of the function $g$ ? (Please keep in mind, that my background in set theory and related areas is almost nonexistant.) – temo Nov 6 '12 at 9:25
The idea behind defining a set by a formula is that you can verify whether or not an object is in this set by trying to see if it satisfies the formula. Let's try that here, shall we? Okay so we are given $(n,r)\in\mathbb{N\times R}$. Now to see that this pair is in the set we need to show that $x^n=r$. But wait, what is $x$? No one says whether it is a concrete number (fixed beforehand, i.e. a parameter) or is it $\exists x$ or $\forall x$. Each of these results will define a different set. Ambiguity is not good for mathematics... – Asaf Karagila Nov 6 '12 at 9:29
up vote 3 down vote accepted

You're correct, certainly, that showing the existence of the function is (almost trivially) equivalent to showing the existence of the relation - but how do you propose to define the relation '$r=x^n$' (we can even assume $r$ and $x$ integers here - the problem still isn't easy!) in non-recursive fashion? An excellent exercise (which I first found in Hofstadter's Godel, Escher, Bach) is to characterize the predicate '$n$ is a power of $2$' in explicit fashion - note that 'explicit' here means without the use of recursion or iteration (which is, for these purposes, recursion in disguise)! If you're able to get that one, you might try the predicate '$n$ is a power of $10$' - that should go a long way towards showing just how powerful the recursion theorem is as a tool.

In general, I'd be very wary of using 'intuition' to understand these concepts, because logic and axiomatics are one area where your intuition can lead you strongly astray (for instance, look at the Axiom of Choice) and where formal arguments are a necessity. In fact, it would probably be helpful just to find the appropriate formal way to prove the existence of these functions with the recursion theorem: in its most useful form here the theorem formally states that for any number $a$ and function $f(x):\mathbb{N}\to\mathbb{N}$ there's a function $F(x):\mathbb{N}\to\mathbb{N}$ with $F(0) = a$ and $F(n+1) = f(F(n))$.

To understand what can go wrong, it may be worth understanding how the recursion theorem can fail: imagine an abstract system where our notion of 'number' remains the same, and we're given the basic arithmetic operations of addition and multiplication, but the notion of function is restricted to polynomially bounded functions: for each function $f$ there exist constants $k$ and $C$ such that for all $n$, $|f(n)| \le \left|n\right|^k+C$ . Then we can add and multiply these functions and still get totally legitimate functions, and we can even compose these functions to get legitimate functions: if $f(n)$ and $g(n)$ are polynomially bounded, then the function $h$ defined by $h(n) = f(g(n))$ is polynomially bounded. But the recurion theorem (in the form I gave) fails in this setting - can you see why?

share|cite|improve this answer
I’d have said in its simplest useful form: parameters make it substantially more useful! But it’s good enough for your example, which is nice. – Brian M. Scott Nov 5 '12 at 18:00
@BrianM.Scott Fair point - I think I have the parameteric version so internalized that I don't even think about it at this point! Agreed that they're immensely useful, though. – Steven Stadnicki Nov 5 '12 at 19:01
@StevenStadnicki I suppose you mean that the recursion theorem fails in the following way, if I understood it right: If, for example $a=2$ and $f(n):=n^2$ is a polynomially bounded function then the $F$ I get from the recursion theorem isn't polynomially bounded anymore, since it's the tetration function $$\underbrace{2^{2^{2^{\cdots ^ {2}}}}}_{n \text{ times}}.$$But I don't quite understand how this illustrates how this is relevant for my case, since there there aren't functions which grow so fast that the recursion theorem can't capture them, i.e. I don't understand why the failure in [...] – temo Nov 6 '12 at 9:16
[...] the polynomially bounded case illustrates a general feature in which the recursion theorem can fail ? (since it seems natural that if we restrict the functions we are allowed to consider sufficiently, that the recursion theorem will provide us a function that does not lie in this small, restricted set of functions.) – temo Nov 6 '12 at 9:19
@temo The point is that you're not guaranteed the recursion theorem; it can actually be false, based on the axiom system you choose. There are perfectly good (and even mathematically relevant) axiomatizations of the concept of function for which the recursion theorem fails and the function, e.g,, $f(n) = 2^n$ doesn't exist. – Steven Stadnicki Nov 6 '12 at 15:56

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.