Esmakordselt avaldatud ke 1. september 1999; sisuline redaktsioon teisipäev, 4. september 2018
Intuitionistlik loogika hõlmab loogiliste mõttekäikude üldpõhimõtteid, mille logistid on intuitsioonistlikust matemaatikast kokku võtnud, nagu on välja töötanud LEJ Brouwer oma artiklites [1907] ja [1908]. Kuna need põhimõtted kehtivad ka vene rekursiivse matemaatika ning E. Bishopi ja tema järgijate konstruktiivse analüüsi kohta, võib intuitiivset loogikat pidada konstruktiivse matemaatika loogiliseks aluseks. Ehkki intuitionistlik analüüs on vastuolus klassikalise analüüsiga, on intuitiivne Heytingi aritmeetika klassikalise Peano aritmeetika alamsüsteem. Siit järeldub, et intuitionistlik propositsiooniline loogika on klassikalise propositsiooniloogika õige alamsüsteem ja puhas intuitionistlik predikaatloogika on puhta klassikalise predikaatloogika õige alamsüsteem.
Filosoofiliselt erineb intuitionism loogikast sellega, et käsitleb loogikat pigem matemaatika kui matemaatika alusena; alates finitismvõimaldades konstruktiivseid põhjendusi loendamatute struktuuride kohta (nt ühetooniliste ribade induktsioon puul looduslike arvude potentsiaalselt lõpmatute jadade osas); ja platonismist, vaadates matemaatilisi objekte vaimsete konstruktsioonidena, millel pole iseseisvat ideaalset eksistentsi. Hilberti formalistlik programm, mille eesmärk oli õigustada klassikalist matemaatikat, taandades selle formaalseks süsteemiks, mille järjepidevus tuleks kehtestada finitistlike (seega konstruktiivsete) vahenditega, oli Brouweri areneva intuitsioonismi kõige võimsam kaasaegne rivaal. Intuitionism ja formalism ennustas oma 1912. aasta essees õigesti, et iga katse tõestada naturaalarvude täieliku induktsiooni järjepidevust tekitab nõiaringi.
Brouwer lükkas formaalsuse iseenesest tagasi, kuid tunnistas intuitiivselt korrektseid konstruktsioone, näiteks modus ponensi väljendavate loogiliste üldpõhimõtete sõnastamise potentsiaalset kasulikkust. Intuitsionistliku propositsioonilise ja predikaatloogika ning aritmeetika ametlikud süsteemid töötasid täielikult välja Heyting [1930], Gentzen [1935] ja Kleene [1952]. Gödel [1933] tõestas intuitiivsete ja klassikaliste teooriate võrdset järjepidevust. Beth [1956] ja Kripke [1965] pakkusid semantikat, mille suhtes intuitionistlik loogika on korrektne ja täielik, ehkki intuitionistliku predikaatloogika täielikkuse tõestusmaterjalid nõuavad klassikalist arutlust.
Intuitionistlikku loogikat saab lühidalt kirjeldada kui klassikalist loogikat, ilma et Aristoteli seadused oleksid välistatud:
) silt {LEM} A \ vee \ neg A)
või kahekordse eituse välistamise klassikaline seadus:
) silt {DNE} neg \ neg A \ paremnool A)
kuid vastuolu seadusega:
[(A \ parempoolne nool B) parempoolne nool ((A \ paremarvel \ neg B) parempoolne \ neg A))
ja ex falso sequitur quodlibet:
) neg A \ paremääris (A \ paremääris B).)
Brouwer [1908] leidis, et LEM oli abiks piiratud situatsioonidest, seejärel laiendati seda õigustamata lõpmatute kogude kohta käivatele avaldustele. Näiteks laske (x, y) ulatuda naturaalarvude (0, 1, 2, \ ldots) piirkonda ja (B (y)) lühendada ((primepred (y) oldand \ algsümbol (y + 2))), kus (algpäritud (y)) väljendab “(y) on algarv”. Siis (forall y (B (y) vee \ neg B (y))) kehtib nii intuitiivselt kui ka klassikaliselt, sest selleks, et teha kindlaks, kas naturaalarv on ülitähtis või mitte, peame kontrollima ainult seda, kas see on jagaja rangelt enda ja 1 vahel.
Aga kui (A (x)) lühendab (eksisteerib y (y \ gt x \ oldand B (y))), siis selleks, et kinnitada (forall x (A (x) vee \ neg A (x))) vajaksime intuitiivselt tõhusat (vrd kiriku-Turingi väitekirja) meetodit, et teha kindlaks, kas leidub suvalise loomuliku arvu (x) kaudu suuremat kaksikprimaati või mitte, ja siiani sellist meetodit ei teata. Ilmne pooltulemuslik meetod on algarvude paaride loetlemine, kasutades Eratosthenes'i sõela täpsustamist (loomulike arvude genereerimine ükshaaval ja iga arvu (y) väljaarvamine, mis ei vasta (B (y))) ja kui on kaks või kaks algarvu, mis on suuremad kui (x), siis leiab see meetod lõpuks esimese. Kuid (forall x A (x)) väljendab kaksikprimüütide oletust, mida pole veel tõestatud ega ümber lükatud,seega ei saa meie praeguses teaduses väita, et (forall x (A (x) vee \ neg A (x))) ega (forall x A (x) vee \ neg \ forall x A (x)).
Võib vaidlustada, et need näited sõltuvad tõsiasjast, et Kaksikprimiste oletus pole veel lahendatud. Mitmed Brouweri algsed “vastunäited” sõltusid probleemidest (näiteks Fermati viimane teoreem), mis on sellest ajast alates lahendatud. Kuid Brouweri jaoks oli üldine LEM samaväärne a priori eeldusega, et igal matemaatilisel probleemil on lahendus - eelduse, mille ta lükkas tagasi, ennetades Gödeli mittetäielikkuse teoreemi veerandsajandiks.
LEM-i tagasilükkamisel on kaugeleulatuvad tagajärjed. Ühest küljest,
Intuitsiooniliselt tõestab reductio ad absurdum ainult negatiivseid väiteid, kuna (neg \ neg A \ parempoolne nool A) üldiselt ei kehti. (Kui see juhtuks, järgiks LEM modeus ponensi intuitiivselt tõestatavast (neg \ neg (A \ vee \ neg A)).)
Intuitionistlikul loogikal puudub lõplik tõestabeli tõlgendus. Intuitsionistliku ja klassikalise loogika vahel on lõpmata palju erinevaid aksiomaatilisi süsteeme.
Mitte kõigil pakkumisvalemitel pole intuitiivselt ekvivalentset disjunktiivset või konjunktiivset normaalvormi, mis on üles ehitatud algvalemitest ja nende eitajatest kasutades ainult (vee) ja (oldand).
Kõigil predikaatvalemitel pole intuitiivselt samaväärset prenexi normaalvormi, mille ees on kõik kvantitaatorid.
Kui (forall x \ neg \ neg (A (x) vee \ neg A (x))) on intuitiivse predikaatloogika teoreem, siis (neg \ neg \ forall x (A (x) vee \ neg A (x))) ei ole; nii et (neg \ forall x (A (x) vee \ neg A (x))) on kooskõlas intuitsioonilise predikaatloogikaga.
Teiselt poolt,
Vormi (A \ vee B) suletud väite iga intuitiivset tõendit saab tõhusalt muuta (A) intuitiivseks tõendiks või (B) intuitiivseks tõestuseks ja samamoodi suletud eksistentsiaalsete avalduste jaoks.
Intuitionistlik propositsiooniline loogika on tegelikult otsustatav selles mõttes, et piiratud konstruktiivne protsess kehtib ühetaoliselt kõigi propositsiooniliste valemite kohta, esitades valemi intuitiivse tõestuse või näidates, et sellist tõestust ei saa eksisteerida.
Intuitsionistliku loogika negatiivne fragment (ilma (vee) või (olemas)) sisaldab klassikalise loogika usutavat tõlget ning sarnaselt intuitionistliku ja klassikalise aritmeetikaga.
Intuitionistlikku aritmeetikat saab järjekindlalt laiendada aksioomide abil, mis on vastuolus klassikalise aritmeetikaga, võimaldades rekursiivse matemaatika formaalset uurimist.
Brouweri vastuolulist intuitiivset analüüsi, mis on LEM-iga vastuolus, saab vormistada ja näidata järjepidevalt klassikaliselt ja intuitiivselt korrektse alateooria suhtes.
2. Intuitionistlik esimese astme ennustusloogika
Formaliseeritud intuitionistlikku loogikat motiveerib loomulikult Brouwer-Heyting-Kolmogorovi mitteametlik selgitus intuitionistlikust tõest, mis on välja toodud intuitiivismi käsitlevates sissejuhatustes matemaatikafilosoofias ja intuitionistliku loogika arendamises. Loogiliste toimingute konstruktiivne sõltumatus (oldand, \ vee, \ parempoolne nool, \ neg, \ forall, \ eksisteeriv) on vastuolus klassikalise olukorraga, kus nt (A \ vee B) võrdub (neg (neg A \ oldand \ neg B)) ja (eksisteerib xA (x)) võrdub (neg \ forall x \ neg A (x)). BHK vaatenurgast väidab vormi (A \ vee B) lause, et on ehitatud (A) või (B) tõestus;samal ajal kui (neg (neg A \ oldand \ neg B)) väidab, et on loodud algoritm, mis konverteeriks tõhusalt iga konstruktsiooni paari, mis tõestavad vastavalt (neg A) ja (neg B), teadaoleva vastuolu tõendiks.
Järgneb Hilberti stiilis formalism (mathbf {H – IQC}) Kleene'ilt [1952] (vrd Troelstra ja van Dalen [1988]) intuitiivse esimese astme predikaatloogika jaoks. (Mathbf {H – IQC}) keeles (L) on predikaattähed (P, Q (.), \ Ldots) kõigist arityedest ja üksikutest muutujatest (x, y, z, \ ldots) (koos alamtellikutega (1, 2, \ ldots)), samuti sümbolid (oldand, \ vee, \ paremnool, \ neg, \ forall, \ eksisteeriv) loogiliste ühenduste jaoks ja kvantifikaatorid ja sulud (,). (L) aatomi (või algvormi) valemid on sellised avaldised nagu (P, Q (x), R (x, y, x)) kus (P, Q ({.}), R ({.} {.} {.})) on vastavalt (0) - ary, (1) - ary ja (3) - ary predikaattähed; see tähendab, et iga tühiku predikaattähe täitmine üksikute muutujate sümbolitega on esmane valem.(L) (hästi vormistatud) valemid on induktiivselt määratletud järgmiselt.
Iga aatomi valem on valem.
Kui (A) ja (B) on valemid, siis on ka ((A \ oldand B), (A \ vee B), (A \ paremäär B)) ja (neg A).
Kui (A) on valem ja (x) on muutuja, siis (forall xA) ja (eksisteerib xA) on valemid.
Üldiselt kasutame hästi moodustatud valemite metamuutujatena (A, B, C) ja üksikute muutujate metamuutujatena (x, y, z). Rakenduste ennetamine (näiteks intuitiivse aritmeetika jaoks) kasutame terminite metamuutujatena (s, t); puhta predikaatloogika korral on terminid lihtsalt üksikud muutujad. Muutuja (x) esinemine valemis (A) on seotud juhul, kui see asub kvantitaatori (forall x) või (eksisteeriv x) piires, vastasel juhul vaba. Intuitionistlikult kui klassikaliselt lühendab ((A \ vasakpoolne B)) lühendatult (((A \ paremäär B) oldand (B \ parempoolne A))) ja sulud jäetakse välja, kui see ei tekita segadust.
On kolm järelduse reeglit:
Modus Ponens
Alates (A) ja (A \ parempoolne nool B), lõpetage (B).
(forall) - sissejuhatus saidilt \
(C \ parempoolne nool A (x)), kus (x) on muutuja, mis ei esine vabalt rakenduses (C), järeldus (C \ paremnool \ forall x A (x)).
(eksisteerib) - Elimineerimine
(A (x) parempoolne nool C), kus (x) on muutuja, mis ei esine vabalt asukohas (C), järeldus (eksisteerib x A (x) paremnool C).
Aksioomid on kõik järgmiste vormide valemid, kus kahes viimases skeemis on alamvorm (A (t)) tagajärg, kui mõiste (t) esinemine asendatakse iga (x) vaba esinemisega) jaotises (A (x)) ja ükski (t) -vaba muutuja ei muutu asendamisel (A (t)) -ga seotud.
) alustage {array} {l} A \ paremääris (B \ paremääris A) (A \ paremääris B) paremääris ((A \ paremääris (B \ paremääris C)) paremääris (A \ paremääris C)) \ parempoolne nool (B \ paremääris (A \ oldand B)) (A \ oldand B) parempoolne nool A \(A \ oldand B) parempoolne nool B \\ A \ parempoolne nool (A \ vee B) \ B \ parempoolne (A \ vee B) (A \ parempoolne C) parempoolne ((B \ parempoolne C) parempoolne ((A \ vee B) parempoolne C)) (A \ paremääris B) parempoolne ((A \ parempoolne \ neg B) parempoolne \ neg A) \ \ neg A \ parempoolne (A \ parempoolne B) \ \ forall xA (x) rightarrow A (t) \ A (t) paremnool \ eksisteerib xA (x) end {array})
Tõendiks on mis tahes lõplik valemitest koosnev jada, millest igaüks on ahena või selle tagajärjeks reegli (ühe või kahe) valemile eelneva valemi järeldamisreegel. Väidetavalt tõendab iga tõend oma viimast valemit, mida nimetatakse esimese järgu intuitiivse predikaatloogika teoreemiks või tõestatavaks valemiks. Valemi (E) tuletis oletuste kogumist (F) on valemi mis tahes jada, millest igaüks kuulub (F) või on aksioom või selle otsene tagajärg tuletatud reegli abil, jada eelnevate valemite järgi, nii et (E) on jada viimane valem. Kui selline tuletus on olemas, siis ütleme, et (E) on tuletatav (F) -st.
Intuitionistlik pakutav loogika (mathbf {H – IPC}) on (mathbf {H – IQC}) alamsüsteem, mis tuleneb siis, kui keel on piiratud valemitega, mis on loodud pakkumistähtedest (P, Q, R, \ ldots), kasutades pakkumisjuhendeid (oldand, \ vee, \ rightarrow) ja (neg), ja kasutatakse ainult pakkumispostulaate. Seega puuduvad ettepanekul põhinevas alamsüsteemis kaks viimast järelduse reeglit ja kaks viimast aksioomiskeemi.
Kui antud intuitiivse propositsioonilise või esimese järgu predikaatloogika aksioomiskeemide loendis on ex falso sequitur quodlibet'i väljendav seadus:
) neg A \ paremääris (A \ paremääris B))
asendatakse klassikalise topelt eituse kõrvaldamise seadusega DNE:
) neg \ neg A \ parempoolne nool A)
(või samamoodi, kui eituse sissejuhatuse intuitiivne seadus:
[(A \ parempoolne nool B) parempoolne nool ((A \ paremarvel \ neg B) parempoolne \ neg A))
asendatakse LEM), klassikalise juhendiloogika jaoks ametlik süsteem (mathbf {H – CPC}) või klassikalise predikaatloogika tulemuste jaoks (mathbf {H – CQC}). Kuna ex falso ja vastuoluseadus on klassikalised teoreemid, sisaldub intuitionistlik loogika klassikalises loogikas. Teatud mõttes sisaldub klassikaline loogika ka intuitsioonilises loogikas; vt allpool jaotist 4.1.
Oluline on märkida, et kuigi LEM ja DNE on (mathbf {H – IPC}) skeemidena võrdsed, tähendab implikatsioon
[(neg \ neg A \ parempoolne nool A) paremnool (A \ vee \ neg A))
ei ole (mathbf {H – IPC}) teoreemskeem. Intuitsioonilisel loogikal põhinevate teooriate (mathbf {T}) korral, kui (E) on (L (mathbf {T})) suvaline valem, siis määratluse järgi:
(E) on otsustatud rakenduses (mathbf {T}) ainult siis, kui (mathbf {T}) osutub (E \ vee \ neg E).
(E) on stabiilne (mathbf {T}) juhul ja ainult siis, kui (mathbf {T}) osutub (neg \ neg E \ parempoolne nool E).
(E) on testitav rakenduses (mathbf {T}) ainult siis, kui (mathbf {T}) osutub (neg E \ vee \ neg \ neg E).
Otsustatavus tähendab stabiilsust, kuid mitte vastupidi. Stabiilsuse ja kontrollitavuse koosmõju on samaväärne otsustatavusega. Brouwer ise tõestas, et “absurdsuse absurdsus võrdub absurdsusega” (Brouwer [1923C]), nii et vormi (neg A) iga valem on stabiilne; kuid (mathbf {H – IPC}) ja (mathbf {H – IQC}) algvalemites ja nende eitustes ei saa otsustada, nagu on näidatud jaotises 5.1.
2.2 Alternatiivsed formalismid ja deduktsioonide teoreem
Hilberti-tüüpi süsteem (mathbf {H – IQC}) on kasulik intuitionistliku loogika metamatmaatilistele uurimistele, kuid deduktiivsuste sunniviisiline lineariseerimine ja eelistamine reeglite aksioomidele muudab selle tuletatavuse seadmiseks ebamugavaks. Looduslik deduktsioonisüsteem (mathbf {N – IQC}) intuitiivse predikaatloogika tuletamiseks deduktiivsüsteemist (mathbf {D}), mis on esitatud käesoleva entsüklopeedia klassikalise loogika sissekande 3. osas, jättes välja identiteedi sümbol ja reeglid ning asendades kahekordse eituse kõrvaldamise klassikalise reegli (DNE) intuitiivse eituse kõrvaldamise reegliga, mis väljendab ex falso:
(INE) Kui (F) tähendab (A) ja (F) tähendab (neg A), siis (F) tähendab (B)
Võtmed, mis tõestavad, et (mathbf {H – IQC}) on samaväärne dokumendiga (mathbf {N – IQC}), on modus ponens ja selle vastupidine:
Dedutsiooniteoreem
Kui (B) on tuletatav (A) ja võib-olla muudest valemitest (F), kusjuures kõiki muutujaid, mis on vabad (A) -s, hoitakse tuletuses konstantsena (see tähendab, et teist või kolmas järeldamisreegel iga muutuja (x) korral, mis esinevad vaba kujul (A), välja arvatud juhul, kui eeldus (A) ei esine tuletuses enne kõnealust järeldust), siis (A \ paremnool B) on tuletatav (F) -st.
Seda põhimõttelist tulemust, mis väljendab jämedalt reeglit ((parempoolne I)) (mathbf {I}), saab tõestada (mathbf {H – IQC}) jaoks sissejuhatusega määratlusele tuletamine. Muud reeglid (mathbf {I}) kehtivad (mathbf {H – IQC}) jaoks põhimõtteliselt modus ponensi järgi, mis vastab (mathbf {N –IQC}); ja kõik (mathbf {H – IQC}) aksioomid on tõestatavad kataloogis (mathbf {N – IQC}).
Dedutsiooniteoreemi kasulikkuse illustreerimiseks kaaluge (ilmselt triviaalset) teoreemi skeemi ((A \ paremäär A)). (Mathbf {H – IPC}) õige tõestus võtab viis rida:
1. (parempoolne nool (A \ paremääris))
2. ((A \ parempoolne (A \ parempoolne A)) parempoolne ((A \ parempoolne ((A \ parempoolne A) parempoolne A)) parempoolne (A \ paremääris A)))
3. ((A \ parempoolne ((A \ parempoolne A) parempoolne A)) parempoolne (A \ parempoolne A))
4. (paremäär nool ((A \ parem nool A) paremnool A))
5. (parempoolne nool A)
kus 1, 2 ja 4 on aksioomid ja 3, 5 pärinevad modus ponensi varasematest joontest. Kuid (A) on tuletatav dokumendist (A) (eeldusena) ühes ilmses etapis, seega võimaldab deduktsiooni teoreem järeldada, et (A \ parempoolne A) on olemas. (Tegelikult on äsja esitatud (A \ parempoolne nool A) ametlik tõend osa mahaarvamisteoreemi konstruktiivsest tõestusest!)
Oluline on märkida, et (mathbf {H – IQC}) eeldustest tuletamise määratlemisel käsitletakse oletuse valemeid nii, nagu oleks kõik nende vabad muutujad universaalselt kvantifitseeritud, nii et (forall x A (x)) on tuletatav hüpoteesist (A (x)). Muutujat (x) varieeritakse (mitte konstantsena) selles tuletuses, kasutades reeglit (forall) - sissejuhatus; ja seega ei saa deduktsiooniteoreemi abil järeldada (ekslikult), et (A (x) parempoolne nool \ forall x A (x)) (ja järelikult (on olemas) - likvideerimine, (eksisteerib x A (x) paremnool \ forall x A (x))) on tõestatavad kataloogis (mathbf {H – IQC}). Predikaatloogika jaoks deduktsiooniteoreemi korrektse kasutamise näitena võiks kaaluda implikatsiooni (eksisteerib x A (x) paremnool \ neg \ forall x \ neg A (x)). Selle näitamine on dokumendis (mathbf {H – IQC}) tõestatav,kõigepealt tuletame (neg \ forall x \ neg A (x)) väärtusest (A (x)), kus kõiki vabu muutujaid hoitakse konstantsena:
1. (jätkub x \ neg A (x) paremnool \ neg A (x))
2. (A (x) parempoolne nool (forall x \ neg A (x) rightarrow A (x)))
3. (A (x)) (eeldus)
4. (jätkub x \ neg A (x) parempoolne nool A (x))
5. ((forall x \ neg A (x) rightarrow A (x)) rightarrow ((forall x \ neg A (x) rightarrow \ neg A (x)) rightarrow \ neg \ forall x \ neg A (x)))
6. ((forall x \ neg A (x) rightarrow \ neg A (x)) rightarrow \ neg \ forall x \ neg A (x))
7. (neg \ forall x \ neg A (x))
Siin on 1, 2 ja 5 aksioomid; 4 on moodustatud punktidest 2 ja 3; ning 6 ja 7 on pärit modus ponensi varasematest liinidest; seega pole muutujaid muudetud. Dedutsiooniteoreem ütleb, et dokumendis (mathbf {H – IQC}) on ((x) parempoolne nool \ neg \ forall) x (neg A (x)) tõestus (P).) ja üks rakenduse (eksisteerib) - likvideerimine teisendab (P) (eksisteerib x A (x) paremnool \ neg \ forall x \ neg A (x)) tõestuseks. Vastupidist pole (mathbf {H – IQC}) abil tõestada, nagu on näidatud jaotises 5.1.
Muudeks olulisteks alternatiivideks (mathbf {H – IQC}) ja (mathbf {N – IQC}) jaoks on erinevad järjestikused arvutuspõhimõtted intuitiivistliku ja predikaatloogika jaoks. Esimese sellise kivi määratles Gentzen [1934–5], vrd. Kleene [1952]. Järjestikused süsteemid, mis tõestavad täpselt samu valemeid nagu (mathbf {H – IQC}) ja (mathbf {N – IQC}), jälgivad selgesõnaliselt kõiki eeldusi ja järeldusi tõenduse igal etapil, asendades need modus ponens (mis välistab vahevalemi) lõikereegli abil (mida võib osutuda lubatavaks reegliks (vt punkt 4.2) allsüsteemi jaoks, kui see jääb ära).
Kui formaalsuse üksikasjad pole olulised, järgime nüüdsest Troelstra ja van Dalenit [1988], lastes “(mathbf {IQC})” või “(mathbf {IPC})” viidata mis tahes formaalne süsteem vastavalt intuitiivse predikaadi või propositsioonilise loogika jaoks ning sarnaselt klassikalise predikaadi ja propositsioonilise loogika jaoks "(mathbf {CQC})" ja "(mathbf {CPC})".
Nii (mathbf {IPC}) kui ka (mathbf {IQC}) vastavad interpolatsiooniteoreemidele, nt: kui (A) ja (B) on pakkumisvalemid, millel on vähemalt üks ühine tähereklaam, ja kui (A \ parempoolne nool B) on tõestatav dokumendis (mathbf {IPC}), siis on olemas valem (C), mis sisaldab ainult pakkumistähti, mis esinevad nii (A) kui (B), nii et (A \ parempoolne nool C) ja (C \ parempoolne nool B) on tõestatavad. Neid teemasid käsitletakse Kleene'is [1952] ning Troelstra ja Schwichtenbergis [2000].
Ehkki identiteeti saab loomulikult lisada intuitsioonilisele loogikale, käsitletakse rakenduste (nt aritmeetika) puhul võrdsussümbolit üldiselt eristatud predikaatkonstandina, mis vastab ekvivalentsussuhte (refleksivus, sümmeetria ja transitiivsus) aksioomidele ja täiendavatele mitteloogilistele aksioomidele (nt, liitmise ja korrutamise primitiivsed rekursiivsed määratlused). Identiteet on nii intuitiivselt kui ka klassikaliselt otsustatav, kuid intuitsiooniline laienemisvõrdsus ei ole alati otsustatav; vt Brouweri järjepidevuse aksioomide arutelu intuitiivismi käsitleva sissejuhatuse 3. jaos matemaatikafilosoofias.
Intuitionistlikul (heyting) aritmeetilisel (mathbf {HA}) ja klassikalisel (Peano) aritmeetilisel (mathbf {PA}) on sama esimese astme keel ja samad mitteloogilised aksioomid; ainult loogika on erinev. Lisaks loogilistele ühendustele, kvantifikaatoritele ja sulgudele ning üksikutele muutujatele (x, y, z, \ ldots) (kasutatakse ka metamuutujatena) on aritmeetika keeles (L (mathbf {HA})) ka aritmeetika keel binaarne predikaatmärk (=), individuaalne konstant (0), ühefunktsiooniline konstant (S) ja lõplikult või loendamatult lõpmata palju täiendavaid konstante primitiivsete rekursiivsete funktsioonide jaoks, sealhulgas liitmine ja korrutamine; täpne valik on maitse ja mugavuse küsimus. Terminid on üles ehitatud muutujatest ja (0) kasutades funktsiooni konstante; eriti,iga naturaalarv (n) väljendatakse keeles numbriga (mathbf {n}), mis saadakse, rakendades (S) (n) korda väärtusele (0) (nt (S (S (0))) on (2) number. Peamised valemid on kujul ((s = t)), kus (s, t) on terminid, ja liitvalemid saadakse nendest nagu tavaliselt.
(Mathbf {HA}) loogilised aksioomid ja reeglid on esimese astme intuitiivne predikaatloogika (mathbf {IQC}). Mitteloogilised aksioomid hõlmavad (=) refleksiivseid, sümmeetrilisi ja transitiivseid omadusi:) forall x (x = x),)) forall x \ forall y (x = y \ rightarrow y = x),;
) kõik x \ neg (S (x) = 0),)
aksioom, mis iseloomustab (S) üks-ühele funktsioonina:
) jätkatakse x \ jätkatakse y (S (x) = S (y) parempoolne nool x = y),)
(S) võrdõiguslikkuse aksioom:
) jätkub x \ jätka y (x = y \ paremnool S (x) = S (y));)
iga funktsiooni konstandi primitiivsed rekursiivsed definitsioonivõrrandid, eriti liitmiseks:) forall x (x + 0 = x),)) forall x \ forall y (x + S (y) = S (x +) y));) ja korrutamine:) forall x (x \ cdot 0 = 0),)) forall x \ forall y (x \ cdot S (y) = (x \ cdot y) + x);) ja matemaatilise induktsiooni skeem (universaalne sulgemine) suvaliste valemite jaoks (A (x)):
[(A (0) lahendid \ forall x (A (x) paremnool A (S (x)))) paremnool \ forall x A (x).)
Kõigi funktsioonikonstantide ekstensiivsed võrdsuse aksioomid on tuletatavad matemaatilise induktsiooni abil (S) ja primitiivsete rekursiivsete funktsioonide aksioomide võrdsuse aksioomist.
Naturaalse järjekorra seose (x \ lt y) saab määratleda rakenduses (mathbf {HA}) abil (eksisteerib z (S (z) + x = y)) või kvantifikaatorita valem (S (x) punkt {-} y = 0), kui sümbol ja eelkäija määratlevad primitiivsed rekursiivsed võrrandid: [Pd (0) = 0,)) forall x (Pd (S (x))) = x)) ja läbilõike lahutamine:) forall x (x \ dot {-} 0 = 0),)) forall x (x \ dot {-} S (y) = Pd (x \ dot {-} y))) esinevad formalismis. (mathbf {HA}) tõestab võrdlevat seadust
) kõik x x kogu aeg y (x \ lt y \ vee x = y \ vee y \ lt x))
ja väikseima arvu põhimõtte intuitiivne vorm suvaliste valemite (A (x)) jaoks:
) Forall x) Forall y (y \ lt x \ paremnool (A (y) vee \ neg A (y))) rightarrow \(eksisteerib y ((y \ lt x \ oldand A (y))) oldand \ forall z (z \ lt y \ rightarrow \ neg A (z))) vee \\ \ forall y (y \ lt x \ rightarrow \ neg A (y)))].)
Hüpoteesi on vaja, kuna mitte kõik aritmeetilised valemid ei ole (mathbf {HA}) korral otsustatavad. Kuid (forall x \ forall y (x = y \ vee \ neg (x = y)))) saab tõestada otse matemaatilise induktsiooni abil ja nii
Peamised valemid (ja seega ka kõik kvantitaatorivabad valemid) on (mathbf {HA}) korral otsustatavad ja stabiilsed.
Kui (A (x)) on otsustusvõimeline rakenduses (mathbf {HA}), siis sissejuhatusega sisse lülitades (x) on ka (jätkub y (y \ lt x \ parempoolne nool A (y))) ja (eksisteerib y (y \ lt x \ oldand A (y))). Seega
Valemid, milles kõik kvantifikaatorid on piiratud, on (mathbf {HA}) korral otsustatavad ja stabiilsed.
Aritmeetiliste valemite kogum (Delta_0), milles kõik kvantifikaatorid on piiratud, on klassikalise aritmeetilise hierarhia madalaim tase, mis põhineb kvantifikaatorite vaheldumiste mustril prenexi valemis. Aastal (mathbf {HA}) pole kõigil valemitel prenexi vormi, kuid Burr [2004] avastas lihtsa intuitsionistliku aritmeetilise hierarhia, mis vastab tasandite kaupa klassikale. Ainult järgmise kahe määratluse jaoks tähistab (forall x) lõplikult paljude universaalsete numbrikõnestuste plokki ja samamoodi tähistab (eksisteerib x) lõplikult paljude eksistentsiaalsete numbrikvantorite plokki. Nende kokkulepete abil on Burri klassid (Phi_n) ja (Psi_n) määratletud järgmiselt:
(Phi_0 = \ Psi_0 = \ Delta_0),
(Phi_1) on vormi kõigi valemite klass (forall x A (x)), kus (A (x)) asub (Psi_0). (N \ ge 2) jaoks on (Phi_n) vormi kõigi valemite klass (forall x [A (x) parempoolne nool on olemas y B (x, y)]), kus (A (x)) on asukohas (Phi_ {n-1}) ja (B (x, y)) on asukohas (Phi_ {n-2}),
(Psi_1) on vormi kõigi valemite klass (eksisteerib x A (x)), kus (A (x)) asub (Phi_0). Sest (n \ ge 2), (Psi_n) on kõigi vormi (A parempoolne nool B) valemite klass, kus (A) asub (Phi_n) ja (B) asub asukohas (Phi_ {n-1}).
Vastavad klassikalised prenexi klassid on lihtsamalt määratletud:
(Pi_0 = \ Sigma_0 = \ Delta_0),
(Pi_ {n +1}) on vormi kõigi valemite klass (forall x A (x)), kus (A (x)) asub (Sigma_n),
(Sigma_ {n +1}) on vormi kõigi valemite klass (eksisteerib x A (x)), kus (A (x)) asub (Pi_n).
Peano aritmeetiline (mathbf {PA}) pärineb aritmeetikast Heyting (mathbf {HA}), lisades LEM või (neg \ neg A \ parempoolne nool A) loogiliste aksioomide loendisse, st kasutades intuitiivse loogika asemel klassikalist. Järgmised tulemused kehtivad isegi (mathbf {HA}) ja (mathbf {PA}) fragmentide korral, kusjuures induktsiooniskeem on piiratud (Delta_0) valemitega.
Burri teoreem:
Iga aritmeetiline valem on tõestatavalt (mathbf {HA}) ekvivalentselt valemiga ühes klassidest (Phi_n).
Iga valem rakenduses (Phi_n) on tõestatavalt samaväärne dokumendis (mathbf {PA}) valemiga dokumendis (Pi_n) ja vastupidi.
Iga valem dokumendis (Psi_n) on tõestatavalt samaväärne dokumendis (mathbf {PA}) valemiga dokumendis (Sigma_n) ja vastupidi.
(mathbf {HA}) ja (mathbf {PA}) on tõestusteoreetiliselt ekvivalentsed, nagu näidatakse jaotises 4. Mõlemad suudavad (numbriliselt) väljendada oma tõendipregaati. Gödeli kuulsa mittetäielikkuse teoreemi järgi, kui (mathbf {HA}) on järjekindel, siis ei (mathbf {HA}) ega (mathbf {PA}) suuda omaenda järjepidevust tõestada.
Intuitsionistliku loogika põhiline fakt on see, et sellel on sama järjepidevuse tugevus kui klassikalisel loogikal. Algloogika jaoks tõestas seda esmakordselt Glivenko [1929].
Glivenko teoreem Suvaline juhendvalem
(A) on klassikaliselt tõestatav, kui ja ainult siis, kui (neg \ neg A) on intuitiivselt tõestatav.
Glivenko teoreem ei laiene predikaatloogikale, ehkki suvaline predikaatvalem (A) on klassikaliselt tõestatav siis ja ainult siis, kui (neg \ neg A) on intuitiivses predikaatloogikas pluss kahekordse eituse nihke skeemis tõestatav.
) sildi {DNS} forall x \ neg \ neg B (x) rightarrow \ neg \ neg \ forall x B (x))
Klassikalise teksti keerukam negatiivne tõlkimine intuitsioonistlikesse teooriatesse seostub Gödeli ja Gentzeniga sõltumatult keele iga valemiga (A) teise valemiga (L) teise valemiga (g (A)) (millel pole (vee) või (on olemas)), näiteks
(I) Klassikaline predikaatloogika tõendab (A \ leftrightarrow g (A)).
(II) Intuitionistlik predikaatloogika tõendab (g (A) vasakpoolne \ neg \ neg g (A)).
(III) Kui klassikaline predikaatloogika osutub (A), siis intuitiivne predikaatloogika tõendab (g (A)).
Tõendid on sirged järgmisest (g (A)) induktiivsest määratlusest (kasutades Gentzeni otsest implikatsiooni tõlget, mitte Gödeli sõnade (neg) ja (oldand) tähendust):
) alusta {joonda *} g (P) & \ tekst {on} neg \ neg P, \ tekst {kui} P \ tekst {on peamine}. \\ g (A \ oldand B) & \ text { on} g (A) oldand g (B). \\ g (A \ vee B) & \ tekst {on} neg (neg g (A) oldand \ neg g (B)). \\ g (A \ parempoolne nool B) ja \ tekst {on} g (A) paremnool g (B). \\ g (neg A) & \ tekst {on} neg g (A). \\ g (forall xA (x)) & \ text {on} forall xg (A (x)). \\ g (eksisteerib xA (x)) & \ tekst {on} neg \ forall x \ neg g (A (x)). \ lõpeta {joonda *})
Iga valemi (A) korral on (g (A)) intuitiivselt tõestatav ainult siis, kui (A) on klassikaliselt tõestatav. Eelkõige juhul, kui (B \ oldand \ neg B) oleks mõne valemi jaoks klassikaliselt tõestatav (B), siis (g (B) oldand \ neg g (B)) (mis on (g (B \ oldand \ neg B))) oleks omakorda intuitiivselt tõestatav. Seega
(IV) Klassikaline ja intuitiivne predikaatloogika on võrdses järjepidevuses
Klassika negatiivne tõlkimine intuitionistlikuks arvuteooriaks on veelgi lihtsam, kuna intuitionistliku aritmeetika algvalemid on stabiilsed. Seega võib (g (s = t)) võtta kui (s = t) ja ülejäänud klauslid on muutmata. Matemaatilise induktsiooni mis tahes astme negatiivne tõlge on veel üks matemaatilise induktsiooni näide ja aritmeetika muud mitteloogilised aksioomid on nende enda negatiivsed tõlked, seega
Punktid (I), (II), (III) ja (IV) kehtivad ka numbriteooria jaoks
Gödel [1933e] tõlgendas neid tulemusi nii, et need näitasid, et intuitionistlik loogika ja aritmeetika on klassikalisest loogikast ja aritmeetikast rikkamad, kuna intuitionistlik teooria eristab valemid, mis on klassikaliselt ekvivalentsed ja millel on sama järjepidevustugevus kui klassikalisel teoorial. Eelkõige kehtivad Gödeli mittetäielikkuse teoreemid nii (mathbf {HA}) kui ka (mathbf {PA}) kohta.
Otsesed katsed laiendada negatiivset tõlgendust analüüsile ebaõnnestuvad, kuna valitud loendatava aksioomi negatiivne tõlkimine ei ole intuitionistliku analüüsi teoreem. Kleene rekursiivse realiseeritavuse funktsionaalse versiooni kohaselt on see siiski kooskõlas intuitiivse analüüsiga, sealhulgas Brouweri vastuolulise jätkuvuse põhimõttega (vt punkt 6.2 allpool). Sellest järeldub, et intuitsiooniline matemaatika, mida saab väljendada ainult kõigi standardsete loogiliste ühenduste ja kvantifikaatorite abil, on kooskõlas klassikalise matemaatika ustava tõlkega, vältides (vee) ja (eksisteerivat).
See on oluline, kuna Brouweri intuitionistlik analüüs on LEM-iga vastuolus. Kui aga (A) on mõni negatiivne valem (ilma (vee) või (olemas)), on (neg \ neg A \ parempoolne nool) tõestatav, kasutades intuitiivset loogikat. Moschovakis [2017] soovitatakse intuitiivse ja klassikalise analüüsi vastavusse viimist vastavalt Kripke valimisjada ideele.
4.2 Intuitsionistliku loogika ja aritmeetika lubatavad reeglid
Gödel [1932] leidis, et intuitsioonilisel propositsiooniloogikal on disjunktsiooni omadus:
(DP) Kui (A \ vee B) on teoreem, siis (A) on teoreem või (B) on teoreem
Gentzen [1935] kehtestas intuitsioonilise predikaatloogika suletud valemite disjunktsiooni omaduse. Siit järeldub, et kui intuitiivne loogika on järjekindel, siis (P \ vee \ neg P) pole teoreem, kui (P) on aatomivalem. Kleene [1945, 1952] tõestas, et intuitsioonilisel esimese järgu numbriteoorial on olemas ka seotud (vrd Friedman [1975]) olemasolu omadus:
(EP) Kui (eksisteerib x A (x)) on suletud teoreem, siis mõne suletud termini (t) korral on (A (t)) teoreem
Disjunktsiooni- ja olemasoluomadused on mitteklassikalistele teooriatele omased üldnähtuse erijuhud. Teooria lubatavad reeglid on reeglid, mille alusel teooria suletakse. Näiteks Harrop [1960] täheldas seda reeglit
Kui (neg A \ parempoolne nool (B \ vee C)) on teoreem, siis on ka see ((neg A \ parempoolne nool B) vee (neg A \ parempoolne nool C))
on lubatav intuitsioonilises juhendiloogikas (mathbf {IPC}), sest kui (A), (B) ja (C) on suvalised valemid, nii et (neg A \ parempoolne nool (B \ vee C)) on tõestatav lehel (mathbf {IPC}), siis on ka ((neg A \ parempoolne B) vee (neg A \ parempoolne nool C)) tõestatav kaustas (mathbf {IPC }). Harropi reegel pole tuletatav dokumendis (mathbf {IPC}), kuna (((neg A \ parempoolne (B \ vee C)) paremnool (neg A \ parempoolne B) vee (neg A \ parempoolne nool C)) ei ole intuitiivselt tõestatav. Veel üks oluline näide (mathbf {IPC}) lubatava mittetulematu reegli kohta on Mintsi reegel:
Kui ((A \ parempoolne nool B) parempoolne nool (A \ vee C)) on teoreem, siis on ka see {(((A \ parempoolne B) parempoolne nool A) vee ((A \ paremääris B) paremnool C)).
Klassikalise propositsioonilise loogika (mathbf {CPC}) kahe väärtusega tõestabeli tõlgendus annab lihtsa tõestuse selle kohta, et (mathbf {CPC}) iga lubatav reegel on tuletatav: vastasel juhul on mõni omistamine (A), (B) jne muudaksid hüpoteesi tõeseks ja järelduse valeks ning asendaks tähega “true” ja (P \ oldand \ neg P tähega näiteks tähed (P \ parempoolne nool P)) neile, kellele on määratud „vale”, oleks tõestatav hüpotees ja tõestamatu järeldus. Tõsiasi, et intuitionistlik olukord on huvitavam, põhjustab palju loomulikke küsimusi, millele mõnele on hiljuti vastatud.
Mintsi reegli üldistades tuvastasid Visser ja de Jongh järjest tugevamate vastuvõetavate reeglite (“Visseri reeglid”) rekursiivselt loendatava jada, mis nende poolt oletanud moodustasid aluse (mathbf {IPC}) lubatavatele reeglitele selles mõttes et iga lubatav reegel on tuletatav disjunktsiooniomadusest ja ühest järjestuse reeglist. Ghilardi [1999] töö põhjal õnnestus Iemhoffil [2001] nende oletusi tõestada. Rybakov [1997] tõestas, et (mathbf {IPC}) kõigi lubatavate reeglite kogumine on otsustatav, kuid sellel pole lõplikku alust. Visser [2002] näitas, et tema reeglid on ka Markovi peaministri laiendatud (määratletud allpool jaotises 5.2) laiendatud (mathbf {HA}) ja (mathbf {HA}) eeldatavad reeglid. Viimasel ajal,Jerabek [2008] leidis (mathbf {IPC}) lubatavatele reeglitele sõltumatu aluse koos omadusega, et ükski selle reegli alus ei tulene teisest.
Intuitsionistliku predikaatloogika lubatavate reeglite kohta on palju vähem teada. Puhtal (mathbf {IQC}), ilma individuaalsete või predikatiivsete konstantideta, on järgmine tähelepanuväärne reegel (A (x)) jaoks, ilma et muutujad oleksid vabad, kuid (x):
Kui (eksisteerib x A (x)) on teoreem, siis on ka see (forall x A (x)).
Mitte iga lubatav predikaatreegel (mathbf {IQC}) pole lubatav kõigi formaalsete süsteemide jaoks, mis põhinevad (mathbf {IQC}); näiteks rikub (mathbf {HA}) ilmselgelt just öeldud reeglit. Visser tõestas [1999], et (mathbf {HA}) lubatava predikaadireegli omadus on (Pi_2) täielik, ja [2002], et (mathbf {HA}) (+) MP-l on samad eeldatavad lubatavad reeglid kui (mathbf {HA}). Plisko [1992] tõestas, et (mathbf {HA}) (+) MP predikaatloogika (lausekomplekt nende (mathbf {IQC}) keeles, kelle kõik ühesugused asendusjuhud aritmeetika keel on tõestatav, kui (mathbf {HA}) (+) MP) on (Pi_2) täielik; Visser [2006] laiendas seda tulemust mõnele konstruktiivselt huvitavale järjekindlale laiendile (mathbf {HA}), mida (mathbf {PA}) ei sisaldu.
Ehkki neid ei ole täielikult klassifitseeritud, hõlmavad intuitiivse predikaatloogika lubatavad reeglid Markovi reeglit otsustatavate predikaatide kohta:
Kui (forall x (A (x) vee \ neg A (x)) oldand \ neg \ forall x \ neg A (x)) on teoreem, siis on ka (eksisteerib x A (x)).
ja järgmine eeldusliku sõltumatuse reegel (kus eeldatakse, et (y) ei esine vabalt asukohas (A (x))):
Kui (forall x (A (x) vee \ neg A (x)) oldand (forall x A (x) rightarrow \ eksisteeriv y B (y))) on teoreem, siis on ka (eksisteerib y (kõik x A (x) paremnool B (y))).
Mõlemad reeglid on vastuvõetavad ka (mathbf {HA}) jaoks. Vastavaid implikatsioone (vastavalt MP ja IP), mis ei ole intuitiivselt tõestatavad, kontrollitakse Gödeli tõlkega (mathbf {HA}) (Dialectica) (vrd allpool jaotist 6.3). Nii on ka implikatsioon (CT), mis vastab Heytingi aritmeetika kõige huvitavamale vastuvõetavale reeglile, nimetagem seda kiriku-Kleene'i reegliks:
Kui (forall x \ eksisteerib y A (x, y)) on (mathbf {HA}) suletud teoreem, siis on olemas arv (n), nii et provably in (mathbf {HA}), osaline rekursiivne funktsioon Gödeli numbriga (n) on kokku ja kaardistab iga (x) (y), mis vastab (A (x, y)) (ja pealegi (A (mathbf {x}, \ mathbf {y})) on tõestatav, kus (mathbf {x}) on naturaalarvu (x) ja (mathbf {y}) on (y)) number.
Markovi reegli ühendamine negatiivse tõlkega annab tulemuse, et klassikaline ja intuitiivne aritmeetika tõestavad vorme (forall x \ eksisteerib y A (x, y)), kus (A (x, y)) on samad valemid kvantifikaatorivaba. Üldiselt, kui (A (x, y)) on tõestatavalt otsustatav dokumendis (mathbf {HA}) ja kui (forall x \ eksisteerib y A (x, y)) on suletud teoreem klassikaline aritmeetika (mathbf {PA}), kehtib Kiriku-Kleene'i reegli järeldus isegi intuitionistlikus aritmeetikas. Kui kui (mathbf {HA}) osutub (forall x \ forall y (A (x, y) vee \ neg A (x, y)))), siis Kiriku-Kleene'i reegli järgi iseloomulik funktsioon of (A (x, y)) omab Gödeli arvu (m), tõenäoliselt (mathbf {HA}); nii (mathbf {HA}) osutub (forall x \ eksisteerib y A (x, y) leftrightarrow \ forall x \ eksisteerib y \ eksisteerib z B (mathbf {m}, x, y, z)) kus (B) on kvantitatiivselt vaba,ja külgnevate eksistentsiaalsete kvantifikaatoritega saab kokku leppida kataloogis (mathbf {HA}). Sellest järeldub, et (mathbf {HA}) ja (mathbf {PA}) on samad provokatiivselt rekursiivsed funktsioonid.
See on tõend selle kohta, et reegel “Kui (forall x (A \ vee B (x))]) on teoreem, nii on ka (A \ vee \ forall x B (x))” (kus (x) ei ole rakenduses (A)) lubatud (mathbf {HA}) jaoks, kui (mathbf {HA}) on järjekindel. Gödeli numeratsioon annab kvantitatiivse valemi (G (x)), mis (numbriliselt) väljendab predikaati “(x) on (mathbf {HA}) tõestuse kood, mis on ((0) = 1)).” Kvantitatiivsete aritmeetiliste valemite otsustatavusega intuitiivse loogika abil tõestab (mathbf {HA}), et (forall x (eksisteerib y G (y) vee \ neg G (x))). Kui aga (mathbf {HA}) osutus (eksisteerib yG (y) vee \ forall x \ neg G (x)), siis disjunktsiooni omaduse järgi peab (mathbf {HA}) tõesta kas (eksisteerib yG (y)) või (forall x \ neg G (x)). Esimene juhtum on võimatu,olemasolu omaduse kaudu järjepidevuse eeldusega ja tõsiasjaga, et (mathbf {HA}) tõestab kõiki tõelisi kvantifikaatorivabu lauseid. Kuid ka teine juhtum on Gödeli teise puudulikkuse teoreemi järgi võimatu, kuna (forall x \ neg G (x)) väljendab (mathbf {HA}) järjepidevust.
5. Põhisemantika
Intuitionistlikud süsteemid on inspireerinud mitmesuguseid tõlgendusi, sealhulgas Bethi tabel, Rasiowa ja Sikorski topoloogilised mudelid, Heytingi algebrad, valemid kui tüübid, Kleene rekursiivne realiseeritavus, Kleene ja Aczeli kaldkriipsud ning pätsidel ja topoil põhinevad mudelid. Kõigist neist tõlgendustest sarnaneb Kripke [1965] võimaliku maailma semantika, milles intuitionistlik predikaatloogika on täielik ja järjekindel, kõige enam sarnaneb klassikalisele mudelateooriale. Rekursiivsed realiseeritavuse tõlgendused üritavad seevastu BHK intuitiivse tõe seletust tõhusalt rakendada.
5.1 Kripke intuitiivse loogika semantika
Kripke struktuur (mathbf {K}) jaoks (L) koosneb sõlmede osaliselt tellitud komplektist (K) ja domeenifunktsioonist D, mis omistatakse igale sõlmele (k) (K) asustatud komplekt (D (k)), nii et kui (k \ le k '), siis (D (k) subseteq D (k')). Lisaks on (mathbf {K}) sundusside, mis on määratletud järgmiselt.
Iga sõlme (k) jaoks olgu (L (k)) keel, mis laiendab (L) uute konstanditega kõigi elementide (D (k)) jaoks. Igale sõlmele (k) ja igale (0) - eeldatav täht (iga pakkumise täht) (P), määrake (f (P, k) =) tõene või jätke (f (P, k)) määratlemata, kooskõlas nõudega, et kui (k \ le k ') ja (f (P, k) =) tõene, siis (f (P, k') =) tõene ka. Öelda, et
(k) (vDash) (P) ainult siis, kui (f (P, k) =) vastab tõele.
Igale sõlmele (k) ja igale ((n + 1)) - sisestage predikaattäht (Q (ldots)), määrake (võib-olla tühi) komplekt (T (Q, k)) of ((n + 1)) - (D (k)) elementide kogumid viisil, et kui (k \ le k '), siis (T (Q, k) subseteq T (Q, k ')). Öelda, et
(k) (vDash) (Q (d_0, \ ldots, d_n)) siis ja ainult siis, kui ((d_0, \ ldots, d_n) in T (Q, k)).
Nüüd määratlege (k) (vDash) (E) (mida võib lugeda kui "(k) jõud (E)") liitlausete (E) jaoks (L (k)) induktiivselt järgmiselt:
(k) (vDash) ((A \ oldand B))
if (k) (vDash) (A) ja (k) (vDash) (B).
(k) (vDash) ((A \ vee B))
if (k) (vDash) (A) või (k) (vDash) (B).
(k) (vDash) ((A \ paremäär B))
kui iga (k '\ ge k), kui (k') (vDash) (A) siis (k ') (vDash) (B).
(k) (vDash) (neg A)
kui ei, siis (k '\ ge k) ei (k') (vDash) (A).
(k) (vDash) (forall x A (x))
kui iga (k '\ ge k) ja iga (d \ sisse D (k')), (k ') (vDash) (A (d)) jaoks.
(k) (vDash) (eksisteerib x A (x))
kui mõne jaoks (d \ D (k)), (k) (vDash) (A (d)).
Iga selline sunniviisiline seos on järjepidev:
Lauseta (A) ja (k) puhul pole nii, et nii (k) (vDash) (A) kui ka (k) (vDash) (neg A).
ja ühetooniline:
Kui (k \ le k ') ja (k) (vDash) (A), siis (k') (vDash) (A).
Kripke õigsuse ja täielikkuse teoreemid kinnitavad, et lause (L) lause on intuitiivses predikaatloogikas tõestatav siis ja ainult siis, kui see on sunnitud iga Kripke struktuuri iga sõlme poolt. Seega, selleks, et näidata, et (neg \ forall x \ neg P (x) rightarrow \ eksisteerib x P (x)) on intuitiivselt tõestamatu, piisab Kripke'i struktuuri kaalumisest (K = {k, k '},) (k \ lt k',) (D (k) = D (k ') = {0 }), (T (P, k)) tühi, kuid (T (P, k ') = {0 }). Ja vastupidise näitamiseks on intuitiivselt tõestatav (ilma tõestust tegemata) on vaja vaid suvaliste Kripke mudelite järjepidevust ja monotoonsust koos määratlusega (vDash).
Võrdõiguslikkusega keelte Kripke-mudelid võivad tõlgendada iga sõlme (=) suvalise ekvivalentsussidemega monotoonilisuse tingimustes. Intuitsionistliku aritmeetika rakendamiseks piisab normaalsetest mudelitest (neist, kus võrdsust tõlgendatakse identiteedina igas sõlmes), kuna naturaalarvude võrdsus on otsustatav.
Propositsiooniline Kripke semantika on eriti lihtne, kuna suvaline propositsiooniline valem on intuitiivselt tõestatav siis ja ainult siis, kui seda sunnib iga Kripke mudeli juur, mille raam (sõlmede komplekt ((K)) koos nende osalise järjestamisega) on piiratud puu, millel on kõige vähem elementi (juur). Näiteks Kripke mudel koos (K = {k, k ', k' '}, k \ lt k') ja (k \ lt k '') ning koos (P) tõsi ainult juhul, kui (k '), näitab, et nii (P \ vee \ neg P) kui ka (neg P \ vee \ neg \ neg P) on rakenduses (mathbf {IPC}) tõestamatud.
Kripke mudeli iga lõppsõlm või leht on klassikaline mudel, kuna leht sunnib igat valemit või selle eitust. Ainult need pakkumise tähed, mis esinevad valemis (E), ja ainult need sõlmed (k '), mis (k \ le k'), on olulised otsuse tegemisel, kas (k) jõud (E). Sellised kaalutlused võimaldavad meil tõhusalt seostada (L (mathbf {IPC})) lõplike Kripke struktuuride iga valemiga (E) lõpliku klassi, mis sisaldab vastupidist mudelit (E), kui selline on olemas. Kuna kõigi teoreemide klass (mathbf {IPC}) on rekursiivselt loendatav, järeldame, et
(mathbf {IPC}) on tegelikult otsustatav. On olemas rekursiivne protseduur, mis määrab iga pakkumisvalemi (E) jaoks, kas (E) on teoreem (mathbf {IPC}), lõpetades kas (E) või (piiratud) Kripke kontramodell.
(Mathbf {IPC}) otsustusvõimelisuse saavutas Gentzen esmakordselt 1935. aastal. (Mathbf {IQC}) otsustamatus tuleneb (mathbf {CQC}) otsustamatusest negatiivse tõlgenduse abil..
Tuttavad mitteintuitsionistlikud loogilised skeemid vastavad näiteks Kripke mudelite struktuurilistele omadustele
DNS on igas Kripke mudelis piiratud raamiga.
((A \ parempoolne nool B) vee (B \ parempoolne nool A)) hoiab igas Kripke mudelis lineaarselt järjestatud raami. Seevastu igal pakkumisvalemil, mis ei ole tuletatav lehel (mathbf {IPC} + (A \ parempoolne nool B) vee (B \ parempoolne nool A)), on lineaarselt järjestatud raamiga Kripke-vastasmudel (vrd allpool punkt 6.1).
Kui (x) pole rakenduses (A) vaba, siis (forall x (A \ vee B (x)) parempoolset noolt (A \ vee \ forall x B (x))) hoiab igas Kripkes mudel (mathbf {K}) konstantse domeeniga (nii, et (D (k) = D (k ')) kõigi (k, k') jaoks (K)). Sama kehtib ka MP kohta.
Kripke mudelid ja Bethi mudelid (mis erinevad Kripke mudelitest üksikasjalikult, kuid on intuitiivselt ekvivalentsed) on võimas tööriist intuitiivsete formaalsete süsteemide omaduste kindlakstegemiseks; vrd Troelstra ja van Dalen [1988], Smorynski [1973], de Jongh ja Smorynski [1976], Ghilardi [1999] ja Iemhoff [2001], [2005]. Puudub aga intuitiivne tõend selle kohta, et iga lause, mis kehtib kõigis Kripke ja Bethi mudelites, on tõestatav ka versioonis (mathbf {IQC}). Pärast Gödeli tähelepanekut kontrollis Kreisel [1958], et Bethi semantika intuitiivse predikaatloogika täielikkus on samaväärne Markovi põhimõttelise MP-ga, mille Brouwer tagasi lükkas.
Veelgi enam, Dyson ja Kreisel [1961] näitasid, et kui (mathbf {IQC}) on Beti semantika jaoks nõrgalt täielik (see tähendab, kui igas Beti mudelis pole ühtegi tõestamatut lauset), siis on MP järgmine järeldus: [silt {GDK} forall \ alpha_ {B (alpha)} neg \ neg \ eksisteerib x R (alpha, x) paremnool \ neg \ neg \ forall \ alpha_ {B (alpha)} eksisteerib x R (alpha, x),) kus (x) ulatub kõigi naturaalarvude suhtes, (alpha) ulatub kõigist naturaalarvude lõpmatutest jadadest, (B (alpha)) lühendab (forall x (alpha (x) leq 1)) ja (R) väljendab (alpha) ja (x) primitiivset rekursiivset suhet. GDK tähendab seevastu (mathbf {IQC}) nõrka täielikkust. See huvitav põhimõte, mis õigustaks Brouweri fänniteoreemi teatud vormi negatiivset tõlgendamist,on nõrgem kui MP, kuid praegustes intuitionistliku analüüsi süsteemides tõestamatu. Kreisel [1962] leidis, et GDK võib olla intuitiivse matemaatika seni avastamata omaduste põhjal tõestatav.
Muutes Kripke mudeli määratlust nii, et see võimaldaks iga lauset sundivaid "plahvatavaid sõlmi", leidis Veldman [1976] täielikkuse tõestuse, kasutades ainult intuitionistlikku loogikat, kuid ta seadis kahtluse alla, kas plahvatavate sõlmedega Kripke mudelid olid intuitiivselt tähendusrikkad matemaatilised objektid.
Üks viis aritmeetika intuitiivse tõe BHK-seletuse rakendamiseks on seostada (mathbf {HA}) iga lausega (E) mõni arvkoodide kogum algoritmidele, mis võimaldavad tuvastada (E). Kleene'i [1945] järgi realiseerib arv (e) aritmeetika keele lause (E) induktsiooni abil loogilisele kujule: (E):
(e) mõistab (r = t)
kui (r = t) on tõene.
(e) realiseerib (A \ oldand B)
kui (e) kodeerib paari ((f, g)) nii, et (f) realiseerub (A) ja (g) realiseerub (B).
(e) realiseerib (A \ vee B)
kui (e) kodeerib paari ((f, g)) nii, et kui (f = 0), siis (g) realiseerub (A) ja kui (f \ gt 0), siis (g) realiseerib (B).
(e) realiseerib (A \ paremnool B)
kui alati, kui (f) realiseerub (A), määratletakse (e) osaline rekursiivne funktsioon punktis (f) ja selle väärtus realiseerub (B).
(e) realiseerib (neg A)
kui no (f) ei saa aru (A).
(e) realiseerib (forall x A (x))
kui iga (n) jaoks on (e) osaline rekursiivne funktsioon defineeritud väärtuses (n) ja selle väärtus realiseerub (A (mathbf {n})).
(e) realiseerib (eksisteerib x A (x))
kui (e) kodeerib paari ((n, g)) ja (g) realiseerub (A (mathbf {n})).
Suvaline valem on realiseeritav, kui mõni number saab aru oma universaalsest sulgemisest. Pange tähele, et nii (A) kui ka (neg A) pole ühegi valemi (A) jaoks realiseeritavad. Põhiline tulemus on
Nelsoni teoreem [1947]
Kui (A) on tuletatav rakenduses (mathbf {HA}) realiseeritavatest valemitest (F), siis on (A) realiseeritav.
Mõnda mitteintuitsionistlikku põhimõtet saab näidata realiseeritavana. Näiteks saab Markovi põhimõtet (otsustatavate valemite jaoks) väljendada skeemi abil
(MP) (forall x (A (x) vee \ neg A (x)) oldand \ neg \ forall x \ neg A (x) rightarrow \ eksisteeriv x A (x))
Ehkki (mathbf {HA}) pole tõestatav, on MP realiseeritav argumendiga, mis kasutab Markovi põhimõtet mitteametlikult. Kuid realiseeritavus on põhimõtteliselt mitteklassikaline tõlgendus. Raamatus (mathbf {HA}) on võimalik väljendada rekursiivse valiku CT aksioomi (kiriku väitekirja jaoks), mis on LEM-iga vastuolus, kuid on (konstruktiivselt) realiseeritav. Nelsoni teoreemi järgi on (mathbf {HA}) (+) MP (+) CT järjekindel.
Kleene kasutas numbrite realiseeritavuse varianti, et tõestada, et (mathbf {HA}) vastab Kiriku-Kleene'i reeglile; sama argument töötab ka (mathbf {HA}) puhul koos MP või CT ja (mathbf {HA}) (+) MP (+) CT. Kleene'is ja Vesley'is [1965] ja Kleene'is [1969] asendavad funktsioonid numbreid realiseerivate objektidena, luues formaliseeritud intuitionistliku analüüsi järjepidevuse ja selle sulgemise kiriku-Kleene reegli teise järgu versiooni alusel.
Nelsoni teoreem kehtestab mõne (klassikalise predikaatloogika teoreemi) tõestamatuse (mathbf {IQC}). Kui igale (n) - panna predikaattäht (P (ldots)), siis valemiga (f (P)) on (L (mathbf {HA})) koos (n) määratakse vabad muutujad ja kui valemi (f (A)) väärtus (L (mathbf {HA})) pärineb valemist (A) (L), asendades need iga algvalem (P (x_1, \ ldots, x_n)), kasutades (f (P) (x_1, \ ldots, x_n)), siis (f (A)) nimetatakse aritmeetiliseks asendusinstantsiks (A). Näitena, kui valem (L (mathbf {HA})), mis väljendab “(x), kodeerib valemi (mathbf {HA}) tõestuse koodiga (y)”On määratud väärtusele (P (x, y)), tulemuseks on aritmeetiline asendusinstants ((eksisteerib y) (eksisteerib x P (x, y) vee \ neg \ eksisteerib x P (x, y))) on realiseerimatu ja seega tõestamatu (mathbf {HA}) puhul, nagu ka selle kahekordne eitus. Sellest järeldub, et (neg \ neg \ forall y (eksisteerib x P (x, y) vee \ neg \ eksisteerib x P (x, y))) pole (mathbf {IQC}).
De Jongh [1970] ühendas realiseeritavuse Kripke modelleerimisega, et näidata, et intuitionistlik propositsiooniline loogika (mathbf {IPC}) ja osa (mathbf {IQC}) on aritmeetiliselt täielikud (mathbf {HA}). Tõestamiseks piisab tähtede ennustamiseks lihtsate eksistentsiaalsete valemite ühetaolisest määramisest
De Jonghi teoreem (IPC jaoks) [1970]
Kui keele (L) pakkumisvalem (A) pole (mathbf {IPC}) tõestatav, siis on mõni ((A) aritmeetiline asendusinstinkt) pole (mathbf {HA}) abil tõestatav.
De Jonghi teoreemi selle versiooni tõestus ei vaja realiseeritavust; vrd Smorynski [1973]. Näitena võib tuua Rosseri Gödeli mittetäielikkuse teoreemi sellise lause (C) lause (L (mathbf {HA})), et (mathbf {PA}) ei tõesta ei (C) ega (neg C), seega disjunktsiooni omadus (mathbf {HA}) ei suuda tõestada ((C \ vee \ neg C)). Kuid de Jonghi semantiline tõend näitas ka seda, et igal intuitiivselt tõestamata piiratud laadi predikaat-valemitel on aritmeetiline asendusinstinkt, mis on (mathbf {HA}) tõestamatu. Süntaktilist meetodit kasutades laiendas Daniel Leivant [1979] de Jonghi teoreemi kõigile intuitiivselt tõestamatutele predikaatvalemitele, tõestades, et (mathbf {IQC}) on (bf {HA}) aritmeetiliselt täielik. Vaadake van Osteini [1991] ajaloolist ekspositsiooni ja täieliku teoreemi lihtsamat tõestust, kasutades Kripke mudelite asemel abstraktset realiseeritavust Beth-mudelitega.
Väitamata, et arvu realiseeritavus langeb kokku intuitiivse aritmeetilise tõega, täheldas Nelson, et iga valemi (A () (L (mathbf {HA})) korral saab predikaat „(y) aru ((A))”Saab väljendada kujul (mathbf {HA}) mõne muu valemiga (lühendatult“(y \ realizesrel A)”) ja skeem (A \ leftrightarrow \ eksisteerib y (y \ realizesrel A)) on kooskõlas (mathbf {HA}). Troelstra [1973] näitas, et (mathbf {HA}) (+) ((A \ leftrightarrow on olemas y (y \ realiseerib A))) võrdub (mathbf {HA}) (+) ECT, kus ECT on CT tugevdatud vorm. (Mathbf {HA}) (+) MP (+) ECT-s, mida Troelstra peab vene rekursiivse matemaatika vormistamiseks (vrd konstruktiivse matemaatika sissekande punkt 3.2), on iga vormil ((y \ realizesrel A)) on samaväärne “klassikaline” prenexi vorm (A '(y)), mis koosneb kvantitatiivsest alamvormist, millele eelnevad vormide (neg \ neg \ eksisteerib x) ja (forall z \ neg \ neg) vahelduvad „klassikalised“kvantitaatorid, ja nii (eksisteerib y A '(y)) on (A) mingi eelvorm.
6. Lisateemad ja edasine lugemine
6.1 Subintuitsiooniline ja vaheloogika
Praegu on selles entsüklopeedias mitmeid teisi sisendeid, mis käsitlevad intuitionistlikku loogikat erinevates kontekstides, kuid nõrgema ja tugevama propositsioonilise ja predikatiivse loogika üldine käsitlus näib olevat puudulik. Paljud sellised loogikad on tuvastatud ja uuritud. Siin on mõned näited.
Subintuitsionaalse pakkumise loogika saab saidilt (mathbf {IPC}), piirates keelt või nõrgendades loogikat või mõlemat. Äärmuslik näide esimesest on (mathbf {RN}), intuitiivne loogika ühe pakkumismuutujaga (P), mis on oma nime saanud avastajate Riegeri ja Nishimura järgi [1960]. (mathbf {RN}) iseloomustab Riegeri-Nishimura võre, millel on lõpmata palju mitteekvivalentseid valemeid (F_n), nii et iga valem, mille ainus pakutav muutuja on (P), on intuitiivse loogikaga samaväärne mõne (F_n). Nishimura versioon on
) alusta {joonda *} F _ { infty} & = P \ parempoolne nool P. \\ F_0 & = P \ oldand \ neg P. \\ F_1 & = P. \\ F_2 & = \ neg P. \\ F_ {2 n + 3} & = F_ {2 n + 1} vee F_ {2n + 2}. \\ F_ {2 n + 4} & = F_ {2 n + 3} parempoolne nool F_ {2 n + 1}. \ lõpeta {joonda *})
In (mathbf {RN}) ei tähenda ei (F_ {2 n + 1}) ega (F_ {2 n + 2}) teist; kuid (F_ {2 n}) tähendab (F_ {2 n + 1}) ja (F_ {2 n + 1}) tähendab kõiki (F_ {2 n + 3}) ja (F_ {2 n + 4}).
Fragmentidest (mathbf {IPC}) puuduvad üks või mitu loogilist ühendit piirab keelt ja muuseas ka loogikat, kuna intuitiivsed ühendused (oldand), (vee), (rightarrow), (neg) on loogiliselt sõltumatud (mathbf {IPC}) üle. Rose [1953] tõestas, et implikatsioonitu fragment (ilma (parempoolse noolega)) on realiseeritavuse osas täielik, selles mõttes, et kui iga pakkumisvalmi (E) aritmeetiline asendusnäide on ilma (parempoolse noolega) on (arv) realiseeritav, siis (E) on teoreem (mathbf {IPC}). See tulemus vastandub
Rose'i teoreem [1953]
(mathbf {IPC}) on realiseeritavuse osas puudulik.
Olgu (F) pakkumisvalem [(((neg \ neg D \ parempoolne nool D) parempoolne (neg \ neg D \ vee \ neg D)) parempoolne (neg \ neg D \ vee \ neg D)) kus (D) on ((neg P \ vee \ neg Q)) ja (P), (Q) on peaminister. Kõik (F) aritmeetilised asendusnäited on realiseeritavad (kasutades klassikalist loogikat), kuid (F) pole (mathbf {IPC}) tõestatavad.
Sellest järeldub, et (mathbf {IPC}) on (mathbf {HA}) (+) ECT jaoks aritmeetiliselt puudulik (vrd punkt 5.2).
Minimaalne loogika (mathbf {ML}) tuleneb intuitionistlikust loogikast, kustutades ex falso. Kolmogorov [1925] näitas, et see fragment sisaldab juba klassikalise loogika negatiivset tõlgendust, säilitades mõlemad kvantitaatorid, vrd. Leivant [1985]. Minimaalne loogika tõestab tõestatult negatiivsete asjaolude esinemise erijuhtumit (neg A \ parempoolne nool (A \ paremääris \ neg B)). Colacito, de Jongh ja Vardas [2017] uurivad mitmesuguseid subminimaalseid loogikaid, igaüks nõrgem kui (mathbf {ML}).
Griss vaidlustas Brouweri eituse kasutamise, vaidlustades nii vastuoluseaduse kui ka ex falso. Väärib märkimist, et eitus pole intuitiivse matemaatika jaoks tegelikult vajalik, kuna (0 = 1) on teadaolev vastuolu, nii et (neg A) saab määratleda väärtusega (A \ paremäär 0 = 1). Siis võib ex falso öelda kui (0 = 1 \ parempoolne nool A) ja vastuolu seadus on tõestatav (mathbf {H}) ülejäänud aksioomide põhjal.
Vahepealne pakkeloogika on mis tahes järjepidev pakkumisvalemite kogum, mis sisaldab kõiki (mathbf {IPC}) aksioome ja on suletud modus ponensiga ning suvaliste valemite asendamine pakkumistähtedega. Iga vahepealne pakkumisloogika sisaldub (mathbf {CPC}). Mõningaid konkreetseid pakutavaid loogikaid, millele on iseloomulik ühe või mitme klassikaliselt korrektse, kuid intuitiivselt tõestamatu aksioomiskeemi lisamine (mathbf {IPC}), on põhjalikult uuritud.
Üks lihtsamaid vahepealseid pakutavaid loogikaid on Gödel-Dummeti loogika (mathbf {LC}), mis saadakse, lisades (mathbf {IPC}) skeemi ((A \ parempoolne nool B) vee (B \ parempoolne nool A)), mis kehtib kõigil ja ainult nendel Kripke kaadritel, mille sõlmede osaline järjestus on lineaarne. Gödel [1932] kasutas järjest tugevama vaheloogika loogikat, näidates, et (mathbf {IPC}) pole lõplikku tõestabeli tõlgendust. Iga positiivse täisarvu (n) korral olgu (mathbf {G_n}) (mathbf {LC}) pluss skeem ((A_1 \ parempoolne nool A_2) vee \ ldots \ vee (A_1 \ oldand \ ldots \ oldand A_n \ parempoolne nool A_ {n + 1})). Siis kehtib (mathbf {G_n}) kõigis ja ainult nendes lineaarselt järjestatud Kripke kaadrites, milles pole rohkem kui (n) sõlme.
Jankovi loogikal (mathbf {KC}), mis lisab (mathbf {IPC}) kontrollitavuse põhimõttele (neg A \ vee \ neg \ neg A), ilmselgelt puudub disjunktsioon. vara. Kreisel-Putnami loogika (mathbf {KP}), mis saadakse, lisades (mathbf {IPC}) skeemi ((neg A \ parempoolne B \ vee C) parempoolne nool ((neg A \ parempoolne nool B) vee (neg A \ parempoolne nool C))), omab disjunktsiooni omadust, kuid ei vasta kõigile Visseri reeglitele. Vaheloogika, mis saadakse skeemi ((((neg \ neg D \ parempoolne nool D) parempoolne (D \ vee \ neg D)) parempoolne nool (neg \ neg D \ vee \ neg D)) lisamisega, mis vastab Rose'i vastanäidisele, ka (mathbf {IPC}) omab ka disjunktsiooni omadust. Iemhoff [2005] tõestas, et (mathbf {IPC}) on ainus vahepealne pakkumisloogika disjunktsiooni omadusega, mis on suletud Visseri reeglite kohaselt. Iemhoff ja Metcalfe [2009] töötasid välja ametliku arvutuse (mathbf {IPC}) üldise vastuvõetavuse ja mõne loogika vaheliseks arvestamiseks. Goudsmit [2015] on vaheloogika lubatavate reeglite põhjalik uurimine koos põhjaliku bibliograafiaga.
Vahepealsel pakutaval loogikal (mathbf {L}) öeldakse olevat piiratud kaadri omadus, kui leidub mingi piiratud kaadrite klass, kus Kripke-i kehtivad valemid vastavad täpselt (mathbf {L}) teoreemidele.. Seda omadust omavad paljud vahepealsed loogikad, sealhulgas (mathbf {LC}) ja (mathbf {KP}). Jankov [1968] kasutas lõpmatut juurdunud Kripke kaadrite jada, et tõestada, et vahepealsete loogikatega on seotud pidevus. De Jongh, Verbrugge ja Visser [2009] tõestasid, et iga vahepealne loogika (mathbf {L}) koos lõpliku kaadri omadusega on (mathbf {HA (L)}) pakutav loogika, see tähendab, kõigi valemite klass (mathbf {IPC}) keeles, mille kõigi aritmeetiliste asendusnäidete olemasolu on tõestatav (mathbf {HA}) loogilises laiendis, kasutades (mathbf {L}).
Vahepealne pakutav loogika (mathbf {L}) on struktuurilt täielik, kui iga reegli, mis on lubatav faili (mathbf {L}) jaoks, on tuletatav dokumendis (mathbf {L}), ja pärilikult struktuuriliselt täielik, kui ka iga (mathbf {L}) laiendav loogika on struktuurilt täielik. Igal vaheloogikal loogikal (mathbf {L}) on struktuuriline lõpuleviimine (mathbf { overline {L}}), mis saadakse kõigi lubatud reeglite liitmisel. (mathbf {LC}) ja (mathbf {G_n}) on pärilikult struktuurilt valmis. Ehkki (mathbf {IPC}), (mathbf {RN}) ja (mathbf {KC}) ei ole struktuuriliselt täielikud, on nende struktuurilised lõpuleviimised struktuurilt pärilikud. Nende tulemuste ja muu kohta leiate artiklist Citkin [2016, Muud Interneti ressursid].
Mõni vahepealne predikaatloogika, laiendades (mathbf {IQC}) ja suletud, on (mathbf {IQC}) (+) DNS (jaotis 4.1), (mathbf {IQC}) (+) MP (vrd punkt 5.2), (mathbf {IQC}) (+) MP (+) IP (vt punkt 4.2) ja konstantsete domeenide intuitsiooniline loogika (mathbf {CD}), mis on saadud skeemi (mathbf {IQC}) lisamisega (forall x (A \ vee B (x)) \ parempoolne nool (A \ vee \ forall x B (x))) kõigi valemite (A), (B (x)) korral, kui (x) ei esine vabas vormis (A). Mints, Olkhovikov ja Urquhart [2012, Muud Interneti ressursid] näitasid, et (mathbf {CD}) pole interpoleerimise omadust, lükkades ümber teiste autorite varem avaldatud tõendid.
6.2 Täpsemad teemad
Brouweri mõju Gödelile oli märkimisväärne, ehkki Gödelist ei saanud kunagi intuitsiooni. Gödeli intuitiivse propositsioonilise loogika tõlget modaalsesse loogikasse (1933f) [(mathbf {S4})) kirjeldatakse Gödelit käsitleva sissekande osas 2.5 ja sissejuhatavas märkuses Troelstra sissejuhatuses Gödeli kogumiku I köites [1933f] tõlkele. Töötab. Vt ka Mints [2012]. Kripke modaalloogika mudelid eelnesid intuitsioonilise loogika mudelitele.
Alternatiividena Kripke ja Bethi semantilistele intuitsioonilisele juhendus- ja predikaatloogikale võib nimetada Stone'i [1937], Tarski [1938] ja Mostowski [1948] topoloogilist tõlgendust (vrd Rasiowa ja Sikorski [1963], Rasiowa [1974]), mida laiendati Scott [1968] ja Krol [1978] intuitionistlikule analüüsile. M. Hyland [1982] määratles efektiivse topos Eff ja tõestas, et selle loogika on intuitiivne. W. Ruitenbergi intuitiivse loogika ja matemaatika semantika väga informatiivse arutelu ning G. Bezhanishvili ja W. Holliday huvitava uue vaatenurga leiate muudest Interneti ressurssidest (allpool).
Üks alternatiiv intuitiivse aritmeetika realiseerimissemantikale on Gödeli [1958] tõlge „Dialektika“, mis seob iga (L (mathbf {HA})) valemiga (B) kvantifikaatorivaba valemi (B_D) kõigi piiritletud tüüpide intuitionistliku aritmeetika keeles. Funktsiooni (B), mida nimetatakse selleks (B ^ D), „Dialektika“tõlgendus on (eksisteerib Y \ Forall x B_D (Y, x)). Kui (B) on (mathbf {HA}) suletud teoreem, siis (B_D (F, x)) on mõne mõiste (F) jaoks Gödeli teoorias tõestatav (mathbf { T}) kõrgemat tüüpi primitiivsete rekursiivsete funktsionaalide jaoks. Tõlkimine (B) - (B ^ D) nõuab valitud aksioomi (kõigil piiratud tüüpidel), MP ja IP, nii et see pole rangelt konstruktiivne; Kuid,numbriteoreetilised funktsioonid, mis on väljendatavad mõistetega (F) (mathbf {T}), on täpselt (mathbf {HA}) (ja (mathbf {PA}) provokatiivselt rekursiivsed funktsioonid). Tõlgendust laiendati Spectori analüüsile [1962]; vrd Howard [1973]. Selged ekspositsioonid ja täiendavad viited on Troelstra sissejuhatuses Dialectica originaalartikli ingliskeelse tõlke kohta Gödel [1990], Avigadis ja Fefermanis [1998] ning Ferreira [2008].
Kui (mathbf {HA}) on klassikalise aritmeetika õige osa, siis intuitiivne suhtumine matemaatilistesse objektidesse annab tulemuseks reaalarvude teooria (vt matemaatikafilosoofia intuitsioonismi käsitleva sissekande punktid 3.4–3.7), mis erinevad. klassikast. Kleene funktsioonide realiseeritavuse tõlgendus, mis on välja töötatud selleks, et tõestada jadade intuitionistliku teooria vormistamise (mathbf {FIM}) järjepidevust („intuitionistlik analüüs”), muudab aritmeetiliste valemite tõlgendust; näiteks (neg \ neg \ forall x (A (x) vee \ neg A (x))) on funktsiooni teostatav iga aritmeetilise valemi (A (x)) jaoks. Analüüsi keelesMarkovi põhimõte ja valitud loendatava aksioomi negatiivne tõlge on paljude mitteintuitsionistlike põhimõtete hulgas, mis on funktsionaalselt realiseeritavad (klassikaliste argumentide järgi) ja seega kooskõlas põhimõttega (mathbf {FIM}); vrd Kleene [1965], Vesley [1972] ja Moschovakis [2003].
Loogikud ja arvutiteadlased on välja töötanud ja uurinud mitmesuguste ametlike süsteemide konkreetset ja abstraktset realiseeritavust. vrd Troelstra [1998] ja van Oosten [2002] ja [2008]. Põhimõistete variatsioonid on eriti kasulikud intuitiivsel loogikal põhinevate teooriate mitteloogiliste aksioomide suhtelise järjepidevuse ja suhtelise sõltumatuse kindlakstegemiseks; mõned näited on Moschovakis [1971], Lifschitz [1979] ning Rathjeni [2006, 2012] ja Cheni [2012] väljatöötatud konstruktiivsete ja intuitionistlike kogumiteooriate realiseeritavuse kontseptsioonid. Varaste abstraktsete teostatavusmõistete hulka kuuluvad Kleene'i [1962, 1963] ja Aczeli [1968] ning Läuchli [1970] kaldkriipsud. Kohlenbach, Avigad ja teised on välja töötanud klassikalise matemaatika osade realiseeritavuse tõlgendused.
Artemovi õigustusloogika on intuitiivsete ühenduste ja kvantifikaatorite BHK-seletuse alternatiivne tõlgendus koos (idealiseeritud) tõenditega, mis mängivad osa objektide realiseerimisest. Vt ka Artemov ja Iemhoff [2007].
Teine intuitiivistliku loogika uurimistöö puudutab Brouweri väga vastuolulist “subjekti vastanäidete loomist” klassikalise analüüsi põhimõtetele (näiteks Markovi põhimõte), mida Kleene ja (mathbf {FIM}) teooria põhjal ümber lükata ei saa. Vesley [1965]. Nõrgendades Kleene kuju Brouweri pideva valiku põhimõttest ja lisades aksioomi, mida ta nimetas Kripke skeemiks (KP), suutis Myhill vormistada loovad subjektiargumendid. KP on vastuolus (mathbf {FIM}), kuid Vesley [1970] leidis alternatiivse põhimõtte (Vesley's Schema VS), mille saab järjekindlalt lisada ka (mathbf {FIM}) ja hõlmab kõiki vastanäiteid, mille jaoks Brouwer nõudis loovat subjekti. Krol [1978] ja Scowcroft andsid topoloogilise järjepidevuse tõestused intuitsioonilise analüüsi jaoks Kripke skeemi ja nõrga järjepidevuse abil.
6.3 Soovituslik lugemine
LEJ Brouwerit käsitlevas kirjes käsitletakse Brouweri filosoofiat ja matemaatikat koos oma elu kronoloogia ja valitud loetelu publikatsioonidega, sealhulgas tõlked ja teisesed allikad. Parim viis rohkem teada saada on lugeda mõnda originaaltööd. Brouweri doktoriväitekirja ingliskeelsed tõlked ja muud algselt hollandi keeles ilmunud artiklid koos paljude saksakeelsete artiklitega on saadaval LEY Brouwer: Collected Works [1975], toimetaja Heyting. Benacerrafi ja Putnami oluline allikraamat sisaldab Brouwerit [1912] (ingliskeelses tõlkes), Brouwerit [1949] ja Dummettit [1975]. Mancosu [1998] pakub paljude Brouweri, Heytingi, Glivenko ja Kolmogorovi põhiartiklite ingliskeelseid tõlkeid W. van Stigti valgustava sissejuhatava materjaliga, mille [1990] on veel üks väärtuslik ressurss.
Heytingi klassika [1956] kolmas trükk [1971] on atraktiivne sissejuhatus intuitionistlikku filosoofiasse, loogikasse ja matemaatilisse praktikasse. Brouweri Nachlassi redigeerimise ja avaldamise valmimisprojekti osana pakub van Dalen [1981] Brouweri enda intuitsioonilisest filosoofiast tervikliku ülevaate. Brouweri [1927] ingliskeelne tõlge van Heijenoorti [1969] (koos Parsonsi peene sissejuhatusega) on endiselt hädavajalik viide Brouweri jätkuvuse teooriale. Veldman [1990] ja [2005] on autentsed kaasaegsed näited traditsioonilisest intuitionistlikust matemaatilisest praktikast. Troelstra [1991] seab intuitiivse loogika oma ajaloolisesse konteksti kui konstruktiivse matemaatika ühiseks aluseks 20. sajandil. Bezhanishvili ja de Jongh [2005,Muud Interneti-ressursid] sisaldab intuitiivse loogika hiljutisi arenguid.
Kleene ja Vesley [1965] annab intuitionistliku analüüsi hoolika aksiomaatilise käsitluse, tõestuse selle järjepidevuse kohta klassikaliselt korrektse alateooria osas ning Brouweri teooria laiendatud rakenduse reaalarvude generaatorite kohta. Kleene'i [1969] vormistab osaliste rekursiivsete funktsionaalide teooria, võimaldades [1965] kasutatud funktsiooni realiseeritavuse tõlgenduse ja sellega seotud q-realiseeritavuse tõlgenduse täpset vormistamist, mis annab Kiriku-Kleene'i reegli intuitiivseks analüüsiks.
Troelstra [1973], Beesoni [1985] ning Troelstra ja van Daleni [1988] (koos parandustega) paistavad intuitiivsete ja pool-intuitionistlike formaalteooriate kõige põhjalikumate uurimustena, kasutades nii konstruktiivseid kui ka klassikalisi meetodeid, koos kasulike bibliograafiatega. Troelstra ja Schwichtenberg [2000] esitavad paralleelselt klassikalise, intuitionistliku ja minimaalse loogika tõestusteooria, keskendudes järjestikustele süsteemidele. Troelstra [1998] pakub valemitüüpidena (Kleene ja Aczel) kaldkriipsuga tõlgendusi aluse- ja predikaatloogika jaoks, aga ka abstraktse ja konkreetse realiseeritavuse paljude rakenduste jaoks. Martin-Löfi konstruktiivne tüüpi teooria [1984] (vrd konstruktiivse matemaatika sissejuhatuse punkt 3.4) pakub veel ühe üldise raamistiku, milles intuitiivne mõttekäik jätkub.
Bibliograafia
Aczel, P., 1968, “Küllastunud intuitionistlikud teooriad”, HA Schmidt, K. Schütte ja H.-J. Thiele (toim.), Kaastöö matemaatilisse loogikasse, Amsterdam: Põhja-Holland: 1–11.
Artemov, S. ja Iemhoff, R., 2007, “Tõendite põhiline intuitionistlik loogika”, Journal of Symbol Logic, 72: 439–451.
Avigad, J. ja Feferman, S., 1998, “Gödeli funktsionaalne (“Dialectica”) tõlgendus”, Busi V peatükk (toim) 1998: 337–405.
Bar-Hillel, Y. (toim.), 1965, loogika, metoodika ja teadusfilosoofia, Amsterdam: Põhja-Holland.
Beeson, MJ, 1985, Konstruktiivse matemaatika alused, Berliin: Springer.
Benacerraf, P. ja Hilary Putnam (toim.), 1983, Matemaatikafilosoofia: valitud lugemised, 2. trükk, Cambridge: Cambridge University Press.
Beth, EW, 1956, “Intuitsioonilise loogika semantiline konstrueerimine”, Koninklijke Nederlandse Akad. von Wettenscappen, 19 (11): 357–388.
–––, 1912, „Intuitsionism ja formalism”, A. Dresdeni tõlge, American Mathematical Society bülletään, 20 (1913): 81–96, kordustrükk trükistes Benacerraf ja Putnam (toim.) 1983: 77–89; kordustrükk ka ajakirjas Heyting (toim.) 1975: 123–138.
–––, 1923, [1954], „Välistatud keskpunkti põhimõtte olulisusest matemaatikas, eriti funktsiooniteoorias”, „Lisad ja parandused” ning „Lisad ja parandused”, ingliskeelne tõlge van Heijenoortis (toim.) 1967: 334–345.
–––, 1923C, “Intuitionistische Zerlegung matemaatik Grundbegriffe”, Jahresbericht der Deutschen Mathematiker-Vereinigung, 33 (1925): 251–256; kordustrükk ajakirjas Heyting (toim.) 1975, 275–280.
–––, 1927, „Intuitionistlikud mõtisklused formalismi üle”, algselt avaldatud 1927, ingliskeelne tõlge van Heijenoortis (toim) 1967: 490–492.
–––, 1948, „Teadvus, filosoofia ja matemaatika”, algselt avaldatud (1948), kordustrükk trükistes Benacerraf ja Putnam (toim.) 1983: 90–96.
Burr, W., 2004, “Intuitionistlik aritmeetiline hierarhia”, J. van Eijck, V. van Oostrom ja A. Visser (toim), loogikakollokvium '99 (loengu märkused logikas 17), Wellesley, MA: ASL ja AK Peters, 51–59.
Buss, S. (toim), 1998, Proof Theory käsiraamat, Amsterdam ja New York: Elsevier.
Chen, RM. ja Rathjen, M., 2012, “Lifschitzi realiseeritavus intuitiivse Zermelo-Fraenkeli komplekti teooria jaoks”, Archive for Mathematical Logic, 51: 789–818.
Colacito, A., de Jongh, D. ja Vargas, A., 2017, “Subminimaalne eitus”, pehme arvuti, 21: 165–164.
Crossley, J. ja MAE Dummett (toim.), 1965, Formaalsed süsteemid ja rekursiivsed funktsioonid, Amsterdam: Põhja-Hollandi kirjastus.
van Dalen, D. (toim.), 1981, Brouweri Cambridge'i loengud intuitsiooni kohta, Cambridge: Cambridge University Press.
Dummett, M., 1975, “Intuitionistliku loogika filosoofiline alus”, algselt avaldatud (1975), kordustrükk Benacerrafis ja Putnamis (toim.) 1983: 97–129.
Dyson, V. ja Kreisel, G., 1961, Bethi intuitiivse loogika semantilise konstruktsiooni analüüs, tehniline aruanne nr 3, Stanford: Stanfordi ülikooli rakendusmatemaatika ja statistikalabor.
Friedman, H., 1975, “Disjunktsiooni omadus tähendab numbrilist eksistentsi omadust”, National Science Science, 72: 2877–2878, Proceedings of the National Academy of Science.
Gentzen, G., 1934–5, “Untersuchungen Über das logische Schliessen”, Mathematische Zeitschrift, 39: 176–210, 405–431.
Glivenko, V., 1929, “Sur quelques points de la logique de M. Brouwer,” Académie Royale de Belgique, Bulletins de la classe des sciences, 5 (15): 183–188.
Gödel, K., 1932, “Zum intuitionistischen Aussagenkalkül”, Anzeiger der Akademie der Wissenschaften Wienis, 69: 65–66. Paljundatud ja tõlgitud sissejuhatava märkusega AS Troelstra poolt Gödel 1986: 222–225.
–––, 1933e, “Zur intuitionistischen Arithmetik und Zahlentheorie”, Ergebnisse eines matemaatikakollokviumid, 4: 34–38.
–––, 1933f, “Eine Interpretation des intuitionistischen Aussagenkalküls”, taasesitanud ja tõlkinud sissejuhatava märkusega AS Troelstra Gödel 1986: 296–304.
––– 1958, “Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes”, Dialectica, 12: 280–287. Paljundatud ingliskeelse tõlkega Gödel 1990: 241–251.
–––, 1986, Collected Works, kd. Mina, S. Feferman jt. (toim), Oxford: Oxford University Press.
–––, 1990, Collected Works, kd. II, S. Feferman jt. (toim), Oxford: Oxford University Press.
Goudsmit, JP, 2015, Intuitsionistlikud reeglid: vaheloogika lubatavad reeglid, Ph. D. väitekiri, Utrechti ülikool.
Harrop R., 1960, “Mis puutub tüüpide (A \ parempoolne nool B \ vee C, A \ paremääris (Ex) B (x)) valemitesse intuitsioonistlikes formaalsetes süsteemides,” Journal of Symbolic Logic, 25: 27–32.
van Heijenoort, J. (toim.), 1967, Fregest Gödelini: Mattemaatilise loogika lähtetekst 1879–1931, Cambridge, MA: Harvard University Press.
Heyting, A., 1930, “Die formalen Regeln der intuitionistischen Logik”, kolmes osas, Sitzungsberichte der preussischen Akademie der Wissenschaften: 42–71, 158–169. I osa ingliskeelne tõlge Mancosus 1998: 311–327.
Hyland, JME, 1982, “Efektiivne topos”, Troelstra ja van Dalen (toim) 1982: 165–216.
Iemhoff, R., 2001, “Intuitionistliku propositsiooniloogika lubatavate reeglite kohta”, Journal of Symbolic Logic, 66: 281–294.
–––, 2005, “Vahepealne loogika ja Visseri reeglid”, Notre Dame Journal of Formal Logic, 46: 65–81.
Iemhoff, R. ja Metcalfe, G., 2009, “Lubatud reeglite tõestusteooria”, Annals of Pure and Applied Logic, 159: 171–186.
Jankov, VA, 1968, “Tugevalt sõltumatute superintuitsionistlike ettepanekute arvutuskulude jada konstrueerimine”, Nõukogude matemaatika. Doklady, 9: 801–807.
Jerabek, E., 2008, “Lubatavate reeglite iseseisvad alused”, IGPL Logic Journal, 16: 249–267.
de Jongh, DHJ, 1970, “Intuitsionistliku propositsioonilise kalkulatsiooni maksimaalsus Heytingi aritmeetika suhtes”, Journal of Symbolic Logic, 6: 606.
de Jongh, DHJ ja Smorynski, C., 1976, “Kripke mudelid ja liikide intuitiivne teooria”, Annals of Mathematical Logic, 9: 157–186.
de Jongh, D., Verbrugge, R. ja Visser, A., 2011, “Vahepealne loogika ja de Jonghi vara”, Matemaatilise loogika arhiiv, 50: 197–213.
Kino, A., Myhill, J. ja Vesley, RE (toim.), 1970, intuitsioon ja tõestusteooria: Buffalo suvekonverentsi toimumised, NY, 1968, Amsterdam: Põhja-Holland.
Kripke, SA, 1965, “Intuitionistliku loogika semantiline analüüs”, J. Crossley ja MAE Dummett (toim) 1965: 92–130.
Krol, M., 1978, “Intuitionistliku analüüsi topoloogiline mudel Kripke skeemiga”, Zeitschrift für Math. Logik und Grundlagen der Math., 24: 427–436.
Leivant, D., 1979, “Intuitionistliku loogika maksimum”, Mathematical Center Tracts 73, Mathematisch Centrum, Amsterdam.
––– 1985, “Süntaktilised tõlked ja provokatiivselt rekursiivsed funktsioonid”, Journal of Symbolic Logic, 50: 682–688.
Läuchli, H., 1970, “Kestlik idee realiseeritavusest, mille jaoks intuitiivne predikaatarvutus on täielik”, A. Kino jt. (toim) 1965: 227–234.
Lifschitz, V., 1979, “CT (_ 0) on tugevam kui CT (_ 0)!”, Proceedings of the American Mathematical Society, 73 (1): 101–106.
Mancosu, P., 1998, Brouwerist Hilbertini: Arutelu matemaatika aluste üle 1920. aastatel, New York ja Oxford: Oxford University Press.
Martin-Löf, P., 1984, Intuitionistlik teooria, Giovanni Sambini märkused Padovas peetud loengusarjast, juuni 1980, Napoli: Bibliopolis.
Mints, G., 2012, “Gödeli – Tarski tõlked intuitiivsete ideevalemite valemitest”, Õige arutluskäik (arvutiteaduse loengumärkused 7265), E. Erdem jt. (toim), Dordrecht: Springer-Verlag: 487–491.
Moschovakis, JR, 1971, “Kas ei saa olla mitterekursiivseid funktsioone?”, Journal of Symbolic Logic, 36: 309–315.
–––, 2003, „Klassikalised ja konstruktiivsed hierarhiad laiendatud intuitionistlikus analüüsis“, Journal of Symbolic Logic, 68: 1015–1043.
–––, 2009, „Brouweri ja Heytingi loogika”, loogikas Russellist kirikuni (loogika ajaloo käsiraamat, 5. köide), J. Woods ja D. Gabbay (toim.), Amsterdam: Elsevier: 77 –125.
–––, 2017, “Intuitionistlik analüüs ja aja lõpp”, Sümboolse loogika bülletään, 23: 279–295.
Nelson, D., 1947, “Rekursiivsed funktsioonid ja intuitsiooniline arvuteooria”, American Mathematical Society, 61: 307–368.
Nishimura, I., 1960, “Ühe muutuja valemitest intuitionistlikus propositsioonilises kalkulatsioonis”, Journal of Symbolic Logic, 25: 327–331.
van Oosten, J., 1991, “De Jonghi teoreemi semantiline tõestus”, Archives for Mathematical Logic, 31: 105–114.
–––, 2002, “Realiseeritavus: ajalooline essee”, Matemaatilised struktuurid arvutiteaduses, 12: 239–263.
–––, 2008, Teostatavus: sissejuhatus selle kategooriasse, Amsterdam: Elsevier.
Plisko, VE, 1992, “Teatud konstruktiivse loogika aritmeetilise keerukuse kohta”, Mathematical Notes, (1993): 701–709. Tõlgitud väljaandest Matematicheskie Zametki, 52 (1992): 94–104.
Rasiowa, H., 1974, mitteklassikalise loogika algebraline kirjeldus, Amsterdam: Põhja-Holland.
Rasiowa, H. ja Sikorski, R., 1963, Metamaatika matemaatika, Varssavi: Panstwowe Wydawnictwo Naukowe.
Rathjen, M., 2006, “Konstruktiivse Zermelo-Fraenkeli komplekti teooria realiseeritavus”, ajakirjas Logic Colloquium 2003 (loengu märkused logikas 24), J. Väänänen jt. (toim), AK Peters 2006: 282–314.
–––, 2012, „Nõrgast kuni tugeva eksistentsi omaduseni“, Annals of Pure and Applied Logic, 163: 1400–1418.
Rose, GF, 1953, “Propositsionaalne arvutus ja realiseeritavus”, American Mathematical Society, 75: 1–19.
Rybakov, V., 1997, Loogiliste järelduste reeglite lubatavus, Amsterdam: Elsevier.
Smorynski, CA, 1973, “Kripke mudelite rakendused”, Troelstra (toim.) 1973: 324–391.
Spector, C., 1962, “Tõenäoliselt rekursiivsed analüüsi funktsionaalid: analüüsi järjepidevuse tõend, laiendades praeguses intuitsioonistlikus matemaatikas sõnastatud põhimõtteid”. Rekursiivne funktsioonide teooria: puhta matemaatika sümpoosionide toimingud, 5. köide, JCE Dekker (toim.), Providence, RI: American Mathematical Society, 1–27.
van Stigt, WP, 1990, Brouweri intuitsioon, Amsterdam: Põhja-Holland.
Stone, MH, 1937, “Jaotusvõrkude ja Brouweri loogika topoloogiline kujutis”, Casopis Pest. Mat. Fys., 67: 1–25.
Tarski, A., 1938, “Der Aussagenkalkül und die Topologie”, Fundamenta Mathematicae, 31: 103–104.
Troelstra, AS, 1991, “Konstruktivismi ajalugu XX sajandil”, ITLI eelväljaannete seeria ML – 1991–05, Amsterdam. Lõplik versioon matemaatika komplekti teooriast, aritmeetikast ja alustest (loengu märkused loogikas 36), J. Kenney ja R. Kossak (toim), Symbolic Logic Association, Ithaca, NY, 2011: 150–179.
–––, 1998, „Realiseeritavus“, Busi VI peatükk (toim.), 1998: 407–473.
–––, 1958. ja 1972. aasta sissejuhatav märkus, Gödel, 1990: 217–241.
Troelstra, AS (toim.), 1973, intuitsioonilise aritmeetika ja analüüsi metameetriline uurimine (loengu märkused matemaatikas 344), Berliin: Springer-Verlag. Parandused ja täiendused on saadaval redaktoris.
Troelstra, AS ja Schwichtenberg, H., 2000, Basic Proof Theory (Cambridge Tracts in Theoretical Computer Science: Volume 43), 2nd edition, Cambridge: Cambridge University Press.
Troelstra, AS ja van Dalen, D., 1988, Konstruktivism matemaatikas: sissejuhatus, 2 köidet, Amsterdam: Põhja-Hollandi kirjastus. [Vt ka parandusi muudes Interneti-ressurssides.]
Troelstra, AS ja van Dalen, D. (toim.), 1982, The LEJ Brouwer Centenary Symposium, Amsterdam: Põhja-Hollandi kirjastus.
Veldman, W., 1976, “Intuitionistliku predikaatloogika intuitiivse täielikkuse teoreem”, Journal of Symbolic Logic, 41: 159–166.
––– 1990, „Petitsioonide kirjeldava intuitiivse kogumiteooria ülevaade“, PP Petkov (toim), Matemaatiline loogika, Heytingi konverentsi toimetised, New York ja London: Plenum Press, 155–174.
–––, 2005, “Kaks lihtsat komplekti, mis ei ole positiivselt Borel,” Annals of Pure and Applied Logic, 135: 151–209.
Vesley, RE, 1972, “Valikujärjestused ja Markovi põhimõte”, Compositio Mathematica, 24: 33–53.
–––, 1970, „Kripke skeemi maitsev alternatiiv”, A. Kino jt. (toim) 1970: 197ff.
Visser, A., 1999, “Reeglid ja aritmeetika”, Notre Dame Journal of Formal Logic, 40: 116–140.
–––, 2002, “((Sigma ^ {0} _1) lausete asendamised: uurimised intuitiivse propositsioonilise loogika ja intuitionistliku aritmeetika vahel”, Annals of Pure and Applied Logic, 114: 227–271.
