Intuitionistická Logika

2023 Autor: Noah Black | [email protected]. Naposledy zmenené: 2023-08-25 04:39

Vstupná navigácia

• Obsah vstupu
• Bibliografia
• Akademické nástroje
• Náhľad priateľov PDF
• Informácie o autorovi a citácii
• Späť na začiatok

Intuitionistická logika

Prvýkrát uverejnené 1. septembra 1999; podstatná revízia Ut 4. september 2018

Intuitionistická logika zahŕňa všeobecné princípy logického zdôvodnenia, ktoré logici abstrahovali od intuicionálnej matematiky, ako ich vyvinul LEJ Brouwer začínajúci v [1907] a [1908]. Pretože tieto princípy platia aj pre ruskú rekurzívnu matematiku a konštruktívnu analýzu E. Bishopa a jeho nasledovníkov, intuitívna logika sa môže považovať za logický základ konštruktívnej matematiky. Hoci intuicionálna analýza je v rozpore s klasickou analýzou, intuicionálna Heytingova aritmetika je podsystémom klasickej Peano aritmetiky. Z toho vyplýva, že intuitionistická výroková logika je správnym subsystémom klasickej výrokovej logiky a čistá intuitionistická predikátová logika je správnym subsystémom čistej klasickej predikátovej logiky.

Filozoficky sa intuicionizmus odlišuje od logicizmu tým, že logiku považuje skôr za súčasť matematiky ako za základ matematiky; od finitizmuumožnením konštruktívneho zdôvodnenia nespočetných štruktúr (napr. indukcia monotónnej tyčinky na strome potenciálne nekonečných sekvencií prirodzených čísel); az platonizmu pozeraním matematických objektov na mentálne konštrukty bez existencie nezávislej ideálnej existencie. Hilbertov formalistický program, ktorý ospravedlňuje klasickú matematiku tým, že ju redukuje na formálny systém, ktorého konzistentnosť by sa mala stanoviť pomocou finitistických (teda konštruktívnych) prostriedkov, bol najmocnejším súčasným rivalom rozvíjajúceho sa intuitizmu Brouwera. Vo svojej eseji Intuitionism and Formalism Brouwer z roku 1912 správne predpovedal, že akýkoľvek pokus dokázať konzistentnosť úplnej indukcie v prirodzených číslach povedie k začarovanému kruhu.

Brouwer sám odmietol formalizmus, ale pripustil potenciálnu užitočnosť formulovania všeobecných logických princípov vyjadrujúcich intuicionisticky správne konštrukcie, ako napríklad modus ponens. Formálne systémy pre intuicionálne výrokové a predikátové logiky a aritmetiky boli úplne vyvinuté Heytingom [1930], Gentzenom [1935] a Kleenom [1952]. Gödel [1933] preukázal rovnováhu intuicionálnych a klasických teórií. Beth [1956] a Kripke [1965] poskytli sémantiku, vzhľadom na ktorú je intuicionistická logika správna a úplná, hoci dôkazy úplnosti pre intuicionálnu predikátovú logiku vyžadujú určité klasické zdôvodnenie.

• 1. Odmietnutie terc. Non datur

• 2. Intuionistická logika predikátu prvého poriadku

  • 2.1 Formálne systémy (mathbf {H – IPC}) a (mathbf {H – IQC})
  • 2.2 Alternatívne formalizmy a teória o odpočte
• 3. Intuitionistická teória čísel (heyting aritmetika) (mathbf {HA})

• 4. Základná teória korektúry

  • 4.1 Preložiť klasickú do intuicionálnej logiky
  • 4.2 Prípustné pravidlá intuicionálnej logiky a aritmetiky

• 5. Základná sémantika

  • 5.1 Kripkeho sémantika pre intuicionálnu logiku
  • 5.2 Sémantika uskutočniteľnosti pre aritmetiku heytingu

• 6. Ďalšie témy a ďalšie čítanie

  • 6.1 Subintuitionistická a stredná logika
  • 6.2 Pokročilé témy
  • 6.3 Odporúčané čítanie
• Bibliografia
• Akademické nástroje
• Ďalšie internetové zdroje
• Súvisiace záznamy

1. Odmietnutie terc. Non datur

Intuitionistickú logiku možno stručne opísať ako klasickú logiku bez aristotelského zákona vylúčeného stredu:

(tag {LEM} A / vee / neg A)

alebo klasický zákon o zamedzení dvojitého vylúčenia:

(tag {DNE} neg / neg A / rightarrow A)

ale so zákonom o protirečení:

[(A / rightarrow B) rightarrow ((A / rightarrow / neg B) rightarrow / neg A))

a ex falso sequitur quodlibet:

(neg A / rightarrow (A / rightarrow B).)

Brouwer [1908] poznamenal, že LEM bol zbavený konečných situácií, a potom bol bez odôvodnenia rozšírený na vyhlásenia o nekonečných zbierkach. Napríklad nechajme (x, y) na prirodzené čísla (0, 1, 2, / ldots) a necháme (B (y)) skrátiť ((primepred (y) oldand) primepred (y + 2))), kde (primepred (y)) vyjadruje „(y) je prvočíslo.“Potom (forall y (B (y) vee / neg B (y))) drží intuicionálne aj klasicky, pretože na určenie, či je alebo nie je prirodzené číslo prvoradé, potrebujeme iba skontrolovať, či je, alebo nie) má deliteľa medzi sebou a 1.

Ale ak (A (x)) je skratka (existuje y (y / gt x / oldand B (y))), potom, aby sa uplatnilo (forall x (A (x) vee / neg) A (x))) intuitívne by sme potrebovali účinnú metódu (porovnaj Cirkev-Turingovu prácu), aby sme určili, či existuje dvojica prvočísel, väčšia ako ľubovoľné prirodzené číslo (x), a zatiaľ takáto metóda nie je známa. Zrejmou poloefektívnou metódou je zostavenie zoznamu párov prvočísel pomocou rafinácie Eratosthenesovho sita (generovanie prirodzených čísel jeden po druhom a vyčiarknutie každého čísla (y), ktoré nespĺňa požiadavky (B (y))), a ak existuje dvojica prvočísel, ktorá je väčšia ako (x), táto metóda nakoniec nájde prvú. Avšak (forall x A (x)) vyjadruje dohad o dvojakej prime, ktorý zatiaľ nebol dokázaný alebo vyvrátený,takže v súčasnom stave našich vedomostí nemôžeme uplatniť ani (forall x (A (x) vee / neg A (x))) ani (forall x A (x) vee / neg / forall x A (x)).

Možno namietať, že tieto príklady závisia od skutočnosti, že dohad o dvojitých primeloch ešte nebol vyriešený. Niekoľko pôvodných Brouwerových „protikladov“záviselo od problémov (ako je napríklad Fermatova posledná veta), ktoré sa odvtedy vyriešili. Ale Brouwerovi bola všeobecná LEM a priori rovnocenná s domnienkou, že každý matematický problém má riešenie - predpoklad, ktorý odmietol, pričom predpokladal Gödelovu teóriu neúplnosti o štvrtinu storočia.

Odmietnutie LEM má ďalekosiahle následky. Na jednej strane,

• Intuitionistically, redukctio ad absurdum dokazuje iba negatívne výroky, pretože (neg / neg A / rightarrow A) všeobecne neplatí. (Ak by sa tak stalo, LEM by nasledoval modus ponens z intuitionisticky preukázateľného (neg / neg (A / vee / neg A)).)
• Intuitionistická výroková logika nemá konečný výklad tabuľky pravdy. Medzi intuicionálnou a klasickou logikou existuje nekonečne veľa rôznych axiomatických systémov.
• Nie každý výrokový vzorec má intuicionálne ekvivalentný disjunkčný alebo spojivý normálny tvar, ktorý je postavený na prvotných vzorcoch a ich negáciách pomocou iba (vee) a (oldand).
• Nie každý predikátový vzorec má intuicionálne ekvivalentnú normálnu formu predexu so všetkými kvantifikátormi na prednej strane.
• Zatiaľ čo (forall x / neg / neg (A (x) vee / neg A (x))) je veta intuitívnej predikátovej logiky, (neg / neg / forall x (A (x) vee) neg A (x))) nie je; takže (neg / forall x (A (x) vee / neg A (x))) je v súlade s intuicionálnou predikátovou logikou.

Na druhej strane,

• Každý intuicionistický dôkaz o uzavretom tvare (A / vee B) sa dá efektívne transformovať na intuicionistický dôkaz o (A) alebo intuicionálny dôkaz o (B) a podobne pre uzavreté existenciálne tvrdenia.
• Intuitionistická výroková logika je efektívne rozhodujúca v tom zmysle, že konečný konštruktívny proces sa uplatňuje jednotne na každý výrokový vzorec, a to buď predložením intuitívneho dôkazu vzorca alebo preukázaním, že takýto dôkaz nemôže existovať.
• Negatívny fragment intuicionálnej logiky (bez (vee) alebo (existuje)) obsahuje verný preklad klasickej logiky a podobne pre intuicionálnu a klasickú aritmetiku.
• Intuitionistickú aritmetiku možno dôsledne rozšíriť o axiómy, ktoré sú v rozpore s klasickou aritmetikou, čo umožňuje formálne štúdium rekurzívnej matematiky.
• Brouwerova kontroverzná intuicionistická analýza, ktorá je v rozpore s LEM, môže byť formalizovaná a preukázaná konzistentná v porovnaní s klasicky a intuitívne správnym podtypom.

2. Intuionistická logika predikátu prvého poriadku

Formalizovaná intuicionistická logika je prirodzene motivovaná neformálnym Brouwer-Heyting-Kolmogorovovým vysvetlením intuicionálnej pravdy, načrtnutým v záznamoch o intuicionizme vo filozofii matematiky a vývoji intuicionistickej logiky. Konštruktívna nezávislosť logických operácií (oldand, / vee, / rightarrow, / neg, / forall, / existuje) je v kontraste s klasickou situáciou, kde napr. (A / vee B) je ekvivalentné (neg (neg A / oldand / neg B)) a (existuje xA (x)) je ekvivalentné (neg / forall x / neg A (x)). Z hľadiska BHK veta formulára (A / vee B) tvrdí, že bol buď vyhotovený dôkaz o (A) alebo dôkaz o (B);zatiaľ čo (neg (neg (neg A / oldand / neg B)) tvrdí, že bol skonštruovaný algoritmus, ktorý by efektívne konvertoval ľubovoľnú dvojicu konštrukcií preukazujúcich (neg A) a (neg B), do dôkazu známeho rozporu.

2.1 Formálne systémy (mathbf {H – IPC}) a (mathbf {H – IQC})

Nasleduje hilberský formalizmus (mathbf {H – IQC}) od Kleene [1952] (porovnaj Troelstra a van Dalen [1988]) pre intuicionálnu predikátovú logiku prvého poriadku. Jazyk (L) (mathbf {H – IQC}) obsahuje predikátové písmená (P, Q (.), / Ldots) všetkých aritéz a jednotlivých premenných (x, y, z, / ldots) (s alebo bez predplatného (1, 2, / ldots))), ako aj symboly (oldand, / vee, / rightarrow, / neg, / forall, / existuje) pre logické spoje a kvantifikátory a zátvorky (,). Atómové (alebo prvotné) vzorce (L) sú výrazy ako (P, Q (x), R (x, y, x)), kde (P, Q ({.}), R ({.} {.} {.})) sú (0) - ary, (1) - ary a (3) - ary predikátové písmená; to znamená, že výsledok vyplnenia každého medzery v predikátovom liste individuálnym variabilným symbolom je prvotný vzorec.(Dobre formované) vzorce (L) sú definované indukčne nasledovne.

• Každý atómový vzorec je vzorec.
• Ak (A) a (B) sú vzorce, platí to tiež ((A / oldand B), (A / vee B), (A / rightarrow B)) a (neg A).
• Ak (A) je vzorec a (x) je premenná, potom (forall xA) a (existuje xA) sú vzorce.

Všeobecne používame (A, B, C) ako metavariable pre dobre formované vzorce a (x, y, z) ako metavariables pre jednotlivé premenné. Pri predpokladaných aplikáciách (napríklad na intuicionálnu aritmetiku) používame (s, t) ako metavariabily termínov; v prípade čistej predikátovej logiky sú pojmy jednoducho jednotlivé premenné. Výskyt premennej (x) vo vzorci (A) je viazaný, ak je v rámci kvantifikátora (forall x) alebo (existuje x), inak je voľný. Intuitionisticky tak klasicky, ((A / leftrightarrow B)) skratky (((A / rightarrow B) oldand (B / rightarrow A))) a zátvorky budú vynechané, ak to nespôsobí zámenu.

Existujú tri pravidlá dedukcie:

Modus Ponens

Z (A) a (A / rightarrow B), uzavrieť (B).

(forall) - Úvod

Z (C / rightarrow A (x)), kde (x) je premenná, ktorá sa nevyskytuje bezplatne v (C), uzavrite (C / rightarrow / forall x A (x)).

(existuje) - Eliminácia

z (A (x) rightarrow C), kde (x) je premenná, ktorá sa nevyskytuje bezplatne v (C), uzavrite (existuje x A (x) rightarrow C).

Axiómy sú všetky vzorce nasledujúcich foriem, kde v posledných dvoch schémach je podformula (A (t)) výsledkom nahradenia výskytu výrazu (t) za každý voľný výskyt (x)) v (A (x)) a žiadna premenná voľná v (t) nie je viazaná v (A (t)) v dôsledku substitúcie.

(begin {array} {l} A / rightarrow (B / rightarrow A) (A / rightarrow B) rightarrow ((A / rightarrow (B / rightarrow C)) rightarrow (A / rightarrow C)) / A / rightarrow (B / rightarrow (A / oldand B)) (A / oldand B) rightarrow A \(A / oldand B) rightarrow B \\ A / rightarrow (A / vee B) / B / rightarrow (A / vee B) (A / rightarrow C) rightarrow ((B / rightarrow C) rightarrow ((A / vee B) rightarrow C)) (A / rightarrow B) rightarrow ((A / rightarrow / neg B) rightarrow / neg A) / \ neg A / rightarrow (A / rightarrow B) / \ forall xA (x) rightarrow A (t) / A (t) rightarrow / existuje xA (x) end {array})

Dôkazom je akákoľvek konečná postupnosť vzorcov, z ktorých každá je axiómom alebo bezprostredným dôsledkom (jedného alebo dvoch) predchádzajúcich vzorcov postupnosti. Akýkoľvek dôkaz sa považuje za dôkaz jeho posledného vzorca, ktorý sa nazýva veta alebo preukázateľný vzorec intuitívnej predikátovej logiky prvého poriadku. Odvodenie vzorca (E) zo súboru (F) predpokladov je akákoľvek postupnosť vzorcov, z ktorých každá patrí do (F) alebo je axiómom alebo bezprostredným dôsledkom, z toho odvodzovacím pravidlom, z predchádzajúcich vzorcov sekvencie tak, že (E) je posledný vzorec sekvencie. Ak takáto derivácia existuje, hovoríme, že (E) je odvoditeľné z (F).

Intuitionistická výroková logika (mathbf {H – IPC}) je subsystém (mathbf {H – IQC}), ktorý vznikne, keď je jazyk obmedzený na vzorce zostavené z výrokových písmen (P, Q, R, / ldots) pomocou výrokových spojív (oldand, / vee, / rightarrow) a (neg) a použijú sa iba výrokové postuláty. Posledné dve dedukčné pravidlá a posledné dve axiómové schémy teda chýbajú v propozičnom subsystéme.

Ak v danom zozname axiómových schém pre intuicionálnu výrokovú logiku alebo predikátovú logiku prvého poriadku zákon vyjadrujúci ex falso sequitur quodlibet:

(neg A / rightarrow (A / rightarrow B))

sa nahrádza klasickým zákonom o zamedzení dvojitého vylúčenia DNE:

(neg / neg A / rightarrow A)

(alebo rovnocenne, ak intuicionistický zákon o zavedení negácie:

[(A / rightarrow B) rightarrow ((A / rightarrow / neg B) rightarrow / neg A))

je nahradený LEM), formálnym systémom (mathbf {H – CPC}) pre klasickú výrokovú logiku alebo (mathbf {H – CQC}) pre klasické predikátové logické výsledky. Pretože ex falso a zákon kontradikcie sú klasické vety, intuicionálna logika je obsiahnutá v klasickej logike. V istom zmysle je klasická logika obsiahnutá aj v intuicionálnej logike; pozri oddiel 4.1 nižšie.

Je dôležité si uvedomiť, že zatiaľ čo LEM a DNE sú rovnocenné ako schémy nad (mathbf {H – IPC}), implikácia

[(neg / neg A / rightarrow A) rightarrow (A / vee / neg A))

nie je schéma vety (mathbf {H – IPC}). Pokiaľ ide o teórie (mathbf {T}) založené na intuičnej logike, ak (E) je ľubovoľný vzorec (L (mathbf {T})), potom podľa definície:

(E) je rozhodnuteľné v (mathbf {T}) iba vtedy, ak (mathbf {T}) dokazuje (E / vee / neg E).

(E) je stabilný v (mathbf {T}) iba vtedy, ak (mathbf {T}) dokazuje (neg / neg E / rightarrow E).

(E) je testovateľné v (mathbf {T}) iba vtedy, ak (mathbf {T}) dokazuje (neg E / vee / neg / neg E).

Rozhodnuteľnosť znamená stabilitu, ale nie naopak. Spojenie stability a testovateľnosti je rovnocenné rozhodnuteľnosti. Brouwer sám dokázal, že „absurdita absurdity absurdity je ekvivalentná absurdite“(Brouwer [1923C]), takže každý vzorec formy (neg A) je stabilný; ale v (mathbf {H – IPC}) a (mathbf {H – IQC}) prvotné vzorce a ich negácie sú nerozhodnuteľné, ako je uvedené v oddiele 5.1 nižšie.

2.2 Alternatívne formalizmy a teória o odpočte

Systém Hilbertovho štýlu (mathbf {H – IQC}) je užitočný pre metamatematické skúmanie intuicionálnej logiky, ale jeho nútená linearizácia dedukcií a preferencia axiómov pred pravidlami z nej robia nepríjemný nástroj na stanovenie derivability. Prirodzený dedukčný systém (mathbf {N – IQC}) pre intuicionálne predikátové logické výsledky je výsledkom deduktívneho systému (mathbf {D}), prezentovaného v oddiele 3 záznamu o klasickej logike v tejto encyklopédii vynechaním symbol a pravidlá identity a nahradenie klasického pravidla (DNE) dvojitého vylučovania vylučovacím pravidlom intuitionistického pravidla vylučovania vyjadrujúceho ex falso:

(INE) Ak (F) znamená (A) a (F) znamená (neg A), potom (F) znamená (B)

Kľúče, ktoré dokazujú, že (mathbf {H – IQC}) sú ekvivalentné s (mathbf {N – IQC}), sú modus ponens a jeho inverzia:

Teória odpočtov

Ak je (B) odvoditeľný z (A) a možno aj z iných vzorcov (F), všetky premenné voľné v (A) zostávajú pri derivácii konštantné (tj bez použitia druhej alebo tretie pravidlo inferencie o akejkoľvek premennej (x) vyskytujúcej sa voľne v (A), pokiaľ predpoklad (A) pri derivácii nenastane pred danou inferenciou), potom (A / rightarrow B) je odvoditeľné z (F).

Tento zásadný výsledok, ktorý zhruba vyjadruje pravidlo ((rightarrow I)) z (mathbf {I}), možno dokázať pre (mathbf {H – IQC}) indukciou pri definícii odvodenie. Ostatné pravidlá (mathbf {I}) platia pre (mathbf {H – IQC}) v podstate podľa modus ponens, čo zodpovedá ((rightarrow E)) v (mathbf {N -IQC}); a všetky axiómy (mathbf {H – IQC}) sú preukázateľné v (mathbf {N – IQC}).

Na ilustráciu užitočnosti teórie dedukcie zvážte schému (zdanlivo triviálnej) teórie ((A / rightarrow A)). Správny dôkaz v (mathbf {H – IPC}) trvá päť riadkov:

• 1. (A / rightarrow (A / rightarrow A))
• 2. ((A / rightarrow (A / rightarrow A)) rightarrow ((A / rightarrow ((A / rightarrow A) rightarrow A)) rightarrow (A / rightarrow A)))
• 3. ((A / rightarrow ((A / rightarrow A) rightarrow A)) rightarrow (A / rightarrow A))
• 4. (A / rightarrow ((A / rightarrow A) rightarrow A))
• 5. (A / rightarrow A)

kde 1, 2 a 4 sú axiómy a 3, 5 pochádzajú z predchádzajúcich riadkov od modus ponens. Avšak (A) je možné odvodiť z (A) (ako predpoklad) v jednom zjavnom kroku, takže Dedukčná veta nám umožňuje dospieť k záveru, že existuje dôkaz (A / rightarrow A). (V skutočnosti je formálny dôkaz (A / rightarrow A), ktorý bol práve predložený, súčasťou konštruktívneho dôkazu odpočetovej vety!)

Je dôležité poznamenať, že pri definícii derivácie z predpokladov v (mathbf {H – IQC}) sa s predpokladovými vzorcami zaobchádza tak, akoby boli všetky ich voľné premenné univerzálne kvantifikované, takže (forall x A (x)) je odvoditeľná z hypotézy (A (x)). Premenná (x) sa však bude pri tejto derivácii líšiť (nebude držať konštantnú) pomocou pravidla (forall) - introdukcie; a tak sa nedá veta o dedukcii použiť na to, aby sme dospeli k záveru (falošne), že (A (x) rightarrow / forall x A (x)) (a teda podľa (existuje) - odstránenie, (existuje x A (x) rightarrow / forall x A (x))) sú preukázateľné v (mathbf {H – IQC}). Ako príklad správneho použitia teórie dedukcie pre predikátovú logiku zvážte implikáciu (existuje x A (x) rightarrow / neg / forall x / neg A (x)). Toto je preukázateľné v (mathbf {H – IQC}),Najprv odvodíme (neg / forall x / neg A (x)) z (A (x)) so všetkými voľnými premennými udržiavanými konštantnými:

• 1. (forall x / neg A (x) rightarrow / neg A (x))
• 2. (A (x) rightarrow (forall x / neg A (x) rightarrow A (x)))
• 3. (A (x)) (predpoklad)
• 4. (forall x / neg A (x) rightarrow 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))

1, 2 a 5 sú tu axiómy; 4 pochádza z 2 a 3 od modus ponens; a 6 a 7 pochádzajú z predchádzajúcich riadkov od modus ponens; takže sa nemenili žiadne premenné. Teória odpočtu hovorí, že v (mathbf {H – IQC}) je dôkaz (P) z (A (x) rightarrow / neg / forall) x (neg A (x)) a jedna aplikácia (existuje) - eliminácia premení (P) na dôkaz (existuje x A (x) rightarrow / neg / forall x / neg A (x)). Inverzia nie je preukázateľná v (mathbf {H – IQC}), ako je uvedené v časti 5.1 nižšie.

Ďalšími dôležitými alternatívami k (mathbf {H – IQC}) a (mathbf {N – IQC}) sú rôzne postupné kalkulácie pre intuicionálnu výrokovú a predikátovú logiku. Prvý taký počet bol definovaný Gentzenom [1934–5], porov. Kleene [1952]. Postupné systémy, ktoré dokazujú presne rovnaké vzorce ako (mathbf {H – IQC}) a (mathbf {N – IQC}), v každom kroku preukazovania jednoznačne sledujú všetky predpoklady a závery a nahrádzajú ich. modus ponens (ktorý vylučuje stredný vzorec) na základe pravidla strihu (ktoré sa môže ukázať ako prípustné pravidlo (porovnaj oddiel 4.2) pre subsystém zostávajúci, keď sa vynechá).

Ak detaily formalizmu nie sú dôležité, odteraz sledujeme Troelstra a van Dalena [1988], keď necháme „(mathbf {IQC})“alebo „(mathbf {IPC})“odkazovať na formálny systém pre intuicionálnu predikátovú alebo výrokovú logiku, a podobne „(mathbf {CQC})“a „(mathbf {CPC})“pre klasickú predikátovú a výrokovú logiku.

(Mathbf {IPC}) aj (mathbf {IQC}) vyhovujú interpolačným teorémom, napr.: Ak (A) a (B) sú výrokové vzorce, ktoré majú spoločnú aspoň jednu výzvu, a ak (A / rightarrow B) je preukázateľné v (mathbf {IPC}), potom existuje vzorec (C), obsahujúci iba návrhy, ktoré sa vyskytujú v (A) aj (B), takže sú preukázateľné (A / rightarrow C) a (C / rightarrow B). Týmito témami sa zaoberajú Kleene [1952] a Troelstra a Schwichtenberg [2000].

Zatiaľ čo identita môže byť samozrejme pridaná k intuicionálnej logike, pre aplikácie (napr. Aritmetické) sa symbol rovnosti všeobecne považuje za rozlišovaciu predikčnú konštantu, ktorá spĺňa axiómy pre ekvivalenčný vzťah (reflexivita, symetria a transitivita) a ďalšie nelogické axiómy (napr., primitívne rekurzívne definície sčítania a násobenia). Identita je rozhodujúca, intuicionálne aj klasicky, ale intuitionistická extenzívna rovnosť nie je vždy rozhodujúca; pozri diskusiu o Brouwerových axiómach kontinuity v oddiele 3 záznamu o intuicionizme vo filozofii matematiky.

3. Intuitionistická teória čísel (heyting aritmetika) (mathbf {HA})

