Hi all,(adsbygoogle = window.adsbygoogle || []).push({});

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 [itex]\phi[/itex]: a[itex]^{\mathbb{N}}[/itex][itex]\rightarrow[/itex]a[itex]^{\mathbb{N}}[/itex] be a function such that for every natural number n, if f, g [itex]\in[/itex]a[itex]^{\mathbb{N}}[/itex] are such that f|_{n}= g|_{n}, then [itex]\phi[/itex](f)(n) = [itex]\phi[/itex](g)(n). Then [itex]\phi[/itex] has a unique fixpoint L_{[itex]\phi[/itex]}[itex]\in[/itex] a[itex]^{\mathbb{N}}[/itex], which means that [itex]\phi[/itex] (L_{[itex]\phi[/itex] }) = L_{[itex]\phi[/itex] }. Consider the function [itex]\phi[/itex]_{n}: a[itex]^{n}[/itex][itex]\rightarrow[/itex]a which evaluates to [itex]\phi[/itex]_{n}(g) = [itex]\phi[/itex](g*)(n). Then we have

L_{[itex]\phi[/itex] }(0) = [itex]\phi[/itex]_{0}(!:0[itex]\rightarrow[/itex]a)

L_{[itex]\phi[/itex] }(n^{+}) = [itex]\phi[/itex]_{n+}(L_{[itex]\phi[/itex] }|_{n+})

What I get from this is:

Let [itex]\phi[/itex] 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[itex]^{\mathbb{N}}[/itex] and these return the same result for an element n, then the set of functions [itex]\phi[/itex] 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 [itex]\phi[/itex] which yields itself given itself as input to [itex]\phi[/itex]. 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 [itex]\phi[/itex], 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 [itex]\phi[/itex](L) = L and [itex]\phi[/itex](M) = M, and suppose that they are different. Then there is a smallest value n_{0}such that L(n_{0}) ≠ M(n_{0}). This means that L|_{n0}= M|_{n0}. But then [itex]\phi[/itex](L)(n_{0}) = [itex]\phi[/itex](M)(n_{0}), a contradiction. So there is at most one such fixpoint. For every n [itex]\in[/itex] [itex]\mathbb{N}[/itex], let S(n) [itex]\subset[/itex] a^{n}be the set of those functions f: n [itex]\rightarrow[/itex] a such that for all m [itex]\in[/itex] n, f(m) = [itex]\phi[/itex]_{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^{+}[itex]\rightarrow[/itex] a by h|_{N}= g_{N}and h(N) = [itex]\phi[/itex]_{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) = [itex]\phi[/itex](g_{n+}|_{n}) = [itex]\phi[/itex]_{n}(g_{n}) = [itex]\phi[/itex](g[itex]^{*}_{n}[/itex])(n) = [itex]\phi[/itex](L)(n) since L|_{n}= g_{n}= g[itex]^{*}_{n}[/itex]|_{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

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Understanding the recursion theorem

Loading...

Similar Threads for Understanding recursion theorem |
---|

I Understanding the transformation of skewness formula |

I An easy proof of Gödel's first incompleteness theorem? |

B Understanding Chi Squared p-values |

I Recursive Ordinals and Creativity |

**Physics Forums | Science Articles, Homework Help, Discussion**