Editing Kleene's recursion theorem (section)

=== Proof sketch for the first recursion theorem ===
The proof of part 1 of the first recursion theorem is obtained by iterating the enumeration operator Φ beginning with the [[empty set]]. First, a sequence ''F''<sub>''k''</sub> is constructed, for <math>k  = 0, 1, \ldots</math>.  Let ''F''<sub>0</sub> be the empty set. Proceeding inductively, for each ''k'', let ''F''<sub>''k'' + 1</sub> be <math>F_k \cup \Phi(F_k)</math>. Finally, ''F'' is taken to be <math display="inline">\bigcup F_k</math>.  The remainder of the proof consists of a verification that ''F'' is recursively enumerable and is the least fixed point of Φ.   The sequence ''F''<sub>''k''</sub> used in this proof corresponds to the Kleene chain in the proof of the [[Kleene fixed-point theorem]].

The second part of the first recursion theorem follows from the first part. The assumption that Φ is a recursive operator is used to show that the fixed point of Φ is the graph of a partial function. The key point is that if the fixed point ''F'' is not the graph of a function, then there is some ''k'' such that ''F''<sub>''k''</sub> is not the graph of a function.