Teoria Tipului

Cuprins:

Teoria Tipului
Teoria Tipului

Video: Teoria Tipului

Video: Teoria Tipului
Video: Informatica; cl. IX, "Tipuri de date structurate. Tipuri de date tablou unidimensional" 2024, Martie
Anonim

Navigare la intrare

  • Cuprins de intrare
  • Bibliografie
  • Instrumente academice
  • Prieteni PDF Previzualizare
  • Informații despre autor și citare
  • Inapoi sus

Teoria tipului

Publicat pentru prima dată miercuri, 8 februarie 2006; revizuire de fond mar 17 iulie 2018

Subiectul teoriei tipurilor este fundamental atât în logică, cât și în informatică. Ne limităm aici pentru a schița câteva aspecte care sunt importante în logică. Pentru importanța tipurilor în informatică, referim cititorul, de exemplu, la Reynolds 1983 și 1985.

  • 1. Paradoxuri și teorii de tip Russell
  • 2. Teoria tipului simplu și (lambda) - Calcul
  • 3. Ierarhia ramificată și principiile impredicative
  • 4. Introduceți teoria / teoria setului
  • 5. Teoria tipului / teoria categoriei
  • 6. Extensii ale sistemului de tip, polimorfism, paradoxuri
  • 7. Fundații univalente
  • Bibliografie
  • Instrumente academice
  • Alte resurse de internet
  • Intrări conexe

1. Paradoxuri și teorii de tip Russell

Teoria tipurilor a fost introdusă de Russell pentru a face față unor contradicții pe care le-a găsit în relatarea sa despre teoria seturilor și a fost introdusă în „Apendicele B: Doctrina tipurilor” de Russell 1903. Această contradicție a fost obținută prin analizarea unei teoreme a lui Cantor că nici o mapare

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

(unde (Pow (X)) este clasa subclaselor unei clase (X)) poate fi supusă; adică (F) nu poate fi astfel încât fiecare membru (b) din (Pow (X)) să fie egal cu (F (a)) pentru un element (a) din (X). Acest lucru poate fi exprimat „intuitiv” ca fiind faptul că există mai multe subseturi de (X) decât elementele (X). Dovada acestui fapt este atât de simplă și de bază, încât merită să o oferim aici. Luați în considerare următorul subset de (X):

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

Acest subset nu poate fi în intervalul (F). Pentru dacă (A = F (a)), pentru unii (a), atunci

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

ceea ce este o contradicție. Unele observații sunt în regulă. În primul rând, dovada nu folosește legea mijloacelor excluse și, prin urmare, este valabilă intuitiv. În al doilea rând, metoda folosită, numită diagonalizare, era deja prezentă în lucrarea du Bois-Reymond pentru construirea funcțiilor reale care cresc mai repede decât orice funcție dintr-o secvență dată de funcții.

Russell a analizat ce se întâmplă dacă aplicăm această teoremă în cazul în care A este clasa tuturor claselor, recunoscând că există o astfel de clasă. El a fost apoi condus să ia în considerare clasa specială a claselor care nu aparțin lor înșiși

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

Avem atunci

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

Se pare că Cantor era deja conștient de faptul că clasa tuturor seturilor nu poate fi considerată ca fiind un set.

Russell a comunicat această problemă lui Frege, iar scrisoarea sa, împreună cu răspunsul lui Frege apar în van Heijenoort 1967. Este important să ne dăm seama că formularea (*) nu se aplică așa cum este cazul sistemului Frege. Așa cum Frege însuși a scris în răspunsul său către Russell, expresia „un predicat este predicat de la sine” nu este exactă. Frege a făcut o distincție între predicate (concepte) și obiecte. Un predicat (de prim ordin) se aplică unui obiect, dar nu poate avea un argument predicat ca argument. Formularea exactă a paradoxului în sistemul lui Frege folosește noțiunea de extensie a unui predicat (P), pe care îl desemnăm drept (varepsilon P). Extensia unui predicat este ea însăși un obiect. Axiomul important V este:

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

Această axiomă afirmă că extensia (P) este identică cu extensia (Q) dacă și numai dacă (P) și (Q) sunt echivalente material. Putem traduce apoi paradoxul (*) al lui Russell în sistemul lui Frege prin definirea predicatului

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

Apoi poate fi verificat, folosind Axiom V într-un mod crucial

[R (varepsilon R) echiv / neg R (varepsilon R))

și avem și o contradicție. (Observați că pentru definirea predicatului (R), am folosit o cuantificare existențială impredicativă pe predicate. Se poate demonstra că versiunea predicativă a sistemului Frege este consecventă (vezi Heck 1996 și pentru alte rafinări Ferreira 2002).

Din această relatare reiese clar că o idee de tipuri era deja prezentă în lucrarea lui Frege: acolo găsim o distincție între obiecte, predicate (sau concepte), predicate ale predicatelor etc. (Acest punct este subliniat în Quine 1940.) Această ierarhie este numită „ierarhia extensivă” de Russell (1959), iar necesitatea acesteia a fost recunoscută de Russell ca urmare a paradoxului său.

2. Teoria tipului simplu și (lambda) - Calcul

După cum am văzut mai sus, distincția: obiecte, predicate, predicat de predicate etc., pare suficientă pentru a bloca paradoxul lui Russell (iar acest lucru a fost recunoscut de Chwistek și Ramsey). Mai întâi descriem structura tipului așa cum este în Principia și mai târziu în această secțiune prezentăm formularea elegantă datorată Bisericii 1940 bazată pe calcul (lambda) - calcul. Tipurile pot fi definite ca fiind

  1. (i) este tipul de indivizi
  2. ((,)) este tipul de propoziții
  3. dacă (A_1, / ldots, A_n) sunt tipuri atunci ((A_1, / ldots, A_n)) este tipul de relații (n) - ary peste obiecte de tipuri (A_1, / ldots, Un)

De exemplu, tipul de relații binare asupra indivizilor este ((i, i)), tipul de conexiuni binare este (((,), (,))), tipul de cuantificatori asupra indivizilor este (((i))).

Pentru formarea propozițiilor folosim această structură de tip: astfel (R (a_1, / ldots, a_n)) este o propunere dacă (R) este de tip ((A_1, / ldots, A_n)) și (a_i) este de tip (A_i) pentru (i = 1, / ldots, n). Această restricție face imposibilă formarea unei propoziții a formei (P (P)): tipul (P) ar trebui să fie de forma ((A)), iar (P) poate fi doar să fie aplicat la argumentele de tip (A) și, prin urmare, nu poate fi aplicat la sine, deoarece (A) nu este același cu ((A)).

Cu toate acestea, teoria tipurilor simple nu este predicativă: putem defini un obiect (Q (x, y)) de tip ((i, i)) prin

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

Presupunem că avem două persoane (a) și (b) astfel încât (Q (a, b)) să dețină. Putem defini (P (x)) să fie (Q (x, a)). Atunci este clar că (P (a)) reține, deoarece este (Q (a, a)). Prin urmare, (P (b)) ține și el. Am dovedit, într-un mod impredicativ, că (Q (a, b)) implică (Q (b, a)).

Gödel și Tarski au formulat formulări alternative mai simple, care păstrează doar noțiunea de clase, clase de clase etc. De fapt, această versiune mai simplă a fost folosită de Gödel în lucrarea sa din 1931 pe propuneri formal nedecidabile. Descoperirea propozițiilor nedecidabile ar fi putut fi motivată de un argument euristic, potrivit căruia este puțin probabil ca cineva să poată extinde teorema de completare a logicii de prim ordin la teoria tipului (vezi sfârșitul Prelegerii sale la Königsberg 1930 în Gödel Collected Work, Volumul III și Goldfarb 2005). Tarski a avut o versiune a teoremei definibilității exprimată în teoria tipurilor (vezi Hodges 2008). Vezi Schiemer și Reck 2013.

Avem obiecte de tip 0, pentru indivizi, obiecte de tip 1, pentru clase de indivizi, obiecte de tip 2, pentru clase de clase de indivizi, etc. Funcțiile a două sau mai multe argumente, cum ar fi relațiile, nu trebuie să fie incluse între obiectele primitive, deoarece se pot defini relațiile pentru a fi clase de perechi ordonate, iar perechile ordonate să fie clase de clase. De exemplu, perechea ordonată de indivizi a, b poate fi definită a fi ({ {a }, {a, b } }) unde ({x, y }) denotă clasa ale cărei unice elemente sunt (x) și (y). (Wiener 1914 a sugerat o reducere similară a relațiilor cu clasele.) În acest sistem, toate propunerile au forma (a (b)), unde (a) este un semn de tip (n + 1) și (b) un semn de tip (n). Astfel, acest sistem se bazează pe conceptul unei clase sau subseturi arbitrare de obiecte ale unui anumit domeniu și pe faptul că colectarea tuturor subseturilor domeniului dat poate forma un nou domeniu de tipul următor. Pornind de la un anumit domeniu de indivizi, acest proces este apoi iterat. Așa cum s-a subliniat, de exemplu, în Scott 1993, în teoria seturilor acest proces de formare a subseturilor este iterat în transfinit.

În aceste versiuni ale teoriei tipurilor, ca în teoria seturilor, funcțiile nu sunt obiecte primitive, ci sunt reprezentate ca relații funcționale. Funcția de adăugare, de exemplu, este reprezentată ca o relație ternară de un obiect de tip ((i, i, i)). O formulare elegantă a teoriei tipului simplu care o extinde prin introducerea funcțiilor ca obiecte primitive a fost dată de Biserică în 1940. Folosește notația (lambda) - calcul (Barendregt, 1997). Întrucât o astfel de formulare este importantă în informatică, pentru conexiunea cu teoria categoriilor și pentru teoria tipului Martin-Löf, o descriem în detaliu. În această formulare, predicatele sunt văzute ca un fel special de funcții (funcții propoziționale), idee care se întoarce la Frege (vezi de exemplu Quine 1940). În plus,noțiunea de funcție este văzută ca mai primitivă decât noțiunea de predicate și relații, iar o funcție nu mai este definită ca un tip special de relație. (Oppenheimer și Zalta 2011 prezintă câteva argumente împotriva unei reprezentări atât de primitive a funcțiilor.) Tipurile acestui sistem sunt definite inductiv după cum urmează

  1. există două tipuri de bază (i) (tipul de indivizi) și (o) (tipul de propoziții)
  2. dacă (A, B) sunt tipuri atunci (A / rightarrow B), tipul de funcții de la (A) la (B), este un tip

Putem forma astfel tipurile:

(i / rightarrow o) (tip de predicate)
((i / rightarrow o) rightarrow o) (tip de predicate de predicate)

care corespund tipurilor ((i)) și (((i))), dar și noilor tipuri

(i / rightarrow i) (tip de funcții)
((i / rightarrow i) rightarrow i) (tipul funcționalelor)

Este convenabil să scrii

[A_1, / ldots, A_n / rightarrow B)

pentru

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

În acest fel

[A_1, / ldots, A_n / rightarrow o)

corespunde tipului ((A_1, / ldots, A_n)).

Logica de prim ordin ia în considerare doar tipurile de formă

(i, / ldots, i / rightarrow i) (tipul simbolurilor funcției), și
(i, / ldots, i / rightarrow o) (tip de predicat, simboluri de relație)

Observa asta

[A / rightarrow B / rightarrow C)

înseamnă

[A / rightarrow (B / rightarrow C))

(asociere la dreapta).

Pentru termenii acestei logici, nu vom urma relatarea Bisericii, ci o ușoară variație a acesteia, datorită lui Curry (care avea idei similare înainte de apariția lucrării Bisericii) și care este prezentat în detaliu în cartea lui R. Hindley despre teoria tipurilor. La fel ca Biserica, folosim calculul (lambda) - care oferă o notare generală pentru funcții

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

Aici am folosit așa-numita notație BNF, foarte convenabilă în știința computerelor. Aceasta oferă o specificație sintactică a termenilor (lambda) care, atunci când este extins, înseamnă:

  • fiecare variabilă este un simbol al funcției;
  • fiecare juxtapunere a două simboluri funcționale este un simbol al funcției;
  • fiecare (lambda xM) este un simbol al funcției;
  • nu există alte simboluri funcționale.

Notarea pentru aplicarea funcțiilor (MN) este puțin diferită de notația matematică, care ar fi (M (N)). În general, [M_1 M_2 M_3)

înseamnă

[(M_1 M_2) M_3)

(asociere la stânga). Termenul (lambda xM) reprezintă funcția pe care se asociază (N) (M [x: = N)]. Această notare este atât de convenabilă încât ne întrebăm de ce nu este folosită pe scară largă în matematică. Ecuația principală a (lambda) - calcul este apoi ((beta) - conversie)

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

care exprimă semnificația lui (lambda xM) ca funcție. Am folosit (M [x: = N)] ca notare pentru valoarea expresiei care rezultă când (N) este înlocuită pentru variabila (x) din matrice (M). De obicei, cineva vede această ecuație ca o regulă de rescriere ((beta) - reducere)

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

În calculul lambda neatins, se poate ca această rescriere să nu se încheie. Exemplul canonic este dat de termenul (Delta = / lambda xx x) și de aplicație

(Delta / Delta / rightarrow / Delta / Delta)

(Observați asemănarea cu paradoxul lui Russell.) Ideea lui Curry este apoi să privească tipurile ca predicate peste termenii lambda, scriind (M: A) pentru a exprima că (M) satisface predicatul / tipul (A). Înțelesul lui

[N: A / rightarrow B)

este atunci

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

care justifică următoarele reguli

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

În general, unul funcționează cu judecăți ale formei

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

unde (x_1,…, x_n) sunt variabile distincte, iar (M) este un termen care are toate variabilele libere între (x_1,…, x_n). Pentru a putea obține sistemul Bisericii, se adaugă câteva constante pentru a forma propoziții. tipic

nu: (o / rightarrow o)
implică: (o / rightarrow o / rightarrow o)
și: (o / rightarrow o / rightarrow o)
pentru toți: ((A / rightarrow o) rightarrow o)

Termenul

(lambda x. / neg (xx))

reprezintă predicatul predicatelor care nu se aplică pentru ei înșiși. Cu toate acestea, acest termen nu are un tip, adică nu este posibil să se găsească (A) astfel

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

care este expresia formală a faptului că paradoxul lui Russell nu poate fi exprimat. Egalitatea Leibniz

[Q: i / rightarrow i / rightarrow o)

va fi definit ca fiind

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

Unul scrie de obicei (forall x [M)] în loc de (forall (lambda xM)), iar definiția lui (Q) poate fi rescrisă ca

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

Acest exemplu ilustrează din nou că putem formula definiții impredicative în teoria tipurilor simple.

Folosirea termenilor (lambda) - și (beta) - este cea mai convenabilă pentru reprezentarea regulilor complexe de substituție care sunt necesare în teoria tipurilor simple. De exemplu, dacă vrem să înlocuim predicatul (lambda xQ ax) cu (P) în propoziția

(implică (P a) (P b))

primim

(implică ((lambda xQ ax) a) ((lambda xQ ax) b))

și, folosind (beta) - reducere, (implică (Q aa) (Q ab))

În rezumat, teoria tipului simplu interzice autoaplicarea, dar nu și circularitatea prezentă în definițiile impredicative.

Formalismul de calcul (lambda) - permite, de asemenea, o analiză mai clară a paradoxului lui Russell. O putem vedea ca fiind definiția predicatului

[R x = / neg (xx))

Dacă ne gândim la reducerea (beta) ca fiind procesul de desfășurare a unei definiții, vedem că există deja o problemă în înțelegerea definiției RR

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

Într-un anumit sens, avem o definiție neîntemeiată, care este la fel de problematică ca o contradicție (o propoziție echivalentă cu negația ei). O teoremă importantă, teorema de normalizare, spune că acest lucru nu se poate întâmpla cu tipuri simple: dacă avem (M: A) atunci (M) este normalizabil într-un mod puternic (orice secvență de reduceri începând de la (M) se încheie).

Pentru mai multe informații despre acest subiect, ne referim la intrarea despre teoria tipului simplu a Bisericii.

3. Ierarhia ramificată și principiile impredicative

Russell a introdus o altă ierarhie, care nu a fost motivată de paradoxurile formale exprimate într-un sistem formal, ci mai degrabă de teama de „circularitate” și de paradoxurile informale similare cu paradoxul mincinosului. Dacă un om spune „mint”, atunci avem o situație care amintește de paradoxul lui Russell: o propoziție echivalentă cu propria negație. O altă situație informală, paradoxală, este obținută dacă definim un număr întreg ca fiind „cel mai puțin întreg nu poate fi definit în mai puțin de 100 de cuvinte”. Pentru a evita astfel de paradoxuri informale, Russell a considerat necesar să introducă un alt tip de ierarhie, așa-numita „ierarhie ramificată”. Necesitatea unei astfel de ierarhii este indicată în apendicele B din Russell 1903. Este interesant că acest lucru este legat de întrebarea identității propunerilor echivalente și a produsului logic al unei clase de propoziții. O discuție amănunțită poate fi găsită în capitolul 10 din Russell 1959. Întrucât această noțiune de ierarhie ramificată a fost extrem de influentă în logică și mai ales în teoria probelor, o descriem în unele detalii.

Pentru a motiva și mai mult această ierarhie, iată un exemplu datorat lui Russell. Dacă spunem

Napoleon era corsican.

nu ne referim în această propoziție la vreun ansamblu de proprietăți. Se spune că proprietatea „a fi corsic” este predicativă. Dacă spunem pe de altă parte

Napoleon avea toate calitățile unui mare general

ne referim la o totalitate de calități. Se spune că proprietatea „de a avea toate calitățile unui mare general” este impredicativă.

Un alt exemplu, provenit tot de la Russell, arată cum proprietățile impredicative pot duce la probleme care amintesc de paradoxul mincinos. Să presupunem că sugerăm definiția

Un englez tipic este unul care deține toate proprietățile deținute de majoritatea englezilor.

Este clar că majoritatea englezilor nu posedă toate proprietățile pe care majoritatea englezilor le dețin. Prin urmare, un englez tipic, în conformitate cu această definiție, ar trebui să fie lipsit de caracter. Problema, potrivit Russell, este că cuvântul „tipic” a fost definit printr-o referire la toate proprietățile și a fost tratat ca el însuși o proprietate. (Este remarcabil faptul că apar probleme similare la definirea noțiunii de numere aleatorii, cf. Martin-Löf „Note despre matematica constructivă” (1970).) Russell a introdus ierarhia ramificată pentru a face față circulației aparente a unor astfel de definiții impredicative. Ar trebui să facem o distincție între proprietățile de prim ordin, cum ar fi corsa, care nu se referă la totalitatea proprietăților și să considerăm că proprietățile de ordinul doi se referă doar la totalitatea proprietăților de prim ordin. Se poate introduce apoi proprietăți de ordinul al treilea, care se pot referi la totalitatea proprietăților de ordinul al doilea și așa mai departe. Aceasta elimină clar toate circularitățile conectate la definiții impredicative.

Aproximativ în același timp, Poincaré a efectuat o analiză similară. El a subliniat importanța clasificărilor „predicative” și de a nu defini elemente ale unei clase folosind o cuantificare peste această clasă (Poincaré 1909). Poincaré a folosit următorul exemplu. Presupunem că avem o colecție cu elementele 0, 1 și o operație + satisfăcătoare

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

Să spunem că o proprietate este inductivă dacă deține 0 și ține pentru (x + 1) dacă ține pentru (x).

O definiție impredicativă și potențial „periculoasă” ar fi să definească un element care să fie un număr dacă acesta satisface toate proprietățile inductive. Este apoi ușor de arătat că această proprietate „a fi un număr” este ea însăși inductivă. Într-adevăr, 0 este un număr deoarece satisface toate proprietățile inductive, iar dacă (x) satisface toate proprietățile inductive, atunci face și (x + 1). În mod similar este ușor de arătat că (x + y) este un număr dacă (x, y) sunt numere. Într-adevăr, proprietatea (Q (z)) care (x + z) este un număr este inductivă: (Q) (0) ține de când (x + 0 = x) și dacă (x + z) este un număr, la fel și (x + (z + 1) = (x + z) +1). Tot acest argument este circular, întrucât proprietatea „a fi un număr” nu este predicativă și trebuie tratată cu suspiciune.

În schimb, ar trebui să introducem o ierarhie ramificată de proprietăți și numere. La început, unul are doar proprietăți inductive de prim ordin, care nu se referă în definițiile lor la o totalitate de proprietăți, iar unul definește numerele de ordine 1 pentru a fi elementele care satisfac toate proprietățile inductive de prim ordin. În continuare se poate lua în considerare proprietățile inductive de ordinul al doilea, care se pot referi la colecția de proprietăți de ordinul întâi și la numerele de ordine 2, adică elementele care satisfac proprietățile inductive ale ordinului 2. Se poate lua în considerare în mod similar numere de ordine. 3 și așa mai departe. Poincaré subliniază faptul că un număr de ordine 2 este a fortiori un număr de ordine 1 și, în general, un număr de ordine (n + 1) este a fortiori un număr de ordine (n). Avem astfel o secvență de proprietăți din ce în ce mai restrânse:proprietăți inductive de ordinul 1, 2,… și o succesiune de colecții din ce în ce mai restrânse de obiecte: numere de ordine 1, 2,… De asemenea, proprietatea „a fi un număr de ordine (n)” este ea însăși o inductivă proprietatea comenzii (n + 1).

Nu pare posibil să se demonstreze că (x + y) este un număr de ordine (n) dacă (x, y) sunt numere de ordine (n). Pe de altă parte, este posibil să se arate că dacă (x) este un număr de ordine (n + 1), iar (y) un număr de ordine (n + 1) atunci (x + y) este un număr de ordine (n). Într-adevăr, proprietatea (P (z)) care „(x + z) este un număr de ordine (n)” este o proprietate inductivă a ordinii (n + 1: P) (0) reține deoarece (x + 0 = x) este un număr de ordine (n + 1) și, prin urmare, de ordine (n) și dacă (P (z)) deține, adică dacă (x + z) este un număr de ordine (n), atunci este și (x + (z + 1) = (x + z) +1) și deci (P (z + 1)) deține. Deoarece (y) este un număr de ordine (n + 1), iar (P (z)) este o proprietate inductivă a ordinii (n + 1, P (y)) deține și așa (x + y) este un număr de ordine (n). Acest exemplu ilustrează bine complexitățile introduse de ierarhia ramificată.

Complexitățile sunt amplificate și mai mult dacă unul, la fel ca Russell ca și pentru Frege, definește chiar și obiectele de bază precum numerele naturale ca clase de clase. De exemplu numărul 2 este definit ca clasa tuturor claselor de indivizi care au exact două elemente. Obținem din nou un număr natural de ordine diferite în ierarhia ramificată. În afară de Russell însuși și, în ciuda tuturor acestor complicații, Chwistek a încercat să dezvolte aritmetica într-un mod ramificat, iar Skolem a subliniat interesul unei astfel de analize. Vedeți Burgess și Hazen 1998 pentru o dezvoltare recentă.

Un alt exemplu matematic, adesea dat, al unei definiții impredicative este definiția celei mai puțin limită superioară a unei clase delimitate de numere reale. Dacă identificăm un real cu setul de raționamente care sunt mai mici decât acest real, vedem că această legătură minimă superioară poate fi definită ca uniunea tuturor elementelor din această clasă. Să identificăm subseturile raționalelor ca predicate. De exemplu, pentru numere raționale (q, P (q)) reține iff (q) este un membru al subsetului identificat ca (P). Acum, definim predicatul (L_C) (un subset al raționalelor) ca fiind cea mai mică limită superioară a clasei (C) ca:

(forall q [L_C (q) stânga dreaptă / există P [C (P) wedge P (q)])

ceea ce este impredicativ: am definit un predicat (L) printr-o cuantificare existențială asupra tuturor predicatelor. În ierarhia ramificată, dacă (C) este o clasă de clase de raționament de prim ordin, atunci (L) va fi o clasă de raționale de ordinul doi. Atunci nu se obține o singură noțiune sau numere reale, ci numere reale de diferite ordine 1, 2, … Cea mai mică limita superioară a unei colecții de realități de ordinul 1 va fi apoi cel puțin de ordinul 2 în general.

Așa cum am văzut mai devreme, încă un exemplu de definiție impredicativ este dat de definiția lui Leibniz de egalitate. Pentru Leibniz, predicatul „este egal cu (a)” este adevărat pentru (b) dacă (b) satisface toate predicatele satisfăcute de (a).

Cum trebuie tratat complicațiile introduse de ierarhia ramificată? Russell a arătat, în introducerea celei de-a doua ediții a Principia Mathematica, că aceste complicații pot fi evitate în unele cazuri. Chiar a crezut, în apendicele B a celei de-a doua ediții a Principia Mathematica, că ierarhia ramificată a numerelor naturale de ordinul 1,2, … se prăbușește la ordinul 5. Cu toate acestea, Gödel a găsit mai târziu o problemă în argumentul său și, într-adevăr, a fost a arătat Myhill 1974 că această ierarhie nu se prăbușește la niciun nivel finit. O problemă similară,discutat de Russell în introducerea la a doua ediție a Principia Mathematica apare în dovada teoremei lui Cantor că nu poate exista funcții injective de la colecția tuturor predicatelor la colecția tuturor obiectelor (versiunea paradoxului lui Russell în sistemul lui Frege pe care noi prezentat în introducere). Se poate face acest lucru într-o ierarhie ramificată? Russell s-a îndoit că acest lucru se poate realiza într-o ierarhie ramificată a predicatelor și acest lucru a fost într-adevăr confirmat într-adevăr mai târziu (Heck 1996).

Din cauza acestor probleme, Russell și Whitehead au introdus în prima ediție a Principia Mathematica următoarea axiomă de reducibilitate: ierarhia predicatelor, ordinul întâi, ordinea a doua etc., se prăbușește la nivelul 1. Aceasta înseamnă că pentru orice predicat al oricărui ordinea, există un predicat al nivelului de prim ordin care este echivalent cu acesta. În cazul egalității, de exemplu, postulăm o relație de prim ordin „(a = b)”, care este echivalentă cu „(a) satisface toate proprietățile pe care (b) le satisface”. Motivația acestui axiom a fost pur pragmatică. Fără aceasta, toate noțiunile matematice de bază, precum numerele reale sau naturale sunt stratificate în ordine diferite. De asemenea, în ciuda circularității aparente a definițiilor impredicative, axioma reducibilității nu pare să conducă la inconsistențe.

Așa cum a observat însă mai întâi Chwistek, și mai târziu de Ramsey, în prezența axiomului reducibilității, nu are niciun rost să introducem ierarhia ramificată deloc! Este mult mai simplu să accepți din start definiții impredicative. Simpla ierarhie „extensională” a indivizilor, claselor, claselor de clase,… este suficientă. Obținem în acest fel sistemele mai simple formalizate în Gödel 1931 sau în Biserica 1940 prezentate mai sus.

Axioma reducibilității atrage atenția asupra stării problematice a definițiilor impredicative. Pentru a cita Weyl 1946, axioma reducibilității „este o axiomă îndrăzneață, aproape fantastică; există prea puține justificări pentru aceasta în lumea reală în care trăim și deloc în dovezile pe care mintea noastră își bazează construcțiile”! Până în prezent, nu s-au găsit contradicții folosind axioma reducibilității. Cu toate acestea, după cum vom vedea mai jos, investigațiile teoretice ale probelor confirmă puterea extremă a unui astfel de principiu.

Ideea ierarhiei ramificate a fost extrem de importantă în logica matematică. Russell a luat în considerare doar iterarea finită a ierarhiei: ordinul întâi, ordinea a doua etc., dar, de la început, a fost luată în considerare posibilitatea extinderii ramificării transfinitor. Poincaré (1909) menționează activitatea lui Koenig în această direcție. Pentru exemplul de mai sus de numere de ordine diferite, el definește, de asemenea, un număr care să fie inductiv de ordine (omega) dacă este inductiv de toate ordinele finite. El subliniază că x + y este inductiv de ordine (omega) dacă ambele (x) și (y) sunt. Acest lucru arată că introducerea ordinelor transfinite poate juca, în unele cazuri, rolul axiomului de reducibilitate. O asemenea extindere transfinită a ierarhiei ramificate a fost analizată în continuare de Gödel, care a observat faptul esențial că următoarea formă a axiomului de reducibilitate este de fapt posibilă: atunci când se extinde ierarhia ramificată a proprietăților peste numerele naturale în transfinit, această ierarhie se prăbușește la nivel (omega_1), ordinul cel mai puțin de numărat (Gödel 1995 și Prawitz 1970). În plus, în timp ce la toate nivelurile (lt / omega_1), colectarea predicatelor este contabilă, colectarea predicatelor la nivel (omega_1) este de cardinalitate (omega_1). Acest fapt a fost o motivație puternică în spatele modelului de seturi construibile ale lui Gödel. În acest model, colecția tuturor subseturilor din setul de numere naturale (reprezentate de predicate) este de cardinalitate (omega_1) și este similară cu ierarhia ramificată. Acest model satisface în acest fel Ipoteza continuă și oferă o dovadă de consistență relativă a acestui axiom. (Motivația lui Gödel a fost inițial doar de a construi un model în care colecția tuturor subseturilor de numere naturale să fie bine ordonată.)

Ierarhia ramificată a fost, de asemenea, sursa multor lucrări în teoria probelor. După descoperirea de către Gentzen că coerența aritmeticii ar putea fi dovedită prin inducție transfinită (peste predicatele hotărâtoare) de-a lungul ordinalului (varepsilon_0), problema naturală era să găsească ordinalul corespunzător pentru diferitele niveluri ale ierarhiei ramificate. Schütte (1960) a constatat că pentru primul nivel al ierarhiei ramificate, aceasta este dacă extindem aritmetica cuantificând numai peste proprietățile de ordinul prim, obținem un sistem de forță ordinală (varepsilon _ { varepsilon_0}). Pentru cel de-al doilea nivel obținem puterea ordinală (varepsilon _ { varepsilon_ { varepsilon_0}}), etc. Reamintim că (varepsilon _ { alpha}) denotă (alpha) - th (varepsilon) - număr ordinal,un (varepsilon) - număr ordinal fiind un (beta) ordinal, astfel încât (omega ^ { beta} = / beta), vezi Schütte (1960).

Gödel a subliniat faptul că abordarea sa asupra problemei ipotezei continuului nu a fost constructivă, deoarece are nevoie de nenumăratul ordinal (omega_1), și era firesc să studieze ierarhia ramificată de-a lungul ordinelor constructive. După lucrările preliminare ale lui Lorenzen și Wang, Schütte a analizat ce se întâmplă dacă vom continua în felul mai constructiv. Deoarece aritmetica are pentru puterea ordinală (varepsilon_0), considerăm mai întâi iterarea ierarhiei ramificate până la (varepsilon_0). Schütte a calculat puterea ordinală a sistemului rezultat și a găsit o putere ordinală (u (1) gt / varepsilon_0). Am iterat apoi ierarhizat ramificat până la acest (u (1)) ordinal și obținem un sistem de putere ordinal (u (2) gt u (1)), etc. Fiecare (u (k)) poate fi calculat în termenii așa-numitei ierarhii Veblen:(u (k + 1)) este (phi_ {u (k)} (0)). Limita acestui proces dă un ordinal numit (Gamma_0): dacă vom itera ierarhia ramificată până la ordinal (Gamma_0) obținem un sistem de forță ordinală (Gamma_0). Un astfel de ordinal a fost obținut independent de același timp de către S. Feferman. S-a afirmat că (Gamma_0) joacă pentru sistemele predicative un rol similar cu (varepsilon_0) pentru Arithmetic. Cu toate acestea, lucrările recente teoretice ale probelor se referă la sisteme care au ordinale teoretice mai mari care pot fi considerate predicative (vezi, de exemplu, Palmgren 1995). S-a afirmat că (Gamma_0) joacă pentru sistemele predicative un rol similar cu (varepsilon_0) pentru Arithmetic. Cu toate acestea, lucrările recente teoretice ale probelor se referă la sisteme care au ordinale teoretice mai mari care pot fi considerate predicative (vezi, de exemplu, Palmgren 1995). S-a afirmat că (Gamma_0) joacă pentru sistemele predicative un rol similar cu (varepsilon_0) pentru Arithmetic. Cu toate acestea, lucrările recente teoretice ale probelor se referă la sisteme care au ordinale teoretice mai mari care pot fi considerate predicative (vezi, de exemplu, Palmgren 1995).

Pe lângă aceste investigații teoretice ale dovezilor legate de ierarhia ramificată, în teoria teoriei probelor s-a dedicat multă muncă analizării consistenței axiomului reducibilității sau, echivalent, a consistenței definițiilor impredicative. În urma analizei lui Gentzen a proprietății de eliminare a tăieturilor în calculul secvențial, Takeuti a găsit o formulare elegantă de secvență a teoriei tipului simplu (fără ramificare) și a făcut conjectura îndrăzneață pe care eliminarea tăietoare ar trebui să o țină pentru acest sistem. Această conjectură părea la început extrem de dubioasă, având în vedere circularitatea cuantificării impredicative, care se reflectă bine în acest formalism. Regula cuantificărilor este într-adevăr

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

unde (T) este orice termen predicat, care poate presupune el însuși o cuantificare asupra tuturor predicatelor. Astfel, formula (A [X: = T]) poate fi ea însăși mult mai complexă decât formula (A (X)).

Un rezultat timpuriu este faptul că eliminarea tăieturilor pentru sistemul impredicativ al lui Takeuti implică în mod finit consistența aritmeticii de ordinul doi. (Se arată că acest lucru implică consecvența unei forme adecvate de axiom de infinit, vezi Andrews 2002.) În urma lucrărilor lui Schütte, ulterior a fost arătat de W. Tait și D. Prawitz că proprietatea de eliminare a tăieturilor deține (dovada de aceasta trebuie să utilizeze un principiu teoretic mai puternic, așa cum ar trebui să fie în conformitate cu teorema incompletitudinii.)

Ceea ce este important aici este că aceste studii au relevat puterea extremă a cuantificării impredicative sau, echivalent, a puterii extreme a axiomului de reducibilitate. Acest lucru confirmă într-un fel intuițiile lui Poincaré și Russell. Puterea teoretică a aritmeticii de ordinul al doilea este cu mult peste toate extensiile ramificate ale aritmeticii considerate de Schütte. Pe de altă parte, în ciuda circularității definițiilor impredicative, care este atât de explicită în calculul lui Takeuti, nu s-au găsit încă paradoxuri în aritmetica de ordinul doi.

O altă direcție de cercetare în teoria dovezilor a fost aceea de a înțelege cât de mult din cuantificarea impredicativă poate fi explicată din principii care sunt disponibile în matematica intuiționalistă. Cele mai puternice astfel de principii sunt forme puternice de definiții inductive. Cu astfel de principii, se poate explica o formă limitată a unei cuantificări impredicative, numită (Pi_ {1} ^ 1) - înțelegere, unde se folosește doar un nivel de cuantificare impredicativă peste predicate. Este interesant faptul că aproape toate utilizările cunoscute ale cuantificărilor impredicative: egalitatea Leibniz, limita minimă superioară, etc., se poate face cu (Pi_ {1} ^ 1) - înțelegere. Această reducere a (Pi_ {1} ^ 1) - înțelegere a fost realizată pentru prima dată de Takeuti într-un mod destul de indirect, iar ulterior a fost simplificată de Buchholz și Schütte folosind așa-numita regulă (Omega) -. Poate fi văzută ca o explicație constructivă a unor utilizări restrânse, dar nepriceviale ale definițiilor impredicative.

4. Introduceți teoria / teoria setului

Teoria tipurilor poate fi folosită ca bază pentru matematică și, într-adevăr, a fost prezentată ca atare de Russell în lucrarea sa din 1908, apărută în același an cu lucrarea lui Zermelo, prezentând teoria seturilor ca fundament pentru matematică.

Este clar intuitiv cum putem explica teoria tipurilor în teoria seturilor: un tip este interpretat pur și simplu ca un set, iar tipurile de funcții (A / rightarrow B) pot fi explicate folosind noțiunea teoretică a funcției (ca relație funcțională, adică un set de perechi de elemente). Tipul (A / rightarrow o) corespunde operației powerset.

Cealaltă direcție este mai interesantă. Cum putem explica noțiunea de seturi în termeni de tipuri? Există o soluție elegantă, datorată lui A. Miquel, care completează lucrările anterioare ale lui P. Aczel (1978) și care are, de asemenea, avantajul de a explica seturi neapărat întemeiate a la Finsler. Se interpretează pur și simplu un set ca un grafic punctat (unde săgeata din grafic reprezintă relația de membru). Acest lucru este foarte convenabil reprezentat în teoria tipurilor, un grafic punctat fiind dat pur și simplu de un tip A și o pereche de elemente

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

Atunci putem defini în teoria tipurilor când două astfel de seturi (A, a, R) și (B, b, S) sunt egale: acesta este cazul dacă există o bisimulare (T) între (A) și (B) astfel încât (Tab) să păstreze. O bisimulare este o relație

[T: A / rightarrow B / rightarrow o)

astfel încât, de câte ori (Txy) și (Rxu) ține, există (v) astfel încât (Tuv) și (Syv) să țină, și de câte ori (Txy) și (Ryv)) mențineți, există (u) astfel încât (Tuv) și (Rxu) să țină. Putem defini apoi relația de membru: setul reprezentat (B, b, S) este un membru al setului reprezentat de (A, a, R) dacă există (a_1) astfel încât (Ra_1a) și (A, a_1, R) și (B, b, S) sunt bisimile.

Se poate verifica apoi că toate axiomele obișnuite ale extensionalității teoriei de seturi, setul de puteri, unirea, înțelegerea asupra formulelor delimitate (și chiar antifundarea, astfel încât relația de apartenență nu trebuie să fie întemeiată) în acest model simplu. (O formulă delimitată este o formulă în care toate cuantificările sunt de formă (forall x / în / ldots) sau (există x / în a / ldots)). În acest fel, se poate demonstra că teoria tipului simplu a Bisericii este în concordanță cu versiunea delimitată a teoriei de set a lui Zermelo.

5. Teoria tipului / teoria categoriei

Există conexiuni profunde între teoria tipurilor și teoria categoriilor. Ne limităm la prezentarea a două aplicații ale teoriei tipurilor la teoria categoriilor: construcțiile categoriei închise carteziene libere și topos-urilor libere (a se vedea intrarea în teoria categoriilor pentru o explicație a „închisului cartezian” și „topos”).

Pentru construirea categoriei închise carteziene gratuite, extindem teoria tipului simplu cu tipul 1 (tip de unitate) și tipul de produs (A / times B), pentru tipurile (A, B). Termenii sunt extinși prin adăugarea operațiunilor de asociere și proiecții și a unui element special de tip 1. La fel ca în Lambek și Scott 1986, se poate defini apoi o noțiune de conversii dactilografiate între termeni și arată că această relație este decisabilă. Se poate arăta apoi (Lambek și Scott 1986) că categoria cu tipuri ca obiecte și ca morfisme de la (A) la (B) setul de termeni închisi de tip (A / rightarrow B) (cu conversie ca egalitate) este categoria închisă carteziană liberă. Acest lucru poate fi utilizat pentru a arăta că egalitatea între săgețile din această categorie este decisivă.

Teoria tipurilor de Biserică poate fi folosită și pentru construirea toposurilor libere. Pentru aceasta, luăm ca perechi de obiecte (A, E) cu tipul (A) și (E) o relație de echivalență parțială, adică un termen închis (E: A / rightarrow A / rightarrow o) care este simetrică și tranzitivă. Luăm ca morfisme între (A, E) și (B, F) relațiile (R: A / rightarrow B / rightarrow o) care sunt funcționale, astfel încât pentru orice (a: A) satisfăcător (E aa) există unul și un singur element (modulo (F)) (b) din (B) astfel încât (F bb) și (R ab). Pentru clasificatorul subobiectului, luăm perechea (o, E) cu (E: o / rightarrow o / rightarrow o) definită ca

[EMN = / text {și} (implică \, MN) (implică \, NM))

Se poate arăta apoi că această categorie formează un topos, într-adevăr toposul liber.

Trebuie menționat că teoria tipurilor din Lambek și Scott 1986 folosește o variație a teoriei tipului, introdusă de Henkin și rafinată de P. Andrews (2002), care trebuie să aibă o egalitate extensivă ca unică conectivitate logică, adică o constantă polimorfă

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

și pentru a defini toate conectivitățile logice din această conectivitate și constante (T, F: o). De exemplu, unul definește

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

Egalitatea la tip (o) este echivalența logică.

Un avantaj al formulării intensive este faptul că permite notarea directă a probelor bazate pe calcul (lambda) - calcul (Martin-Löf 1971 și Coquand 1986).

6. Extensii ale sistemului de tip, polimorfism, paradoxuri

Am văzut analogia dintre operația A (rightarrow) A (rightarrow) o pe tipuri și operația poweret pe seturi. În teoria seturilor, operația powerset poate fi iterată transfinit de-a lungul ierarhiei cumulative. Este apoi firesc să căutăm versiuni transfinite analoge ale teoriei tipurilor.

O astfel de extensie a teoriei tipului simplu al Bisericii este obținută prin adăugarea de universuri (Martin-Löf 1970). Adăugarea unui univers este un proces de reflecție: adăugăm un tip (U) ale cărui obiecte sunt tipurile considerate până acum. Pentru teoria tipului simplu al Bisericii vom avea

[o: U, i: U / text {și} A / rightarrow B: U / text {dacă} A: U, B: U)

și, în plus, (A) este un tip dacă (A: U). Putem apoi să luăm în considerare tipuri precum

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

și funcții precum

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

ID-ul funcției are ca argument un tip „mic” (A: U) și un element (x) de tip (A) și scoate un element de tip (A). Mai general dacă (T (A)) este un tip sub presupunerea (A: U), se poate forma tipul dependent

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

Că (M) este de acest tip înseamnă că (MA: T (A)) ori de câte ori (A: U). Obținem în acest fel extensii ale teoriei de tip a căror forță este similară cu cea a teoriei de set a lui Zermelo (Miquel 2001). Formele de universuri mai puternice sunt luate în considerare în (Palmgren 1998). Miquel (2003) prezintă o versiune a teoriei tipului de forță echivalentă cu cea a lui Zermelo-Fraenkel.

O formă foarte puternică de univers este obținută prin adăugarea axiomului (U: U). Acest lucru a fost sugerat de P. Martin-Löf în 1970. JY Girard a arătat că teoria tipului rezultat este inconsistentă ca sistem logic (Girard 1972). Deși la început se pare că se poate reproduce direct paradoxul lui Russell folosind un set de toate seturile, un astfel de paradox direct nu este posibil, din cauza diferenței dintre seturi și tipuri. Într-adevăr, derivarea unei contradicții într-un astfel de sistem este subtilă și a fost mai degrabă indirectă (deși, așa cum s-a observat în Miquel 2001, ea poate fi acum redusă la paradoxul lui Russell reprezentând seturi ca grafice punctate). JY Girard și-a obținut pentru prima dată paradoxul pentru un sistem mai slab. Acest paradox a fost rafinat mai târziu (Coquand 1994 și Hurkens 1995). (Noțiunea de sistem de tip pur, introdusă în Barendregt 1992,este convenabil pentru a obține o formulare bruscă a acestor paradoxuri.) În loc de axiom (U: U), nu se presupune decât

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

dacă (T (A): U [A: U]). Observați circularitatea, într-adevăr de aceeași natură ca cea care este respinsă de ierarhia ramificată: definim un element de tip (U) prin cuantificarea tuturor elementelor (U). De exemplu tipul

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

va fi tipul funcției de identitate polimorfă. În ciuda acestei circularități, JY Girard a fost capabil să arate normalizarea sistemelor de tip cu această formă de polimorfism. Cu toate acestea, extinderea teoriei de tip simplu a Bisericii cu polimorfismul este inconsistentă ca sistem logic, adică toate propozițiile (termenii tipului o) sunt probabile.

Motivația lui JY Girard de a lua în considerare un sistem tip cu polimorfism a fost să extindă interpretarea lui Gödel Dialectica (Gödel 1958) la aritmetica de ordinul doi. El a dovedit normalizarea folosind metoda reducibilității, care a fost introdusă de Tait (1967) în timp ce a analizat Gödel 1958. Este destul de remarcabil faptul că circularitatea inerentă impredicativității nu are ca rezultat termeni non-normalizabili. (Argumentul lui Girard a fost folosit apoi pentru a arăta că eliminarea tăierii se termină în calculul secvențial al lui Takeuti prezentat mai sus.) Un sistem similar a fost introdus independent de J. Reynolds (1974) în timp ce analiza noțiunea de polimorfism în informatică.

Introducerea unui tip de toate tipurile lui Martin-Löf provine din identificarea conceptului de propuneri și tipuri, sugerat de lucrările lui Curry și Howard. Merită să ne amintim aici cele trei puncte motivante ale sale:

  1. Definiția lui Russell a tipurilor ca domenii ale semnificației funcțiilor propoziționale
  2. faptul că trebuie să cuantificăm toate propunerile (impredicativitatea teoriei tipului simplu)
  3. identificarea propoziției și tipurilor

Date (1) și (2) ar trebui să avem un tip de propoziții (ca în teoria tipurilor simple), iar dat (3) acesta ar trebui să fie și tipul tuturor tipurilor. Paradoxul lui Girard arată că nu se poate avea simultan (1), (2) și (3). Alegerea lui Martin-Löf a fost să scoată (2), limitând teoria tipului să fie predicativă (și, într-adevăr, noțiunea de univers a apărut mai întâi în teoria tipurilor ca versiune predicativă a tipului de toate tipurile). Alegerea alternativă de a lua (3) este discutată în Coquand 1986.

7. Fundații univalente

Conexiunile dintre teoria tipurilor, teoria seturilor și teoria categoriilor capătă o nouă lumină prin lucrarea asupra Fundațiilor univalente (Voevodsky 2015) și axiomului univalenței. Aceasta implică într-un mod esențial extinderea teoriei tipurilor descrisă în secțiunea anterioară, în special tipurile dependente, viziunea propozițiilor ca tipuri și noțiunea de univers de tipuri. Aceste dezvoltări sunt relevante și pentru discutarea noțiunii de structură, a cărei importanță a fost, de exemplu, subliniată în Russell 1959.

Martin-Löf 1975 [1973] a introdus un nou tip de bază (mathbf {Id} _A (a, b)), dacă (a) și (b) sunt de tip (A), care poate fi gândit ca tipul de dovezi privind egalitatea elementului (a) și (b). O caracteristică importantă a acestui nou tip este că poate fi iterată, astfel încât putem lua în considerare tipul (mathbf {Id} _ { mathbf {Id} _A (a, b)} (p, q)) dacă (p) și (q) sunt de tip (mathbf {Id} _A (a, b)). Dacă ne gândim la un tip ca la un tip special de set, este firesc să presupunem că un astfel de tip de dovezi de egalitate este întotdeauna locuit pentru orice două dovezi de egalitate (p) și (q). Într-adevăr, intuitiv, pare să existe cel mult o dovadă de egalitate între două elemente (a) și (b). Surprinzător, Hofmann și Streicher 1996 au conceput un model de teorie a tipului dependent în care acest lucru nu este valabil,acesta este un model în care pot fi dovezi diferite că două elemente sunt egale. În acest model, un tip este interpretat de un groupoid și tipul (mathbf {Id} _A (a, b)) de setul de izomorfisme dintre (a) și (b), set care poate au mai mult de un element. Existența acestui model are consecința că nu se poate dovedi, în general, în teoria tipurilor că un tip de egalitate are cel mult un element. Această interpretare gruppoidă a fost generalizată în felul următor, ceea ce oferă o interpretare intuitivă a tipului de identitate. Un tip este interpretat de un spațiu topologic, până la homotopie, iar un tip (mathbf {Id} _A (a, b)) este interpretat prin tipul de căi care leagă (a) și (b). (A se vedea Awodey et al. 2013 și [HoTT 2013, Alte resurse de Internet]).)un tip este interpretat de un groupoid și tipul (mathbf {Id} _A (a, b)) de setul de izomorfisme dintre (a) și (b), set care poate avea mai mult de unul element. Existența acestui model are consecința că nu se poate dovedi, în general, în teoria tipurilor că un tip de egalitate are cel mult un element. Această interpretare gruppoidă a fost generalizată în felul următor, ceea ce oferă o interpretare intuitivă a tipului de identitate. Un tip este interpretat de un spațiu topologic, până la homotopie, iar un tip (mathbf {Id} _A (a, b)) este interpretat prin tipul de căi care leagă (a) și (b). (A se vedea Awodey et al. 2013 și [HoTT 2013, Alte resurse de Internet]).)un tip este interpretat de un groupoid și tipul (mathbf {Id} _A (a, b)) de setul de izomorfisme dintre (a) și (b), set care poate avea mai mult de unul element. Existența acestui model are consecința că nu se poate dovedi, în general, în teoria tipurilor că un tip de egalitate are cel mult un element. Această interpretare gruppoidă a fost generalizată în felul următor, ceea ce oferă o interpretare intuitivă a tipului de identitate. Un tip este interpretat de un spațiu topologic, până la homotopie, iar un tip (mathbf {Id} _A (a, b)) este interpretat prin tipul de căi care leagă (a) și (b). (A se vedea Awodey et al. 2013 și [HoTT 2013, Alte resurse de Internet]).)Existența acestui model are consecința că nu se poate dovedi, în general, în teoria tipurilor că un tip de egalitate are cel mult un element. Această interpretare gruppoidă a fost generalizată în felul următor, ceea ce oferă o interpretare intuitivă a tipului de identitate. Un tip este interpretat de un spațiu topologic, până la homotopie, iar un tip (mathbf {Id} _A (a, b)) este interpretat prin tipul de căi care leagă (a) și (b). (A se vedea Awodey et al. 2013 și [HoTT 2013, Alte resurse de Internet]).)Existența acestui model are consecința că nu se poate dovedi, în general, în teoria tipurilor că un tip de egalitate are cel mult un element. Această interpretare gruppoidă a fost generalizată în felul următor, ceea ce oferă o interpretare intuitivă a tipului de identitate. Un tip este interpretat de un spațiu topologic, până la homotopie, iar un tip (mathbf {Id} _A (a, b)) este interpretat prin tipul de căi care leagă (a) și (b). (A se vedea Awodey et al. 2013 și [HoTT 2013, Alte resurse de Internet]).)b)) este interpretat de tipul căilor care leagă (a) și (b). (A se vedea Awodey et al. 2013 și [HoTT 2013, Alte resurse de Internet]).)b)) este interpretat de tipul căilor care leagă (a) și (b). (A se vedea Awodey et al. 2013 și [HoTT 2013, Alte resurse de Internet]).)

Voevodsky 2015 a introdus următoarea stratificare a tipurilor. (Această stratificare a fost motivată în parte de această interpretare a unui tip ca spațiu topologic, dar poate fi înțeleasă direct fără a face referire la această interpretare.) Spunem că un tip (A) este o propunere dacă avem (mathbf {Id} _A (a, b)) pentru orice element (a) și (b) din (A) (asta înseamnă că tipul (A) are cel mult un element). Spunem că un tip (A) este un set dacă tipul (mathbf {Id} _A (a, b)) este o propunere pentru orice element (a) și (b) din (A). Spunem că un tip (A) este un groupoid dacă tipul (mathbf {Id} _A (a, b)) este un set pentru orice element (a) și (b) din (A). Justificarea acestei terminologii este că se poate demonstra, folosind doar regulile teoriei tipurilor, că orice astfel de tip poate fi într-adevăr privit ca un gruppoid în sensul categoric obișnuit,unde obiectele sunt elementele de acest tip, setul de morfisme dintre (a) și (b) fiind reprezentat de setul (mathbf {Id} _A (a, b)). Compoziția este dovada tranzitivității egalității, iar morfismul identitar este dovada reflexivității egalității. Faptul că fiecare morfism are o inversă corespunde faptului că identitatea este o relație simetrică. Această stratificare poate fi extinsă și putem defini când un tip este un 2-grupoid, 3-grupoid și așa mai departe. În această privință, teoria tipurilor apare ca o vastă generalizare a teoriei de seturi, deoarece un set este un tip particular de tip.iar morfismul identitar este dovada reflexivității egalității. Faptul că fiecare morfism are o inversă corespunde faptului că identitatea este o relație simetrică. Această stratificare poate fi extinsă și putem defini când un tip este un 2-grupoid, 3-grupoid și așa mai departe. În această privință, teoria tipurilor apare ca o vastă generalizare a teoriei de seturi, deoarece un set este un tip particular de tip.iar morfismul identitar este dovada reflexivității egalității. Faptul că fiecare morfism are o inversă corespunde faptului că identitatea este o relație simetrică. Această stratificare poate fi extinsă și putem defini când un tip este un 2-grupoid, 3-grupoid și așa mai departe. În această privință, teoria tipurilor apare ca o vastă generalizare a teoriei de seturi, deoarece un set este un tip particular de tip.

