Intuitionistisk Logik

Innehållsförteckning:

Intuitionistisk Logik
Intuitionistisk Logik
Anonim

Inmatningsnavigering

  • Inmatningsinnehåll
  • Bibliografi
  • Akademiska verktyg
  • Vänner PDF-förhandsvisning
  • Författare och Citation Info
  • Tillbaka till toppen

Intuitionistisk logik

Först publicerad ons 1 september 1999; substantiell revidering tis 4 september 2018

Intuitionistisk logik omfattar de allmänna principerna för logisk resonemang som har abstraherats av logiker från intuitionistisk matematik, som utvecklats av LEJ Brouwer från och med hans [1907] och [1908]. Eftersom dessa principer också gäller för rysk rekursiv matematik och den konstruktiva analysen av E. Bishop och hans följare, kan intuitionistisk logik betraktas som den logiska grunden för konstruktiv matematik. Även om intuitionistisk analys står i konflikt med klassisk analys, är intuitionistisk Heyting-aritmetik ett delsystem för klassisk Peano-aritmetik. Av detta följer att intuitionistisk propositionslogik är ett ordentligt delsystem för klassisk propositionlogik, och ren intuitionistisk predikatlogik är ett ordentligt undersystem av ren klassisk predikatlogik.

Filosofiskt skiljer sig intuitionismen från logik genom att behandla logik som en del av matematiken snarare än som grunden för matematik; från finitismgenom att tillåta konstruktivt resonemang om oräkneliga strukturer (t.ex. monotonstångsinduktion på trädet av potentiellt oändliga sekvenser med naturligt antal) och från platonismen genom att betrakta matematiska föremål som mentala konstruktioner utan någon oberoende idealisk existens. Hilberts formalistiska program, för att rättfärdiga klassisk matematik genom att reducera det till ett formellt system vars konsistens borde fastställas med finitistiska (följaktligen konstruktiva) medel, var den mest kraftfulla samtida rival till Brouwer utvecklande intuitionism. I sitt essä från 1912 förutspådde Brouwer korrekt att varje försök att bevisa konsistensen av fullständig induktion på de naturliga siffrorna skulle leda till en ond cirkel.

Brouwer avvisade formalism i sig men medgav den potentiella nyttan av att formulera allmänna logiska principer som uttrycker intuitionistiskt korrekta konstruktioner, till exempel modus ponens. Formella system för intuitionistiska propositioner och predikatlogik och aritmetik utvecklades helt av Heyting [1930], Gentzen [1935] och Kleene [1952]. Gödel [1933] bevisade ekvivalent med intuitionistiska och klassiska teorier. Beth [1956] och Kripke [1965] tillhandahöll semantik med avseende på vilken intuitionistisk logik är korrekt och fullständig, även om fullständiga bevis för intuitionistiska predikatlogik kräver vissa klassiska resonemang.

  • 1. Avslag på Tertium Non Datur
  • 2. Intuitionistisk första ordningens predikatlogik

    • 2.1 De formella systemen (mathbf {H – IPC}) och (mathbf {H – IQC})
    • 2.2 Alternativa formaliteter och avdragssats
  • 3. Intuitionistic Number Theory (Heyting Arithmetic) (mathbf {HA})
  • 4. Grundläggande bevisteori

    • 4.1 Översättning av klassisk till intuitionistisk logik
    • 4.2 Tillåtliga regler för intuitionistisk logik och aritmetik
  • 5. Grundläggande semantik

    • 5.1 Kripke semantik för intuitionistisk logik
    • 5.2 Realiserbarhetssemantik för Heyting aritmetik
  • 6. Ytterligare ämnen och vidare läsning

    • 6.1 Subintuitionistisk och mellanliggande logik
    • 6.2 Avancerade ämnen
    • 6.3 Rekommenderad läsning
  • Bibliografi
  • Akademiska verktyg
  • Andra internetresurser
  • Relaterade poster

1. Avslag på Tertium Non Datur

Intuitionistisk logik kan beskrivas kortfattat som klassisk logik utan den aristoteliska lagen i den uteslutna mitten:

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

eller den klassiska lagen om eliminering av dubbel negation:

(tag {DNE} neg / neg A / högermark A)

men med motsägelselagen:

[(A / höger pil B) höger höger ((A / höger pil / neg B) höger höj / neg A))

och ex falso sequitur quodlibet:

(neg A / höger pil (A / höger pil B).)

Brouwer [1908] observerade att LEM abstraherades från ändliga situationer och utvidgades sedan utan motivering till uttalanden om oändliga samlingar. Till exempel, låt (x, y) sträcka sig över de naturliga siffrorna (0, 1, 2, / ldots) och låt (B (y)) förkorta ((primepred (y) oldand / primepred (y + 2))), där (primepred (y)) uttrycker "(y) är ett primtal." Sedan håller (forall y (B (y) vee / neg B (y))) intuitionistiskt såväl som klassiskt, för för att avgöra om ett naturligt tal är prim eller inte behöver vi bara kontrollera om det inte är har en delare strikt mellan sig och 1.

Men om (A (x)) förkortar (existerar y (y / gt x / oldand B (y))), för att hävda (allall x (A (x) vee / neg En (x))) intuitionistiskt skulle vi behöva en effektiv (jfr. Church-Turing-avhandlingen) metod för att avgöra om det finns ett par tvillingprimar större än ett godtyckligt naturligt tal (x), och hittills ingen sådan metod är känd. En uppenbar halveffektiv metod är att lista primtalspar med hjälp av en förfining av Eratosthenes-sikt (generera de naturliga siffrorna en efter en och slå ut alla siffror (y) som inte uppfyller (B (y)))), och om det finns ett par tvillingprimar som är större än (x) hittar den här metoden så småningom den första. Emellertid uttrycker (allall x A (x)) tvillingprimalkonjunkturen, som ännu inte har bevisats eller avvisats,så i det nuvarande läget av vår kunskap kan vi hävda varken (för alla x (A (x) vee / neg A (x))) eller (forall x A (x) vee / neg / forall x Yxa)).

Man kan göra invändningar mot att dessa exempel beror på det faktum att tvillingprimsförståelsen ännu inte har avgjorts. Ett antal av Brouwer's ursprungliga”motexempel” berodde på problem (som Fermats sista sats) som sedan har lösts. Men för Brouwer var det allmänna LEMet likvärdigt med det a priori antagandet att varje matematiskt problem har en lösning - ett antagande som han förkastade och förutsåg Gödels ofullständighetsteorem med ett kvart århundrade.

Avvisningen av LEM har långtgående konsekvenser. Å ena sidan,

  • Intuitionistiskt bevisar reductio ad absurdum endast negativa uttalanden, eftersom (neg / neg A / högermark A) inte rymmer i allmänhet. (Om det gjorde det, skulle LEM följa med modusponens från det intuitionistiskt bevisbara (neg / neg (A / vee / neg A)).)
  • Den intuitionistiska propositionella logiken har ingen begränsad sanningsbordstolkning. Det finns oändligt många distinkta axiomatiska system mellan intuitionistisk och klassisk logik.
  • Inte varje förslagsformel har en intuitionistiskt ekvivalent disjunktiv eller konjunktiv normalform, byggd av primära formler och deras negationer med bara (vee) och (oldand).
  • Inte varje predikatformel har en intuitionistiskt ekvivalent prenex normalform, med alla kvantifierare framtill.
  • Medan (forall x / neg / neg (A (x) vee / neg A (x))) är ett ställe för intuitionistisk predikatlogik, (neg / neg / forall x (A (x) vee / neg A (x))) är inte; så (neg / forall x (A (x) vee / neg A (x))) överensstämmer med intuitionistiska predikatlogik.

Å andra sidan,

  • Varje intuitionistiskt bevis på ett slutet uttalande av formen (A / vee B) kan omvandlas till ett intuitionistiskt bevis på (A) eller ett intuitionistiskt bevis på (B), och på liknande sätt för stängda existentiella uttalanden.
  • Intuitionistisk propositionslogik är effektivt avgörbar, i den meningen att en ändlig konstruktiv process tillämpas enhetligt på varje propositionformel, antingen producerar ett intuitionistiskt bevis på formeln eller visar att inget sådant bevis kan existera.
  • Det negativa fragmentet av intuitionistisk logik (utan (vee) eller (exist)) innehåller en trogen översättning av klassisk logik, och på liknande sätt för intuitionistisk och klassisk aritmetik.
  • Intuitionistisk aritmetik kan konsekvent utvidgas med axiomer som motsäger klassisk aritmetik, vilket möjliggör den formella studien av rekursiv matematik.
  • Brouwer's kontroversiella intuitionistiska analys, som strider mot LEM, kan formaliseras och visas konsekvent i förhållande till en klassisk och intuitionistiskt korrekt underteori.

2. Intuitionistisk första ordningens predikatlogik

Formaliserad intuitionistisk logik motiveras naturligtvis av den informella Brouwer-Heyting-Kolmogorov-förklaringen om intuitionistisk sanning, som beskrivs i inläggen om intuitionism i matematikfilosofin och utvecklingen av intuitionistisk logik. Den konstruktiva oberoende av de logiska operationerna (oldand, / vee, / rightarrow, / neg, / forall, / exist) står i kontrast till den klassiska situationen, där t.ex. (A / vee B) motsvarar (neg (neg A / oldand / neg B)), och (existerar xA (x)) motsvarar (neg / forall x / neg A (x)). Från BHK-synvinkel hävdar en mening med formen (A / vee B) att antingen ett bevis på (A) eller ett bevis på (B) har konstruerats;medan (neg (neg A / oldand / neg B)) hävdar att en algoritm har konstruerats som effektivt konverterar alla konstruktionspar som bevisar (neg A) respektive (neg B), till ett bevis på en känd motsägelse.

2.1 De formella systemen (mathbf {H – IPC}) och (mathbf {H – IQC})

Följande är en formalism i Hilbert-stil (mathbf {H – IQC}) från Kleene [1952] (jfr. Troelstra och van Dalen [1988]) för intuitionistisk första ordningens predikatlogik. Språket (L) för (mathbf {H – IQC}) har predikatbokstäver (P, Q (.), / Ldots) för alla ariteter och enskilda variabler (x, y, z, / ldots) (med eller utan abonnemang (1, 2, / ldots)), liksom symboler (oldand, / vee, / rightarrow, / neg, / forall, / exist) för de logiska anslutningarna och kvantifierare och parenteser (,). De atomiska (eller primära) formlerna för (L) är uttryck som (P, Q (x), R (x, y, x)) där (P, Q ({.}), R ({.} {.} {.})) är (0) - ary, (1) - ary och (3) - ary predikat bokstäver respektive; det vill säga att resultatet av att fylla varje ämne i en predikatbokstav med en enskild variabel symbol är en huvudformel. De (välformade) formlerna för (L) definieras induktivt enligt följande.

  • Varje atomformel är en formel.
  • Om (A) och (B) är formler, så är ((A / oldand B), (A / vee B), (A / högermark B)) och (neg A).
  • Om (A) är en formel och (x) är en variabel är (för alla xA) och (existerar xA) formler.

I allmänhet använder vi (A, B, C) som metavariabler för välformerade formler och (x, y, z) som metavariabler för enskilda variabler. Att förutse applikationer (till exempel till intuitionistisk aritmetik) använder vi (s, t) som metavariabler för termer; när det gäller ren predikatlogik är termer helt enkelt enskilda variabler. En förekomst av en variabel (x) i en formel (A) är bunden om den ligger inom ramen för en kvantifierare (forall x) eller (existerar x), annars gratis. Intuitionistiskt lika klassiskt, ((A / leftrightarrow B)) förkortar (((A / högermark B) oldand (B / högermark A))), och parenteser kommer att utelämnas när detta orsakar ingen förvirring.

Det finns tre regler för slutsatser:

Modus Ponens

Från (A) och (A / högermark B), avslut (B).

(forall) - Introduktion

Från (C / högermark A (x)), där (x) är en variabel som inte förekommer fritt i (C), sluta (C / högermark / forall x A (x)).

(exist) - Eliminering

från (A (x) högermark C), där (x) är en variabel som inte förekommer fritt i (C), sluta (exist x A (x) höger pil C).

Axiomerna är alla formler för följande former, där underformerna (A (t)) i de två senaste schemaen är resultatet av att en förekomst av termen (t) ersätter varje fri förekomst av (x) i (A (x)), och ingen variabel fri i (t) blir bunden i (A (t)) som ett resultat av substitutionen.

(börja {array} {l} A / höger pil (B / höger pil A) (A / höger pil B) höger pil ((A / höger höger (B / höger pil C)) höger pil (A / höger höger C)) / A / högerpil (B / högermark (A / oldand B)) (A / oldand B) högermark A \(A / oldand B) högermark B \\ A / högermark (A / vee B) / B / höger pil (A / vee B) (A / höger pil C) höger pil ((B / höger pil C) höger pil ((A / vee B) höger pil C)) (A / höger pil B) höger pil ((A / höger pil / neg B) höger pil / neg A) / \ neg A / höger pil (A / höger pil B) / \ för alla xA (x) höger pil A (t) / A (t) höger pil / existerar xA (x) slut {array})

Ett bevis är varje ändlig sekvens med formler, som var och en är en axiom eller en omedelbar följd av en slutsregel av (en eller två) föregående formler i sekvensen. Varje bevis sägs bevisa sin sista formel, som kallas ett ställe eller bevisbar formel för första ordningens intuitionistiska predikatlogik. En härledning av en formel (E) från en samling (F) av antaganden är vilken formel som helst, som var och en tillhör (F) eller är ett axiom eller en omedelbar följd av en slutsregel, av föregående formler i sekvensen, så att (E) är den sista formeln i sekvensen. Om en sådan härledning finns, säger vi (E) är härledd från (F).

Intuitionistisk förslagslogik (mathbf {H – IPC}) är delsystemet till (mathbf {H – IQC}) som resulterar när språket är begränsat till formler byggda från propositionbokstäver (P, Q, R, / ldots) med hjälp av de propositionella anslutningarna (oldand, / vee, / rightarrow) och (neg), och endast de propositionella postulaten används. Således saknas de två sista inferensreglerna och de två sista axiomskemorna från det propositionella delsystemet.

Om lagen som uttrycker ex falso sequitur quodlibet i den givna listan över axiomscheman för intuitionistiska propositioner eller första ordningens predikatlogik:

(neg A / höger pil (A / höger pil B))

ersätts av den klassiska lagen om eliminering av dubbelnegation DNE:

(neg / neg A / högermark A)

(eller, likvärdigt, om den intuitionistiska lagen om negation introduktion:

[(A / höger pil B) höger höger ((A / höger pil / neg B) höger höj / neg A))

ersätts av LEM), ett formellt system (mathbf {H – CPC}) för klassisk propositionslogik eller (mathbf {H – CQC}) för klassiska predikatlogikresultat. Eftersom ex falso och motsägelselagen är klassiska teorem, finns intuitionistisk logik i klassisk logik. På ett sätt finns klassisk logik också i intuitionistisk logik; se avsnitt 4.1 nedan.

Det är viktigt att notera att även om LEM och DNE är likvärdiga som scheman över (mathbf {H – IPC}), innebär implikationen

[(neg / neg A / högermark A) högermark (A / vee / neg A))

är inte ett teoremschema för (mathbf {H – IPC}). För teorier (mathbf {T}) baserat på intuitionistisk logik, om (E) är en godtycklig formel för (L (mathbf {T})), då per definition:

(E) kan avgöras i (mathbf {T}) om och bara om (mathbf {T}) bevisar (E / vee / neg E).

(E) är stabil i (mathbf {T}) om och bara om (mathbf {T}) bevisar (neg / neg E / högermark E).

(E) är testbar i (mathbf {T}) om och bara om (mathbf {T}) bevisar (neg E / vee / neg / neg E).

Avgörbarhet innebär stabilitet, men inte omvänt. Konjunktionen av stabilitet och testbarhet motsvarar beslutbarhet. Brouwer själv bevisade att”absurditet av absurditet av absurditet motsvarar absurditet” (Brouwer [1923C]), så varje formel i formen (neg A) är stabil; men i (mathbf {H – IPC}) och (mathbf {H – IQC}) primärformler och deras negationer kan inte avvisas, vilket visas i avsnitt 5.1 nedan.

2.2 Alternativa formaliteter och avdragssats

Systemet Hilbert-stil (mathbf {H – IQC}) är användbart för metamatematiska undersökningar av intuitionistisk logik, men dess tvingade linjärisering av avdrag och dess preferens för axiomer framför regler gör det till ett besvärligt instrument för att fastställa derivabilitet. Ett naturligt avdragssystem (mathbf {N – IQC}) för intuitionistiska predikatlogikresultat från det deduktiva systemet (mathbf {D}), presenterat i avsnitt 3 i posten om klassisk logik i denna encyklopedi, genom att utelämna symbolen och reglerna för identitet och ersätta den klassiska regeln (DNE) om eliminering av dubbel negation med den intuitionistiska eliminationsregeln som uttrycker ex falso:

(INE) Om (F) medför (A) och (F) innebär (neg A), då (F) innebär (B)

Nycklarna för att bevisa att (mathbf {H – IQC}) är ekvivalent med (mathbf {N – IQC}) är modusponens och dess konversation, den:

Avdragssats

om (B) kan härledas från (A) och eventuellt andra formler (F), med alla variabler som är fria i (A) som hålls konstant i härledningen (det vill säga utan att använda den andra eller tredje inferensregeln för någon variabel (x) som förekommer fritt i (A), såvida inte antagandet (A) inte förekommer i härledningen före inferensen i fråga), (A / högermark B) kan härledas från (F).

Detta grundläggande resultat, som grovt uttrycker regeln ((högermark I)) för (mathbf {I}), kan bevisas för (mathbf {H – IQC}) genom induktion av definitionen av en härledning. De andra reglerna för (mathbf {I}) gäller för (mathbf {H – IQC}) väsentligen genom modusponens, vilket motsvarar ((höger E)) i (mathbf {N -IQC}); och alla axiomerna till (mathbf {H – IQC}) är bevisbara i (mathbf {N – IQC}).

För att illustrera användbarheten av Avdragssatsen, tänk på (uppenbarligen triviala) teoremschemat ((A / högermark A)). Ett korrekt bevis i (mathbf {H – IPC}) tar fem rader:

  • 1. (A / höger pil (A / höger höger A))
  • 2. ((A / höger pil (A / höger höger A)) höger pil ((A / höger höger ((A / höger höger A) höger höger A)) höger höger (A / höger höger A)))
  • 3. ((A / höger pil ((A / höger höger A) höger höger A)) höger höger (A / höger höger A))
  • 4. (A / höger pil ((A / höger höger A) höger höger A))
  • 5. (A / högermark A)

där 1, 2 och 4 är axiomer och 3, 5 kommer från tidigare linjer med modus ponens. Emellertid är (A) härledd från (A) (som antagande) i ett uppenbart steg, så Deduktionsteoremet tillåter oss att dra slutsatsen att ett bevis på (A / högermark A) finns. (Faktum är att det formella beviset för (A / högermark A) som just presenterades är en del av det konstruktiva beviset för avdragssatsen!

Det är viktigt att notera att i definitionen av en härledning från antaganden i (mathbf {H – IQC}) behandlas antagandeformlerna som om alla deras fria variabler var universellt kvantifierade, så att (forall x A (x)) kan härledas från hypotesen (A (x)). Men variabeln (x) kommer att varieras (inte hållas konstant) i det här avledningen med hjälp av regeln för (forall) - introduktion; och så kan inte avdragssatsen användas för att dra slutsatsen (falskt) att (A (x) högermark / för alla x A (x)) (och därmed av (exist) - eliminering, (exist x A (x) högermark / för alla x A (x))) kan visas i (mathbf {H – IQC}). Som ett exempel på en korrekt användning av avdragssatsen för predikatlogik, överväg implikationen (existerar x A (x) högermark / neg / forall x / neg A (x)). För att visa detta kan provas i (mathbf {H – IQC}),vi härleder först (neg / forall x / neg A (x)) från (A (x)) med alla fria variabler som hålls konstant:

  • 1. (för alla x / neg A (x) högermark / neg A (x))
  • 2. (A (x) höger pil (för alla x / neg A (x) höger pil A (x)))
  • 3. (A (x)) (antagande)
  • 4. (för alla x / neg A (x) höger höger A (x))
  • 5. ((för alla x / neg A (x) höger pil A (x)) höger pil ((för alla x / neg A (x) höger höj / neg A (x)) höger höj / neg / för alla x / neg A (x)))
  • 6. ((allall x / neg A (x) högermark / neg A (x)) högermark / neg / forall x / neg A (x))
  • 7. (neg / forall x / neg A (x))

Här är 1, 2 och 5 axiomer; 4 kommer från 2 och 3 av modus ponens; och 6 och 7 kommer från tidigare linjer med modus ponens; så inga variabler har varierats. Avdragssatsen säger att det finns ett bevis (P) i (mathbf {H – IQC}) för (A (x) högermark / neg / forall) x (neg A (x)) och en applikation av (existerar) - eliminering konverterar (P) till ett bevis på (finns x A (x) högermark / neg / forall x / neg A (x)). Det konverserade är inte bevisbart i (mathbf {H – IQC}), som visas i avsnitt 5.1 nedan.

Andra viktiga alternativ till (mathbf {H – IQC}) och (mathbf {N – IQC}) är de olika sekvensberäkningarna för intuitionistiska förslag och predikatlogik. Den första sådana beräkningen definierades av Gentzen [1934–5], jfr. Kleene [1952]. Sekventiella system, som bevisar exakt samma formler som (mathbf {H – IQC}) och (mathbf {N – IQC}), följer uttryckligen alla antaganden och slutsatser vid varje steg i ett bevis, och ersätter modus ponens (som eliminerar en mellanliggande formel) med en skärningsregel (som kan visas som en tillåten regel (jfr avsnitt 4.2) för delsystemet som är kvar när det utelämnas).

När detaljerna om formalismen inte är viktig följer vi från och med Troelstra och van Dalen [1988] för att låta "(mathbf {IQC})" eller "(mathbf {IPC})" hänvisa till någon formellt system för intuitionistisk predikat respektive propositionslogik, och på liknande sätt "(mathbf {CQC})" och "(mathbf {CPC})" för klassisk predikat och propositionlogik.

Både (mathbf {IPC}) och (mathbf {IQC}) uppfyller interpoleringsteorem, t.ex.: Om (A) och (B) är propositioner med minst en propositionbok gemensamt, och om (A / högermark B) kan visas i (mathbf {IPC}), finns det en formel (C), som endast innehåller propositionbokstäver som förekommer i både (A) och (B), så att både (A / höger pil C) och (C / höger pil B) är bevisbara. Dessa ämnen behandlas i Kleene [1952] och Troelstra och Schwichtenberg [2000].

Medan identitet naturligtvis kan läggas till intuitionistisk logik, för tillämpningar (t.ex. till aritmetik) behandlas likhetssymbolen i allmänhet som ett utmärkt predikatskonstant som tillfredsställer axiomen för en ekvivalensrelation (reflexivitet, symmetri och transitivitet) och ytterligare icke-logiska axiomer (t.ex., de primitiva rekursiva definitionerna av tillsats och multiplikation). Identitet är avgörbar, intuitionistiskt såväl som klassiskt, men intuitionistisk extensional jämlikhet är inte alltid avgörbar; se diskussionen om Brouwer's kontinuitetsaxiomer i avsnitt 3 i posten om intuitionism i matematikfilosofin.

3. Intuitionistic Number Theory (Heyting Arithmetic) (mathbf {HA})

Intuitionistiska (Heyting) aritmetiska (mathbf {HA}) och klassiska (Peano) aritmetiska (mathbf {PA}) delar samma första ordningsspråk och samma icke-logiska axiomer; bara logiken är annorlunda. Förutom de logiska anslutningarna, kvantifierare och parenteser och de enskilda variablerna (x, y, z, / ldots) (även används som metavariabler) har språket (L (mathbf {HA})) för aritmetik en binär predikatsymbol (=), individuell konstant (0), unär funktionskonstant (S), och ändligt eller oändligt oändligt många ytterligare konstanter för primitiva rekursiva funktioner inklusive tillägg och multiplikation; det exakta valet är en fråga om smak och bekvämlighet. Termer bygger på variabler och (0) med funktionskonstanter; särskilt,varje naturligt tal (n) uttrycks i språket med siffran (mathbf {n}) erhållen genom att använda (S) (n) gånger på (0) (t.ex. (S (S (0))) är siffran för (2)). Prime-formler har formen ((s = t)) där (s, t) är termer, och sammansatta formler erhålls från dessa som vanligt.

De logiska axiomerna och reglerna för (mathbf {HA}) är de för första ordningens intuitionistiska predikatlogik (mathbf {IQC}). De icke-logiska axiomerna inkluderar de reflexiva, symmetriska och transitiva egenskaperna för (=): (för alla x (x = x),) (allall x / forall y (x = y / högermark y = x),) (allall x / forall y / forall z ((x = y / oldand y = z) höger pil x = z);) axiom som karakteriserar (0) som det minsta naturliga antalet:

(för alla x / neg (S (x) = 0),)

axiomen som karakteriserar (S) som en en-till-en-funktion:

(allall x / forall y (S (x) = S (y) höger pil x = y),)

den utvidgade jämställdhetsaxiom för (S):

(forall x / forall y (x = y / höger höger S (x) = S (y));)

de primitiva rekursiva definierande ekvationerna för varje funktionskonstant, speciellt för tillägg: (forall x (x + 0 = x),) (forall x / forall y (x + S (y) = S (x + y));) och multiplikation: (forall x (x / cdot 0 = 0),) (forall x / forall y (x / cdot S (y) = (x / cdot y) + x);) och (universal stängning av) schemat för matematisk induktion, för godtyckliga formler (A (x)):

[(A (0) oldand / forall x (A (x) högermark A (S (x)))) högermark / forall x A (x).)

Extensionella jämställdhetsaxiomer för alla funktionskonstanter kan härledas genom matematisk induktion från jämställdhetsaxiomen för (S) och de primitiva rekursiva funktionens axiomer.

Den naturliga ordningsrelationen (x / lt y) kan definieras i (mathbf {HA}) av (existerar z (S (z) + x = y)) eller med kvantifieringsfritt formel (S (x) punkt {-} y = 0) om symbolen och den primitiva rekursiva definierande ekvationerna för föregångaren: [Pd (0) = 0,) (för alla x (Pd (S (x)) = x)) och avstängningssubtraktion: (för all x (x / dot {-} 0 = 0),) (forall x (x / dot {-} S (y) = Pd (x / dot {-} y))) är närvarande i formalismen. (mathbf {HA}) bevisar den jämförande lagen

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

och en intuitionistisk form av principen med minst antal, för godtyckliga formler (A (x)):

(forall x (forall y (y / lt x / högerpil (A (y) vee / neg A (y))) högerpil \(existerar 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)))].)

