The differences between two versions of Recursion Theorem

91 Views Asked by At

Version 1:

For any set $A$, any $a\in A$, and any function $g:A\times \Bbb N\to A$, there exists a unique infinite sequence $f:\Bbb N\to A$ such that

(1) $f_0=a$;

(2) $f_{n+1}=g(f_n,n)$ for all $n\in\Bbb N$

Version 2:

Let $G$ be an operation. For any set $a$, there exists a unique infinite sequence $(f_n\mid n\in\Bbb N)$ such that

(1) $f_0=a$;

(2) $f_{n+1}=G(f_n,n)$ for all $n\in\Bbb N$


Of my understanding, the input of Version 1 are two factors: a set and one of its elements, while that of Version 2 is just one factor: a set. Maybe I'm wrong, but I feel that they are quite similar.

My questions:

  1. Are there more fundamental differences of these two versions?

  2. Please give me an simple-to-understand example where one version is still valid to apply, while the other is not. (I'm just exposed to Transfinite Induction/Recursion, so I'm afraid that I'm unable to grasp advanced examples).

Thank you so much!

1

There are 1 best solutions below

4
On BEST ANSWER

Actually, version 2 doesn't make a lot of sense, because you never say what $A$ is nor where the operation $G$ is defined. And if, as I suspect, $A$ is an arbitrary set, $a$ is an element of $A$, and $G$ is a function from $A\times\mathbb N$ into $A$, the version 2 becomes version 1.