- #1
Jerbearrrrrr
- 127
- 0
There are probably a million theorems called "the recursion theorem" and I'm not sure if this is actually one of them, but there's a remark saying that it defines recursion.
It's proven by piecing together 'attempts' (functions defined on subsets of a domain) and states:
For X a well-ordered set, Y any set:
For any G:P(XxY)->Y,
there exists f:X->Y
such that f(x)=G(f|Ix), for all x in X.
where:
Ix is the initial subset {y in X iff y<x}
f|A = {(x,f(x) : x in A} - the restriction of f to A.
P denotes power set.
I just have no idea what it's saying.
Googling suggests that it's "Cantor's theorem, originally stated for ordinals, which extends inductive proof to recursive construction." but I can't find anything on it, possibly because the lecturer has mixed a few proofs together so it's a weaker form of a better-known theorem, but much easier to prove.
Thanks :\
[edit]
Wait...is this just saying that, for any G:{functions}->{numbers}, there's a function, f, that satisfies f(5)=G[f(4)]? And so on.
It's proven by piecing together 'attempts' (functions defined on subsets of a domain) and states:
For X a well-ordered set, Y any set:
For any G:P(XxY)->Y,
there exists f:X->Y
such that f(x)=G(f|Ix), for all x in X.
where:
Ix is the initial subset {y in X iff y<x}
f|A = {(x,f(x) : x in A} - the restriction of f to A.
P denotes power set.
I just have no idea what it's saying.
Googling suggests that it's "Cantor's theorem, originally stated for ordinals, which extends inductive proof to recursive construction." but I can't find anything on it, possibly because the lecturer has mixed a few proofs together so it's a weaker form of a better-known theorem, but much easier to prove.
Thanks :\
[edit]
Wait...is this just saying that, for any G:{functions}->{numbers}, there's a function, f, that satisfies f(5)=G[f(4)]? And so on.
Last edited: