Understanding the recursion theorem

[martijnh]

Hi all,

Im doing some self study in set theory, but got kind of stuck with a proof my textbook gives about the so called recursion theorem:

Theorem:
Let a be a set, and let \phi: a^{\mathbb{N}}\rightarrowa^{\mathbb{N}} be a function such that for every natural number n, if f, g \ina^{\mathbb{N}} are such that f|_n = g|_n, then \phi(f)(n) = \phi(g)(n). Then \phi has a unique fixpoint L_\phi \in a^{\mathbb{N}}, which means that \phi (L_\phi ) = L_\phi . Consider the function \phi_n : a^{n}\rightarrowa which evaluates to \phi_n(g) = \phi(g*)(n). Then we have

L_\phi (0) = \phi₀(!:0\rightarrowa)

L_\phi (n⁺) = \phi_n+(L_\phi |_n+)

What I get from this is:
Let \phi be a function that maps the result of a function that maps natural numbers to the set a, to the result of another function that does the same.

If you'd pick two functions from the function set a^{\mathbb{N}} and these return the same result for an element n, then the set of functions \phi would yield the same given f or g using n as input.

They then continue to use this to show there is a so called fixpoint in the set of functions \phi which yields itself given itself as input to \phi. But I don't see how this follows from the facts described above...


Then they go on proving there can be only one such a fixpoint in the set of functions \phi, but this makes even less sense to me:

Proof:
There is at most one such fixpoint. In fact, let L and M be two such fixpoints \phi(L) = L and \phi(M) = M, and suppose that they are different. Then there is a smallest value n₀ such that L(n₀) ≠ M(n₀). This means that L|_n0 = M|_n0. But then \phi(L)(n₀) = \phi(M)(n₀), a contradiction. So there is at most one such fixpoint. For every n \in \mathbb{N}, let S(n) \subset aⁿ be the set of those functions f: n \rightarrow a such that for all m \in n, f(m) = \phi_m(f|_m). Clearly, either S(n) is empty or S(n) contains precisely one function g_n. The set S(0) is not empty. Let N⁺ be the smallest natural number such that S(N⁺) is empty. We may define a function h: N⁺ \rightarrow a by h|_N = g_N and h(N) = \phi_N(h|_N). But this is a function in S(N⁺), so every S(n) is non-empty. Now define L(n) = g_n+(n). Clearly, this function is our candidate for a fixpoint: To begin with, if n < m, then evidently, by the uniqueness of the elements of S(n), g(m)|_n = g(n). Therefore, L|_n = g_n for all n. And L is a fixpoint, in fact: L(n) = g_n+(n) = \phi(g_n+|_n) = \phi_n(g_n) = \phi(g^{*}_{n})(n) = \phi(L)(n) since L|_n = g_n = g^{*}_{n}|_n. The claimed formula then follows by construction.

I was hoping someone could explain this theorem and proof in a somewhat less abstract fashion and maybe point out flaws in my reasoning?

Any help is greatly appreciated!

Thanks!

Martijn

 

[AKG]

What I get from this is:
Let \phi be a function that maps [STRIKE]the result of[/STRIKE] a function that maps natural numbers to the set a, to [STRIKE]the result of[/STRIKE] another function that does the same.

If you'd pick two functions, say f and g, from the function set a^{\mathbb{N}} and these return the same results for [STRIKE]an element n[/STRIKE] all inputs 0 through n-1 inclusive (i.e. f(0) = g(0), ..., f(n-1) = g(n-1)), then the [STRIKE]set of[/STRIKE] functions \phi would yield, namely \phi(f) and \phi(g) [STRIKE]the same given f or g using n as input.[/STRIKE] return the same result on input n (i.e. \phi(f)(n) = \phi(g)(n)).

They then [STRIKE]continue to use this to show[/STRIKE] assume that if \phi is some arbitrary map of functions satisfying the above property, then there is a so called fixed point in the set of functions which yields itself given itself as input to \phi. But I don't see how this follows from the facts described above.

They construct the fixed point of \phi. They call this fixed point L_0, and they give you a recursive definition of this function, although admittedly their description is a bit confusing because it involves this intermediate definition of the functions \phi_n. Let's make sure you understand the basics first before understanding the construction of L_0. I.e. make sure you understand what I've written above, the corrections and additions to your statements. Be especially clear about the fact that a^{\mathbb{N}} is a set of functions, and a function a^{\mathbb{N}}\to a^{\mathbb{N}} is a function whose inputs and outputs are functions! Meaning whole functions are being treated as individual objects, which can serve as inputs and outputs of yet other functions. You should also be clear that the \phi in the statement of the theorem is not a particular function \phi. Rather, it says that if \phi is any function of functions which has a particular nice property, then it has a unique fixed point.

 

[martijnh]

Thank you very much, that certainly helped!

So the corrected line of thinking should be; If there are two functions in a set of functions which return the same results for input restricted up to n, then the set of functions yield the same result on either f(n) or g(n).

I think I get the statement of the theorem; Given a set of functions there exist at most one input (a function) on the set of functions that yields this same input (the same function). And I think I understand the proof by contradication they provide to show there can be only 1 such function.

But I'm still lost in the details:
L_\phi(n⁺) maps n+ to a
\phi_n+ is the set of functions that map n+ to a
L_\phi|_n+ is the set of results of L_\phi from 0 up to n

So how can L_\phi(n⁺) be equal to \phi_n+(L_\phi|_n+) ?

Thanks again!

Martijn

 

[SteveL27]

Thank you very much, that certainly helped!

So the corrected line of thinking should be; If there are two functions in a set of functions which return the same results for input restricted up to n, then the set of functions yield the same result on either f(n) or g(n).

You might find it helpful to visualize a function from N->X is a sequence of elements of X. That let's you see more clearly what they're getting at.

 

[martijnh]

You might find it helpful to visualize a function from N->X is a sequence of elements of X. That let's you see more clearly what they're getting at.

Hmmm if I'd simplify the case and substitute the set of functions by a function that maps \mathbb{N} to \mathbb{N}, and the function inputs f & g by elements from \mathbb{N}... it would basically say something very trivial; a function maps each input to one output, so if the input equals the output, that would be the fixpoint??

 

[AKG]

Hmmm, what you're saying definitely isn't right. You're not mentioning \phi at all.

We've got our set of natural numbers \mathbb{N} = \{ 0, 1, 2, \dots \}. And then we've got some other random set a. Now we can talk about functions from \mathbb{N} to a. We can imagine the collection of all such functions, and we call said collection a^{\mathbb{N}}. If f\in a^{\mathbb{N}}, then f inputs natural numbers n, and outputs something f(n) \in a.

Next, we can think about these sort of monster functions, which eat up entire functions as input (i.e. their inputs are not merely numbers, but entire functions), and spit out entire functions. We're interested now in talking about monsters \phi which input elements in a^{\mathbb{N}} and output elements in a^{\mathbb{N}}.

\phi \in \left(a^{\mathbb{N}}\right)^{a^{\mathbb{N}}}

or, equivalently:

\phi : a^{\mathbb{N}} \to a^{\mathbb{N}}

But we're not interested in any old \phi. We're only interested in a certain kind of \phi, those that have a certain nice property. The Recursion Theorem says that if \phi is any monster which has some particular nice property, then \phi has a "fixed point," namely some input f such that \phi(f) = f.

\forall \phi \in \left(a^{\mathbb{N}}\right)^{a^{\mathbb{N}}}\ \ \left(\phi\mbox{ nice }\Rightarrow \exists f \in a^{\mathbb{N}} : \phi(f) = f\right)

The first question is, what is this "nice property?" We'll say \phi is nice if for any two functions f,g\in a^{\mathbb{N}}, if it so happens that for some n\in\mathbb{N}

f(0) = g(0), f(1) = g(1), \dots, f(n-1) = g(n-1)

(i.e. f and g "agree up to n") then when the monster eats up f and g, the resulting functions it spits out "agree at n), i.e. \phi(f) (n) = \phi(g) (n).

Definition: For \phi : a^{\mathbb{N}} \to a^{\mathbb{N}}, we say \phi is "nice" iff:

\forall f,g\in a^{\mathbb{N}} \forall n \in \mathbb{N} \left [\left(f(0) = g(0), \dots , f(n-1) = g(n-1)\right) \Rightarrow \phi(f) (n) = \phi(g) (n)\right]

There will be infinitely many nice monsters, and infinitely many not-nice monsters (assuming |a|&gt;1).

Again, let me stop here and make sure you've understood all this correctly before I go on and explain the proof of the theorem. There's a lot more to say about better ways to understand functions \mathbb{N} \to a, better way to understand nice monsters a^{\mathbb{N}} \to a^{\mathbb{N}}, and understanding how the Recursion Theorem justifies the process of "defining functions by recursion" (e.g. you could define the Fibonacci function by f(0) = 0, f(1) = 1, f(n+2) = f(n+1) + f(n), but how do you know there exists a unique function satisfying this definition? It seems obvious, but the rigorous answer is: The Recursion Theorem). But let's make sure we're on the same page with the basics first.

 

[martijnh]

Thank you very much for this lucid explanation, I wish my textbook was that clear!

I still wonder about the proof and the practical usefullness of the theorem though!

PS: I did not mention \phi in my previous post as I thought Steve suggested I should look at it in a simplified way; Where \phi would be analogous to a function \mathbb{N} \rightarrow \mathbb{N} and the input functions f & g analogous to elements of \mathbb{N} (so comparing the construct to a regular function). But I now understand the gist of the recusrsion theorem to be about a property of functions.