Intuitionistické (Heyting) aritmetické (mathbf {HA}) a klasické (Peano) aritmetické (mathbf {PA}) zdieľajú rovnaký jazyk prvého poriadku a rovnaké logické axiómy; iba logika je iná. Okrem logických spojív, kvantifikátorov a zátvoriek a jednotlivých premenných (x, y, z, / ldots) (tiež sa používajú ako metavariable) má jazyk aritmetiky (L (mathbf {HA}))) binárny predikátový symbol (=), individuálna konštanta (0), nemenná funkčná konštanta (S) a konečne alebo spočítateľne nekonečne veľa ďalších konštánt pre primitívne rekurzívne funkcie vrátane sčítania a násobenia; presný výber je záležitosťou vkusu a pohodlia. Výrazy sú zostavené z premenných a (0) pomocou funkčných konštánt; najmä,každé prirodzené číslo (n) je vyjadrené v jazyku číselnou (mathbf {n}) získanou použitím (S) (n) krát na (0) (napr. (S (S (0))) je číslica pre (2)). Počiatočné vzorce sú vo forme ((s = t)), kde (s, t) sú pojmy a zložené vzorce sa z nich získavajú obvyklým spôsobom.

Logické axiómy a pravidlá (mathbf {HA}) sú pravidlá a intuitívne predikátové logiky prvého poriadku (mathbf {IQC}). Medzi nelogické axiómy patria reflexné, symetrické a tranzitívne vlastnosti (=): (forall x (x = x),) (forall x / forall y (x = y / rightarrow y = x),) (forall x / forall y / forall z ((x = y / oldand y = z) rightarrow x = z);) axiom charakterizujúci (0) ako najmenšie prirodzené číslo:

(forall x / neg (S (x) = 0),)

axiom charakterizujúcim (S) ako funkciu one-to-one:

(forall x / forall y (S (x) = S (y) rightarrow x = y),)

axióma rozšírenej rovnosti pre (S):

(forall x / forall y (x = y / rightarrow S (x) = S (y));)

primitívne rekurzívne definujúce rovnice pre každú funkčnú konštantu, zvlášť pre sčítanie: (forall x (x + 0 = x),) (forall x / forall y (x + S (y) = S (x +) y));) a množenie: (forall x (x / cdot 0 = 0),) (forall x / forall y (x / cdot S (y) = (x / cdot y) + x);) a (univerzálne uzavretie) schémy matematickej indukcie pre ľubovoľné vzorce (A (x)):

[(A (0) oldand / forall x (A (x) rightarrow A (S (x)))) rightarrow / forall x A (x).)

Rozšírené axiómy rovnosti pre všetky funkčné konštanty sú odvoditeľné matematickou indukciou z axiómu rovnosti pre (S) a primitívnych rekurzívnych funkčných axiómov.

Vzťah prirodzeného poriadku (x / lt y) môže byť definovaný v (mathbf {HA}) pomocou (existuje z (S (z) + x = y)) alebo bez kvantifikátora vzorec (S (x) dot {-} y = 0), ak symbol a primitívne rekurzívne definujúce rovnice pre predchodcu: [Pd (0) = 0,) (forall x (Pd (S (x))) = x)) a medzné odčítanie: (forall x (x / dot {-} 0 = 0),) (forall x (x / dot {-} S (y) = Pd (x) dot {-} y))) sú prítomné vo formalizme. (mathbf {HA}) dokazuje porovnávací zákon

(forall x / forall y (x / lt y / vee x = y / vee y / lt x))

a intuicionálna forma princípu najmenšieho čísla pre ľubovoľné vzorce (A (x)):

(forall x (forall y (y / lt x / rightarrow (A (y) vee / neg A (y))) rightarrow \(existuje 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)))].)

Hypotéza je potrebná, pretože nie všetky aritmetické vzorce sú rozhodnuteľné v (mathbf {HA}). Avšak (forall x / forall y (x = y / vee / neg (x = y))) sa dá dokázať priamo matematickou indukciou, a tak

Počiatočné vzorce (a teda všetky vzorce bez kvantifikátora) sú rozhodujúce a stabilné v (mathbf {HA}).

Ak je (A (x)) rozhodnuteľné v (mathbf {HA}), potom indukciou (x) je (forall y (y / lt x / rightarrow A (y))) a (existuje y (y / lt x / oldand A (y))). z toho dôvodu

Vzorce, v ktorých sú všetky kvantifikátory ohraničené, sú rozhodujúce a stabilné v (mathbf {HA}).

Zbierka (Delta_0) aritmetických vzorcov, v ktorých sú všetky kvantifikátory ohraničené, je najnižšou úrovňou klasickej aritmetickej hierarchie založenej na modeli alternácií kvantifikátorov v prenexovom vzorci. V (mathbf {HA}) nemá každý vzorec predponový tvar, ale Burr [2004] objavil jednoduchú intuicionistickú aritmetickú hierarchiu zodpovedajúcu úroveň klasike. Iba na účely nasledujúcich dvoch definícií, (forall x) označuje blok konečne veľa univerzálnych číselných kvantifikátorov a podobne (existuje x) označuje blok konečne mnohých kvantifikátorov existenciálneho čísla. Pri týchto konvenciách sú Burrove triedy (Phi_n) a (Psi_n) definované:

• (Phi_0 = / Psi_0 = / Delta_0),
• (Phi_1) je trieda všetkých vzorcov vo formáte (forall x A (x)), kde (A (x)) je v (Psi_0). Pre (n / ge 2) je (Phi_n) trieda všetkých vzorcov tvaru (forall x [A (x) rightarrow / existuje y B (x, y)]) kde (A (x)) je v (Phi_ {n-1}) a (B (x, y)) je v (Phi_ {n-2}),
• (Psi_1) je trieda všetkých vzorcov vo formáte (existuje x A (x)), kde (A (x)) je v (Phi_0). Pre (n / ge 2) je (Psi_n) trieda všetkých vzorcov vo formáte (A / rightarrow B), kde (A) je v (Phi_n) a (B) je v (Phi_ {n-1}).

Zodpovedajúce klasické triedy predexu sú definované jednoduchšie:

• (Pi_0 = / Sigma_0 = / Delta_0),
• (Pi_ {n +1}) je trieda všetkých vzorcov tvaru (forall x A (x)), kde (A (x)) je v (Sigma_n),
• (Sigma_ {n +1}) je trieda všetkých vzorcov formy (existuje x A (x)), kde (A (x)) je v (Pi_n).

Peano aritmetika (mathbf {PA}) pochádza z Heytingovej aritmetiky (mathbf {HA}) pridaním LEM alebo (neg / neg A / rightarrow A) do zoznamu logických axiómov, tj pomocou klasickej namiesto intuičnej logiky. Nasledujúce výsledky platia aj vo fragmentoch (mathbf {HA}) a (mathbf {PA}) s indukčnou schémou obmedzenou na (Delta_0) vzorcov.

Burrova veta:

• Každý aritmetický vzorec je preukázateľne ekvivalentný v (mathbf {HA}) so vzorcom v jednej z tried (Phi_n).
• Každý vzorec v (Phi_n) je preukázateľne ekvivalentný v (mathbf {PA}) so vzorcom v (Pi_n) a naopak.
• Každý vzorec v (Psi_n) je preukázateľne ekvivalentný v (mathbf {PA}) so vzorcom v (Sigma_n) a naopak.

(mathbf {HA}) a (mathbf {PA}) sú teoreticky rovnocenné, ako bude uvedené v oddiele 4. Každý z nich je schopný (číselne) vyjadriť svoj vlastný predikát dôkazu. Podľa slávneho Gödelho vety o neúplnosti, ak je (mathbf {HA}) konzistentný, ani (mathbf {HA}) ani (mathbf {PA}) nedokážu preukázať svoju vlastnú konzistenciu.

4. Základná teória korektúry

4.1 Preložiť klasickú do intuicionálnej logiky

Základným faktom o intuicionálnej logike je to, že má rovnakú pevnosť ako klasická logika. Pre výrokovú logiku to prvýkrát preukázal Glivenko [1929].

Glivenkoova veta

Ľubovoľná výroková formule (A) je klasicky dokázateľná, iba vtedy, ak je (neg / neg A) intuitionisticky dokázateľná.

Glivenkoova veta sa nerozširuje na predikátovú logiku, hoci ľubovoľný predikátový vzorec (A) je klasicky dokázateľný, iba ak je (neg / neg A) preukázateľný v intuicionálnej predikátovej logike plus schému „dvojitého posunu negácie“.

(tag {DNS} forall x / neg / neg B (x) rightarrow / neg / neg / forall x B (x))

Sofistikovanejší negatívny preklad klasických do intuičných teórií, nezávisle na Gödelovi a Gentzénovom, spája s každým vzorcom (A) jazyka (L) iný vzorec (g (A)) (bez (vee) alebo (existuje)), napríklad

• (I) Dokazuje sa klasická predikátová logika (A / leftrightarrow g (A)).
• (II) Intuitionistická predikátová logika dokazuje (g (A) leftrightarrow / neg / neg g (A)).
• (III) Ak sa preukáže klasická predikátová logika (A), preukáže sa intuicionálna predikátová logika (g (A)).

Dôkazy sú zrejmé z nasledujúcej induktívnej definície (g (A)) (použitím Gentzenovho priameho prekladu implikácie, namiesto Gödelovho z hľadiska (neg) a (oldand)):

(begin {align *} g (P) & / text {is} neg / neg P, / text {if} P / text {is Prime}. \\ g (A / oldand B) & / text { je} g (A) old a g (B). \\ g (A / vee B) & / text {is} neg (neg g (A) old a / neg g (B)). \\ g (A / rightarrow B) & / text {is} g (A) rightarrow g (B). \\ g (neg A) & / text {is} neg g (A). \\ g (forall xA (x)) & / text {is} forall xg (A (x)). \\ g (existuje xA (x)) & / text {is} neg / forall x / neg g (A (x)). / End {align *})

Pre každý vzorec (A) je (g (A)) preukázateľne intuicionálne, iba ak je (A) klasicky dokázateľné. Najmä ak (B / oldand / neg B) boli klasicky preukázateľné pre nejaký vzorec (B), potom (g (B) oldand / neg g (B)) (čo je (g (B / oldand / neg B))) by sa zase ukázalo intuitívne. z toho dôvodu

(IV) Klasická a intuicionálna predikátová logika je rovnocenná

Negatívny preklad klasiky do intuicionálnej teórie čísel je ešte jednoduchší, pretože prvotné vzorce intuicionistickej aritmetiky sú stabilné. Takže (g (s = t)) je možné považovať za (s = t) a ostatné ustanovenia sa nezmenili. Negatívny preklad akejkoľvek inštancie matematickej indukcie je ďalším príkladom matematickej indukcie a ostatné nelogické axiómy aritmetiky sú ich vlastné negatívne preklady, takže

(I), (II), (III) a (IV) platia aj pre teóriu čísel

Gödel [1933e] interpretoval tieto výsledky tak, že ukázal, že intuicionálna logika a aritmetika sú bohatšie ako klasická logika a aritmetika, pretože intuicionistická teória rozlišuje vzorce, ktoré sú klasicky ekvivalentné a má rovnakú konzistenciu ako klasická teória. Gödelove vety o neúplnosti sa vzťahujú najmä na (mathbf {HA}), ako aj na (mathbf {PA}).

Priame pokusy rozšíriť negatívnu interpretáciu na analýzu zlyhávajú, pretože negatívny preklad počítateľnej axiómy výberu nie je veta intuicionistickej analýzy. Je však v súlade s intuicionistickou analýzou vrátane Brouwerovho kontroverzného princípu kontinuity prostredníctvom funkčnej verzie rekurzívnej realizovateľnosti spoločnosti Kleene (porovnaj oddiel 6.2 nižšie). Z toho vyplýva, že intuicionálna matematika, ktorú možno vyjadriť iba pomocou všetkých štandardných logických spojív a kvantifikátorov, je v súlade s verným prekladom klasickej matematiky, ktorý sa vyhýba (vee) a (existuje).

Je to dôležité, pretože intuitívna analýza Brouwera nie je v súlade s LEM. Ak je však (A) negatívny vzorec (bez (vee) alebo (existuje)), potom (neg / neg A / rightarrow A) sa dá dokázať pomocou intuičnej logiky. V Moschovakisu sa navrhuje zmierenie intuicionálnej a klasickej analýzy v tomto smere, inšpirované Kripkeho predstavou o výbere sekvencie [2017].

4.2 Prípustné pravidlá intuicionálnej logiky a aritmetiky

Gödel [1932] poznamenal, že intuitionistická výroková logika má disjunkčnú vlastnosť:

(DP) Ak (A / vee B) je veta, potom (A) je veta alebo (B) je veta

Gentzen [1935] založil disjunkčnú vlastnosť pre uzavreté vzorce intuicionálnej predikátovej logiky. Z toho vyplýva, že ak je intuicionálna logika konzistentná, potom (P / vee / neg P) nie je veta, ak (P) je atómový vzorec. Kleene [1945, 1952] preukázal, že intuicionistická prvého rádu teórie čísel má tiež súvisiace (pozri Friedman [1975]), existencie majetku:

