Dějiny teorie typů - History of type theory

The teorie typů byl původně vytvořen, aby se zabránilo paradoxům v různých formálních logika a přepsat systémy. Později se teorie typů zmínila o třídě formální systémy, z nichž některé mohou sloužit jako alternativa k naivní teorie množin jako základ pro celou matematiku.

Od té doby se váže k formální matematice Principia Mathematica na dnešní důkazní asistenti.

1900–1927

Původ Russellovy teorie typů

V dopise Gottlob Frege (1902), Bertrand Russell oznámil svůj objev paradoxu ve Fregeově Begriffsschrift.[1] Frege pohotově zareagoval, uznal problém a v technické diskusi o „úrovních“ navrhl řešení. Citovat Frege:

Mimochodem, zdá se mi, že výraz „a predikát je predikován sám o sobě "není přesný. Predikát je zpravidla funkcí první úrovně a tato funkce vyžaduje objekt jako argument a nemůže mít sám sebe jako argument (předmět). Proto bych raději řekl" koncept je predikován vlastního rozšíření ".[2]

Pokračuje v předvádění, jak by to mohlo fungovat, ale zdá se, že se z toho stáhl. V důsledku toho, co se stalo známé jako Russellův paradox Frege i Russell museli rychle upravit díla, která měli u tiskáren. V příloze B, kterou si Russell připnul na svou Principy matematiky (1903) lze najít jeho „předběžnou“ teorii typů. Tato záležitost sužovala Russella asi pět let.[3]

Willard Quine[4] představuje historický přehled původu teorie typů a „rozvětvené“ teorie typů: po zvážení opuštění teorie typů (1905) navrhl Russell postupně tři teorie:

  1. cikcaková teorie
  2. teorie omezení velikosti,
  3. teorie bez třídy (1905–1906) a poté,
  4. readopting the theory of types (1908ff)

Quine poznamenává, že Russellovo zavedení pojmu „zdánlivá proměnná“ mělo následující výsledek:

rozdíl mezi „all“ a „any“: „all“ je vyjádřen vázanou („zjevnou“) proměnnou univerzální kvantifikace, která se pohybuje nad typem, a „any“ je vyjádřen volnou („skutečnou“) proměnnou který schematicky odkazuje na jakoukoli nespecifikovanou věc bez ohledu na typ.

Quine odmítá tento pojem „vázané proměnné“ jako „zbytečné kromě určitého aspektu teorie typů".[5]

1908 „rozvětvená“ teorie typů

Quine vysvětluje rozvětvený Teorie takto: „Bylo to tak nazváno, protože typ funkce závisí jak na typech jejích argumentů, tak na typech zjevných proměnných v ní obsažených (nebo v jejich výrazu), pokud překračují typy argumenty ".[5] Stephen Kleene v jeho 1952 Úvod do matematiky popisuje rozvětvený teorie typů tímto způsobem:

Primární objekty nebo jednotlivci (tj. Dané věci nepodléhající logické analýze) jsou přiřazeny jednomu typu (řekněme zadejte 0), vlastnosti jednotlivců typ 1, vlastnosti vlastností jednotlivců typ 2, atd.; a nepřijímají se žádné vlastnosti, které nespadají do žádného z těchto logických typů (např. tím se vlastnosti „předvídatelné“ a „nepravděpodobné“ ... dostanou mimo logiku). Podrobnější účet by popsal povolené typy pro jiné objekty jako vztahy a třídy. Pak vyloučit předběžný definice v rámci typu, typy nad typem 0 se dále dělí na objednávky. U typu 1 tedy patří vlastnosti definované bez uvedení jakékoli totality objednávka 0a vlastnosti definované pomocí souhrnu vlastností dané objednávky patří k dalšímu vyššímu řádu. ... Ale toto rozdělení na řády znemožňuje zkonstruovat známou analýzu, kterou jsme viděli výše, a obsahuje nedefinativní definice. Aby unikl tomuto výsledku, Russell postuloval svůj axiom redukovatelnosti, který tvrdí, že pro jakoukoli vlastnost patřící do řádu nad nejnižší existuje koextenzivní vlastnost (tj. vlastněná přesně stejnými objekty) řádu 0. Pokud jsou považovány pouze definovatelné vlastnosti, pak axiom znamená, že pro každou impredikativní definice v rámci daného typu existuje ekvivalentní predikativní (Kleene 1952: 44–45).

Axiom redukovatelnosti a pojem „matice“

