Intuicionistinė Tipo Teorija

Turinys:

Intuicionistinė Tipo Teorija
Intuicionistinė Tipo Teorija
Anonim

Įėjimas Navigacija

  • Įstojimo turinys
  • Bibliografija
  • Akademinės priemonės
  • Draugai PDF peržiūra
  • Informacija apie autorius ir citata
  • Atgal į viršų

Intuicionistinė tipo teorija

Pirmą kartą paskelbta 2016 m. Vasario 12 d., Penktadienis; esminė peržiūra Pirmadienis, 2020 m. birželio 8 d

Intuicionistinė tipo teorija (taip pat konstruktyviojo tipo teorija arba Martino-Löfo tipo teorija) yra formali loginė sistema ir filosofinis pagrindas konstruktyviai matematikai. Tai yra visos apimties sistema, kuria siekiama atlikti panašų vaidmenį konstruktyvioje matematikoje, kaip ir Zermelo-Fraenkelio rinkinio teorija, atliekant klasikinę matematiką. Jis grindžiamas teiginių kaip tipų principu ir paaiškina Brouwerio-Heytingo-Kolmogorovo intuicionistinės logikos interpretaciją. Tai išplečia šį aiškinimą ir pateikia bendresnį intuicionizmo tipo teorijos nustatymą ir taip pateikia bendrą sampratą ne tik apie tai, kas yra konstruktyvus įrodymas, bet ir apie tai, kas yra konstruktyvus matematinis objektas. Pagrindinė mintis yra ta, kad matematinės sąvokos, tokios kaip elementai, rinkiniai ir funkcijos, yra paaiškinamos tokiomis sąvokomis kaip programavimas, pavyzdžiui, duomenų struktūros,duomenų tipai ir programos. Šiame straipsnyje aprašoma formalioji intuicionizmo tipo teorijos sistema ir jos semantiniai pagrindai.

Šiame įraše pirmiausia apžvelgiame svarbiausius intuicionizmo tipo teorijos aspektus - tam tikrą „išplėstinę santrauką“. Jis skirtas skaitytojui, jau šiek tiek susipažinusiam su teorija. Kita vertus, 2 skyrius skirtas skaitytojui, naujoviškam intuicionizmo tipo teorijoje, tačiau žinančiam tradicinę logiką, įskaitant teiginio ir predikato logiką, aritmetiką ir aibės teoriją. Čia neoficialiai pristatome keletą aspektų, kurie išskiria intuicionizmo tipo teoriją iš šių tradicinių teorijų. 3 skyriuje pateikiame pagrindinę teorijos versiją, artimą pirmajai Martin-Löf paskelbtai 1972 m. Versijai. Skaitytojas, kurį suintrigavo 2 skyriaus neformalumas, dabar išsamiai pamatys, kaip ši teorija kuriama. Tada 4 skyriuje pateikiama keletas svarbių pagrindinės teorijos pratęsimų. Visų pirma,Tai pabrėžia pagrindinį indukcinių (ir induktyviai-rekursinių) apibrėžimų vaidmenį. 5 skyriuje pristatomos pagrindinės filosofinės idėjos, įskaitant prasmės teoriją, kurią sukūrė Martin-Löf. Nors 5 skyriuje kalbama apie filosofiją ir pagrindus, 6 skyriuje apžvelgiami teoriniai matematiniai modeliai. Galiausiai 7 skyriuje aprašome keletą svarbių pagrindinės Martin-Löf „intencionalinės“teorijos variantų, aprašytų 3 ir 4 skyriuose.aprašome keletą svarbių pagrindinės Martin-Löf „intencionalinės“teorijos variacijų, aprašytų 3 ir 4 skyriuose.aprašome keletą svarbių pagrindinės Martin-Löf „intencionalinės“teorijos variacijų, aprašytų 3 ir 4 skyriuose.

  • 1. Apžvalga
  • 2. Pasiūlymai kaip tipai

    • 2.1 Intuicionizmo tipo teorija: naujas būdas pažvelgti į logiką?
    • 2.2 Curry-Howardo korespondencija
    • 2.3 Įrodomų objektų rinkiniai
    • 2.4 Priklausomi tipai
    • 2.5 Pasiūlymai kaip tipai intuicijos tipo teorijoje
  • 3. Pagrindinė intuicinio tipo teorija

    • 3.1 Teismo sprendimai
    • 3.2 Teismo sprendimų formos
    • 3.3 Išvadų taisyklės
    • 3.4 Intuicionistinė numatomoji logika
    • 3.5 Natūralūs skaičiai
    • 3.6 Mažų tipų visata
    • 3.7 Propozicinė tapatybė
    • 3.8 Pasirinkimo aksioma yra teorema
  • 4. Pratęsimai

    • 4.1 Loginė sistema
    • 4.2 Bendrasis asmens tapatybės tipas
    • 4.3 Gerai pamatyti medžiai
    • 4.4 Iteraciniai rinkiniai ir CZF
    • 4.5. Induktyviosios apibrėžtys
    • 4.6 Indukciniai-rekursiniai apibrėžimai
  • 5. Reikšmių paaiškinimai

    • 5.1 Skaičiavimas į kanoninę formą
    • 5.2 Kategoriškų sprendimų reikšmė
    • 5.3 Hipotetinių sprendimų reikšmė
  • 6. Matematiniai modeliai

    • 6.1 Kategoriniai modeliai
    • 6.2 Nustatytasis teorinis modelis
    • 6.3 Realizavimo modeliai
    • 6.4 Įprastų formų pavyzdys ir tipo tikrinimas
  • 7. Teorijos variantai

    • 7.1 Išplėtimo tipo teorija
    • 7.2. Universalūs pagrindai ir homotopijos tipo teorija
    • 7.3 Dalinė ir nestandartinė tipo teorija
    • 7.4 Neįtariama tipo teorija
    • 7.5 Įrodomi padėjėjai
  • Bibliografija
  • Akademinės priemonės
  • Kiti interneto šaltiniai
  • Susiję įrašai

1. Apžvalga

Mes pradedame nuo žvilgsnio iš paukščio skrydžio į kai kuriuos svarbius intuicionizmo tipo teorijos aspektus. Skaitytojai, kurie nepažįsta teorijos, gali praleisti ją praleisti per pirmąjį svarstymą.

Intuicionistinės tipo teorijos ištakos yra Brouwerio intuicionizmas ir Russello tipo teorija. Kaip ir Bažnyčios klasikinė paprasta tipų teorija, ji remiasi lambda skaičiavimu su tipais, tačiau nuo jo skiriasi tuo, kad remiasi teiginių kaip tipų principu, kurį Curry (1958) atrado teiginio logikai ir pratęstas logikai pagrįsti. Howardas (1980 m.) Ir de Bruijnas (1970 m.). Šis išplėtimas tapo įmanomas įvedant indeksuotas tipų (priklausomų tipų) šeimas, vaizduojančias predikato logikos predikatus. Tokiu būdu visi loginiai jungiamieji elementai ir kiekybiniai rodikliai gali būti interpretuojami pagal tipų sudarytojus. Prie intuicionistinės tipo teorijos pridedami kiti tipai, tokie kaip natūraliųjų skaičių tipas, mažų tipų tipas (visata) ir gerai pagrįstų medžių rūšis. Gautoje teorijoje yra intuicionistinė skaičių teorija (Heitingo aritmetinė) ir daug daugiau.

Teorija suformuluota natūraliu išskaičiavimu, kur kiekvienam tipui būdingos taisyklės yra klasifikuojamos kaip formavimo, įvedimo, pašalinimo ir lygybės taisyklės. Šios taisyklės parodo tam tikrą įvedimo ir pašalinimo taisyklių, pateiktų po Gentzeno ir Prawitzo natūralaus išskaičiavimo traktavimo, simetriją, kaip paaiškinta įraše apie įrodymų teoretinę semantiką.

Teiginių elementai, aiškinant juos kaip tipus, vadinami įrodymais. Kai įrodymai pridedami prie natūralių dedukcinių skaičiavimų, tai tampa tipiškais lambda skaičiavimais su priklausomais tipais, kurie išplečia originalų Bažnyčios įvestą lambda skaičiavimą. Lygybės taisyklės yra šio skaičiavimo sąlygų skaičiavimo taisyklės. Kiekviena teorijoje apibrėžta funkcija yra visavertė ir apskaičiuojama. Taigi intuicijos tipo teorija yra tipizuota funkcinė programavimo kalba, turinti neįprastą savybę, kurią nutraukia visos programos.

Intuicionistinio tipo teorija yra ne tik formali loginė sistema, bet ir pateikiama išsami intuityvizmo filosofinė sistema. Tai yra išaiškinta kalba, kur esminis vaidmuo tenka atskyrimui tarp sprendimo demonstravimo ir teiginio įrodymo (Sundholm 2012). Sistema paaiškina Brouwerio-Heytingo-Kolmogorovo intuicionistinės logikos interpretaciją ir išplečia ją į bendrą intuicionizmo tipo teorijos nustatymą. Tai daro bendrą koncepciją ne tik apie konstruktyvų įrodymą, bet ir apie tai, kas yra konstruktyvus matematinis objektas. Intuicionistinės tipo teorijos sprendimų prasmė aiškinama kanoninių tipų ir terminų formų skaičiavimais. Šie neformalūs,intuityvūs prasmių paaiškinimai yra „prieš matematiką“ir turėtų būti kontrastuojami su oficialiais matematikos modeliais, sukurtais standartinėje matematikos sistemoje, pavyzdžiui, aibės teorijoje.

Ši prasmės teorija taip pat pagrindžia įvairius indukcinius, rekursinius ir indukcinius-rekursinius apibrėžimus. Nors teoriškai tvirtas sąvokas galima pateisinti, pavyzdžiui, kai kurių didelių kardinolų analogais, sistema laikoma vyraujančia. Neįmanomi tokio tipo apibrėžimai, kokie randami aukštesnės eilės logikoje, intuicionistinėje rinkinio teorijoje ir toposo teorijoje, nėra teorijos dalis. Taip pat nėra Markovo principas, taigi teorija skiriasi nuo rusų konstruktyvizmo.

Alternatyvi formali loginė sistema prediktyviai konstruktyviai matematikai yra Myhill ir Aczelio konstruktyvi Zermelo-Fraenkel aibės teorija (CZF). Ši teorija, pagrįsta intuicionistine pirmosios eilės predikatine logika ir susilpninančia kai kurias klasikinės Zermelo-Fraenkel rinkinio teorijos aksiomas, turi natūralų intuicionistinio tipo teorijos aiškinimą. Taigi Martin-Löf prasmių paaiškinimai netiesiogiai sudaro CZF pagrindą.

Intuicionistinio tipo teorijos variantai yra keletas plačiai naudojamų įrodymų padėjėjų, įskaitant „NuPRL“, „Coq“ir „Agda“. Šie įrodymų padėjėjai yra kompiuterinės sistemos, kurios buvo naudojamos formuojant didelius ir sudėtingus matematinių teoremų įrodymus, tokius kaip Keturių spalvų teorema grafiko teorijoje ir Feito-Thompsono teorema baigtinių grupių teorijoje. Jie taip pat buvo naudojami įrodyti tikroviško C kompiliatoriaus (Leroy 2009) ir kitos kompiuterio programinės įrangos teisingumą.

Filosofiškai ir praktiškai intuicionizmo tipo teorija yra pamatinė sistema, kurioje konstruktyvi matematika ir kompiuterinis programavimas giliąja prasme yra tas pats. Šis punktas buvo pabrėžtas (Gonthier 2008) dokumente, kuriame jis aprašo savo keturių spalvų teoremos įrodymą:

Šiam įrodymui pasisekė, kad beveik kiekviena matematinė koncepcija buvo paversta duomenų struktūra arba programa „Coq“sistemoje, tokiu būdu paverčiant visą įmonę programos patikrinimo programa.

2. Pasiūlymai kaip tipai

2.1 Intuicionizmo tipo teorija: naujas būdas pažvelgti į logiką?

Intuicionistinė tipo teorija siūlo naują logikos analizės būdą, daugiausia pateikdama aiškių įrodymų objektus. Tai suteikia tiesioginį skaičiavimo logikos aiškinimą, nes yra įrodymų objektų skaičiavimo taisyklės. Kalbant apie išraiškingą galią, intuicionizmo tipo teorija gali būti laikoma pirmosios eilės logikos pratęsimu, panašiai kaip aukštesnės eilės logika, bet prediktyvi.

2.1.1 A tipo teorija

Raselis sukūrė tipo teoriją, atsakydamas į naivios teorijos paradokso atradimą. Jo supaprastinto tipo teorijoje matematiniai objektai klasifikuojami pagal jų tipus: teiginių tipus, objektų tipus, objektų savybių tipus ir kt. Kai Bažnyčia sukūrė savo paprastą tipų teoriją remdamasi spausdinta jo versija. lambda calculus jis pridėjo taisyklę, kad tarp bet kurių dviejų teorijos tipų yra tam tikros rūšies funkcijos. Intuicionistinė tipo teorija dar labiau išplečia paprasčiausiai įvestą lambda skaičiavimą priklausomais tipais, tai yra, indeksuotomis tipų šeimomis. Pavyzdys yra (n) tipų šeima, indeksuojama (n).

Tipai ilgą laiką buvo plačiai naudojami programavime. Ankstyvosios aukšto lygio programavimo kalbos įvedė sveikųjų skaičių ir slankiojo kablelio skaičių tipus. Šiuolaikinės programavimo kalbos dažnai turi turtingo tipo sistemas su daugybe konstrukcijų naujiems tipams formuoti. Intuicionistinė tipo teorija yra funkcinė programavimo kalba, kurioje tipo sistema yra tokia turtinga, kad praktiškai bet kokia įsivaizduojama programos savybė gali būti išreikšta tipu. Taigi tipai gali būti naudojami kaip programos užduoties specifikacijos.

2.1.2 Intuityvi logika su įrodymais

Brouwerio logikos analizė atvedė jį į intuicionistinę logiką, atmetančią atskirto vidurio ir dvigubo neigimo dėsnius. Šie dėsniai negalioja intuicionizmo tipo teorijoje. Taigi jame nėra klasikinės (Peano) aritmetinės, o tik intuityvios (Heyting) aritmetikos. (Kitas dalykas, kad Peano aritmetiką Heytingo aritmetikoje galima interpretuoti dvigubo neigimo aiškinimu, žr. Intuityvinės logikos įrašą.)

Apsvarstykite intuityvinės aritmetikos teoremą, tokią kaip padalijimo teorema

(Forall m, n. m> 0 / supset / egzistuoja q, r. mq + r = n / pleištas m> r)

Formalus šios teoremos įrodymas (įprasta prasme) yra formulių seka (arba medis), kur paskutinė (šaknies) formulė yra teorema, o kiekviena sekos formulė yra arba aksioma (lapas), arba taikant išvados taisyklę kai kurioms ankstesnėms (aukštesnėms) formulėms.

Kai dalijimosi teorema yra įrodyta intuityvistinėje tipo teorijoje, mes statome ne tik oficialų įrodymą įprasta prasme, bet ir konstrukciją (arba įrodymą-objektą) „(divi)“, liudijančią teoremos tiesą. Mes rašome

(divi: / forall m, n {:} N. \, m> 0 / supset / egzistuoja q, r {:} N. \, mq + r = n / pleišto m> r)

