Diagonální lemma - Diagonal lemma

v matematická logika, diagonální lemma (také známý jako diagonalizační lemma, samorealizační lemma^[1] nebo věta o pevném bodě) stanoví existenci autoreferenční věty v určitých formálních teoriích přirozená čísla —Konkrétně ty teorie, které jsou dostatečně silné, aby reprezentovaly všechny vypočítatelné funkce. Věty, jejichž existence je zajištěna diagonálním lemmatem, lze následně použít k prokázání základních omezujících výsledků, jako jsou Gödelovy věty o neúplnosti a Tarskiho věta o nedefinovatelnosti.^[2]

Pozadí

Nechat ${ displaystyle mathbb {N}}$ být množinou přirozená čísla. A teorie T představuje vypočítatelná funkce ${ displaystyle f: mathbb {N} rightarrow mathbb {N}}$ pokud existuje predikát "grafu" ${ displaystyle Gamma _ {f} (x, y)}$ v jazyce T takové, že pro každého ${ displaystyle x in mathbb {N}}$, T dokazuje

${ displaystyle forall y quad left ({} ^ { circ} f (x) = y Leftrightarrow Gamma _ {f} ({} ^ { circ} x, y) right)}$.^[3]

Tady ${ displaystyle {} ^ { circ} x}$ je číslice odpovídající přirozenému číslu ${ displaystyle x}$, který je definován jako uzavřený termín 1+ ··· +1 (${ displaystyle x}$ ty) a ${ displaystyle {} ^ { circ} f (x)}$ je číslice odpovídající ${ displaystyle f (x)}$.

Diagonální lemma také vyžaduje, aby existoval systematický způsob přiřazování každému vzorci θ přirozené číslo # (θ) nazývané jeho Gödelovo číslo. Vzorce pak mohou být v teorii reprezentovány číslicemi odpovídajícími jejich Gödelovým číslům. Například θ je reprezentováno ° # (θ)

Diagonální lemma platí pro teorie schopné reprezentovat všechny primitivní rekurzivní funkce. Mezi takové teorie patří Peano aritmetika a slabší Robinsonova aritmetika. Společné tvrzení o lemmatu (jak je uvedeno níže) vytváří silnější předpoklad, že teorie může představovat vše vypočítatelné funkce.

Prohlášení o lemmatu

Nechat T být první objednávka teorie v jazyce aritmetiky a schopná reprezentovat všechny vypočítatelné funkce. Nechť F je vzorec v jazyce s jednou volnou proměnnou, pak:

Intuitivně, ${ displaystyle psi}$ je autoreferenční věta, která to říká ${ displaystyle psi}$ má vlastnost F. Věta ${ displaystyle psi}$ lze také zobrazit jako pevný bod operace přiřazující ke každému vzorci ${ displaystyle theta}$ věta ${ displaystyle F (^ { circ} # ( theta))}$. Věta ${ displaystyle psi}$ postavený v důkazu není doslova stejný jako ${ displaystyle F (^ { circ} # ( psi))}}$, ale je prokazatelně ekvivalentní tomu v teoriiT.

Důkaz

Nechat F: N→N být funkcí definovanou:

F(# (θ)) = # (θ (° # (θ)))

pro každého T-formule θ v jedné volné proměnné a F(n) = 0 jinak. Funkce F je vypočítatelný, takže existuje vzorec Γ_F zastupující F v T. Pro každý vzorec θ tedy T dokazuje

(∀y) [Γ_F(° # (θ),y) ↔ y = °F(# (θ))],

což znamená

(∀y) [Γ_F(° # (θ),y) ↔ y = ° # (θ (° # (θ)))].

Nyní definujte vzorec β (z) tak jako:

β (z) = (∀y) [Γ_F(z,y) → F (y)].

Pak T dokazuje

β (° # (θ)) ↔ (∀y) [ y = ° # (θ (° # (θ))) → F (y)],

což znamená

β (° # (θ)) ↔ F (° # (θ (° # (θ)))).

Nyní vezměte θ = β a ψ = β (° # (β)) a předchozí věta se přepíše na ψ ↔ F (° # (ψ)), což je požadovaný výsledek.

(Stejný argument v různých termínech je uveden v [Raatikainen (2015a)].)

Dějiny

Lema se nazývá „úhlopříčka“, protože má určitou podobnost Cantorův diagonální argument.^[5] Výrazy „diagonální lemma“ nebo „pevný bod“ se v systému neobjevují Kurt Gödel je Článek z roku 1931 nebo v Alfred Tarski je Článek z roku 1936.

Rudolf Carnap (1934) jako první prokázal obecné autoreferenční lemma^[6] který říká, že pro jakýkoli vzorec F v teorii T splňující určité podmínky, existuje vzorec ψ takový, že ψ ↔ F (° # (ψ)) je prokazatelný v T. Carnapova práce byla formulována v alternativním jazyce, jako koncept vypočítatelné funkce v roce 1934 ještě nebyl vyvinut. Mendelson (1997, s. 204) se domnívá, že Carnap jako první uvedl, že něco jako diagonální lemma bylo implicitní v Gödelově uvažování. Gödel věděl o Carnapově práci do roku 1937.^[7]

Diagonální lema úzce souvisí s Kleenova věta o rekurzi v teorie vypočítatelnosti a jejich příslušné důkazy jsou podobné.

Viz také

• Nepřímý vlastní odkaz
• Seznam vět o pevném bodě
• Primitivní rekurzivní aritmetika
• Vlastní reference
• Autoreferenční paradoxy

Poznámky

Reference

• George Boolos a Richard Jeffrey, 1989. Vyčíslitelnost a logika, 3. vyd. Cambridge University Press. ISBN  0-521-38026-X ISBN  0-521-38923-2
• Rudolf Carnap, 1934. Logische Syntax der Sprache. (Anglický překlad: 2003. Logická syntax jazyka. Publikování na otevřeném dvoře.)
• Haim Gaifman, 2006. 'Pojmenování a diagonalizace: Od Cantora po Gödela po Kleene '. Logický deník IGPL, 14: 709–728.
• Hinman, Peter, 2005. Základy matematické logiky. A K Peters. ISBN  1-56881-262-0
• Mendelson, Elliott, 1997. Úvod do matematické logiky, 4. vyd. Chapman & Hall.
• Panu Raatikainen, 2015a. Diagonalizační lemma. v Stanfordská encyklopedie filozofie, vyd. Zalta. Dodatek k Raatikainen (2015b).
• Panu Raatikainen, 2015b. Gödelovy věty o neúplnosti. v Stanfordská encyklopedie filozofie, vyd. Zalta.
• Raymond Smullyan, 1991. Gödelovy věty o neúplnosti. Oxford Univ. Lis.
• Raymond Smullyan, 1994. Diagonalizace a vlastní reference. Oxford Univ. Lis.
• Alfred Tarski (1936). „Der Wahrheitsbegriff in den formalisierten Sprachen“ (PDF). Studia Philosophica. 1: 261–405. Archivovány od originál (PDF) dne 9. ledna 2014. Citováno 26. června 2013.
  • Alfred Tarski, tr. J. H. Woodger, 1983. „Koncept pravdy ve formalizovaných jazycích“. Anglický překlad článku Tarského z roku 1936. In A. Tarski, ed. J. Corcoran, 1983, Logika, sémantika, matematikaHackett.