Hypotesen behövs eftersom inte alla aritmetiska formler är avgörbara i (mathbf {HA}). Emellertid kan (forall x / forall y (x = y / vee / neg (x = y))) bevisas direkt genom matematisk induktion, och så

Prime-formler (och därmed alla kvantifieringsfria formler) är avgörbara och stabila i (mathbf {HA}).

Om (A (x)) kan avgöras i (mathbf {HA}), är det genom induktion på (x) så (för alla y (y / lt x / högermark A (y))) och (finns y (y / lt x / oldand A (y))). Därav

Formler där alla kvantifierare är begränsade är avgörbara och stabila i (mathbf {HA}).

Samlingen (Delta_0) av aritmetiska formler där alla kvantifierare är avgränsade är den lägsta nivån i en klassisk aritmetisk hierarki baserad på mönstret för växlingar av kvantifierare i en prenexformel. I (mathbf {HA}) har inte varje formel en prenexform, men Burr [2004] upptäckte en enkel intuitionistisk aritmetisk hierarki motsvarande nivå för nivå till det klassiska. Endast i de följande två definitionerna betecknar (allall x) ett block med slutligt många universella talkvantifierare, och på liknande sätt betecknar (exist x) ett block med slutligen många existentiella talkvantifierare. Med dessa konventioner definieras Burrs klasser (Phi_n) och (Psi_n) av:

  • (Phi_0 = / Psi_0 = / Delta_0),
  • (Phi_1) är klassen för alla formler i formen (allall x A (x)) där (A (x)) är i (Psi_0). För (n / ge 2) är (Phi_n) klassen för alla formler i formen (för alla x [A (x) högermark / finns y B (x, y)]) där (A (x)) är i (Phi_ {n-1}) och (B (x, y)) är i (Phi_ {n-2}),
  • (Psi_1) är klassen för alla formler i formen (existerar x A (x)) där (A (x)) finns i (Phi_0). För (n / ge 2) är (Psi_n) klassen för alla formler i formen (A / högermark B) där (A) är i (Phi_n) och (B) är i (Phi_ {n-1}).

Motsvarande klassiska prenexklasser definieras enklare:

  • (Pi_0 = / Sigma_0 = / Delta_0),
  • (Pi_ {n +1}) är klassen för alla formler i formen (för alla x A (x)) där (A (x)) är i (Sigma_n),
  • (Sigma_ {n +1}) är klassen för alla formler i formen (existerar x A (x)) där (A (x)) är i (Pi_n).

Peano aritmetic (mathbf {PA}) kommer från Heyting aritmetic (mathbf {HA}) genom att lägga till LEM eller (neg / neg A / högermark A) i listan över logiska axiomer, dvs av använder klassisk istället för intuitionistisk logik. Följande resultat gäller även i fragmenten av (mathbf {HA}) och (mathbf {PA}) med induktionsschemat begränsat till (Delta_0) formler.

Burrs sats:

  • Varje aritmetisk formel är sannolikt ekvivalent i (mathbf {HA}) till en formel i en av klasserna (Phi_n).
  • Varje formel i (Phi_n) är sannolikt ekvivalent i (mathbf {PA}) till en formel i (Pi_n) och omvänt.
  • Varje formel i (Psi_n) är sannolikt ekvivalent i (mathbf {PA}) till en formel i (Sigma_n) och omvänt.

(mathbf {HA}) och (mathbf {PA}) är bevisteoretiskt likvärdiga, vilket kommer att visas i avsnitt 4. Var och en kan (numeriskt) uttrycka sitt eget bevispredikat. Genom Gödels berömda inkompleten teorem, om (mathbf {HA}) är konsekvent, kan varken (mathbf {HA}) eller (mathbf {PA}) bevisa sin egen konsistens.

4. Grundläggande bevisteori

4.1 Översättning av klassisk till intuitionistisk logik

Ett grundläggande faktum om intuitionistisk logik är att den har samma konsistensstyrka som klassisk logik. För propositionell logik bevisades detta först av Glivenko [1929].

Glivenkos sats

En godtycklig propositionformel (A) är klassiskt bevisbar, om och bara om (neg / neg A) är intuitionistiskt bevisbar.

Glivenkos sats sträcker sig inte till predikatlogik, även om en godtycklig predikatformel (A) är klassiskt bevisbar om och bara om (neg / neg A) kan bevisas i intuitionistisk predikatlogik plus schemat "dubbel negationskift".

(tag {DNS} forall x / neg / neg B (x) högermark / neg / neg / forall x B (x))

Den mer sofistikerade negativa översättningen av klassiska till intuitionistiska teorier, oberoende av Gödel och Gentzen, associerar med varje formel (A) i språket (L) en annan formel (g (A)) (utan (vee) eller (existerar)), så att

  • (I) Klassisk predikatlogik visar (A / leftrightarrow g (A)).
  • (II) Intuitionistisk predikatlogik visar (g (A) leftrightarrow / neg / neg g (A)).
  • (III) Om klassisk predikatlogik bevisar (A), visar intuitionistisk predikatlogik (g (A)).

Beviset är okomplicerat från följande induktiva definition av (g (A)) (med Gentzens direkta översättning av implikation, snarare än Gödel i termer av (neg) och (oldand)):

(börja {align *} g (P) & / text {är} neg / neg P, / text {if} P / text {är prime}. \\ g (A / oldand B) & / text { är} g (A) oldand g (B). \\ g (A / vee B) & / text {är} neg (neg g (A) oldand / neg g (B)). \\ g (A / höger pil B) & / text {är} g (A) höger pil g (B). \\ g (neg A) & / text {är} neg g (A). \\ g (forall xA (x)) & / text {är} forall xg (A (x)). \\ g (finns xA (x)) & / text {är} neg / forall x / neg g (A (x)). / End {align *})

För varje formel (A) är (g (A)) bevisbart intuitionistiskt om och bara om (A) är klassiskt bevisbart. I synnerhet om (B / oldand / neg B) klassiskt kunde bevisas för någon formel (B), då (g (B) oldand / neg g (B)) (vilket är (g (B / oldand / neg B))) skulle i sin tur vara bevisbar intuitionistiskt. Därav

(IV) Klassisk och intuitionistisk predikatlogik är likvärdiga

Den negativa översättningen av klassisk till intuitionistisk talteori är ännu enklare, eftersom de främsta formlerna för den intuitionistiska aritmetiken är stabila. Således kan (g (s = t)) anses vara (s = t), och de andra klausulerna är oförändrade. Den negativa översättningen av alla instanser av matematisk induktion är ett annat exempel på matematisk induktion, och de andra icke-logiska axiomerna för aritmetik är deras egna negativa översättningar, så

(I), (II), (III) och (IV) gäller också för talteori

Gödel [1933e] tolkade dessa resultat som att visa att intuitionistisk logik och aritmetik är rikare än klassisk logik och aritmetik, eftersom den intuitionistiska teorin skiljer formler som är klassiskt ekvivalenta och har samma konsistensstyrka som den klassiska teorin. Speciellt gäller Gödels ofullständighetsteorem för (mathbf {HA}) såväl som (mathbf {PA}).

Direkta försök att utvidga den negativa tolkningen till analys misslyckas eftersom den negativa översättningen av det räknbara axiom som valts inte är ett teorem för intuitionistisk analys. Det överensstämmer emellertid med den intuitionistiska analysen, inklusive Brouwer's kontroversiella kontinuitetsprincip, genom den funktionella versionen av Kleens rekursiva realiserbarhet (se avsnitt 6.2 nedan). Av detta följer att intuitionistisk matematik, som bara kan uttryckas genom att använda alla standardlogiska anslutningar och kvantifierare, är förenlig med en trogen översättning av klassisk matematik som undviker (vee) och (exist).

Detta är viktigt eftersom Brouwer: s intuitionistiska analys är inkonsekvent med LEM. Men om (A) är någon negativ formel (utan (vee) eller (exist)) så kan (neg / neg A / högermark A) bevisas med intuitionistisk logik. En försoning av intuitionistisk och klassisk analys enligt dessa linjer, inspirerad av Kripkes uppfattning om valföljd, föreslås i Moschovakis [2017].

4.2 Tillåtliga regler för intuitionistisk logik och aritmetik

Gödel [1932] konstaterade att den intuitionistiska propositionella logiken har skillnadsegenskapen:

(DP) Om (A / vee B) är ett teorem, är (A) ett teorem eller (B) är ett teorem

Gentzen [1935] etablerade skillnadsegenskapen för slutna formler för intuitionistisk predikatlogik. Av detta följer att om intuitionistisk logik är konsekvent så är (P / vee / neg P) inte ett teorem om (P) är en atomformel. Kleene [1945, 1952] bevisade att den intuitionistiska första ordningens nummerteori också har den relaterade (jfr Friedman [1975]) existensegenskapen:

(EP) Om (existerar x A (x)) är en stängd teorem, är för en stängd term (t), (A (t)) ett teorem

Egenskaperna för disjunktion och existens är speciella fall av ett allmänt fenomen som är speciellt för icke-klassiska teorier. Teoriens tillåtna regler är de regler under vilka teorin är stängd. Till exempel observerade Harrop [1960] att regeln

Om (neg A / högermark (B / vee C)) är ett ställe, så är ((neg A / högermark B) vee (neg A / högermark C))

är tillåtet för intuitionistiska förslagslogik (mathbf {IPC}) eftersom om (A), (B) och (C) är några formler så att (neg A / högermark (B / vee C)) kan provas i (mathbf {IPC}), då kan också ((neg A / högermark B) vee (neg A / högermark C)) bevisas i (mathbf {IPC }). Harrops regel är inte härledbar i (mathbf {IPC}) eftersom ((neg A / högermark (B / vee C)) högermark (neg A / högermark B) vee (neg A / högermark C)) är inte intuitionistiskt bevisbart. Ett annat viktigt exempel på en tillåtlig oundviklig regel om (mathbf {IPC}) är Mints regel:

Om ((A / högermark B) högermark (A / vee C)) är ett ställe, så är (((A / högermark B) högermark A) vee ((A / högermark B) högerpil C)).

Den tvåvärderade sanningstabellens tolkning av klassisk propositionlogik (mathbf {CPC}) ger upphov till ett enkelt bevis på att alla tillåtna regler för (mathbf {CPC}) är härledbara: annars, en del tilldelning till (A), (B), etc. skulle göra hypotesen sant och slutsatsen falsk, och genom att t.ex. (P / högermark P) ersätta bokstäverna som är tilldelade “true” och (P / oldand / neg P) för de som tilldelats”falskt” skulle man ha en bevisbar hypotes och obevisad slutsats. Att den intuitionistiska situationen är mer intressant leder till många naturliga frågor, av vilka några nyligen har besvarats.

Genom att generalisera Mints regel identifierade Visser och de Jongh en rekursivt otalig sekvens av successivt starkare tillåtna regler (”Vissers regler”), som de antog, bildade en grund för de tillåtna reglerna för (mathbf {IPC}) i den meningen att alla tillåtna regler kan härledas från skillnadsegenskapen och en av sekvensreglerna. Genom att bygga på Ghilardis arbete [1999] lyckades Iemhoff [2001] bevisa deras antaganden. Rybakov [1997] bevisade att samlingen av alla tillåtna regler för (mathbf {IPC}) är avgörbar men har ingen begränsad grund. Visser [2002] visade att hans regler också är de tillåtna propositionbestämmelserna för (mathbf {HA}) och av (mathbf {HA}) som utvidgas av Markovs MP-princip (definieras i avsnitt 5.2 nedan). Nyligen,Jerabek [2008] fann en oberoende grund för de tillåtna reglerna för (mathbf {IPC}), med den egenskap som ingen regel i grunden härleder en annan.

Mycket mindre är känt om de tillåtna reglerna för den intuitionistiska predikatlogiken. Ren (mathbf {IQC}), utan individuella eller predikatskonstanter, har följande anmärkningsvärda tillåtna regel för (A (x)) utan variabler som är fria men (x):

Om (existerar x A (x)) är ett teorem, så är (för alla x A (x)).

Inte varje tillåtet predikatregel för (mathbf {IQC}) är tillåtet för alla formella system baserade på (mathbf {IQC}); till exempel bryter (mathbf {HA}) uppenbarligen den regel som anges. Visser bevisade [1999] att egenskapen att vara en tillåtet predikatregel för (mathbf {HA}) är (Pi_2) komplett, och [2002] att (mathbf {HA}) (+) MP har samma tillåtna regler som är tillåtna som (mathbf {HA}). Plisko [1992] visade att predikatlogiken för (mathbf {HA}) (+) MP (uppsättningen av meningar på språket för (mathbf {IQC}) som alla har enhetliga substitutionstillfällen i aritmetiska språket kan bevisas i (mathbf {HA}) (+) MP) är (Pi_2) komplett; Visser [2006] utökade detta resultat till några konstruktivt intressanta konsekventa förlängningar av (mathbf {HA}) som inte finns i (mathbf {PA}).

Även om de inte har klassificerats helt, är de tillåtna reglerna för den intuitionistiska predikatlogiken kända för att inkludera Markovs regel för avgörbara predikat:

Om (forall x (A (x) vee / neg A (x)) oldand / neg / forall x / neg A (x)) är ett teorem, så är (existerar x A (x)).

och följande regel för självständighet (där (y) antas inte inträffa fritt i (A (x))):

Om (förall x (A (x) vee / neg A (x)) oldand (forall x A (x) högermark / existerar y B (y))) är ett teorem, så är (existerar y (för alla x A (x) högermark B (y))).

Båda reglerna är också tillåtna för (mathbf {HA}). Motsvarande implikationer (MP respektive IP), som inte är bevisbara intuitionistiskt, verifieras genom Gödels”Dialectica” -tolkning av (mathbf {HA}) (se avsnitt 6.3 nedan). Så är implikationen (CT) som motsvarar en av de mest intressanta tillåtna reglerna för Heyting aritmetik, låt oss kalla det kyrkan-Kleene regel:

Om (förall x / existerar y A (x, y)) är en stängd teorem för (mathbf {HA}) så finns det ett nummer (n) sådant som, sannolikt i (mathbf {HA}), den partiella rekursiva funktionen med Gödel-nummer (n) är total och kartlägger varje (x) till en (y) som uppfyller (A (x, y)) (och dessutom (A (mathbf {x}, / mathbf {y})) kan visas, där (mathbf {x}) är siffran för det naturliga talet (x) och (mathbf {y}) är siffran för (y)).

Att kombinera Markovs regel med den negativa översättningen ger resultatet att klassisk och intuitionistisk aritmetik bevisar samma formler för formen (förall x / existerar y A (x, y)) där (A (x, y)) är kvantifierare fria. I allmänhet, om (A (x, y)) är sannolikt avgörbart i (mathbf {HA}) och om (allall x / existerar y A (x, y)) är en stängd teorem av klassisk aritmetik (mathbf {PA}), slutsatsen av kyrkan-Kleene-regeln även i intuitionistisk aritmetik. För om (mathbf {HA}) bevisar (allall x / forall y (A (x, y) vee / neg A (x, y))), då av Church-Kleene styr den karakteristiska funktionen av (A (x, y)) har ett Gödel-nummer (m), sannolikt i (mathbf {HA}); så (mathbf {HA}) bevisar (allall x / existerar y A (x, y) lefstrightarrow / forall x / existerar y / existerar z B (mathbf {m}, x, y, z)) där (B) är kvantifieringsfritt,och de intilliggande existentiella kvantifierarna kan kontraheras i (mathbf {HA}). Av detta följer att (mathbf {HA}) och (mathbf {PA}) har samma provbart rekursiva funktioner.

Här är ett bevis på att regeln "Om (förall x (A / vee B (x))) är ett teorem, så är (A / vee / forall x B (x))" (där (x) är inte fritt i (A)) är inte tillåtet för (mathbf {HA}), om (mathbf {HA}) är konsekvent. Gödel-numrering ger en kvantifieringsfri formel (G (x)) som (numeriskt) uttrycker predikatet “(x) är koden för ett bevis i (mathbf {HA}) för ((0 = 1)).” Genom intuitionistisk logik med avgörbarheten för kvantifieringsfria aritmetiska formler, bevisar (mathbf {HA}) (forall x (existerar y G (y) vee / neg G (x))). Men om (mathbf {HA}) visat (existerar yG (y) vee / forall x / neg G (x)) måste (mathbf {HA})) bevisa antingen (existerar yG (y)) eller (för alla x / neg G (x)). Det första fallet är omöjligt,av existensegenskapen med konsistensantagandet och det faktum att (mathbf {HA}) bevisar alla riktiga kvantifieringsfria meningar. Men det andra fallet är också omöjligt, av Gdeles andra ofullständighetsteorem, eftersom (allall x / neg G (x)) uttrycker konsistensen av (mathbf {HA}).

5. Grundläggande semantik

Intuitionistiska system har inspirerat till en mängd olika tolkningar, inklusive Beths tablåer, Rasiowa och Sikorskis topologiska modeller, Heyting algebror, formler som typer, Kleens rekursiva realiserbarhet, Kleene och Aczel snedstreck, och modeller baserade på skivor och topoi. Av alla dessa tolkningar Kripkes [1965] möjliga världssemantik, med avseende på vilken intuitionistisk predikatlogik är fullständig och konsekvent, liknar mest klassisk modellteori. Rekursiva tolkningar av realiserbarhet, å andra sidan, försöker effektivt implementera BHK-förklaringen om intuitionistisk sanning.

5.1 Kripke semantik för intuitionistisk logik

En Kripke-struktur (mathbf {K}) för (L) består av en delvis ordnad uppsättning (K) av noder och en domänfunktion D som tilldelar varje nod (k) i (K) en bebodd set (D (k)), så att om (k / le k '), då (D (k) subseteq D (k')). Dessutom har (mathbf {K}) en tvångsrelation bestämd enligt följande.

För varje nod (k) låt (L (k)) vara det språk som sträcker sig (L) med nya konstanter för alla elementen i (D (k)). Till varje nod (k) och varje (0) - ary predikatbokstav (varje propositionbokstav) (P), antingen tilldela (f (P, k) =) sant eller lämna (f (P, k)) odefinierad, överensstämmer med kravet att om (k / le k ') och (f (P, k) =) sant så (f (P, k') =) sant också. Säg det

(k) (vDash) (P) om och bara om (f (P, k) =) true.

Till varje nod (k) och varje ((n + 1)) - ary predikat bokstav (Q (ldots)), tilldela en (eventuellt tom) uppsättning (T (Q, k)) av ((n + 1)) - delar av element i (D (k)) på ett sådant sätt att om (k / le k ') då (T (Q, k) subseteq T (Q, k ')). Säg det

(k) (vDash) (Q (d_0, / ldots, d_n)) om och bara om ((d_0, / ldots, d_n) i T (Q, k)).

Definiera nu (k) (vDash) (E) (som kan läsas "(k) krafter (E)") för sammansatta meningar (E) för (L (k)) induktivt enligt följande:

