Intuitionistická Teorie Typů

2023 Autor: Noah Black | [email protected]. Naposledy změněno: 2023-11-26 16:06

Vstupní navigace

• Obsah příspěvku
• Bibliografie
• Akademické nástroje
• Náhled PDF přátel
• Informace o autorovi a citaci
• Zpět na začátek

Intuitionistická teorie typů

První publikováno 12. února 2016; věcná revize po 8. červnu 2020

Intuitionistická typová teorie (také konstruktivní typová teorie nebo Martin-Löfova typová teorie) je formální logický systém a filozofický základ pro konstruktivní matematiku. Jedná se o systém v plném měřítku, jehož cílem je hrát podobnou roli pro konstruktivní matematiku jako Zermelo-Fraenkelova teorie teorií pro klasickou matematiku. Je založen na principu propozic typu a objasňuje Brouwer-Heyting-Kolmogorovovu interpretaci intuicionistické logiky. Rozšiřuje tuto interpretaci na obecnější nastavení teorie intuicionistického typu a poskytuje tak obecnou představu nejen o tom, co je konstruktivní důkaz, ale také o tom, co je konstruktivní matematický objekt. Hlavní myšlenkou je, že matematické pojmy, jako jsou prvky, množiny a funkce, jsou vysvětleny pomocí pojmů programování, jako jsou datové struktury,datové typy a programy. Tento článek popisuje formální systém teorie intuicionistického typu a jeho sémantické základy.

V tomto příspěvku nejprve uvádíme přehled nejdůležitějších aspektů teorie intuicionistického typu - jakési „rozšířené abstrakt“. Je určen pro čtenáře, který je s teorií již poněkud obeznámen. Oddíl 2 na druhé straně je určen pro čtenáře, který je novým v intuicionistické teorii typů, ale je obeznámen s tradiční logikou, včetně výrokové a predikátové logiky, aritmetiky a teorie množin. Zde neformálně představujeme několik aspektů, které odlišují intuicionistickou teorii typů od těchto tradičních teorií. V části 3 představujeme základní verzi teorie, blíže k první publikované verzi Martina-Löfa z roku 1972. Čtenář, který zaujal neformálností oddílu 2, nyní podrobně uvidí, jak je tato teorie vybudována. Oddíl 4 pak představuje řadu důležitých rozšíření základní teorie. Zejména,zdůrazňuje hlavní roli induktivních (a induktivně-rekurzivních) definic. Část 5 představuje základní filozofické myšlenky včetně teorie významu vyvinuté Martinem-Löfem. Zatímco část 5 se týká filosofie a základů, oddíl 6 poskytuje přehled matematických modelů teorie. V kapitole 7 konečně popisujeme několik důležitých variací jádra „intenzivní“teorie Martin-Löfa popsané v oddílech 3 a 4.popisujeme několik důležitých variací jádra „intenční“teorie Martin-Löfa popsané v oddílech 3 a 4.popisujeme několik důležitých variací jádra „intenční“teorie Martin-Löfa popsané v oddílech 3 a 4.

• 1. Přehled

• 2. Propozice jako typy

  • 2.1 Intuitionistická teorie typů: nový způsob pohledu na logiku?
  • 2.2 Kari-Howardova korespondence
  • 2.3 Sady důkazních objektů
  • 2.4 Závislé typy
  • 2.5 Propozice jako typy v intuitivní teorii typů

• 3. Základní teorie intuitivního typu

  • 3.1 Rozsudky
  • 3.2 Formuláře soudů
  • 3.3 Pravidla odvození
  • 3.4 Intuitionistic Predicate Logic
  • 3.5 Přírodní čísla
  • 3.6 Vesmír malých typů
  • 3.7 Propoziční identita
  • 3.8 Axiom of Choice je věta

• 4. Rozšíření

  • 4.1 Logický rámec
  • 4.2 Bývalý typ obecné identity
  • 4.3 Dobře založené stromy
  • 4.4 Iterativní sady a CZF
  • 4.5 Induktivní definice
  • 4.6 Indukčně-rekurzivní definice

• 5. Význam Vysvětlení

  • 5.1 Výpočet do kanonické podoby
  • 5.2 Význam kategorických soudů
  • 5.3 Význam hypotetických soudů

• 6. Matematické modely

  • 6.1 Kategorické modely
  • 6.2 Set-teoretický model
  • 6.3 Realizovatelné modely
  • 6.4 Model normálních formulářů a kontrola typu

• 7. Varianty teorie

  • 7.1 Teorie rozšíření typu
  • 7.2 Univalentní základy a teorie typů homotopií
  • 7.3 Částečná a nestandardní teorie typů
  • 7.4 Předpokládaná teorie typů
  • 7.5 Důkazní asistenti
• Bibliografie
• Akademické nástroje
• Další internetové zdroje
• Související záznamy

1. Přehled

Začínáme ptačí pohledem na některé důležité aspekty intuicionistické teorie typů. Čtenáři, kteří nejsou s touto teorií obeznámeni, ji mohou při prvním čtení raději vynechat.

Počátky intuicionistické teorie typů jsou Brouwerův intuicionismus a Russellova typová teorie. Stejně jako klasická církevní jednoduchá teorie typů, je založena na lambda počtu s typy, ale liší se od ní v tom, že je založena na principu propozice typu, který objevil Curry (1958) pro výrokovou logiku a rozšířil se na predikátovou logiku Howard (1980) a de Bruijn (1970). Toto rozšíření bylo možné zavedením indexovaných rodin typů (závislých typů) pro reprezentaci predikátů predikátové logiky. Tímto způsobem mohou být všechny logické spojky a kvantifikátory interpretovány formátory typu. V intuicionistické teorii typů se přidávají další typy, jako je typ přirozených čísel, typ malých typů (vesmír) a typ dobře založených stromů. Výsledná teorie obsahuje intuitionistickou teorii čísel (Heytingova aritmetika) a mnohem více.

Teorie je formulována v přirozené dedukci, kde jsou pravidla pro každý typ bývalého typu klasifikována jako pravidla formace, zavedení, eliminace a rovnosti. Tato pravidla vykazují určité symetrie mezi úvodními a vylučovacími pravidly po Gentzenově a Prawitzově léčbě přirozené dedukce, jak je vysvětleno v záznamu o důkazově teoretické sémantice.

Prvky výroků, pokud jsou interpretovány jako typy, se nazývají korektury. Když jsou do přirozeného dedukčního počtu přidány korektury, stává se typovaným lambda kalkulem se závislými typy, což rozšiřuje původní církevní typovaný lambda kalkul. Pravidla rovnosti jsou pravidla výpočtu pro podmínky tohoto počtu. Každá funkce definovatelná v teorii je úplná a porovnatelná. Intuitionistická typová teorie je tedy typizovaný funkční programovací jazyk s neobvyklou vlastností, kterou všechny programy ukončují.

Intuitionistická typová teorie není jen formálním logickým systémem, ale také poskytuje komplexní filozofický rámec pro intuicionismus. Jde o interpretovaný jazyk, v němž hraje zásadní roli rozlišení mezi prokázáním rozsudku a důkazem (Sundholm 2012). Rámec objasňuje Brouwer-Heyting-Kolmogorovovu interpretaci intuicionistické logiky a rozšiřuje ji na obecnější nastavení teorie intuicionistického typu. Přitom poskytuje obecnou představu nejen o tom, co je konstruktivní důkaz, ale také o tom, co je konstruktivní matematický objekt. Význam rozsudků teorie intuicionistického typu je vysvětlen na základě výpočtů kanonických forem typů a termínů. Tyto neformální,intuitivní vysvětlení významu je „předmematatická“a měla by být v kontrastu s formálními matematickými modely vyvinutými uvnitř standardního matematického rámce, jako je teorie množin.

Tato teorie významu také ospravedlňuje řadu induktivních, rekurzivních a induktivně-rekurzivních definic. I když lze ospravedlnit teoreticky silné představy, jako jsou analoga určitých velkých kardinálů, systém je považován za prediktivní. Nevysvětlující definice druhu nalezené v logice vyššího řádu, teorii intuicionistických množin a teorie toposů nejsou součástí teorie. Markovův princip neexistuje, a proto se teorie liší od ruského konstruktivismu.

Alternativní formální logický systém pro prediktivní konstruktivní matematiku je konstruktivní teorie Myhlera a Aczela Zermelo-Fraenkelova teorie (CZF). Tato teorie, která je založena na intuicionální predikátové logice prvního řádu a oslabuje některé axiomy klasické teorie teorií Zermelo-Fraenkel, má přirozenou interpretaci v intuicionistické teorii typů. Vysvětlení významu Martin-Löfa tak také nepřímo tvoří základ pro CZF.

Varianty intuicionistické teorie typů jsou základem několika široce používaných asistentů, včetně NuPRL, Coq a Agda. Tito asistenti důkazu jsou počítačové systémy, které byly použity pro formalizaci velkých a složitých důkazů matematických vět, jako je Four Color Theorem v teorii grafů a Feit-Thompsonova věta v teorii konečných skupin. Byly také použity k prokázání správnosti realistického kompilátoru C (Leroy 2009) a dalšího počítačového softwaru.

Filozoficky a prakticky je intuicionální teorie typů základním rámcem, ve kterém je konstruktivní matematika a počítačové programování v hlubokém smyslu stejné. Tento bod zdůraznil (Gonthier 2008) v příspěvku, v němž popisuje svůj důkaz o čtyřech barevných větech:

Přístup, který se osvědčil pro tento důkaz, spočíval v přeměně téměř každého matematického konceptu na datovou strukturu nebo program v systému Coq, čímž byl celý podnik převeden na ověřování programu.

2. Propozice jako typy

2.1 Intuitionistická teorie typů: nový způsob pohledu na logiku?

Intuitionistická teorie typů nabízí nový způsob analýzy logiky, zejména zavedením explicitních důkazních objektů. To poskytuje přímou výpočetní interpretaci logiky, protože existují pravidla pro výpočet pro objekty korektury. Pokud jde o expresivní sílu, lze intuiciistickou teorii typů považovat za rozšíření logiky prvního řádu, stejně jako logiku vyššího řádu, ale prediktivní.

2.1.1 Teorie typu

Russell vyvinul teorii typu v reakci na objev paradoxu v teorii naivních setů. Ve své rozvětvené teorii typů jsou matematické objekty klasifikovány podle jejich typů: typ propozic, typ objektů, typ vlastností objektů atd. Když Church vyvinul svou jednoduchou teorii typů na základě typizované verze svého lambda calculus dodal pravidlo, že mezi jakýmikoli dvěma typy teorie existuje určitý druh funkcí. Intuitionistická teorie typů dále rozšiřuje jednoduše zadaný lambda počet se závislými typy, tj. Indexovanými rodinami typů. Příkladem je rodina typů (n) - n-tic, která jsou indexována pomocí (n).

Typy se v programování používají velmi dlouho. Počáteční programovací jazyky na vysoké úrovni představovaly typy celých čísel a čísel s pohyblivou řádovou čárkou. Moderní programovací jazyky mají často bohaté typy systémů s mnoha konstrukcemi pro vytváření nových typů. Intuitionistická typová teorie je funkční programovací jazyk, ve kterém je typový systém tak bohatý, že prakticky jakoukoli myslitelnou vlastnost programu lze vyjádřit jako typ. Typy tak mohou být použity jako specifikace úkolu programu.

2.1.2 Intuitivní logika s korekturními objekty

Brouwerova analýza logiky ho vedla k intuicionistické logice, která odmítá zákon vyloučeného středu a zákon dvojité negace. Tyto zákony nejsou platné v intuicionistické teorii typů. Neobsahuje tedy klasickou (peano) aritmetiku, ale pouze intuicionální (heyting) aritmetiku. (Je další věcí, že Peano aritmetika může být interpretována v Heyting aritmetice interpretací dvojité negace, viz položka o intuicionistické logice.)

Uvažujme teorém intuicionistické aritmetiky, jako je věta o rozdělení

) forall m, n. m> 0 / supset / existuje q, r. mq + r = n / wedge m> r)

Formálním důkazem (v obvyklém smyslu) této věty je posloupnost (nebo strom) vzorců, kde poslední (kořenový) vzorec je věta a každý vzorec v posloupnosti je buď axiom (list), nebo výsledek použití pravidla odvození na některé dřívější (vyšší) vzorce.

Když je věta o rozdělení prokázána v intuicionistické teorii typů, nebudujeme pouze formální důkaz v obvyklém smyslu, ale také konstrukci (nebo důkazový objekt) „((divi))“, která svědčí o pravdě věty. Píšeme

) divi: / forall m, n {:} N. \, m> 0 / supset / existuje q, r {:} N. \, mq + r = n / wedge m> r)

vyjádřit, že (divi) je důkazním objektem pro teorém divize, tj. prvek typu představující divizní teorém. Když jsou návrhy reprezentovány jako typy, kvantifikátor (forall) je identifikován pomocí bývalého závislého funkčního prostoru (nebo obecného kartézského produktu) (Pi), kvantifikátoru (existuje) - se závislými páry zadejte bývalý (nebo obecný disjunktní součet) (Sigma), spojení (wedge) s kartézským součinem (times), vztah identity = s typem bývalý (I) zkušebních objektů identit a větší než vztah (>) s typem bývalého (GT) důkazních objektů větších než příkazů. Pomocí „notace typu“tedy píšeme

) divi: / Pi m, n {:} N. \, / GT (m, 0) rightarrow / Sigma q, r {:} N. \, / I (N, mq + r, n) times / GT (m, r))

vyjádřit, že korektní objekt „(divi)“je funkce, která mapuje dvě čísla (m) a (n) a korektní objekt (p) svědčící o tom (m> 0) na čtyřnásobek ((q, (r, (s, t)))), kde (q) je kvocient a (r) je zbytek získaný dělením (n) na (m). Třetí komponenta (s) je objektem důkazu svědčící o tom, že (mq + r = n) a čtvrtá komponenta (t) je objektem důkazu svědčícím (m> r).

Důležité je, že (divi) není jen funkcí v klasickém smyslu; je to také funkce v intuicionálním smyslu, tj. program, který počítá výstup ((q, (r, (s, t)))), pokud je zadán (m), (n), (p) jako vstupy. Tento program je termín v lambda počtu se speciálními konstantami, to je program ve funkčním programovacím jazyce.

2.1.3 Rozšíření predikátové logiky prvního řádu

Intuitionistickou teorii typů lze považovat za rozšíření logiky prvního řádu, stejně jako logika vyššího řádu je rozšíření logiky prvního řádu. V logice vyššího řádu najdeme některé jednotlivé domény, které lze interpretovat jako jakékoli sady, které se nám líbí. Pokud jsou v podpisu relační konstanty, lze je interpretovat jako jakýkoli vztah mezi množinami interpretujícími jednotlivé domény. Kromě toho můžeme kvantifikovat vztahy a vztahy vztahů atd. Logiku vyššího řádu můžeme považovat za logiku prvního řádu vybavenou způsobem zavedení nových domén kvantifikace: if (S_1, / ldots, S_n) jsou oblasti kvantifikace, potom ((S_1, / ldots, S_n)) je nová doména kvantifikace sestávající ze všech n-arylových vztahů mezi doménami (S_1, / ldots, S_n). Logika vyššího řádu má přímou interpretaci teoretických množin, kde ((S_1, / ldots, S_n)) je interpretováno jako mocenská množina (P (A_1 / times / cdots / times A_n)) kde (A_i) je interpretace (S_i) pro (i = 1, / ldots, n). Toto je druh logiky vyššího řádu nebo jednoduché teorie typů, které zavedl Ramsey, Church a další.

Intuitionistickou teorii typů lze prohlížet podobným způsobem, pouze zde jsou možnosti pro zavedení domén kvantifikace bohatší, lze použít (Sigma, / Pi, +, / I) k vytvoření nových ze starých. (Část 3.1; Martin-Löf 1998 [1972]). Intuitionistická typová teorie má také přímou teoretickou interpretaci, kde (Sigma), (Pi) atd. Jsou interpretovány jako odpovídající set-teoretické konstrukce; viz. níže. Do intuicionistické teorie typů můžeme přidat nespecifikované jednotlivé domény stejně jako v HOL. Jsou interpretovány jako sady jako pro HOL. Nyní vykazujeme rozdíl od HOL: v intuicionistické teorii typů můžeme zavést nespecifikované rodinné symboly. Můžeme představit (T) jako rodinu typů v jednotlivých doménách (S):

[T (x); { rm type}; (x {:} S).)

Pokud je (S) interpretováno jako (A), (T) lze interpretovat jako jakoukoli rodinu sad indexovaných pomocí (A). Jako nematematický příklad můžeme uvést, že binární vztah miluje mezi členy individuální domény lidí následujícím způsobem. Představte binární rodinu Loves nad doménou People

[{ rm Loves} (x, y); { rm typ}; (x {:} { rm People}, y {:} { rm People}).)

Interpretací může být jakákoli rodina množin (B_ {x, y}) ((x {:} A), (y {:} A)). Jak to zahrnuje standardní pojetí vztahu? Předpokládejme, že máme binární vztah (R) na (A) ve známém množinově teoretickém smyslu. Můžeme vytvořit binární rodinu, která tomu odpovídá

[B_ {x, y} = / begin {cases} {0 } & / text {if} R (x, y) text {hold} / \ varnothing & / text {if} R (x, y) text {je nepravdivý.} end {případech})

Nyní jasně (B_ {x, y}) je neprázdné, pokud a pouze pokud (R (x, y)) platí). (Mohli jsme si vybrat jakýkoli jiný prvek z našeho množinového teoretického vesmíru než 0, abychom ukázali pravdu.) Takže z jakéhokoli vztahu můžeme vytvořit rodinu, jejíž pravda (x, y) je ekvivalentní (B_ {x, y})) není prázdný. Všimněte si, že tato interpretace nezajímá, co je důkazem pro (R (x, y)), jen že to drží. Připomeňme si, že intuicionistická teorie typů interpretuje výroky jako typy, takže (p {:} { rm Loves} ({ rm John}, { rm Mary})) znamená, že ({ rm Loves} ({ rm) John}, { rm Mary})) je pravda.

Interpretace vztahů jako rodin umožňuje sledování důkazů nebo důkazů, které drží (R (x, y)), ale můžeme se také rozhodnout je ignorovat.

V Montague sémantice, logika vyššího řádu je používána dát sémantiku přirozeného jazyka (a příklady jak nahoře). Ranta (1994) představil myšlenku namísto toho využít intuitionistickou teorii typů k lepšímu zachycení struktury vět pomocí závislých typů.

Na rozdíl od toho, jak by se matematická souvislost (>) mezi přirozenými čísly řešila v intuicionistické teorii typů? Nejprve potřebujeme typ čísel (N). V zásadě bychom mohli zavést nespecifikovanou jednotlivou doménu (N), a pak přidat axiomy stejně jako v logice prvního řádu, když jsme nastavili axiomy pro Peano aritmetiku. To by nám však neposkytlo žádoucí výpočetní výklad. Jak je vysvětleno níže, stanovujeme úvodní pravidla pro konstrukci nových přirozených čísel v (N) a pravidla pro eliminaci a výpočet pro definování funkcí na (N) (rekurzí). Vztah standardní objednávky (>) by měl vyhovovat

) mbox {(x> y) iff existuje (z {:} N), takže (y + z + 1 = x)}.)

Pravá ruka je interpretována jako (Sigma z {:} N. \, / I (N, y + z + 1, x)) v intuicionistické teorii typů, a my to bereme jako definici vztahu (>). ((+) je definováno rekurzivními rovnicemi, (I) je konstrukce typu identity). Nyní jsou všechny vlastnosti (>) určeny uvedenými úvodními a eliminačními a výpočtovými pravidly pro (N).

2.1.4 Logika s několika formami úsudku

Typový systém intuicionistické teorie typů je velmi expresivní. Důsledkem je, že dobře tvarovaná forma již není pouhou analýzou, je třeba něco dokázat. Dobře tvarovaná forma je jednou z forem intuice socialistické teorie. Dobrá typičnost termínu s ohledem na typ je další. Kromě toho existují rozsudky pro rovnost typů a termínů. Toto je další způsob, kterým se intuicionistická typová teorie liší od běžné logiky prvního řádu se zaměřením na jediný úsudek vyjadřující pravdivost výroku.

2.1.5 Sémantika