išreikšti, kad (divi) yra padalijimo teoremos įrodymo objektas, tai yra tipo elementas, atstovaujantis padalijimo teoremai. Kai teiginiai pateikiami kaip tipai, (forall) - kiekybinis rodiklis identifikuojamas su priklausomos funkcijos erdvės buvusiuoju (arba bendru Dekarto produktu) (Pi), (egzistuoja) - kiekybiniu rodikliu su priklausomomis poromis. tipo buvęs (arba bendroji atskyrimo suma) (Sigma), junginys (pleištas) su dekarto produktu (kartų), tapatybės santykis = su įrodomųjų objektų buvusiuoju veidu ((I)) tapatybių, ir didesnis nei santykis (>) su ankstesnio tipo ((GT)) įrodymų objektų, didesnių už teiginius. Taigi, naudodami „tipo žymėjimą“, rašome

(div: / Pi m, n {:} N. \, / GT (m, 0) dešinėn rodyklė / Sigma q, r {:} N. \, / I (N, mq + r, n) kartų / GT (m, r))

išreikšti, kad įrodymo objektas „(divi)“yra funkcija, žyminti du skaičius (m) ir (n), ir įrodymo objektas (p), liudijantis tai (m> 0) į keturženklį ((q, (r, (s, t)))), kur (q) yra koeficientas, o (r) yra likutis, gautas dalijant (n) iš (m). Trečiasis komponentas (s) yra įrodymo objektas, liudijantis, kad (mq + r = n), o ketvirtasis komponentas (t) yra įrodantis objektas, liudijantis (m> r).

Svarbiausia, kad (divi) yra ne tik funkcija klasikine prasme; tai taip pat funkcija intuicionistine prasme, tai yra, programa, kuri apskaičiuoja išėjimą ((q, (r, (s, t)))), kai duota (m), (n), (p) kaip įvestys. Ši programa yra terminas lambda skaičiavime su specialiomis konstantomis, tai yra, programa funkcine programavimo kalba.

2.1.3 Pirmos eilės predikatinės logikos pratęsimas

Intuicionistinė tipo teorija gali būti laikoma pirmosios eilės logikos pratęsimu, nes aukštesnės eilės logika yra pirmosios eilės logikos pratęsimas. Aukštesnės eilės logikoje randame keletą atskirų domenų, kuriuos galima suprasti kaip bet kuriuos mums patinkančius rinkinius. Jei paraše yra santykinių konstantų, tai galima suprasti kaip bet kokius ryšius tarp aibių, aiškinančių atskiras sritis. Be to, mes galime kiekybiškai įvertinti santykį, santykių santykį ir pan. Galime galvoti apie aukštesnės eilės logiką kaip pirmosios eilės logiką, turinčią būdą įvesti naujas kiekybinio įvertinimo sritis: if (S_1, / ldots, S_n) yra kiekybinio įvertinimo sritys, tada ((S_1, / ldots, S_n)) yra nauja kiekybinio įvertinimo sritis, susidedanti iš visų n-ary ryšių tarp domenų (S_1, / ldots, S_n). Aukštesnės eilės logika turi aiškų aibę teorinės interpretacijos, kai ((S_1, / ldotai, S_n)) aiškinamas kaip galios rinkinys (P (A_1 / kartus / cdots / kartų A_n)), kur (A_i). yra (S_i), skirto (i = 1, / ldots, n) aiškinimas. Tai yra aukštesnės eilės logika arba paprasta tipų teorija, kurią pristatė Ramsey, Church ir kiti.

Intuicionistinė tipo teorija gali būti vertinama panašiai, tik čia yra gausesnės kiekybinių sričių įvedimo galimybės, galima naudoti (Sigma, / Pi, +, / I) naujoms iš senų kurti. (3.1 skyrius; Martin-Löf, 1998 [1972]). Intuicionistinė tipo teorija taip pat turi aiškų aibės teorijos aiškinimą, kur (Sigma), (Pi) ir tt aiškinami kaip atitinkamos aibės teorinės konstrukcijos; žiūrėti žemiau. Prie intuicionistinio tipo teorijos galime pridėti ir neapibrėžtas atskiras sritis, kaip ir HOL. Jie aiškinami kaip rinkiniai kaip ir HOL. Dabar mes matome skirtumą nuo HOL: intuicionizmo tipo teorijoje galime įvesti neapibrėžtus šeimos simbolius. Galime pristatyti (T) kaip tipų šeimą atskirame domene (S):

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

Jei (S) aiškinamas kaip (A), (T) gali būti suprantamas kaip bet kuri rinkinių šeima, indeksuota (A). Kaip ne matematinį pavyzdį, dvejetainius meilės ryšius tarp atskirų žmonių srities žmonių galime pateikti taip. Pristatykite dvejetainę šeimos meilę per domeną Žmonės

[{ rm myli} (x, y); { rm tipas}; (x {:} { rm People}, y {:} { rm People}).)

Išaiškinimas gali būti bet kokia aibių šeima (B_ {x, y}) ((x {:} A), (y {:} A). Kaip tai apima standartinę santykio sampratą? Tarkime, kad turime dvejetainį ryšį (R) on (A) pažįstama aibės teorine prasme. Mes galime sudaryti dvejetainę šeimą, atitinkančią tai taip

[B_ {x, y} = / pradėti {atvejai} {0 } & / tekstas {jei} R (x, y) tekstas {sulaiko} / \ lakas nieko & / tekstas {if} R (x, y) tekstas {klaidingas.} pabaiga {atvejai})

Dabar akivaizdu, kad (B_ {x, y}) yra nereikšmingas tik tada, kai (R (x, y)). (Tiesai nurodyti galėjome pasirinkti bet kurį kitą elementą iš savo nustatytos teorinės visatos, išskyrus 0). Taigi iš bet kokių ryšių mes galime sukurti šeimą, kurios (x, y) tiesa yra lygi (B_ {x, y}) nebūdami tušti. Atminkite, kad šis aiškinimas nesureikšmina, koks yra (R (x, y)) įrodymas, tik kad jis yra. Prisiminkite, kad intuicionistinė tipo teorija teiginius interpretuoja kaip tipus, taigi (p {:} { rm myli} ({rm John}, {rm Mary})) reiškia, kad ({ rm myli} ({ rm Jonas}, {rm Mary})) yra tiesa.

Santykių, kaip šeimų, aiškinimas leidžia sekti įrodymus ar įrodymus, kurie yra (R (x, y)), bet mes galime pasirinkti ir to nepaisyti.

Montague semantikoje natūralios kalbos semantikai pateikti naudojamos aukštesnės eilės logika (ir pavyzdžiai, kaip aprašyta aukščiau). Ranta (1994) pristatė idėją vietoj to naudoti intuicionistinę tipo teoriją, kad būtų lengviau sugauti sakinio struktūrą pasitelkiant priklausomus tipus.

Kaip matematinis santykis (>) tarp natūraliųjų skaičių būtų aiškinamas intuityvistinėje tipo teorijoje? Pirmiausia mums reikia skaičių tipo (N). Mes iš principo galėtume įvesti neapibrėžtą individualų domeną (N) ir tada pridėti aksiomas, kaip ir pirmosios eilės logika, kai nustatome „Peano“aritmetikos aksiomų sistemą. Tačiau tai nesuteiktų mums pageidaujamo skaičiavimo aiškinimo. Taigi, kaip paaiškinta žemiau, pateikiame įvadines taisykles naujųjų natūraliųjų skaičių sudarymui iš (N) ir pašalinimo bei skaičiavimo taisykles funkcijoms apibrėžti (N) (rekursijos būdu). Standartinis užsakymo santykis (>) turėtų atitikti

(„box “{(x> y), jei yra (z {:} N), kad (y + z + 1 = x)}.)

Dešinė ranka intuityvistinėje tipo teorijoje pateikiama kaip (Sigma z {:} N. \, / I (N, y + z + 1, x)), ir mes tai laikome santykio apibrėžimu (>). ((+) yra apibrėžta rekursinėmis lygtimis; (I) yra tapatybės tipo konstrukcija). Dabar visas (>) savybes lemia minėtos (N) įvedimo ir pašalinimo bei skaičiavimo taisyklės.

2.1.4 Logika su keliomis sprendimo formomis

Intuicionistinės tipo teorijos tipų sistema yra labai išraiškinga. Todėl gero tipo formavimas nebėra paprastas analizės dalykas, jis turi būti įrodytas. Gerai suformuotas tipas yra viena iš intuicionistinės tipo teorijos sprendimų formų. Kitas termino tipiškumas tipo atžvilgiu. Be to, yra lygių galimybių sprendimų dėl tipų ir terminų. Tai yra dar vienas būdas, kuriuo intuicionistinė tipo teorija skiriasi nuo įprastos pirmosios eilės logikos, nes joje pagrindinis dėmesys skiriamas vieninteliam teiginiui, išreiškiančiam teiginio tiesą.

2.1.5 Semantika

Nors standartinis pirmojo laipsnio logikos pateikimas vadovautųsi Tarskiu apibrėžiant modelio sąvoką, intuityvistinė tipo teorija seka Brouwerian prasmės teorijos tradiciją, kurią toliau plėtojo Heytingas ir Kolmogorovas, vadinamąjį BHK logikos aiškinimą. Svarbiausia yra tai, kad implikacijos įrodymas (A / supset B) yra metodas, kuris (A) įrodymą paverčia (B) įrodymu. Intuicionistinėje tipo teorijoje šį metodą oficialiai apibūdina programa (f {:} A / supset B) arba (f {:} A / dešinė rodyklė B): implikacijos įrodymų tipas (A / supset B) yra funkcijų rūšis, kurios priskiria (A) įrodymus prie (B) įrodymų.

Be to, kadangi „Tarski“semantika paprastai pateikiama meta-matematiškai ir ji remiasi rinkinio teorija, Martyno-Löfo intuicionistinio tipo teorijos prasmės teorija turėtų būti suprantama tiesiogiai ir „prieš matematiką“, tai yra, nemanant, kad tokia metakalba kaip rinkinio teorija..

2.1.6 Funkcinė programavimo kalba

Skaitytojai, turintys lambda skaičiavimo pagrindą ir funkcinį programavimą, gali gauti alternatyvų pirmąjį intuicionistinio tipo teorijos derinimą, galvodami apie tai kaip įvestą funkcinio programavimo kalbą Haskell stiliaus ar vienos iš ML tarmių srityje. Tačiau ji skiriasi nuo šių dviejų esminių aspektų: (i) turi priklausomus tipus (žr. Toliau) ir (ii) visos spausdinamos programos baigiamos. (Atkreipkite dėmesį, kad intuicionistinė tipo teorija turėjo įtakos naujausiems Haskell plėtiniams su apibendrintomis algebrinėmis duomenų rūšimis, kurios kartais gali atlikti panašų vaidmenį kaip induktyviai apibrėžti priklausomi tipai.)

2.2 Curry-Howardo korespondencija

Kaip jau minėta, principas, kad

teiginys yra jo įrodymų rūšis.

yra esminė intuicionizmo tipo teorijai. Šis principas dar žinomas kaip Curry-Howard susirašinėjimas ar netgi Curry-Howard izomorfizmas. Curry atrado implikacijos intuityvinės logikos fragmentą ir paprasčiausiai įvestą lambda-calculus atitiktį. Howardas išplėtė šį susirašinėjimą iki pirmos eilės predikatinės logikos. Intuityvistinėje tipo teorijoje šis atitikimas tampa teiginio ir tipų identifikavimu, kuris buvo išplėstas, kad apimtų aukštesniųjų tipų ir daugiau kiekybinį vertinimą.

2.3 Įrodomų objektų rinkiniai

Taigi, kokie yra šie įrodymai? Jie neturėtų būti laikomi loginiais dariniais, o kaip tam tikrais (struktūrizuotais) simboliniais įrodymais, kad kažkas yra tiesa. Kitas tokių įrodymų terminas yra „tiesos formuotojas“.

Patartina, kad šioje korespondencijoje tipai būtų pakeisti paprastais rinkiniais, kaip šiek tiek grubus pirmasis derinimas. Apibrėžkite aibę (E_ {m, n}), atsižvelgiant į (m, n / į {{ mathbb N}}):

(E_ {m, n} = / kairė { pradėti {masyvas} {ll} {0 } & / „mbox“{if (m = n)} / \ nieko nedaryti & / mbox {if (m / ne n).} pabaiga {masyvas} dešinė.)

Tada (E_ {m, n}) yra beprasmis, kai (m = n). Rinkinys (E_ {m, n}) atitinka teiginį (m = n), o skaičius (0) yra įrodymo objektas (tiesos formuotojas), gyvenantis rinkiniuose (E_ {m, m}).

Apsvarstykite teiginį, kad (m) yra lyginis skaičius, išreikštas formule (egzistuoja n {{ mathbb N}}. M = 2n). Mes galime sukurti šią formulę atitinkančių įrodymų objektų rinkinį, naudodami bendrąją aibės-teorijos sumos operaciją. Tarkime, kad (A_n) ((n {{ mathbb N}})) yra aibių šeima. Tuomet jos nesusiejamą sumą suteikia porų rinkinys

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

Jei šią konstrukciją pritaikysime šeimai (A_n = / E_ {m, 2n}), pamatysime, kad ((Sigma n {{ mathbb N}}) E_ {m, 2n}) yra nestokojantis, kai yra (n {{ mathbb N}}) su (m = 2n). Panaudodami bendrą rinkinio teorinę produkto operaciją ((Pi n {{ mathbb N}}) A_n) panašiai galime gauti aibę, atitinkančią visuotinai kiekybinį teiginį.

2.4 Priklausomi tipai

Intuityvistinėje tipo teorijoje yra primityviųjų tipų formuotojai (Sigma) ir (Pi) bendroms sumoms ir produktams bei (I) tapatybės tipams, analogiški aukščiau aprašytoms aibės teorinių konstrukcijų. Tapatybės tipas (I (N, m, n)), atitinkantis aibę (E_ {m, n}) yra priklausomo tipo pavyzdys, nes jis priklauso nuo (m) ir (n). Ji taip pat vadinama indeksuota tipų šeima, nes tai yra tipų, indeksuotų (m) ir (n) tipų šeima. Panašiai mes galime suformuoti tokios rūšies šeimos bendrąją atskyrimo sumą (Sigma x {:} A. \, B) ir bendrąjį kartezinį produktą (Pi x {:} A. \, B). (B) indeksuotas (x {:} A), atitinkantis aukščiau nustatytą teorinę sumą ir produkto operacijas.

Priklausomus tipus taip pat galima apibrėžti primityvia rekursija. Pavyzdys yra (n) - elementų (A ^ n) tipo elementai, kurių tipas (A) ir indeksuojami (n {:} N) elementais, apibrėžtais lygtimis.

(pradėti {lygiuoti *} A ^ 0 & = 1 \\ A ^ {n + 1} & = A / kartus A ^ n / pabaiga {lygiuoti *})

kur (1) yra vieno elemento tipas ir (times) žymi dviejų tipų kartezinį produktą. Atkreipiame dėmesį, kad priklausomi tipai įveda skaičiavimą pagal tipus: aukščiau apibrėžtos taisyklės yra skaičiavimo taisyklės. Pavyzdžiui, skaičiavimo (A ^ 3) rezultatas yra (A / kartų (A / kartų (A / kartus 1))).

2.5 Pasiūlymai kaip tipai intuicijos tipo teorijoje

Jei teiginiai yra tipai, predikatai tampa priklausomais tipais. Pavyzdžiui, predikatas (mathrm {Prime} (x)) tampa įrodymo, kad (x) yra svarbiausias, tipu. Šis tipas priklauso nuo (x). Panašiai, (x <y) yra įrodymų rūšis, kad (x) yra mažesnis nei (y).

Remiantis Curry-Howardo teiginių, kaip tipų, aiškinimu, loginės konstantos aiškinamos kaip tipo sudarytojai:

(pradėti {lygiuoti *} bot & = / varnothing \\ / top & = 1 \\ A / vee B & = A + B \\ A / pleištas B & = A / kartus B \\ A / supset B & = A dešinė rodyklė B \\ / egzistuoja x {:} A. \, B & = / Sigma x {:} A. \, B \\ / forall x {:} A. \, B & = / Pi x {:} A. \, B / pabaiga {lygiuoti *})

kur (Sigma x {:} A. \, B) yra (A) - indeksuotų tipų šeimos (B) ir (Pi x {:} A.) atskirtoji suma. B) yra jos kartezinis produktas. Kanoniniai elementai (Sigma x {:} A. \, B) yra porų ((a, b)) porų, kad (a {:} A) ir (b {:} B [x: = a]) (tipas, gautas visus laisvus (x) įvykius (B) pakeitus (a)). (Pi x {:} A. \, B) elementai yra (apskaičiuojamos) funkcijos (f) tokios, kad (f \, a {:} B [x: = a]), kada ({:} A).

Pavyzdžiui, apsvarstykite pasiūlymą

(pradėti {lygtis} forall m {:} N. \, / egzistuoja n {:} N. \, m / lt n / pleištas / mathrm {Prime} (n) tag {1} etiketė {prop1} pabaiga {lygtis})

išreikšdamas, kad yra savavališkai dideli primai. Remiantis Curry-Howardo interpretacija, tai tampa tipu (Pi m {:} N. \, / Sigma n {:} N. \, m / lt n / times / mathrm {Prime} (n)). funkcijų, nurodančių skaičių (m) į trigubą ((n, (p, q))), kur (n) yra skaičius, (p) yra įrodymas, kad (m / lt n) ir (q) yra įrodymas, kad (n) yra svarbiausias. Tai yra įrodymas, kaip programų principas: konstruktyvus įrodymas, kad yra savavališkai dideli primai, tampa programa, kuri, pateikus bet kurį skaičių, sukuria didesnę premiją kartu su įrodymais, kad ji iš tikrųjų yra didesnė ir iš tikrųjų yra svarbiausia.

Atkreipkite dėmesį, kad įrodymas, kuris prieštarauja prielaidai, kad didžiausia pradinė reikšmė, nėra konstruktyvus, nes jis aiškiai nesuteikia galimybės apskaičiuoti dar didesnio pradinio lygio. Norėdami paversti šį įrodymą konstruktyviu, turime aiškiai parodyti, kaip sukonstruoti didesnįjį pagrindą. (Kadangi aukščiau pateiktas teiginys (ref {prop1}) yra (Pi ^ 0_2) - formulę, pavyzdžiui, galime panaudoti Friedmano A vertimą, kad tokį įrodymą klasikinėje aritmetikoje paverstų intuityvinės aritmetikos įrodymu, taigi, kad įrodymas intuicionistinėje tipo teorijoje.)

3. Pagrindinė intuicinio tipo teorija

Dabar pateikiame pagrindinę intuicionizmo tipo teorijos versiją, glaudžiai susijusią su pirmąja teorijos versija, kurią Martin-Löf pateikė 1972 m. (Martin-Löf 1998 [1972]). Be aukščiau išvardytų tipų formuotojų, reikalingų Curry-Howardo aiškinimui apie įvestos intuityvios predikato logikos interpretaciją, turime ir du tipus: natūraliųjų skaičių (N) tipą ir mažų tipų (U) tipą.

Gautą teoriją galima parodyti kaip intuicionistinę skaičių teoriją (HA) (heitinginę aritmetiką), aukštesniojo tipo primityvių rekursinių funkcijų Gödelio sistemą (T) ir teoriją (HA ^ / omega). aukštesniojo tipo Heytingo aritmetikos.

Ši pagrindinė intuicionizmo tipo teorija yra ne tik originali, bet galbūt ir minimali versija, parodanti esminius teorijos bruožus. Vėlesni pratęsimai su primityviais tapatybės tipais, pagrįstais medžių tipais, visatos hierarchijomis ir bendromis indukcinių ir indukcinių-rekursinių apibrėžimų sąvokomis padidino teorijos įrodomąją teorinę galią ir padarė ją patogesnę matematikos programavimui ir įforminimui. Pavyzdžiui, pridėjus gerai pagrįstų medžių, mes galime išaiškinti Aczelio (1978 [1977]) konstruktyviąją Zermelo-Fraenkel rinkinio teoriją (CZF). Tačiau lauksime iki kito skyriaus, kuriame bus aprašyti šie plėtiniai.

3.1 Teismo sprendimai

Martin-Löf (1996) pateikia bendrą logikos filosofiją, kurioje tradicinė sprendimo samprata yra išplėsta ir užima pagrindinę vietą. Teismo sprendimas yra ne tik teiginio patvirtinimas ar paneigimas, bet bendras žinojimo aktas. Motyvuodami matematiškai, mes priimame sprendimus apie matematinius objektus. Viena sprendimo formų yra teigti, kad kai kurie matematiniai teiginiai yra teisingi. Kita sprendimo forma yra teigti, kad kažkas yra matematinis objektas, pavyzdžiui, aibė. Loginės taisyklės pateikia metodus teisingų sprendimų sudarymui iš ankstesnių sprendimų. Pagal tokias taisykles gauti sprendimai gali būti pateikiami medžio pavidalu

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

arba nuoseklia forma

  • (1) (J_1 / quad / text {axiom})
  • (2) (J_2 / quad / tekstas {aksioma})
  • (3) (J_3 / quad / text {pagal taisyklę (r_1) iš (1) ir (2)})
  • (4) (J_4 / quad / text {axiom})
  • (5) (J_5 / quad / text {pagal taisyklę (r_2) iš (4)})
  • (6) (J_6 / quad / text {axiom})
  • (7) (J_7 / quad / text {pagal taisyklę (r_3) iš (5) ir (6)})
  • (8) (J_8 / quad / text {pagal taisyklę (r_4) iš (3) ir (7)})

Pastaroji forma yra įprasta matematiniuose argumentuose. Tokia seka arba medis, sudarytas iš loginių taisyklių iš aksiomų, yra teismo sprendimo išvestis arba įrodymas.

Pirmosios eilės pagrindimas gali būti pateiktas remiantis vienos rūšies sprendimu:

teiginys (B) yra tikras pagal hipotezę, kad visi teiginiai (A_1, / ldots, A_n) yra teisingi.

Šį hipotetinį sprendimą rašome kaip vadinamąjį „Gentzen“tęsinį

[A_1, / taškai, A_n { vdash} B.)

Atminkite, kad tai yra vienas teismo sprendimas, kurio nereikėtų painioti su sprendimo ({ vdash} B) išvedimu iš sprendimų ({ vdash} A_1, / ldots, { vdash} A_n). Kai (n = 0), tada kategoriškas sprendimas ({ vdash} B) teigia, kad (B) yra tiesa be jokių prielaidų. Su nuosekliaisiais žymėjimais tampa pažįstama jungtinio įvado taisyklė

(išeiti [(žemė I)] {A_1, / ldot, A_n { vdash} B / land C} {A_1, / ldots, A_n { vdash} B & A_1, / ldots, A_n { vdash} C}.)

3.2 Teismo sprendimų formos

Martin-Löf tipo teorija turi keturias pagrindines sprendimų formas ir yra žymiai sudėtingesnė sistema nei pirmosios eilės logika. Viena iš priežasčių yra tai, kad išvestinėse yra daugiau informacijos, nes yra teiginiai ir tipai. Kita priežastis yra ta, kad labiau įtraukiama sintaksė. Pvz., Gerai suformuotos formulės (tipai) turi būti generuojamos tuo pačiu metu kaip ir tikrosios formulės (apgyvendintos rūšys).

Keturios kategorinio sprendimo formos yra

  • (vdash A \; { rm tipas}), tai reiškia, kad (A) yra gerai suformuotas tipas,
  • (vdash a: {A}), tai reiškia, kad (a) tipas yra (A),
  • (vdash A = A '), tai reiškia, kad (A) ir (A') yra vienodi tipai,
  • (vdash a = a '{:} A), tai reiškia, kad (a) ir (a') yra vienodi (A) tipo elementai.

Apskritai, sprendimas yra hipotetinis, tai yra, jis daromas kontekste (Gama), tai yra (x_1 {:} A_1, / ldots, x_n {:} A_n) kintamųjų, kurie nuosprendyje gali atsirasti laisvai kartu su atitinkamomis jų rūšimis. Atminkite, kad tipai kontekste gali priklausyti nuo ankstesnių tipų kintamųjų. Pvz., (A_n) gali priklausyti nuo (x_1 {:} A_1, / ldots, x_ {n-1} {:} A_ {n-1}). Keturios hipotetinių sprendimų formos yra

  • (Gama / vdash A \; { rm tipas}), tai reiškia, kad (A) yra gerai suformuotas tipas kontekste (gama),
  • (Gamma / vdash a: {A}), reiškiantis, kad (a) kontekste yra (A) (Gamma),
  • (Gamma / vdash A = A '), tai reiškia, kad (A) ir (A') yra vienodi tipai kontekste (Gamma),
  • (Gamma / vdash a = a '{:} A), tai reiškia, kad (a) ir (a') yra vienodi (A) tipo elementai kontekste (Gamma).

Pagal pasiūlymą kaip tipų aiškinimas

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

gali būti suprantamas kaip sprendimas, kad (a) yra teiginio (A) objektas. Slopindami šį objektą gauname sprendimą, atitinkantį įprastą pirmosios eilės logiką (žr. Aukščiau):

(žyma {3} etiketė {sintetinė} vdash A \; {rm true}.)

3.1 pastaba. Martin-Löf (1994) tvirtina, kad Kanto analitinį sprendimą a priori ir sintetinį sprendimą a priori logikos srityje gali parodyti atitinkamai ([analitinis]) ir ([sintetinis]). Analitiniame sprendime ([analitiniame]) viskas, ko reikia, kad sprendimas būtų akivaizdus, yra aiškus. Sintetinės versijos ([sintetinės]) konstrukcija, kuri gali būti sudėtinga, turi būti pateikta (a), kad ji būtų akivaizdi. Šis analitiškumo ir sintetinumo supratimas turi stebėtiną padarinį, kad „visi loginiai dėsniai jų įprastoje formuluotėje yra sintetiniai“. Martin-Löf (1994: 95). Jo analizė taip pat suteikia:

„[…] analitinių sprendimų logika, tai yra dviejų analitinių formų sprendimų priėmimo logika, yra išsami ir leistina, tuo tarpu sintetinių sprendimų logika yra neišsami ir nenuginčijama, kaip parodė Gödel“. Martin-Löf (1994: 97).

Dviejų analitinių sprendimų ((vdash a:: A) ir (vdash a = b {:} A) priimtinumas priklauso nuo tipo teorijos metamatematinių savybių: stipraus normalizavimo ir priimtino tipo tikrinimo.

Kartais šios formos aiškiai laikomos teorijos sprendimais:

  • (Gama \; { rm kontekstas}), tai reiškia, kad (gama) yra gerai suformuotas kontekstas.
  • (Gama = / gama '), tai reiškia, kad (gama) ir (gama') yra vienodi kontekstai.

Žemiau mes sutrumpinsime sprendimą (Gamma / vdash A \; { rm type}) kaip (Gamma / vdash A) ir (Gamma \; { rm kontekstas}) kaip (Gama / vdash.)

3.3 Išvadų taisyklės

Nurodydami taisykles, raidę (Gama) naudosime kaip meta kintamąjį, besiskiriantį kontekstais, (A, B, / ldots) kaip meta kintamuosius, svyruojančius pagal tipus, ir (a, b, c, d, e, f, / ldots) kaip meta kintamieji, svyruojantys pagal terminus.

Pirmoji išvadų taisyklių grupė yra bendrosios taisyklės, įskaitant prielaidos, pakeitimo ir konteksto formavimo taisykles. Taip pat yra taisyklių, kurios išreiškia, kad lygybės yra lygiavertiškumo santykiai. Tokių taisyklių yra daugybė, ir mes parodome tik ypač svarbią lygybės taisyklę, kuri yra labai svarbi skaičiuojant tipus:

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

Likusios taisyklės yra būdingos tipų formuotojams. Jos klasifikuojamos kaip formavimo, įvedimo, pašalinimo ir lygybės taisyklės.

3.4 Intuicionistinė numatomoji logika

Mes pateikiame tik (Pi) taisykles. Yra analogiškos taisyklės ir kito tipo formuotojams, atitinkantiems įvestos predikato logikos logines konstantas.

Toliau (B [x: = a]) reiškia terminą, gautą pakeičiant terminą (a) kiekvienam laisvam kintamojo (x) pasireiškimui (B) (išvengiant kintamojo užfiksavimo).

(Pi) - formavimas. (frac { Gamma / vdash A / hspace {2em} Gama, x {:} A / vdash B} { Gamma / vdash / Pi x {:} A. B}) (Pi) -įvadas. (frac { gama, x {:} A / vdash b {:} B} { gama / vdash / lambda x. b {:} Pi x {:} A. B}) (Pi) - pašalinimas. (frac { Gama / vdash f {:} Pi x {:} AB / hspace {2em} Gama / vdash a {:} A} { Gamma / vdash f \, a {:} B [x: = a]}) (Pi) - lygybė. (frac { Gama, x {:} A / vdash b {:} B / hspace {2em} Gama / vdash a {:} A} { Gamma / vdash (lambda xb), a = b [x: = a] {:} B [x: = a]}) Tai yra (beta) konversijos taisyklė. Taip pat galime pridėti (eta) - konvertavimo taisyklę: (frac { Gamma / vdash f {:} Pi x {:} A. B} { Gamma / vdash / lambda x. f \, x = f {:} Pi x {:} A. B}.)

Be to, egzistuoja suderinamumo taisyklės, išreiškiančios, kad operacijos, įvestos formuojant, įvedant ir pašalinant taisykles, išsaugo lygybę. Pvz., (Pi) derėjimo taisyklė yra

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

3.5 Natūralūs skaičiai

Kaip ir „Peano“aritmetikoje, natūralieji skaičiai generuojami iš 0 ir iš eilės einančios operacijos (s). Šalinimo taisyklėje teigiama, kad tai yra vieninteliai įmanomi natūraliojo skaičiaus generavimo būdai.

Rašome (f (c) = / R (c, d, xy.e)) funkcijai, kuri apibrėžiama pirminiu natūralaus skaičiaus rekursija (c), naudojant bazinę raidę (d) ir žingsnį. funkcija (xy.e) (arba alternatyviai (lambda xy.e)), kuri nusako ankstesnio skaičiaus (y) reikšmę (x {:} N) prie (s (x)). Atminkite, kad (R) yra naujas kintamuosius rišantis operatorius: kintamieji (x) ir (y) tampa įpareigoti (e).

(N) - formavimas. (Gamma / vdash / N) (N) - įvadas. (Gamma / vdash 0 {:} N / hspace {2em} frac { Gamma / vdash a {:} N} { Gamma / vdash s (a) {:} N}) (N) - pašalinimas. (frac { Gama, x {:} N / vdash C / hspace {1em} Gama / vdash c {:} N / hspace {1em} Gama / vdash d {:} C [x: = 0] hspace {1em} gama, y {:} N, z {:} C [x: = y] vdash e {:} C [x: = s (y)]} { Gamma / vdash / R (c, d, yz.e) {:} C [x: = c]}) (N) - lygybė (tinkamose patalpose). (pradėti {lygiuoti *} R (0, d, yz.e) & = d {:} C [x: = 0] / \ R (s (a), d, yz.e) & = e [y: = a, z: = / R (a, d, yz.e)] {:} C [x: = s (a)] pabaiga {lygiuoti *})

(N) - pašalinimo taisyklė tuo pačiu metu išreiškia funkcijos tipą, apibrėžtą primityviu rekursija, o pagal Curry-Howardo interpretaciją - matematinės indukcijos taisyklę: mes įrodome natūralaus skaičiaus savybę (C). (x) įvesdami (x).

Gödelio sistema (T) iš esmės yra intuicionistinė tipo teorija, turinti tik tipo formuotojus (N) ir (A / dešinė rodyklė B) (funkcijų rūšis nuo (A) iki (B)., kuris yra ypatingas ((Pi x {:} A) B) atvejis, kai (B) nepriklauso nuo (x {:} A). Kadangi sistemoje (T) nėra priklausomų tipų, taisykles galima supaprastinti.

3.6 Mažų tipų visata

Pirmojoje Martin-Löf tipo teorijos versijoje (Martin-Löf 1971a) buvo aksioma, teigianti, kad egzistuoja visų rūšių tipas. Tai įrodė nenuoseklus Girard'as, kuris nustatė, kad šioje teorijoje gali būti užkoduotas Burali-Forti paradoksas.

Siekdamas įveikti šį patologinį netaktiškumą, tačiau vis tiek išlaikydamas savo ekspresyvumą, Martin-Löf 1972 m. Pristatė mažų tipų visatą (U), uždarytą pagal visus teorijos tipus, išskyrus tai, kad joje nėra savęs (Martin- Löf 1998 [1972]). Taisyklės:

(U) - formavimas. (Gama / vdash / U) (U) - įvadas. (Gamma / vdash / varnothing {:} U / hspace {3em} Gamma / vdash 1 {:} U) (frac { Gamma / vdash A {:} U / hspace {2em} Gama / vdash B {:} U} { Gama / vdash A + B {:} U} hspace {3em} frac { Gamma / vdash A {:} U / hspace {2em} Gama / vdash B {:} U} { gama / vdash A / kartų B {:} U}) (frac { gama / vdash A {:} U / hspace {2em} gama / vdash B {:} U} { gama / vdash A / dešinė rodyklė B {:} U}) (frac { gama / vdash A {:} U / hspace {2em} gama, x {:} A / vdash B {:} U} { Gamma / vdash / Sigma x {:} A., B {:} U} hspace {3em} frac { Gamma / vdash A {:} U / hspace {2em} gama, x {:} A / vdash B {:} U} { gama / vdash / Pi x {:} A. \, B {:} U}) (gama / vdash / N {:} U) (U) - pašalinimas. (frac { Gamma / vdash A {:} U} { Gamma / vdash A})

Kadangi (U) yra tipas, mes galime naudoti (N) - eliminaciją, kad apibrėžtume mažus tipus pagal primityvią rekursiją. Pavyzdžiui, jei (A: / U), (n) - elementų, esančių (A), tipą galime apibrėžti taip:

[A ^ n = / R (n, 1, xy. A / kartų y) {:} U)

Ši tipo teorinė visata (U) yra analogiška Grothendiecko visatai aibių teorijoje, kuri yra aibių aibė, uždaryta visais būdais, kaip aibės gali būti sudaromos pagal Zermelo-Fraenkel aibių teoriją. Grothendiecko visatos egzistavimas negali būti įrodytas remiantis įprastomis Zermelo-Fraenkel aibių teorijos aksiomomis, tačiau reikia naujos aksiomos.

Martin-Löf (1975) visata išplėsta į nesuskaičiuojamą visatų hierarchiją

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

Tokiu būdu kiekvienas tipas turi tipą, ne tik kiekvieną mažą tipą.

3.7 Propozicinė tapatybė

Pirmiau mes pristatėme teismo sprendimą už lygybę

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

Paprastai tai vadinama „apibrėžtine lygybe“, nes ją galima nuspręsti normalizavus terminus (a) ir (a ') ir patikrinant, ar normaliosios formos yra tapačios. Tačiau ši lygybė yra sprendimas, o ne teiginys (tipas), todėl mes negalime įrodyti tokių teismo lygiateisiškumų indukcija. Dėl šios priežasties turime įvesti teiginio tapatumo tipus. Pavyzdžiui, natūraliųjų skaičių (I (N, m, n)) tapatybės tipą galima apibrėžti pagal (U) vertinamą primityvią rekursiją. Tada mes galime išreikšti ir įrodyti Peano aksiomas. Be to, išplėstinę funkcijų lygtį galima apibrėžti

(I (N / dešinė rodyklė / N, f, f ') = / Pi x {:} N. / I (N, f \, x, f '\, x).)

3.8 Pasirinkimo aksioma yra teorema

Ši pasirinktos aksiomos forma yra tiesioginė intuicionistinių kiekybinių rodiklių BHK interpretacijos pasekmė ir lengvai įrodyta intuicionistinio tipo teorijoje:

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

Priežastis ta, kad (Pi x {:} A. / Sigma y {:} B. C) yra funkcijų rūšis, kurios elementus (x {:} A) susieja poromis ((y, z)) su (y {:} B) ir (z {:} C). Pasirinkimo funkcija (f) gaunama grąžinus pirmąjį šios poros komponentą (y {:} B).

Galbūt stebina, kad intuicionistinė tipo teorija tiesiogiai patvirtina pasirinktą aksiomą, nes ši aksioma dažnai laikoma problemiška konstruktyviu požiūriu. Galimas šios situacijos paaiškinimas yra tai, kad aukščiau išdėstyta yra tipų pasirinkta aksioma ir kad tipai apskritai nėra tinkami konstruktyvūs aibės klasikine prasme. Pvz., Realų skaičių kaip „Cauchy“seką galime pavaizduoti intuicionistinėje tipo teorijoje, tačiau realiųjų skaičių aibė yra ne „Cauchy“sekų tipas, bet „Cauchy“sekų tipas iki lygiaverčio. Apskritai, vyskupo konstruktyviosios matematikos aibė vaizduojama tipu (paprastai vadinamu „iš anksto nustatytu“) kartu su ekvivalentiškumo santykiu.

Jei (A) ir (B) turi lygiavertiškumo ryšius, žinoma, nėra jokios garantijos, kad pasirinkimo funkcija, aukščiau, (f), yra išplėstinė ta prasme, kad ji nusako lygiaverčius elementus lygiaverčiais elementais. Tai yra pasirinktos išplėstinės aksiomos nesėkmė, analizę žr. Martin-Löf (2009).

4. Pratęsimai

4.1 Loginė sistema

Tai, kas išdėstyta, užbaigia pagrindinės intuicionizmo tipo teorijos, panašios į tai, aprašymą (Martin-Löf 1998 [1972]).

1986 m. Martin-Löf pasiūlė pertvarkyti intuicionizmo tipo teoriją; ekspoziciją žr. Nordström, Peterson ir Smith (1990). Tikslas buvo pateikti kompaktiškesnę formuluotę, kur (lambda) ir (Pi) yra vienintelės kintamos įrišimo operacijos. Šiais laikais ji laikoma pagrindine teorijos versija. Tai taip pat yra „Agda“įrodymo asistento pagrindas. 1986 m. Teoriją sudaro dvi dalys:

  • tipų teorija (loginė sistema);
  • aibių (mažų tipų) teorija.

4.1 pastaba. Atminkite, kad žodis „rinkinys“loginėje struktūroje nesutampa su tuo, kaip jis vartojamas Vyskupo konstruktyvioje matematikoje. Siekiant išvengti šios painiavos, tipai ir ekvivalentiškumo santykiai intuityvinėje tipo teorijoje paprastai vadinami „setoidais“arba „pratęsiamaisiais rinkiniais“.

Loginę sistemą sudaro tik dviejų tipų formuotojai: (Pi x {:} A. B) (paprastai rašoma ((x {:} A) B) arba ((x {:} A) dešinė rodyklė B) loginiame pagrindų formulavime) ir (U) (paprastai vadinami (Set)). Taisyklės, skirtos (Pi x {:} A. B) (((x {:} A) dešinė rodyklė B) yra tokios pačios, kaip nurodytos aukščiau (įskaitant (eta) - konvertavimą). (U) ((Set)) taisyklės taip pat yra tos pačios, išskyrus tai, kad loginėje sistemoje numatytas uždarymas tik pagal (Pi) tipo formavimą.

Kiti mažo tipo formuotojai („komplektavimo formavimo įrenginiai“) pristatomi rinkinių teorijoje. Loginiame pagrindų formulavime kiekviena formavimo, įvedimo ir pašalinimo taisyklė gali būti išreikšta kaip naujos konstantos įvedimas. Pavyzdžiui, tampa natūraliųjų skaičių taisyklės

(pradėti {lygiuoti *} N &: / Nustatyti, \\ 0 &: / N, \\ / s &: / N / dešinė rodyklė / N, \\ / R &: (C {:} N / dešiniosios rodyklės / rinkinys) dešiniosios rodyklės C \, 0 / dešinės rodyklės ((x {:} N) dešiniosios rodyklės C \, x / dešiniosios rodyklės C \, (s \, x)) dešinės rodyklės (c {:} N) dešinė rodyklė C \, c. / pabaiga {lygiuoti *})

kur praleidome bendrą kontekstą (gama), nes šių konstantų tipai yra uždari. Atminkite, kad rekursijos operatorius (R), priešingai nei pirminėje formuluotėje, turi pirmąjį argumentą (C {:} N / dešinėn rodyklė / Set).

Be to, lygybės taisyklės gali būti išreikštos lygtimis

(pradėti {lygiuoti *} R \, C \, d \, e \, 0 & = d {:} C \, 0 \\ / R \, C \, d \, e \, (s \, a) & = e \, a \, (R \, C \, d \, e \, a) {:} C \, (s \, a) pabaiga {sulyginti *})

esant tinkamoms prielaidoms.

Tęsinyje pateiksime keletą tipo teorijos pratęsimų. Tačiau norėdami išlaikyti pateikimo formą vienodą, nenaudosime loginio tipo teorijos pateikimo, o naudosime tą pačią žymėjimą kaip 2 skyriuje.

4.2 Bendrasis asmens tapatybės tipas

Kaip minėjome aukščiau, natūraliųjų skaičių tapatumą galima apibrėžti primityvia rekursija. Tapatybės santykiai su kitomis rūšimis taip pat gali būti apibrėžti pagrindinėje intuicionizmo tipo teorijos versijoje, pateiktoje 2 skyriuje.

Tačiau Martin-Löf (1975) išplėtė intuicionistinę tipo teoriją, pritaikydamas visiems tipams vienodą primityvųjį tapatybės tipą, buvusį (I). (I) taisyklės išreiškia, kad tapatybės ryšį induktyviai sukuria refleksyvumo įrodymas, kanoninė konstanta, vadinama (r). (Atminkite, kad (r) įvadiniame įrodymo objektų pristatyme, 2.3 punkte, buvo užkoduotas skaičius 0. Tapatybės tipo pašalinimo taisyklė yra tapatybės eliminavimo apibendrinimas predikatinėje logikoje ir įveda eliminavimo konstantą (J). Čia mes parodome formuluotę dėl Paulino-Mohringo (1993), o ne pagal originalią Martino-Löfo (1975) formuluotę. Išvada yra tokia.

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

(I) - įvadas. (frac { Gama / vdash A / hspace {1em} Gama / vdash a {:} A} { Gama / vdash / r {:} I (A, a, a)})

(I) - pašalinimas.

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

(I) - lygybė (esant tinkamoms prielaidoms).

(pradėti {sulyginti *} J (r, d) & = d / baigti {sulyginti *})

Atminkite, kad jei (C) priklauso tik nuo (x: A), o ne nuo įrodymo (y: / I (A, a, x)) (o mes taip pat slopiname įrodymų objektus), (I) - pašalinimas Mes atkuriame tapatybės pašalinimo taisyklę predikatinėje logikoje.

Sudarę tipo teorijos modelį, kai tipai aiškinami kaip grupoidai (kategorijos, kur visos rodyklės yra izomorfizmai), Hofmannas ir Streicheris (1998) parodė, kad intuicionistinėje tipo teorijoje negalima įrodyti, kad visi (I (A, a, b) įrodymai.)) yra identiški. Tai gali atrodyti kaip teorijos neišsamumas ir Streicheris pasiūlė naują aksiomą (K), iš kurios darytina išvada, kad visi (I (A, a, b)) įrodymai yra identiški (r).

Tipas (I) dažnai vadinamas intenciniu tapatumo tipu, nes neatitinka funkcijos išplėtimo principo. Intuicionistinė tipo teorija su intencionalaus tapatumo tipu taip pat dažnai vadinama intencionaline intuicionistine tipo teorija, siekiant atskirti ją nuo išplėstinės intuicionistinės tipo teorijos, kuri bus aprašyta 7.1 skyriuje.

4.3 Gerai pamatyti medžiai

Gerai pagrįstų medžių rūšis (W x {:} A. B) buvo įvesta Martin-Löf 1982 m. (O griežtesnę formą pateikė Scott 1970 m.). (W x {:} A. B) elementai yra įvairaus ir savavališko išsišakojimo medžiai: kintantys, nes išsišakojimo tipas (B) indeksuotas (x {:} A), ir savavališki, nes (B) gali būti savavališkas. Tipas pateiktas apibendrintu indukciniu apibrėžimu, nes gerai pagrįsti medžiai gali be galo šakotis. Galime galvoti apie (W x {:} A. B) kaip laisvojo termino algebrą, kur kiekvienas (a {:} A) reiškia terminą konstruktorius (sup \, a) su (galbūt) begalinis) arity (B [x: = a]).

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

Mes praleidome (W) - panaikinimo ir (W) - lygybės taisykles.

Gerai pagrįstų medžių pridėjimas prie intuityvistinio tipo teorijos žymiai padidina įrodymo teorijos stiprumą (Setzer (1998)).

4.4 Iteraciniai rinkiniai ir CZF

Svarbus gerai pagrįstų medžių pritaikymas yra Aczelio (1978 m.) Konstruktyvaus Zermelo Fraenkelio rinkinio teorijos tipo teorinio modelio konstravimas. Šiuo tikslu jis apibrėžia iteracinių aibių tipą kaip

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

Tegul (A {:} U) yra mažos rūšies ir (x {:} A / vdash M) yra indeksuota iteracinių aibių šeima. Tuomet (sup (A, xM)) arba su daugiau siūlomu žymeniu ({M / mid x {:} A }) yra iteracinis rinkinys. Perfrazuojant: iteracinis rinkinys yra iteracinių rinkinių, indeksuotų mažu tipu, šeima.

Atminkite, kad iteracinis rinkinys yra alt="sep žmogaus piktograma" /> Kaip cituoti šį įrašą.

sep vyro ikona
sep vyro ikona

Peržiūrėkite šio įrašo PDF versiją „Friends of the SEP“draugijoje.

info piktograma
info piktograma

Ieškokite šios įrašo temos interneto filosofijos ontologijos projekte (InPhO).

„Phil Papers“piktograma
„Phil Papers“piktograma

Patobulinta šio įrašo „PhilPapers“bibliografija su nuorodomis į jo duomenų bazę.

Kiti interneto šaltiniai

  • Internetinė filosofijos enciklopedija: konstruktyvioji matematika
  • „Scholarpedia“: skaičiavimo tipo teorija
  • „nLab“: tipo teorija

Rekomenduojama: