User:IssaRice/Computability and logic/Diagonalization lemma (Yanofsky method): Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
This page is just a rewritten version of the [https://arxiv.org/pdf/math/0305282.pdf#section.5 proof of the diagonalization lemma from Yanofsky's paper]. There are some parts I found difficult to understand/gaps that I thought should be filled, so this version will hopefully be much more complete. | This page is just a rewritten version of the [https://arxiv.org/pdf/math/0305282.pdf#section.5 proof of the diagonalization lemma from Yanofsky's paper]. There are some parts I found difficult to understand/gaps that I thought should be filled, so this version will hopefully be much more complete. | ||
'''Theorem (Diagonalization lemma).''' Let <math>T</math> be some nice theory (I don't remember the exact conditions, but Peano Arithmetic or Robinson Arithmetic would work). For any single-place formula <math>\mathcal E(x)</math> with <math>x</math> as its only free variable, there exists a sentence (closed formula) <math>\mathcal C</math> such that <math>T \ | '''Theorem (Diagonalization lemma).''' Let <math>T</math> be some nice theory (I don't remember the exact conditions, but Peano Arithmetic or Robinson Arithmetic would work). For any single-place formula <math>\mathcal E(x)</math> with <math>x</math> as its only free variable, there exists a sentence (closed formula) <math>\mathcal C</math> such that <math>T \vdash \mathcal C \leftrightarrow \mathcal E(\ulcorner \mathcal C \urcorner)</math> | ||
Acknowledgments: Thanks to Rupert McCallum for helping me work through the proof. | Acknowledgments: Thanks to Rupert McCallum for helping me work through the proof. | ||
Revision as of 20:27, 27 July 2021
This page is just a rewritten version of the proof of the diagonalization lemma from Yanofsky's paper. There are some parts I found difficult to understand/gaps that I thought should be filled, so this version will hopefully be much more complete.
Theorem (Diagonalization lemma). Let be some nice theory (I don't remember the exact conditions, but Peano Arithmetic or Robinson Arithmetic would work). For any single-place formula with as its only free variable, there exists a sentence (closed formula) such that
Acknowledgments: Thanks to Rupert McCallum for helping me work through the proof.