Ale protože ustanovení rozvětvené teorie by se ukázala (cituji Quina) „obtížná“, Russell v roce 1908 Matematická logika založená na teorii typů[6] také navrhne jeho axiom redukovatelnosti. V roce 1910 Whitehead a Russell v jejich Principia Mathematica by dále rozšířil tento axiom o pojem a matice - plně rozšiřující specifikace funkce. Z její matice lze funkci odvodit procesem „generalizace“ a naopak, tj. Oba procesy jsou reverzibilní - (i) zobecnění z matice na funkci (pomocí zjevných proměnných) a (ii) reverzní proces redukce typu o průběhy hodnot nahrazení argumentů pro zjevnou proměnnou. Touto metodou je možné se vyhnout nedůtklivosti.[7]

Pravdivé tabulky

V roce 1921 Emil Post by vyvinulo teorii „pravdivostních funkcí“ a jejich pravdivostní tabulky, které by nahradily pojem zdánlivé versus skutečné proměnné. Od jeho 1921 jeho „Úvod“: „Zatímco úplná teorie [Whitehead a Russell (1910, 1912, 1913)] vyžaduje pro vyjádření svých tvrzení skutečné a zjevné proměnné, které představují jednotlivce i výrokové funkce různých druhů, a jako výsledek vyžaduje těžkopádnou teorii typů, používá tato podkategorie pouze skutečné proměnné a tyto skutečné proměnné představují pouze jeden druh entity, kterou se autoři rozhodli nazývat elementární věty “.[8]

Přibližně ve stejnou dobu Ludwig Wittgenstein vyvinul podobné myšlenky ve své práci z roku 1922 Tractatus Logico-Philosophicus:

3.331 Z tohoto pozorování získáme další pohled - na Russellovou teorii typů. Russellova chyba je patrná ze skutečnosti, že při vypracovávání svých symbolických pravidel musí hovořit o významech svých znamení.

3.332 Žádný výrok nemůže o sobě nic říci, protože výrokový znak nemůže být v sobě obsažen (to je celá „teorie typů“).

3.333 Funkce nemůže být jejím vlastním argumentem, protože funkční znak již obsahuje prototyp vlastního argumentu a nemůže obsahovat sám sebe ...

Wittgenstein také navrhl metodu tabulky pravdivosti. Ve svých 4,3 až 5,101 Wittgenstein přijímá neomezené Shefferova mrtvice jako jeho základní logická entita a poté vyjmenuje všech 16 funkcí dvou proměnných (5.101).

Pojem tabulky matice jako pravda se objevuje až ve 40. až 50. letech 20. století v díle Tarského, např. jeho indexy z roku 1946 „Matrix, viz: Pravdivá tabulka“[9]

Russellovy pochybnosti

Russell v jeho 1920 Úvod do matematické filozofie věnuje celou kapitolu „Axiomu nekonečna a logických typů“, kde vyjadřuje své obavy: „Teorie typů důrazně nepatří k hotové a určité části našeho předmětu: většina této teorie je stále intimní, zmatená, a temný. Ale potřeba nějaký nauka typů je méně pochybná než přesná forma, kterou by nauka měla mít; a v souvislosti s axiomem nekonečna je zvláště snadné pochopit nutnost nějaké takové doktríny “.[10]

Russell opouští axiom redukovatelnosti: Ve druhém vydání Principia Mathematica (1927) uznává Wittgensteinův argument.[11] Na začátku svého úvodu prohlašuje, že „není pochyb ... že není třeba rozlišovat mezi skutečnými a zdánlivými proměnnými ...“.[12] Nyní plně přijal pojem matice a prohlásil „A funkce se může v matici objevit pouze prostřednictvím jejích hodnot„(ale uvádí v poznámce pod čarou:„ Nahrazuje (ne zcela adekvátně) axiom redukovatelnosti “[13]). Dále zavádí nový (zkrácený, zobecněný) pojem „matice“, pojem „logické matice…, která neobsahuje žádné konstanty. p|q je logická matice ".[14] Russell tedy prakticky opustil axiom redukovatelnosti,[15] ale ve svých posledních odstavcích uvádí, že z „našich současných primitivních tvrzení“ nemůže odvodit „dedekindovské vztahy a dobře uspořádané vztahy“ a poznamenává, že pokud bude existovat nový axiom, který nahradí axiom redukovatelnosti, „zbývá jej objevit“.[16]

Teorie jednoduchých typů

Ve 20. letech Leon Chwistek[17] a Frank P. Ramsey[18] si všiml, že pokud je člověk ochoten se vzdát princip bludného kruhu, hierarchii úrovní typů ve „rozvětvené teorii typů“ lze sbalit.

Výsledná omezená logika se nazývá teorie jednoduchých typů[19] nebo snad častěji jednoduchá teorie typů.[20] Podrobné formulace teorie jednoduchých typů byly publikovány koncem 20. a počátkem 30. let R. Carnapem, F. Ramseyem, W.V.O. Quine a A. Tarski. V roce 1940 Alonzo Church (znovu) formuloval jako jednoduše zadaný lambda kalkul.[21] a zkoumal Gödel v roce 1944. Průzkum tohoto vývoje lze nalézt v Collinsovi (2012).[22]

40. léta - současnost

Gödel 1944

Kurt Gödel v jeho 1944 Russellova matematická logika dal v poznámce pod čarou následující definici „teorie jednoduchých typů“:

Teorií jednoduchých typů mám na mysli nauku, která říká, že předměty myšlení (nebo v jiném výkladu symbolické výrazy) se dělí na typy, a to: jednotlivci, vlastnosti jednotlivců, vztahy mezi jednotlivci, vlastnosti těchto vztahů, atd. (s podobnou hierarchií přípon) a věty ve tvaru: " A má majetek φ ", " b nese vztah R na C „atd. nemají smysl, pokud a, b, c, R, φ nejsou typů, které do sebe zapadají. Jsou vyloučeny smíšené typy (například třídy obsahující jednotlivce a třídy jako prvky), a proto také transfinitní typy (například třída všech tříd konečných typů). Že teorie jednoduchých typů postačuje k tomu, aby se zabránilo také epistemologickým paradoxům, ukazuje jejich bližší analýza. (Srov. Ramsey 1926 a Tarski 1935, str. 399). “.[23]

Uzavřel (1) teorii jednoduchých typů a (2) axiomatickou teorii množin „povolte odvození moderní matematiky a současně se vyhněte všem známým paradoxům“ (Gödel 1944: 126); dále teorie jednoduchých typů “je systém prvního Principia [Principia Mathematica] ve vhodném výkladu. . . . [M] jakékoli příznaky však ukazují až příliš jasně, že primitivní pojmy vyžadují další objasnění “(Gödel 1944: 126).

Curry – Howardova korespondence, 1934–1969

The Curry – Howardova korespondence je interpretace důkazů jako programů a vzorců jako typů. Myšlenka začínající v roce 1934 s Haskell Curry a dokončena v roce 1969 s William Alvin Howard. Spojilo „výpočetní komponentu“ mnoha teorií typů s derivacemi v logice.

Howard ukázal, že zadaný lambda kalkul odpovídal intuicionismu přirozený odpočet (tj. přirozený odpočet bez Zákon vyloučeného středu ). Spojení mezi typy a logikou vede k mnoha následným výzkumům k nalezení teorií nového typu pro existující logiku a nové logiky pro existující teorie typů.

de Bruijn's AUTOMATH, 1967–2003

Nicolaas Govert de Bruijn vytvořil teorii typů Automath jako matematický základ pro systém Automath, který by mohl ověřit správnost důkazů. Systém se postupem času vyvíjel a přidával funkce podle vývoje teorie typů.

Martin-Löfova intuitivní teorie typů, 1971–1984

Per Martin-Löf našel teorii typů, která odpovídala predikátová logika zavedením závislé typy, který se stal známým jako intuicionistická teorie typů nebo Martin-Löfova teorie typů.

Teorie Martin-Löfa používá induktivní typy k reprezentaci neomezených datových struktur, jako jsou přirozená čísla.

Barendregtova kostka lambda, 1991

The lambda kostka nebyla nová teorie typů, ale kategorizace existujících teorií typů. Osm rohů krychle obsahovalo některé existující teorie s jednoduše zadaný lambda kalkul v nejnižším rohu a počet konstrukcí na nejvyšší úrovni.

Reference

  1. ^ Russell's (1902) Dopis Frege se s komentářem objevuje ve van Heijenoort 1967: 124–125.
  2. ^ Frege (1902) Dopis Russellovi se s komentářem objevuje ve van Heijenoort 1967: 126–128.
  3. ^ srov. Quinův komentář před Russellem (1908) Matematická logika založená na teorii typů in van Heijenoort 1967: 150
  4. ^ srov. komentář od W. V. O. Quine před Russellem (1908) Matematická logika založená na teorii typů in van Hiejenoort 1967: 150–153
  5. ^ A b Quinův komentář před Russellem (1908) Matematická logika založená na teorii typů in van Heijenoort 1967: 151
  6. ^ Russell (1908) Matematická logika založená na teorii typů in van Heijenoort 1967: 153–182
  7. ^ srov. zejména p. 51 v kapitole II Teorie logických typů a * 12 Hierarchie typů a axiom redukovatelnosti 162–167. Whitehead a Russell (1910–1913, 2. vydání, 1927) Principia Mathematica
  8. ^ Příspěvek (1921) Úvod do obecné teorie elementárních vět in van Heijenoort 1967: 264–283
  9. ^ Tarski 1946, Úvod do logiky a metodologie dedukčních věd, Dover republication 1995
  10. ^ Russell 1920: 135
  11. ^ srov. „Úvod“ do 2. vydání, Russell 1927: xiv a dodatek C.
  12. ^ srov. „Úvod“ do 2. vydání, Russell 1927: i
  13. ^ srov. „Úvod“ do 2. vydání, Russell 1927: xxix
  14. ^ Svislá čára „|“ je Shefferův tah; srov. „Úvod“ do 2. vydání, Russell 1927: xxxi
  15. ^ „Teorie tříd je v jednom směru zjednodušena a v jiném komplikována předpokladem, že funkce se vyskytují pouze prostřednictvím jejich hodnot a opuštěním axiomu redukovatelnosti“; srov. „Úvod“ do 2. vydání, Russell 1927: xxxix
  16. ^ Tyto citace z „Úvod“ do 2. vydání, Russell 1927: xliv – xlv.
  17. ^ L. Chwistek, Antynomje logikiformalnej, Przeglad Filozoficzny 24 (1921) 164–171
  18. ^ F. P. Ramsey, Základy matematiky, Proceedings of the London Mathematical Society, Série 2 25 (1926) 338–384.
  19. ^ Gödel 1944, strany 126 a 136–138, poznámka pod čarou 17: „Russellova matematická logika“ uvedená v Kurt Gödel: Sebrané práce: Publikace svazku II 1938–1974Oxford University Press, New York NY, ISBN  978-0-19-514721-6(v.2.pbk).
  20. ^ To neznamená, že teorie je „jednoduchá“, to znamená, že teorie je omezený: typy různých řádů nelze kombinovat: "Smíšené typy (například třídy obsahující jednotlivce a třídy jako prvky), a proto jsou vyloučeny i transfinitní typy (například třída všech tříd konečných typů)." Gödel 1944, strany 127, poznámka pod čarou 17: „Russellova matematická logika“, která se objevuje v Kurt Gödel: Sebrané práce: Publikace svazku II 1938–1974Oxford University Press, New York NY, ISBN  978-0-19-514721-6(v.2.pbk).
  21. ^ A. Church, Formulace jednoduché teorie typů, Journal of Symbolic Logic 5 (1940) 56–68.
  22. ^ J. Collins, A History of the Theory of Types: Developments after the Second Edition 'Principia Mathematica'. LAP Lambert Academic Publishing (2012). ISBN  978-3-8473-2963-3, zejm. chs. 4–6.
  23. ^ Gödel 1944: 126 poznámka pod čarou 17: „Russellova matematická logika“ v Kurt Gödel: Sebrané práce: Publikace svazku II 1938–1974Oxford University Press, New York NY, ISBN  978-0-19-514721-6(v.2.pbk).

Zdroje

  • Bertrand Russell (1903), Principy matematiky: sv. 1, Cambridge na University Press, Cambridge, Velká Británie.
  • Bertrand Russell (1920), Úvod do matematické filozofie (druhé vydání), Dover Publishing Inc., New York NY, ISBN  0-486-27724-0 (zejména kapitoly XIII a XVII).
  • Alfred Tarski (1946), Úvod do logiky a metodologie dedukčních věd, publikováno 1995 společností Dover Publications, Inc., New York, NY ISBN  0-486-28462-X
  • Jean van Heijenoort (1967, 3. tisk 1976), Od Frege po Godla: Kniha pramenů v matematické logice, 1879–1931, Harvard University Press, Cambridge, MA, ISBN  0-674-32449-8 (pbk)
    • Bertrand Russell (1902), Dopis Frege s komentářem van Heijenoorta, strany 124–125. Russell oznamuje svůj objev „paradoxu“ ve Fregeově díle.
    • Gottlob Frege (1902), Dopis Russellovi s komentářem van Heijenoorta, strany 126–128.
    • Bertrand Russell (1908), Matematická logika založená na teorii typů, s komentářem od Willard Quine, strany 150–182.
    • Emil Post (1921), Úvod do obecné teorie elementárních vět, s komentářem van Heijenoorta, strany 264–283.
  • Alfred North Whitehead a Bertrand Russell (1910–1913, 1927 2. vydání dotisk 1962), Principia Mathematica do * 56, Cambridge na University Press, London UK, bez čísla ISBN nebo amerického katalogového čísla karty.
  • Ludwig Wittgenstein (publikováno v roce 2009), Hlavní díla: Vybrané filozofické spisy, HarperCollins, New York. ISBN  978-0-06-155024-9. Wittgenstein's (1921 v angličtině), Tractatus Logico-Philosophicus, strany 1–82.

Další čtení

  • W. Farmer, „Sedm ctností teorie jednoduchého typu“, Journal of Applied Logic, Sv. 6, č. 3 (září 2008), s. 267–286.