User:IssaRice/Computability and logic/Diagonalization lemma

From Machinelearning
< User:IssaRice
Revision as of 02:10, 8 February 2019 by IssaRice (talk | contribs) (Diagonalization lemma)
Jump to: navigation, search

Rogers's fixed point theorem

Let f be a total computable function. Then there exists an index e such that \varphi_e \simeq \varphi_{f(e)}.

Diagonalization lemma

(semantic version)

Let A be a formula with one free variable. Then there exists a sentence G such that G iff A(\ulcorner G\urcorner).

Define \mathrm{diag}(x) to be \ulcorner C(\ulcorner C\urcorner)\urcorner, where x = \ulcorner C\urcorner.