(EP) Ak (existuje x A (x)) je uzavretá veta, potom pre nejaký uzavretý termín (t), (A (t)) je veta

Vlastnosti disjunkcie a existencie sú špeciálnymi prípadmi všeobecného fenoménu typického pre neklasické teórie. Prípustné pravidlá teórie sú pravidlá, podľa ktorých je teória uzavretá. Napríklad Harrop [1960] poznamenal, že pravidlo

Ak (neg A / rightarrow (B / vee C)) je veta, je to aj ((neg A / rightarrow B) vee (neg A / rightarrow C))

je prípustný pre intuicionálnu výrokovú logiku (mathbf {IPC}), pretože ak (A), (B) a (C) sú nejaké vzorce, ktoré (neg A / rightarrow (B / vee) C)) je preukázateľné v (mathbf {IPC}), potom ((neg A / rightarrow B) vee (neg A / rightarrow C)) je preukázateľné v (mathbf {IPC) }). Harropove pravidlo nie je odvoditeľné v (mathbf {IPC}), pretože ((neg A / rightarrow (B / vee C))) rightarrow (neg A / rightarrow B) vee (neg A / rightarrow C)) nie je intuicionálne preukázateľné. Ďalším dôležitým príkladom prípustného nedostupného pravidla (mathbf {IPC}) je mincovne pravidlo:

Ak ((A / rightarrow B) rightarrow (A / vee C)) je veta, je to aj (((A / rightarrow B) rightarrow A) vee ((A / rightarrow B) rightarrow C)).

Výklad klasickej výrokovej logiky (mathbf {CPC}) s dvoma hodnotami dáva jednoduchý dôkaz o tom, že každé prípustné pravidlo (mathbf {CPC}) je odvoditeľné: inak, niektoré priradenie (A), (B) atď. By urobili hypotézu pravdivou a záver nepravdivý a nahradením napr. (P / rightarrow P) písmenami "true" a (P / oldand / neg P)) pre tých, ktorým bolo pridelené „falošné“, by sa preukázala hypotéza a preukázateľný záver. Skutočnosť, že intuicionálna situácia je zaujímavejšia, vedie k mnohým prirodzeným otázkam, z ktorých niektoré boli nedávno zodpovedané.

Zovšeobecnením Mincovcovho pravidla identifikovali Visser a de Jongh rekurzívne vymenovateľnú postupnosť postupne silnejších prípustných pravidiel (ďalej len „Visserove pravidlá“), ktoré, ako tvrdili, vytvorili základ pre prípustné pravidlá (mathbf {IPC}) v zmysle že každé prípustné pravidlo je odvoditeľné od disjunkčnej vlastnosti a jedného z pravidiel postupnosti. Na základe práce Ghilardiho [1999] sa Iemhoffovi [2001] podarilo dokázať ich domnienky. Rybakov [1997] preukázal, že výber všetkých prípustných pravidiel (mathbf {IPC}) je rozhodujúci, ale nemá konečný základ. Visser [2002] ukázal, že jeho pravidlá sú tiež prípustnými výrokovými pravidlami (mathbf {HA}) a (mathbf {HA}) rozšírenými o Markovov princíp MP (definovaný v časti 5.2 nižšie). V poslednej dobe,Jerabek [2008] našiel nezávislý základ pre prípustné pravidlá (mathbf {IPC}), s majetkom, z ktorého žiadne pravidlo nevyvoláva iné.

O prípustných pravidlách intuicionálnej predikátovej logiky sa vie oveľa menej. Čisté (mathbf {IQC}), bez individuálnych alebo predikátových konštánt, má pre pozoruhodné prípustné pravidlo pre (A (x)) bez akýchkoľvek premenných, ale (x):

Ak (existuje x A (x)) je veta, je to aj (forall x A (x)).

Nie každé prípustné predikátové pravidlo (mathbf {IQC}) je prípustné pre všetky formálne systémy založené na (mathbf {IQC}); napríklad (mathbf {HA}) zjavne porušuje práve uvedené pravidlo. Visser v roku 1999 dokázal, že vlastnosť prípustného predikátneho pravidla (mathbf {HA}) je (Pi_2) úplná, av roku 2002 to (mathbf {HA}) (+) MP má rovnaké prediktívne pravidlá ako (mathbf {HA}). Plisko [1992] preukázal, že predikátová logika (mathbf {HA}) (+) MP (množina viet v jazyku (mathbf {IQC}), ktorých všetky rovnaké substitučné prípady sú v jazyk aritmetiky je preukázateľný v (mathbf {HA}) (+) MP) je (Pi_2) úplný; Visser [2006] rozšíril tento výsledok na niektoré konštruktívne zaujímavé konzistentné rozšírenia (mathbf {HA}), ktoré nie sú obsiahnuté v (mathbf {PA}).

Aj keď neboli úplne klasifikované, je známe, že prípustné pravidlá intuicionálnej predikátovej logiky zahŕňajú Markovove pravidlo pre rozhodujúce predikáty:

Ak (forall x (A (x) vee / neg A (x)) oldand / neg / forall x / neg A (x)) je veta, je (existuje x A (x)).

a nasledujúce pravidlo nezávislosti (kde (y) sa predpokladá, že sa nevyskytuje zadarmo v (A (x))):

Ak (forall x (A (x) vee / neg A (x)) oldand (forall x A (x) rightarrow / existuje, y B (y))) je veta, tak je (existuje y (forall x A (x) rightarrow B (y))).

Obidve pravidlá sú prípustné aj pre (mathbf {HA}). Zodpovedajúce implikácie (MP a IP), ktoré nie sú intuitívne preukázateľné, sú overené Gödelovou interpretáciou Dialektiky (mathbf {HA}) (porovnaj oddiel 6.3 nižšie). Rovnako tak implikácia (CT) zodpovedajúca jednému z najzaujímavejších prípustných pravidiel Heytingovej aritmetiky, nazývajme to pravidlo Church-Kleene:

Ak (forall x / existuje y A (x, y)) je uzavretá veta (mathbf {HA}), existuje číslo (n) také, že preukázateľne v (mathbf {HA}) je čiastočná rekurzívna funkcia s Gödelovým číslom (n) celková a mapuje každú (x) na (y), ktorá vyhovuje (A (x, y)) (a navyše (A (mathbf {x}, / mathbf {y})) je preukázateľné, kde (mathbf {x}) je číslica pre prirodzené číslo (x) a (mathbf {y}) je číslica pre (y)).

Kombinácia Markovovho pravidla s negatívnym prekladom vedie k tomu, že klasická a intuitívna aritmetika dokazuje rovnaké vzorce vzorca (forall x / existuje y A (x, y)), kde (A (x, y)) je quantifier-free. Všeobecne platí, že ak (A (x, y)) je preukázateľne rozhodnuteľné v (mathbf {HA}) a ak (forall x / existuje y A (x, y)) je uzavretá veta klasická aritmetika (mathbf {PA}), záver Cirkevno-Kleenovho pravidla platí aj v intuicionálnej aritmetike. Pretože ak (mathbf {HA}) preukáže (forall x / forall y (A (x, y) vee / neg A (x, y)))), potom podľa Church-Kleeneho pravidla charakteristickou funkciou z (A (x, y)) má Gödel číslo (m), preukázateľne v (mathbf {HA}); takže (mathbf {HA}) dokazuje (forall x / existuje y A (x, y) leftrightarrow / forall x / existuje y / existuje z B (mathbf {m}, x, y, z)) kde (B) je bez kvantifikátora,a susediace existenciálne kvantifikátory sa môžu uzavrieť v (mathbf {HA}). Z toho vyplýva, že (mathbf {HA}) a (mathbf {PA}) majú rovnaké preukázateľne rekurzívne funkcie.

Tu je dôkaz, že pravidlo „Ak (forall x (A / vee B (x))) je veta, je to aj (A / vee / forall x B (x))” (kde (x) nie je zadarmo v (A)), nie je prípustné pre (mathbf {HA}), ak je (mathbf {HA}) konzistentné. Gödel číslovanie poskytuje vzorec bez kvantifikátora (G (x)), ktorý (číselne) vyjadruje predikát „(x) je kód dôkazu v (mathbf {HA}) z ((0) = 1)). “Intuionistickou logikou s rozhodovacou schopnosťou aritmetických vzorcov bez kvantifikátora / \ / \ mathbf {HA}) dokazuje (forall x (existuje y G (y) vee / neg G (x))). Ak sa však (mathbf {HA}) osvedčil (existuje yG (y) vee / forall x / neg G (x)), potom disjunkčnou vlastnosťou musí (mathbf {HA}) dokázať buď / (existuje yG (y)) alebo (forall x / neg G (x)). Prvý prípad je nemožný,vlastnosťou existencie s predpokladom konzistentnosti a skutočnosťou, že (mathbf {HA}) dokazuje všetky skutočné vety bez kvantifikátora. Druhý prípad je však tiež nemožný, podľa Gödelovej druhej vety o neúplnosti, pretože (forall x / neg G (x)) vyjadruje konzistenciu (mathbf {HA}).

5. Základná sémantika

Intuitionistické systémy inšpirovali rôzne interpretácie, vrátane Bethových tabliet, Rasiowových a Sikorských topologických modelov, Heytingových algebier, vzorcov ako typov, Kleenových rekurzívnych realizovateľností, Kleenov a Aczelových lomít a modelov založených na snopoch a topoi. Zo všetkých týchto interpretácií Kripkeho sémantika možného sveta (1965), s ohľadom na ktorú je intuicionálna predikátová logika úplná a konzistentná, sa najviac podobá teórii klasického modelu. Na druhej strane sa rekurzívne interpretácie realizovateľnosti snažia efektívne implementovať BHK vysvetlenie intuitionistickej pravdy.

5.1 Kripkeho sémantika pre intuicionálnu logiku

Kripkeho štruktúra (mathbf {K}) pre (L) pozostáva z čiastočne usporiadanej množiny (K) uzlov a funkcie domény D priradenej každému uzlu (k) v (K) obývaná množina (D (k)), takže ak (k / le k '), potom (D (k) subseteq D (k')). Okrem toho (mathbf {K}) má vzťah vynútenia určený nasledovne.

Pre každý uzol (k) nech (L (k)) bude jazyk rozširujúci (L) o nové konštanty pre všetky prvky (D (k)). Ku každému uzlu (k) a každému (0) - ary predikátové písmeno (každé propozičné písmeno) (P), buď priraďte (f (P, k) =) true alebo nechajte (f (P, k)) nedefinované, v súlade s požiadavkou, že ak (k / le k ') a (f (P, k) =) true, potom (f (P, k') =) true tiež. Povedz to

(k) (vDash) (P) iba vtedy, ak (f (P, k) =) true.

Ku každému uzlu (k) a každému ((n + 1)) - ary predikátové písmeno (Q (ldots)), priraďte (možno prázdny) množinu (T (Q, k)) z ((n + 1)) - n-tice prvkov (D (k)) takým spôsobom, že ak (k / le k ') potom (T (Q, k) subseteq T (Q, k ')). Povedz to

(k) (vDash) (Q (d_0, / ldots, d_n)) iba vtedy, ak ((d_0, / ldots, d_n) v T (Q, k)).

Teraz definujte (k) (vDash) (E) (ktorý môže byť čítaný "(k) force (E)") pre zložené vety (E) z (L (k)) induktívne takto:

(k) (vDash) ((A / oldand B))	ak (k) (vDash) (A) a (k) (vDash) (B).
(k) (vDash) ((A / vee B))	ak (k) (vDash) (A) alebo (k) (vDash) (B).
(k) (vDash) ((A / rightarrow B))	ak pre každé (k '\ ge k), ak (k') (vDash) (A), potom (k ') (vDash) (B),
(k) (vDash) (neg A)	ak pre nie (k '\ ge k) nemá (k') (vDash) (A).
(k) (vDash) (forall x A (x))	ak pre každé (k '\ ge k) a každé (d / v D (k')), (k ') (vDash) (A (d)).
(k) (vDash) (existuje x A (x))	ak pre niektoré (d / in D (k)), (k) (vDash) (A (d)).

Každý taký nútený vzťah je konzistentný:

Pre žiadnu vetu (A) a nie (k) je to tak, že (k) (vDash) (A) a (k) (vDash) (neg A).

a monotónne:

Ak (k / le k ') a (k) (vDash) (A), potom (k') (vDash) (A).

Kripkeho vety o úplnosti a úplnosti dokazujú, že veta intuitívnej predikátovej logiky sa dá dokázať vetou (L) iba vtedy, ak ju vynúti každý uzol každej štruktúry Kripke. Aby sme dokázali, že (neg / forall x / neg P (x) rightarrow / existuje x P (x)) je intuicionálne nedostupné, stačí uvažovať o Kripkeho štruktúre s (K = {k, k '},) (k / lt k',) (D (k) = D (k ') = {0 }), (T (P, k)) prázdne, ale (T (P, k ') = {0 }). A aby sme ukázali, že konverzácia je intuitívne preukázateľná (bez toho, aby sme skutočne preukázali dôkaz), človek potrebuje iba konzistentné a monotónne vlastnosti ľubovoľných Kripkových modelov s definíciou (vDash).

Kripkeho modely pre jazyky s rovnosťou môžu interpretovať (=) v každom uzle ľubovoľným vzťahom ekvivalencie, podliehajúc monotonite. Pre aplikácie na intuicionálnu aritmetiku postačujú normálne modely (tie, v ktorých je rovnosť interpretovaná identitou v každom uzle), pretože rovnosť prirodzených čísel je rozhodujúca.

Výroková Kripkeho sémantika je obzvlášť jednoduchá, pretože svojvoľný výrokový vzorec je intuicionálne preukázateľný, iba ak je vynútený koreňom každého modelu Kripke, ktorého rámec (množina uzlov spolu s čiastočným usporiadaním) je konečný strom s najmenším prvkom (koreň). Napríklad model Kripke s (K = {k, k ', k' '}, k / lt k') a (k / lt k '') a (P) true iba na (k '), ukazuje, že (P / vee / neg P) a (neg P / vee / neg / neg P) sú nedostupné v (mathbf {IPC}), Každý koncový uzol alebo krídlo Kripkeho modelu je klasický model, pretože list vynúti každú formuláciu alebo jej negáciu. Iba tie návrhy, ktoré sa vyskytujú vo vzorci (E), a iba tie uzly (k '), že (k / le k'), sú relevantné pri rozhodovaní, či sily (k) sú alebo nie. (E). Takéto úvahy nám umožňujú efektívne sa spojiť s každým vzorcom (E) z (L (mathbf {IPC})) konečnej triedy konečných štruktúr Kripke, ktoré budú obsahovať protiklad k (E), ak taký existuje. Pretože trieda všetkých veta (mathbf {IPC}) je rekurzívne spočítateľná, usudzujeme, že

(mathbf {IPC}) je skutočne rozhodnuteľné. Existuje rekurzívny postup, ktorý pre každý výrokový vzorec (E) určuje, či (E) je alebo nie je veta (mathbf {IPC}) a ktorá končí buď dôkazom (E) alebo (konečný) Kripke kontramodel.

Rozhodnuteľnosť (mathbf {IPC}) bola prvýkrát získaná Gentzenom v roku 1935. Nerozhodnuteľnosť (mathbf {IQC}) vyplýva z nerozhodnuteľnosti (mathbf {CQC}) negatívnou interpretáciou, Známe neintuinistické logické schémy zodpovedajú napríklad štrukturálnym vlastnostiam Kripkových modelov

• DNS má v každom modeli Kripke konečný rámec.
• ((A / rightarrow B) vee (B / rightarrow A)) má v každom modeli Kripke lineárne usporiadaný rám. A naopak, každý výrokový vzorec, ktorý nemožno odvodiť v (mathbf {IPC} + (A / rightarrow B) vee (B / rightarrow A)), má Kripkeho protipól s lineárne usporiadaným rámcom (porovnaj oddiel 6.1 nižšie).
• Ak (x) nie je zadarmo v (A), potom (forall x (A / vee B (x)) rightarrow (A / vee / forall x B (x))) platí v každom Kripke model (mathbf {K}) s konštantnou doménou (takže (D (k) = D (k ')) pre všetky (k, k') v (K)). To isté platí pre MP.

Modely Kripke a Beth (ktoré sa líšia od modelov Kripke v detailoch, sú však intuicionálne rovnocenné) sú mocným nástrojom na stanovenie vlastností intuicionálnych formálnych systémov; porov Troelstra a van Dalen [1988], Smorynski [1973], de Jongh a Smorynski [1976], Ghilardi [1999] a Iemhoff [2001], [2005]. Neexistuje však žiadny intuičný dôkaz, že každá veta platná vo všetkých modeloch Kripkeho a Beth je preukázateľná v (mathbf {IQC}). Po pozorovaní Gödelom Kreisel [1958] overil, že úplnosť intuicionálnej predikátovej logiky pre Beth sémantiku je rovnocenná Markovovmu princípu MP, ktorý Brouwer odmietol.

Okrem toho Dyson a Kreisel [1961] ukázali, že ak (mathbf {IQC}) je slabo kompletný pre Beth sémantiku (to znamená, ak v každom Bethovom modeli nie je žiadna nepreukázateľná veta), potom nasledujúci dôsledok MP platí: [tag {GDK} forall / alpha_ {B (alfa)} neg / neg / existuje x R (alfa, x) rightarrow / neg / neg / forall / alpha_ {B (alfa)} existuje x R (alfa, x),) kde (x) je v rozsahu všetkých prirodzených čísel, (alfa) v rozsahu všetkých nekonečných sekvencií prírodných čísel, (B (alfa)) je skratka (forall x (alfa (x) leq 1)) a (R) vyjadruje primitívny rekurzívny vzťah (alfa) a (x). Naopak, GDK znamená slabú úplnosť (mathbf {IQC}). Tento zaujímavý princíp, ktorý by odôvodňoval negatívny výklad formy Brouwerovho Fan Fan,je slabší ako MP, ale v súčasných systémoch intuicionálnej analýzy nie je preukázateľný. Kreisel [1962] navrhol, že GDK sa môže nakoniec dokázať na základe doteraz neobjavených vlastností intuitívnej matematiky.

Modifikáciou definície Kripkeho modelu tak, aby umožňoval „explodujúce uzly“, ktoré si vynútia každú vetu, Veldman [1976] našiel dôkaz úplnosti pomocou iba intuičnej logiky, ale spochybnil, či Kripkeho modely s explodujúcimi uzlami boli intuitívne zmysluplné matematické objekty.

5.2 Sémantika uskutočniteľnosti pre aritmetiku heytingu

Jedným zo spôsobov, ako implementovať BHK vysvetlenie intuitionistickej pravdy pre aritmetiku, je spojiť s každou vetou (E) z (mathbf {HA}) nejakú zbierku číselných kódov pre algoritmy, ktoré by mohli vytvoriť konštruktívnu pravdu o (E). Po Kleene [1945], číslo (e) realizuje vetu (E) jazyka aritmetiky indukciou na logickej forme (E):

(e) realizuje (r = t)	ak (r = t) je pravda.
(e) realizuje (A / oldand B)	ak (e) kóduje pár ((f, g)) tak, že (f) realizuje (A) a (g) realizuje (B).
(e) realizuje (A / vee B)	ak (e) kóduje pár ((f, g)), takže ak (f = 0) potom (g) realizuje (A), a ak (f / gt 0) potom (g) realizuje (B).
(e) realizuje (A / rightarrow B)	ak, kedykoľvek (f) realizuje (A), potom (e) tretia rekurzívna funkcia je definovaná v (f) a jej hodnota realizuje (B).
(e) realizuje (neg A)	ak nie (f) realizuje (A).
(e) realizuje (forall x A (x))	ak pre každú (n) je (e) tretia rekurzívna funkcia definovaná v (n) a jej hodnota realizuje (A (mathbf {n})).
(e) realizuje (existuje x A (x))	ak (e) kóduje pár ((n, g)) a (g) realizuje (A (mathbf {n})).

Ľubovoľný vzorec je realizovateľný, ak niektorí z nich realizujú jeho univerzálne uzavretie. Všimnite si, že nie (A) a (neg A) sú realizovateľné pre všetky vzorce (A). Základným výsledkom je

Nelsonova veta [1947]

Ak (A) je možné odvodiť v (mathbf {HA}) z realizovateľných vzorcov (F), potom je realizovateľné (A).

Ukázalo sa, že niektoré neintuitionistické princípy sú realizovateľné. Schéma môže napríklad vyjadriť Markovov princíp (pre rozhodujúce vzorce)

(MP) (forall x (A (x) vee / neg A (x)) oldand / neg / forall x / neg A (x) rightarrow / existuje x A (x))

Hoci to nie je možné v (mathbf {HA}) preukázať, MP je realizovateľný argumentom, ktorý využíva Markovov princíp neformálne. Realizovateľnosť je však v zásade neklasickou interpretáciou. V (mathbf {HA}) je možné vyjadriť axióma rekurzívnej voľby CT (pre "Cirkevnú tézu"), ktorá je v rozpore s LEM, ale je (konštruktívne) realizovateľná. Preto podľa Nelsonovej vety je (mathbf {HA}) (+) MP (+) CT konzistentný.

Kleene použil variant číselnej realizovateľnosti, aby dokázal, že (mathbf {HA}) spĺňa pravidlo Church-Kleene; rovnaký argument funguje pre (mathbf {HA}) s MP alebo CT a pre (mathbf {HA}) (+) MP (+) CT. V Kleene a Vesley [1965] a Kleene [1969] funkcie nahradzujú čísla ako realizujúce objekty, čím sa vytvára konzistentnosť formalizovanej intuicionistickej analýzy a jej uzavretie podľa verzie druhého rádu podľa Church-Kleene Rule.

Nelsonova veta zavádza nevykonateľnosť niektorých / ~ (mathbf {IQC}) niektorých teórií klasickej predikátovej logiky. Ak do každého (n) - umiestnite predikátové písmeno (P (ldots)), vzorec (f (P)) z (L (mathbf {HA})) s (n) sú priradené voľné premenné a ak vzorec (f (A)) z (L (mathbf {HA})) pochádza zo vzorca (A) z (L) nahradením každého prvú rovnicu (P (x_1, / ldots, x_n)) podľa (f (P) (x_1, / ldots, x_n)), potom (f (A)) sa nazýva aritmetická substitučná inštancia (A). Napríklad, ak vzorec (L (mathbf {HA})) vyjadrujúci „(x) kóduje dôkaz v (mathbf {HA}) vzorca s kódom (y)”Je priradené k (P (x, y)), výslednej aritmetickej substitučnej inštancii (forall y (existuje x P (x, y) vee / neg / existuje x P (x, y)))) je v (mathbf {HA}) nerealizovateľný, a teda nezvládnuteľný, rovnako ako jeho dvojitá negácia. Z toho vyplýva, že (neg / neg / forall y (existuje x P (x, y) vee / neg / existuje x P (x, y))) nie je možné preukázať v (mathbf {IQC})).

De Jongh [1970] kombinoval realizovateľnosť s Kripkeovým modelovaním, aby ukázal, že intuitívna výroková logika (mathbf {IPC}) a fragment (mathbf {IQC}) sú aritmeticky úplné pre (mathbf {HA})). Stačí dokázať jednotné priradenie jednoduchých existenciálnych vzorcov k predikátovým písmenám

De Jonghova veta (pre IPC) [1970]

Ak výroková formule (A) jazyka (L) nie je preukázateľná v (mathbf {IPC}), potom nejaká aritmetická substitučná inštancia (A) nie je možné preukázať v (mathbf {HA}).

Dôkaz tejto verzie de Jonghovej vety sa nevyžaduje realizovateľnosť; porov Smorynski [1973]. Napríklad Rosserova forma Gödelho vety o neúplnosti obsahuje vetu (C) z (L (mathbf {HA})) tak, že (mathbf {PA}) nepreukazuje ani (C) ani (neg C), takže vlastnosť disjunkcie (mathbf {HA}) nemôže dokázať ((C / vee / neg C)). Ale de Jonghov sémantický dôkaz tiež preukázal, že každý intuicionálne nepreukázateľný predikátový vzorec obmedzeného druhu má aritmetickú substitučnú inštanciu, ktorá je v (mathbf {HA}) nepreukázateľná. Použitím syntaktickej metódy Daniel Leivant [1979] rozšíril de Jonghovu teóriu na všetky intuitívne nepreukázateľné predikátové vzorce, čo dokazuje, že (mathbf {IQC}) je aritmeticky úplný pre (bf {HA}). Viď van Oosten [1991], kde nájdete historickú expozíciu a jednoduchší dôkaz úplnej vety, pomocou abstraktnej realizovateľnosti s Beth modelmi namiesto Kripkových modelov.

Bez toho, aby tvrdil, že realizovateľnosť čísel sa zhoduje s intuicionálnou aritmetickou pravdou, Nelson poznamenal, že pre každý vzorec (A) z (L (mathbf {HA})) predikát "(y) realizuje (A) "Možno vyjadriť v (mathbf {HA}) iným vzorcom (skratka" (y / realizesrel A) ") a schéma (A / leftrightarrow / existuje y (y / realizesrel A)) je v súlade s (mathbf {HA}). Troelstra [1973] ukázal, že (mathbf {HA}) (+) ((A / leftrightarrow / existuje y (y / realizesrel A))) je ekvivalentné (mathbf {HA}) (+) ECT, kde ECT je posilnená forma CT. V (mathbf {HA}) (+) MP (+) ECT, ktorý Troelstra považuje za formalizáciu ruskej rekurzívnej matematiky (pozri oddiel 3.2 záznamu o konštruktívnej matematike), každý vzorec forma ((y / realizesrel A)) má ekvivalentnú „klasickú“formu predexportu (A 'y)) pozostávajúce z podformulu bez kvantifikátora, ktorému predchádzajú striedanie „klasických“kvantifikátorov foriem (neg / neg / existuje x) a (forall z / neg / neg), a tak (existuje y A '(y)) je druh predexponovanej formy (A).

6. Ďalšie témy a ďalšie čítanie

6.1 Subintuitionistic and Intermediate Logics

V súčasnosti existuje v tejto encyklopédii niekoľko ďalších záznamov, ktoré sa zaoberajú intuicionálnou logikou v rôznych kontextoch, ale zdá sa, že všeobecné zaobchádzanie so slabšou a silnejšou výrokovou a predikátovou logikou chýba. Bolo identifikovaných a študovaných mnoho takýchto logík. Tu je niekoľko príkladov.

Subintuitionistická výroková logika sa dá získať od (mathbf {IPC}) obmedzením jazyka alebo oslabením logiky alebo oboch. Extrémnym príkladom prvej je (mathbf {RN}), intuicionálna logika s jedinou výrokovou premennou (P), ktorá je pomenovaná po jej objaviteľoch Riegerovi a Nishimure [1960]. (mathbf {RN}) je charakterizovaný Riegerovou-Nishimurovou mriežkou nekonečne veľa nekvivalentných vzorcov (F_n), takže každý vzorec, ktorého jediná výroková premenná je (P), je podľa intuicionálnej logiky ekvivalentný s niektorými (F_n). Nishimura verzia je

(begin {align *} F _ { infty} & = P / rightarrow 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} rightarrow F_ {2 n + 1}. / End {align *})

V (mathbf {RN}) ani (F_ {2 n + 1}) ani (F_ {2 n + 2}) neimplikuje ostatné; ale (F_ {2 n}) znamená (F_ {2 n + 1}) a (F_ {2 n + 1}) znamená každý z (F_ {2 n + 3}) a (F_ {2 n + 4}).

Fragmenty (mathbf {IPC}), ktorým chýba jedno alebo viac logických spojív, obmedzujú jazyk a náhodne logiku, pretože intuicionálne spojnice (oldand), (vee), (rightarrow), (neg) sú logicky nezávislé od (mathbf {IPC}). Rose [1953] preukázala, že bezpredmetný fragment (bez (rightarrow)) je úplný vzhľadom na realizovateľnosť v tom zmysle, že ak každá aritmetická substitučná inštancia výrokového vzorca (E) bez (rightarrow) je (number) -realizable potom (E) je veta (mathbf {IPC}). Tento výsledok je v kontraste s

Roseova veta [1953]

(mathbf {IPC}) je neúplná, pokiaľ ide o realizovateľnosť.

Nech (F) je výrokový vzorec [((neg / neg D / rightarrow D) rightarrow (neg / neg D / vee / neg D)) rightarrow (neg / neg D / vee / neg D)) kde (D) je ((neg P / vee / neg Q)) a (P), (Q) sú prvoradé. Každá aritmetická substitučná inštancia (F) je realizovateľná (pomocou klasickej logiky), ale (F) nie je preukázateľná v (mathbf {IPC}).

Z toho vyplýva, že (mathbf {IPC}) je aritmeticky neúplný pre (mathbf {HA}) (+) ECT (porovnaj časť 5.2).

Minimálna logika (mathbf {ML}) vychádza z intuicionálnej logiky odstránením ex falso. Kolmogorov [1925] ukázal, že tento fragment už obsahuje negatívnu interpretáciu klasickej logiky zachovávajúcej oba kvantifikátory, porovnaj Leivant [1985]. Minimálna logika dokazuje, že zvláštny prípad (neg A / rightarrow (A / rightarrow / neg B)) ex falso pre negácie. Colacito, de Jongh a Vardas [2017] študujú rôzne subminimálne logiky, z ktorých každá je slabšia ako (mathbf {ML}).

Griss namietal proti Brouwerovej použitiu negácie, namietajúc tak protirečenie, ako aj ex falso. Je potrebné poznamenať, že negácia nie je skutočne potrebná pre intuitívnu matematiku, pretože (0 = 1) je známy rozpor, takže (neg A) možno definovať pomocou (A / rightarrow 0 = 1). Potom ex falso možno označiť ako (0 = 1 / rightarrow A) a zákon kontradikcie je preukázateľný zo zvyšných axiómov (mathbf {H}).

Medziľahlá výroková logika je akákoľvek konzistentná zbierka výrokových vzorcov obsahujúcich všetky axiómy (mathbf {IPC}) a uzavretá v modus ponens a nahradenie ľubovoľných vzorcov za výrokové listy. Každá prechodná výroková logika je obsiahnutá v (mathbf {CPC}). Niektoré konkrétne prechodné výrokové logiky, charakterizované pridaním jedného alebo viacerých klasicky správnych, ale intuicionálne nepreukázateľných axiómových schém, do (mathbf {IPC}), boli podrobne študované.

Jednou z najjednoduchších prechodných výrokových logík je Gödel-Dummettova logika (mathbf {LC}), získaná pridaním schémy ((A / rightarrow B) vee (B / rightarrow A)), ktorý platí pre všetky a iba tie Kripkeho snímky, v ktorých je čiastkové poradie uzlov lineárne. Gödel [1932] použil nekonečnú sekvenciu postupne silnejších stredných logík, aby ukázal, že (mathbf {IPC}) nemá konečnú interpretáciu tabuľky pravdy. Pre každé kladné celé číslo (n) nech (mathbf {G_n}) bude (mathbf {LC}) plus schéma ((A_1 / rightarrow A_2) vee / ldots / vee (A_1 / oldand / ldots / oldand A_n / rightarrow A_ {n + 1})). Potom (mathbf {G_n}) platí pre všetky a iba tie lineárne usporiadané Kripkeho snímky, ktoré nemajú viac ako (n) uzlov.

Jankovova logika (mathbf {KC}), ktorá pridáva k (mathbf {IPC}) princíp testovateľnosti (neg A / vee / neg / neg A), samozrejme nemá disjunkciu nehnuteľnosť. Logika Kreisel-Putnam (mathbf {KP}), získaná pridaním schémy (mathbf {IPC}) do schémy ((neg A / rightarrow B / vee C) rightarrow ((neg A / rightarrow B) vee (neg A / rightarrow C))), má disjunkčnú vlastnosť, ale nespĺňa všetky Visserove pravidlá. Stredná logika získaná pridaním schémy (((neg / neg D / rightarrow D) rightarrow (D / vee / neg D)) rightarrow (neg / neg D / vee / neg D)), zodpovedajúcej k Rose je príklad, k (mathbf {IPC}) má tiež disjunkčná vlastnosť. Iemhoff [2005] preukázal, že (mathbf {IPC}) je jediná prechodná výroková logika s disjunkčnou vlastnosťou, ktorá je uzavretá podľa všetkých Visserových pravidiel. Iemhoff a Metcalfe [2009] vyvinuli formálny počet pre všeobecnú prijateľnosť pre (mathbf {IPC}) a pre niektoré prechodné logiky. Goudsmit [2015] je dôkladnou štúdiou o prípustných pravidlách medziskladovej logiky s komplexnou bibliografiou.

Hovorí sa, že stredná výroková logika (mathbf {L}) má vlastnosť konečných rámcov, ak existuje trieda konečných rámcov, na ktorých Kripkeho platné vzorce sú presne vety vety (mathbf {L}), Túto vlastnosť má mnoho stredných logík vrátane (mathbf {LC}) a (mathbf {KP}). Jankov [1968] použil nekonečnú postupnosť konečne zakorenených Kripkeho snímok, aby dokázal, že existuje kontinuum mnohých stredných logík. De Jongh, Verbrugge a Visser [2009] preukázali, že každá stredná logika (mathbf {L}) s vlastnosťou konečnej snímky je výroková logika (mathbf {HA (L)}), to znamená trieda všetkých vzorcov v jazyku (mathbf {IPC}), ktorých všetky aritmetické substitučné výskyty sú preukázateľné logickým rozšírením (mathbf {HA}) o (mathbf {L}).

Stredne výroková logika (mathbf {L}) je štrukturálne úplná, ak každé pravidlo, ktoré je prípustné pre (mathbf {L}), je odvoditeľné z (mathbf {L}), a hereditárne štrukturálne úplné, ak každá stredná logika rozširujúca (mathbf {L}) je tiež štrukturálne kompletná. Každá stredná logika (mathbf {L}) má štrukturálne dokončenie (mathbf { overline {L}}), ktoré sa získa prepojením všetkých jej prípustných pravidiel. (mathbf {LC}) a (mathbf {G_n}) sú dedične štrukturálne úplné. Kým (mathbf {IPC}), (mathbf {RN}) a (mathbf {KC}) nie sú štrukturálne úplné, ich štrukturálne dokončenie je dedične štrukturálne úplné. Tieto výsledky a ďalšie informácie nájdete v Citkin [2016, Other Internet Resources].

Niektoré stredné predikátové logiky, rozširujúce (mathbf {IQC}) a uzavreté pod substitúciou, sú (mathbf {IQC}) (+) DNS (oddiel 4.1), (mathbf {IQC}) (+) MP (porovnaj oddiel 5.2), (mathbf {IQC}) (+) MP (+) IP (porovnaj oddiel 4.2) a intuicionálnu logiku konštantných domén (mathbf {CD}) získané pridaním schémy (mathbf {IQC}) do schémy (forall x (A / vee B (x)) rightarrow (A / vee / forall x B (x))) pre všetky vzorce (A), (B (x)) s (x), ktoré sa nevyskytujú zadarmo v (A). Mincovne, Olkhovikov a Urquhart [2012, Iné internetové zdroje] ukázali, že (mathbf {CD}) nemá interpoláciu, čo vyvracia skôr publikované dôkazy iných autorov.

6.2 Pokročilé témy

Brouwerov vplyv na Gödel bol významný, hoci Gödel sa nikdy nestal intuicionistom. Gödelov preklad [1933f] intuicionálnej výrokovej logiky do modálnej logiky (mathbf {S4}) je opísaný v oddiele 2.5 záznamu o Gödel av úvodnej poznámke Troelstra k prekladu [1933f] v zväzku I Gödel's Collected. Tvorba. Pozri aj mincovne [2012]. Modely Kripke pre modálnu logiku predchádzali modelom pre intuicionálnu logiku.

K alternatívam Kripkeho a Bethovej sémantiky pre intuicionálnu výrokovú a predikátovú logiku patrí topologická interpretácia Stone [1937], Tarski [1938] a Mostowski [1948] (porovnaj Rasiowa a Sikorski [1963], Rasiowa [1974]), ktorá bola rozšírená k intuicionálnej analýze Scott [1968] a Krol [1978]. M. Hyland [1982] definoval efektívny topos Eff a preukázal, že jeho logika je intuicionálna. Pre veľmi informatívnu diskusiu o sémantike pre intuicionálnu logiku a matematiku od W. Ruitenberga a zaujímavú novú perspektívu od G. Bezhanishviliho a W. Holliday, pozri Ďalšie internetové zdroje (nižšie).

Jednou alternatívou k sémantike realizovateľnosti pre intuicionálnu aritmetiku je Gödelova interpretácia „dialektiky“z roku 1958, ktorá spája s každým vzorcom (B) z (L (mathbf {HA})) vzorec bez kvantifikátora (B_D) v jazyku intuicionálnej aritmetiky všetkých konečných typov. Interpretácia (B) "Dialectica", nazvaná (B ^ D), je (existuje Y / forall x B_D (Y, x)). Ak (B) je uzavretá veta (mathbf {HA}), potom (B_D (F, x)) je preukázateľné na nejaký termín (F) v Gödelovej teórii (mathbf { T}) „primitívnych rekurzívnych“funkcionárov vyššieho typu. Preklad z (B) do (B ^ D) vyžaduje axiom výberu (vo všetkých konečných typoch), MP a IP, takže nie je striktne konštruktívny; však,číselno-teoretické funkcie vyjadriteľné výrazmi (F) z (mathbf {T}) sú presne preukázateľne rekurzívnymi funkciami (mathbf {HA}) (a (mathbf {PA})). Interpretácia bola rozšírená na analýzu Spectorom [1962]; porov Howard [1973]. Jasné vysvetlenia a ďalšie odkazy sa nachádzajú v úvode Troelstra k anglickému prekladu v Gödele (1990) pôvodného článku o dialektike, v Avigad a Feferman [1998] a vo Ferreire [2008].

Zatiaľ čo (mathbf {HA}) je vhodnou súčasťou klasickej aritmetiky, intuicionistický prístup k matematickým objektom vedie k teórii reálnych čísel (porovnaj oddiely 3.4–3.7 záznamu o intuicionizme vo filozofii matematiky), ktorý sa odlišuje. z klasického. Kleeneho interpretácia realizovateľnosti funkcií, vyvinutá na preukázanie konzistencie jeho formalizácie (mathbf {FIM}) intuitionistickej teórie sekvencií („intuitionistická analýza“), mení interpretáciu aritmetických vzorcov; napríklad (neg / neg / forall x (A (x) vee / neg A (x))) je funkčne realizovateľné pre každý aritmetický vzorec (A (x)). V jazyku analýzyMarkovov princíp a negatívny preklad spočítateľnej axiómy výberu patria medzi mnoho neintuintuistických princípov, ktoré sú funkčne realizovateľné (klasickými argumentmi), a preto sú v súlade s (mathbf {FIM}); porov Kleene [1965], Vesley [1972] a Moschovakis [2003].

Logici a počítačoví vedci vyvinuli a študovali konkrétnu a abstraktnú sémantiku realizovateľnosti pre celý rad formálnych systémov; porov Troelstra [1998] a van Oosten [2002] a [2008]. Variácie základných pojmov sú zvlášť užitočné na stanovenie relatívnej konzistentnosti a relatívnej nezávislosti nelogických axiómov v teóriách založených na intuicionálnej logike; niektoré príklady sú Moschovakis [1971], Lifschitz [1979] a predstavy realizovateľnosti pre konštruktívne a intuitívne teórie množín vyvinuté Rathjenom [2006, 2012] a Chenom [2012]. Medzi prvé abstraktné pojmy realizovateľnosti patria lomítka Kleena [1962, 1963] a Aczel [1968] a Läuchli [1970]. Kohlenbach, Avigad a ďalší vyvinuli interpretácie realizovateľnosti pre časti klasickej matematiky.

Artemovova odôvodňovacia logika je alternatívnou interpretáciou BHK vysvetlenia intuicionálnych spojív a kvantifikátorov s (idealizovanými) dôkazmi, ktoré hrajú úlohu pri realizácii predmetov. Pozri tiež Artemov a Iemhoff [2007].

Ďalšia línia výskumu v intuicionistickej logike sa týka veľmi kontroverzného Brouwera „vytvárania predmetných príkladov“na princípoch klasickej analýzy (ako je Markovov princíp), ktoré nemožno vyvrátiť na základe teórie Kleena a Matébf {FIM}) Vesley [1965]. Oslabením Kleeneho formy Brouwerovho princípu nepretržitého výberu a pridaním axiómu, ktorý nazval Kripkeho schéma (KP), sa Myhill podarilo formalizovať argumenty tvoriacich predmet. KP nie je v súlade s (mathbf {FIM}), ale Vesley [1970] našiel alternatívny princíp (Vesley's Schema VS), ktorý je možné nepretržite pridať k (mathbf {FIM}) a zahŕňa všetky protiklady, pre ktoré Brouwer vyžadoval vytvorenie subjektu. Krol [1978] a Scowcroft poskytli topologické dôkazy konzistencie pre intuicionálnu analýzu s Kripkeho schémou a slabou kontinuitou.

6.3 Odporúčané čítanie

Záznam o LEJ Brouwerovi pojednáva o Brouwerovej filozofii a matematike, s chronológiou jeho života a vybraným zoznamom publikácií vrátane prekladov a sekundárnych zdrojov. Najlepším spôsobom, ako sa dozvedieť viac, je prečítať si niektoré pôvodné články. Anglické preklady doktorandskej dizertačnej práce Brouwerovej a iných článkov, ktoré sa pôvodne objavili v holandčine, spolu s množstvom článkov v nemčine, možno nájsť v knihe LEJ Brouwer: Collected Works [1975], editoval Heyting. Benacerraf a Putnamova základná zdrojová kniha obsahuje Brouwera [1912] (v anglickom preklade), Brouwera (1949) a Dummetta [1975]. Mancosu's [1998] poskytuje anglické preklady mnohých základných článkov Brouwera, Heytinga, Glivenka a Kolmogorova a osvetľuje úvodný materiál W. van Stigta, ktorého [1990] je ďalším cenným zdrojom.

Tretie vydanie (1971) Heytingovej klasiky [1956] je atraktívnym úvodom do intuičnej filozofie, logiky a matematickej praxe. Ako súčasť impozantného projektu úpravy a publikovania Brouwerovej Nachlass, van Dalen [1981] poskytuje komplexný pohľad na vlastnú intuitívnu filozofiu Brouwera. Anglický preklad vo Van Heijenoort [1969] Brouwerovho [1927] (s dobrým úvodom od Parsonsa) je stále nevyhnutným odkazom na Brouwerovu teóriu kontinua. Veldman [1990] a [2005] sú autentickými modernými príkladmi tradičnej intuitívnej matematickej praxe. Troelstra [1991] stavia intuicionálnu logiku do svojho historického kontextu ako spoločný základ konštruktívnej matematiky v dvadsiatom storočí. Bezhanishvili a de Jongh [2005,Iné zdroje internetu] zahŕňa najnovší vývoj v intuičnej logike.

Kleene a Vesley's [1965] poskytuje starostlivé axiomatické zaobchádzanie s intuicionistickou analýzou, dôkaz jej konzistencie vo vzťahu k klasicky správnemu subtheoru a rozšírenú aplikáciu Brouwerovej teórie generátorov skutočných čísel. Kleeneho (1969) formalizuje teóriu čiastkových rekurzívnych funkcionálov, čo umožňuje presné formalizácie interpretácie funkčnej realizovateľnosti použitej v [1965] a súvisiacej interpretácie q-realizovateľnosti, ktorá dáva Cirkev-Kleeneho pravidlo pre intuicionálnu analýzu.

Troelstra [1973], Beeson [1985] a Troelstra a van Dalen [1988] (s korekciami) vynikajú ako najucelenejšie štúdie intuicionálnych a polointu intuicionálnych formálnych teórií, ktoré využívajú konštruktívne aj klasické metódy, s užitočnými bibliografiami. Troelstra a Schwichtenberg [2000] prezentujú paralelne teóriu dôkazov klasickej, intuicionálnej a minimálnej logiky so zameraním na nadväzujúce systémy. Troelstra [1998] predstavuje interpretácie vzorcov ako typov a (Kleene a Aczel) lomítko pre výrokovú a predikátovú logiku, ako aj abstraktné a konkrétne realizovateľnosti pre množstvo aplikácií. Konštruktívna teória typov Martin-Löfa [1984] (porovnaj oddiel 3.4 záznamu o konštruktívnej matematike) poskytuje ďalší všeobecný rámec, v ktorom sa intuitívne uvažovanie ďalej vyvíja.

Bibliografia

• Aczel, P., 1968, „Nasýtené intuičné teórie“, v HA Schmidt, K. Schütte a H.-J. Thiele (ed.), Príspevky k matematickej logike, Amsterdam: Severný Holland: 1-11.
• Artemov, S. a Iemhoff, R., 2007, „Základná intuicionálna logika dôkazov“, Journal of Symbol Logic, 72: 439–451.
• Avigad, J. a Feferman, S., 1998, „Gödelho funkčný výklad („ Dialectica “),“kapitola V Buss (ed.) 1998: 337–405.
• Bar-Hillel, Y. (ed.), 1965, Logic, Methodology and Philosophy of Science, Amsterdam: North Holland.
• Beeson, MJ, 1985, základy konštruktívnej matematiky, Berlín: Springer.
• Benacerraf, P. a Hilary Putnam (ed.), 1983, Filozofia matematiky: Vybrané čítania, 2. vydanie, Cambridge: Cambridge University Press.
• Beth, EW, 1956, „Sémantická konštrukcia intuitívnej logiky“, Koninklijke Nederlandse Akad. von Wettenscappen, 19 (11): 357 - 388.
• Brouwer, LEJ, 1907, „O základoch matematiky“, Thesis, Amsterdam; Anglický preklad v Heyting (ed.) 1975: 11–101.
• –––, 1908, „Nespoľahlivosť logických princípov“, anglický preklad v Heytingu (ed.) 1975: 107–111.
• –––, 1912, „Intuitionizmus a formalizmus“, anglický preklad A. Drážďana, Bulletin American Mathematical Society, 20 (1913): 81–96, dotlač v Benacerraf a Putnam (ed.) 1983: 77–89; tiež dotlačený v Heyting (ed.) 1975: 123–138.
• –––, 1923 [1954], „O význame princípu vylúčeného stredu v matematike, najmä vo funkčnej teórii“, „Dodatky a korigendá“a „Ďalšie dodatky a korigendá“, anglický preklad vo van Heijenoort (ed.) 1967: 334 - 345.
• –––, 1923C, „Intuitionistische Zerlegung matematik Grundbegriffe,“Jahresbericht der Deutschen Mathematiker-Vereinigung, 33 (1925): 251-256; dotlačené v Heyting (ed.) 1975, 275-280.
• –––, 1927, „Intuitionistické úvahy o formalizme“, pôvodne uverejnená v roku 1927, anglický preklad vo van Heijenoort (ed.) 1967: 490–492.
• –––, 1948, „Vedomie, filozofia a matematika“, pôvodne uverejnená (1948), dotlačená v Benacerraf a Putnam (ed.) 1983: 90–96.
• Burr, W., 2004, „The intuitionistic aritmetical hierarchie,“v J. van Eijck, V. van Oostrom a A. Visser (eds.), Logic Colloquium '99 (Poznámky k prednáške v Logic 17), Wellesley, MA: ASL a AK Peters, 51 - 59.
• Buss, S. (ed.), 1998, Handbook of Proof Theory, Amsterdam and New York: Elsevier.
• Chen, RM. a Rathjen, M., 2012, „Realizovateľnosť Lifschitzu pre intuicionálnu teóriu množín Zermelo-Fraenkel,“Archív pre matematickú logiku, 51: 789–818.
• Colacito, A., de Jongh, D. a Vargas, A., 2017, „Subminimálna negácia“, Soft computing, 21: 165–164.
• Crossley, J., a MAE Dummett (eds.), 1965, Formal Systems and Recursive Functions, Amsterdam: North-Holland Publishing.
• van Dalen, D. (ed.), 1981, Brouwer's Cambridge Lectures on Intuitionism, Cambridge: Cambridge University Press.
• Dummett, M., 1975, „Filozofický základ intuicionálnej logiky“, pôvodne publikovaný (1975), dotlačený v Benacerraf a Putnam (ed.) 1983: 97–129.
• Dyson, V. a Kreisel, G., 1961,, Analýza Bethovej sémantickej konštrukcie intuitívnej logiky, Technická správa č. 3, Stanford: Laboratórium aplikovanej matematiky a štatistiky, Stanfordská univerzita.
• Ferreira, F., 2008, „Najmalebnejší balíček zmiešaných myšlienok“, Dialectica, 62: 205–222.
• Friedman, H., 1975, „Vlastnosť disjunkcie znamená vlastnosť numerickej existencie,“Zborník Národnej akadémie vied, 72: 2877–2878.
• Gentzen, G., 1934–5, „Untersuchungen Über das logische Schliessen“, Mathematische Zeitschrift, 39: 176–210, 405–431.
• Ghilardi, S., 1999, “Unification in intuitionistic logic,” Journal of Symbolic Logic, 64: 859 - 880.
• Glivenko, V., 1929, „Sur quelques points de la logique de M. Brouwer“, Académie Royale de Belgique, Bulletins de la classe des science, 5 (15): 183–188.
• Gödel, K., 1932, „Zum intuitionistischen Aussagenkalkül,“Anzeiger der Akademie der Wissenschaften vo Viedni, 69: 65–66. Reprodukované a preložené úvodnou poznámkou AS Troelstra v Gödel 1986: 222–225.
• –––, 1933e, „Zur intuitionistischen Arithmetik und Zahlentheorie“, Ergebnisse eines Mathatischen Kolloquiums, 4: 34–38.
• –––, 1933f, „Eine Interpretation des intuitionistischen Aussagenkalküls“, reprodukovaný a preložený úvodnou poznámkou AS Troelstra v Gödel 1986: 296–304.
• –––, 1958, „Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes,“Dialectica, 12: 280–287. Reprodukované anglickým prekladom v Gödel 1990: 241–251.
• –––, 1986, Collected Works, roč. I. S. Feferman a kol. (eds.), Oxford: Oxford University Press.
• –––, 1990, Collected Works, roč. II, S. Feferman a kol. (eds.), Oxford: Oxford University Press.
• Goudsmit, JP, 2015, Intuitionistické pravidlá: Prípustné pravidlá strednej logiky, Ph. D. dizertačná práca, Univerzita v Utrechte.
• Harrop R., 1960, „Čo sa týka vzorcov typov (A / rightarrow B / vee C, A / rightarrow (Ex) B (x)) v intuicionálnych formálnych systémoch,“Journal of Symbolic Logic, 25: 27–32,
• van Heijenoort, J. (ed.), 1967, Z Frege do Gödel: Zdrojová kniha v matematickej logike 1879 - 1931, Cambridge, MA: Harvard University Press.
• Heyting, A., 1930, „Die formalen Regeln der intuitionistischen Logik“, v troch častiach, Sitzungsberichte der preussischen Akademie der Wissenschaften: 42–71, 158–169. Anglický preklad časti I v Mancosu 1998: 311–327.
• –––, 1956, Intuitionism: Introduction, Amsterdam: North-Holland Publishing, 3. revidované vydanie, 1971.
• Heyting, A. (ed.), 1975, LEJ Brouwer: Collected Works (zväzok 1: Filozofia a základy matematiky), Amsterdam a New York: Elsevier.
• Howard, WA, 1973, „Dereditované funkcionality konečného typu,“v Troelstra (ed.) 1973: 454–461.
• Hyland, JME, 1982, „Efektívne toposy“v Troelstra a van Dalen (ed.) 1982: 165–216.
• Iemhoff, R., 2001, „O prípustných pravidlách intuicionálnej výrokovej logiky“, Journal of Symbolic Logic, 66: 281–294.
• ––– 2005, „Intermediálna logika a Visserove pravidlá“, Notre Dame Journal of Formal Logic, 46: 65–81.
• Iemhoff, R. a Metcalfe, G., 2009, „Teória dôkazu pre prípustné pravidlá“, Annals of Pure and Applied Logic, 159: 171–186.
• Jankov, VA, 1968, „Konštrukcia postupnosti silne nezávislých superintuitionistických výrokov,“Soviet Math Math. Doklady, 9: 801 - 807.
• Jerabek, E., 2008, „Nezávislé základy prípustných pravidiel“, Logic Journal of IGPL, 16: 249–267.
• de Jongh, DHJ, 1970, „Maximalita intuicionálneho výrokového počtu s ohľadom na Heytingovu aritmetiku,“Journal of Symbolic Logic, 6: 606.
• de Jongh, DHJ a Smorynski, C., 1976, „Kripkeho modely a intuitionistická teória druhov,“Annals of Mathematical Logic, 9: 157–186.
• de Jongh, D., Verbrugge, R. a Visser, A., 2011, „Intermediate logics and the de Jongh property,“Archiv for Mathematical Logic, 50: 197-213.
• Kino, A., Myhill, J. a Vesley, RE (ed.), 1970, Intuitionism and Proof Theory: Zborník z letnej konferencie v Buffale, NY, 1968, Amsterdam: Severný Holland.
• Kleene, SC, 1945, „K interpretácii intuicionálnej teórie čísel“, Journal of Symbolic Logic, 10: 109–124.
• –––, 1952, Úvod do metamatematiky, Princeton: Van Nostrand.
• –––, 1962, „Disjunkcia a existencia pod vplyvom elementárnych intuicionistických formalistov“, Journal of Symbolic Logic, 27: 11–18.
• –––, 1963, „Dodatok“, Journal of Symbolic Logic, 28: 154–156.
• –––, 1965, „Klasické rozšírenie intuitívnej matematiky“, Bar-Hillel (ed.) 1965: 31–44.
• –––, 1969, Formalizované rekurzívne funkcie a Formalizovaná realizovateľnosť, Pamätníky americkej matematickej spoločnosti 89.
• Kleene, SC a Vesley, RE, 1965, základy intuitívnej matematiky, najmä vo vzťahu k rekurzívnym funkciám, Amsterdam: Severný Holland.
• Kreisel, G., 1958, „Základné vlastnosti úplnosti intuicionálnej logiky s poznámkou o negáciách predexexových vzorcov“, Journal of Symbolic Logic, 23: 317–330.
• –––, 1962, „O slabej úplnosti intuicionálnej predikátovej logiky“, Journal of Symbolic Logic, 27: 139–158.
• Kripke, SA, 1965, „Sémantická analýza intuitívnej logiky“, v J. Crossley a MAE Dummett (eds.) 1965: 92–130.
• Krol, M., 1978, „Topologický model intuitívnej analýzy s Kripkeho schémou“, Zeitschrift für Math. Logik und Grundlagen der Math., 24: 427 - 436.
• Leivant, D., 1979, „Maximalita intuitívnej logiky“, Mathematical Center Tracts 73, Mathematisch Centrum, Amsterdam.
• –––, 1985, „Syntaktické preklady a preukázateľne rekurzívne funkcie“, Journal of Symbolic Logic, 50: 682–688.
• Läuchli, H., 1970, „Abstraktný pojem realizovateľnosti, pre ktorý je intuitívny predikátový počet úplný“, v A. Kino et al. (eds.) 1965: 227 - 234.
• Lifschitz, V., 1979, „CT (_ 0) je silnejší ako CT (_ 0) !,“Zborník American Mathematical Society, 73 (1): 101–106.
• Mancosu, P., 1998, od Brouwera k Hilbertovi: Debata o základoch matematiky v 20. rokoch 20. storočia, New York a Oxford: Oxford University Press.
• Martin-Löf, P., 1984, Intuionistická teória typov, Poznámky Giovanniho Sambina k sérii prednášok, ktoré sa konali v Padove v júni 1980, Napoli: Bibliopolis.
• Mints, G., 2012, „Preklady intuitívnych výrokových receptov Gödel – Tarski,“v Správne zdôvodnenie (Lecture Notes in Computer Science 7265), E. Erdem a kol. (eds.), Dordrecht: Springer-Verlag: 487 - 491.
• Moschovakis, JR, 1971, „Nemôžu existovať žiadne neregulované funkcie?“Journal of Symbolic Logic, 36: 309–315.
• –––, 2003, „Klasické a konštruktívne hierarchie v rozšírenej intuicionistickej analýze“, Journal of Symbolic Logic, 68: 1015–1043.
• ––– 2009, „Logika Brouwera a Heytinga“v Logic od Russella po Cirkev (Handbook of History of Logic, Zväzok 5), J. Woods a D. Gabbay (ed.), Amsterdam: Elsevier: 77 -125.
• ––– 2017, „Intuitionistická analýza a koniec času“, Bulletin of Symbolic Logic, 23: 279–295.
• Nelson, D., 1947, „Rekurzívne funkcie a intuitionistická teória čísel“, Transactions of American Mathematical Society, 61: 307–368.
• Nishimura, I., 1960, „O vzorcoch jednej premennej v intuicionálnom výrokovom počte“, Journal of Symbolic Logic, 25: 327–331.
• van Oosten, J., 1991, „Sémantický dôkaz de Jonghovej vety“, Archives for Mathematical Logic, 31: 105–114.
• ––– 2002, „Realizovateľnosť: historická esej“, Matematické štruktúry v informatike, 12: 239–263.
• –––, 2008, Realizovateľnosť: Úvod do kategorickej stránky, Amsterdam: Elsevier.
• Plisko, VE, 1992, „O aritmetickej zložitosti určitej konštruktívnej logiky“, Mathematical Notes, (1993): 701–709. Preložené z Matematicheskie Zametki, 52 (1992): 94–104.
• Rasiowa, H., 1974, Algebraický aptát na neklasickú logiku, Amsterdam: Severný Holland.
• Rasiowa, H. a Sikorski, R., 1963, Matematika metamatematiky, Varšava: Panstwowe Wydawnictwo Naukowe.
• Rathjen, M., 2006, „Realizovateľnosť pre konštruktívnu teóriu množín Zermelo-Fraenkel,“v Logic Colloquium 2003 (Poznámky k prednáške v Logic 24), J. Väänänen et al. (eds.), AK Peters 2006: 282 - 314.
• ––– 2012, „Od slabosti k silnému existenčnému majetku“, Annals of Pure and Applied Logic, 163: 1400–1418.
• Rose, GF, 1953, „Propozičný počet a realizovateľnosť“, Transactions of American Mathematical Society, 75: 1-19.
• Rybakov, V., 1997, Prípustnosť pravidiel logického dedukcie, Amsterdam: Elsevier.
• Scott, D., 1968, „Rozšírenie topologickej interpretácie na intuicionálnu analýzu,“Compositio Mathematica, 20: 194-210.
• Smorynski, CA, 1973, „Aplikácia Kripkeho modelov“, v Troelstra (ed.) 1973: 324–391.
• Spector, C., 1962, „Dočasne rekurzívne funkcionality analýzy: dôkaz konzistencie analýzy rozšírením princípov formulovaných v súčasnej intuicionistickej matematike,“Teória rekurzívnej funkcie: Postupy sympózií v čistej matematike, zväzok 5, JCE Dekker (ed.), Providence, RI: American Mathematical Society, 1-27.
• van Stigt, WP, 1990, Brouwer's Intuitionism, Amsterdam: North-Holland.
• Stone, MH, 1937, „Topologické znázornenie distribučných mriežok a brouwerovskej logiky“, Casopis Pest. Mat. Fys. 67: 1-25.
• Tarski, A., 1938, „Der Aussagenkalkül und die Topologie“, Fundamenta Mathematicae, 31: 103–104.
• Troelstra, AS, 1991, „Dejiny konštruktivizmu v dvadsiatom storočí“, séria publikácií ITLI ML – 1991–05, Amsterdam. Finálna verzia v Teórii množín, aritmetike a základoch matematiky (prednášky v logike 36), J. Kenney a R. Kossak (ed.), Asociácia pre symbolickú logiku, Ithaca, NY, 2011: 150–179.
• –––, 1998, „Realizability“, kapitola VI of Buss (ed.), 1998: 407–473.
• –––, úvodná poznámka k roku 1958 a 1972, v Gödel, 1990: 217–241.
• Troelstra, AS (ed.), 1973, Metamathematical Research of Intuitionistic Aritmetic and Analysis (Lecture Notes in Mathematics 344), Berlin: Springer-Verlag. Opravy a doplnky sú k dispozícii od editora.
• Troelstra, AS a Schwichtenberg, H., 2000, základná teória korektúry (Cambridge Tracts v teoretickej informatike: zväzok 43), 2. vydanie, Cambridge: Cambridge University Press.
• Troelstra, AS a van Dalen, D., 1988, Konštruktivizmus v matematike: Úvod, 2 zväzky, Amsterdam: North-Holland Publishing. [Pozri tiež Opravy, v časti Iné internetové zdroje.]
• Troelstra, AS a van Dalen, D. (ed.), 1982, Sté sympózium Brouwera na sté výročie, Amsterdam: North-Holland Publishing.
• Veldman, W., 1976, „intuicionálna veta o úplnosti pre intuicionálnu predikátovú logiku“, Journal of Symbolic Logic, 41: 159–166.
• –––, 1990, „Prehľad intuicionálnej deskriptívnej teórie množín“, v PP Petkov (ed.), Mathematical Logic, Proceedings of Heyting Conference, New York and London: Plenum Press, 155–174.
• –––, 2005, „Dva jednoduché súbory, ktoré nie sú pozitívne Borel,“Annals of Pure and Applied Logic, 135: 151–209.
• Vesley, RE, 1972, „Výberové sekvencie a Markovov princíp“, Compositio Mathematica, 24: 33–53.
• –––, 1970, „Chutná alternatíva Kripkeho schémy“, v A. Kino a kol. (eds.) 1970: 197 a ďalšie.
• Visser, A., 1999, „Rule and aritmetics“, Notre Dame Journal of Formal Logic, 40: 116-140.
• –––, 2002, „Striedanie viet (Sigma ^ {0} _1): prieskumy medzi intuicionálnou výrokovou logikou a intuicionálnou aritmetikou,“Annals of Pure and Applied Logic, 114: 227–271.
• ––– 2006, „Predikátová logika konštruktívnych aritmetických teórií“, Journal of Symbolic Logic, 72: 1311–1326.

Akademické nástroje

	Ako citovať tento záznam.
	Ukážku verzie tohto príspevku vo formáte PDF si môžete pozrieť na stránke Friends of the SEP Society.
	Vyhľadajte túto vstupnú tému v projekte Internet Philosophy Ontology Project (InPhO).
	Vylepšená bibliografia tohto záznamu vo PhilPapers s odkazmi na jeho databázu.

Ďalšie internetové zdroje

• Bezhanishvili, G. a Holliday, W., 2018, „Sémantická hierarchia pre intuicionistickú logiku“, rukopis, publikácie UC Berkeleyovej fakulty.
• Bezhanishvili, N. a de Jongh, DHJ, 2005, Intuitionistic Logic, Prednáškové listy prezentované na ESSLLI, Edinburgh.
• Brouwer, Výňatky z Brouwerových prednášok v Cambridge.
• Citkin, A., 2016, „Dedične štruktúrne úplné superintuitionistické deduktívne systémy,“rukopis na arXiv.org.
• Mincovne, G., Olkhovikov, G. a Urquhart, A., 2012, „Zlyhanie interpolácie v intuicionálnej logike konštantných domén“, rukopis, arXiv.org.
• Troelstra, AS a JR Moschovakis, 2018, Opravy AS Troelstra a D. van Dalena, 1988, Konštruktivizmus v matematike.
• Problémy v logike preukázateľnosti, udržiavané Levom Beklemishevom.
• Realizability Bibliography, spravuje Lars Birkedal.
• van Oosten 2000 a ďalšie predtlače súvisiace s realizovateľnosťou, ktoré udržoval Jaap van Oosten.