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
  1. I was wondering about what is the general definition of a recursive mapping between any two sets.
  2. Is there a condition for a mapping to be able to be written in recursive form? Is the following claim true:

    A mapping can be represented recursively if and only if its domain is a set that can be defined recursively?

Thanks and regards!

share|cite|improve this question
up vote 5 down vote accepted

Essentially, for you to be able to give a function recursively the domain must be well-ordered. And it all depends on what you mean by "recursive mapping"; see below.

A partial oder $\preceq$ on a set $X$ is a well-order if and only if every nonempty subset of $X$ has a least element under the relation $\preceq$. Assuming the Axiom of Choice, every set can be well-ordered, but these well-orders may not be explicit or constructive.

The following is from Halmos's Naive Set Theory (Chapter 18: Transfinite Recursion):

If $(W,\preceq)$ is a well-ordered set, and $X$ is an arbitrary set, a sequence of type $a$ in $X$ means a function from the initial segment of $a$ in $W$, $\{w\in W\mid w\prec a\}$, to $X$.

A sequence function of type $W$ in $X$ is a function $f$ whose domain is all sequences of type $a$ in $X$, for all $a\in W$, and whose range is contained in $X$; essentially, a "sequence function" tells you how to lengthen a sequence.

Transfinite Recursion Theorem. If $(W,\preceq)$ is a well-ordered set, and if $f$ is a sequence function of type $W$ in a set $X$, then there exists a unique function $U\colon W\to X$ such that $U(a) = f(U|_{i(a)})$ for each $a\in W$, where $i(a)=\{ w\in W\mid w\prec a\}$ is the initial segment determined by $a$ in $W$.

The theorem tells you that you can define a function recursively on a well-ordered set (with a given well order).

Now, when can a function be defined recursively? In a sense, always if your domain is well-ordered. To see why, consider the case of $\mathbb{N}$ first.

Suppose you have an arbitrary function $f\colon\mathbb{N}\to X$. Let $g\colon \mathbb{N}\times X\to X$ be a function defined as follows: fix $x_0\in X$; then $$g(n,x) = \left\{\begin{array}{ll} f(n+1) &\text{if $f(n)=x$;}\\ x_0 &\text{if $f(n)\neq x$.} \end{array}\right.$$ Then we have $f(n+1) = g(n,f(n))$, so that $f$ is defined "recursively". This can be done with any function, so every function with domain $\mathbb{N}$ can be defined "recursively" this way.

Similar constructions hold for an arbitrary well-ordered set.

You might say, "but you're cheating! you start with $f$ and you determine $g$ from it". Well, yes; but if you were walking on the street and you found $g$ lying on the corner, and didn't know where it came from, you would still be able to use it to define a function. This tells you that there is always a way of writing $f$ recursively, even if it is a bit silly in the grand scheme of things. The problem is that we have no good way of distinguishing "silly ways" and "real ways", other than the way that Justice Potter Stewart was able to tell what was and what was not pornography: we know it when we see it.

share|cite|improve this answer
Thanks for bringing up such fundamental theorem! May I ask if there is any condition for a set to be able to define recursively? If there is, is the condition for a recursive set related to that for a recursive mapping? – Tim Jan 11 '11 at 16:42
@Tim: A subset of the natural numbers is "recursively enumerable" if there is a Turing machine that will produce a list of all elements of the set (the list may be infinite). There are uncountably many subsets of the natural numbers, but only countably many recursively enumerable ones (since there are only countably many Turing machines), so there are lots of sets that are not recursively enumerable; I suspect that this is the notion you are really after when you say "be able to define [the set] recursively." Of course, you can always do similar "cheats" like the one above for any given set. – Arturo Magidin Jan 11 '11 at 16:47
(1) All examples of subsets of $\mathbb{N}$ given in that page are recursively enumerable, but absent a formal definition, proving an equivalence would be impossible. But any function with domain $\mathbb{N}$ and where the value at $n$ depends via some formula from the value at all $a\lt n$ can be modeled by a Turing machine; (2) notice I italized "given". If you are given a set, then you must have some kind of description for it; assuming Turing's Thesis, this description lets you set up the Turing machine. (3) Each recursively enumerable subset has its own TM; TMs are deterministic. – Arturo Magidin Jan 11 '11 at 17:02
@Tim: There are only countably many predicates you can actually write down (or even possible at all with a countable alphabet), but there are uncountably many subsets of $\mathbb{N}$; in a sense, this is what is behind Goedel's "Constructible Universe", which only considers sets that can actually be described. There is in fact an important difference between "you are given $X$" and "$X$ exists". E.g., that a countable union of countable sets is countable requires AC; but if you are given the sets with a surjection from $\mathbb{N}$, then you don't need AC. PS "Turing's Thesis"->"Church's" – Arturo Magidin Jan 11 '11 at 17:21
@Tim: A predicte is a finite sequence of symbols which satisfies certain properties; if the collection of possible symbols has cardinality $\kappa$, then the set of all finite sequences of such symbols has cardinality $\aleph_0\kappa$. In particular, our usual alphabet is countably infinite, so there are only $\aleph_0$ possible sequence of symbols, hence only $\aleph_0$ possible predicates. – Arturo Magidin Jan 11 '11 at 17:35

I am not sure of the context of your question, but for many decades the subject now known as computability theory was known as recursion theory, from the time of Goedel and Turing up to the mid 1990s. The recursion theory terminology grew out of the historical fact that the class of computable functions was first defined in terms of the closure of a simple set of functions under composition and recursion (giving the primitive recursive functions) and then also under the unbounded search operator (which then gives the full class of recursive functions or computable functions). Thus, a function $f$ is recursive if it is in this class. But of course, it was soon realized that this is equivalent to it being computable by a Turing machine or computable by any of the other equivalent notions of compubility, and so the subject was really about the class now known as the computable functions. Mathematicians similarly would say that a set $A$ is recursive if the characteristic function of the set is a recursive function (which is to say, if it is computable), but we now say that such a set is decidable or that it is computable. The recursively enumerable or r.e. sets were those that are the range of a recursive function, but we now call these the computably enumerable or c.e. sets.

There was a remarkable development in the mid-to-late 1990's, when Bob Soare mounted an against-the-odds effort to rename the subject of Recursion Theory to be Computability theory. (Imagine trying to rename a major area of scientific inquiry!) The main argument was that the subject was not actually about recursion at all, but about computability at its heart. And although there was huge or even overwhelming as well as mocking opposition at first, nowadays almost everyone says comptubility theory---Soare completely won the war---and only the old die-hards still use the old recursion theory terminology.

But this could be what you are talking about. That is, a recursive mapping between two mathematical structures would simply mean what we would now call a computable function between them, in the old recursion theoretic terminology of computability theory. (But "old" is relative here, since people used this terminology quite a lot even 15 years ago.)

share|cite|improve this answer

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.