Flashcards
Logic VI
Cards in this deck (13)
- 1The diagonalisation of A\(\thereis\)x(x ='A' & A)
- 2Diagonalisation LemmaLet T be a theory extending Q. Then for any formula b(y) there is a sentence G s.t. g<-> B('G')
- 3Tarski's Indefinability TheoremThe set \(\Theta\) of Gödel numbers of sentences of L* that are true in the standard interpretation is not arithmetically definable
- 4Undecidability of Arithmetic TheoremThe set \(\theta\) of Gödel numbers or sentences \(\in\)L* true in standard model is not recursive. By Church's thesis, \(\theta\) is not effectively decidable.
- 5Essential Undecidability TheoremAny theorem extending Q is undecidable
- 6Church's TheoremThe set of logically valid sentences of first-order classical logic is not decidable
- 7First Incompleteness TheoremAny complete and axiomatisable theory extending Q is inconsistent.
- 8A sentence is disprovable in Tif its negation is provable in T
- 9A sentence is undecidable in Tif neither provable nor disprovable in T
- 10A Gödel sentence of a theory Tis the sentence \(\G_T\) s.t. \(\vdash_T\G_T) <->~\(\thereis\)y \(\Prf_T\)('\(\G_T\)',y)
- 11First Incompleteness Theorem (Historical)Let T be a consistent, axiomatizable extension of Q. Then \(\G_T\) is unprovable in T, & if T is \(\omega\)-consistent, \(\G_T\) is undisprovable in T.
- 12Consistency Sentence for TFor any T in L* extending Q this is ~\(\Prf_T\)('\(\Gamma_0\)'=\(\Gamma\)) , equivalently ~\(\thereis\)y(\(\Prf_t\)('0=1',y))
- 13Second Incompleteness TheoremLet T be any consistent axiomatizable extension of P arithmetic. Then the consistency sentence for T is not provable in T.