User:IssaRice/Computability and logic/Diagonalization lemma: Difference between revisions
| Line 5: | Line 5: | ||
==Diagonalization lemma== | ==Diagonalization lemma== | ||
(semantic version) | |||
Let <math>A</math> be a formula with one free variable. Then there exists a sentence <math>G</math> such that <math>G</math> iff <math>A(\ulcorner G\urcorner)</math>. | Let <math>A</math> be a formula with one free variable. Then there exists a sentence <math>G</math> such that <math>G</math> iff <math>A(\ulcorner G\urcorner)</math>. | ||
Revision as of 02:06, 8 February 2019
Rogers's fixed point theorem
Let be a total computable function. Then there exists an index such that .
Diagonalization lemma
(semantic version)
Let be a formula with one free variable. Then there exists a sentence such that iff .
