Interpretacja dialektyki

W teorii dowodu interpretacja Dialectica jest interpretacją dowodową arytmetyki intuicjonistycznej ( arytmetyka Heytinga ) na skończone rozszerzenie pierwotnej arytmetyki rekurencyjnej , tak zwany System T. Został opracowany przez Kurta Gödela w celu zapewnienia dowodu spójności arytmetyki. Nazwa interpretacji pochodzi od czasopisma Dialectica , w którym artykuł Gödla został opublikowany w 1958 roku w specjalnym numerze poświęconym Paulowi Bernaysowi z okazji jego 70. urodzin.

Motywacja

Poprzez negatywne tłumaczenie Gödla-Gentzena spójność klasycznej arytmetyki Peano została już zredukowana do spójności intuicjonistycznej arytmetyki Heytinga . Motywacją Gödla do opracowania interpretacji dialektyki było uzyskanie względnego spójności dla arytmetyki Heytinga (a więc i dla arytmetyki Peano).

Dialektyczna interpretacja logiki intuicjonistycznej

Tłumaczenie ustne składa się z dwóch części: tłumaczenia formuły i tłumaczenia próbnego. Tłumaczenie formuły opisuje, w jaki sposób każda formuła $Heytinga$ $displaystyle A}$ formułę wolną od kwantyfikatorów T, gdzie ${\ displaystyle x}$ i ${\ displaystyle y}$ to krotki świeżych zmiennych (nie pojawiające się swobodnie w ${\ displaystyle A}$ ). Intuicyjnie, $}$ interpretowany jako ${\ Displaystyle \ istnieje x \ forall yA_ {D} (x; y)$ . Tłumaczenie próbne pokazuje, w jaki sposób dowód $displaystyle A$ $}$ $ilość informacji, aby być$ interpretacji , tj. Dowód można przekształcić w termin zamknięty $t}$ ${\$ i dowód w systemie T. ${\ Displaystyle A_ {D} (t; y)}$

Tłumaczenie formuły

Formuła wolna od kwantyfikatorów $w$ na strukturze logicznej sposób, gdzie $}$ $P$ wzór atomowy:

{\ Displaystyle {\ rozpocząć {tablica} {lcl} (P) _ {D} i \ równoważnik & P \\ (A \ klin B) _ {D} (x, v; y, w )&\równoważnik &A_{D}(x;y)\klin B_{D}(v;w)\\(A\vee B)_{D}(x,v,z;y,w)&\równoważnik &(z=0\rightarrow A_{D}(x;y))\klin (z\neq 0\to B_{D}(v;w))\\(A\rightarrow B)_{D}(f ,g;x,w)&\równoważnik &A_{D}(x;fxw)\rightarrow B_{D}(gx;w)\\(\istnieje zA)_{D}(x,z;y)&\ równoważne &A_{D}(x;y)\\(\forall zA)_{D}(f;y,z)&\równoważne &A_{D}(fz;y)\end{tablica}}}

Tłumaczenie próbne (solidność)

Interpretacja formuły jest taka, że ilekroć $t {$ $do udowodnienia$ istnieje sekwencja wyrazów zamkniętych $A$ , że ${\ displaystyle$ $\ displaystyle t}$ jest dowodliwy w systemie T. Sekwencja terminów dowód są konstruowane z danego ${\ Displaystyle A_ {D} (t; y)}$ dowód w $Heytinga$ . Konstrukcja $wolne$ z wyjątkiem aksjomatu $, który wymaga$ od kwantyfikatorów są rozstrzygalne

Zasady charakteryzacji

Wykazano również, że arytmetyka Heytinga obejmuje następujące zasady

Aksjomat wyboru
Zasada Markowa
Niezależność przesłanek dla formuł uniwersalnych

jest konieczne i wystarczające do scharakteryzowania formuł HA, które są interpretowane przez interpretację Dialectica. ^{[ potrzebne źródło ]}

Rozszerzenia podstawowej interpretacji

Podstawowa dialektyczna interpretacja logiki intuicjonistycznej została rozszerzona na różne silniejsze systemy. Intuicyjnie, dialektyczna interpretacja może być zastosowana do silniejszego systemu, o ile dialektyczna interpretacja dodatkowej zasady może być potwierdzona terminami w systemie T (lub rozszerzeniem systemu T).

Wprowadzenie

Biorąc pod uwagę twierdzenie Gödla o niezupełności (które implikuje, że spójności PA nie można udowodnić środkami finitystycznymi ), uzasadnione jest oczekiwanie, że system T musi zawierać konstrukcje niefinitystyczne. Rzeczywiście tak jest. Konstrukcje niefinitystyczne pojawiają się w interpretacji indukcji matematycznej . Aby dać dialektyczną interpretację indukcji, Gödel wykorzystuje tak zwane prymitywne funkcjonały rekurencyjne Gödla , które są funkcjami wyższego rzędu z prymitywnymi opisami rekurencyjnymi.

Logika klasyczna

Wzorom i dowodom w arytmetyce klasycznej można również nadać interpretację Dialectica poprzez wstępne osadzenie w arytmetyce Heytinga, po której następuje interpretacja arytmetyki Heytinga w Dialectica. Shoenfield w swojej książce łączy tłumaczenie negatywne i interpretację Dialectica w jedną interpretację klasycznej arytmetyki.

Zrozumienie

W 1962 roku Spector rozszerzył interpretację arytmetyki Gödel's Dialectica na pełną analizę matematyczną, pokazując, w jaki sposób schematowi policzalnego wyboru można nadać interpretację Dialectica poprzez rozszerzenie systemu T o rekurencję słupkową .

Dialektyczna interpretacja logiki liniowej

Interpretacja Dialectica została wykorzystana do zbudowania modelu udoskonalania przez Girarda logiki intuicjonistycznej , znanej jako logika liniowa , poprzez tak zwane przestrzenie Dialectica . Ponieważ logika liniowa jest udoskonaleniem logiki intuicjonistycznej, dialektyczną interpretację logiki liniowej można również postrzegać jako udoskonalenie dialektycznej interpretacji logiki intuicjonistycznej.

Chociaż liniowa interpretacja w pracy Shirahaty potwierdza regułę osłabienia (w rzeczywistości jest to interpretacja logiki afinicznej ), interpretacja przestrzeni dialektycznych de Paivy nie potwierdza osłabienia dla dowolnych formuł.

Warianty interpretacji Dialectica

Od tego czasu zaproponowano kilka wariantów interpretacji Dialectica. Przede wszystkim wariant Dillera-Nahma (aby uniknąć problemu ze skróceniem) oraz monotonne i ograniczone interpretacje Kohlenbacha i Ferreiry-Olivy (aby zinterpretować słaby lemat Kőniga ). Kompleksowe traktowanie interpretacji można znaleźć w , i.

^ Kurt Gödel (1958). Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes . dialektyka. s. 280–287.
^ Clifford Spector (1962). Udowodnione rekurencyjne funkcjonały analizy: dowód spójności analizy poprzez rozszerzenie zasad obecnej matematyki intuicjonistycznej . Teoria funkcji rekurencyjnych: Proc. Sympozja z czystej matematyki. s. 1–27.
^ Valeria de Paiva (1991). Kategorie dialektyki (PDF) . University of Cambridge, Laboratorium komputerowe, rozprawa doktorska, raport techniczny 213.
Bibliografia _ Dialectica interpretacja klasycznej logiki afinicznej pierwszego rzędu . Teoria i zastosowania kategorii, tom. 17, nr 4. s. 49–79.
^ Jeremy Avigad i Solomon Feferman (1999). Interpretacja funkcjonalna Gödla („Dialectica”) (PDF) . w S. Buss ed., The Handbook of Proof Theory, North-Holland. s. 337–405.
^ Ulrich Kohlenbach (2008). Stosowana teoria dowodu: interpretacje dowodu i ich zastosowanie w matematyce . Springer Verlag w Berlinie. s. 1 –536.
^ Anne S. Troelstra (z CA Smoryńskim, JI Zuckerem, WAHowardem) (1973). Metamatematyczne badanie intuicjonistycznej arytmetyki i analizy . Springer Verlag w Berlinie. s. 1–323. {{ cite book }} : CS1 maint: wiele nazwisk: lista autorów ( link )

[1] Kurt Gödel (1958). Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes . dialektyka. s. 280–287.

[2] Clifford Spector (1962). Udowodnione rekurencyjne funkcjonały analizy: dowód spójności analizy poprzez rozszerzenie zasad obecnej matematyki intuicjonistycznej . Teoria funkcji rekurencyjnych: Proc. Sympozja z czystej matematyki. s. 1–27.

[3] Valeria de Paiva (1991). Kategorie dialektyki (PDF) . University of Cambridge, Laboratorium komputerowe, rozprawa doktorska, raport techniczny 213.

[4] Bibliografia _ Dialectica interpretacja klasycznej logiki afinicznej pierwszego rzędu . Teoria i zastosowania kategorii, tom. 17, nr 4. s. 49–79.

[5] Jeremy Avigad i Solomon Feferman (1999). Interpretacja funkcjonalna Gödla („Dialectica”) (PDF) . w S. Buss ed., The Handbook of Proof Theory, North-Holland. s. 337–405.

[6] Ulrich Kohlenbach (2008). Stosowana teoria dowodu: interpretacje dowodu i ich zastosowanie w matematyce . Springer Verlag w Berlinie. s. 1 –536.

[7] Anne S. Troelstra (z CA Smoryńskim, JI Zuckerem, WAHowardem) (1973). Metamatematyczne badanie intuicjonistycznej arytmetyki i analizy . Springer Verlag w Berlinie. s. 1–323. {{ cite book }} : CS1 maint: wiele nazwisk: lista autorów ( link )