Teorie Typu

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

Teorie typu

První publikováno 8. února 2006; věcná revize Út 17. července 2018

Téma teorie typů je zásadní jak v logice, tak v informatice. Omezujeme se zde, abychom načrtli některé aspekty, které jsou v logice důležité. Pro důležitost typů v informatice odkazujeme čtenáře například na Reynoldse 1983 a 1985.

• 1. Paradoxy a Russellovy teorie teorií
• 2. Teorie jednoduchého typu a (lambda) - počet
• 3. Ramifikovaná hierarchie a nevysvětlitelné principy
• 4. Zadejte Teorie / Teorie množin
• 5. Teorie typů / Teorie kategorií
• 6. Rozšíření typového systému, polymorfismus, paradoxy
• 7. Univalentní nadace
• Bibliografie
• Akademické nástroje
• Další internetové zdroje
• Související záznamy

1. Paradoxy a Russellovy teorie teorií

Teorie typů byla zavedena Russellem, aby se vypořádala s některými rozpory, které našel ve svém popisu teorie množin, a byla zavedena v „Dodatku B: Nauka o typech“Russella 1903. Tento rozpor byl získán analýzou Cantorovy věty. že žádné mapování

[F: X / rightarrow / Pow (X))

(kde (Pow (X)) je třída podtříd třídy (X)) může být adjektivní; to znamená, že (F) nemůže být takový, že každý člen (b) z (Pow (X)) je roven (F (a)) pro nějaký prvek (a) z (X). To lze vyjádřit „intuitivně“jako skutečnost, že existuje více podskupin (X) než prvků (X). Doklad o této skutečnosti je tak jednoduchý a základní, že se vyplatí poskytnout zde. Zvažte následující podmnožinu (X):

[A = {x / in X / mid x / not / in F (x) }.)

Tato podmnožina nemůže být v rozsahu (F). Pro if (A = F (a)), pro některé (a), pak

) begin {zarovnat} a / in F (a) a / text {iff} a / in A \& / text {iff} a / not / in F (a) end {zarovnat})

což je rozpor. Některé poznámky jsou v pořádku. Zaprvé, důkaz nepoužívá zákon vyloučeného středu, a je tedy platný intuicionálně. Za druhé, metoda, která se používá, zvaná diagonalizace, již byla přítomna v práci du Bois-Reymond pro budování reálných funkcí rostoucích rychleji než jakákoli funkce v dané posloupnosti funkcí.

Russell analyzoval, co se stane, pokud použijeme tuto větu na případ, kdy A je třída všech tříd, a připouští, že taková třída existuje. Poté byl veden, aby zvážil zvláštní třídu tříd, které nepatří sobě

) tag {*} R = {w / mid w / not / in w }.)

Pak to máme

[R / in R / text {iff} R / not / in R.)

Skutečně se zdá, že Cantor si byl vědom skutečnosti, že třídu všech sad nelze považovat za sadu.

Russell sdělil tento problém Fregeovi a jeho dopis se společně s Fregeovou odpovědí objevil ve van Heijenoort 1967. Je důležité si uvědomit, že formulace (*) se nevztahuje tak jako na Fregeův systém. Jak sám Frege napsal ve své odpovědi na Russella, výraz „predikát je predikován sám o sobě“není přesný. Frege rozlišoval mezi predikáty (pojmy) a objekty. Predikát (prvního řádu) se vztahuje na objekt, ale nemůže mít predikát jako argument. Přesná formulace paradoxu v Fregeově systému používá pojem rozšíření predikátu (P), který označujeme jako (varepsilon P). Samotné rozšíření predikátu je objekt. Důležitým axiomem V je:

) tag {Axiom V} varepsilon P = / varepsilon Q / equiv / forall x [P (x) equiv Q (x)])

Tento axiom tvrdí, že rozšíření (P) je totožné s rozšířením (Q) pouze tehdy, jsou-li (P) a (Q) materiálně ekvivalentní. Potom můžeme přeložit Russellův paradox (*) do Fregeova systému definováním predikátu

[R (x) text {iff} existuje P [x = / varepsilon P / wedge / neg P (x)])

To pak může být zkontrolováno pomocí Axiom V zásadním způsobem

[R (varepsilon R) equiv / neg R (varepsilon R))

a máme také rozpor. (Všimněte si, že pro definici predikátu (R) jsme použili implikativní existenciální kvantifikaci predikátů. Lze ukázat, že predikativní verze Fregeova systému je konzistentní (viz Heck 1996 a další upřesnění Ferreira 2002).

Z tohoto účtu je zřejmé, že ve Fregeově práci již byla představa typů: zde najdeme rozlišení mezi objekty, predikáty (nebo koncepty), predikáty predikátů atd. (Tento bod je zdůrazněn v Quine 1940.) Tato hierarchie je nazýván „rozšiřovací hierarchií“Russellem (1959) a jeho nezbytnost byla Russellem uznána jako důsledek jeho paradoxu.

2. Teorie jednoduchého typu a (lambda) - počet

Jak jsme viděli výše, rozlišení: objekty, predikáty, predikáty predikátů atd. Se zdají být dostačující k tomu, aby blokovaly Russellův paradox (a to uznal Chwistek a Ramsey). Nejprve popisujeme strukturu typu, jaká je v Principii, a později v této části představíme elegantní formulaci kvůli kostelu 1940 založenou na (lambda) - počtu. Typy lze definovat jako

1. (i) je typ jednotlivců
2. ((,)) je typ propozic
3. pokud (A_1, / ldots, A_n) jsou typy, pak ((A_1, / ldots, A_n)) je typ (n) - ary vztahů nad objekty příslušných typů (A_1, / ldots, A_n)

Například typ binárních vztahů nad jednotlivci je ((i, i)), typ binárních spojů je (((,), (,))), typ kvantifikátorů nad jednotlivci je ((i))).

Pro vytváření návrhů používáme tuto typovou strukturu: tedy (R (a_1, / ldots, a_n)) je návrh, pokud (R) je typu ((A_1, / ldots, A_n)) a (a_i) je typu (A_i) pro (i = 1, / ldots, n). Toto omezení znemožňuje vytvořit nabídku ve tvaru (P (P)): typ (P) by měl být ve tvaru ((A)) a (P) může být pouze být aplikován na argumenty typu (A), a proto nemůže být aplikován na sebe, protože (A) není stejné jako ((A)).

Jednoduchá teorie typů však není prediktivní: můžeme definovat objekt (Q (x, y)) typu ((i, i)) pomocí

) forall P [P (x) supset P (y)])

Předpokládejme, že máme dva jednotlivce (a) a (b), takže (Q (a, b)) platí. Můžeme definovat (P (x)) jako (Q (x, a)). Pak je jasné, že (P (a)) platí, protože to je (Q (a, a)). Proto platí také (P (b)). Ukázali jsme, že (Q (a, b)) implikuje (Q (b, a)).

Alternativní a jednodušší formulace, které si zachovávají pouze představu o třídách, třídách atd., Formuloval Gödel a Tarski. Ve skutečnosti tuto jednodušší verzi použil Gödel ve svém příspěvku z roku 1931 o formálně nerozhodnutelných propozicích. Objev nerozhodnutelných propozic mohl být motivován heuristickým argumentem, že je nepravděpodobné, že člověk může rozšířit teorém o úplnosti logiky prvního řádu na teorii typů (viz konec své přednášky na Königsbergu 1930 v Gödel Collected Work, Volume III). a Goldfarb 2005). Tarski měl verzi věty o definovatelnosti vyjádřenou v teorii typů (viz Hodges 2008). Viz Schiemer a Reck 2013.

Máme objekty typu 0, pro jednotlivce, objekty typu 1, pro třídy jednotlivců, objekty typu 2, pro třídy tříd jednotlivců atd. Funkce dvou nebo více argumentů, jako jsou vztahy, nemusí být zahrnuty mezi primitivní objekty, protože lze definovat vztahy jako třídy uspořádaných párů a uspořádané páry jako třídy tříd. Například uspořádaný pár jednotlivců a, b lze definovat jako ({ {a }, {a, b } }) kde ({x, y }) označuje třída, jejíž jediné prvky jsou (x) a (y). (Wiener 1914 navrhl podobné omezení vztahů ke třídám.) V tomto systému mají všechny propozice tvar (a (b)), kde (a) je znakem typu (n + 1) a (b) znak typu (n). Tento systém je tedy postaven na konceptu libovolné třídy nebo podmnožiny objektů dané domény a na skutečnosti, že kolekce všech podmnožin dané domény může tvořit novou doménu dalšího typu. Počínaje danou doménou jednotlivců je tento proces iterován. Jak je zdůrazněno například ve Scott 1993, v teorii množin je tento proces vytváření podskupin iterován do transfinitu.

V těchto verzích teorie typů, stejně jako v teorii množin, funkce nejsou primitivní objekty, ale jsou reprezentovány jako funkční vztah. Funkce sčítání je například reprezentována jako ternární vztah objektem typu ((i, i, i)). Elegantní formulace teorie jednoduchých typů, která ji rozšiřuje zavedením funkcí jako primitivních objektů, byla dána církví v roce 1940. Používá notaci (lambda) - počet (Barendregt 1997). Protože taková formulace je důležitá v informatice, pro souvislosti s teorií kategorií a pro teorii typu Martin-Löf, popisujeme ji podrobně. V této formulaci jsou predikáty považovány za zvláštní druh funkcí (výrokové funkce), což je myšlenka, která sahá až do Frege (viz například Quine 1940). Dále,pojem funkce je vnímán jako primitivnější než pojem predikátů a vztahů a funkce již není definována jako zvláštní druh vztahu. (Oppenheimer a Zalta 2011 uvádí některé argumenty proti takové primitivní reprezentaci funkcí.) Typy tohoto systému jsou definovány induktivně následovně

1. existují dva základní typy (i) (typ jednotlivců) a (o) (typ propozic)
2. jestliže (A, B) jsou typy, pak (A / rightarrow B), typ funkcí od (A) do (B), je typ

Takto můžeme tvořit typy:

(i / rightarrow o)	(typ predikátů)
((i / rightarrow o) rightarrow o)	(typ predikátů predikátů)

které odpovídají typům ((i)) a ((i))), ale také novým typům

(i / rightarrow i)	(typ funkcí)
((i / rightarrow i) rightarrow i)	(typ funkcionálu)

Je vhodné psát

[A_1, / ldots, A_n / rightarrow B)

pro

[A_1 / rightarrow (A_2 / rightarrow / ldots / rightarrow (A_n / rightarrow B)))

Takto

[A_1, / ldots, A_n / rightarrow o)

odpovídá typu ((A_1, / ldots, A_n)).

Logika prvního řádu bere v úvahu pouze typy formuláře

(i, / ldots, i / rightarrow i)	(typ funkčních symbolů),	a
(i, / ldots, i / rightarrow o)	(typ predikátu, relační symboly)

Všimněte si toho

[A / rightarrow B / rightarrow C)

znamená

[A / rightarrow (B / rightarrow C))

(spojení vpravo).

Co se týče této logiky, nebudeme se řídit církevním popisem, ale jeho malou variací, kvůli Currymu (který měl podobné myšlenky dříve, než se objevil Churchův papír) a který je podrobně uveden v knize R. Hindleyho o teorii typů. Stejně jako Church používáme (lambda) - počet, který poskytuje obecný zápis funkcí

[M:: = x / střední MM / střední / lambda xM)

Zde jsme použili tzv. Notaci BNF, velmi pohodlnou v oblasti výpočetní techniky. Toto dává syntaktickou specifikaci (lambda) - podmínky, které, když se rozšíří, znamená:

• každá proměnná je funkční symbol;
• každá juxtapozice dvou funkčních symbolů je funkční symbol;
• každý (lambda xM) je funkční symbol;
• neexistují žádné další funkční symboly.

Zápis pro funkční aplikaci (MN) je trochu odlišný od matematického zápisu, který by byl (M (N)). Obecně, [M_1 M_2 M_3)

znamená

[(M_1 M_2) M_3)

(spojení vlevo). Termín (lambda xM) představuje funkci, kterou (N) asociuje (M [x: = N)]. Tato notace je tak pohodlná, že si člověk klade otázku, proč není v matematice široce používán. Hlavní rovnicí (lambda) - počtu je pak ((beta) - konverze)

[(lambda xM) N = M [x: = N])

který vyjadřuje význam (lambda xM) jako funkce. Jako notaci jsme použili (M [x: = N)] jako hodnotu výrazu, který vznikne, když (N) nahradí proměnnou (x) v matici (M). Tuto rovnici obvykle vidíme jako přepisovací pravidlo ((beta) - redukce)

[(lambda xM) N / rightarrow M [x: = N])

U beztypového počtu lambda se může stát, že takové přepisování nekončí. Kánonický příklad je dán termínem (Delta = / lambda xx x) a aplikací

) Delta / Delta / rightarrow / Delta / Delta)

(Všimněte si podobnosti s Russellovým paradoxem.) Myšlenka Curryho je pak dívat se na typy jako predikáty nad lambda výrazy, psáním (M: A) vyjadřovat, že (M) vyhovuje predikátu / typu (A). Význam

[N: A / rightarrow B)

je tedy

) forall M, / text {if} M: A / text {then} NM: B)

což odůvodňuje následující pravidla

) frac {N: A / rightarrow BM: A} {NM: B})) frac {M: B [x: A]} { lambda xM: A / rightarrow B})

Obecně lze říci, že pracuje s úsudky o formě

[x_1: A_1, …, x_n: A_n / vdash M: A)

kde (x_1, …, x_n) jsou odlišné proměnné a (M) je termín, který má všechny volné proměnné mezi (x_1, …, x_n). Abychom mohli získat církevní systém, přidáme nějaké konstanty, abychom vytvořili návrhy. Typicky

ne:	(o / rightarrow o)
implikovat:	(o / rightarrow o / rightarrow o)
a:	(o / rightarrow o / rightarrow o)
pro všechny:	((A / rightarrow o) rightarrow o)

Termín

) lambda x. / neg (xx))

představuje predikát predikátů, které se nevztahují na sebe. Tento termín však nemá typ, to znamená, že není možné najít (A) takový

) lambda x. / neg (xx): (A / rightarrow o) rightarrow o)

což je formální vyjádření skutečnosti, že Russellův paradox nelze vyjádřit. Rovnost Leibniz

[Q: i / rightarrow i / rightarrow o)

bude definován jako

[Q = / lambda x. / lambda y. / forall (lambda P. / imply (P x) (P y)))

Jeden obvykle píše (forall x [M)] místo (forall (lambda xM)) a definice (Q) pak může být přepsána jako

[Q = / lambda x. / Lambda y. / Forall P) implikovat (P x) (P y)])

Tento příklad znovu ilustruje, že dokážeme formulovat implikativní definice v jednoduché teorii typů.

Použití redukce (lambda) - a (beta) - je nejvhodnější pro reprezentaci složitých substitučních pravidel, která jsou zapotřebí v jednoduché teorii typů. Pokud například chceme v predikci nahradit predikát (lambda xQ ax) za (P)

) implikovat (P a) (P b))

dostaneme

) imply ((lambda xQ ax) a) ((lambda xQ ax) b))

a pomocí (beta) - redukce,) implikovat (Q aa) (Q ab))

V souhrnu lze říci, že jednoduchá teorie typů zakazuje samočinnou aplikaci, ale nikoli kruhovitost přítomnou v implicitních definicích.

Formalismus (lambda) - počtu také umožňuje jasnější analýzu Russellova paradoxu. Vidíme to jako definici predikátu

[R x = / neg (xx))

Pokud uvažujeme o (beta) - redukci jako procesu rozvinutí definice, vidíme, že již existuje problém s pochopením definice RR

[RR / rightarrow / neg (RR) rightarrow / neg (neg (RR)) rightarrow / ldots)

V jistém smyslu máme nedefinovanou definici, která je stejně problematická jako rozpor (výrok ekvivalentní její negaci). Jedna důležitá věta, normalizační věta, říká, že k tomu nemůže dojít u jednoduchých typů: pokud máme (M: A), pak (M) je normalizovatelné silným způsobem (jakákoli posloupnost redukcí začínající od (M)) končí).

Pro více informací o tomto tématu odkazujeme na záznam o jednoduché církevní teorii typů.

3. Ramifikovaná hierarchie a nevysvětlitelné principy

Russell zavedl další hierarchii, která nebyla motivována formálními paradoxy vyjádřenými ve formálním systému, ale spíše strachem z „kruhovitosti“a neformálních paradoxů podobných paradoxu lháře. Pokud člověk řekne „lžu“, pak máme situaci připomínající Russella paradox: problém, který odpovídá jeho vlastní negaci. Další neformální taková paradoxní situace je získána, pokud definujeme celé číslo jako „nejmenší celé číslo, které nelze definovat méně než 100 slovy“. Aby se předešlo takovým neformálním paradoxům, Russell považoval za nutné zavést jiný druh hierarchie, tzv. „Rozvětvenou hierarchii“. Potřeba takové hierarchie je naznačena v dodatku B Russella 1903. Je zajímavé, že s tím souvisí otázka identity ekvivalentních propozic a logického produktu třídy propozic. Důkladná diskuse se nachází v kapitole 10 Russella 1959. Jelikož tato představa rozvětvené hierarchie byla v logice a zejména v teorii důkazů mimořádně vlivná, popisujeme ji v některých podrobnostech.

Pro další motivaci této hierarchie je zde jeden příklad kvůli Russellovi. Pokud řekneme

Napoleon byl Korsičan.

v této větě neodkazujeme na žádné shromáždění vlastností. Vlastnost „být Korsičanem“je údajně prediktivní. Pokud řekneme na druhou stranu

Napoleon měl všechny vlastnosti velkého generála

máme na mysli úplnost kvalit. Vlastnost „mít všechny vlastnosti velkého generála“je považována za nepředvídatelnou.

Jiný příklad, také pocházející z Russella, ukazuje, jak mohou nepředvídatelné vlastnosti potenciálně vést k problémům připomínajícím lhářský paradox. Předpokládejme, že navrhujeme definici

Typický Angličan je ten, kdo má všechny vlastnosti, které vlastní většina Angličanů.

Je jasné, že většina Angličanů nemá všechny vlastnosti, které většina Angličanů vlastní. Typický Angličan by proto měl být podle této definice netypický. Problém je podle Russella, že slovo „typické“bylo definováno odkazem na všechny vlastnosti a bylo s ním zacházeno jako s vlastností. (Je pozoruhodné, že podobné problémy vznikají při definování pojmu náhodných čísel, srov. Martin-Löf „Poznámky ke konstruktivní matematice“(1970).) Russell zavedl rozvětvenou hierarchii, aby se vypořádal se zdánlivou kruhovostí takových implicitních definic. Jeden by měl rozlišovat mezi vlastnostmi prvního řádu, jako je Korsičan, které se netýkají součtu vlastností, a je třeba vzít v úvahu, že vlastnosti druhého řádu se vztahují pouze k souhrnu vlastností prvního řádu. Pak lze zavést vlastnosti třetího řádu, které se mohou vztahovat na celkovou vlastnost druhého řádu atd. To jasně vylučuje všechny oběžnosti spojené s implikativními definicemi.

Přibližně ve stejnou dobu Poincaré provedl podobnou analýzu. Zdůraznil význam „predikativních“klasifikací a nedefinování prvků třídy pomocí kvantifikace nad touto třídou (Poincaré 1909). Poincaré použil následující příklad. Předpokládejme, že máme kolekci s prvky 0, 1 a operaci + uspokojující

) begin {zarovnat} x + 0 & = 0 \\ x + (y + 1) & = (x + y) +1 / end {zarovnat})

Řekněme, že vlastnost je induktivní, pokud drží 0 a platí pro (x + 1), pokud drží pro (x).

Implikativní a potenciálně „nebezpečná“definice by měla definovat prvek jako číslo, pokud splňuje všechny induktivní vlastnosti. Je pak snadné ukázat, že tato vlastnost „být číslem“je sama o sobě induktivní. Ve skutečnosti 0 je číslo, protože splňuje všechny indukční vlastnosti, a pokud (x) splňuje všechny indukční vlastnosti, pak také platí (x + 1). Podobně je snadné ukázat, že (x + y) je číslo, pokud (x, y) jsou čísla. Vlastnost (Q (z)), že (x + z) je číslo, je induktivní: (Q) (0) platí od (x + 0 = x) a pokud (x + z) je číslo, tak je i (x + (z + 1) = (x + z) +1). Celý tento argument je však kruhový, protože vlastnost „být číslem“není prediktivní a mělo by se s ním nakládat s podezřením.

Místo toho je třeba zavést rozvětvenou hierarchii vlastností a čísel. Na začátku má člověk pouze indukční vlastnosti prvního řádu, které ve svých definicích neodkazují na souhrn vlastností, a jeden definuje čísla řádu 1 jako prvky splňující všechny indukční vlastnosti prvního řádu. Jeden může dále zvážit indukční vlastnosti druhého řádu, které se mohou vztahovat na soubor vlastností prvního řádu a čísla řádu 2, které jsou prvky splňující induktivní vlastnosti řádu 2. Jeden může pak podobně uvažovat čísla řádu 3 atd. Poincaré zdůrazňuje skutečnost, že počet řádů 2 je a fortiori počet řádů 1 a obecněji počet řádů (n + 1) je a fortiori počet řádů (n). Máme tak řadu stále více omezených vlastností:indukční vlastnosti řádu 1, 2, … a posloupnost více a více omezených sbírek objektů: čísla řádu 1, 2,… Také vlastnost „být číslem řádu (n)“je sama o sobě induktivní vlastnost řádu (n + 1).

Nezdá se být možné prokázat, že (x + y) je číslo řádu (n), pokud (x, y) jsou čísla řádu (n). Na druhou stranu je možné ukázat, že pokud (x) je číslo řádu (n + 1) a (y) číslo řádu (n + 1), pak (x + y) je číslo řádu (n). Vlastnost (P (z)), že "(x + z) je číslo řádu (n)", je induktivní vlastnost řádu (n + 1: P) (0) platí, protože (x + 0 = x) je počet řádů (n + 1), a tedy řádek (n), a pokud (P (z)) platí, je to (x + z) je počet řádků (n), tak je to i (x + (z + 1) = (x + z) +1), a tak (P (z + 1)) drží. Protože (y) je počet řádů (n + 1), a (P (z)) je indukční vlastnost řádu (n + 1, P (y)) platí, takže (x + y) je číslo řádu (n). Tento příklad dobře ilustruje složitosti zavedené rozvětvenou hierarchií.

Složitosti jsou dále umocněny, pokud jeden, jako Russell jako pro Frege, definuje dokonce základní objekty, jako jsou přirozená čísla, jako třídy tříd. Například číslo 2 je definováno jako třída všech tříd jednotlivců, kteří mají přesně dva prvky. Opět získáváme přirozená čísla různých řádů v rozvětvené hierarchii. Kromě Russella samotného a přes všechny tyto komplikace se Chwistek pokusil vyvinout aritmetiku rozvětveným způsobem a zájem o takovou analýzu zdůraznil Skolem. Viz Burgess a Hazen 1998 pro nejnovější vývoj.

Dalším, často uváděným, matematickým příkladem implikativní definice je definice nejmenší horní hranice ohraničené třídy reálných čísel. Pokud identifikujeme skutečný se sadou racionálů, která jsou menší než tato reálná, vidíme, že tuto nejmenší horní hranici lze definovat jako spojení všech prvků v této třídě. Označme podmnožiny racionálů jako predikáty. Například pro racionální čísla (q, P (q)) platí iff (q) je člen podmnožiny označený jako (P). Nyní definujeme predikát (L_C) (podmnožinu racionálů) jako nejmenší horní hranici třídy (C) jako:

) forall q [L_C (q) leftrightarrow / existuje P [C (P) wedge P (q)])

což je nepředvídatelné: predikát (L) jsme definovali existenciální kvantifikací přes všechny predikáty. Pokud je v rozvětvené hierarchii třída (C) třída racionálních tříd prvního řádu, pak (L) bude třídou racionálů druhého řádu. Jeden pak získá ne jeden pojem nebo reálná čísla, ale reálná čísla různých řádů 1, 2, … Nejmenší horní hranice souboru realit řádu 1 bude potom obecně alespoň řádu 2.

Jak jsme viděli dříve, dalším příkladem implikativní definice je Leibnizova definice rovnosti. Pro Leibniz je predikát „roven (a)“pravdivý pro (b) iff (b) splňuje všechny predikáty uspokojené pomocí (a).

Jak by se člověk měl vypořádat s komplikacemi zavedenými rozvětvenou hierarchií? Russell v úvodu druhého vydání Principia Mathematica ukázal, že těmto komplikacím lze v některých případech zabránit. Dokonce si myslel, v dodatku B druhého vydání Principia Mathematica, že rozvětvená hierarchie přirozených čísel řádu 1,2, … se zhroutí v pořadí 5. Nicméně Gödel později našel problém ve svém argumentu a skutečně to bylo ukázal Myhill 1974, že tato hierarchie ve skutečnosti nespadá na žádné konečné úrovni. Podobný problém,Russell v úvodu do druhého vydání Principia Mathematica vyvstává v důkazu Cantorovy věty, že nemohou existovat žádné injekční funkce od sběru všech predikátů po sbírku všech objektů (verze Russellova paradoxu ve Fregeově systému, kterou jsme uvedené v úvodu). Lze to provést v rozvětvené hierarchii? Russell pochyboval o tom, že by to mohlo být provedeno v rozvětvené hierarchii predikátů, což bylo skutečně potvrzeno později (Heck 1996).

Kvůli těmto problémům Russell a Whitehead představili v prvním vydání Principia Mathematica následující axiom redukovatelnosti: hierarchie predikátů, prvního řádu, druhého řádu atd., Se zhroutí na úrovni 1. To znamená, že pro jakýkoli predikát jakéhokoli pořadí, existuje predikát úrovně prvního řádu, který je s ním ekvivalentní. V případě rovnosti například postulujeme vztah prvního řádu „(a = b)“, který je ekvivalentní s „(a) splňuje všechny vlastnosti, které (b) splňuje“. Motivace pro tento axiom byla čistě pragmatická. Bez něj jsou všechny základní matematické pojmy, jako jsou reálná nebo přirozená čísla, rozvrstveny do různých řádů. Zdá se, že i přes zjevnou kruhovost implicitních definic nevede axiom redukovatelnosti k rozporům.

Jak si však všiml nejprve Chwistek a později Ramsey, v přítomnosti axiomu redukovatelnosti nemá vůbec smysl zavádět rozvětvenou hierarchii! Je mnohem jednodušší přijmout implicitní definice hned od začátku. Jednoduchá „rozšiřovací“hierarchie jednotlivců, tříd, tříd tříd, … pak stačí. Tímto způsobem získáme jednodušší systémy formalizované v Gödel 1931 nebo Church 1940, které byly uvedeny výše.

Axiom redukovatelnosti upozorňuje na problematický stav implicitních definic. Citovat Weyl 1946, axiom redukovatelnosti „je odvážný, téměř fantastický axiom; ve skutečném světě, ve kterém žijeme, není dostatečné ospravedlnění a vůbec žádné důkazy, na nichž naše mysl staví své konstrukce “! Dosud nebyly zjištěny žádné rozpory při použití axiomu redukovatelnosti. Jak však uvidíme níže, vyšetřování na základě důkazů potvrzuje extrémní sílu takového principu.

Myšlenka rozvětvené hierarchie byla v matematické logice nesmírně důležitá. Russell zvažoval pouze konečnou iteraci hierarchie: první řád, druhý řád atd., Ale od začátku byla zvažována možnost prodloužení rozvětvení přechodně. Poincaré (1909) zmiňuje v tomto směru práci Koeniga. Pro výše uvedený příklad čísel různých řádů také definuje číslo, které má být induktivní pro řád (omega), pokud je induktivní pro všechny konečné příkazy. Poté poukáže na to, že x + y indukuje řád (omega), pokud jsou (x) i (y). To ukazuje, že zavedení transfinitových řádů může v některých případech hrát roli axiomu redukovatelnosti. Takovéto transfinitové rozšíření rozvětvené hierarchie bylo dále analyzováno Gödelem, který si všiml klíčové skutečnosti, že následující forma axiomu redukovatelnosti je skutečně prokazatelná: když člověk rozšíří rozvětvenou hierarchii vlastností nad přirozenými čísly do transfinitu, tato hierarchie se zhroutí na úrovni (omega_1), nejméně nespočetný ordinál (Gödel 1995 a Prawitz 1970). Navíc, zatímco na všech úrovních (lt / omega_1) je kolekce predikátů spočítatelná, kolekce predikátů na úrovni (omega_1) je kardinality (omega_1). Tato skutečnost byla silnou motivací Gödelova modelu konstruktivních sestav. V tomto modelu je kolekce všech podmnožin množiny přirozených čísel (reprezentovaných predikáty) kardinality (omega_1) a je podobná rozvětvené hierarchii. Tento model tímto způsobem splňuje hypotézu Continuum a poskytuje tento axiom relativní konzistenci. (Motivací Gödel bylo původně pouze vytvoření modelu, kde je kolekce všech podmnožin přirozených čísel dobře uspořádána.)

Rozvětvená hierarchie byla také zdrojem mnoha prací v teorii důkazů. Poté, co Gentzen objevil, že konzistence aritmetiky může být prokázána transfinitovou indukcí (přes rozhodující predikáty) podél ordinálu (varepsilon_0), bylo přirozenou otázkou najít odpovídající ordinál pro různé úrovně rozvětvené hierarchie. Schütte (1960) zjistil, že pro první úroveň rozvětvené hierarchie, tj. Pokud rozšíříme aritmetiku kvantifikací pouze přes vlastnosti prvního řádu, dostaneme systém ordinální síly (varepsilon _ { varepsilon_0}). Pro druhou úroveň dostaneme ordinální sílu (varepsilon _ { varepsilon_ { varepsilon_0}}) atd. Připomínáme, že (varepsilon _ { alpha}) označuje (alfa) - th (varepsilon) - pořadové číslo,(varepsilon) - pořadové číslo je pořadové (beta) takové, že (omega ^ { beta} = / beta), viz Schütte (1960).

Gödel zdůraznil skutečnost, že jeho přístup k problému hypotézy kontinua nebyl konstruktivní, protože vyžaduje nepočetnou ordinální (omega_1), a bylo přirozené studovat rozvětvenou hierarchii podél konstruktivních ordinálů. Po předběžných pracích Lorenzena a Wanga Schütte analyzoval, co se stane, pokud budeme postupovat následujícím konstruktivnějším způsobem. Protože aritmetika má pro ordinální sílu (varepsilon_0), uvažujeme nejprve iteraci rozvětvené hierarchie až do (varepsilon_0). Schütte vypočítal ordinální sílu výsledného systému a našel ordinální sílu (u (1) gt / varepsilon_0). Opakujeme a následně rozvětvujeme hierarchii až do této ordinální (u (1)) a získáme systém ordinální síly (u (2) gt u (1)) atd. Každý (u (k))) lze vypočítat pomocí tzv. Veblenské hierarchie:(u (k + 1)) je (phi_ {u (k)} (0)). Limitem tohoto procesu je ordinál zvaný (Gamma_0): pokud opakujeme rozvětvenou hierarchii až na ordinál (Gamma_0), dostaneme systém ordinální síly (Gamma_0). Takové pořadové číslo bylo získáno nezávisle přibližně ve stejnou dobu S. Fefermanem. To bylo prohlašoval, že (Gamma_0) hraje pro prediktivní systémy roli podobnou (varepsilon_0) pro aritmetiku. Nedávná důkazně-teoretická díla se však zabývají systémy, které mají větší důkazně-teoretické ordinály, které lze považovat za prediktivní (viz například Palmgren 1995). To bylo prohlašoval, že (Gamma_0) hraje pro prediktivní systémy roli podobnou (varepsilon_0) pro aritmetiku. Nedávná důkazně-teoretická díla se však zabývají systémy, které mají větší důkazně-teoretické ordinály, které lze považovat za prediktivní (viz například Palmgren 1995). To bylo prohlašoval, že (Gamma_0) hraje pro prediktivní systémy roli podobnou (varepsilon_0) pro aritmetiku. Nedávná důkazně-teoretická díla se však zabývají systémy, které mají větší důkazně-teoretické ordinály, které lze považovat za prediktivní (viz například Palmgren 1995).

Kromě těchto důkazních teoretických zkoumání souvisejících s rozvětvenou hierarchií bylo v teorii důkazů věnováno velké množství analýze důslednosti axiomu redukovatelnosti, nebo, stejně, konzistence implicitních definic. Po Gentzenově analýze cut-eliminační vlastnosti v sekvenčním počtu, Takeuti našel elegantní sekvenční formulaci jednoduché teorie typů (bez rozvětvení) a učinil odvážné dohady, že cut-eliminace by měla platit pro tento systém. Tato domněnka se zdála zpočátku velmi pochybná vzhledem k okružnosti implicitní kvantifikace, která se dobře odráží v tomto formalismu. Pravidlo kvantifikace je skutečně

) frac { Gamma / vdash / forall X [A (X)]} { Gamma / vdash A [X: = T]})

kde (T) je jakýkoli predikát termínu, který může sám zahrnovat kvantifikaci všech predikátů. Vzorec (A [X: = T]) tedy může být sám mnohem složitější než vzorec (A (X)).

Jedním z prvních výsledků je, že eliminace redukce pro Takeutiho implicitní systém implicitně znamená konzistenci aritmetiky druhého řádu. (Jeden ukazuje, že to implikuje konzistenci vhodné formy axiomu nekonečna, viz Andrews 2002.) Po práci Schütteho později W. Tait a D. Prawitz ukázali, že vlastnost cut-eliminačního vlastníka (důkaz o toto musí používat silnější důkazní teoretický princip, jak by to mělo být podle věty o neúplnosti.)

Důležité je, že tyto studie odhalily extrémní sílu implicitní kvantifikace, nebo ekvivalentně, extrémní sílu axiomu redukovatelnosti. To nějakým způsobem potvrzuje intuice Poincarého a Russella. Důkazově-teoretická síla aritmetiky druhého řádu je především především rozvětvená rozšíření aritmetiky uvažovaná Schütte. Na druhou stranu, navzdory kruhové orientaci implicitních definic, které jsou v Takeutiho počtu tak jasně vyjádřeny, nebyly v aritmetice druhého řádu dosud nalezeny žádné paradoxy.

Dalším výzkumným směrem v teorii důkazů bylo pochopit, jak velkou část implikativní kvantifikace lze vysvětlit z principů, které jsou k dispozici v intuicionistické matematice. Nejsilnější takové principy jsou silné formy induktivních definic. S takovými principy lze vysvětlit omezenou formu impredikativní kvantifikace, nazvanou (Pi_ {1} ^ 1) - porozumění, kde jeden používá pouze jednu úroveň implikativní kvantifikace nad predikáty. Je zajímavé, že téměř všechna známá použití implicitních kvantifikací: Leibnizova rovnost, nejméně horní mez atd., Lze provést pomocí (Pi_ {1} ^ 1) - porozumění. Toto snížení (Pi_ {1} ^ 1) - porozumění bylo poprvé dosaženo Takeuti docela nepřímým způsobem, a později jej Buchholz a Schütte zjednodušili pomocí pravidla tzv. (Omega). Může to být chápáno jako konstruktivní vysvětlení některých omezených, ale netriviálních použití implicitních definic.

4. Zadejte Teorie / Teorie množin

Teorie typů může být použita jako základ pro matematiku, a opravdu, jako takový byl prezentován Russellem v jeho dokumentu z roku 1908, který se objevil ve stejném roce jako Zermelův papír, představující teorii množin jako základ pro matematiku.

Intuitivně je jasné, jak můžeme vysvětlit teorii typů v teorii množin: typ je jednoduše interpretován jako množina a typy funkcí (A / rightarrow B) lze vysvětlit pomocí teoretického pojmu funkce (jako funkční vztah, tj. soubor párů prvků). Typ (A / rightarrow o) odpovídá operaci sady setset.

Druhý směr je zajímavější. Jak můžeme vysvětlit pojem množiny z hlediska typů? Elegantní řešení je díky A. Miquovi, které doplňuje předchozí díla P. Aczela (1978) a které má také tu výhodu, že vysvětluje nezbytně opodstatněné sady a la Finsler. Jeden jednoduše interpretuje množinu jako špičatý graf (kde šipka v grafu představuje vztah členství). Toto je velmi pohodlně reprezentováno v teorii typů, špičatý graf je jednoduše dán typem A a dvojicí prvků

[a: A, R: A / rightarrow A / rightarrow o)

Můžeme pak definovat v teorii typů, když jsou dvě takové množiny (A, a, R) a (B, b, S) stejné: to je případ iff existuje bisimulace (T) mezi (A) a (B) tak, že platí (Tab). Bisimulace je vztah

[T: A / rightarrow B / rightarrow o)

tak, že kdykoli drží (Txy) a (Rxu), existuje (v), takže (Tuv) a (Syv) drží, a kdykoli (Txy) a (Ryv) hold, existuje (u) takový, že (Tuv) a (Rxu) hold. Pak můžeme definovat vztah členství: množina reprezentovaná (B, b, S) je člen množiny reprezentované (A, a, R), pokud existuje (a_1), takže (Ra_1a)) a (A, a_1, R) a (B, b, S) jsou dvojrozměrné.

Potom je možné zkontrolovat, že v tomto jednoduchém modelu platí všechny obvyklé axiomy rozšiřování teorie množin, mocnin, sjednocení, porozumění nad ohraničenými formulemi (a dokonce i antifoundace, takže členské vztahy nemusí být opodstatněné). (Omezený vzorec je vzorec, kde všechny kvantifikace mají tvar (forall x / in / ldots) nebo (existuje x / in / ldots)). Tímto způsobem lze ukázat, že jednoduchá teorie typu církve je v souladu s omezenou verzí Zermeloovy teorie množin.

5. Teorie typů / Teorie kategorií

Mezi teorií typů a teorií kategorií existují hluboké souvislosti. Omezujeme se na představení dvou aplikací teorie typů na teorii kategorií: konstrukce uzavřené kategorie volného kartézského typu a volného toposu (vysvětlení pojmu „karteziánské uzavřené“a „toposové“viz položka teorie teorie).

Pro sestavení volné karteziánské uzavřené kategorie rozšiřujeme jednoduchou teorii typů o typ 1 (typ jednotky) a typ produktu (A / times B), pro typy (A, B). Termíny jsou rozšířeny přidáním párovacích operací a projekcí a zvláštního prvku typu 1. Stejně jako v Lambek a Scott 1986 lze definovat pojem typově převedených mezi pojmy a ukázat, že tento vztah je rozhodnutelný. Pak lze ukázat (Lambek a Scott 1986), že kategorie s typy jako objekty a morfismy z (A) na (B) množinu uzavřených podmínek typu (A / rightarrow B) (s převodem jako rovnost) je volná karteziánská uzavřená kategorie. To lze použít k prokázání, že rovnost mezi šipkami v této kategorii je rozhodnutelná.

Teorie typů církví může být také použita k vytvoření svobodných toposů. Za to bereme jako objekty dvojice (A, E) s (A) typem a (E) dílčí ekvivalenční vztah, tj. Uzavřený termín (E: A / rightarrow A / rightarrow o) což je symetrické a přechodné. Bereme jako morfismy mezi (A, E) a (B, F) vztahy (R: A / rightarrow B / rightarrow o), které jsou funkční a které jsou pro všechny (a: A) vyhovující (E aa) existuje jeden a pouze jeden (modulo (F)) element (b) z (B), takže (Fbb) a (R ab). Pro klasifikátor subobjektů bereme dvojici (o, E) s (E: o / rightarrow o / rightarrow o) definovanou jako

[EMN = / text {a} (imply \, MN) (imply \, NM))

Pak lze ukázat, že tato kategorie tvoří topos, skutečně topos zdarma.

Je třeba poznamenat, že teorie typů v Lambek a Scott 1986 používá variaci teorie typů, která byla představena Henkinem a vylepšena P. Andrewsem (2002), která má jako jediný logický spojovací prvek, tj. Polymorfní konstantu, existovat extenzivní rovnost

) text {eq}: A / rightarrow A / rightarrow o)

a definovat všechny logické spojky z tohoto spojovacího a konstanty (T, F: o). Například jeden definuje

) forall P = _ {df} text {eq} (lambda xT) P)

Rovnost u typu (o) je logická ekvivalence.

Jednou z výhod intenzivní formulace je, že umožňuje přímé zaznamenávání důkazů na základě (lambda) - počtu (Martin-Löf 1971 a Coquand 1986).

6. Rozšíření typového systému, polymorfismus, paradoxy

Viděli jsme analogii mezi operací A (rightarrow) A (rightarrow) o u typů a operací sady setset. V teorii množin lze operaci sady mocnin iterovat transfinitivně podél kumulativní hierarchie. Je tedy přirozené hledat analogické transfinitové verze teorie typů.

Jedno takové rozšíření teorie jednoduchých typů církví je získáno přidáním vesmírů (Martin-Löf 1970). Přidání vesmíru je proces reflexe: přidáme typ (U), jehož objekty jsou dosud považovanými typy. Pro církevní jednoduchou teorii typů budeme mít

[o: U, i: U / text {a} A / rightarrow B: U / text {if} A: U, B: U)

a dále, (A) je typ, pokud (A: U). Můžeme pak zvážit typy jako

[(A: U) rightarrow A / rightarrow A)

a funkce jako

) text {id} = / lambda A. / lambda xx: (A: U) rightarrow A / rightarrow A)

Funkční id bere jako argument „malý“typ (A: U) a prvek (x) typu (A) a vydává prvek typu (A). Obecněji, pokud (T (A)) je typ za předpokladu (A: U), lze vytvořit závislý typ

[(A: U) rightarrow T (A))

To, že (M) je tohoto typu znamená, že (MA: T (A)) kdykoli (A: U). Tímto způsobem získáváme rozšíření teorie typů, jejíž síla je podobná té z Zermeloovy teorie množin (Miquel 2001). Silnější forma vesmírů je zvažována v (Palmgren 1998). Miquel (2003) představuje verzi typové teorie síly ekvivalentní s verzí Zermelo-Fraenkel.

Jedna velmi silná forma vesmíru se získá přidáním axiomu (U: U). To navrhl P. Martin-Löf v roce 1970. JY Girard ukázal, že výsledná teorie typů je jako logický systém nekonzistentní (Girard 1972). Ačkoli se na první pohled zdá, že by Russellův paradox mohl přímo reprodukovat pomocí sady všech sad, takový přímý paradox není vlastně možný kvůli rozdílu mezi sadami a typy. Ve skutečnosti je odvození rozporu v takovém systému jemné a bylo spíše nepřímé (ačkoli, jak bylo zaznamenáno v Miquel 2001, může být nyní redukováno na Russellův paradox tím, že představuje množiny jako špičaté grafy). JY Girard nejprve získal svůj paradox pro slabší systém. Tento paradox byl vylepšen později (Coquand 1994 a Hurkens 1995). (Pojetí systému čistého typu, představeného v Barendregtu 1992,je vhodný pro získání ostré formulace těchto paradoxů.) Místo axiomu (U: U) se předpokládá pouze

[(A: U) rightarrow T (A): U)

pokud (T (A): U [A: U]). Všimněte si kruhovitosti, skutečně stejného druhu jako ta, která je odmítnuta rozvětvenou hierarchií: definujeme prvek typu (U) kvantifikací přes všechny prvky (U). Například typ

[(A: U) rightarrow A / rightarrow A: U)

bude typ funkce polymorfní identity. Přes tuto kruhovitost, JY Girard byl schopen ukázat normalizaci pro systémy typu s touto formou polymorfismu. Rozšíření církevní jednoduché typové teorie o polymorfismus je však jako logický systém nekonzistentní, tj. Všechny výroky (podmínky typu o) jsou prokazatelné.

Motivací JY Girarda pro zvažování typového systému s polymorfismem bylo rozšíření interpretace Gödelovy dialektiky (Gödel 1958) na aritmetiku druhého řádu. Normalizaci prokázal pomocí metody redukovatelnosti, která byla zavedena Taitem (1967) při analýze Gödel 1958. Je celkem pozoruhodné, že kruhovitost vlastní impredicativity nevede k neobvyklým pojmům. (Girardův argument byl pak použit k ukázání toho, že cut-eliminační zakončení končí v Takeutiho sekvenčním počtu, který je uveden výše.) Podobný systém zavedl nezávisle J. Reynolds (1974) při analýze pojmu polymorfismus v informatice.

Martin-Löf představil typ všech typů pochází z identifikace konceptu propozic a typů, navržených prací Curryho a Howarda. Zde stojí za to připomenout jeho tři motivační body:

1. Russellova definice typů jako rozsahů významu výrokových funkcí
2. skutečnost, že je třeba kvantifikovat všechny výroky (nepředvídatelnost jednoduché teorie typů)
3. identifikace nabídky a typů

Vzhledem k (1) a (2) bychom měli mít typ propozic (jako v jednoduché teorii typů) a vzhledem k (3) by to měl být také typ všech typů. Girardův paradox ukazuje, že jeden nemůže mít (1), (2) a (3) současně. Martin-Löf měl na výběr, aby vzal (2), omezující teorii typů, aby byl predikativní (a ve skutečnosti se pojem vesmír objevil jako první v teorii typů jako predikativní verze typu všech typů). Alternativní volba odběru (3) je diskutována v Coquand 1986.

7. Univalentní nadace

Spojení mezi teorií typů, teorií množin a teorií kategorií získává nové světlo díky práci na Univalent Foundations (Voevodsky 2015) a Axiom of Univalence. To zásadním způsobem zahrnuje rozšíření teorie typů popsané v předchozí části, zejména závislých typů, zobrazení výroků jako typů a pojmu vesmír typů. Tento vývoj je také důležitý pro diskusi o pojmu struktura, jehož význam byl například zdůrazněn v Russellu 1959.

Martin-Löf 1975 [1973] představil nový základní typ (mathbf {Id} _A (a, b)), pokud (a) a (b) jsou v typu (A), což lze považovat za typ důkazů rovnosti prvku (a) a (b). Důležitou vlastností tohoto nového typu je to, že může být iterováno, takže můžeme zvážit typ (mathbf {Id} _ { mathbf {Id} _A (a, b)} (p, q)), pokud (p) a (q) jsou typu (mathbf {Id} _A (a, b)). Pokud uvažujeme o typu jako o zvláštním druhu souboru, je přirozené předpokládat, že takový typ důkazů rovnosti je vždy obýván pro jakékoli dva doklady rovnosti (p) a (q). Intuitivně se zdá, že existuje nanajvýš důkaz rovnosti mezi dvěma prvky (a) a (b). Hofmann a Streicher 1996 překvapivě navrhli model teorie závislých typů, kde to neplatí,to je model, kde mohou být různé důkazy, že dva prvky jsou si rovny. V tomto modelu je typ interpretován grupoidem a typem (mathbf {Id} _A (a, b)) sadou izomorfismů mezi (a) a (b), která může mají více než jeden prvek. Existence tohoto modelu má za následek, že v teorii typů nelze obecně dokázat, že typ rovnosti má nanejvýš jeden prvek. Tato interpretace grupoidů byla zobecněna následujícím způsobem, což dává intuitivní interpretaci typu identity. Typ je interpretován topologickým prostorem až po homotopii a typ (mathbf {Id} _A (a, b)) je interpretován podle typu cest spojujících (a) a (b). (Viz Awodey et al. 2013 a [HoTT 2013, Další internetové zdroje].)typ je interpretován groupoidem a typ (mathbf {Id} _A (a, b)) množinou izomorfismů mezi (a) a (b), množinou, která může mít více než jednu živel. Existence tohoto modelu má za následek, že v teorii typů nelze obecně dokázat, že typ rovnosti má nanejvýš jeden prvek. Tato interpretace grupoidů byla zobecněna následujícím způsobem, což dává intuitivní interpretaci typu identity. Typ je interpretován topologickým prostorem až po homotopii a typ (mathbf {Id} _A (a, b)) je interpretován podle typu cest spojujících (a) a (b). (Viz Awodey et al. 2013 a [HoTT 2013, Další internetové zdroje].)typ je interpretován groupoidem a typ (mathbf {Id} _A (a, b)) množinou izomorfismů mezi (a) a (b), množinou, která může mít více než jednu živel. Existence tohoto modelu má za následek, že v teorii typů nelze obecně dokázat, že typ rovnosti má nanejvýš jeden prvek. Tato interpretace grupoidů byla zobecněna následujícím způsobem, což dává intuitivní interpretaci typu identity. Typ je interpretován topologickým prostorem až po homotopii a typ (mathbf {Id} _A (a, b)) je interpretován podle typu cest spojujících (a) a (b). (Viz Awodey et al. 2013 a [HoTT 2013, Další internetové zdroje].)Existence tohoto modelu má za následek, že v teorii typů nelze obecně dokázat, že typ rovnosti má nanejvýš jeden prvek. Tato interpretace grupoidů byla zobecněna následujícím způsobem, což dává intuitivní interpretaci typu identity. Typ je interpretován topologickým prostorem až po homotopii a typ (mathbf {Id} _A (a, b)) je interpretován podle typu cest spojujících (a) a (b). (Viz Awodey et al. 2013 a [HoTT 2013, Další internetové zdroje].)Existence tohoto modelu má za následek, že v teorii typů nelze obecně dokázat, že typ rovnosti má nanejvýš jeden prvek. Tato interpretace grupoidů byla zobecněna následujícím způsobem, což dává intuitivní interpretaci typu identity. Typ je interpretován topologickým prostorem až po homotopii a typ (mathbf {Id} _A (a, b)) je interpretován podle typu cest spojujících (a) a (b). (Viz Awodey et al. 2013 a [HoTT 2013, Další internetové zdroje].)b)) se interpretuje podle typu cest spojujících (a) a (b). (Viz Awodey et al. 2013 a [HoTT 2013, Další internetové zdroje].)b)) se interpretuje podle typu cest spojujících (a) a (b). (Viz Awodey et al. 2013 a [HoTT 2013, Další internetové zdroje].)

Voevodsky 2015 představil následující stratifikaci typů. (Tato stratifikace byla částečně motivována touto interpretací typu jako topologického prostoru, ale lze ji chápat přímo bez odkazu na tuto interpretaci.) Říkáme, že typ (A) je výrok, pokud máme (mathbf {Id} _A (a, b)) pro jakýkoli prvek (a) a (b) z (A) (to znamená, že typ (A) má maximálně jeden prvek). Říkáme, že typ (A) je množina, pokud je typ (mathbf {Id} _A (a, b)) návrhem pro jakýkoli prvek (a) a (b) z (A). Říkáme, že typ (A) je groupoid, pokud je typ (mathbf {Id} _A (a, b)) množina pro libovolný prvek (a) a (b) z (A). Zdůvodnění této terminologie spočívá v tom, že je možné prokázat pouze pomocí pravidel teorie typů, že jakýkoli takový typ lze skutečně považovat za groupoid v obvyklém kategorickém smyslu,kde objekty jsou prvky tohoto typu, sada morfismů mezi (a) a (b) je reprezentována sadou (mathbf {Id} _A (a, b)). Složení je důkazem transitivity rovnosti a morfismus identity je důkazem reflexivity rovnosti. Skutečnost, že každý morfismus má inverzní tvar, odpovídá skutečnosti, že identita je symetrický vztah. Tato stratifikace pak může být rozšířena a můžeme definovat, kdy je typem 2-groupoid, 3-groupoid a tak dále. V tomto pohledu se teorie typů objevuje jako rozsáhlá zobecnění teorie množin, protože množina je zvláštní druh typu.a morfismus identity je důkazem reflexivity rovnosti. Skutečnost, že každý morfismus má inverzní tvar, odpovídá skutečnosti, že identita je symetrický vztah. Tato stratifikace pak může být rozšířena a můžeme definovat, kdy je typem 2-groupoid, 3-groupoid a tak dále. V tomto pohledu se teorie typů objevuje jako rozsáhlá zobecnění teorie množin, protože množina je zvláštní druh typu.a morfismus identity je důkazem reflexivity rovnosti. Skutečnost, že každý morfismus má inverzní tvar, odpovídá skutečnosti, že identita je symetrický vztah. Tato stratifikace pak může být rozšířena a můžeme definovat, kdy je typem 2-groupoid, 3-groupoid a tak dále. V tomto pohledu se teorie typů objevuje jako rozsáhlá zobecnění teorie množin, protože množina je zvláštní druh typu.

Voevodsky 2015 zavádí také pojem ekvivalence mezi typy, pojem, který jednotným způsobem zobecňuje pojmy logické ekvivalence mezi propozicemi, bijekti mezi množinami, kategorickou ekvivalenci mezi grupoidy atd. Říkáme, že mapa (f: A / rightarrow B) je ekvivalence, pokud pro jakýkoli prvek (b) v (B) typ párů (a, p) kde (p) je typu (mathbf {Id} _B (fa, b)), je výrok a je obýván. To silně vyjadřuje, že prvek v (B) je obrazem přesně jednoho prvku v (A), a pokud jsou (A) a (B) sady, obnovíme obvyklou představu bijection mezi sadami. (Obecně jestliže (f: A / rightarrow B) je ekvivalence, pak máme mapu (B / rightarrow A), kterou lze považovat za inverzní k (f).) Lze například ukázat, že mapa identity je vždy ekvivalence. Nechť (text {Equiv} (A, B)) je typ párů (f, p), kde (f: A / rightarrow B) a (p) je důkaz, že (f) je ekvivalence. Vzhledem k tomu, že mapa identity je ekvivalence, máme prvek (text {Equiv} (A, A)) pro jakýkoli typ (A). To znamená, že máme mapu

) mathbf {Id} _U (A, B) rightarrow / text {Equiv} (A, B))

a Axiom of Univalence uvádí, že tato mapa je ekvivalence. Zejména máme důsledky

) text {Equiv} (A, B) rightarrow / mathbf {Id} _U (A, B))

a pokud tedy existuje ekvivalent mezi dvěma malými typy, pak jsou tyto typy stejné.

Tento Axiom lze považovat za silnou formu principu extenzivity. Skutečně zobecňuje axiom výrokové prodlužování zmíněné církví 1940, který uvádí, že dva logicky ekvivalentní výroky jsou si rovny. Překvapivě to také implikuje Axiom funkcionální rozšiřitelnosti, Axiom 10 v kostele 1940, který uvádí, že dvě bodově stejné funkce jsou si rovny (Voevodsky 2015). Rovněž to přímo znamená, že dvě izomorfní sady jsou si rovny, že dva kategoricky ekvivalentní groupoidy jsou si rovny, a tak jeden.

To lze použít k formulaci pojmu transport struktur (Bourbaki 1957) podél ekvivalencí. Například nechť (MA) je typ monoidních struktur v množině (A): jedná se o typ n-ticek (m, e, p), kde (m) je binární operace na (A) a (e) prvek (A) a (p) důkaz, že tyto prvky splňují obvyklé monoidní zákony. Pravidlo nahrazení rovným rovným má podobu

) mathbf {Id} _U (A, B) rightarrow MA / rightarrow MB)

Pokud existuje bijekce mezi (A) a (B), jsou si rovni Axiom of Univalence a my můžeme tuto implikaci použít k transportu jakékoli monoidní struktury (A) v monoidní struktuře (B).

Tento rámec můžeme také použít k upřesnění Russellova 1959 diskuse o pojmu struktura. Například nechť Monoid je typ párů (A, p), kde (p) je prvek (MA). Dva takové páry (A, p) a (B, q) jsou izomorfní, pokud existuje bijek (f) z (A) na (B) tak, že (q) je rovná se transportu struktury (p) podél (f). Důsledkem Axiom of Univalence je, že dva izomorfní prvky typu Monoidjsou si rovni, a proto sdílejí stejné vlastnosti. Všimněte si, že takový obecný přenos vlastností není možný, když jsou struktury formulovány v množině teoretických rámců. Opravdu, v množině teoretických rámců, je možné formulovat vlastnosti pomocí členských vztahů, například vlastnost, že nosná sada struktury obsahuje přirozené číslo (0), vlastnost, která se obecně nezachovává izomorfismy. Intuitivně není stanovený teoretický popis struktury dostatečně abstraktní, protože můžeme hovořit o způsobu, jakým je tato struktura vybudována. Tento rozdíl mezi teorií množin a teorií typů je dalším příkladem charakterizace typové struktury J. Reynolds 1983 jako „syntaktické disciplíny pro vynucení úrovně abstrakce“.

Bibliografie

• Aczel, P., 1978, „Teoretická interpretace typu konstruktivní teorie množin“, Logické kolokvium '77, Amsterdam: North-Holland, 55–66.
• Andrews, P., 2002, Úvod do matematické logiky a teorie typů: pravdě prostřednictvím důkazu (Applied Logic Series: Svazek 27), Dordrecht: Kluwer Academic Publishers, druhé vydání.
• Awodey, S., Pelayo, A., Warren, M. 2013, „Axiom univalence v teorii typů homotopií“, Oznámení American Mathematical Society, 60 (9): 1157–1164.
• Barendregt, H., 1997, „Dopad lambda počtu v logice a informatice“, Bulletin of Symbolic Logic, 3 (2): 181–215.
• –––, 1992, Lambda kalkulu s typy. Příručka logiky v informatice, svazek 2, Oxford, New York: Oxford University Press, 117–309.
• Bell, JL, 2012, „Druhy, sady a kategorie“, v Akihiro Kanamory Handbook of History of Logic. Svazek 6: Sady a rozšíření ve dvacátém století, Amsterdam: Severní Holandsko.
• Bourbaki, N., 1958, Théorie des Ensembles, 3. vydání, Paříž: Hermann.
• de Bruijn, NG, 1980, „Přehled projektu AUTOMATH“, v To HB Curry: eseje o kombinativní logice, lambda počtu a formalismu, Londýn-New York: Academic Press, 579–606.
• Burgess JP a Hazen AP, 1998, „Prediktivní logika a formální aritmetický zdroj“, Notre Dame J. Formal Logic, 39 (1): 1-17.
• Buchholz, W. a K. Schütte, 1988, Důkazová teorie improvokativních subsystémů analýzy (Studie v teorii důkazů: Monografie 2), Neapol: Bibliopolis.
• Church, A., 1940, „Formulace jednoduché teorie typů“, Journal of Symbolic Logic, 5: 56–68
• –––, 1984, „Russelllova teorie identity propozic“, Philosophia Naturalis, 21: 513–522
• Chwistek, L., 1948, Meze vědy: Nástin logiky a metodologie přesných věd, Londýn: Routledge a Kegan Paul.
• Coquand, T., 1986, „Analýza Girardova paradoxu“, Sborník z IEEE Symposium on Logic in Computer Science, 227–236.
• –––, 1994, „Nový paradox v teorii typů“, Stud. Logika nalezena. Matematika. (Svazek 134), Amsterdam: Severní Holandsko, 555–570.
• du Bois-Reymond, P., 1875, „Ueber asymptotische Werthe, infintaere Appproximationen und infitaere Aufloesung von Gleichungen,“Mathematische Annalen, 8: 363–414.
• Feferman, S., 1964, „Systémy predikativní analýzy“, Journal of Symbolic Logic, 29: 1-30.
• Ferreira, F. a Wehmeier, K., 2002, „O konzistenci fragmentu Delta-1-1-CA Frege's Grundgesetze,“Journal of Philosophic Logic, 31: 301–311.
• Girard, JY, 1972, Interpretation fonctionelle et eleimination des coupures dans l'arithmetique d'ordre superieure, These d'Etat, Université Paris 7.
• Goldfarb, Warren, 2005. „Na cestě Godel in: Vliv Rudolfa Carnapa.“Bulletin of Symbolic Logic 11 (2): 185–193.
• Gödel, K., 1995, Collected Works Volume III, Nepublikované eseje a přednášky, Oxford: Oxford University Press, 1995.
• –––, 1931, „Über formální untentscheidbare Sätze der Principia Mathematica und verwandter Systeme I,“Monatshefte fü Mathematik und Physik, 38: 173–198.
• –––, 1944, „Russelllova matematická logika“, ve filozofii Bertranda Russella, PA Schilppa (ed.), Evanston: Northwestern University Press, 123–153.
• –––, 1958, „Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes,“, Dialectica, 12: 280–287.
• Heck, R., Jr., 1996, „Konzistence prediktivních fragmentů Fregeova Grundgesetze der Arithmetika,“History and Philosophy of Logic, 17 (4): 209-220.
• van Heijenoort, 1967, Z Frege do Gödel. Zdrojová kniha v matematické logice 1879–1931, Cambridge, MA: Harvard University Press.
• Hindley, R., 1997, Základní teorie jednoduchých typů, Cambridge: Cambridge University Press.
• Hodges, W., 2008, „Tarski na Padoa's Method: testovací příklad pro pochopení logiků jiných tradic“, v Logic, Navya-Nyāya and Applications: Pocta Bimalovi Krišnovi Matilalovi, Mihir K. Chakraborti et al. (eds.), London: College Publications, str. 155–169
• Hofmann, M. a Streicher, Th. 1996, „The Groupoid interpretace Teorie typů“, ve dvaceti pěti letech teorie konstruktivního typu (Oxford Logic Guides: Svazek 36), Oxford, New York: Oxford University Press, 83–111.
• Howard, WA, 1980, „Formule-as-type concept of construction,“in To HB Curry: eseje o kombinované logice, lambda počtu a formalismu, Londýn, New York: Academic Press, 480–490.
• Hurkens, AJC, 1995, „Zjednodušení Girardova paradoxu. Typed lambda calculi and applications, “v Lecture Notes in Computer Science (Svazek 902), Berlín: Springer: 266–278.
• Lambek, J., 1980. "Od (lambda) - počet do karteziánských uzavřených kategorií" v Do HB Curry: Eseje o kombinované logice, (lambda) - počet a formalismus, J. Seldin a J. Hindley (eds.), Londýn, New York: Academic Press. str. 375–402.
• Lambek, J. a Scott, PJ, 1986, Úvod do kategorické logiky vyššího řádu (Cambridge Studies in Advanced Mathematics: Volume 7), Cambridge: Cambridge University Press; dotisknut 1988.
• Lawvere, FW a Rosebrugh, R., 2003, Sady pro matematiku, Cambridge: Cambridge University Press.
• Martin-Löf, P., 1970, Poznámky ke konstruktivní matematice, Stockholm: Almqvist & Wiksell.
• –––, 1971, Teorie typů, Technická zpráva 71–3, Stockholm: Stockholmská univerzita.
• ––– 1998, „Intuitivní teorie typů“, za dvacet pět let teorie konstruktivního typu (Oxford Logic Guides: Volume 36), Oxford, New York: Oxford University Press, 127–172.
• –––, 1975 [1973], „intuicionální teorie typů: predikativní část“, v logickém kolokviu '73 (Sborníky logického kolokvia, Bristol 1973) (studia logiky a základy matematiky: svazek 80), VŠ Rose a JC Shepherdson (ed.), Amsterdam: North-Holland, 73–118.
• Myhill, J., 1974, „Nedefinovatelnost množiny přírodních čísel v rozvětvené Principii“, v Bertrand Russell's Philosophy, G. Nakhnikian (ed.), London: Duckworth, 19–27.
• Miquel, A., 2001, implicitní Le Calcul des Constructions: syntaxe et sémantique, Thèse de doctorat, Université Paris 7.
• –––, 2003, „Silně normalizující Curryho-Howardova korespondence pro teorii množin IZF,“v počítačové informatice Logic (Lecture Notes in Computer Science, 2803), Berlín: Springer: 441–454.
• Oppenheimer, P. a E. Zalta, 2011, „Vztahy versus funkce na základech logiky: teoretické úvahy typu“, Journal of Logic and Computation, 21: 351–374.
• Palmgren, Erik, 1998, „O vesmírech v teorii typů“, za dvacet pět let teorie konstruktivního typu (Oxford Logic Guides: Svazek 36), Oxford, New York: Oxford University Press, 191–204.
• Poincaré, 1909, „H. La logique de l'infini”Revue de metaphysique et de morale, 17: 461–482.
• Prawitz, D., 1967, „Úplnost a Hauptsatz pro logiku druhého řádu“, Theoria, 33: 246–258.
• –––, 1970, „O teorii důkazů matematické analýzy“, v Logice a hodnotě (Eseje věnované Thorildovi Dahlquistovi o jeho padesátých narozeninách), Filosofiska Studier (Filosof. Föreningen och Filosof. Inst.), Č. 9, Uppsala: Uppsala University, 169-180.
• Quine, W., 1940, „Recenze kostela 'Formulace jednoduché teorie typů',“Journal of Symbolic Logic, 5: 114.
• Ramsey, FP, 1926, „Základy matematiky,“Sborník London Mathematical Society, s2–25 (1), 338–384.
• Russell, B., 1903, Principy matematiky, Cambridge: Cambridge University Press.
• –––, 1908, „Matematická logika založená na teorii typů“, American Journal of Mathematics, 30: 222–262.
• –––, 1959, Můj filozofický vývoj, Londýn, New York: Routledge.
• Russell, B. and Whitehead, A., 1910, 1912, 1913, Principia Mathematica (3 svazky), Cambridge: Cambidge University Press.
• Reynolds, J., 1974, „Směrem k teorii typové struktury“, v Programming Symposium (Poznámky k přednáškám z informatiky: Svazek 19), Berlín: Springer, 408–425.
• –––, 1983, „Druhy, abstrakce a parametrický polymorfismus“, sborník z 9. světového počítačového kongresu IFIP, Paříž, 513–523.
• –––, 1984, „Polymorfismus není teoretický. Sémantika datových typů, “Přednáška z informatiky (svazek 173), Berlín: Springer, 145–156.
• –––, 1985, „Tři přístupy k typové struktuře. Matematické základy vývoje softwaru, “v Lecture Notes in Computer Science (Svazek 185), Berlín: Springer, 97–138.
• Schiemer, G. a Reck, EH, 2013, „Logika ve 30. letech: Teorie typů a teorie modelů,“Bulletin symbolické logiky, 19 (4): 433–472.
• Schütte, K., 1960, Beweistheorie, Berlín: Springer-Verlag.
• Scott, D., 1993 „Teoretická alternativa k ISWIM, CUCH, OWHY,“teoretická informatika, 121: 411–440.
• Skolem, T., 1970, Vybraná logická díla, Jens Erik Fenstad (ed.), Oslo: Universitetsforlaget.
• Tait, WW, 1967, „Intenzivní interpretace funkcionálů konečného typu“, Journal of Symbolic Logic, 32 (2): 198–212.
• Takeuti, G., 1955 „K základní domněnce GLC: I“, Journal of the Mathematical Society of Japan, 7: 249-275.
• –––, 1967, „Důkazy o shodě subsystémů klasické analýzy“, The Annals of Mathematics (Second Series), 86 (2): 299–348.
• Tarski, A., 1931, „Sur les ensembleles de nombres reels I,“Fundamenta Mathematicae, 17: 210–239.
• Urquhart, A., 2003, „Theory of Type“, The Cambridge Companion, Bertrand Russell, Nicholas Griffin (ed.), Cambridge: Cambridge University Press.
• Voevodsky, V., 2015, „Experimentální knihovna formalizované matematiky založené na univalentních základech,“dostupné matematické struktury v informatice, 25: 1278–1294.
• Wiener, N., 1914, „Zjednodušení logiky vztahů,“Sborník z Cambridge Philosophical Society, 17: 387–390.
• Weyl, H., 1946, „Matematika a logika“, American Mathematical Monthly, 53: 2–13.
• Zermelo, E., 1908, „Untersuchungen über die Grundlagen der Mengenlehre I,“Mathematische Annalen, 65: 261–281.

Akademické nástroje

	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

• Kubota, K., 2018, „Základy matematiky. Genealogie a přehled, “rukopis, návrh ze dne 27. března 2018.
• [HoTT 2013], Homotopy Type Theory: Univalent Foundations of Mathematics, Institute for Advanced Study.