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

Revision as of 02:10, 8 February 2019

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

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

Revision as of 02:06, 8 February 2019 (view source) IssaRice (talk \| contribs) (→‎Diagonalization lemma) ← Older edit		Revision as of 02:10, 8 February 2019 (view source) IssaRice (talk \| contribs) (→‎Diagonalization lemma) Newer edit →
Line 9:		Line 9:

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

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