Voevodsky 2015 introduce de asemenea o noțiune de echivalență între tipuri, noțiune care generalizează într-un mod uniform noțiunile de echivalență logică între propoziții, bijectie între mulțimi, echivalență categorică între grupuri și așa mai departe. Spunem că o hartă (f: A / rightarrow B) este o echivalență dacă, pentru orice element (b) din (B) tipul de perechi (a, p) unde (p)) este de tip (mathbf {Id} _B (fa, b)), este o propunere și este locuită. Aceasta exprimă într-un mod puternic că un element din (B) este imaginea exact a unui element din (A), iar dacă (A) și (B) sunt seturi, recuperăm noțiunea obișnuită de bijectie între mulțimi. (În general, dacă (f: A / rightarrow B) este o echivalență, atunci avem o hartă (B / rightarrow A), care poate fi considerată inversă a lui (f).) Se poate arăta, de exemplu, că harta identității este întotdeauna o echivalență. Fie (text {Equiv} (A, B)) tipul de perechi (f, p) unde (f: A / rightarrow B) și (p) este o dovadă că (f) este o echivalență. Folosind faptul că harta identității este o echivalență, avem un element (text {Equiv} (A, A)) pentru orice tip (A). Aceasta implică faptul că avem o hartă

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

iar Axioma univalenței afirmă că această hartă este o echivalență. În special, avem implicația

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

și deci dacă există o echivalență între două tipuri mici, atunci aceste tipuri sunt egale.

Acest Axiom poate fi văzut ca o formă puternică a principiului extensionalității. Într-adevăr, generalizează Axioma extensionalității propoziționale menționată de Biserica 1940, care afirmă că două propoziții logic echivalente sunt egale. În mod surprinzător, implică și Axiomul extensionalității funcției, Axiomul 10 din Biserica 1940, care afirmă că două funcții punctuale sunt egale (Voevodsky 2015). De asemenea, implică în mod direct că două seturi izomorfe sunt egale, că două grupoide echivalente categoric sunt egale, și deci una.

Aceasta poate fi utilizată pentru a da o formulare a noțiunii de transport de structuri (Bourbaki 1957) de-a lungul echivalențelor. De exemplu, să fie (MA) tipul de structuri monoide din set (A): acesta este tipul de tupluri (m, e, p) unde (m) este o operație binară pe (A) și (e) un element din (A) și (p) o dovadă că aceste elemente satisfac legile monoide obișnuite. Regula substituției egalului cu egal ia forma

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

Dacă există o bijecție între (A) și (B), acestea sunt egale prin Axiomul Univalenței și putem folosi această implicație pentru a transporta orice structură monoidă a (A) într-o structură monoidă a (B).

Putem folosi, de asemenea, acest cadru pentru a perfecționa discuția Russell din 1959 despre noțiunea de structură. De exemplu, lasă Monoid să fie tipul de perechi (A, p) unde (p) este un element din (MA). Două astfel de perechi (A, p) și (B, q) sunt izomorfe dacă există o bijecție (f) de la (A) la (B) astfel încât (q) este egal cu transportul structurii (p) de-a lungul (f). O consecință a Axiomului Univalenței este aceea că două elemente izomorfe de tipul Monoidsunt egale și, prin urmare, au aceleași proprietăți. Observați că un astfel de transport general de proprietăți nu este posibil atunci când structurile sunt formulate într-un cadru teoretic stabilit. Într-adevăr, într-un cadru teoretic stabilit, este posibilă formularea de proprietăți folosind relațiile de apartenență, de exemplu, proprietatea pe care setul purtător al structurii conține numărul natural (0), proprietate care nu este păstrată în general de izomorfisme. Intuitiv, descrierea teoretică setată a unei structuri nu este suficient de abstractă, deoarece putem vorbi despre modul în care este structurată această structură. Această diferență între teoria seturilor și teoria tipurilor este încă o ilustrare a caracterizării de către J. Reynolds 1983 a unei structuri de tip ca o „disciplină sintactică pentru aplicarea nivelului de abstractizare”.

Bibliografie

  • Aczel, P., 1978, „Interpretarea teoretică de tip a teoriei constructive a seturilor”, Logic Colloquium ’77, Amsterdam: Olanda de Nord, 55–66.
  • Andrews, P., 2002, O introducere în logica matematică și teoria tipurilor: la adevăr prin dovadă (Seria Logică Aplicată: Volumul 27), Dordrecht: Kluwer Academic Publishers, ediția a doua.
  • Awodey, S., Pelayo, A., Warren, M. 2013, „Axiomul univalenței în teoria tipului de homotopie”, Notices of the American Mathematical Society, 60 (9): 1157–1164.
  • Barendregt, H., 1997, „Impactul calculului lambda în logică și informatică”, Buletinul logicii simbolice, 3 (2): 181–215.
  • –––, 1992, calculi Lambda cu tipuri. Manual de logică în informatică, Volumul 2, Oxford, New York: Oxford University Press, 117–309.
  • Bell, JL, 2012, „Tipuri, seturi și categorii”, în Akihiro Kanamory Handbook of History of Logic. Volumul 6: Seturi și extensii în secolul XX, Amsterdam: Olanda de Nord.
  • Bourbaki, N., 1958, Théorie des Ensembles, ediția a III-a, Paris: Hermann.
  • de Bruijn, NG, 1980, „Un sondaj al proiectului AUTOMATH”, în To HB Curry: eseuri privind logica combinatorie, calcul lambda și formalism, London-New York: Academic Press, 579–606.
  • Burgess JP și Hazen AP, 1998, „Predicative Logic and Aritmetic Formal Source”, Notre Dame J. Formal Logic, 39 (1): 1–17.
  • Buchholz, W. și K. Schütte, 1988, Teoria probei subsistemelor impredicative de analiză (Studii în teoria probei: Monografia 2), Napoli: Bibliopolis.
  • Church, A., 1940, „O formulare a teoriei simple a tipurilor”, Journal of Symbolic Logic, 5: 56–68
  • –––, 1984, „Teoria lui Russell despre identitatea propunerilor”, Philosophia Naturalis, 21: 513–522
  • Chwistek, L., 1948, Limitele științei: conturul logicii și al metodologiei științelor exacte, Londra: Routledge și Kegan Paul.
  • Coquand, T., 1986, „O analiză a paradoxului lui Girard”, Proceedings of the IEEE Symposium on Logic in Computer Science, 227–236.
  • –––, 1994, „Un nou paradox în teoria tipului”, Stud. Logica găsită. Math. (Volumul 134), Amsterdam: Olanda de Nord, 555–570.
  • du Bois-Reymond, P., 1875, „Ueber asymptotische Werthe, infintaere Appproximationen and infitaere Aufloesung von Gleichungen”, Mathematische Annalen, 8: 363–1414.
  • Feferman, S., 1964, „Sisteme de analiză predicativă”, Journal of Symbolic Logic, 29: 1-30.
  • Ferreira, F. și Wehmeier, K., 2002, „Pe consistența fragmentului Delta-1-1-CA din 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. „Pe drumul lui Godel în: influența lui Rudolf Carnap.” Buletinul logicii simbolice 11 (2): 185–193.
  • Gödel, K., 1995, Opere colectate Volumul III, Eseuri și lecturi nepublicate, 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, „Logica matematică a lui Russell”, în Filosofia lui Bertrand Russell, PA Schilpp (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, „Consistența fragmentelor predicative din Frege’s Grundgesetze der Arithmetik”, History and Philosophy of Logic, 17 (4): 209–220.
  • van Heijenoort, 1967, De la Frege la Gödel. O carte sursă în logică matematică 1879–1931, Cambridge, MA: Harvard University Press.
  • Hindley, R., 1997, Teoria de bază de tip simplu, Cambridge: Cambridge University Press.
  • Hodges, W., 2008, „Tarski on Metoda Padoa: un caz de testare pentru înțelegerea logicienilor altor tradiții”, în Logic, Navya-Nyāya și Aplicații: Homage to Bimal Krishna Matilal, Mihir K. Chakraborti et al. (eds.), Londra: College Publications, pp. 155–169
  • Hofmann, M. și Streicher, Th. 1996, „Interpretarea grupului din teoria tipului”, în douăzeci și cinci de ani de teorie constructivă a tipului (Oxford Logic Guides: Volume 36), Oxford, New York: Oxford University Press, 83–111.
  • Howard, WA, 1980, „Formula-as-notion types of construction”, în To HB Curry: eseuri privind logica combinatorie, calcul lambda și formalism, London, New York: Academic Press, 480–490.
  • Hurkens, AJC, 1995, „O simplificare a paradoxului lui Girard. Calcule tip lambda și aplicații”, în Note de lectură în informatică (Volumul 902), Berlin: Springer: 266–278.
  • Lambek, J., 1980. „De la (lambda) - calcul la categoriile închise carteziene” în To HB Curry: Essays on Combinatory Logic, (lambda) - calcul și Formalism, J. Seldin și J. Hindley (eds.), Londra, New York: Academic Press. p. 375–402.
  • Lambek, J. și Scott, PJ, 1986, Introducere în logica categorică a ordinii superioare (Cambridge Studies in Advanced Mathematics: Volume 7), Cambridge: Cambridge University Press; reeditat 1988.
  • Lawvere, FW și Rosebrugh, R., 2003, Seturi pentru matematică, Cambridge: Cambridge University Press.
  • Martin-Löf, P., 1970, Note privind matematica constructivă, Stockholm: Almqvist & Wiksell.
  • –––, 1971, O teorie a tipurilor, raport tehnic 71–3, Stockholm: Universitatea din Stockholm.
  • –––, 1998, „O teorie intuiționalistă a tipurilor”, în Douăzeci și cinci de ani de teorie constructivă a tipurilor (Oxford Logic Guides: Volume 36), Oxford, New York: Oxford University Press, 127–172.
  • –––, 1975 [1973], „O teorie intuiționalistă a tipurilor: Partea predicativă”, în Logic Colloquium ’73 (Proceedings of the Logic Colloquium, Bristol 1973) (Studii în logică și fundamentele matematicii: volumul 80), Î. Rose și JC Shepherdson (eds.), Amsterdam: Olanda de Nord, 73–118.
  • Myhill, J., 1974, „Undefinability of the Set of Natural Numbers in the Ramified Principia”, în Bertrand Russell's Philosophy, G. Nakhnikian (ed.), London: Duckworth, 19–27.
  • Miquel, A., 2001, Le Calcul des Constructions implicite: syntaxe et sémantique, Thèse de doctorat, Université Paris 7.
  • –––, 2003, „O corespondență intensă a Curry-Howard pentru teoria seturilor IZF”, în Computer Science Logic (Lecture Notes in Computer Science, 2803), Berlin: Springer: 441–454.
  • Oppenheimer, P. și E. Zalta, 2011, „Relații versus funcții la fundamentele logicii: Considerații de tip teoretic”, Journal of Logic and Computation, 21: 351–374.
  • Palmgren, Erik, 1998, „Pe universuri în teoria tipurilor”, în Douăzeci și cinci de ani de Teorie de tip constructiv (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 moral, 17: 461–482.
  • Prawitz, D., 1967, „Completitudinea și Hauptsatz pentru logica de ordinul doi”, Theoria, 33: 246–258.
  • –––, 1970, „Cu privire la teoria probelor analizei matematice”, în Logică și valoare (Eseuri dedicate lui Thorild Dahlquist la cincisprezece ani de naștere), Filosofiska Studier (Filosof. Föreningen och Filosof. Inst.), Nr. 9, Uppsala: Universitatea Uppsala, 169-180.
  • Quine, W., 1940, „Revizuirea Bisericii„ O formulare a teoriei simple a tipurilor”,„ Journal of Symbolic Logic, 5: 114.
  • Ramsey, FP, 1926, „The basic of mathematics”, Proceedings of the London Mathematical Society, s2–25 (1), 338–384.
  • Russell, B., 1903, Principiile matematicii, Cambridge: Cambridge University Press.
  • –––, 1908, „Logica matematică, bazată pe teoria tipurilor”, American Journal of Mathematics, 30: 222–262.
  • –––, 1959, Dezvoltarea mea filozofică, Londra, New York: Routledge.
  • Russell, B. și Whitehead, A., 1910, 1912, 1913, Principia Mathematica (3 volume), Cambridge: Cambidge University Press.
  • Reynolds, J., 1974, „Spre o teorie a structurii tipului”, în Programing Symposium (Lecture Notes in Computer Science: Volume 19), Berlin: Springer, 408–425.
  • –––, 1983, „Tipuri, abstracție și polimorfism parametric”, Proceedings of the IFIP 9th World Computer Computer, Paris, 513–523.
  • –––, 1984, „Polimorfismul nu este teoretic. Semantica tipurilor de date”, Note de lectură în informatică (volumul 173), Berlin: Springer, 145–156.
  • –––, 1985, „Trei abordări ale structurii de tip. Bazele matematice ale dezvoltării de software”, în Note de lectură în informatică (volumul 185), Berlin: Springer, 97–138.
  • Schiemer, G. și Reck, EH, 2013, „Logica în anii 1930: Teoria tipului și teoria modelului”, Buletinul logicii simbolice, 19 (4): 433–472.
  • Schütte, K., 1960, Beweistheorie, Berlin: Springer-Verlag.
  • Scott, D., 1993 „O alternativă de tip teoretic la ISWIM, CUCH, OWHY”, Teoretica Calculatoare, 121: 411–440.
  • Skolem, T., 1970, Selected works in logic, Jens Erik Fenstad (ed.), Oslo: Universitetsforlaget.
  • Tait, WW, 1967, „Interpretări intenționate ale funcționalelor de tip finit”, Journal of Symbolic Logic, 32 (2): 198–212.
  • Takeuti, G., 1955 „Pe conjectura fundamentală a GLC: I”, Journal of the Mathematical Society of Japan, 7: 249-275.
  • –––, 1967, „Dovadă de consecvență a subsistemelor de analiză clasică”, Analele Matematicii (Seria a doua), 86 (2): 299–348.
  • Tarski, A., 1931, „Sur les ensembles definesables of nombres reels I”, Fundamenta Mathematicae, 17: 210–239.
  • Urquhart, A., 2003, „Theory of Types”, în The Cambridge Companion to Bertrand Russell, Nicholas Griffin (ed.), Cambridge: Cambridge University Press.
  • Voevodsky, V., 2015, „O bibliotecă experimentală de matematică formalizată bazată pe fundamente univalente”, Structuri matematice în informatică, 25: 1278–1294, disponibilă online.
  • Wiener, N., 1914, „O simplificare a logicii relațiilor”, Proceedings of the Cambridge Philosophical Society, 17: 387-390.
  • Weyl, H., 1946, „Matematică și logică”, American Mathematical Monthly, 53: 2–13.
  • Zermelo, E., 1908, „Untersuchungen über die Grundlagen der Mengenlehre I”, Mathematische Annalen, 65: 261–281.

Instrumente academice

pictograma omului sep
pictograma omului sep
Cum se citează această intrare.
pictograma omului sep
pictograma omului sep
Previzualizați versiunea PDF a acestei intrări la Societatea Prietenii SEP.
pictograma inpho
pictograma inpho
Căutați acest subiect de intrare la Proiectul Ontologia Filozofiei pe Internet (InPhO).
pictograma documente phil
pictograma documente phil
Bibliografie îmbunătățită pentru această intrare la PhilPapers, cu link-uri către baza de date a acesteia.

Alte resurse de internet

  • Kubota, K., 2018, „Fundații de matematică. Genealogie și imagine de ansamblu”, manuscris, schiță din 27 martie 2018.
  • [HoTT 2013], Teoria tipului de homotopie: Fundații univalente de matematică, Institutul de studiu avansat.

Recomandat: