User:IssaRice/Computability and logic/Diagonalization lemma: Difference between revisions

Revision as of 02:06, 8 February 2019

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

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

Revision as of 02:03, 8 February 2019 (view source) IssaRice (talk \| contribs) (Created page with " ==Rogers's fixed point theorem== Let <math>f</math> be a total computable function. Then there exists an index <math>e</math> such that <math>\varphi_e \simeq \varphi_{f(e)}...")		Revision as of 02:06, 8 February 2019 (view source) IssaRice (talk \| contribs) (→‎Diagonalization lemma) Newer edit →
Line 5:		Line 5:

	==Diagonalization lemma==		==Diagonalization lemma==

			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>.