Typ Theorie

Inhoudsopgave:

Typ Theorie
Typ Theorie

Video: Typ Theorie

Video: Typ Theorie
Video: Theorie Typ 3 2024, Maart
Anonim

Toegang navigatie

  • Inhoud van het item
  • Bibliografie
  • Academische hulpmiddelen
  • Vrienden PDF-voorbeeld
  • Info over auteur en citaat
  • Terug naar boven

Typ Theorie

Voor het eerst gepubliceerd op 8 februari 2006; inhoudelijke herziening di 17 jul.2018

Het onderwerp typetheorie is fundamenteel, zowel in de logica als in de informatica. We beperken ons hier tot het schetsen van enkele aspecten die belangrijk zijn in de logica. Voor het belang van typen in de informatica verwijzen we de lezer bijvoorbeeld naar Reynolds 1983 en 1985.

  • 1. Paradoxen en Russells typetheorieën
  • 2. Simple Type Theory en de (lambda) - Calculus
  • 3. Vertakte hiërarchie en impredicatieve principes
  • 4. Typ Theorie / Set-theorie
  • 5. Typetheorie / categorietheorie
  • 6. Extensies van Type System, Polymorphism, Paradoxes
  • 7. Univalente grondslagen
  • Bibliografie
  • Academische hulpmiddelen
  • Andere internetbronnen
  • Gerelateerde vermeldingen

1. Paradoxen en Russells typetheorieën

De typenleer werd door Russell geïntroduceerd om een aantal tegenstrijdigheden het hoofd te bieden die hij vond in zijn verslag van de verzamelingenleer en werd geïntroduceerd in "Appendix B: The Doctrine of Types" van Russell 1903. Deze tegenspraak werd verkregen door een stelling van Cantor te analyseren dat geen mapping

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

(waarbij (Pow (X)) de klasse van subklassen van een klasse is (X)) kan surjectief zijn; dat wil zeggen, (F) kan niet zodanig zijn dat elk lid (b) van (Pow (X)) gelijk is aan (F (a)) voor een bepaald element (a) van (X). Dit kan "intuïtief" worden geformuleerd als het feit dat er meer subsets van (X) zijn dan elementen van (X). Het bewijs hiervan is zo eenvoudig en fundamenteel dat het de moeite waard is om het hier te geven. Beschouw de volgende subset van (X):

[A = {x / in X / midden x / niet / in F (x) }.)

Deze subset mag niet binnen het bereik van (F) vallen. Voor if (A = F (a)), voor sommige (a), dan

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

wat een tegenstrijdigheid is. Enkele opmerkingen zijn in orde. Ten eerste maakt het bewijs geen gebruik van de wet van uitgesloten midden en is dus intuïtionistisch geldig. Ten tweede was de gebruikte methode, diagonalisatie genaamd, al aanwezig in het werk van du Bois-Reymond voor het bouwen van echte functies die sneller groeien dan welke functie dan ook in een bepaalde reeks functies.

Russell analyseerde wat er gebeurt als we deze stelling toepassen op het geval waarin A de klasse van alle klassen is, en geeft toe dat er zo'n klasse is. Hij werd vervolgens geleid om de speciale klasse van klassen te overwegen die niet van zichzelf zijn

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

We hebben dan

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

Het lijkt er inderdaad op dat Cantor zich al bewust was van het feit dat de klasse van alle sets niet als een set kan worden beschouwd.

Russell communiceerde dit probleem met Frege en zijn brief, samen met het antwoord van Frege, verschijnt in van Heijenoort 1967. Het is belangrijk om te beseffen dat de formulering (*) niet van toepassing is op het systeem van Frege. Zoals Frege zelf in zijn antwoord aan Russell schreef, is de uitdrukking "een predikaat is van zichzelf bepaald" niet exact. Frege maakte onderscheid tussen predikaten (concepten) en objecten. Een (eerste-orde) predikaat is van toepassing op een object, maar kan geen predikaat als argument hebben. De exacte formulering van de paradox in Frege's systeem maakt gebruik van de notie van de uitbreiding van een predikaat (P), dat we aanduiden als (varepsilon P). De uitbreiding van een predikaat is zelf een object. Het belangrijke axioma V is:

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

Dit axioma stelt dat de extensie van (P) identiek is aan de extensie van (Q) als en alleen als (P) en (Q) materieel equivalent zijn. Vervolgens kunnen we Russell's paradox (*) in Frege's systeem vertalen door het predikaat te definiëren

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

Vervolgens kan het gecontroleerd worden, met Axiom V op een cruciale manier

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

en we hebben ook een tegenstrijdigheid. (Merk op dat we voor het definiëren van het predikaat (R) een indicatieve existentiële kwantificering van predikaten hebben gebruikt. Er kan worden aangetoond dat de predicatieve versie van het Frege-systeem consistent is (zie Heck 1996 en voor verdere verfijningen Ferreira 2002).

Uit dit verslag blijkt duidelijk dat er al een idee van typen aanwezig was in Frege's werk: daar vinden we een onderscheid tussen objecten, predikaten (of concepten), predikaten van predikaten, enz. (Dit punt wordt benadrukt in Quine 1940.) Deze hiërarchie wordt door Russell (1959) de 'extensionale hiërarchie' genoemd en de noodzaak ervan werd door Russell erkend als een gevolg van zijn paradox.

2. Simple Type Theory en de (lambda) - Calculus

Zoals we hierboven zagen, lijkt het onderscheid: objecten, predikaten, predikaten van predikaten, enz. Genoeg om de paradox van Russell te blokkeren (en dit werd erkend door Chwistek en Ramsey). We beschrijven eerst de typestructuur zoals deze is in Principia en later in deze sectie presenteren we de elegante formulering die te danken is aan Church 1940 gebaseerd op (lambda) - calculus. De typen kunnen worden gedefinieerd als

  1. (i) is het type individuen
  2. ((,)) is het type proposities
  3. als (A_1, / ldots, A_n) typen zijn, dan is ((A_1, / ldots, A_n)) het type (n) - ary relaties over objecten van respectieve typen (A_1, / ldots, Een)

Het type binaire relaties over individuen is bijvoorbeeld ((i, i)), het type binaire connectieven is (((,), (,))), het type kwantoren over individuen is \(((ik))).

Voor het vormen van proposities gebruiken we deze typestructuur: dus (R (a_1, / ldots, a_n)) is een propositie als (R) van het type ((A_1, / ldots, A_n)) en (a_i) is van het type (A_i) voor (i = 1, / ldots, n). Deze beperking maakt het onmogelijk om een voorstel van de vorm (P (P)) te vormen: het type (P) moet de vorm ((A)) hebben en (P) kan alleen worden toegepast op argumenten van het type (A), en kunnen dus niet op zichzelf worden toegepast omdat (A) niet hetzelfde is als ((A)).

Maar eenvoudige typetheorie is niet voorspellend: we kunnen een object (Q (x, y)) van type ((i, i)) definiëren door

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

Stel dat we twee individuen (a) en (b) hebben zodat (Q (a, b)) geldt. We kunnen (P (x)) definiëren als (Q (x, a)). Het is dan duidelijk dat (P (a)) geldt, aangezien het (Q (a, a)) is. Daarom geldt (P (b)) ook. We hebben op een impedicatieve manier bewezen dat (Q (a, b)) impliceert (Q (b, a)).

Alternatieve, eenvoudigere formuleringen, die alleen het idee van klassen, klassen van klassen, enz. Behouden, werden opgesteld door Gödel en Tarski. Eigenlijk werd deze eenvoudigere versie door Gödel gebruikt in zijn paper uit 1931 over formeel onbeslisbare stellingen. De ontdekking van de onbeslisbare stellingen is mogelijk ingegeven door een heuristisch argument dat het onwaarschijnlijk is dat de volledigheidsstelling van de eerste-orde logica kan worden uitgebreid tot de typetheorie (zie het einde van zijn lezing op Königsberg 1930 in Gödel Collected Work, Volume III) en Goldfarb 2005). Tarski had een versie van de definieerbaarheidstheorie uitgedrukt in typetheorie (zie Hodges 2008). Zie Schiemer en Reck 2013.

We hebben objecten van type 0, voor individuen, objecten van type 1, voor klassen van individuen, objecten van type 2, voor klassen van individuen, enzovoort. Functies van twee of meer argumenten, zoals relaties, hoeven niet te worden opgenomen onder primitieve objecten, aangezien men relaties kan definiëren als klassen van geordende paren en geordende paren als klassen van klassen. Het geordende paar individuen a, b kan bijvoorbeeld worden gedefinieerd als ({ {a }, {a, b } }) waar ({x, y }) staat voor de klasse waarvan de enige elementen (x) en (y) zijn. (Wiener 1914 had een vergelijkbare reductie van relaties tot klassen voorgesteld.) In dit systeem hebben alle proposities de vorm (a (b)), waarbij (a) een teken is van type (n + 1) en (b) een teken van type (n). Dit systeem is dus gebaseerd op het concept van een willekeurige klasse of subset van objecten van een bepaald domein en op het feit dat het verzamelen van alle subsets van het gegeven domein een nieuw domein van het volgende type kan vormen. Uitgaande van een bepaald domein van individuen wordt dit proces herhaald. Zoals bijvoorbeeld in Scott 1993 werd benadrukt, wordt in de verzamelingenleer dit proces van het vormen van deelverzamelingen herhaald in het transfiniet.

In deze versies van de typetheorie, zoals in de verzamelingenleer, zijn functies geen primitieve objecten, maar worden ze weergegeven als functionele relatie. De optelfunctie wordt bijvoorbeeld weergegeven als een ternaire relatie door een object van het type ((i, i, i)). Een elegante formulering van de eenvoudige typetheorie die deze uitbreidt door functies als primitieve objecten te introduceren, werd door Church in 1940 gegeven. Het gebruikt de (lambda) - calculusnotatie (Barendregt 1997). Aangezien een dergelijke formulering belangrijk is in de informatica, voor de verbinding met de categorietheorie en voor de Martin-Löf-typetheorie, beschrijven we deze in meer detail. In deze formulering worden predikaten gezien als een speciaal soort functies (propositionele functies), een idee dat teruggaat tot Frege (zie bijvoorbeeld Quine 1940). Bovendienhet begrip functie wordt gezien als primitiever dan het begrip predikaten en relaties, en een functie wordt niet meer gedefinieerd als een speciaal soort relatie. (Oppenheimer en Zalta 2011 presenteert enkele argumenten tegen een dergelijke primitieve representatie van functies.) De typen van dit systeem worden als volgt inductief gedefinieerd

  1. er zijn twee basistypen (i) (het type individuen) en (o) (het type proposities)
  2. als (A, B) typen zijn, dan is (A / rightarrow B), het type functies van (A) tot (B), een type

We kunnen op deze manier de typen vormen:

(i / rightarrow o) (type predikaten)
((i / rightarrow o) rightarrow o) (type predikaten van predikaten)

die overeenkomen met de types ((i)) en (((i))) maar ook met de nieuwe types

(i / rightarrow i) (type functies)
((i / rightarrow i) rightarrow i) (type functionaliteiten)

Het is handig om te schrijven

[A_1, / ldots, A_n / rightarrow B)

voor

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

Op deze manier

[A_1, / ldots, A_n / rightarrow o)

komt overeen met het type ((A_1, / ldots, A_n)).

Logica van de eerste orde houdt alleen rekening met typen van het formulier

(i, / ldots, i / rightarrow i) (type functiesymbolen), en
(i, / ldots, i / rightarrow o) (type predikaat, relatiesymbolen)

Let erop dat

[A / rightarrow B / rightarrow C)

betekent

[A / rightarrow (B / rightarrow C))

(associatie naar rechts).

Voor de termen van deze logica zullen we Church's verslag niet volgen, maar een kleine variatie daarop, vanwege Curry (die soortgelijke ideeën had voordat Church's paper verscheen) en die in detail wordt gepresenteerd in R. Hindley's boek over typetheorie. Net als Church gebruiken we (lambda) - calculus, wat een algemene notatie geeft voor functies

[M:: = x / mid MM / mid / lambda xM)

Hier hebben we de zogenaamde BNF-notatie gebruikt, erg handig in de informatica. Dit geeft een syntactische specificatie van de (lambda) - termen die, indien uitgebreid, betekent:

  • elke variabele is een functiesymbool;
  • elke nevenschikking van twee functiesymbolen is een functiesymbool;
  • elke (lambda xM) is een functiesymbool;
  • er zijn geen andere functiesymbolen.

De notatie voor functietoepassing (MN) is een beetje anders dan de wiskundige notatie, die (M (N)) zou zijn. In het algemeen, [M_1 M_2 M_3)

betekent

[(M_1 M_2) M_3)

(associatie naar links). De term (lambda xM) stelt de functie voor die (N) associeert (M [x: = N)]. Deze notatie is zo handig dat je je afvraagt waarom deze niet veel wordt gebruikt in de wiskunde. De hoofdvergelijking van (lambda) - calculus is dan ((beta) - conversie)

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

wat de betekenis van (lambda xM) als functie uitdrukt. We hebben (M [x: = N)] gebruikt als een notatie voor de waarde van de uitdrukking die resulteert wanneer (N) wordt vervangen door de variabele (x) in de matrix (M). Men ziet deze vergelijking meestal als een herschrijfregel ((beta) - reductie)

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

In ongetypeerde lambda-calculus kan het zijn dat een dergelijke herschrijving niet eindigt. Het canonieke voorbeeld wordt gegeven door de term (Delta = / lambda xx x) en de applicatie

(Delta / Delta / rightarrow / Delta / Delta)

(Let op de gelijkenis met Russell's paradox.) Het idee van Curry is dan om typen te beschouwen als predikaten over lambda-termen, waarbij (M: A) wordt geschreven om uit te drukken dat (M) voldoet aan het predikaat / type (A). De betekenis van

[N: A / rechterpijl B)

is dan

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

wat de volgende regels rechtvaardigt

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

Over het algemeen werkt men met beoordelingen van het formulier

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

waar (x_1,…, x_n) verschillende variabelen zijn en (M) een term is met alle vrije variabelen onder (x_1,…, x_n). Om het systeem van de kerk te kunnen verkrijgen, voegt men enkele constanten toe om proposities te vormen. Typisch

niet: (o / rightarrow o)
impliceren: (o / rightarrow o / rightarrow o)
en: (o / rightarrow o / rightarrow o)
voor iedereen: ((A / rightarrow o) rightarrow o)

De voorwaarde

(lambda x. / neg (xx))

vertegenwoordigt het predikaat van predikaten die niet op zichzelf van toepassing zijn. Deze term heeft echter geen type, dat wil zeggen dat het niet mogelijk is om (A) zo te vinden

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

wat de formele uitdrukking is van het feit dat Russell's paradox niet kan worden uitgedrukt. Leibniz gelijkheid

[V: i / rightarrow i / rightarrow o)

zal worden gedefinieerd als

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

Men schrijft meestal (forall x [M)] in plaats van (forall (lambda xM)), en de definitie van (Q) kan dan worden herschreven als

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

Dit voorbeeld illustreert nogmaals dat we in eenvoudige typetheorie impredicatieve definities kunnen opstellen.

Het gebruik van (lambda) - termen en (beta) - reductie is het handigst om de complexe vervangingsregels weer te geven die nodig zijn in de eenvoudige typetheorie. Als we bijvoorbeeld het predikaat (lambda xQ ax) willen vervangen door (P) in de propositie

(impliceren (P a) (P b))

we krijgen

(impliceren ((lambda xQ ax) a) ((lambda xQ ax) b))

en met (beta) - reductie, (impliceren (Q aa) (Q ab))

Samenvattend verbiedt eenvoudige typetheorie zelftoepassing, maar niet de circulariteit die aanwezig is in impredicatieve definities.

Het (lambda) - calculusformalisme maakt ook een duidelijkere analyse van Russell's paradox mogelijk. We kunnen het zien als de definitie van het predikaat

[R x = / neg (xx))

Als we denken aan (beta) - reductie als het proces van het ontvouwen van een definitie, zien we dat er al een probleem is met het begrijpen van de definitie van RR

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

In zekere zin hebben we een niet-gefundeerde definitie, die net zo problematisch is als een tegenspraak (een voorstel dat equivalent is aan de ontkenning ervan). Een belangrijke stelling, de normalisatiestelling, zegt dat dit niet kan gebeuren met eenvoudige typen: als we (M: A) hebben, dan is (M) op een sterke manier normaliseerbaar (elke reeks reducties vanaf (M) eindigt).

Voor meer informatie over dit onderwerp verwijzen we naar het artikel over de eenvoudige typetheorie van de kerk.

3. Vertakte hiërarchie en impredicatieve principes

Russell introduceerde een andere hiërarchie, die niet ingegeven werd door enige formele paradoxen uitgedrukt in een formeel systeem, maar eerder door de angst voor 'circulariteit' en door informele paradoxen vergelijkbaar met de paradox van de leugenaar. Als een man zegt: 'Ik lieg', dan hebben we een situatie die doet denken aan Russell's paradox: een voorstel dat gelijk staat aan zijn eigen ontkenning. Een andere informele dergelijke paradoxale situatie wordt verkregen als we een geheel getal definiëren als het "minst gehele getal dat niet in minder dan 100 woorden kan worden gedefinieerd". Om dergelijke informele paradoxen te vermijden, vond Russell het nodig om een ander soort hiërarchie te introduceren, de zogenaamde 'vertakte hiërarchie'. In Bijlage B van Russell 1903 wordt gewezen op de noodzaak van een dergelijke hiërarchie. Interessant is dat dit daar verband houdt met de kwestie van de identiteit van gelijkwaardige proposities en van het logische product van een klasse van proposities. Een grondige bespreking is te vinden in hoofdstuk 10 van Russell 1959. Aangezien deze notie van vertakte hiërarchie buitengewoon invloedrijk is geweest in de logica en vooral in de bewijstheorie, beschrijven we deze in enkele details.

Om deze hiërarchie verder te motiveren, is hier een voorbeeld te danken aan Russell. Als we zeggen

Napoleon was Corsicaans.

we verwijzen in deze zin niet naar een verzameling eigendommen. De eigenschap "Corsicaans zijn" zou predicatief zijn. Als we het daarentegen zeggen

Napoleon had alle kwaliteiten van een grote generaal

we verwijzen naar een geheel van kwaliteiten. De eigenschap 'alle kwaliteiten van een grote generaal te hebben' zou indrukwekkend zijn.

Een ander voorbeeld, ook afkomstig van Russell, laat zien hoe impredicatieve eigenschappen mogelijk kunnen leiden tot problemen die doen denken aan de leugenaarsparadox. Stel dat we de definitie voorstellen

Een typische Engelsman is iemand die alle eigenschappen bezit die de meerderheid van de Engelsen bezit.

Het is duidelijk dat de meeste Engelsen niet alle eigenschappen bezitten die de meeste Engelsen bezitten. Daarom zou een typische Engelsman volgens deze definitie ongebruikelijk moeten zijn. Het probleem is volgens Russell dat het woord 'typisch' is gedefinieerd door een verwijzing naar alle eigenschappen en als een eigenschap is behandeld. (Het is opmerkelijk dat soortgelijke problemen zich voordoen bij het definiëren van het begrip willekeurige getallen, zie Martin-Löf "Opmerkingen over constructieve wiskunde" (1970).) Russell introduceerde de vertakte hiërarchie om de schijnbare circulariteit van zulke ongeplande definities aan te pakken. Men zou een onderscheid moeten maken tussen de eigenschappen van de eerste orde, zoals Corsicaans, die niet verwijzen naar het geheel van eigenschappen, en menen dat de eigenschappen van de tweede orde alleen verwijzen naar het geheel van eigenschappen van de eerste orde. Men kan dan eigenschappen van de derde orde introduceren, die kunnen verwijzen naar het geheel van eigenschappen van de tweede orde, enzovoort. Dit elimineert duidelijk alle circulariteiten die verband houden met impredicatieve definities.

Ongeveer tegelijkertijd voerde Poincaré een soortgelijke analyse uit. Hij benadrukte het belang van "predicatieve" classificaties en van het niet definiëren van elementen van een klasse met een kwantificering over deze klasse (Poincaré 1909). Poincaré gebruikte het volgende voorbeeld. Stel dat we een verzameling hebben met elementen 0, 1 en een bewerking + bevredigend

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

Laten we zeggen dat een eigenschap inductief is als deze 0 bevat en geldt voor (x + 1) als deze geldt voor (x).

Een suggestieve en potentieel "gevaarlijke" definitie zou zijn om een element te definiëren als een getal als het aan alle inductieve eigenschappen voldoet. Het is dan gemakkelijk aan te tonen dat deze eigenschap 'een nummer zijn' zelf inductief is. Inderdaad, 0 is een getal omdat het aan alle inductieve eigenschappen voldoet, en als (x) aan alle inductieve eigenschappen voldoet, dan geldt dat ook voor (x + 1). Evenzo is het gemakkelijk om te laten zien dat (x + y) een getal is als (x, y) getallen zijn. De eigenschap (Q (z)) dat (x + z) een nummer is, is inductief: (Q) (0) geldt sinds (x + 0 = x) en if (x + z) is een getal dan is (x + (z + 1) = (x + z) +1). Dit hele argument is echter circulair omdat de eigenschap 'een nummer zijn' niet predicatief is en met argwaan moet worden behandeld.

In plaats daarvan zou men een vertakte hiërarchie van eigenschappen en cijfers moeten introduceren. In het begin heeft men alleen inductieve eigenschappen van de eerste orde, die in hun definities niet verwijzen naar een geheel van eigenschappen, en men definieert de aantallen van orde 1 als de elementen die voldoen aan alle inductieve eigenschappen van de eerste orde. Vervolgens kan men de inductieve eigenschappen van de tweede orde beschouwen, die kan verwijzen naar de verzameling van eigenschappen van de eerste orde, en de nummers van orde 2, dat zijn de elementen die voldoen aan de inductieve eigenschappen van orde 2. Men kan dan op dezelfde manier aantallen van orde beschouwen 3, enzovoort. Poincaré benadrukt het feit dat een aantal orde 2 a fortiori een aantal orde 1 is, en meer in het algemeen een aantal orde (n + 1) a fortiori een aantal orde (n). We hebben dus een reeks van steeds meer beperkte eigenschappen:inductieve eigenschappen van orde 1, 2, … en een opeenvolging van steeds meer beperkte verzamelingen objecten: nummers van orde 1, 2, … Ook is de eigenschap "om een aantal orde te zijn (n)" zelf een inductieve eigendom van order (n + 1).

Het lijkt niet mogelijk om te bewijzen dat (x + y) een nummer van orde (n) is als (x, y) nummers van orde (n) zijn. Aan de andere kant is het mogelijk om te laten zien dat als (x) een aantal orde (n + 1) is en (y) een aantal orde (n + 1) dan (x + y) is een aantal bestelling (n). Inderdaad, de eigenschap (P (z)) dat "(x + z) een aantal orde (n) is" is een inductieve eigenschap van orde (n + 1: P) (0) geldt omdat (x + 0 = x) een aantal orde (n + 1) is, en dus van orde (n), en als (P (z)) geldt, is dat als (x + z) is een aantal volgorde (n), dan is (x + (z + 1) = (x + z) +1), en dus (P (z + 1)) houdt. Omdat (y) een aantal ordes is (n + 1), en (P (z)) een inductieve eigenschap is van order (n + 1, geldt P (y)) en dus (x + y) is een aantal bestelling (n). Dit voorbeeld illustreert goed de complexiteit van de vertakte hiërarchie.

De complexiteit wordt verder versterkt als men, zoals Russell zoals voor Frege, zelfs basisobjecten zoals natuurlijke getallen definieert als klassen van klassen. Zo wordt nummer 2 gedefinieerd als de klasse van alle klassen van individuen met precies twee elementen. We verkrijgen weer natuurlijke aantallen van verschillende ordes in de vertakte hiërarchie. Naast Russell zelf, en ondanks al deze complicaties, probeerde Chwistek op een vertakte manier rekenen te ontwikkelen, en Skolem benadrukte het belang van een dergelijke analyse. Zie Burgess and Hazen 1998 voor een recente ontwikkeling.

Een ander wiskundig voorbeeld, vaak gegeven, van een impredicatieve definitie is de definitie van de kleinste bovengrens van een begrensde klasse van reële getallen. Als we een real identificeren met de set rationals die kleiner zijn dan deze real, zien we dat deze kleinste bovengrens kan worden gedefinieerd als de vereniging van alle elementen in deze klasse. Laten we subsets van de rationelen identificeren als predikaten. Voor rationale getallen geldt bijvoorbeeld (q, P (q)) als iff (q) een lid is van de subset geïdentificeerd als (P). Nu definiëren we het predikaat (L_C) (een subset van de rationelen) als de laagste bovengrens van klasse (C) als:

(voorall q [L_C (q) leftrightarrow / bestaat P [C (P) wedge P (q)])

wat een belemmering is: we hebben een predikaat (L) gedefinieerd door een existentiële kwantificering over alle predikaten. Als (C) in de vertakte hiërarchie een klasse van rationelen van de eerste orde is, dan zal (L) een rationele klasse van de tweede orde zijn. Men verkrijgt dan niet één begrip of reële getallen, maar reële getallen van verschillende ordes 1, 2,… De kleinste bovengrens van een verzameling reals van order 1 zal dan in het algemeen van orde 2 zijn.

Zoals we eerder zagen, wordt nog een ander voorbeeld van een impredicatieve definitie gegeven door Leibniz 'definitie van gelijkheid. Voor Leibniz is het predikaat "is gelijk aan (a)" waar voor (b) iff (b) voldoet aan alle predikaten waaraan (a) voldoet.

Hoe moet men omgaan met de complicaties van de vertakte hiërarchie? Russell liet in de inleiding van de tweede editie van Principia Mathematica zien dat deze complicaties in sommige gevallen kunnen worden voorkomen. Hij dacht zelfs, in appendix B van de tweede editie van Principia Mathematica, dat de vertakte hiërarchie van natuurlijke getallen van orde 1,2, … instort in volgorde 5. Maar Gödel vond later een probleem in zijn argument, en inderdaad, het was Myhill 1974 toonde aan dat deze hiërarchie op geen enkel eindig niveau ineenstort. Een soortgelijk probleem,besproken door Russell in de inleiding van de tweede editie van Principia Mathematica komt naar voren als bewijs van de stelling van Cantor dat er geen injectiefuncties kunnen zijn van de verzameling van alle predikaten tot de verzameling van alle objecten (de versie van Russell's paradox in Frege's systeem dat we gepresenteerd in de inleiding). Kan dit worden gedaan in een vertakte hiërarchie? Russell betwijfelde of dit kon gebeuren binnen een vertakte hiërarchie van predikaten en dit werd inderdaad later bevestigd (Heck 1996).

Vanwege deze problemen introduceerden Russell en Whitehead in de eerste editie van Principia Mathematica het volgende reduceerbaarheids axioma: de hiërarchie van predikaten, eerste-orde, tweede-orde, enz. Stort in op niveau 1. Dit betekent dat voor elk predikaat van elk orde, is er een predikaat van het eerste-orde niveau dat er gelijk aan is. In het geval van gelijkheid postuleren we bijvoorbeeld een eerste-orde relatie "(a = b)" die equivalent is aan "(a) voldoet aan alle eigenschappen die (b) voldoet". De motivatie voor dit axioma was puur pragmatisch. Zonder dit worden alle wiskundige basisbegrippen, zoals echte of natuurlijke getallen, in verschillende ordenen verdeeld. Ondanks de schijnbare circulariteit van impredicatieve definities, lijkt het axioma van reduceerbaarheid niet te leiden tot inconsistenties.

Zoals echter eerst opgemerkt door Chwistek, en later door Ramsey, in het bijzijn van het axioma van reduceerbaarheid, heeft het eigenlijk helemaal geen zin om de vertakte hiërarchie in te voeren! Het is veel eenvoudiger om vanaf het begin ongepaste definities te accepteren. De simpele "extensieve" hiërarchie van individuen, klassen, klassen van klassen, … is dan voldoende. We krijgen op deze manier de eenvoudigere systemen geformaliseerd in Gödel 1931 of Kerk 1940 die hierboven werden gepresenteerd.

Het axioma van reduceerbaarheid vestigt de aandacht op de problematische status van impredicatieve definities. Om Weyl 1946 te citeren: het axioma van reduceerbaarheid “is een gedurfd, een bijna fantastisch axioma; er is weinig rechtvaardiging voor in de echte wereld waarin we leven, en helemaal niet in het bewijs waarop onze geest zijn constructies baseert”! Tot dusver zijn er geen tegenstellingen gevonden met behulp van het reduceerbaarheids axioma. Zoals we hieronder zullen zien, bevestigen proof-theoretische onderzoeken de extreme kracht van een dergelijk principe.

Het idee van de vertakte hiërarchie is buitengewoon belangrijk geweest in de wiskundige logica. Russell overwoog alleen de eindige iteratie van de hiërarchie: eerste orde, tweede orde enz., Maar vanaf het begin werd de mogelijkheid overwogen om de vertakking voor onbepaalde tijd uit te breiden. Poincaré (1909) noemt het werk van Koenig in deze richting. Voor het bovenstaande voorbeeld van getallen van verschillende orde, definieert hij ook een getal dat inductief is voor orde (omega) als het inductief is voor alle eindige ordes. Vervolgens wijst hij erop dat x + y inductief is voor orde (omega) als zowel (x) als (y) dat zijn. Dit toont aan dat de introductie van transfinite-orders in sommige gevallen de rol kan spelen van het axioma van reduceerbaarheid. Een dergelijke transfinite-uitbreiding van de vertakte hiërarchie werd verder geanalyseerd door Gödel, die het belangrijkste feit opmerkte dat de volgende vorm van het reduceerbaarheids-axioma eigenlijk bewijsbaar is: wanneer men de vertakte hiërarchie van eigenschappen over de natuurlijke getallen uitbreidt naar de transfinite, stort deze hiërarchie in op niveau (omega_1), de minst ontelbare ordinale (Gödel 1995 en Prawitz 1970). Hoewel op alle niveaus (lt / omega_1) de verzameling van predikaten telbaar is, is de verzameling van predikaten op niveau (omega_1) van kardinaliteit (omega_1). Dit feit was een sterke motivatie achter Gödel's model van bouwbare sets. In dit model is de verzameling van alle deelverzamelingen van de verzameling natuurlijke getallen (voorgesteld door predikaten) van kardinaliteit (omega_1) en is vergelijkbaar met de vertakte hiërarchie. Dit model voldoet op deze manier aan de Continuum Hypothese en geeft een relatief consistent bewijs van dit axioma. (De motivatie van Gödel was oorspronkelijk alleen om een model te bouwen waarin de verzameling van alle subsets van natuurlijke getallen goed geordend is.)

De vertakte hiërarchie is ook de bron geweest van veel werk in de bewijstheorie. Na de ontdekking door Gentzen dat de consistentie van rekenkunde kon worden bewezen door transfinite inductie (over beslisbare predikaten) langs de ordinale (varepsilon_0), was de natuurlijke vraag om de corresponderende ordinal te vinden voor de verschillende niveaus van de vertakte hiërarchie. Schütte (1960) ontdekte dat we voor het eerste niveau van de vertakte hiërarchie, dat wil zeggen als we de rekenkunde uitbreiden door alleen over eigenschappen van de eerste orde te kwantificeren, een systeem van ordinale kracht (varepsilon _ { varepsilon_0}) krijgen. Voor het tweede niveau krijgen we de ordinale sterkte (varepsilon _ { varepsilon_ { varepsilon_0}}), enz. We herinneren eraan dat (varepsilon _ { alpha}) de (alpha) - th / aangeeft (varepsilon) - volgnummer,an (varepsilon) - rangnummer is een rangnummer (beta) zodat (omega ^ { beta} = / beta), zie Schütte (1960).

Gödel benadrukte het feit dat zijn benadering van het probleem van de continuümhypothese niet constructief was, omdat het de ontelbare ordinale (omega_1) nodig heeft, en het was natuurlijk om de vertakte hiërarchie langs constructieve ordinalen te bestuderen. Na voorbereidende werken van Lorenzen en Wang analyseerde Schütte wat er gebeurt als we op de volgende meer constructieve manier te werk gaan. Aangezien rekenen voor ordinale kracht (varepsilon_0) geldt, beschouwen we eerst de iteratie van de vertakte hiërarchie tot (varepsilon_0). Schütte berekende de ordinale sterkte van het resulterende systeem en vond een ordinale sterkte (u (1) gt / varepsilon_0). We itereren vervolgens de vertakte hiërarchie tot aan deze ordinale (u (1)) en krijgen een systeem van ordinale kracht (u (2) gt u (1)), enz. Elke (u (k)) kan worden berekend in termen van de zogenaamde Veblen-hiërarchie:(u (k + 1)) is (phi_ {u (k)} (0)). De limiet van dit proces geeft een ordinale genaamd (Gamma_0): als we de vertakte hiërarchie herhalen tot aan de ordinale (Gamma_0), krijgen we een systeem van ordinale kracht (Gamma_0). Zo'n ordinaal werd rond dezelfde tijd onafhankelijk verkregen door S. Feferman. Er wordt beweerd dat (Gamma_0) voor predikatieve systemen een vergelijkbare rol speelt als (varepsilon_0) voor rekenkunde. Recente bewijstheoretische werken betreffen echter systemen met grotere bewijstheoretische ordinalen die als predicatief kunnen worden beschouwd (zie bijvoorbeeld Palmgren 1995). Er wordt beweerd dat (Gamma_0) voor predikatieve systemen een vergelijkbare rol speelt als (varepsilon_0) voor rekenkunde. Recente bewijstheoretische werken betreffen echter systemen met grotere bewijstheoretische ordinalen die als predicatief kunnen worden beschouwd (zie bijvoorbeeld Palmgren 1995). Er wordt beweerd dat (Gamma_0) voor predikatieve systemen een vergelijkbare rol speelt als (varepsilon_0) voor rekenkunde. Recente bewijstheoretische werken betreffen echter systemen met grotere bewijstheoretische ordinalen die als predicatief kunnen worden beschouwd (zie bijvoorbeeld Palmgren 1995).

Naast deze bewijstheoretische onderzoeken met betrekking tot de vertakte hiërarchie, is er in de bewijstheorie veel aandacht besteed aan het analyseren van de consistentie van het axioma van reduceerbaarheid, of, equivalent, de consistentie van impredicatieve definities. Na Gentzen's analyse van de cut-eliminatie-eigenschap in de sequent-calculus, vond Takeuti een elegante sequent-formulering van eenvoudige typetheorie (zonder vertakking) en maakte het gewaagde vermoeden dat cut-eliminatie voor dit systeem zou moeten gelden. Dit vermoeden leek in eerste instantie uiterst twijfelachtig, gezien de circulariteit van impredicatieve kwantificering, wat goed tot uiting komt in dit formalisme. De regel voor kwantificering is inderdaad

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

waarbij (T) een term is voor het predikaat, wat op zich een kwantificering kan zijn over alle predikaten. De formule (A [X: = T]) kan dus zelf veel complexer zijn dan de formule (A (X)).

Een vroeg resultaat is dat de eliminatie van bezuinigingen voor Takeuti's impredicatieve systeem op finitaire wijze de consistentie van rekenkunde van de tweede orde impliceert. (Eén toont aan dat dit de consistentie impliceert van een geschikte vorm van oneindigheids axioma, zie Andrews 2002.) Na het werk van Schütte werd later door W. Tait en D. Prawitz aangetoond dat inderdaad de eigenschap voor het elimineren van snijwonden geldt (het bewijs van dit moet een sterker proof-theoretisch principe gebruiken, zoals het zou moeten zijn volgens de onvolledigheidsstelling.)

Wat hier belangrijk is, is dat deze studies de extreme kracht van impredicatieve kwantificering hebben onthuld, of, equivalent, de extreme kracht van het axioma van reduceerbaarheid. Dit bevestigt op een bepaalde manier de intuïties van Poincaré en Russell. De bewijstheoretische kracht van rekenkunde van de tweede orde ligt ver boven alle vertakte uitbreidingen van rekenkunde die door Schütte worden beschouwd. Aan de andere kant zijn er, ondanks de circulariteit van impredicatieve definities, die zo expliciet wordt gemaakt in Takeuti's calculus, nog geen paradoxen gevonden in de tweede-orde rekenkunde.

Een andere onderzoeksrichting in de bewijstheorie was om te begrijpen hoeveel van de impredicatieve kwantificering kan worden verklaard uit principes die beschikbaar zijn in intuïtionistische wiskunde. De sterkste van dergelijke principes zijn sterke vormen van inductieve definities. Met dergelijke principes kan men een beperkte vorm van een impredicatieve kwantificering verklaren, genaamd (Pi_ {1} ^ 1) - begrip, waarbij men slechts één niveau van impredicatieve kwantificering gebruikt ten opzichte van predikaten. Interessant is dat bijna alle bekende toepassingen van impredicatieve kwantificeringen: Leibniz-gelijkheid, minst bovengrens, enz. Kunnen worden gedaan met (Pi_ {1} ^ 1) - begrip. Deze reductie van (Pi_ {1} ^ 1) - begrip werd voor het eerst bereikt door Takeuti op een vrij indirecte manier, en werd later vereenvoudigd door Buchholz en Schütte met behulp van de zogenaamde (Omega) - regel. Het kan worden gezien als een constructieve verklaring van een beperkt, maar niet triviaal gebruik van impredicatieve definities.

4. Typ Theorie / Set-theorie

Typetheorie kan worden gebruikt als basis voor wiskunde, en inderdaad, het werd als zodanig gepresenteerd door Russell in zijn paper uit 1908, dat in hetzelfde jaar verscheen als Zermelo's paper, waarin de verzamelingenleer werd gepresenteerd als een basis voor wiskunde.

Het is intuïtief duidelijk hoe we de typetheorie in de verzamelingenleer kunnen verklaren: een type wordt eenvoudigweg geïnterpreteerd als een set, en functietypen (A / rightarrow B) kunnen worden verklaard met behulp van het verzamelingenleerconcept (als functionele relatie dwz een set van paren elementen). Het type (A / rightarrow o) komt overeen met de powerset-bewerking.

De andere richting is interessanter. Hoe kunnen we het begrip sets in termen van typen verklaren? Er is een elegante oplossing dankzij A. Miquel, die een aanvulling vormt op eerdere werken van P. Aczel (1978) en die ook het voordeel heeft om niet noodzakelijkerwijs goed onderbouwde sets a la Finsler uit te leggen. Men interpreteert eenvoudig een set als een puntige grafiek (waarbij de pijl in de grafiek de lidmaatschapsrelatie vertegenwoordigt). Dit wordt heel handig weergegeven in de typetheorie, een puntige grafiek wordt eenvoudig gegeven door een type A en een paar elementen

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

We kunnen dan in typetheorie definiëren wanneer twee van dergelijke sets (A, a, R) en (B, b, S) gelijk zijn: dit is het geval als er een bisimulatie (T) is tussen (T) A) en (B) zodat (Tab) geldt. Een bisimulatie is een relatie

[T: A / rightarrow B / rightarrow o)

zodanig dat wanneer (Txy) en (Rxu) vasthouden, er (v) bestaat zodat (Tuv) en (Syv) vasthouden, en telkens wanneer (Txy) en (Ryv) hold, er bestaat (u) zodat (Tuv) en (Rxu) gelden. We kunnen dan de lidmaatschapsrelatie definiëren: de set vertegenwoordigd (B, b, S) is een lid van de set vertegenwoordigd door (A, a, R) als er (a_1) bestaat zodat (Ra_1a) en (A, a_1, R) en (B, b, S) zijn bisimilar.

Vervolgens kan worden gecontroleerd of alle gebruikelijke axioma's van uitbreidbaarheid van verzamelingenleer, machtsverzameling, vereniging, begrip van begrensde formules (en zelfs antifoundatie, zodat de lidmaatschapsrelatie niet gefundeerd hoeft te zijn) in dit eenvoudige model blijven. (Een begrensde formule is een formule waarbij alle kwantificaties de vorm hebben (forall x / in a / ldots) of (bestaat x / in a / ldots)). Op deze manier kan worden aangetoond dat de eenvoudige typetheorie van Church in overeenstemming is met de begrensde versie van Zermelo's verzamelingenleer.

5. Typetheorie / categorietheorie

Er zijn diepe verbanden tussen typetheorie en categorietheorie. We beperken ons tot het presenteren van twee toepassingen van typetheorie op categorietheorie: de constructies van de vrije cartesiaanse gesloten categorie en van de vrije topo's (zie het item over categorietheorie voor een uitleg van "cartesiaanse gesloten" en "topo's").

Voor het bouwen van de gratis cartesiaanse gesloten categorie, breiden we de eenvoudige typetheorie uit met het type 1 (type eenheid) en het producttype (A / maal B), voor (A, B) typen. De termen worden uitgebreid door koppelingsbewerkingen en projecties toe te voegen en een speciaal element van type 1. Net als in Lambek en Scott 1986, kan men dan een notie van getypte conversies tussen termen definiëren en laten zien dat deze relatie beslissend is. Men kan dan aantonen (Lambek en Scott 1986) dat de categorie met types als objecten en als morfismen van (A) tot (B) de set gesloten termen van type (A / rightarrow B) (met conversie als gelijkheid) is de vrije cartesiaanse gesloten categorie. Hiermee kan worden aangetoond dat gelijkheid tussen pijlen in deze categorie beslissend is.

De theorie van kerktypes kan ook gebruikt worden om de gratis topo's te bouwen. Hiervoor nemen we als objecten paren (A, E) met (A) type en (E) een gedeeltelijke equivalentierelatie, dat is een gesloten term (E: A / rightarrow A / rightarrow o) wat symmetrisch en transitief is. We nemen als morfismen tussen (A, E) en (B, F) de relaties (R: A / rightarrow B / rightarrow o) die functioneel zijn, zodat voor elke (a: A) om te voldoen aan (E aa) bestaat er één, en slechts één (modulo (F)) element (b) van (B) zodat (F bb) en (R ab). Voor de subobjectclassificatie nemen we het paar (o, E) met (E: o / rightarrow o / rightarrow o) gedefinieerd als

[EMN = / text {en} (impliceren \, MN) (impliceren \, NM))

Men kan dan aantonen dat deze categorie een topos vormt, inderdaad de gratis topo's.

Opgemerkt moet worden dat de typetheorie in Lambek en Scott 1986 een variatie van de typetheorie gebruikt, geïntroduceerd door Henkin en verfijnd door P. Andrews (2002), die een extensieve gelijkheid moet hebben als de enige logische verbindende, dat wil zeggen een polymorfe constante

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

en om alle logische connectieven te definiëren vanuit deze connectieve en constanten (T, F: o). Men definieert bijvoorbeeld

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

De gelijkheid bij type (o) is logische gelijkwaardigheid.

Een voordeel van de intensieve formulering is dat het een directe aantekening mogelijk maakt van bewijzen gebaseerd op (lambda) - calculus (Martin-Löf 1971 en Coquand 1986).

6. Extensies van Type System, Polymorphism, Paradoxes

We hebben de analogie gezien tussen de operatie A (rightarrow) A (rightarrow) o op types en de powerset operatie op sets. In de verzamelingenleer kan de powerset-bewerking voor onbepaalde tijd worden herhaald langs de cumulatieve hiërarchie. Het is dan normaal om te zoeken naar analoge transfinite versies van typetheorie.

Een dergelijke uitbreiding van Church's eenvoudige typetheorie wordt verkregen door universa toe te voegen (Martin-Löf 1970). Het toevoegen van een universe is een reflectieproces: we voegen een type (U) toe waarvan de objecten tot nu toe beschouwd zijn. Voor de eenvoudige typetheorie van Church zullen we hebben

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

en bovendien is (A) een type als (A: U). We kunnen dan typen als overwegen

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

en functies zoals

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

De functie-id neemt als argument een "klein" type (A: U) en een element (x) van type (A), en voert een element van type (A) uit. Meer in het algemeen, als (T (A)) een type is onder de aanname (A: U), kan men het afhankelijke type vormen

[(A: U) rechterpijl T (A))

Dat (M) van dit type is, betekent dat (MA: T (A)) altijd (A: U). We krijgen op deze manier uitbreidingen van de typetheorie waarvan de kracht vergelijkbaar is met die van de verzamelingenleer van Zermelo (Miquel 2001). Krachtigere vormen van universa worden overwogen in (Palmgren 1998). Miquel (2003) presenteert een versie van de type-theorie van sterkte die gelijkwaardig is aan die van Zermelo-Fraenkel.

Een zeer sterke vorm van universum wordt verkregen door de axioma (U: U) toe te voegen. Dit werd in 1970 voorgesteld door P. Martin-Löf. JY Girard toonde aan dat de resulterende typetheorie inconsequent is als logisch systeem (Girard 1972). Hoewel het in eerste instantie lijkt dat je Russell's paradox rechtstreeks zou kunnen reproduceren met een set van alle sets, is zo'n directe paradox eigenlijk niet mogelijk vanwege het verschil tussen sets en typen. De afleiding van een tegenstrijdigheid in een dergelijk systeem is inderdaad subtiel en eerder indirect geweest (hoewel het, zoals opgemerkt in Miquel 2001, nu kan worden herleid tot Russell's paradox door sets voor te stellen als puntige grafieken). JY Girard behaalde voor het eerst zijn paradox voor een zwakker systeem. Deze paradox werd later verfijnd (Coquand 1994 en Hurkens 1995). (Het begrip puur systeem, geïntroduceerd in Barendregt 1992,is handig om deze paradoxen scherp te formuleren.) In plaats van de axioma (U: U) gaat men er alleen van uit

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

als (T (A): U [A: U]). Let op de circulariteit, inderdaad van dezelfde soort als die welke wordt afgewezen door de vertakte hiërarchie: we definiëren een element van type (U) door kwantificering over alle elementen van (U). Bijvoorbeeld het type

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

zal het type zijn van de polymorfe identiteitsfunctie. Ondanks deze circulariteit was JY Girard in staat om normalisatie te tonen voor type systemen met deze vorm van polymorfisme. De uitbreiding van Church's eenvoudige typetheorie met polymorfisme is echter niet logisch als een logisch systeem, dat wil zeggen dat alle proposities (termen van type o) aantoonbaar zijn.

De motivatie van JY Girard om een typensysteem met polymorfisme te overwegen, was om de interpretatie van Gödel's Dialectica (Gödel 1958) uit te breiden tot rekenkunde van de tweede orde. Hij bewees normalisatie met behulp van de reduceerbaarheidsmethode, die was geïntroduceerd door Tait (1967) tijdens de analyse van Gödel 1958. Het is opmerkelijk dat de circulariteit die inherent is aan impredicativiteit niet resulteert in niet-normaliseerbare termen. (Girard's argument werd vervolgens gebruikt om aan te tonen dat cut-eliminatie eindigt in de hierboven gepresenteerde sequentiële calculus van Takeuti.) Een soortgelijk systeem werd onafhankelijk geïntroduceerd door J. Reynolds (1974) bij het analyseren van het begrip polymorfisme in de informatica.

Martin-Löf's introductie van een type van alle soorten komt voort uit de identificatie van het concept van proposities en typen, voorgesteld door het werk van Curry en Howard. Het is de moeite waard om hier zijn drie motiverende punten in herinnering te brengen:

  1. Russell's definitie van typen als betekenisbereiken van propositionele functies
  2. het feit dat men alle stellingen moet kwantificeren (impedicativiteit van de eenvoudige typetheorie)
  3. identificatie van propositie en typen

Gegeven (1) en (2) zouden we een soort proposities moeten hebben (zoals in de eenvoudige typetheorie), en gegeven (3) zou dit ook het type van alle typen moeten zijn. De paradox van Girard laat zien dat men niet tegelijkertijd (1), (2) en (3) kan hebben. De keuze van Martin-Löf was om weg te nemen (2), waarbij de typetheorie werd beperkt tot predicatief (en inderdaad, het begrip universum verscheen voor het eerst in de typetheorie als een predicatieve versie van het type van alle typen). De alternatieve keuze om mee te nemen (3) wordt besproken in Coquand 1986.

7. Univalente grondslagen

De verbanden tussen typetheorie, verzamelingenleer en categorietheorie krijgen een nieuw licht door het werk aan Univalent Foundations (Voevodsky 2015) en het Axiom of Univalence. Dit behelst op essentiële wijze de uitbreiding van de typetheorie die in de vorige paragraaf is beschreven, in het bijzonder afhankelijke typen, de opvatting van proposities als typen en de notie van typenuniversum. Deze ontwikkeling is ook relevant voor het bespreken van het begrip structuur, waarvan het belang bijvoorbeeld in Russell 1959 werd benadrukt.

Martin-Löf 1975 [1973] introduceerde een nieuw basistype (mathbf {Id} _A (a, b)), als (a) en (b) in het type (A) zitten, wat kan worden beschouwd als het type gelijkheidsbewijzen van het element (a) en (b). Een belangrijk kenmerk van dit nieuwe type is dat het kan worden herhaald, zodat we het type (mathbf {Id} _ { mathbf {Id} _A (a, b)} (p, q)) kunnen beschouwen als (p) en (q) zijn van het type (mathbf {Id} _A (a, b)). Als we een type beschouwen als een speciaal soort verzameling, is het logisch dat zo'n soort gelijkheidsbewijzen altijd wordt bewoond voor twee gelijkwaardigheidsbewijzen (p) en (q). Intuïtief lijkt er inderdaad hooguit een gelijkheidsbewijs te zijn tussen twee elementen (a) en (b). Verrassend genoeg ontwierpen Hofmann en Streicher 1996 een model van afhankelijke typetheorie waar dit niet geldig is,dat is een model waarin het verschillende bewijzen kunnen zijn dat twee elementen gelijk zijn. In dit model wordt een type geïnterpreteerd door een groupoid en het type (mathbf {Id} _A (a, b)) door de set isomorfismen tussen (a) en (b), set die kan meer dan één element hebben. Het bestaan van dit model heeft tot gevolg dat in de typetheorie in het algemeen niet kan worden bewezen dat een gelijkheidstype hoogstens één element heeft. Deze groupoid-interpretatie is op de volgende manier gegeneraliseerd, wat een intuïtieve interpretatie van het identiteitstype geeft. Een type wordt geïnterpreteerd door een topologische ruimte, tot homotopie, en een type (mathbf {Id} _A (a, b)) wordt geïnterpreteerd door het type paden dat (a) en (b) met elkaar verbindt. (Zie Awodey et al. 2013 en [HoTT 2013, Other Internet Resources].)een type wordt geïnterpreteerd door een groupoid en het type (mathbf {Id} _A (a, b)) door de set isomorfismen tussen (a) en (b), een set die er meer dan één kan hebben element. Het bestaan van dit model heeft tot gevolg dat in de typetheorie in het algemeen niet kan worden bewezen dat een gelijkheidstype hoogstens één element heeft. Deze groupoid-interpretatie is op de volgende manier gegeneraliseerd, wat een intuïtieve interpretatie van het identiteitstype geeft. Een type wordt geïnterpreteerd door een topologische ruimte, tot homotopie, en een type (mathbf {Id} _A (a, b)) wordt geïnterpreteerd door het type paden dat (a) en (b) met elkaar verbindt. (Zie Awodey et al. 2013 en [HoTT 2013, Other Internet Resources].)een type wordt geïnterpreteerd door een groupoid en het type (mathbf {Id} _A (a, b)) door de set isomorfismen tussen (a) en (b), een set die er meer dan één kan hebben element. Het bestaan van dit model heeft tot gevolg dat in de typetheorie in het algemeen niet kan worden bewezen dat een gelijkheidstype hoogstens één element heeft. Deze groupoid-interpretatie is op de volgende manier gegeneraliseerd, wat een intuïtieve interpretatie van het identiteitstype geeft. Een type wordt geïnterpreteerd door een topologische ruimte, tot homotopie, en een type (mathbf {Id} _A (a, b)) wordt geïnterpreteerd door het type paden dat (a) en (b) met elkaar verbindt. (Zie Awodey et al. 2013 en [HoTT 2013, Other Internet Resources].)Het bestaan van dit model heeft tot gevolg dat in de typetheorie in het algemeen niet kan worden bewezen dat een gelijkheidstype hoogstens één element heeft. Deze groupoid-interpretatie is op de volgende manier gegeneraliseerd, wat een intuïtieve interpretatie van het identiteitstype geeft. Een type wordt geïnterpreteerd door een topologische ruimte, tot homotopie, en een type (mathbf {Id} _A (a, b)) wordt geïnterpreteerd door het type paden dat (a) en (b) met elkaar verbindt. (Zie Awodey et al. 2013 en [HoTT 2013, Other Internet Resources].)Het bestaan van dit model heeft tot gevolg dat in de typetheorie in het algemeen niet kan worden bewezen dat een gelijkheidstype hoogstens één element heeft. Deze groupoid-interpretatie is op de volgende manier gegeneraliseerd, wat een intuïtieve interpretatie van het identiteitstype geeft. Een type wordt geïnterpreteerd door een topologische ruimte, tot homotopie, en een type (mathbf {Id} _A (a, b)) wordt geïnterpreteerd door het type paden dat (a) en (b) met elkaar verbindt. (Zie Awodey et al. 2013 en [HoTT 2013, Other Internet Resources].)b)) wordt geïnterpreteerd door het type paden dat (a) en (b) verbindt. (Zie Awodey et al. 2013 en [HoTT 2013, Other Internet Resources].)b)) wordt geïnterpreteerd door het type paden dat (a) en (b) verbindt. (Zie Awodey et al. 2013 en [HoTT 2013, Other Internet Resources].)

Voevodsky 2015 introduceerde de volgende stratificatie van typen. (Deze stratificatie werd gedeeltelijk ingegeven door deze interpretatie van een type als een topologische ruimte, maar kan direct worden begrepen zonder verwijzing naar deze interpretatie.) We zeggen dat een type (A) een propositie is als we (mathbf {Id} _A (a, b)) voor elk element (a) en (b) van (A) (dit betekent dat het type (A) maximaal één element heeft). We zeggen dat een type (A) een verzameling is als het type (mathbf {Id} _A (a, b)) een voorstel is voor elk element (a) en (b) van (EEN). We zeggen dat een type (A) een groupoid is als het type (mathbf {Id} _A (a, b)) een set is voor elk element (a) en (b) van (EEN). De rechtvaardiging van deze terminologie is dat kan worden aangetoond, alleen met behulp van de regels van de typetheorie, dat een dergelijk type inderdaad kan worden gezien als een groepoïde in de gebruikelijke categorische zin,waar de objecten de elementen van dit type zijn, wordt de verzameling morfismen tussen (a) en (b) weergegeven door de verzameling (mathbf {Id} _A (a, b)). De compositie is het bewijs van de vergankelijkheid van gelijkheid en het identiteitsmorfisme is het bewijs van de reflexiviteit van de gelijkheid. Het feit dat elk morfisme een inverse heeft, komt overeen met het feit dat identiteit een symmetrische relatie is. Deze stratificatie kan vervolgens worden uitgebreid en we kunnen definiëren wanneer een type een 2-groupoid, 3-groupoid enzovoort is. In deze visie verschijnt typetheorie als een uitgebreide generalisatie van verzamelingenleer, aangezien een verzameling een bepaald soort type is.en het identiteitsmorfisme is het bewijs van reflexiviteit van gelijkheid. Het feit dat elk morfisme een inverse heeft, komt overeen met het feit dat identiteit een symmetrische relatie is. Deze stratificatie kan vervolgens worden uitgebreid en we kunnen definiëren wanneer een type een 2-groupoid, 3-groupoid enzovoort is. In deze visie verschijnt typetheorie als een uitgebreide generalisatie van verzamelingenleer, aangezien een verzameling een bepaald soort type is.en het identiteitsmorfisme is het bewijs van reflexiviteit van gelijkheid. Het feit dat elk morfisme een inverse heeft, komt overeen met het feit dat identiteit een symmetrische relatie is. Deze stratificatie kan vervolgens worden uitgebreid en we kunnen definiëren wanneer een type een 2-groupoid, 3-groupoid enzovoort is. In deze visie verschijnt typetheorie als een uitgebreide generalisatie van verzamelingenleer, aangezien een verzameling een bepaald soort type is.

Voevodsky 2015 introduceert ook een notie van gelijkwaardigheid tussen typen, een notie die op een uniforme manier de noties van logische gelijkwaardigheid tussen proposities, bijectie tussen sets, categorische gelijkwaardigheid tussen groupoids, enzovoort generaliseert. We zeggen dat een kaart (f: A / rightarrow B) een equivalent is als voor elk element (b) in (B) het type paren (a, p) waar (p) is van het type (mathbf {Id} _B (fa, b)), is een voorstel en wordt bewoond. Dit drukt op een sterke manier uit dat een element in (B) de afbeelding is van precies één element in (A), en als (A) en (B) sets zijn, herstellen we het gebruikelijke idee bijectie tussen sets. (In het algemeen als (f: A / rightarrow B) een equivalent is, dan hebben we een kaart (B / rightarrow A), die kan worden gezien als het omgekeerde van (f).) Er kan bijvoorbeeld worden aangetoond dat de identiteitskaart altijd een equivalent is. Laat (text {Equiv} (A, B)) het type paren zijn (f, p) waarbij (f: A / rightarrow B) en (p) een bewijs is dat (f) is een equivalent. Gebruikmakend van het feit dat de identiteitskaart een equivalent is, hebben we een element van (text {Equiv} (A, A)) voor elk type (A). Dit houdt in dat we een kaart hebben

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

en de Axiom of Univalence stelt dat deze kaart een equivalent is. In het bijzonder hebben we de implicatie

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

en dus als er een gelijkwaardigheid is tussen twee kleine typen, dan zijn deze typen gelijk.

Dit Axioma kan worden gezien als een sterke vorm van het extensionaliteitsbeginsel. Het veralgemeent inderdaad het axioma van propositionele extensionaliteit dat door Church 1940 wordt genoemd, waarin staat dat twee logisch gelijkwaardige proposities gelijk zijn. Verrassend genoeg impliceert het ook het axioma van functie-uitbreiding, Axioma 10 in Church 1940, waarin staat dat twee puntsgewijze gelijke functies gelijk zijn (Voevodsky 2015). Het houdt ook direct in dat twee isomorfe sets gelijk zijn, dat twee categorisch equivalente groupoïden gelijk zijn, en dus één.

Dit kan gebruikt worden om een formulering te geven van het begrip transport van constructies (Bourbaki 1957) langs equivalenties. Laat (MA) bijvoorbeeld het type monoïde structuren zijn op de set (A): dit is het type tuples (m, e, p) waar (m) een binaire bewerking is op (A) en (e) een element van (A) en (p) een bewijs dat deze elementen voldoen aan de gebruikelijke monoïde wetten. De vervangingsregel van gelijk door gelijk heeft de vorm

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

Als er een bijectie is tussen (A) en (B), zijn ze gelijk aan het Axiom of Univalence, en we kunnen deze implicatie gebruiken om elke monoïde structuur van (A) in een monoïde structuur van (B).

We kunnen dit raamwerk ook gebruiken om de Russell 1959-discussie over het begrip structuur te verfijnen. Laat Monoid bijvoorbeeld het type paren (A, p) zijn waarbij (p) een element is van (MA). Twee van dergelijke paren (A, p) en (B, q) zijn isomorf als er een bijectie (f) bestaat van (A) naar (B) zodat (q) gelijk aan het transport van structuur van (p) langs (f). Een gevolg van het Axiom of Univalence is dat twee isomorfe elementen van het type Monoidzijn gelijk en delen dus dezelfde eigenschappen. Merk op dat een dergelijk algemeen transport van eigenschappen niet mogelijk is wanneer structuren worden geformuleerd in een verzameltheoretisch kader. In een set-theoretisch kader is het inderdaad mogelijk om eigenschappen te formuleren met behulp van de lidmaatschapsrelaties, bijvoorbeeld de eigenschap dat de dragerset van de structuur het natuurlijke nummer (0) bevat, eigenschap die in het algemeen niet wordt bewaard door isomorfismen. Intuïtief is de theoretische beschrijving van een structuur niet abstract genoeg omdat we kunnen praten over de manier waarop deze structuur is opgebouwd. Dit verschil tussen verzamelingenleer en typetheorie is nog een andere illustratie van de karakterisering door J. Reynolds 1983 van een typestructuur als een "syntactische discipline voor het afdwingen van het abstractieniveau".

Bibliografie

  • Aczel, P., 1978, "The type theoretic interpretation of constructive set theory", Logic Colloquium '77, Amsterdam: North-Holland, 55–66.
  • Andrews, P., 2002, Een inleiding tot wiskundige logica en typetheorie: tot waarheid door middel van bewijs (Applied Logic Series: Volume 27), Dordrecht: Kluwer Academic Publishers, tweede editie.
  • Awodey, S., Pelayo, A., Warren, M. 2013, "The Axiom of Univalence in Homotopy Type Theory", Notices of the American Mathematical Society, 60 (9): 1157–1164.
  • Barendregt, H., 1997, "The impact of the lambda calculus in logic and computer science", Bulletin of Symbolic Logic, 3 (2): 181–215.
  • –––, 1992, Lambda calculi met typen. Handbook of logic in computer science, Volume 2, Oxford, New York: Oxford University Press, 117–309.
  • Bell, JL, 2012, "Typen, sets en categorieën", in Akihiro Kanamory Handbook of the History of Logic. Deel 6: Sets en uitbreidingen in de twintigste eeuw, Amsterdam: Noord-Holland.
  • Bourbaki, N., 1958, Théorie des Ensembles, 3e editie, Paris: Hermann.
  • de Bruijn, NG, 1980, "A survey of the project AUTOMATH", in To HB Curry: essays on combinatory logic, lambda calculus and formalism, London-New York: Academic Press, 579–606.
  • Burgess JP en Hazen AP, 1998, 'Predicative Logic and Formal Arithmetic Source', Notre Dame J. Formal Logic, 39 (1): 1–17.
  • Buchholz, W. en K. Schütte, 1988, Proof theory of impredicative subsystems of analysis (Studies in Proof Theory: Monograph 2), Napels: Bibliopolis.
  • Church, A., 1940, "Een formulering van de eenvoudige theorie van typen", Journal of Symbolic Logic, 5: 56–68
  • –––, 1984, "Russells theorie van de identiteit van proposities", Philosophia Naturalis, 21: 513–522
  • Chwistek, L., 1948, The Limits of Science: Outline of Logic and of the Methodology of the Exact Sciences, London: Routledge en Kegan Paul.
  • Coquand, T., 1986, 'An analysis of Girard's paradox', Proceedings of the IEEE Symposium on Logic in Computer Science, 227–236.
  • –––, 1994, "Een nieuwe paradox in typetheorie", Stud. Logica gevonden. Wiskunde. (Volume 134), Amsterdam: Noord-Holland, 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, "Systemen voor predicatieve analyse", Journal of Symbolic Logic, 29: 1–30.
  • Ferreira, F. en Wehmeier, K., 2002, "Over de consistentie van het Delta-1-1-CA-fragment van 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. "Op weg naar Godel: de invloed van Rudolf Carnap." Bulletin van symbolische logica 11 (2): 185–193.
  • Gödel, K., 1995, Collected Works Volume III, Unpublished Essays and Lectures, Oxford: Oxford University Press, 1995.
  • –––, 1931, "Über formal untentscheidbare Sätze der Principia Mathematica und verwandter Systeme I", Monatshefte fü Mathematik und Physik, 38: 173–198.
  • –––, 1944, "Russells wiskundige logica", in De filosofie van Bertrand Russell, PA Schilpp (red.), 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, 'The consistent of predicative fragments of Frege's Grundgesetze der Arithmetik', History and Philosophy of Logic, 17 (4): 209–220.
  • van Heijenoort, 1967, Van Frege tot Gödel. Een bronnenboek in de wiskundige logica 1879–1931, Cambridge, MA: Harvard University Press.
  • Hindley, R., 1997, Basic Simple Type Theory, Cambridge: Cambridge University Press.
  • Hodges, W., 2008, "Tarski on Padoa's Method: een testcase voor het begrijpen van logici van andere tradities", in Logic, Navya-Nyāya and Applications: Homage to Bimal Krishna Matilal, Mihir K. Chakraborti et al. (red.), London: College Publications, pp. 155–169
  • Hofmann, M. en Streicher, Th. 1996, "The Groupoid interpretation of Type Theory", in vijfentwintig jaar constructieve typetheorie (Oxford Logic Guides: Volume 36), Oxford, New York: Oxford University Press, 83–111.
  • Howard, WA, 1980, "The formulas-as-types notion of construction", in To HB Curry: essays on combinatory logic, lambda calculus and formalism, London, New York: Academic Press, 480–490.
  • Hurkens, AJC, 1995, “Een vereenvoudiging van Girard's paradox. Typed lambda calculi and applications,”in Lecture Notes in Computer Science (Volume 902), Berlin: Springer: 266–278.
  • Lambek, J., 1980. "From (lambda) - calculus to Cartesian Closed Categories" in To HB Curry: Essays on Combinatory Logic, (lambda) - calculus en formalisme, J. Seldin en J. Hindley (redactie), Londen, New York: Academic Press. pp. 375–402.
  • Lambek, J. en Scott, PJ, 1986, Inleiding tot categorische logica van hogere orde (Cambridge Studies in Advanced Mathematics: Volume 7), Cambridge: Cambridge University Press; herdrukt 1988.
  • Lawvere, FW en Rosebrugh, R., 2003, Sets voor wiskunde, Cambridge: Cambridge University Press.
  • Martin-Löf, P., 1970, Opmerkingen over constructieve wiskunde, Stockholm: Almqvist & Wiksell.
  • –––, 1971, A Theory of Types, Technical Report 71–3, Stockholm: Stockholm University.
  • –––, 1998, "Een intuïtionistische typenleer", in vijfentwintig jaar constructieve typetheorie (Oxford Logic Guides: Volume 36), Oxford, New York: Oxford University Press, 127–172.
  • –––, 1975 [1973], "An intuitionistic theory of types: Predicative Part," in Logic Colloquium '73 (Proceedings of the Logic Colloquium, Bristol 1973) (Studies in Logic and the Foundations of Mathematics: Volume 80), HE Rose en JC Shepherdson (red.), Amsterdam: Noord-Holland, 73–118.
  • Myhill, J., 1974, "The Undefinability of the Set of Natural Numbers in the Ramified Principia", in Bertrand Russell's Philosophy, G. Nakhnikian (red.), London: Duckworth, 19–27.
  • Miquel, A., 2001, Le Calcul des Constructions impliciet: syntaxe et sémantique, Thèse de doctorat, Université Paris 7.
  • –––, 2003, "Een sterk normaliserende Curry-Howard-correspondentie voor IZF-verzamelingenleer", in Computer Science Logic (Lecture Notes in Computer Science, 2803), Berlin: Springer: 441–454.
  • Oppenheimer, P. en E. Zalta, 2011, "Relaties versus functies aan de basis van logica: type-theoretische overwegingen", Journal of Logic and Computation, 21: 351–374.
  • Palmgren, Erik, 1998, "On universes in type theory", in vijfentwintig jaar constructieve typetheorie (Oxford Logic Guides: Volume 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, "Competeness and Hauptsatz for second order logic", Theoria, 33: 246–258.
  • –––, 1970, "On the proof theory of mathematical analysis", in Logic and value (Essays gewijd aan Thorild Dahlquist op zijn vijftigste verjaardag), Filosofiska Studier (Filosof. Föreningen och Filosof. Inst.), Nr. 9, Uppsala: Uppsala University, 169–180.
  • Quine, W., 1940, "Review of Church 'A formulation of the simple theory of types'," Journal of Symbolic Logic, 5: 114.
  • Ramsey, FP, 1926, 'De grondslagen van de wiskunde', Proceedings of the London Mathematical Society, s2–25 (1), 338–384.
  • Russell, B., 1903, The Principles of Mathematics, Cambridge: Cambridge University Press.
  • –––, 1908, "Wiskundige logica zoals gebaseerd op de theorie van typen", American Journal of Mathematics, 30: 222–262.
  • –––, 1959, Mijn filosofische ontwikkeling, Londen, New York: Routledge.
  • Russell, B. en Whitehead, A., 1910, 1912, 1913, Principia Mathematica (3 delen), Cambridge: Cambidge University Press.
  • Reynolds, J., 1974, "Towards a theory of type structure", in Programming Symposium (Lecture Notes in Computer Science: Volume 19), Berlin: Springer, 408–425.
  • –––, 1983, "Types, Abstraction and Parametric Polymorphism", Proceedings of the IFIP 9th World Computer Congress, Parijs, 513–523.
  • –––, 1984: “Polymorfisme is geen verzamelingenleer. Semantiek van gegevenstypen, 'Lecture Notes in Computer Science (Volume 173), Berlin: Springer, 145–156.
  • –––, 1985: “Drie benaderingen van typestructuur. Wiskundige grondslagen van softwareontwikkeling ', in Lecture Notes in Computer Science (Volume 185), Berlin: Springer, 97–138.
  • Schiemer, G. en Reck, EH, 2013, 'Logic in the 1930s: Type Theory and Model Theory', The Bulletin of Symbolic Logic, 19 (4): 433–472.
  • Schütte, K., 1960, Beweistheorie, Berlijn: Springer-Verlag.
  • Scott, D., 1993 'Een typetheoretisch alternatief voor ISWIM, CUCH, OWHY', Theoretische informatica, 121: 411–440.
  • Skolem, T., 1970, Selected works in logic, Jens Erik Fenstad (red.), Oslo: Universitetsforlaget.
  • Tait, WW, 1967, "Dimensionale interpretaties van functionele eindige typen", Journal of Symbolic Logic, 32 (2): 198–212.
  • Takeuti, G., 1955 'Over het fundamentele vermoeden van GLC: I', Journal of the Mathematical Society of Japan, 7: 249–275.
  • –––, 1967, 'Consistentiebewijzen van subsystemen van klassieke analyse', The Annals of Mathematics (Second Series), 86 (2): 299–348.
  • Tarski, A., 1931, 'Sur les ensembles definissables de nombres reels I', Fundamenta Mathematicae, 17: 210–239.
  • Urquhart, A., 2003, 'The Theory of Types', in The Cambridge Companion aan Bertrand Russell, Nicholas Griffin (red.), Cambridge: Cambridge University Press.
  • Voevodsky, V., 2015, 'Een experimentele bibliotheek van geformaliseerde wiskunde op basis van univalente grondslagen', Mathematical Structures in Computer Science, 25: 1278–1294, online beschikbaar.
  • Wiener, N., 1914, 'Een vereenvoudiging van de logica van relaties', Proceedings of the Cambridge Philosophical Society, 17: 387–390.
  • Weyl, H., 1946, 'Wiskunde en logica', American Mathematical Monthly, 53: 2–13.
  • Zermelo, E., 1908, 'Untersuchungen über die Grundlagen der Mengenlehre I', 'Mathematische Annalen, 65: 261–281.

Academische hulpmiddelen

sep man pictogram
sep man pictogram
Hoe deze vermelding te citeren.
sep man pictogram
sep man pictogram
Bekijk een voorbeeld van de PDF-versie van dit item bij de Vrienden van de SEP Society.
inpho icoon
inpho icoon
Zoek dit itemonderwerp op bij het Internet Philosophy Ontology Project (InPhO).
phil papieren pictogram
phil papieren pictogram
Verbeterde bibliografie voor dit item op PhilPapers, met links naar de database.

Andere internetbronnen

  • Kubota, K., 2018, 'Foundations of Mathematics. Genealogie en overzicht”, manuscript, concept van 27 maart 2018.
  • [HoTT 2013], Homotopy Type Theory: Univalent Foundations of Mathematics, Institute for Advanced Study.

Aanbevolen: