User:IssaRice/Computability and logic/Diagonalization out of a class

Diagonalization out of a class is a trick used to define a function that is not in a given list of functions.

Let $C$ be some class of total functions. If we are given an enumeration of $C$ such as $f_{0},f_{1},f_{2},f_{3},\ldots$ then we can define a new total function $g(x):=f_{x}(x)+1$. Now given any $n\in \mathbf {N}$, we have $f_{n}(n)\neq f_{n}(n)+1=g(n)$. Thus, $g\neq f_{n}$ for every $n\in \mathbf {N}$, so $g\notin C$.