Zatímco standardní představení logiky prvního řádu by při definování pojmu model následovalo Tarského, teorie intuicionistického typu navazuje na tradici brouwerovské teorie významu, jak ji dále rozvíjí Heyting a Kolmogorov, tzv. Interpretace logiky BHK. Klíčovým bodem je, že důkaz implikace (A / supset B) je metoda, která transformuje důkaz (A) na důkaz (B). V intuicionistické teorii typů je tato metoda formálně reprezentována programem (f {:} A / supset B) nebo (f {:} A / rightarrow B): typ důkazů implikace (A / supset B) je typ funkcí, které mapují důkazy (A) na důkazy (B).

Navíc, zatímco Tarski sémantika je obvykle prezentována meta-matematicky a předpokládá teorii množin, Martin-Löfova významová teorie intuicionistického typu by měla být chápána přímo a „pre-matematicky“, to znamená, aniž by předpokládala meta-jazyk, jako je teorie množin.

2.1.6 Funkční programovací jazyk

Čtenáři s pozadím v lambda počtu a funkčním programováním mohou získat alternativní první aproximaci intuicionistické teorie typů přemýšlením o ní jako o typickém funkčním programovacím jazyce ve stylu Haskell nebo o jednom z dialektů ML. Od těchto se však liší ve dvou zásadních aspektech: (i) má závislé typy (viz níže) a (ii) končí všechny typovatelné programy. (Všimněte si, že intuicionistická teorie typů ovlivnila nedávná rozšíření Haskellu s generalizovanými algebraickými datovými typy, které někdy mohou hrát podobnou roli jako indukčně definované závislé typy.)

2.2 Kari-Howardova korespondence

Jak již bylo zmíněno, princip, že

návrh je typem jeho důkazů.

je základem intuicionistické teorie typů. Tento princip je také známý jako Curry-Howardova korespondence nebo dokonce Curry-Howardův izomorfismus. Curry objevil shodu mezi implikačním fragmentem intuicionistické logiky a jednoduše napsaným lambda-kalkulem. Howard rozšířil tuto korespondenci na predikátovou logiku prvního řádu. V intuicionistické teorii typů se tato korespondence stává identifikací výroků a typů, která byla rozšířena o kvantifikaci nad vyššími typy a více.

2.3 Sady důkazních objektů

Jaké jsou tedy tyto důkazní objekty? Neměli bychom je považovat za logické derivace, ale spíše za nějaký (strukturovaný) symbolický důkaz, že něco je pravda. Dalším výrazem pro takový důkaz je „tvůrce pravdy“.

Jako poněkud hrubé první přiblížení je poučné nahradit v této korespondenci typy obyčejnými množinami. Definujte množinu (E_ {m, n}), v závislosti na (m, n / in {{ mathbb N}}), pomocí:

) E_ {m, n} = / left { begin {array} {ll} {0 } & / mbox {if (m = n)} / \ varnothing & / mbox {if (m / ne n).} end {array} right.)

Pak (E_ {m, n}) je neprázdný přesně, když (m = n). Množina (E_ {m, n}) odpovídá výroku (m = n) a číslo (0) je objektem důkazu (tvůrce pravdy), který obývá sady (E_ {m, m}).

Zvažte tvrzení, že (m) je sudé číslo vyjádřené jako vzorec (existuje n / v {{ mathbb N}}. M = 2n). Můžeme sestavit množinu důkazních objektů odpovídající tomuto vzorci pomocí obecné operace množiny teoretických součtů. Předpokládejme, že (A_n) ((n / in {{ mathbb N}})) je rodina sad. Pak je jeho disjunktní suma dána množinou párů

[(Sigma n / in {{ mathbb N}}) A_n = {(n, a): n / in {{ mathbb N}}, a / in A_n }.)

Pokud použijeme tuto konstrukci na rodinu (A_n = / E_ {m, 2n}), uvidíme, že ((Sigma n / in {{ mathbb N}})) E_ {m, 2n}) je nonempty přesně, když existuje (n / in {{ mathbb N}}) s (m = 2n). Pomocí obecné operace teorie teoretických množin ((Pi n / in {{ mathbb N}}) A_n) můžeme podobně získat množinu odpovídající univerzálně kvantifikované nabídce.

2.4 Závislé typy

V intuicionistické teorii typů existují primitivní formátoři (Sigma) a (Pi) pro obecné součty a produkty a (I) pro typy identity, analogické výše popsaným množinám teoretických konstrukcí. Typ identity (I (N, m, n)) odpovídající sadě (E_ {m, n}) je příkladem závislého typu, protože závisí na (m) a (n). Nazývá se také indexovaná rodina typů, protože se jedná o rodinu typů indexovanou pomocí (m) a (n). Podobně můžeme vytvořit obecný disjunktní součet (Sigma x {:} A. \, B) a obecný kartézský součin (Pi x {:} A. \, B) takové rodiny typů (B) indexováno pomocí (x {:} A), odpovídající výše uvedené teoretické součtu a operacím produktu.

Závislé typy lze také definovat pomocí primitivní rekurze. Příkladem je typ (n) - n-tice (A ^ n) prvků typu (A) a indexovaných podle (n {:} N) definovaných rovnicemi

) begin {zarovnat *} A ^ 0 & = 1 \\ A ^ {n + 1} & = A / krát A ^ n / end {zarovnat *})

kde (1) je typ jednoho prvku a (times) označuje kartézský produkt dvou typů. Poznamenáváme, že závislé typy zavádějí výpočet v typech: výše definující pravidla jsou pravidla výpočtu. Například výsledek výpočtu (A ^ 3) je (A / times (A / times (A / times 1))).

2.5 Propozice jako typy v intuitivní teorii typů

S návrhy jako typy se predikáty stávají závislými typy. Například predikát (mathrm {Prime} (x)) se stává typem důkazů, že (x) je prvotní. Tento typ závisí na (x). Podobně (x <y) je typ důkazů, že (x) je menší než (y).

Podle Curryho-Howardovy interpretace propozic jako typů jsou logické konstanty interpretovány jako formátoři typů:

) begin {Zarovnat *} bot & = / varnothing \\ / top & = 1 \\ A / vee B & = A + B \\ A / wedge B & = A / times B \\ A / supset B & = A / rightarrow B \\ / existuje x {:} A. \, B & = / Sigma x {:} A. \, B \\ / forall x {:} A. \, B & = / Pi x {:} A. \, B / end {zarovnat *})

kde (Sigma x {:} A. \, B) je disjunktní součet (A) - indexované rodiny typů (B) a (Pi x {:} A. \, B) je jeho kartézský produkt. Kánonické prvky (Sigma x {:} A. \, B) jsou páry ((a, b)) takové, že (a {:} A) a (b {:} B [x: = a]) (typ získaný nahrazením všech volných výskytů (x) v (B) za (a)). Prvky (Pi x {:} A. \, B) jsou (kompatibilní) funkce (f) takové, že (f \, a {:} B [x: = a]), kdykoli (a {:} A).

Zvažte například tento návrh

) begin {equation} forall m {:} N. \, / existuje n {:} N. \, m / lt n / wedge / mathrm {Prime} (n) tag {1} label {prop1} end {rovnice})

vyjadřující, že existují libovolně velké prvočísla. Podle interpretace Curryho-Howarda se z toho stane typ (Pi m {:} N. \, / Sigma n {:} N. \, m / lt n / times / mathrm {Prime} (n)) funkcí, které mapují číslo (m) na trojici ((n, (p, q))), kde (n) je číslo, (p) je důkaz, že (m / lt n) a (q) je důkaz, že (n) je prvořadý. Toto je princip důkazů jako programů: konstruktivní důkaz, že existují libovolně velké prvočísla, se stává programem, který vzhledem k tomu, že libovolné číslo produkuje větší prvočíslo, spolu s důkazy o tom, že je skutečně větší a skutečně prvočíselný.

Povšimněte si, že důkaz, který vychází z rozporu z předpokladu, že existuje největší prvočíslo, není konstruktivní, protože výslovně nedává způsob, jak spočítat ještě větší prvočíslo. Abychom dokázali tento důkaz proměnit v konstruktivní, musíme výslovně ukázat, jak postavit větší prvočíslo. (Protože výrok (ref {prop1}) výše je vzorec (Pi ^ 0_2), můžeme například použít Friedmanův A-překlad k tomu, aby se takový důkaz v klasické aritmetice proměnil v důkaz v intuicionální aritmetice, a tedy v důkaz v intuicionistické teorii typů.)

3. Základní teorie intuitivního typu

Nyní představujeme základní verzi teorie intuicionistického typu, která úzce souvisí s první verzí teorie představenou Martinem-Löfem v roce 1972 (Martin-Löf 1998 [1972]). Kromě výše popsaných typů pro tvorbu Curryho-Howardovy interpretace typizované intuicionální predikátové logiky máme dva typy: typ (N) přirozených čísel a typ (U) malých typů.

Výsledná teorie může ukázat, že obsahuje intuicionální teorii čísel (HA) (Heytingova aritmetika), Gödelův systém (T) primitivních rekurzivních funkcí vyššího typu a teorii (HA ^ / omega). Heytingovy aritmetiky vyššího typu.

Tato základní intuicionistická typová teorie není jen původní, ale možná i minimální verze, která vykazuje základní rysy teorie. Pozdější rozšíření o primitivní typy identity, dobře založené typy stromů, hierarchie vesmíru a obecné představy o induktivních a induktivně-rekurzivních definicích zvýšily důkazní teoretickou sílu teorie a také ji učinily pohodlnějším pro programování a formalizaci matematiky. Například přidáním dobře založených stromů můžeme interpretovat Konstruktivní teorii množin Zermelo-Fraenkel (CZF) Aczel (1978 [1977]). Budeme však čekat do další části, abychom popsali tato rozšíření.

3.1 Rozsudky

V Martin-Löf (1996) je představena obecná filosofie logiky, kde se tradiční pojetí úsudku rozšiřuje a má ústřední postavení. Rozsudek již není pouhým potvrzením nebo odmítnutím výroku, ale obecným aktem poznání. Při matematickém uvažování činíme úsudky o matematických objektech. Jednou z forem úsudku je prohlásit, že některé matematické tvrzení je pravdivé. Další formou úsudku je konstatovat, že něco je matematický objekt, například množina. Logická pravidla poskytují metody pro vytváření správných rozsudků z předchozích rozsudků. Rozsudky získané těmito pravidly mohou být prezentovány ve stromové podobě

) infer [r_4] {J_8} { infer [r_1] {J_3} {J_1 & J_2} & / infer [r_3] {J_7} { infer [r_5] {J_5} {J_4} & J_6}}]

nebo v sekvenční formě

• (1) (J_1 / quad / text {axiom})
• (2) (J_2 / quad / text {axiom})
• (3) (J_3 / quad / text {podle pravidla (r_1) od (1) a (2)})
• (4) (J_4 / quad / text {axiom})
• (5) (J_5 / quad / text {podle pravidla (r_2) od (4)})
• (6) (J_6 / quad / text {axiom})
• (7) (J_7 / quad / text {podle pravidla (r_3) z (5) a (6)})
• (8) (J_8 / quad / text {podle pravidla (r_4) od (3) a (7)})

Druhá forma je běžná v matematických argumentech. Taková posloupnost nebo strom tvořený logickými pravidly z axiomů je odvozením nebo demonstrací úsudku.

Odůvodnění prvního řádu může být předloženo pomocí jediného druhu úsudku:

výrok (B) je pravdivý pod hypotézou, že výroky (A_1, / ldots, A_n) jsou všechny pravdivé.

Tento hypotetický úsudek píšeme jako tzv. Gentzenovu sekvenci

[A_1, / ldots, A_n { vdash} B.)

Všimněte si, že toto je jediný rozsudek, který by neměl být zaměňován s odvozením rozsudku ({ vdash} B) z rozsudků ({ vdash} A_1, / ldots, { vdash} A_n). Když (n = 0), pak kategorický úsudek ({ vdash} B) uvádí, že (B) je pravda bez jakýchkoli předpokladů. Se sekvenčním zápisem se stává známým pravidlem spojovací úvod

) infer [(land I)] {A_1, / ldots, A_n { vdash} B / land C} {A_1, / ldots, A_n { vdash} B & A_1, / ldots, A_n { vdash} C}.)

3.2 Formuláře soudů

Teorie typu Martin-Löf má čtyři základní formy úsudků a je to mnohem komplikovanější systém než logika prvního řádu. Jedním z důvodů je, že v derivacích je přenášeno více informací kvůli identifikaci propozic a typů. Dalším důvodem je větší zapojení syntaxe. Například dobře vytvořené vzorce (typy) musí být generovány současně s prokazatelně pravdivými vzorci (obydlené typy).

Čtyři formy kategorického úsudku jsou

• (vdash A \; { rm type}), což znamená, že (A) je dobře tvarovaný typ,
• (vdash a {:} A), což znamená, že (a) má typ (A),
• (vdash A = A '), což znamená, že (A) a (A') jsou stejné typy,
• (vdash a = a '{:} A), což znamená, že (a) a (a') jsou stejné prvky typu (A).

Obecně je úsudek hypotetický, to znamená, že je učiněn v kontextu (Gamma), tj. V seznamu (x_1 {:} A_1, / ldots, x_n {:} A_n) proměnných, které se mohou vyskytnout bezplatně spolu s jejich příslušnými typy. Upozorňujeme, že typy v kontextu mohou záviset na proměnných dřívějších typů. Například (A_n) může záviset na (x_1 {:} A_1, / ldots, x_ {n-1} {:} A_ {n-1}). Čtyři formy hypotetických soudů jsou

• (Gamma / vdash A \; { rm type}), což znamená, že (A) je dobře konformovaný typ v kontextu (Gamma),
• (Gamma / vdash a {:} A), což znamená, že (a) má typ (A) v kontextu (Gamma),
• (Gamma / vdash A = A '), což znamená, že (A) a (A') jsou stejné typy v kontextu (Gamma),
• (Gamma / vdash a = a '{:} A), což znamená, že (a) a (a') jsou stejné prvky typu (A) v kontextu (Gamma).

Podle návrhu jako interpretace typů

) tag {2} label {analytic} vdash a {:} A)

lze chápat jako úsudek, že (a) je objektem důkazu (A). Když potlačíme tento objekt, dostaneme úsudek odpovídající tomu v běžné logice prvního řádu (viz výše):

) tag {3} label {syntetický} vdash A \; { rm true}.)

Poznámka 3.1. Martin-Löf (1994) tvrdí, že Kantův analytický úsudek a priori a syntetický úsudek a priori mohou být doloženy v logické oblasti ([analytic]) a ([syntetický]). V analytickém úsudku ([analytický]) je vše, co je potřeba k tomu, aby byl rozsudek zřejmý, výslovné. Pro jeho syntetickou verzi ([syntetický]) musí být poskytnuta možná komplikovaná důkazní konstrukce (a), aby byla zřejmá. Toto chápání analyticity a syntetičnosti má překvapivý důsledek, že „logické zákony v jejich obvyklé formulaci jsou všechny syntetické.“Martin-Löf (1994: 95). Jeho analýza dále dává:

„[…] Logika analytických úsudků, tj. Logika odvozování úsudků obou analytických forem, je úplná a rozhodnutelná, zatímco logika syntetických úsudků je neúplná a nerozhodnutelná, jak ukázal Gödel.“Martin-Löf (1994: 97).

Rozhodnutelnost dvou analytických úsudků ((vdash a {:} A) a (vdash a = b {:} A)) závisí na metamatematických vlastnostech teorie typů: silná normalizace a rozhodná kontrola typu.

Někdy také následující formy jsou výslovně považovány za soudy teorie:

• (Gamma \; { rm context}), což znamená, že (Gamma) je dobře tvarovaný kontext.
• (Gamma = / Gamma '), což znamená, že (Gamma) a (Gamma') jsou stejné kontexty.

Níže zkrátíme rozsudek (Gamma / vdash A \; { rm type}) jako (Gamma / vdash A) a (Gamma \; { rm context}) jako (Gamma / vdash.)

3.3 Pravidla odvození

Při stanovování pravidel použijeme písmeno (Gamma) jako meta-proměnné v kontextu, (A, B, / ldots) jako meta-proměnné v různých typech a (a, b, c, d, e, f, / ldots) jako meta-proměnné v rozmezí termínů.

První skupina odvozovacích pravidel jsou obecná pravidla včetně pravidel převzetí, nahrazení a formování kontextu. Existují také pravidla, která vyjadřují, že rovnost jsou ekvivalenční vztahy. Existuje mnoho takových pravidel a my ukazujeme jen obzvláště důležité pravidlo rovnosti typu, které je klíčové pro výpočet typů:

) frac { Gamma / vdash a {:} A / hspace {2em} Gamma / vdash A = B} { Gamma / vdash a {:} B})

Zbývající pravidla jsou specifická pro tvůrce typů. Jsou klasifikována jako pravidla formace, zavedení, eliminace a rovnosti.

3.4 Intuitionistic Predicate Logic

Pravidla dáváme pouze pro (Pi). Existují analogická pravidla pro jiné typy formovačů odpovídající logickým konstantám typizované predikátové logiky.

V následujícím výrazu (B [x: = a]) se rozumí termín získaný nahrazením výrazu (a) za každý volný výskyt proměnné (x) v (B) (vyhnutí se proměnnému zachycení).

(Pi) - formace.) frac { Gamma / vdash A / hspace {2em} Gamma, x {:} A / vdash B} { Gamma / vdash / Pi x {:} A. B}) (Pi) -úvod.) frac { Gamma, x {:} A / vdash b {:} B} { Gamma / vdash / lambda x. b {:} Pi x {:} A. B}) (Pi) - eliminace.) frac { Gamma / vdash f {:} Pi x {:} AB / hspace {2em} Gamma / vdash a {:} A} { Gamma / vdash f \, a {:} B [x: = a]}) (Pi) - rovnost.) frac { Gamma, x {:} A / vdash b {:} B / hspace {2em} Gamma / vdash a {:} A} { Gamma / vdash (lambda xb), a = b [x: = a] {:} B [x: = a]}) Toto je pravidlo (beta) - konverze. Můžeme také přidat pravidlo (eta) - konverze:) frac { Gamma / vdash f {:} Pi x {:} A. B} { Gamma / vdash / lambda x. f \, x = f {:} Pi x {:} A. B}.)

Kromě toho existují pravidla shodnosti, která vyjadřují, že operace zavedené pravidly formování, zavedení a eliminace zachovávají rovnost. Například pravidlo shody pro (Pi) je

) frac { Gamma / vdash A = A '\ hspace {2em} Gamma, x {:} A / vdash B = B'} { Gamma / vdash / Pi x {:} A. B = / Pi x {:} A '. B '}.)

3.5 Přírodní čísla

Stejně jako v Peano aritmetice jsou přirozená čísla generována 0 a následnou operací (s). Pravidlo eliminace uvádí, že toto jsou jediné možné způsoby, jak vygenerovat přirozené číslo.

Napíšeme (f (c) = / R (c, d, xy.e)) pro funkci, která je definována primitivní rekurzí na přirozené číslo (c) se základním případem (d) a krokem funkce (xy.e) (nebo alternativně (lambda xy.e)), která mapuje hodnotu (y) pro předchozí číslo (x {:} N) na hodnotu pro (s (x)). Všimněte si, že (R) je nový operátor vázající proměnné: proměnné (x) a (y) se stanou vázány v (e).

(N) - formace.) Gamma / vdash / N) (N) - úvod.) Gamma / vdash 0 {:} N / hspace {2em} frac { Gamma / vdash a {:} N} { Gamma / vdash s (a) {:} N}) (N) - eliminace.) frac { Gamma, x {:} N / vdash C / hspace {1em} Gamma / vdash c {:} N / hspace {1em} Gamma / vdash d {:} C [x: = 0] hspace {1em} Gamma, y {:} N, z {:} C [x: = y] vdash e {:} C [x: = s (y)]} { Gamma / vdash / R (c, d, yz.e) {:} C [x: = c]}) (N) - rovnost (ve vhodných prostorách).) begin {zarovnat *} R (0, d, yz.e) & = d {:} C [x: = 0] / \ R (s (a), d, yz.e) & = e [y: = a, z: = / R (a, d, yz.e)] {:} C [x: = s (a)] end {zarovnat *})

Pravidlo (N) - eliminace současně vyjadřuje typ funkce definované primitivní rekurzí a podle Curryho-Howardovy interpretace pravidlo matematické indukce: prokazujeme vlastnost (C) přirozeného čísla (x) indukcí na (x).

Gödelův systém (T) je v podstatě intuicionistická teorie typů s pouze formátory typu (N) a (A / rightarrow B) (typ funkcí od (A) do (B), což je zvláštní případ ((Pi x {:} A) B), kde (B) nezávisí na (x {:} A)). Protože v systému (T) nejsou žádné závislé typy, lze pravidla zjednodušit.

3.6 Vesmír malých typů

Martin-Löfova první verze teorie typů (Martin-Löf 1971a) měla axiom uvádějící, že existuje typ všech typů. Girard to dokázal nekonzistentně, když zjistil, že v této teorii lze zakódovat paradox Burali-Forti.

Aby překonal tuto patologickou nepředvídavost, ale stále si zachoval určitou expresivitu, Martin-Löf zavedl v roce 1972 vesmír malých typů uzavřených pod všemi formátory teorie, s výjimkou toho, že se sám neobsahuje (Martin- Löf 1998 [1972]). Pravidla jsou:

(U) - formace.) Gamma / vdash / U) (U) - úvod.) Gamma / vdash / varnothing {:} U / hspace {3em} Gamma / vdash 1 {:} U)) frac { Gamma / vdash A {:} U / hspace {2em} Gamma / vdash B {:} U} { Gamma / vdash A + B {:} U} hspace {3em} frac { Gamma / vdash A {:} U / hspace {2em} Gamma / vdash B {:} U} { Gamma / vdash A / times B {:} U})) frac { Gamma / vdash A {:} U / hspace {2em} Gamma / vdash B {:} U} { Gamma / vdash A / rightarrow B {:} U})) frac { Gamma / vdash A {:} U / hspace {2em} Gamma, x {:} A / vdash B {:} U} { Gamma / vdash / Sigma x {:} A. \, B {:} U} hspace {3em} frac { Gamma / vdash A {:} U / hspace {2em} Gamma, x {:} A / vdash B {:} U} { Gamma / vdash / Pi x {:} A. \, B {:} U})) Gamma / vdash / N {:} U) (U) - eliminace.) frac { Gamma / vdash A {:} U} { Gamma / vdash A})

Protože (U) je typ, můžeme pomocí (N) - eliminace definovat malé typy primitivní rekurzí. Například pokud (A: / U) můžeme definovat typ (n) - n-tice prvků v (A) takto:

[A ^ n = / R (n, 1, xy. A / krát y) {:} U)

Tento typově teoretický vesmír (U) je analogický s Grothendieckovým vesmírem v teorii množin, což je množina uzavřených pod všemi způsoby, jak lze sestavy sestavit v teorii množin Zermelo-Fraenkel. Existence Grothendieckova vesmíru nemůže být prokázána z obvyklých axiomů teorie teorií Zermelo-Fraenkel, ale potřebuje nový axiom.

V Martin-Löf (1975) je vesmír rozšířen na početnou hierarchii vesmírů

) U_0: / U_1: / U_2: / cdots.)

Tímto způsobem má každý typ typ, nejen každý malý typ.

3.7 Propoziční identita

Výše jsme uvedli rozsudek rovnosti

) tag {4} label {defeq} Gamma / vdash a = a '{:} A.)

Toto je obvykle nazýváno „definiční rovností“, protože to může být rozhodnuto normalizací výrazů (a) a (a ') a kontrolou, zda jsou normální formy identické. Tato rovnost je však úsudkem, a nikoli návrhem (typem), a proto nemůžeme takové úsudkové ekvity dokázat indukcí. Z tohoto důvodu musíme zavést výrokové typy identity. Například typ identity pro přirozená čísla (I (N, m, n)) lze definovat pomocí primitivní rekurze s hodnotou (U). Pak můžeme vyjádřit a prokázat Peano axiomy. Rovněž rozšiřující rovnost ufnctions lze definovat pomocí

) I (N / rightarrow / N, f, f ') = / Pi x {:} N. / I (N, f \, x, f '\, x).)

3.8 Axiom of Choice je věta

Následující forma axiomu volby je bezprostředním důsledkem BHK interpretace intuicionistických kvantifikátorů a je snadno prokázána v intuicionistické teorii typů:

[(Pi x {:} A. / Sigma y {:} B. C) rightarrow / Sigma f {:} (Pi x {:} A. B). C [y: = f \, x])

Důvod je ten, že (Pi x {:} A. / Sigma y {:} B. C) je typ funkcí, které mapují prvky (x {:} A) na páry ((y, z)) s (y {:} B) a (z {:} C). Funkce výběru (f) je získána vrácením první komponenty (y {:} B) této dvojice.

Možná je překvapivé, že intuicionistická typová teorie přímo potvrzuje axiom volby, protože tento axiom je z konstruktivního hlediska často považován za problematický. Možným vysvětlením tohoto stavu je to, že výše uvedené je axiomem volby pro typy a že typy nejsou obecně vhodnými konstruktivními aproximacemi množin v klasickém smyslu. Například můžeme v intuicionistické teorii typů reprezentovat reálné číslo jako Cauchyho posloupnost, ale množina reálných čísel není typem Cauchyho posloupnosti, ale typem Cauchyho posloupnosti až do rovnováhy. Obecněji řečeno, soubor v Bishopovy konstruktivní matematice je reprezentován typem (běžně nazývaným „preset“) spolu s ekvivalenčním vztahem.

Pokud jsou (A) a (B) vybaveny ekvivalenčními vztahy, není samozřejmě zaručeno, že volba funkce (f) výše je rozšíření v tom smyslu, že mapuje ekvivalentní prvek na ekvivalentní prvky. Toto je selhání extenzivní axiomy výběru, viz Martin-Löf (2009) pro analýzu.

4. Rozšíření

4.1 Logický rámec

Výše uvedené doplňuje popis základní verze teorie intuicionistického typu blízké popisu (Martin-Löf 1998 [1972]).

V roce 1986 Martin-Löf navrhl přeformulování intuitionistické teorie typů; viz expozice Nordström, Peterson a Smith (1990). Účelem bylo poskytnout kompaktnější formulaci, kde (lambda) a (Pi) jsou jediné proměnné vazebné operace. To je dnes považováno za hlavní verzi teorie. Je také základem asistenta Agda proof. Teorie z roku 1986 má dvě části:

• teorie typů (logický rámec);
• teorie množin (malé typy).

Poznámka 4.1. Všimněte si, že slovo „set“v logickém rámci se neshoduje s tím, jak se používá v biskupské konstruktivní matematice. Aby se zabránilo této záměně, typy se spolu s ekvivalenčními vztahy obvykle nazývají „setoidy“nebo „extenzivní sady“v intuicionistické teorii typů.

Logický rámec má pouze dva typy formátorů: (Pi x {:} A. B) (obvykle psaný ((x {:} A) B) nebo ((x {:} A) rightarrow B) ve formulaci logického rámce) a (U) (obvykle se nazývá (Set)). Pravidla pro (Pi x {:} A. B) (((x {:} A) rightarrow B)) jsou stejná jako výše uvedená pravidla (včetně (eta) - konverze). Pravidla pro (U) ((Set)) jsou stejná, kromě toho, že logický rámec stanoví uzavření pouze ve formaci typu (Pi).

Další formátoři malých typů („set formers“) jsou představeni v teorii množin. V formulaci logického rámce lze každou formaci, zavedení a vylučovací pravidlo vyjádřit jako typizaci nové konstanty. Například pravidla pro přirozená čísla se stanou

) begin {zarovnat *} N &: / Set, \\ 0 &: / N, \\ / s &: / N / rightarrow / N, \\ / R &: (C {:} N / rightarrow / Set) rightarrow C \, 0 / rightarrow ((x {:} N) rightarrow C \, x / rightarrow C \, (s \, x)) rightarrow (c {:} N) rightarrow C \, c. / end {zarovnat *})

kde jsme vynechali společný kontext (Gamma), protože typy těchto konstant jsou uzavřené. Všimněte si, že operátor rekurze (R) má první argument (C {:} N / rightarrow / Set) na rozdíl od původní formulace.

Kromě toho lze pravidla rovnosti vyjádřit jako rovnice

) begin {zarovnat *} R \, C \, d \, e \, 0 & = d {:} C \, 0 \\ / R \, C \, d \, e \, (s \, a) & = e \, a \, (R \, C \, d \, e \, a) {:} C \, (s \, a) end {zarovnat *})

za vhodných předpokladů.

V pokračování představíme několik rozšíření teorie typů. Abychom zachovali jednotnou prezentaci, nebudeme používat prezentaci logického rámce teorie typů, ale použijeme stejný zápis jako v části 2.

4.2 Bývalý typ obecné identity

Jak jsme zmínili výše, identitu v přirozených číslech lze definovat primitivní rekurzí. Vztahy s identitami na jiných typech lze také definovat v základní verzi intuicionistické teorie typů uvedené v části 2.

Martin-Löf (1975) však rozšířil intuiciistickou teorii typů o jednotný primitivní typ identity bývalý (I) pro všechny typy. Pravidla pro (I) vyjadřují, že vztah identity je indukčně generován důkazem reflexivity, kanonické konstanty zvané (r). (Všimněte si, že (r) byl kódován číslem 0 v úvodní prezentaci korekturních objektů v 2.3. Eliminačním pravidlem pro typ identity je zobecnění eliminace identity v predikátové logice a zavádí eliminační konstantu (J) Zde zobrazujeme formulaci způsobenou Paulinem-Mohringem (1993) než původní formulaci Martina-Löfa (1975). Pravidla odvození jsou následující.

(I) - formace.) frac { Gamma / vdash A / hspace {1em} Gamma / vdash a {:} A / hspace {1em} Gamma / vdash a '{:} A} { Gamma / vdash / I (A, a, a ')})

(I. Úvod.) frac { Gamma / vdash A / hspace {1em} Gamma / vdash a {:} A} { Gamma / vdash / r {:} I (A, a, a)})

(I) - eliminace.

) frac { Gamma, x {:} A, y {:} I (A, a, x) vdash C / hspace {1em} Gamma / vdash b {:} A / hspace {1em} Gamma / vdash c {:} I (A, a, b) hspace {1em} Gamma / vdash d {:} C [x: = a, y: = r]} { Gamma / vdash / J (c, d) {:} C [x: = b, y: = c]})

(I) - rovnost (za vhodných předpokladů).

) begin {zarovnat *} J (r, d) & = d / end {zarovnat *})

Všimněte si, že pokud (C) závisí pouze na (x: A) a ne na důkazu (y: / I (A, a, x)) (a také potlačujeme objekty důkazu), platí pravidlo (I) - eliminace obnovujeme pravidlo eliminace identity v predikátové logice.

Konstruováním modelu teorie typů, kde jsou typy interpretovány jako groupoidy (kategorie, kde všechny šipky jsou izomorfismy), Hofmann a Streicher (1998) ukázaly, že v intuicionistické teorii typů nelze prokázat, že všechny důkazy (I (A, a, b))) jsou identické. To se může jevit jako neúplnost teorie a Streicher navrhl nový axiom (K), ze kterého vyplývá, že všechny důkazy (I (A, a, b)) jsou totožné s (r).

Typ (I) - se často označuje jako typ intenzivní identity, protože nesplňuje princip rozšířenosti funkce. Intuitionistická typová teorie s intenčním typem identity se také často nazývá intenční intuicionistická typová teorie, která ji odlišuje od teorie extenzivního intuicionistického typu, která bude představena v části 7.1.

4.3 Dobře založené stromy

Druh dobře založených stromů ve tvaru (W x {:} A. B) byl představen v Martin-Löf 1982 (a v omezenější podobě Scottem 1970). Prvky (W x {:} A. B) jsou stromy různého a libovolného větvení: mění se, protože typ větvení (B) je indexován pomocí (x {:} A) a libovolný protože (B) může být libovolný. Tento typ je dán generalizovanou induktivní definicí, protože opodstatněné stromy mohou být nekonečně větvené. Můžeme uvažovat o (W x {:} A. B) jako o volném termínu algebra, kde každý (a {:} A) představuje termín konstruktor (sup \, a) s (možná nekonečný) arity (B [x: = a]).

(W) - formace.) frac { Gamma / vdash A / hspace {2em} Gamma, x {:} A / vdash B} { Gamma / vdash / W x {:} A. B}) (W) -úvod.) frac { Gamma / vdash a {:} A / hspace {2em} Gamma, y {:} B [x: = a] vdash b: Wx {:} A. B} { Gamma / vdash / sup (a, yb): / W x {:} A. B})

Vynecháme pravidla (W) - eliminace a (W) - rovnosti.

Přidání dobře založených stromů k intuicionistické teorii typů výrazně zvyšuje její důkazně teoretickou sílu (Setzer (1998)).

4.4 Iterativní sady a CZF

Důležitou aplikací dobře založených stromů je Aczelova (1978) konstrukce typově teoretického modelu teorie konstruktivních Zermelo Fraenkelů. Za tímto účelem definuje typ iteračních množin jako

) V = / W x {:} U. X.)

Nechť (A {:} U) je malý typ a (x {:} A / vdash M) je indexovaná rodina iteračních množin. Potom (sup (A, xM)), nebo s více sugestivním zápisem ({M / mid x {:} A }), je iterativní množina. Parafrázovat: iterativní množina je rodina iteračních množin indexovaných malým typem.

Všimněte si, že iterační množina je alt = "ikona sep man" /> Jak citovat tento záznam.

Náhled na PDF verzi tohoto příspěvku v Friends of the SEP Society.

Vyhledejte toto vstupní téma v projektu Internet Philosophy Ontology Project (InPhO).

Vylepšená bibliografie tohoto záznamu ve PhilPapers s odkazy na jeho databázi.

Další internetové zdroje

• Internetová encyklopedie filozofie: Konstruktivní matematika
• Scholarpedia: Computational Type Theory
• nLab: Teorie typů