5
$\begingroup$
  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!

2 Answers 2

5

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.

  • 0
    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?2011-01-11
  • 1
    @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.2011-01-11
  • 0
    Thanks! Questions: (1) I don't know how to formalize "a set to be able to define recursively", but this may give you some idea http://en.wikipedia.org/wiki/Recursive_definition . (2) Is "recursively enumerable" defined in terms of Turing machine different from the one implied in your last sentence "you can always do similar "cheats" like the one above for any given set"? I suspect this because not every subset of N is "recursively enumerable" as you said. (3) Two "recursively enumerable" subsets of N can not share the same Turing machine? Does a Turing machine always output the same string?2011-01-11
  • 1
    (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.2011-01-11
  • 0
    Thanks! A little confused as to (2). Isn't any set defined with some description? I thought the membership of any set is defined in terms of a predicate, and the predicate provides description for the set?2011-01-11
  • 1
    @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"2011-01-11
  • 0
    Thanks! Does "there are only countably many predicates you can actually write down" apply for any set or just for any subset of N?2011-01-11
  • 1
    @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.2011-01-11
  • 0
    Thanks! I think I just found what I mean by "recursive definition for a set" here http://en.wikipedia.org/wiki/Definition#Recursive_definitions2011-01-11
  • 0
    I doubt that a set qualified for recursive definition (link given in last comment) and a recursively enumerable set are the same concept. A recursively enumerable set is a set of natural numbers, so it is countable. Ordinal numbers are defined recursively/inductively, if I am correct, and there are ordinal numbers that are uncountable sets themselves. Am I wrong?2011-01-11
  • 0
    @Tim: no, you are not wrong. You can do recursion on any well-ordered set, and there are certainly well-ordered sets that are uncountable (and for which you can describe the well-ordering without using AC). My general point is that if you restrict yourself to subsets of $\mathbb{N}$, then any set that can be "recursively defined" is recursively enumerable; I suspect that the notion that you are after when you speak generally (i.e., not formally) about being able to define a set "recursively" is, at least for subsets of $\mathbb{N}$, equivalent to recursively enumerable; but I could be wrong.2011-01-12
  • 0
    Thanks! So to recursively define any well-ordered set, is it to first find a bijective mapping f from the set to itself that the mapped element of any element is not the element itself (how to I don't know), then recursively define f following the similar way you gave for f and g?2011-01-12
  • 0
    @Tim: You are conflating and confusing notions. On the one hand there is the *formal* notion of recursively defined function whose domain is a *well-ordered set*; that's one thing. A second notion is the informal notion you are trying to home-in to of "define a set recursively". *This* notion is not formal, you are just trying to play with it informally. I'm **guessing** that the kind of thing *you* would call "recursively defined set" will, for subsets of $\mathbb{N}$, coincide with the *formal* notion of "recursively enumerable". But that's a *guess*. As to your comment, I am completely lost2011-01-12
  • 0
    You are right about what I mean for recursively defining a general set (not just a set of natural numbers), and I got your point but didn't expect that I made you lost. So how do you recursively define an arbitrary well-ordered set? Do you use the way you recursively define a function on a well-ordered set?2011-01-12
  • 0
    @Tim: I'm lost because nowhere did I talk about "recursively define a well-ordered set". I talked about well-ordered sets when talking about defining *functions* recursively (their domain must be a well-ordered set). And I talked about subsets *being* or *not being* recursively enumerable. I don't know what you mean when you talk about "recursively define any well-ordered set." This is outside what I was refering to.2011-01-12
  • 0
    By "recursively define a set", I mean like this http://en.wikipedia.org/wiki/Definition#Recursive_definitions :"Normally this consists of three steps: At least one thing is stated to be a member of the set being defined; this is sometimes called a "base set". All things bearing a certain relation to other members of the set are also to count as members of the set. It is this step that makes the definition recursive. All other things are excluded from the set". I think it does not only talk about a set of natural numbers?2011-01-12
  • 0
    @Tim: This is an **informal** description of a general idea, not a formal definition. At best, you could try to do something along the lines of the Recursion Theorem, with the set you are trying to define being a subset of $X$ given by the images of the function $U$, with the notion of the "process" corresponding to "steps" being indexed by the well-ordered set $X$. But you have to **start** with a well-ordered set and a "target" to begin with; you can't just do it willy-nilly about arbitrary "objects" with arbitrary "certain relations", lest you run into all sorts of antinomies.2011-01-12
  • 0
    If I am right, Von Neumann definition of ordinals must be an example of formally and recursively defining a set which is not a set of natural numbers: "each ordinal is the well-ordered set of all smaller ordinals." quoted from http://en.wikipedia.org/wiki/Ordinal_number#Von_Neumann_definition_of_ordinals .2011-01-12
  • 0
    @Tim: You know what? We're talking at cross-purposes and within the limiting context of comments. Nowhere did I mean to say that it could **not** be done except for subset of $\mathbb{N}$, I was discussing what I thought it would mean **within** that context (without restricting it to outside of it). It seems to me now that it is entirely possible that I have completely misunderstood what you are going at, and there seems to be little for me to add to what I have already said if this is not the case. And if it *is* the case, then nothing I said makes sense.2011-01-12
2

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