There exists a computable surjection from to (the codes of) all sentences in the language.
Let . Also, let if is consistent and (the negation of the formula with the code ) otherwise. Finally, let . Prove that all and, therefore, are consistent. So far this is a standard procedure for building a maximal consistent theory containing a given theory T. Show that is complete.
Prove that there is a way to compute each g(n) knowing g(0), ..., g(n - 1). So, one way to find if , i.e., if , is to find n such that and see if or .