(k) (vDash) ((A / oldand B)) om (k) (vDash) (A) och (k) (vDash) (B).
(k) (vDash) ((A / vee B)) om (k) (vDash) (A) eller (k) (vDash) (B).
(k) (vDash) ((A / högermark B)) om, för varje (k '\ ge k), om (k') (vDash) (A) sedan (k ') (vDash) (B).
(k) (vDash) (neg A) om ingen (k '\ ge k) gör (k') (vDash) (A).
(k) (vDash) (för alla x A (x)) om för alla (k '\ ge k) och varje (d / i D (k')), (k ') (vDash) (A (d)).
(k) (vDash) (finns x A (x)) om för vissa (d / i D (k)), (k) (vDash) (A (d)).

Alla sådana tvångsrelationer är konsekvent:

För ingen mening (A) och ingen (k) är det så att både (k) (vDash) (A) och (k) (vDash) (neg A).

och monoton:

Om (k / le k ') och (k) (vDash) (A) då (k') (vDash) (A).

Kripkes sundhet och fullständighetsteorier fastställer att en mening med (L) kan bevisas i intuitionistisk predikatlogik om och bara om den tvingas av varje nod i varje Kripke-struktur. Så för att visa att (neg / forall x / neg P (x) högermark / existerar x P (x)) är intuitionistiskt orovärdligt, räcker det att överväga en Kripke-struktur med (K = {k, k '},) (k / lt k',) (D (k) = D (k ') = {0 }), (T (P, k)) tom men (T (P, k ') = {0 }). Och för att visa det konverserade är intuitionistiskt bevisbart (utan att faktiskt visa ett bevis), behöver man bara konsistensen och monotonicitetsegenskaperna hos godtyckliga Kripke-modeller, med definitionen av (vDash).

Kripke-modeller för språk med jämlikhet kan tolka (=) vid varje nod genom en godtycklig ekvivalensrelation, med förbehåll för monotonicitet. För tillämpningar på intuitionistisk aritmetik räcker normala modeller (de där jämställdhet tolkas av identitet vid varje nod) eftersom jämställdhet mellan naturliga tal är avgörande.

Propositional Kripke semantik är särskilt enkel, eftersom en godtycklig propositionformel är intuitionistiskt bevisbar om och bara om den tvingas av roten till varje Kripke-modell vars ram (uppsättningen (K) av noder tillsammans med deras partiella ordning) är en ändlig träd med minst element (roten). Till exempel Kripke-modellen med (K = {k, k ', k' '}, k / lt k') och (k / lt k '') och med (P) sant endast vid (k '), visar att både (P / vee / neg P) och (neg P / vee / neg / neg P) är oprovliga i (mathbf {IPC}).

Varje terminal nod eller blad i en Kripke-modell är en klassisk modell, eftersom ett blad tvingar varje formel eller dess negation. Endast de propositionsbokstäver som förekommer i en formel (E), och bara de noderna (k ') så att (k / le k'), är relevanta för att avgöra om (k) krafter eller inte (E). Sådana överväganden tillåter oss att associera effektivt med varje formel (E) för (L (mathbf {IPC})) en ändlig klass av ändliga Kripke-strukturer som kommer att inkludera en motmodell till (E) om en sådan finns. Eftersom klassen för alla teorem om (mathbf {IPC}) är rekursivt otaliga, drar vi slutsatsen att

(mathbf {IPC}) kan bestämmas effektivt. Det finns ett rekursivt förfarande som bestämmer för varje propositionformel (E) huruvida (E) är ett teorem för (mathbf {IPC}), avslutande med antingen ett bevis på (E) eller en (finit) Kripke-motmodell.

Avgörbarheten för (mathbf {IPC}) erhölls först av Gentzen 1935. Den obeslutbarheten för (mathbf {IQC}) följer av obeslutbarheten för (mathbf {CQC}) genom den negativa tolkningen.

Kända icke-intuitionistiska logiska scheman motsvarar till exempel strukturella egenskaper hos Kripke-modeller

  • DNS har i alla Kripke-modeller med begränsad ram.
  • ((A / höger pil B) vee (B / höger pil A)) rymmer i varje Kripke-modell med linjärt ordnad ram. Omvänt har varje propositionformel som inte kan härledas i (mathbf {IPC} + (A / högermark B) vee (B / högermark A)) en Kripke-motmodell med linjärt ordnad ram (se avsnitt 6.1 nedan).
  • Om (x) inte är fritt i (A), kommer (allall x (A / vee B (x)) högermark (A / vee / forall x B (x))) att hålla i varje Kripke modell (mathbf {K}) med konstant domän (så att (D (k) = D (k ')) för alla (k, k') i (K)). Detsamma gäller för MP.

Kripke-modeller och Beth-modeller (som skiljer sig från Kripke-modeller i detalj, men är intuitionistiskt likvärdiga) är ett kraftfullt verktyg för att skapa egenskaper hos intuitionistiska formella system; jfr Troelstra och van Dalen [1988], Smorynski [1973], de Jongh och Smorynski [1976], Ghilardi [1999] och Iemhoff [2001], [2005]. Det finns dock inget rent intuitionistiskt bevis på att varje mening som är giltig i alla Kripke- och Beth-modeller kan bevisas i (mathbf {IQC}). Efter en observation av Gödel, bekräftade Kreisel [1958] att fullständigheten av den intuitionistiska predikatlogiken för Beth-semantik motsvarar Markovs principledamot, som Brouwer förkastade.

Dyson och Kreisel [1961] visade dessutom att om (mathbf {IQC}) är svagt fullständigt för Beth-semantik (det vill säga om det inte finns någon orubblig mening i varje Beth-modell), så är följande konsekvens av MP innehar: [tag {GDK} forall / alpha_ {B (alpha)} neg / neg / existerar x R (alpha, x) högermark / neg / neg / forall / alpha_ {B (alpha)} exist x R (alpha, x),) där (x) sträcker sig över alla naturliga siffror, (alpha) sträcker sig över alla oändliga sekvenser av naturliga siffror, (B (alpha)) förkortar (forall x (alpha (x) leq 1)), och (R) uttrycker en primitiv rekursiv relation av (alpha) och (x). Omvänt innebär GDK den svaga fullständigheten hos (mathbf {IQC}). Denna intressanta princip, som skulle motivera den negativa tolkningen av en form av Brouwer's Fan Theorem,är svagare än parlamentsledamot men obevisbart i nuvarande system för intuitionistisk analys. Kreisel [1962] föreslog att GDK så småningom kan vara bevisbara på basis av ännu oupptäckta egenskaper hos intuitionistisk matematik.

Genom att modifiera definitionen av en Kripke-modell för att tillåta "exploderande noder" som tvingar varje mening, hittade Veldman [1976] ett fullständighetsbevis med bara intuitionistisk logik, men han ifrågasatte om Kripke-modeller med exploderande noder var intuitionistiskt meningsfulla matematiska objekt.

5.2 Realiserbarhetssemantik för Heyting aritmetik

Ett sätt att implementera BHK-förklaringen om intuitionistisk sanning för aritmetik är att associera med varje mening (E) av (mathbf {HA}) någon samling numeriska koder för algoritmer som kan fastställa den konstruktiva sanningen av (E). Efter Kleene [1945] inser ett nummer (e) en mening (E) för aritmetiska språket genom induktion av den logiska formen av (E):

(e) inser (r = t) om (r = t) är sant.
(e) inser (A / oldand B) om (e) koder ett par ((f, g)) så att (f) inser (A) och (g) realiserar (B).
(e) inser (A / vee B) om (e) koder ett par ((f, g)) så att om (f = 0) då (g) inser (A), och om (f / gt 0) då (g) inser (B).
(e) inser (A / högermark B) om, när (f) inser (A), definieras den (e): e partiella rekursiva funktionen vid (f) och dess värde realiseras (B).
(e) inser (neg A) om ingen (f) inser (A).
(e) inser (för alla x A (x)) om för varje (n) definieras (e): e delvis rekursiva funktionen vid (n) och dess värde realiserar (A (mathbf {n})).
(e) inser (finns x A (x)) om (e) koder ett par ((n, g)) och (g) inser (A (mathbf {n})).

En godtycklig formel kan realiseras om något antal inser dess universella stängning. Observera att inte både (A) och (neg A) kan realiseras för någon formel (A). Det grundläggande resultatet är

Nelsons sats [1947]

Om (A) kan härledas i (mathbf {HA}) från realiserbara formler (F), kan (A) realiseras.

Vissa icke-intuitionistiska principer kan visas vara realiserbara. Till exempel kan Markovs princip (för avgörbara formler) uttryckas av schemat

(MP) (forall x (A (x) vee / neg A (x)) oldand / neg / forall x / neg A (x) högermark / existerar x A (x))

Även om det inte är sannolikt i (mathbf {HA}) kan MP uppnås genom ett argument som använder Markovs princip informellt. Men realiserbarhet är en grundläggande icke-klassisk tolkning. I (mathbf {HA}) är det möjligt att uttrycka en axiom av rekursivt val CT (för "kyrkans avhandling"), som strider mot LEM men är (konstruktivt) realiserbar. Därför är Nelson (The matemem), (mathbf {HA}) (+) MP (+) CT konsekvent.

Kleene använde en variant av antal-realiserbarhet för att bevisa (mathbf {HA}) uppfyller Church-Kleene-regeln; samma argument fungerar för (mathbf {HA}) med MP eller CT, och för (mathbf {HA}) (+) MP (+) CT. I Kleene och Vesley [1965] och Kleene [1969] ersätter funktioner siffror som förverkligande av objekt, vilket fastställer konsistensen av en formaliserad intuitionistisk analys och dess stängning under en andra ordning av Church-Kleene Rule.

Nelsons sats fastställer oförutsägbarheten i (mathbf {IQC}) för vissa teorier av klassisk predikatlogik. Om, för varje (n) - placera predikat bokstaven (P (ldots)), en formel (f (P)) för (L (mathbf {HA})) med (n) fria variabler tilldelas, och om formeln (f (A)) för (L (mathbf {HA})) kommer från formeln (A) för (L) genom att ersätta varje primär formel (P (x_1, / ldots, x_n)) av (f (P) (x_1, / ldots, x_n)), då kallas (f (A)) en aritmetisk substitutionsinstans av (A). Som exempel, om en formel av (L (mathbf {HA})) som uttrycker “(x) koder ett bevis i (mathbf {HA}) i formeln med kod (y)”Tilldelas (P (x, y)), den resulterande aritmetiska substitutionsinstansen av (för alla y (finns x P (x, y) vee / neg / existerar x P (x, y))) är orealiserbar och därmed oöverskådlig i (mathbf {HA}), och det är dess dubbla negation. Av detta följer att (neg / neg / forall y (existerar x P (x, y) vee / neg / existerar x P (x, y))) inte kan visas i (mathbf {IQC}).

De Jongh [1970] kombinerade realiserbarhet med Kripke-modellering för att visa att den intuitionistiska förslagslogiken (mathbf {IPC}) och ett fragment av (mathbf {IQC}) är aritmetiskt kompletta för (mathbf {HA}). En enhetlig tilldelning av enkla existentiella formler för att predikera bokstäver räcker för att bevisa

De Jonghs sats (för IPC) [1970]

Om en proposition formel (A) för språket (L) inte kan visas i (mathbf {IPC}), då någon aritmetisk substitutionsinstans av (A) kan inte visas i (mathbf {HA}).

Beviset på denna version av de Jonghs sats behöver inte realiseras; jfr Smorynski [1973]. Som ett exempel tillhandahåller Rossers form av Gddel's Incompleteness Theorem en mening (C) av (L (mathbf {HA})) så att (mathbf {PA}) varken bevisar (C) eller (neg C), så genom att disjunktionsegenskapen (mathbf {HA}) inte kan bevisa ((C / vee / neg C)). Men de Jonghs semantiska bevis konstaterade också att varje intuitionistiskt otillåtet predikatformel av ett begränsat slag har en aritmetisk substitutionsinstans som är oövervinnbar i (mathbf {HA}). Med hjälp av en syntaktisk metod utvidgade Daniel Leivant [1979] de Jonghs teorem till alla intuitionistiskt opåverkbara predikatformler, vilket bevisar att (mathbf {IQC}) är aritmetiskt fullständigt för (bf {HA}). Se van Oosten [1991] för en historisk redogörelse och ett enklare bevis på hela teoremet, med abstrakt realiserbarhet med Beth-modeller istället för Kripke-modeller.

Utan att påstå att antalet realiserbarhet sammanfaller med den intuitionistiska aritmetiska sanningen, observerade Nelson att för varje formel (A) av (L (mathbf {HA})) predikatet "(y) inser (A)”Kan uttryckas i (mathbf {HA}) med en annan formel (förkortad“(y / realizesrel A)”), och schemat (A / leftrightarrow / existerar y (y / realisesrel A)) överensstämmer med (mathbf {HA}). Troelstra [1973] visade att (mathbf {HA}) (+) ((A / leftrightarrow / existerar y (y / realisesrel A))) motsvarar (mathbf {HA}) (+) ECT, där ECT är en stärkt form av CT. I (mathbf {HA}) (+) MP (+) ECT, som Troelstra anser vara en formalisering av rysk rekursiv matematik (jfr avsnitt 3.2 i posten om konstruktiv matematik), varje formel i formen ((y / realisesrel A)) har en ekvivalent "klassisk" prenexform (A '(y)) bestående av en kvantifieringsfri subformel föregående med alternerande "klassiska" kvantifierare av formerna (neg / neg / existerar x) och (allall z / neg / neg), och så (existerar y A '(y)) är en typ av prenexform av (A).

6. Ytterligare ämnen och vidare läsning

6.1 Subintuitionistisk och mellanliggande logik

För närvarande finns det flera andra poster i detta leksikon som behandlar intuitionistisk logik i olika sammanhang, men en generell behandling av svagare och starkare propositions- och predikatlogik verkar sakna. Många sådana logiker har identifierats och studerats. Här är några exempel.

En subintuitionistisk förslagslogik kan erhållas från (mathbf {IPC}) genom att begränsa språket, eller försvaga logiken, eller båda. Ett extremt exempel på det första är (mathbf {RN}), intuitionistisk logik med en enda propositionsvariabel (P), som är uppkallad efter upptäckarna Rieger och Nishimura [1960]. (mathbf {RN}) kännetecknas av Rieger-Nishimura-gitteret med oändligt många icke-kvotala formler (F_n) så att varje formel vars enda förslagsvariabel är (P) är ekvivalent med intuitionistisk logik till vissa (F_n). Nishimuras version är

(börja {inriktning *} F _ { infty} & = P / höger pil 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} höger pil F_ {2 n + 1}. / End {align *})

I (mathbf {RN}) varken (F_ {2 n + 1}) eller (F_ {2 n + 2}) implicerar den andra; men (F_ {2 n}) antyder (F_ {2 n + 1}), och (F_ {2 n + 1}) implicerar var och en av (F_ {2 n + 3}) och (F_ {2 n + 4}).

Fragment av (mathbf {IPC}) som saknar ett eller flera logiska anslutningar begränsar språket och förresten logiken, eftersom de intuitionistiska anslutningarna (oldand), (vee), (högermark), (neg) är logiskt oberoende över (mathbf {IPC}). Rose [1953] bevisade att det implicationslösa fragmentet (utan (högermark)) är komplett med avseende på realiserbarhet, i den meningen att om alla aritmetiska substitutionsinstanser av en proposition formel (E) utan (högermark) är (nummer) - realiserbar då är (E) ett ställe för (mathbf {IPC}). Detta resultat står i kontrast till

Roses teorem [1953]

(mathbf {IPC}) är ofullständig med avseende på realiserbarhet.

Låt (F) vara den propositionella formeln [((neg / neg D / högermark D) högermark (neg / neg D / vee / neg D)) högermark (neg / neg D / vee / neg D)) där (D) är ((neg P / vee / neg Q)) och (P), (Q) är prim. Varje aritmetisk substitutionsinstans av (F) kan realiseras (med klassisk logik), men (F) kan inte visas i (mathbf {IPC}).

Av detta följer att (mathbf {IPC}) är aritmetiskt ofullständig för (mathbf {HA}) (+) ECT (se avsnitt 5.2).

Minimal logik (mathbf {ML}) kommer från intuitionistisk logik genom att radera ex falso. Kolmogorov [1925] visade att detta fragment redan innehåller en negativ tolkning av klassisk logik som bibehåller båda kvantifierare, jfr. Leivant [1985]. Minimal logik bevisar specialfallet (neg A / högermark (A / högermark / neg B)) för ex falso för negationer. Colacito, de Jongh och Vardas [2017] studerar olika subminimala logiker, var och en svagare än (mathbf {ML}).

Griss ifrågasatte Brouwer's användning av negation, och invände både motstridslagen och ex falso. Det är värt att notera att negation egentligen inte behövs för intuitionistisk matematik eftersom (0 = 1) är en känd motsägelse så (neg A) kan definieras av (A / höger 0 = 1). Då kan ex falso anges som (0 = 1 / höger till höger A), och motsägningslagen kan bevisas från de återstående axiomerna till (mathbf {H}).

En mellanliggande propositionslogik är varje konsekvent samling av propositionella formler som innehåller alla axiomas av (mathbf {IPC}) och stängs under modusponens och ersätter godtyckliga formler för propositionbokstäver. Varje mellanliggande propositionlogik finns i (mathbf {CPC}). Vissa särskilda mellanliggande förslagslogiker, som kännetecknas av att lägga till en eller flera klassiskt korrekta men intuitionistiskt obevisbara axiomscheman till (mathbf {IPC}), har studerats omfattande.

En av de enklaste mellanliggande förslagslogikerna är Gödel-Dummett-logiken (mathbf {LC}), erhållen genom att lägga till (mathbf {IPC}) schemat ((A / högermark B) vee (B / höger pil A)) som är giltig på alla och endast de Kripke-ramar där nodernas partiella ordning är linjär. Gödel [1932] använde en oändlig sekvens av successivt starkare mellanliggande logik för att visa att (mathbf {IPC}) inte har någon begränsad sanningstabellstolkning. För varje positivt heltal (n), låt (mathbf {G_n}) vara (mathbf {LC}) plus schemat ((A_1 / högermark A_2) vee / ldots / vee (A_1 / oldand / ldots / oldand A_n / rightarrow A_ {n + 1})). Då är (mathbf {G_n}) giltig på alla och endast de linjärt ordnade Kripke-ramar med inte mer än (n) noder.

Jankov-logiken (mathbf {KC}), som lägger till (mathbf {IPC}) principen om testbarhet (neg A / vee / neg / neg A) har uppenbarligen inte disjunktionen fast egendom. Kreisel-Putnam-logiken (mathbf {KP}), erhållen genom att lägga till (mathbf {IPC}) schemat ((neg A / högermark B / vee C) högermark ((neg A / höger pil B) vee (neg A / höger pil C))), har tillhörande egenskap men uppfyller inte alla Visser-regler. Mellanlogiken erhållen genom att lägga till schemat (((neg D / höger pil D) höger pil (D / vee / neg D)) höger pil (neg / neg D / vee / neg D)), motsvarande till Roses motexempel, till (mathbf {IPC}) har också skillnadsegenskapen. Iemhoff [2005] bevisade att (mathbf {IPC}) är den enda mellanliggande förslagslogiken med disjunktionsegenskapen som är stängd under alla Visser-regler. Iemhoff och Metcalfe [2009] utvecklade en formell kalkyl för generaliserad tillåtlighet för (mathbf {IPC}) och vissa mellanliggande logiker. Goudsmit [2015] är en grundlig studie av de tillåtna reglerna för mellanliggande logik, med en omfattande bibliografi.

En mellanliggande förslagslogik (mathbf {L}) sägs ha den begränsade ramegenskapen om det finns en klass av begränsade ramar på vilka de Kripke-giltiga formlerna exakt är teoremen om (mathbf {L}). Många mellanliggande logiker, inklusive (mathbf {LC}) och (mathbf {KP}), har den här egenskapen. Jankov [1968] använde en oändlig sekvens av ändliga rotade Kripke-ramar för att bevisa att det finns kontinuum med många mellanliggande logiker. De Jongh, Verbrugge och Visser [2009] bevisade att varje mellanliggande logik (mathbf {L}) med den ändliga ramegenskapen är den propositionella logiken för (mathbf {HA (L)}), det vill säga klass med alla formler på språket för (mathbf {IPC}) som alla är aritmetiska substitutionsinställningar kan bevisas i den logiska förlängningen av (mathbf {HA}) med (mathbf {L}).

En mellanliggande förslagslogik (mathbf {L}) är strukturellt fullständig om varje regel som är tillåtet för (mathbf {L}) är härledbar i (mathbf {L}) och ärftligt strukturellt fullständigt om varje mellanliggande logik som sträcker sig (mathbf {L}) är också strukturellt fullständig. Varje mellanliggande logik (mathbf {L}) har en strukturell slutförande (mathbf { overline {L}}), erhållen genom angränsande till alla dess tillåtna regler. (mathbf {LC}) och (mathbf {G_n}) är ärftligt strukturellt kompletta. Medan (mathbf {IPC}), (mathbf {RN}) och (mathbf {KC}) inte är strukturellt fullständiga, är deras strukturella kompletteringar ärftligt strukturellt fullständiga. För dessa resultat och mer, se Citkin [2016, andra internetresurser].

Vissa mellanliggande predikatlogiker, som sträcker sig (mathbf {IQC}) och stängda under substitution, är (mathbf {IQC}) (+) DNS (avsnitt 4.1), (mathbf {IQC}) (+) MP (se avsnitt 5.2), (mathbf {IQC}) (+) MP (+) IP (jfr. Avsnitt 4.2), och den intuitionistiska logiken för konstant domäner (mathbf {CD}) erhållet genom att lägga till (mathbf {IQC}) schemat (forall x (A / vee B (x)) högermark (A / vee / forall x B (x))) för alla formler (A), (B (x)) med (x) som inte förekommer gratis i (A). Mints, Olkhovikov och Urquhart [2012, andra internetresurser] visade att (mathbf {CD}) inte har interpolationsegenskapen, vilket motbeviser tidigare publicerade bevis från andra författare.

6.2 Avancerade ämnen

Brouwer's inflytande på Gödel var betydande, även om Gödel aldrig blev en intuitionist. Gödels [1933f] översättning av intuitionistiska propositioneringslogik till modal logik (mathbf {S4}) beskrivs i avsnitt 2.5 i posten om Gödel och i Troelstras inledande anmärkning till översättningen av [1933f] i Volym I av Gödel's Collected Arbetar. Se även Mints [2012]. Kripke-modeller för modal logik föregick de för intuitionistisk logik.

Alternativ till Kripke och Beth semantik för intuitionistisk proposition och logik inkluderar den topologiska tolkningen av Stone [1937], Tarski [1938] och Mostowski [1948] (jfr Rasiowa och Sikorski [1963], Rasiowa [1974]), som utvidgades till intuitionistisk analys av Scott [1968] och Krol [1978]. M. Hyland [1982] definierade den effektiva topos Eff och bevisade att dess logik är intuitionistisk. För en mycket informativ diskussion av semantik för intuitionistisk logik och matematik av W. Ruitenberg och ett intressant nytt perspektiv av G. Bezhanishvili och W. Holliday, se Andra internetresurser (nedan).

Ett alternativ till realiserbarhetssemantik för intuitionistisk aritmetik är Gödels [1958] "Dialectica" -tolkning, som associerar med varje formel (B) för (L (mathbf {HA})) en kvantifieringsfri formel (B_D) på det intuitionistiska aritmetiska språket av alla ändliga typer. "Dialectica" -tolkningen av (B), kalla den (B ^ D), är (existerar Y / för alla x B_D (Y, x)). Om (B) är en stängd teorem för (mathbf {HA}), kan (B_D (F, x)) bevisas under någon term (F) i Gödels teori (mathbf { T}) för "primitiva rekursiva" funktioner av högre typ. Översättningen från (B) till (B ^ D) kräver valt axiom (vid alla ändliga typer), MP och IP, så det är inte strikt konstruktivt; i alla fall,de nummerteoretiska funktionerna som kan uttryckas med termer (F) för (mathbf {T}) är exakt de provbart rekursiva funktionerna för (mathbf {HA}) (och av (mathbf {PA})). Tolkningen utvidgades till analys av Spector [1962]; jfr Howard [1973]. Klara exponeringar och ytterligare referenser finns i Troelstras introduktion till den engelska översättningen i Gödel [1990] av den ursprungliga artikeln Dialectica, i Avigad och Feferman [1998] och i Ferreira [2008].

Medan (mathbf {HA}) är en riktig del av klassisk aritmetik, resulterar den intuitionistiska inställningen till matematiska objekt i en teori om verkliga siffror (jfr avsnitt 3.4–3.7 i posten om intuitionism i matematikfilosofin) divergerande från det klassiska. Kleens tolkning av funktionens realiserbarhet, utvecklad för att bevisa konsistensen i hans formalisering (mathbf {FIM}) av den intuitionistiska teorin om sekvenser ("intuitionistisk analys"), ändrar tolkningen av aritmetiska formler; till exempel, (neg / neg / forall x (A (x) vee / neg A (x))) kan realiseras för varje aritmetisk formel (A (x)). På analysspråketMarkovs princip och den negativa översättningen av den räknbara axiom som valts är bland de många icke-intuitionistiska principerna som är funktionsrealiserbara (av klassiska argument) och därmed överensstämmer med (mathbf {FIM}); jfr Kleene [1965], Vesley [1972] och Moschovakis [2003].

Konkret och abstrakt realiserbarhetssemantik för en mängd olika formella system har utvecklats och studerats av logiker och datavetare; jfr Troelstra [1998] och van Oosten [2002] och [2008]. Variationer av de grundläggande uppfattningarna är särskilt användbara för att fastställa relativ konsistens och relativ oberoende av de icke-logiska axiomerna i teorier baserade på intuitionistisk logik; några exempel är Moschovakis [1971], Lifschitz [1979] och realiseringsbegreppet för konstruktiva och intuitionistiska uppsättningsteorier utvecklade av Rathjen [2006, 2012] och Chen [2012]. Tidiga abstrakta realiserbarhetsuppfattningar inkluderar snedstreck från Kleene [1962, 1963] och Aczel [1968] och Läuchli [1970]. Kohlenbach, Avigad och andra har utvecklat tolkningar av realiserbarhet för delar av klassisk matematik.

Artemovs motiveringslogik är en alternativ tolkning av BHK-förklaringen av de intuitionistiska anslutningarna och kvantifierarna, med (idealiserade) bevis som spelar rollen för att förverkliga föremål. Se även Artemov och Iemhoff [2007].

En annan forskningslinje inom intuitionistisk logik rör Brews mycket kontroversiella”skapa subjektiska motexempel” på principer för klassisk analys (som Markovs princip) som inte kunde motbevisas på grundval av teorin (mathbf {FIM}) för Kleene och Vesley [1965]. Genom att försvaga Kleene form av Brouwer's princip om kontinuerligt val och lägga till ett axiom som han kallade Kripkes Schema (KP) lyckades Myhill formalisera de skapande ämnesargumenten. KP är inkonsekvent med (mathbf {FIM}), men Vesley [1970] fann en alternativ princip (Vesleys schema VS) som konsekvent kan läggas till (mathbf {FIM}) och innebär alla motexempel för vilka Brouwer krävde ett skapande ämne. Krol [1978] och Scowcroft gav topologiska konsistensbevis för intuitionistisk analys med Kripkes schema och svag kontinuitet.

6.3 Rekommenderad läsning

Inlägget på LEJ Brouwer diskuterar Brouwer's filosofi och matematik, med en kronologi om hans liv och en utvald lista över publikationer inklusive översättningar och sekundära källor. Det bästa sättet att lära sig mer är att läsa några av originalpapperna. Engelska översättningar av Brouwer's doktorsavhandling och andra artiklar som ursprungligen publicerades på holländska, tillsammans med ett antal artiklar på tyska, finns i LEJ Brouwer: Collected Works [1975], redigerad av Heyting. Benacerraf och Putnams väsentliga källbok innehåller Brouwer [1912] (i engelsk översättning), Brouwer [1949] och Dummett [1975]. Mancosus [1998] ger engelska översättningar av många grundläggande artiklar av Brouwer, Heyting, Glivenko och Kolmogorov, med upplysande introduktionsmaterial av W. van Stigt vars [1990] är en annan värdefull resurs.

Den tredje upplagan [1971] av Heytings klassiker [1956] är en attraktiv introduktion till intuitionistisk filosofi, logik och matematisk praxis. Som en del av det formidabla projektet för redigering och publicering av Brouwer's Nachlass ger van Dalen [1981] en omfattande bild av Brouwer's egen intuitionistiska filosofi. Den engelska översättningen, i van Heijenoort [1969], av Brouwer's [1927] (med en fin introduktion av Parsons) är fortfarande en oumbärlig referens för Brouwer's teori om kontinuum. Veldman [1990] och [2005] är äkta moderna exempel på traditionell intuitionistisk matematisk praxis. Troelstra [1991] placerar intuitionistisk logik i sitt historiska sammanhang som den gemensamma grunden för konstruktiv matematik under det tjugonde århundradet. Bezhanishvili och de Jongh [2005,Andra Internetresurser] inkluderar den senaste utvecklingen inom intuitionistisk logik.

Kleene och Vesleys [1965] ger en noggrann axiomatisk behandling av intuitionistisk analys, ett bevis på dess konsistens i förhållande till en klassiskt korrekt underteori och en utökad tillämpning på Brouwer's teori om generatorer för verkligt antal. Kleene's [1969] formaliserar teorin om partiella rekursiva funktionaliteter, vilket möjliggör exakta formaliseringar av tolkningen av funktionen-realiserbarhet som användes [1965] och en relaterad tolkning av q-realiserbarhet som ger Church-Kleene regel för intuitionistisk analys.

Troelstras [1973], Beesons [1985] och Troelstra och van Dalens [1988] (med korrigeringar) framträder som de mest omfattande studierna av intuitionistiska och semi-intuitionistiska formteorier, med både konstruktiva och klassiska metoder, med användbara bibliografier. Troelstra och Schwichtenberg [2000] presenterar bevisteorin för klassisk, intuitionistisk och minimal logik parallellt, med fokus på sekvensiella system. Troelstra's [1998] presenterar formler-som-typer och (Kleene och Aczel) snedstolkningar för propositions- och predikatlogik, samt abstrakta och konkreta realiserbarheter för en mängd applikationer. Martin-Löfs konstruktiva teori om typer [1984] (jfr avsnitt 3.4 i posten om konstruktiv matematik) ger en annan allmän ram inom vilken intuitionistisk resonemang fortsätter att utvecklas.

Bibliografi

  • Aczel, P., 1968, "Mättade intuitionistiska teorier" i HA Schmidt, K. Schütte och H.-J. Thiele (red.), Bidrag till matematisk logik, Amsterdam: Nord-Holland: 1–11.
  • Artemov, S. och Iemhoff, R., 2007, "Den grundläggande intuitionistiska logiken för bevis", Journal of Symbol Logic, 72: 439–451.
  • Avigad, J. och Feferman, S., 1998, "Gödels funktionella (" Dialectica ") tolkning," Kap V i Buss (red.) 1998: 337–405.
  • Bar-Hillel, Y. (red.), 1965, Logik, metodik och vetenskapsfilosofi, Amsterdam: Nordholland.
  • Beeson, MJ, 1985, Foundations of Constructive Mathematics, Berlin: Springer.
  • Benacerraf, P. och Hilary Putnam (red.), 1983, Philosophy of Mathematics: Selected Readings, 2nd Edition, Cambridge: Cambridge University Press.
  • Beth, EW, 1956, "Semantisk konstruktion av intuitionistisk logik", Koninklijke Nederlandse Akad. von Wettenscappen, 19 (11): 357–388.
  • Brouwer, LEJ, 1907, "On the Foundations of Mathematics," Avhandling, Amsterdam; Engelsk översättning i Heyting (red.) 1975: 11–101.
  • –––, 1908, “De opålitliga de logiska principerna,” engelsk översättning i Heyting (red.) 1975: 107–111.
  • ––– 1912,”Intuitionism and Formalism,” engelsk översättning av A. Dresden, Bulletin of the American Mathematical Society, 20 (1913): 81–96, omtryckt i Benacerraf och Putnam (red.) 1983: 77–89; också tryckt i Heyting (red.) 1975: 123–138.
  • –––, 1923 [1954], "Om betydelsen av principen om uteslutet mitt i matematik, särskilt i funktionsteori", "Addenda and corrigenda," och "Ytterligare addenda and corrigenda," Engelsk översättning i van Heijenoort (ed. 1967: 334–345.
  • ––– 1923C,”Intuitionistische Zerlegung matematiker Grundbegriffe,” Jahresbericht der Deutschen Mathematiker-Vereinigung, 33 (1925): 251-256; återtryckt i Heyting (red.) 1975, 275–280.
  • ––– 1927,”Intuitionistiska reflektioner om formalism,” publicerades ursprungligen 1927, engelsk översättning i van Heijenoort (red.) 1967: 490–492.
  • ––– 1948,”Medvetande, filosofi och matematik,” publicerades ursprungligen (1948), omtryckta i Benacerraf och Putnam (red.) 1983: 90–96.
  • Burr, W., 2004, "Den intuitionistiska aritmetiska hierarkin", i J. van Eijck, V. van Oostrom och A. Visser (red.), Logic Colloquium '99 (Lecture Notes in Logic 17), Wellesley, MA: ASL och AK Peters, 51–59.
  • Buss, S. (red.), 1998, Handbook of Proof Theory, Amsterdam och New York: Elsevier.
  • Chen, RM. och Rathjen, M., 2012, "Lifschitz-realiserbarhet för intuitionistisk Zermelo-Fraenkel-uppsättningsteori," Archive for Mathematical Logic, 51: 789–818.
  • Colacito, A., de Jongh, D. och Vargas, A., 2017, “Subminimal Negation”, Soft Computing, 21: 165–164.
  • Crossley, J., och MAE Dummett (red.), 1965, Formella system och rekursiva funktioner, Amsterdam: North-Holland Publishing.
  • van Dalen, D. (red.), 1981, Brouwer's Cambridge Lectures on Intuitionism, Cambridge: Cambridge University Press.
  • Dummett, M., 1975, "Den filosofiska grunden för den intuitionistiska logiken", publicerad ursprungligen (1975), tryckt i Benacerraf och Putnam (red.) 1983: 97–129.
  • Dyson, V. och Kreisel, G., 1961, Analys av Beths semantiska konstruktion av intuitionistisk logik, Teknisk rapport nr 3, Stanford: Applied Mathematics and Statistics Laboratory, Stanford University.
  • Ferreira, F., 2008, "Ett mest konstnärligt paket med ett virvlande idéer", Dialectica, 62: 205–222.
  • Friedman, H., 1975, "Egenskaperna för disjunktion innebär den numeriska existensegenskapen," Proceedings of the National Academy of Science, 72: 2877–2878.
  • Gentzen, G., 1934–5, “Untersuchungen Über das logische Schliessen,” Mathematische Zeitschrift, 39: 176–210, 405–431.
  • Ghilardi, S., 1999, "Enhet i intuitionistisk logik", 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 sciences, 5 (15): 183–188.
  • Gödel, K., 1932, "Zum intuitionistischen Aussagenkalkül," Anzeiger der Akademie der Wissenschaften i Wien, 69: 65–66. Reproducerades och översattes med en inledande anmärkning av AS Troelstra i Gödel 1986: 222–225.
  • ––– 1933e, “Zur intuitionistischen Arithmetik und Zahlentheorie,” Ergebnisse eines mathematatischen Kolloquiums, 4: 34–38.
  • ––– 1933f,”Eine Interpretation des intuitionistischen Aussagenkalküls,” reproducerades och översattes med en inledande anmärkning av AS Troelstra i Gödel 1986: 296–304.
  • ––– 1958,”Über eine bisher noch nicht benützte Erweiterung des finiten Standpunktes,” Dialectica, 12: 280–287. Återges med en engelsk översättning i Gödel 1990: 241–251.
  • –––, 1986, Samlade verk, vol. I, S. Feferman et al. (red.), Oxford: Oxford University Press.
  • –––, 1990, Samlade verk, vol. II, S. Feferman et al. (red.), Oxford: Oxford University Press.
  • Goudsmit, JP, 2015, Intuitionistic Rules: Admissible Rules of Intermediate Logics, Ph. D. avhandling, University of Utrecht.
  • Harrop R., 1960, "Om formler av typen (A / högermark B / vee C, A / högermark (Ex) B (x)) i intuitionistiska formella system," Journal of Symbolic Logic, 25: 27–32.
  • van Heijenoort, J. (red.), 1967, Från Frege till Gödel: En källbok i matematisk logik 1879–1931, Cambridge, MA: Harvard University Press.
  • Heyting, A., 1930, "Die formalen Regeln der intuitionistischen Logik," i tre delar, Sitzungsberichte der preussischen Akademie der Wissenschaften: 42–71, 158–169. Engelsk översättning av del I i Mancosu 1998: 311–327.
  • –––, 1956, Intuitionism: An Introduction, Amsterdam: North-Holland Publishing, 3: e reviderade utgåvan, 1971.
  • Heyting, A. (red.), 1975, LEJ Brouwer: Samlade verk (Volym 1: Filosofi och grundval av matematik), Amsterdam och New York: Elsevier.
  • Howard, WA, 1973, "Hereditarily majorizable functionals of finite type", i Troelstra (red.) 1973: 454–461.
  • Hyland, JME, 1982, "De effektiva toposna" i Troelstra och van Dalen (red.) 1982: 165–216.
  • Iemhoff, R., 2001, "Om de tillåtna reglerna för den intuitionistiska propositionella logiken", Journal of Symbolic Logic, 66: 281–294.
  • ––– 2005,”Mellanlogik och Vissers regler,” Notre Dame Journal of Formal Logic, 46: 65–81.
  • Iemhoff, R. och Metcalfe, G., 2009, "Bevissteori för tillåtna regler", Annals of Pure and Applied Logic, 159: 171–186.
  • Jankov, VA, 1968, "Konstruktionen av en sekvens av starkt oberoende superintuitionistiska propositionskalkyler", sovjetisk matematik. Doklady, 9: 801–807.
  • Jerabek, E., 2008, "Oberoende grunder för tillåtna regler," Logic Journal of IGPL, 16: 249–267.
  • de Jongh, DHJ, 1970, "Maximaliteten i den intuitionistiska propositionskalkylen med avseende på Heytings aritmetik," Journal of Symbolic Logic, 6: 606.
  • de Jongh, DHJ och Smorynski, C., 1976, "Kripke-modeller och den intuitionistiska teorin om arter," Annals of Mathematical Logic, 9: 157–186.
  • de Jongh, D., Verbrugge, R. och Visser, A., 2011, "Mellanlogik och egenskapen de Jongh," Archive for Mathematical Logic, 50: 197–213.
  • Kino, A., Myhill, J. och Vesley, RE (red.), 1970, Intuitionism and Proof Theory: Proceedings of the summer conference in Buffalo, NY, 1968, Amsterdam: North-Holland.
  • Kleene, SC, 1945, "Om tolkningen av intuitionistisk talteori", Journal of Symbolic Logic, 10: 109–124.
  • –––, 1952, Introduction to Metamathematics, Princeton: Van Nostrand.
  • –––, 1962,”Disjunktion och existens under implikation i elementära intuitionistiska formaliteter,” Journal of Symbolic Logic, 27: 11–18.
  • ––– 1963,”Ett tillägg”, Journal of Symbolic Logic, 28: 154–156.
  • –––, 1965,”Klassiska förlängningar av intuitionistisk matematik,” i Bar-Hillel (red.) 1965: 31–44.
  • –––, 1969, Formaliserade rekursiva funktioner och formaliserad realisering, memoarer av American Mathematical Society 89.
  • Kleene, SC och Vesley, RE, 1965, The Foundations of Intuitionistic Mathematics, Speciellt i relation till rekursiva funktioner, Amsterdam: Nord-Holland.
  • Kreisel, G., 1958, "Elementära fullständighetsegenskaper för intuitionistisk logik med en anmärkning om negationer av prenexformler," Journal of Symbolic Logic, 23: 317–330.
  • ––– 1962,”På svag fullständighet av den intuitionistiska predikatlogiken,” Journal of Symbolic Logic, 27: 139–158.
  • Kripke, SA, 1965, "Semantisk analys av intuitionistisk logik," i J. Crossley och MAE Dummett (red.) 1965: 92-130.
  • Krol, M., 1978, "En topologisk modell för intuitionistisk analys med Kripkes schema," Zeitschrift für Math. Logik und Grundlagen der Math., 24: 427–436.
  • Leivant, D., 1979, "Maximality of Intuitionistic Logic," Mathematical Center Tracts 73, Mathematisch Centrum, Amsterdam.
  • –––, 1985,”Syntaktiska översättningar och bevisligen rekursiva funktioner,” Journal of Symbolic Logic, 50: 682–688.
  • Läuchli, H., 1970, "Ett abstrakt begrepp om realiserbarhet för vilken intuitionistisk predikatberäkning är fullständig," i A. Kino et al. (red.) 1965: 227–234.
  • Lifschitz, V., 1979, "CT (_ 0) är starkare än CT (_ 0)!". Proceedings of the American Mathematical Society, 73 (1): 101–106.
  • Mancosu, P., 1998, Från Brouwer till Hilbert: Debatten om grunden för matematik på 1920-talet, New York och Oxford: Oxford University Press.
  • Martin-Löf, P., 1984, Intuitionistic Type Theory, Anteckningar av Giovanni Sambin av en serie föreläsningar som ges i Padua, juni 1980, Napoli: Bibliopolis.
  • Mints, G., 2012, "Gödel – Tarski-översättningarna av intuitionistiska propositionella formler", i korrekt resonemang (Lecture Notes in Computer Science 7265), E. Erdem et al. (red.), Dordrecht: Springer-Verlag: 487–491.
  • Moschovakis, JR, 1971, "Kan det inte finnas några icke-rekursiva funktioner?", Journal of Symbolic Logic, 36: 309–315.
  • ––– 2003,”Klassiska och konstruktiva hierarkier i utökad intuitionistisk analys”, Journal of Symbolic Logic, 68: 1015–1043.
  • –––, 2009, “Logiken för Brouwer och Heyting,” i logik från Russell till kyrkan (Handbook of the Logic History, bind 5), J. Woods och D. Gabbay (red.), Amsterdam: Elsevier: 77 -125.
  • ––– 2017,”Intuitionistisk analys och tidens slut”, Bulletin of Symbolic Logic, 23: 279–295.
  • Nelson, D., 1947, "Rekursiva funktioner och intuitionistisk talteori", Transactions of the American Mathematical Society, 61: 307–368.
  • Nishimura, I., 1960, "Om formler för en variabel i intuitionistisk propositionskalkyl", Journal of Symbolic Logic, 25: 327–331.
  • van Oosten, J., 1991, "Ett semantiskt bevis på de Jonghs teorem", Arkiv för matematisk logik, 31: 105–114.
  • –––, 2002,”Realiserbarhet: ett historiskt uppsats,” Matematiska strukturer i datavetenskap, 12: 239–263.
  • –––, 2008, Realiserbarhet: En introduktion till dess kategoriska sida, Amsterdam: Elsevier.
  • Plisko, VE, 1992, "Om aritmetisk komplexitet hos viss konstruktiv logik," Mathematical Notes, (1993): 701–709. Översatt från Matematicheskie Zametki, 52 (1992): 94–104.
  • Rasiowa, H., 1974, Algebraic Appriach to Non-Classical Logics, Amsterdam: North-Holland.
  • Rasiowa, H. och Sikorski, R., 1963, The Matematics of Metamathematics, Warszawa: Panstwowe Wydawnictwo Naukowe.
  • Rathjen, M., 2006, "Realizability for constructive Zermelo-Fraenkel set theory", i Logic Colloquium 2003 (Lecture Notes in Logic 24), J. Väänänen et al. (red.), AK Peters 2006: 282–314.
  • ––– 2012, “Från den svaga till den starka existensegenskapen”, Annals of Pure and Applied Logic, 163: 1400–1418.
  • Rose, GF, 1953, "Propositional calculus and realizability," Transactions of the American Mathematical Society, 75: 1–19.
  • Rybakov, V., 1997, Admissibility of Logical Inferensregler, Amsterdam: Elsevier.
  • Scott, D., 1968, "Utöka den topologiska tolkningen till intuitionistisk analys," Compositio Mathematica, 20: 194-210.
  • Smorynski, CA, 1973, "Applications of Kripke models," i Troelstra (red.) 1973: 324–391.
  • Spector, C., 1962, "Tillhandahållande av rekursiva analysfunktioner: ett konsistenssäkerhetsanalys genom en förlängning av principer formulerade i aktuell intuitionistisk matematik," Rekursiv funktionsteori: Proceedings of Symposia in Pure Mathematics, Volym 5, JCE Dekker (red.), Providence, RI: American Mathematical Society, 1–27.
  • van Stigt, WP, 1990, Brouwer's Intuitionism, Amsterdam: Nord-Holland.
  • Stone, MH, 1937, "Topologisk framställning av distribuerande galler och Brouweriska logik", Casopis Pest. Matta. Fys., 67: 1–25.
  • Tarski, A., 1938, "Der Aussagenkalkül und die Topologie", Fundamenta Mathematicae, 31: 103–104.
  • Troelstra, AS, 1991, "Konstruktivismens historia under det tjugonde århundradet," ITLI Prepublication Series ML – 1991–05, Amsterdam. Slutversion i Set Theory, Arithmetic and Foundations of Mathematics (Lecture Notes in Logic 36), J. Kenney och R. Kossak (red.), Association for Symbolic Logic, Ithaca, NY, 2011: 150–179.
  • ––– 1998,”Realiserbarhet”, kapitel VI i Buss (red.), 1998: 407–473.
  • –––, inledande anmärkning till 1958 och 1972, i Gödel, 1990: 217–241.
  • Troelstra, AS (red.), 1973, Metamatematisk undersökning av intuitionistisk aritmetik och analys (Lecture Notes in Matematics 344), Berlin: Springer-Verlag. Korrigeringar och tillägg tillgängliga från redaktören.
  • Troelstra, AS och Schwichtenberg, H., 2000, Basic Proof Theory (Cambridge Tracts in Theoretical Computer Science: Volume 43), 2nd edition, Cambridge: Cambridge University Press.
  • Troelstra, AS och van Dalen, D., 1988, Constructivism in Mathematics: An Introduction, 2 bind, Amsterdam: North-Holland Publishing. [Se även korrigeringarna i andra Internetresurser.]
  • Troelstra, AS och van Dalen, D. (red.), 1982, LEJ Brouwer Centenary Symposium, Amsterdam: North-Holland Publishing.
  • Veldman, W., 1976,”En intuitionistisk fullständighetsteorem för intuitionistisk predikatlogik,” Journal of Symbolic Logic, 41: 159–166.
  • –––, 1990,”En undersökning av intuitionistisk beskrivande uppsättningsteori,” i PP Petkov (red.), Matematisk logik, Proceedings of the Heyting Conference, New York och London: Plenum Press, 155–174.
  • ––– 2005,”Två enkla uppsättningar som inte är positivt Borel,” Annals of Pure and Applied Logic, 135: 151–209.
  • Vesley, RE, 1972,”Val av sekvenser och Markovs princip,” Compositio Mathematica, 24: 33–53.
  • ––– 1970,”Ett smakligt alternativ till Kripkes schema,” i A. Kino et al. (red.) 1970: 197ff.
  • Visser, A., 1999, "Regler och aritmetik", Notre Dame Journal of Formal Logic, 40: 116–140.
  • –––, 2002,”Substitutions of (Sigma ^ {0} _1) meningar: utforskningar mellan intuitionistisk propositionell logik och intuitionistisk aritmetik,” Annals of Pure and Applied Logic, 114: 227–271.
  • ––– 2006, “Predikatlogik för konstruktiva aritmetiska teorier”, Journal of Symbolic Logic, 72: 1311–1326.

Akademiska verktyg

sep man ikon
sep man ikon
Hur man citerar det här inlägget.
sep man ikon
sep man ikon
Förhandsgranska PDF-versionen av det här inlägget på SEP-samhällets vänner.
ino-ikon
ino-ikon
Slå upp det här ämnet vid Internet Philosophy Ontology Project (InPhO).
phil papper ikon
phil papper ikon
Förbättrad bibliografi för detta inlägg på PhilPapers, med länkar till dess databas.

Andra internetresurser

  • Bezhanishvili, G. och Holliday, W., 2018, "En semantisk hierarki för intuitionistisk logik," manuskript, UC Berkeley Fakultetspublikationer.
  • Bezhanishvili, N. och de Jongh, DHJ, 2005, Intuitionistic Logic, Lecture notes presenterade vid ESSLLI, Edinburgh.
  • Brouwer, utdrag från Brouwer's Cambridge-föreläsningar.
  • Citkin, A., 2016, “Arveligt strukturellt kompletta superintuitionistiska deduktiva system,” manuskript på arXiv.org.
  • Mints, G., Olkhovikov, G. och Urquhart, A., 2012, "Misslyckande med interpolering i den intuitionistiska logiken för ständiga domäner," manuskript, arXiv.org.
  • Troelstra, AS och JR Moschovakis, 2018, Rättelser till AS Troelstra och D. van Dalen, 1988, Konstruktivism i matematik.
  • Problem i provbarhetslogiken, upprätthålls av Lev Beklemishev.
  • Realiserbarhetsbibliografi, underhållen av Lars Birkedal.
  • van Oosten 2000, och andra förtryck relaterade till realiserbarhet, upprätthålls av Jaap van Oosten.

Rekommenderas: