Set Theory: Constructive And Intuitionistic ZF

Innehållsförteckning:

Set Theory: Constructive And Intuitionistic ZF
Set Theory: Constructive And Intuitionistic ZF

Video: Set Theory: Constructive And Intuitionistic ZF

Video: Set Theory: Constructive And Intuitionistic ZF
Video: Intuitionism and Constructive Mathematics 1/19 2024, Mars
Anonim

Inmatningsnavigering

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

Set Theory: Constructive and Intuitionistic ZF

Först publicerad fredag 20 februari 2009; substantiell revidering ons 13 februari 2019

Konstruktiva och intuitionistiska Zermelo-Fraenkel-setteorier är axiomatiska teorier om uppsättningar i stil med Zermelo-Fraenkel-setteori (ZF) som bygger på intuitionistisk logik. De introducerades på 1970-talet och de representerar ett formellt sammanhang för att kodifiera matematik baserad på intuitionistisk logik (se posten om konstruktiv matematik). De är formulerade på det första ordningsspråket i Zermelo-Fraenkel-setteorin och använder ingen direkt användning av iboende konstruktiva idéer. Genom att arbeta i konstruktiv och intuitionistisk ZF kan vi således till viss del lita på vår bekanta med ZF och dess heuristik.

Trots likheterna med klassisk uppsättningsteori skiljer sig begreppen uppsättning som definieras av konstruktiva och intuitionistiska uppsättningsteorier avsevärt från den i den klassiska traditionen; de skiljer sig också från varandra. Teknikerna som används för att arbeta inom dem såväl som för att få metamatematiska resultat om dem, avviker också i vissa avseenden från den klassiska traditionen på grund av deras engagemang för intuitionistisk logik. I själva verket, som vanligt i intuitionistiska miljöer, finns en mängd semantiska och bevisteoretiska metoder tillgängliga för att studera konstruktiva och intuitionistiska uppsatta teorier.

Detta inlägg introducerar huvuddragen i konstruktiva och intuitionistiska uppsättningsteorier. Eftersom fältet expanderar i snabb takt kan vi bara kort återkalla några viktiga aspekter av resultat och tillgängliga tekniker. Vi fokuserar mer på konstruktiv uppsättningsteori för att lyfta fram viktiga grundläggande frågor som uppstår inom den. Observera att vi utelämnar en iögonfallande del av litteraturen om konstruktiv och intuitionistisk ZF som hänför sig till deras kategoriska tolkningar. Detta område har sett stora utvecklingar under åren, så mycket att en adekvat behandling av dessa framsteg skulle kräva en betydande utvidgning av detta inträde. Den intresserade läsaren kanske vill konsultera posten om kategoriteori och dess referenser (se även tillägget Programmatisk läseguide).

  • 1. Essensen av konstruktiv och intuitionistisk uppsättningsteori

    • 1.1 Axiomatisk frihet
    • 1.2 Konstruktiv kontra intuitionistisk uppsättningsteori
    • 1.3 Predikativitet i konstruktiv uppsättningsteori

      • 1.3.1 Separationens impedicativitet
      • 1.3.2 Powersets impedicativitet
      • 1.3.3 Uppsättningens konstruktiva universum
  • 2. Ursprung av konstruktiva och intuitionistiska uppsättningsteorier
  • 3. Axiomsystemen CZF och IZF
  • 4. Konstruktiva valprinciper
  • 5. Proof Theory and Semantics of Constructive and Intuitionistic ZF

    • 5.1 Bevissteoretisk styrka
    • 5.2 Stora uppsättningar i konstruktiv och intuitionistisk ZF
    • 5.3 Metamatematiska egenskaper hos konstruktiva och intuitionistiska ZF och semantiska tekniker

      • 5.3.1 Konjunktions- och existensegenskaper hos konstruktiv och intuitionistisk ZF
      • 5.3.2 Realiserbarhet
      • 5.3.3 Kripke-modeller och Heyting-värderad semantik
      • 5.3.4 Kategoriska modeller av konstruktiv och intuitionistisk uppsättningsteori
      • 5.4 Varianter av konstruktiva och intuitionistiska uppsättningsteorier: Uppsättningsteorier med urelement och icke-extensional uppsättningsteorier
  • Bibliografi
  • Akademiska verktyg
  • Andra internetresurser
  • Relaterade poster

1. Essensen av konstruktiv och intuitionistisk uppsättningsteori

Konstruktiva och intuitionistiska Zermelo-Fraenkel-setteorier är baserade på intuitionistisk snarare än klassisk logik och representerar en naturlig miljö inom vilken man kan kodifiera och studera matematik baserad på intuitionistisk logik. För konstruktiv ZF har huvudfokus varit att representera den matematiska praktiken för Bishop (Bishop 1967, Bishop and Bridges 1985).

För de grundläggande begreppen och drivande idéer för intuitionistisk logik, konstruktiv matematik och intuitionism, kan läsaren vilja konsultera följande poster:

  • intuitionistisk logik,
  • utvecklingen av intuitionistisk logik,
  • konstruktiv matematik,
  • intuitionism i matematikfilosofin,
  • Luitzen Egbertus Jan Brouwer.

För klassisk setteori, se posten i setteori.

Konstruktiv och intuitionistisk ZF bygger på samma första ordningsspråk som klassisk ZF-uppsättningsteori, som endast har den binära predikatsymbolen (in) (medlemskap) som icke-logisk symbol. Det vill säga de är formulerade utifrån en intuitionistisk första ordningslogik med jämlikhet, plus den binära predikatsymbolen (in). Vi kan alltså dra fördel av enkelheten i det setteoretiska språket och av vår kännedom om det (Myhill 1975). Liksom med konstruktiv matematik i biskopstil, är konstruktiv och intuitionistisk ZF förenlig med den klassiska traditionen, i den meningen att alla deras teorier är klassiskt sanna. I själva verket är de två formella system som vi kommer att överväga, konstruktiva Zermelo-Fraenkel (CZF) och intuitionistiska Zermelo-Fraenkel (IZF),ge upphov till full klassisk ZF genom den enkla tillägget av principen om den uteslutna mitten.

1.1 Axiomatisk frihet

Klassisk Zermelo-Fraenkel-uppsättningsteori är baserad på klassisk första ordens predikatlogik med jämlikhet. Ovanpå de logiska principerna finns axiomer och scheman som beskriver uppfattningen om uppsättning som teorin kodifierar. Dessa principer kan klassificeras i tre slag. För det första finns det principer som gör det möjligt för oss att bilda nya uppsättningar från givna. Exempelvis låter parets axiom bilda en uppsättning som är paret av två givna uppsättningar. För det andra finns det principer som fastställer egenskaperna för den inställda teoretiska strukturen. Till exempel identifierar axiommen för extensivitet alla uppsättningar som har samma element. För det tredje finns det slutligen axiomer som hävdar att det finns specifika uppsättningar. Således säger oändlighets axiom att det finns en oändlig uppsättning. Dessa principer tillsammans kallas vanligtvis set-teoretiska principer.

När man introducerar versioner av ZF baserat på intuitionistisk logik är det första steget att eliminera från logiken principen om den uteslutna mitten (EM). Nästa steg är att välja ett bra lager av setteoretiska principer som troget representerar det önskade begreppet konstruktivt set. Dessa uppgifter visar sig vara mer utmanande än man först kunde ha förväntat sig. Som bekant har faktiskt system som bygger på en "svagare" logik förmågan att skilja mellan påståenden som är likvärdiga med tanke på en "starkare" logik. När det gäller uppsättningsteori presenteras ofta ZF-axiomer eller scheman av en av många klassiskt ekvivalenta formuleringar. Klassiskt är det bara en fråga om bekvämlighet vilken man ska använda vid en viss tidpunkt. När man arbetar utifrån en intuitionistisk logik,olika formuleringar av en klassisk axiom kan visa sig vara distinkta (icke-ekvivalenta). I själva verket kan man föreställa sig nya uttalanden som klassiskt motsvarar ett ZF-axiom men intuitionistiskt åtskilda från det (till exempel CZF: s undersamlingsaxiom (Aczel 1978)).

När det gäller det första steget, som består i att eliminera principen om utesluten mitt från logiken, visar det sig att det är otillräckligt att avvisa denna princip från den underliggande logiken. det vill säga det räcker inte att ta den intuitionistiska snarare än den klassiska predikatberäkningen som vår grund. Vi måste också se till att de setteoretiska axiomerna inte ger oönskade former av uteslutna mitten tillbaka till vår teori. Som exempelvis noterats av Myhill (1973) behöver vi extra omsorg när vi väljer ett lämpligt uttalande för grundens axiom. Foundation införs i uppsättningsteori för att utesluta uppsättningar som är medlemmar i sig själva och därmed (in) - kedjor av uppsättningar. Den vanliga formuleringen av stiftelsen hävdar att varje bebodd set (en uppsättning med minst ett element) har ett minstelement med avseende på medlemsförhållandet. Detta uttalande emellertidkan visas ge konstruktivt oacceptabla fall av uteslutet mitt på basis av blygsamma setteoretiska antaganden. Därför måste den vanliga grundformuleringen utelämnas från en uppsättningsteori baserad på intuitionistisk logik. För ett bevis, se det kompletterande dokumentet:

Setteoretiska principer som är oförenliga med intuitionistisk logik.

Det typiska steget vid formulering av setteorier baserat på intuitionistisk logik är då att ersätta foundation med det klassiskt ekvivalenta schemat för set induktion, som inte har samma "biverkningar" men har liknande konsekvenser. [1]

När det gäller det andra steget, relaterat till valet av ett bra lager av setteoretiska principer, har schemat för ersättning och separering och kraftsatsens axiom väckt mest uppmärksamhet. För den exakta formuleringen av dessa principer se tilläggsdokumentet:

Axiomer av CZF och IZF.

Här är följande ett typiskt scenario. Med tanke på vad som klassiskt är två varianter av en enda setteoretisk princip, kräver deras klassiska bevis på likvärdighet någon gång ett exempel på den uteslutna mitten. I allmänhet kommer detta bevis på ekvivalens emellertid inte att leda till ett intuitionistiskt sammanhang, och följaktligen kan det som klassiskt är två former av en princip resultera i två distinkta principer när man arbetar intuitionistiskt. Att välja en snarare än den andra av dem kan därför påverka uppfattningen om uppsättning som vi således definierar. I samband med konstruktiva uppsättningsteorier som CZF ersätts maktuppsättning och separering av intuitionistiskt svagare principer. En anledning till detta är att den fulla styrkan i kraftuppsättningen och fullständig separering ses som onödig,eftersom deras svagare ersättare verkar räcka för att genomföra konstruktiv matematik. Ett annat skäl är att de ses som filosofiskt problematiska, eftersom de kan införa former av impedicativity inom setteorin (se avsnittet Predicativity i konstruktiv setteori). Fallet med utbyte mot samling är på något sätt mer komplicerat (se till exempel artiklarna (Friedman och Scedrov 1985), (Rathjen 2005) och (Rathjen 2012)). Det är värt att betona att medan antagandet av den vanliga grundformuleringen strider mot själva antagandet om intuitionistisk logik som bakgrundslogik, har principerna om separering och maktuppsättning inte någon oförenlighet med intuitionistisk logik alls, så mycket att de är en integrerad del av intuitionistisk teori för uppsättningar IZF (Friedman 1973a). Ett annat skäl är att de ses som filosofiskt problematiska, eftersom de kan införa former av impedicativity inom setteorin (se avsnittet Predicativity i konstruktiv setteori). Fallet med utbyte mot samling är på något sätt mer komplicerat (se till exempel artiklarna (Friedman och Scedrov 1985), (Rathjen 2005) och (Rathjen 2012)). Det är värt att betona att medan antagandet av den vanliga grundformuleringen strider mot själva antagandet om intuitionistisk logik som bakgrundslogik, har principerna om separering och maktuppsättning inte någon oförenlighet med intuitionistisk logik alls, så mycket att de är en integrerad del av intuitionistisk teori för uppsättningar IZF (Friedman 1973a). Ett annat skäl är att de ses som filosofiskt problematiska, eftersom de kan införa former av impedicativity inom setteorin (se avsnittet Predicativity i konstruktiv setteori). Fallet med utbyte mot samling är på något sätt mer komplicerat (se till exempel artiklarna (Friedman och Scedrov 1985), (Rathjen 2005) och (Rathjen 2012)). Det är värt att betona att medan antagandet av den vanliga grundformuleringen strider mot själva antagandet om intuitionistisk logik som bakgrundslogik, har principerna om separering och maktuppsättning inte någon oförenlighet med intuitionistisk logik alls, så mycket att de är en integrerad del av intuitionistisk teori för uppsättningar IZF (Friedman 1973a).eftersom de kan införa former av impredicativity inom setteorin (se avsnittet Predicativity i konstruktiv setteori). Fallet med utbyte mot samling är på något sätt mer komplicerat (se till exempel artiklarna (Friedman och Scedrov 1985), (Rathjen 2005) och (Rathjen 2012)). Det är värt att betona att medan antagandet av den vanliga grundformuleringen strider mot själva antagandet om intuitionistisk logik som bakgrundslogik, har principerna om separering och maktuppsättning inte någon oförenlighet med intuitionistisk logik alls, så mycket att de är en integrerad del av intuitionistisk teori för uppsättningar IZF (Friedman 1973a).eftersom de kan införa former av impredicativity inom setteorin (se avsnittet Predicativity i konstruktiv setteori). Fallet med utbyte mot samling är på något sätt mer komplicerat (se till exempel artiklarna (Friedman och Scedrov 1985), (Rathjen 2005) och (Rathjen 2012)). Det är värt att betona att medan antagandet av den vanliga grundformuleringen strider mot själva antagandet om intuitionistisk logik som bakgrundslogik, har principerna om separering och maktuppsättning inte någon oförenlighet med intuitionistisk logik alls, så mycket att de är en integrerad del av intuitionistisk teori för uppsättningar IZF (Friedman 1973a). Det är värt att betona att medan antagandet av den vanliga grundformuleringen strider mot själva antagandet om intuitionistisk logik som bakgrundslogik, har principerna om separering och maktuppsättning inte någon oförenlighet med intuitionistisk logik alls, så mycket att de är en integrerad del av intuitionistisk teori för uppsättningar IZF (Friedman 1973a). Det är värt att betona att medan antagandet av den vanliga grundformuleringen strider mot själva antagandet om intuitionistisk logik som bakgrundslogik, har principerna om separering och maktuppsättning inte någon oförenlighet med intuitionistisk logik alls, så mycket att de är en integrerad del av intuitionistisk teori för uppsättningar IZF (Friedman 1973a).

För att sammanfatta, när man formulerar en uppsättningsteori baserad på intuitionistisk logik, är den första uppgiften att utvisa principen om utesluten mitt, inklusive de instanser av den som kan döljas i kända formuleringar av setteoretiska axiomer. Nästa uppgift är att välja en version av varje klassisk princip som bäst kännetecknar önskad uppsättning. Detta öppnar en rad olika val man kan göra, eftersom ett flertal intuitionistiska principer kan motsvara en klassisk princip. Det bör betonas att ur ett konstruktivt perspektiv är denna mångfald av alternativ (och därmed system) snarare än att orsaka oro, en mycket önskvärd situation, eftersom den utgör en form av "axiomatisk frihet". Till exempel tillåter det oss att skilja mellan ett antal matematiska föreställningar och därmed bättre fånga våra intuitioner av dem som distinkta. Det ger oss också friheten att välja de föreställningar och teorier som bäst passar ett givet sammanhang. Genom att anta intuitionistisk logik kan vi dessutom inom våra teorier inkludera principer som är klassiskt mycket starka, utan att behöva förbinda sig till deras klassiska styrka. Till exempel kan man lägga till en uppfattning om otillgänglig uppsättning i en svag konstruktiv uppsättningsteori och få en predikativ teori, medan samma uppfattning inbäddad i ett klassiskt sammanhang blir extremt stark (se avsnitten om Predikativitet i konstruktiv uppsättningsteori och stora uppsättningar i konstruktivt och intuitionistisk ZF). Slutligen uppstår naturligtvis ett rikt område med (metateoretisk) studie av förhållandena mellan de resulterande distinkta setteoretiska systemen. Som man kan förvänta sig har denna frihet också ett pris,som en högteknisk studie av de axiomatiska teorierna kan vara nödvändig för att skilja deras principer såväl som för att avslöja några av deras subtiliteter. Detta kan återigen ses som en fördel, eftersom det tvingar oss till en djupare och tydligare analys av de matematiska uppfattningarna som berörs och ber oss att utveckla nya sofistikerade verktyg.

1.2 Konstruktiv kontra intuitionistisk uppsättningsteori

Även om det finns många system med uppsättningar baserade på intuitionistisk logik, kan vi skilja två huvudtrender inom litteraturen. Enligt den första tar vi allt som finns tillgängligt i klassisk ZF-uppsättningsteori och modifierar bara de principerna, till exempel grund, som har en tydlig oförenlighet med intuitionistisk logik. Detta ger upphov till uppsatta teorier som Intuitionistic Zermelo-Fraenkel, IZF, vars variant introducerades redan i (Friedman 1973a). (Se Beeson 1985, kapitel 8 och 9 och Scedrov 1985 för två undersökningar om IZF.) Motiveringen bakom dessa teorier verkar vara att ge matematikern de mest kraftfulla verktygen som är möjliga, så länge kompatibilitet med intuitionistisk logik bevaras. Enligt den andra metoden,utöver anslutningen till intuitionistisk logik inför vi också begränsningar för de uppsatta teoretiska principerna, såvitt det resulterande systemet uppfyller den konstruktiva matematiska praxisen. Teorier av denna andra typ kan således ses som resultatet av en dubbel restriktionsprocess med avseende på klassisk ZF. Först finns det en begränsning av intuitionistisk logik, sedan införs en begränsning för de tillåtna setteoretiska konstruktionerna. Det senare motiveras av (1) iakttagelsen av att svagare principer verkar räcka för den konstruktiva matematiska praxisen och (2) önskan att hålla sig till en form av predikativitet (se nästa avsnitt för en förtydligande av denna uppfattning om predikativitet). Paradigmatiska exempel på den sistnämnda typen av system är Myhill's Constructive Set Theory (Myhill 1975),Friedmans system B (Friedman 1977) och Aczels konstruktiva Zermelo-Fraenkel uppsatte teori CZF (Aczel 1978; 1982; 1986, Aczel & Rathjen 2001; Aczel & Rathjen 2010, andra internetresurser). Vi kan också säga att i denna andra metod påverkar grundmotivationen övningen i högre grad.

I det följande använder vi oss av en konvention som ofta finns på plats idag, enligt vilken adjektivet”intuitionistisk” hänvisar till de uppsatta teorierna, såsom IZF, som är impregnerande, medan”konstruktiva” hänvisar till uppsatta teorier, såsom CZF, som överensstämmer med en form av predikativitet. Observera dock att denna konvention inte alltid följs i litteraturen. I själva verket har adjektivet "konstruktiva" också använts för att beteckna impredicative teorier, och "intuitionistic" för att hänvisa till predicative grundläggande teorier som Martin-Löf typteori (Martin-Löf 1975; 1984). Det är också värt att notera att den nuvarande konventionen om användningen av orden”konstruktiv” och”intuitionistisk” skiljer sig från den som gjorts i samband med konstruktiv matematik (se till exempel posten om konstruktiv matematik och även Bridges och Richman 1987).

1.3 Predikativitet i konstruktiv uppsättningsteori

Predikativism har sitt ursprung i skrifterna av Poincaré och Russell, som svarade på de paradoxer som upptäcktes i Cantors och Freges uppsättningsteorier i början av 1900-talet. Därefter gav Weyl grundläggande bidrag till studien av predikativ matematik (Weyl 1918, se även Feferman 1988). Enligt en uppfattning är en definition imponerande om den definierar ett objekt med hänvisning till en helhet som inkluderar objektet som ska definieras. Med sitt Vicious Circle Principle (VCP) avsåg Russell att eliminera cirkulariteten i matematik som uppstår från sådana impregnerande definitioner. Russell gav olika formuleringar av VCP, varav en är:

Det som innehåller en uppenbar variabel får inte vara ett möjligt värde för den variabeln (Russell 1908, i van Heijenoort 1967, 163).

Poincaré, Russell och Weyls grundläggande analys av predikativitet har banat vägen för en mängd logiska analyser av idén. Den vanligast accepterade analysen beror på Feferman och Schütte (oberoende) efter rader indikerade av Kreisel (Kreisel 1958, Feferman 1964 och Schütte 1965; 1965a). Här har bevisteorin spelat en viktig roll. I mycket grova termer var tanken att utesluta en samling teorier (en transfinit progression av system med förstärkta andra ordningens aritmetiska indexerade av ordinarier) med hjälp av vilka man kan karakterisera en viss uppfattning om predikativ ordinal. Feferman och Schüttes bevisteoretiska analys av dessa teorier har identifierat en ordinal, vanligtvis kallad (Gamma_0), som är den minst icke-predikativa ordinalen enligt denna uppfattning. Ett formellt system anses predikativt motiverat om det är bevisteoretiskt reducerbart till ett system med förstärkt andra ordning armetmetiskt indexerat av en ordinär mindre än (Gamma_0). Därför anses i bevisteori (Gamma_0) normalt representera gränsen för predikativitet. (Se Feferman 2005 för en mer exakt informell redogörelse för denna uppfattning om predikativitet och för ytterligare referenser. Se även Crosilla 2017. Läsaren kan också se avsnittet om predikativism i posten om matematikfilosofi och inträde om paradoxer och samtida logik).(Se Feferman 2005 för en mer exakt informell redogörelse för denna uppfattning om predikativitet och för ytterligare referenser. Se även Crosilla 2017. Läsaren kan också se avsnittet om predikativism i posten om matematikfilosofi och inträde om paradoxer och samtida logik).(Se Feferman 2005 för en mer exakt informell redogörelse för denna uppfattning om predikativitet och för ytterligare referenser. Se även Crosilla 2017. Läsaren kan också se avsnittet om predikativism i posten om matematikfilosofi och inträde om paradoxer och samtida logik).

För konstruktiva grundläggande teorier har en mer "liberal" metod för predikativism föreslagits, från början från slutet av 1950-talet av Lorenzen, Myhill och Wang (se t.ex. Lorenzen och Myhill 1959). Den drivande idén är att så kallade induktiva definitioner borde tillåtas inom området konstruktiv matematik. Den intuitiva motiveringen av induktiva definitioner är relaterad till det faktum att de kan uttryckas med begränsade regler på ett "bottom-up" sätt. Den bevisteoretiska styrkan i teorier om induktiva definitioner går långt utöver Feferman och Schüttes gräns (Buchholz, Feferman, Pohlers och Sieg 1981). Således anses relativt starka teorier vara predikativa i dagens grundval av konstruktiv matematik. Denna mer liberala uppfattning om predikativitet har ofta kallats generaliserad predikativitet. I det här inlägget skriver vi helt enkelt predikativitet för generaliserad predikativitet och kallar predikativitet med tanke på de naturliga siffrorna den bättre kända formen för predikativitet som uppstår i det klassiska sammanhanget och analyserades av Kreisel, Feferman och Schütte.

Ett exempel på en predikativ teori i denna mening är den konstruktiva uppsättningsteorin CZF, eftersom dess bevisteoretiska styrka är densamma som för en teori för en induktiv definition känd som ID (_ 1). Systemet IZF är istället imponerande, eftersom dess bevisteoretiska styrka motsvarar hela klassiska ZF (Friedman 1973a).

I uppsatta teorier baserade på intuitionistisk logik uppnås predikativitet vanligtvis genom att begränsa principerna för separering och maktuppsättning, eftersom dessa verkar vara de viktigaste källorna till impredicativity (när oändlighetsaxiom antas).

1.3.1 Separationens impedicativitet

Schemat för separering tillåter oss att bilda en delmängd av en given uppsättning vars element tillfredsställer en given egenskap (uttryckt med en formel på setteoriens språk). Med en uppsättning (B) och en formel (phi (X)) tillåter separering oss att konstruera en ny uppsättning, uppsättningen av de elementen (X) för (B) för vilka (phi) håller. Detta representeras vanligtvis informellt som: ({X / i B: / phi (X) }). Separation kan leda till impedicativitet om formeln (phi) innehåller obegränsade kvantifierare som sträcker sig över hela universums set; i själva verket, när vi definierar den nya uppsättningen genom separering kan vi alltså hänvisa till denna uppsättning, vilket motsäger Russells VCP. Om vi till exempel definierar en uppsättning (C) genom separering som ({X / i B: / för alla Y / psi (X, Y) }), är (C) bland (Y) som måste kontrolleras för egenskapen (psi). Denna form av impedicativitet undviks i konstruktiv uppsättningsteori genom att begränsa separationsschemat: genom att kräva att alla kvantifierare som förekommer i formeln (phi) bara sträcker sig över "tidigare konstruerade" uppsättningar. Syntaktiskt betyder detta att med en uppsättning (B) kan vi bilda en ny uppsättning ({X / i B: / phi (X) }) genom separering endast om alla kvantifierare i (phi) är avgränsade; det vill säga bara om alla kvantifierare i (phi) har formen (för alla X (X / i Y / högermark / ldots)) eller (finns X (X / i Y / kil / ldots))), för vissa uppsättningar (Y).\ phi (X) }) genom separering endast om alla kvantifierare i (phi) är begränsade; det vill säga bara om alla kvantifierare i (phi) har formen (för alla X (X / i Y / högermark / ldots)) eller (finns X (X / i Y / kil / ldots))), för vissa uppsättningar (Y).\ phi (X) }) genom separering endast om alla kvantifierare i (phi) är begränsade; det vill säga bara om alla kvantifierare i (phi) har formen (för alla X (X / i Y / högermark / ldots)) eller (finns X (X / i Y / kil / ldots))), för vissa uppsättningar (Y).

Vi kan se att begränsa separationen på detta sätt undviker impredicativity, genom att observera att den bevisteoretiska styrkan hos CZF, som endast har begränsat separationen, ligger inom räckvidden för predikativitet. Men genom att lägga till fullständig separering till CZF erhåller man emellertid en impregnerande teori, i själva verket en med samma bevisteoretiska styrka som fullständig andra ordningens aritmetik (Lubarsky 2006). Se även avsnitt 5 för en diskussion om bevisteorins roll vid analys av konstruktiva och intuitionistiska uppsättningsteorier.

1.3.2 Powersets impedicativitet

Power set axiom gör det möjligt för oss att bilda en uppsättning av alla delmängder i en given uppsättning. Ett exempel på impedikativ användning av kraftsats ges genom definitionen av en delmängd av de naturliga siffrorna, (N), enligt följande: (B: = {n / i N: / för alla C / subseteq N / phi (n, C) }), där (phi) kan anses vara en begränsad formel. En form av cirkularitet uppstår här eftersom (B) i sig är bland delmängderna av (N) som måste kontrolleras för (phi). Som framhävts av Myhill (1975, 354), är kraftuppsättningen svår att motivera ur en konstruktiv synvinkel: den samlar alla delmängderna i en given uppsättning, men föreskriver inte en regel som "konstruerar" uppsättningen från tidigare givna uppsättningar. sätter, som predikativitet verkar kräva.

Myhill skriver:

Kraftsats verkar speciellt icke-konstruktivt och imponerande jämfört med de andra axiomerna: det innebär inte, som de andra gör, att sätta ihop eller ta isär apparater som man redan har konstruerat utan snarare välja ur totaliteten för alla uppsättningar de som står i relationen av inkludering i en given uppsättning. (Myhill 1975, 351).

Kraftsats verkar särskilt problematiskt när det gäller oändliga uppsättningar, eftersom "vi har ingen aning om vad en godtycklig delmängd av en oändlig uppsättning är; det finns inget sätt att generera dem alla och så vi har inget sätt att bilda uppsättningen för alla dem "(Myhill 1975, 354). Som en konsekvens verkar det inte finnas något sätt att ge konstruktivt förnuft till uppsättningen av alla undergrupper i en oändlig uppsättning.

Myhill konstaterar avgörande att kraftsats inte behövs för konstruktiv matematikbiskopstil, eftersom det kan ersättas av en av dess konsekvenser. Detta kallas ofta Myhills exponentiation axiom och säger att vi kan bilda en uppsättning av alla funktioner från en given uppsättning till en annan. Denna axiom är helt klart ekvivalent med effektuppsättningen i ett klassiskt sammanhang, där delmängder av en given uppsättning kan representeras av karakteristiska funktioner. I avsaknad av principen om utesluten mitt är maktuppsättning och exponentiering emellertid inte likvärdiga. Myhills grundläggande iakttagelse är att exponentiering räcker för att utföra matematiken i (Bishop 1967); till exempel tillåter det konstruktion av (Cauchy) verkliga siffror inom konstruktiv uppsättningsteori. Myhill hävdar att exponentiering är konstruktivt meningsfullt eftersom en funktion är en regel,ett ändligt objekt som faktiskt kan ges.

Han skriver också att fallet med maktuppsättning skiljer sig från exponentiering som:

även när det gäller oändliga uppsättningar (A) och (B) har vi en idé om en godtycklig mappning från (A) till (B). En godtycklig mappning från (mathbf {Z}) till (mathbf {Z}) är en partiell rekursiv funktion tillsammans med ett bevis på att beräkningen alltid upphör; ett liknande konto kan anges för en godtycklig verklig funktion. Det finns ingen motsvarande förklaring av "godtycklig delmängd". (Myhill 1975, 354).

Myhills exponentiation axiom är nu en del av alla större system för konstruktiv setteori. När det gäller CZF har man faktiskt en förstärkning av exponentiering, känd som delmängdsamling, vilket också är en försvagning av kraftsättningen. En generalisering av exponentiering finns också i konstruktiv typteori.

När det gäller CZF kan påståendet att lägga till kraftsatsaxiom inducerar en form av impedicativitet underbyggas av ett tekniskt resultat. Rathjen (2012b) visar att CZF förstärkt av kraftsatsaxiom överstiger styrkan i klassisk Zermelo-setteori, och att tillägget av kraftsatsaxiom till CZF ger oss till en helt imponerande teori. Detta visar också att implikationen från kraftsats till delmängdssamling inte kan vändas, eftersom CZFs bevisteoretiska styrka ligger långt under Zermleo-setteorin. I andra termer är kraftuppsättningens axiom mycket starkare än både exponentiering och delmängdsuppsamling.

1.3.3 Uppsättningens konstruktiva universum

Efter att ha infört lämpliga begränsningar för strömförsörjning och separering kunde vi nu möta en väsentlig invändning. Konstruktiva och intuitionistiska uppsättningsteorier kan ses som modifieringar av klassisk ZF-uppsättningsteori som erhålls genom: (1) ersätta klassisk med intuitionistisk logik, och (2) noggrant välja bland olika klassiskt likvärdiga principer som verkar lämpligare för givna ändamål. Vi kan till exempel välja principer som är tillräckliga för att representera en viss matematisk praxis, som till exempel matematik för biskopsstil. Den resulterande uppfattningen om uppsättning kan emellertid bli otydlig och valet av uppsättningsteoretiska principer kan i viss mån framstå som godtyckligt. När det gäller intuitionistiska ZF kan man motivera valet av set-teoretiska principer genom att undersöka dess semantiska tolkningar,som Heyting semantik, eller genom att titta på dess kategoriska modeller. När det gäller konstruktiv setteori, för att hindra denna typ av invändningar, har Aczel gett en tolkning av CZF i en version av Martin-Löf typteori (Aczel 1978). Påståendet är att en klar konstruktiv mening alltså tilldelas CZFs uppfattning om uppsättning genom att titta på dess betydelse i Martin-Löf typteori, eftersom den senare vanligtvis anses representera en korrekt och helt motiverad formulering av en konstruktiv uppfattning om uppsättning. Aczels tolkning av CZF i konstruktiv typteori ges genom att interpetera uppsättningar som träd i typteori. Det vill säga, i konstruktiv typteori representeras universumet av uppsättningar av CZF av en typ, V, av iterativa uppsättningar byggda över universum, U, av små typer (Aczel 1978; Martin-Löf 1984). Denna tolkning belyser tydligt (generaliserad) predikativitet för CZF, vars uppsättningar kan ses som träd byggda induktivt, och vars uppsatta teoretiska universum också har en tydlig induktiv struktur.

Predikativiteten för CZF och relaterade system överensstämmer med filosofiska positioner som ofta är förknippade med användningen av intuitionistisk logik. I synnerhet verkar det som om vi konstruerar de matematiska objekten, till exempel, om de matematiska föremålen är mentala konstruktioner av något slag, skulle det att ta till impredikativa definitioner ge en oönskad form av cirkularitet. Detta står klart i kontrast till en vy som ofta är associerad med klassisk uppsättningsteori, för vilken vår matematiska aktivitet kan ses som en gradvis avslöjande av egenskaper hos uppsättningens universum, vars existens är oberoende av oss. En sådan uppfattning är vanligtvis bunden med användningen av klassisk logik och impredicativity för att studera det setteoretiska universum. Predikativitet ses också ofta som relaterat till den tidshöjda skillnaden mellan faktisk och potentiell oändlighet. Predikativa (och därmed i synnerhet konstruktiva) teorier ses ofta som att undvika referens till faktisk oändlighet och endast förbinda sig till potentiell oändlighet (Dummett 2000, Fletcher 2007). Detta verkar igen särskilt i harmoni med de filosofiska positioner som belyser den mänskliga dimensionen av vår matematiska aktivitet genom att till exempel se de matematiska föremålen och sanningen om uttalanden om dem som beroende av oss. En annan besläktad aspekt ses ofta som avser predikativitet: om universums setuppbyggnad byggs upp i etapper av vår egen matematiska aktivitet, skulle det också vara naturligt att se det som öppet slut. Av detta skäl, i ett konstruktivt sammanhang,där avvisningen av klassisk logik uppfyller kravet på predikativitet, beskrivs setenes universum ofta som ett öppet begrepp, ett universum "in fieri". Denna idé exemplifieras särskilt väl inom konstruktiv typteori, där begreppet typteoretiskt universum medvetet har lämnats öppen av Per Martin-Löf (genom att inte postulera specifika eliminationsregler för det). Uppsättningsuniversitetens universum har banat vägen för förlängningar av det genom reflektionsprinciper. Dessa har undersökts både inom typteori och konstruktiv uppsättningsteori. Se (Rathjen 2005a) för en undersökning av resultat och en grundläggande diskussion, och även avsnitt 5.2. För en formell analys av det konstruktiva universum av uppsättningar och en jämförelse med Von Neumann-hierarkin, se (Ziegler 2014).setens universum beskrivs ofta som ett öppet koncept, ett universum "in fieri". Denna idé exemplifieras särskilt inom konstruktiv typteori, där föreställningen om typteoretiskt universum medvetet har lämnats öppen av Per Martin-Löf (genom att inte postulera specifika eliminationsregler för det). Uppsättningsuniversitetens universum har banat vägen för förlängningar av det genom reflektionsprinciper. Dessa har undersökts både inom typteori och konstruktiv uppsättningsteori. Se (Rathjen 2005a) för en undersökning av resultat och en grundläggande diskussion, och även avsnitt 5.2. För en formell analys av det konstruktiva universum av uppsättningar och en jämförelse med Von Neumann-hierarkin, se (Ziegler 2014).setens universum beskrivs ofta som ett öppet koncept, ett universum "in fieri". Denna idé exemplifieras särskilt inom konstruktiv typteori, där föreställningen om typteoretiskt universum medvetet har lämnats öppen av Per Martin-Löf (genom att inte postulera specifika eliminationsregler för det). Uppsättningsuniversitetens universum har banat vägen för förlängningar av det genom reflektionsprinciper. Dessa har undersökts både inom typteori och konstruktiv uppsättningsteori. Se (Rathjen 2005a) för en undersökning av resultat och en grundläggande diskussion, och även avsnitt 5.2. För en formell analys av det konstruktiva universum av uppsättningar och en jämförelse med Von Neumann-hierarkin, se (Ziegler 2014).där föreställningen om typteoretiskt universum medvetet har lämnats öppen av Per Martin-Löf (genom att inte postulera specifika eliminationsregler för det). Uppsättningsuniversitetens universum har banat vägen för förlängningar av det genom reflektionsprinciper. Dessa har undersökts både inom typteori och konstruktiv uppsättningsteori. Se (Rathjen 2005a) för en undersökning av resultat och en grundläggande diskussion, och även avsnitt 5.2. För en formell analys av det konstruktiva universum av uppsättningar och en jämförelse med Von Neumann-hierarkin, se (Ziegler 2014).där föreställningen om typteoretiskt universum medvetet har lämnats öppen av Per Martin-Löf (genom att inte postulera specifika eliminationsregler för det). Uppsättningsuniversitetens universum har banat vägen för förlängningar av det genom reflektionsprinciper. Dessa har undersökts både inom typteori och konstruktiv uppsättningsteori. Se (Rathjen 2005a) för en undersökning av resultat och en grundläggande diskussion, och även avsnitt 5.2. För en formell analys av det konstruktiva universum av uppsättningar och en jämförelse med Von Neumann-hierarkin, se (Ziegler 2014). Dessa har undersökts både inom typteori och konstruktiv uppsättningsteori. Se (Rathjen 2005a) för en undersökning av resultat och en grundläggande diskussion, och även avsnitt 5.2. För en formell analys av det konstruktiva universum av uppsättningar och en jämförelse med Von Neumann-hierarkin, se (Ziegler 2014). Dessa har undersökts både inom typteori och konstruktiv uppsättningsteori. Se (Rathjen 2005a) för en undersökning av resultat och en grundläggande diskussion, och även avsnitt 5.2. För en formell analys av det konstruktiva universum av uppsättningar och en jämförelse med Von Neumann-hierarkin, se (Ziegler 2014).

2. Ursprung av konstruktiva och intuitionistiska uppsättningsteorier

Intuitionistiska versioner av Zermelo-Fraenkel-setteorier introducerades i början av 1970-talet av Friedman och Myhill. I (Friedman 1973) presenterar författaren en studie av formella egenskaper hos olika intuitionistiska system och introducerar för dem en förlängning av Kleens realiseringsmetod. Realiserbarhetstekniken tillämpas i (Myhill 1973) för att visa existensegenskapen för en version av den intuitionistiska Zermelo-Fraenkel-setteorin (med ersättning istället för samlingen). I ett annat grundläggande bidrag utvidgar Friedman den dubbla negativa översättningen av intuitonistisk logik för att relatera klassiska och intuitionistiska uppsättningsteorier (Friedman 1973a). Dessa första artiklar behandlar redan förhållandet mellan några stora intuitionistiska uppsättningsteorier och klassiska ZF. De klargör också ett viktigt inslag i uppsättningsteori baserat på intuitionistisk logik,främst att det är mottagligt för kraftfulla konstruktiva semantiska tolkningar, som realiserbarhet. Dessa tekniker används för att studera avgörande metatoretiska egenskaper som är typiska för det konstruktiva tillvägagångssättet och som åtnjuts av vissa konstruktiva uppsatta teorier (se avsnittet om semantiska tekniker). Detta banbrytande arbete har utnyttjats och utvidgats avsevärt i arbetet av Beeson och McCarty (se Beeson 1985; McCarty 1984). Detta banbrytande arbete har utnyttjats och utvidgats avsevärt i arbetet av Beeson och McCarty (se Beeson 1985; McCarty 1984). Detta banbrytande arbete har utnyttjats och utvidgats avsevärt i arbetet av Beeson och McCarty (se Beeson 1985; McCarty 1984).

Konstruktiv setteori från början har en mer distinkt grundläggande kallelse och den är bunden till Bishop's matematik. I själva verket publicerade Bishop 1967 boken "Fundament of constructive analysis" (Bishop 1967), som öppnade en ny era för matematik baserad på intuitionistisk logik (se posten om konstruktiv matematik). Monografin stimulerade nya försök i det logiska samhället att klargöra och formellt representera de principer som användes av Bishop, men bara på en informell nivå. De första försöken av Goodman och Myhill (Goodman och Myhill 1972) använde versioner av Gödels system T (se även (Bishop 1970) för ett liknande försök). Myhill nådde dock slutsatsen att den resulterande formaliseringen var för komplex och konstgjord (Myhill 1975, 347). Myhill föreslog istället ett system som är närmare det informella begreppet set som ursprungligen användes av Bishop och också närmare den set-teoretiska traditionen. Myhill skriver (1975, 347):

Vi vägrar att tro att saker måste vara så komplicerade - argumentationen från (Bishop 1967) ser väldigt smidig ut och verkar falla direkt från ett visst begrepp om vad som uppsättningar, funktioner etc. är, och vi vill upptäcka en formalism som isolerar principerna som ligger bakom denna uppfattning på samma sätt som Zermelo-Fraenkel uppsättningsteori isolerar principerna bakom klassisk (icke-konstruktiv) matematik. Vi vill att dessa principer ska vara sådana att formaliseringsprocessen blir fullständig trivial, som i det klassiska fallet.

Vi observerar här att Myhils konstruktiva uppsättningsteori hade utmärkt föreställningar om funktion, naturligt antal och uppsättning; det representerade således nära en konstruktiv tradition där funktioner och naturliga antal är konceptuellt oberoende av uppsättningar. Ett annat grundläggande steg i utvecklingen av konstruktiv uppsättningsteori var Friedmans “Set-teoretiska grunder för konstruktiv analys” (Friedman 1977). Här definieras bland andra system ett system som kallas B som har ytterligare begränsningar för set-teoretiska principer jämfört med Myhills (i synnerhet har det ingen inställd induktion). Det har också en begränsad form av axiom av beroende val. System B visas där att det är tillräckligt uttryckligt för att representera den konstruktiva analysen av Bishop (1967) samtidigt som det är teoretiskt mycket svagt (på grund av frånvaron av inställd induktion). System B är i själva verket en konservativ förlängning av aritmetiken (det är alltså långt under gränsen för predikativitet med tanke på de naturliga siffrorna som kort återkallas i avsnitt 1.3). Myhill och Friedmans system modifierades därefter av Aczel för att erhålla ett system, CZF (Constructive Zermelo-Fraenkel), som är fullt kompatibelt med ZF-språket (Aczel 1978, 1982, 1986; Aczel och Rathjen 2001; 2010). CZF inkluderade inte heller några valprinciper. Aczel gav en tolkning av CZF i Martin-Löf typteori med syftet att bekräfta den konstruktiva naturen hos setteorin. Han förstärkte också några av principerna i Myhills system (nämligen samling och exponentiering) på grund av att de starkare versionerna fortfarande valideras av tolkningen i typteorin.

Andra grundläggande system för konstruktiv matematik i biskopstil introducerades i början av 1970-talet. Till exempel: uttrycklig matematik av S. Feferman (Feferman 1975) och den redan nämnda intuitionistiska typteorin (Martin-Löf 1975; 1984). Konstruktiv typteori anses vanligtvis vara den mest tillfredsställande grunden för konstruktiv matematikbiskopstil. Både typteori och uttrycklig matematik kan ses som att de mer direkt uttrycker beräkningsinnehållet i konstruktiv matematik. Typteori kan i synnerhet läsas som ett mycket allmänt och uttrycksfullt programmeringsspråk. Konstruktiva och intuitionistiska uppsättningsteorier visar deras beräkningsinnehåll endast indirekt genom sina semantiska tolkningar (se t.ex. (Aczel 1977), (Lipton 1995) och avsnittet om semantiska tekniker).

3. Axiomsystemen CZF och IZF

För en läsare som redan är bekant med ZF-setteorin, återkallar vi nu kort axiomerna för systemen CZF och IZF. För en fullständig lista och en förklaring av deras axiomer hänvisar vi istället till det kompletterande dokumentet:

Axiomer av CZF och IZF.

CZF och IZF formuleras på grundval av intuitionistisk första ordningslogik med jämlikhet, med endast (in) (medlemskap) som en ytterligare icke-logisk binär predikatsymbol. Deras setteoretiska axiomer är som följer.

(Mathbf {IZF}) (Mathbf {CZF})
Extensionality (samma)
Par (samma)
Union (samma)
Oändlighet (samma)
Separation Begränsad separering
Samling Stark samling
Powerset Delmängdsamling
Ställ in induktion (samma)

Observera att i IZF är separationsschemat obegränsat. I CZF stärks Collection för att kompensera för begränsad separering. Delmängdsamling är en förstärkning av Myhills exponentieringaxiom och ersätter därmed ZFs Powerset.

4. Konstruktiva valprinciper

När man diskuterar rollen som klassisk uppsättningsteori som grund för matematik, betraktar man vanligtvis teorin ZFC, det vill säga axiomsystemet ZF plus valet axiom (AC). Man kan därför undra vad är statusen för valet axiom i intuitionistiska miljöer. Frågan är särskilt viktig eftersom valets axiom ofta sågs som kontroversiellt och mycket icke-konstruktivt vid sin första uppträdande. I konstruktiva sammanhang bevittnar man emellertid ett märkligt fenomen. Den vanliga formen för valet axiom valideras av teorier av typer som Martin-Löf typteori, där Curry-Howard korrespondens har (Se avsnitt 3.4 i posten om konstruktiv matematik). Å andra sidan ger antagandet om valet axiom upphov till fall av det uteslutna mitten i extensionssammanhang,där en form av separering också finns. Detta är till exempel fallet med konstruktiv och intuitionistisk ZF. (För beviset, se det kompletterande dokumentet om setteoretiska principer som är oförenliga med intuitionistisk logik.) Ett bevis på oförenlighet med AC med extensional setteorier baserat på intuitionistisk logik verkar först ha dykt upp i (Diaconescu 1975) i ett kategoriskt sammanhang. Goodman och Myhill ger ett argument för uppsatta teorier baserade på intuitionistisk logik (Goodman och Myhill 1978).) Ett bevis på AC: s inkompatibilitet med utvidgade uppsatta teorier baserade på intuitionistisk logik verkar först ha dykt upp i (Diaconescu 1975) i ett kategoriskt sammanhang. Goodman och Myhill ger ett argument för uppsatta teorier baserade på intuitionistisk logik (Goodman och Myhill 1978).) Ett bevis på AC: s inkompatibilitet med utvidgade uppsatta teorier baserade på intuitionistisk logik verkar först ha dykt upp i (Diaconescu 1975) i ett kategoriskt sammanhang. Goodman och Myhill ger ett argument för uppsatta teorier baserade på intuitionistisk logik (Goodman och Myhill 1978).

Även om valet axiom är oförenligt med både konstruktiv och intuitionistisk ZF, kan andra valprinciper läggas till de grundläggande systemen utan att ge samma oönskade resultat. Till exempel kan man lägga till principen om räknbart val (AC (_ 0)) eller principen om beroende val (DC). I själva verket har båda ofta använts i den konstruktiva matematiska praxis. (För deras exakta formulering se tilläggsdokumentet om Axioms of CZF and IZF.)

I (Aczel 1978) övervägde författaren också en valprincip som kallas Presentation Axiom, som hävdar att varje uppsättning är den subjektiva bilden av en så kallad bas. En bas är en uppsättning, säg (B), så att varje relation med domän (B) utökar en funktion med domän (B).

Förenligheten med alla dessa valformer med konstruktiv setteori har bevisats av Aczel genom att utvidga hans tolkning av CZF i Martin-Löf typteori (Aczel 1982). Rathjen (2006) har också beaktat olika konstruktiva valprinciper och deras ömsesidiga relationer.

En sista kommentar: även om konstruktiva och intuitionistiska uppsättningsteorier är förenliga med de nyss nämnda valprinciperna, definieras uppsättningsteorierna ofta utan några valprinciper. Detta har som mål att möjliggöra en”pluralistisk” grundläggande strategi. I synnerhet skulle man vilja erhålla en grundläggande teori som är kompatibel med dessa sammanhang (t.ex. kategoriska modeller för uppsättningsteori) där till och med dessa svagare val av principer inte kan valideras. För liknande idéer i samband med konstruktiv typteori, se (Maietti och Sambin 2005, Maietti 2009). Vi vill också här nämna Richmans vädjan för en konstruktiv matematik som inte använder valprinciper (Richman 2000; 2001).

5. Proof Theory and Semantics of Constructive and Intuitionistic ZF

När vi betraktar en viss matematisk praxis (eller en teori som används för att kodifiera den) ur ett filosofiskt perspektiv, måste vi med största möjliga precision klargöra antagandena som görs inom den såväl som konsekvenserna av dessa antaganden. Detta är särskilt sant när man arbetar med teorier som bygger på en svagare logik än den klassiska, för vilken en djupare, mer exakt insikt är obligatorisk. Det finns många tekniska verktyg som kan hjälpa oss att förtydliga dessa aspekter. Bland de tillgängliga instrumenten finns det bevisteoretiska tekniker, såsom bevisteoretiska tolkningar, samt semantiska tekniker, såsom realiserbarhet, Kripke-modeller, Heyting-värderad semantik. Faktum är att man i litteraturen ofta bevittnar samspelet mellan bevisteoretiska och semantiska tekniker. Vi tittar här på några av dessa ämnen och föreslår ytterligare läsning.

5.1 Bevissteoretisk styrka

Ett grundläggande tema i bevisteorin (särskilt i grenen av denna disciplin, känd som ordinalanalys) är klassificering av teorier med hjälp av transfinite ordinaler som mäter deras "konsistensstyrka" och "beräkningskraft". Dessa ordinaler ger en indikation på hur stark teori är och erbjuder därför ett sätt att jämföra olika teorier. Exempelvis är ordinalen (varepsilon_0) den bevisteoretiska ordinalen för Peano Arithmetic och är mycket mindre än ordinalen (Gamma_0), vanligtvis benämnd "gränsen för predikativitet" (se avsnitt 1.3 ovan)). Detta tyder på att det finns predikativt godtagbara teorier som är mycket starkare än Peano Arithmetic.

Som diskuterats i avsnitt 1 kräver steget från klassisk ZF till dess intuitionistiska varianter att vi väljer en lämplig formulering för varje setteoretiskt axiom: en klassisk axiom kan ha ett antal intuitionistiska varianter som visar sig vara icke-ekvivalenta med varandra. Detta återspeglas ibland av den teoretiska styrkan hos de resulterande teorierna, som kan variera beroende på vilka principer vi väljer. Till exempel har vi redan konstaterat att vi i CZF inte har fullständig separering och effektuppsättning, som ersätts av de predikativt godtagbara principerna för respektive begränsad separering och delmängd. Men om vi lägger till någon av dessa principer till CZF, får vi impredicative teorier. Impredikativiteten hos de resulterande teorierna bevittnas av det faktum att deras bevisteoretiska styrka långt överskrider CZF: s.

Det är inte förvånande att undersökningar om den bevisteoretiska styrkan hos konstruktiva och intutionistiska uppsatta teorier har varit ett avgörande metateoretiskt verktyg för att förstå dessa teorier och deras relationer med varandra. Undersökningar om en teoris bevisteoretiska styrka är rika och informativa. I synnerhet har Feferman (1993) hävdat att en bevisteoretisk analys kan hjälpa oss att fastställa om en viss teori överensstämmer med en viss filosofisk ram: till exempel kan analysen avslöja att en teori är predicativ eller finitistisk etc. biprodukt från bevisteoretisk analys får vi ibland enkla oberoende bevis. I själva verket kan vi visa att en teori inte kan bevisa en specifik princip eftersom att lägga till den till teorin skulle öka teorins bevisteoretiska styrka. Till exempel,CZF bevisar inte powerets axiom, eftersom tillägget av poweret till CZF ger upphov till en mycket starkare teori. Korrektoriska tolkningar har också använts för att jämföra konstruktiva och intuitionistiska ZF-uppsättningsteorier bland varandra, såväl som med deras klassiska motsvarigheter, och även med andra grundläggande system för konstruktiv matematik, såsom konstruktiv typteori och uttrycklig matematik (se t.ex. Griffor och Rathjen 1994, Tupailo 2003). För exempelvis en definition av begreppet bevisteoretisk styrka och för undersökningar av bevisteori (Rathjen 1999, 2006b).såväl som med deras klassiska motsvarigheter, och även med andra grundläggande system för konstruktiv matematik, såsom konstruktiv typteori och explicit matematik (se t.ex. Griffor och Rathjen 1994, Tupailo 2003). För exempelvis en definition av begreppet bevisteoretisk styrka och för undersökningar av bevisteori (Rathjen 1999, 2006b).såväl som med deras klassiska motsvarigheter, och även med andra grundläggande system för konstruktiv matematik, såsom konstruktiv typteori och explicit matematik (se t.ex. Griffor och Rathjen 1994, Tupailo 2003). För exempelvis en definition av begreppet bevisteoretisk styrka och för undersökningar av bevisteori (Rathjen 1999, 2006b).

Även om CZF och IZF är de mest studerade systemen har många andra system för konstruktiv och intuitionistisk uppsättningsteori beaktats i litteraturen hittills. Den bevisteoretiska styrkan hos ett antal konstruktiva och intuitionistiska uppsättningsteorier har fastställts av en mängd olika verktyg, som till exempel en utvidgning till uppsättningsteorin om tolkningen av dubbelnegation (härrör från (Friedman 1973a)) och en variation av andra bevisteoretiska tolkningar, ofta härrörande från en noggrann kombination av semantiska och bevisteoretiska tekniker. I många fall har bevisets teoretiska styrka bestämts av en kedja av tolkningar mellan konstruktiva och klassiska system, och genom att använda en mängd olika verktyg, från tillförlitlighet till mer "traditionella" bevisteoretiska tekniker, som ordinär analys (se,till exempel Beeson 1985; Griffor och Rathjen 1994; Rathjen 2012b). Framför allt har realiserbarheten visat sig vara mycket användbar på grund av dess flexibilitet. Beträffande resultaten av dessa undersökningar, visade sig några av de analyserade systemen vara så svaga som aritmetik, som till exempel Friedmans system B (Friedman 1977); andra system är lika starka som full klassisk ZF, som IZF (Friedman 1973a). Det finns också system med mellanstyrka, som CZF. Den senare teorins styrka är faktiskt lika med en teori om en induktiv definition som kallas ID (_ 1). Det faktum att CZF har samma styrka som ID (_ 1) tas för att bekräfta (generaliserad) predikativitet för setteorin, och för att bevisa att den överskrider predicativitetsgränsen med tanke på de naturliga siffrorna, eftersom ID (_ 1): s bevisteoretiska ordinal är långt över (Gamma_0). Beeson 1985; Griffor och Rathjen 1994; Rathjen 2012b). Framför allt har realiserbarheten visat sig vara mycket användbar på grund av dess flexibilitet. Beträffande resultaten av dessa undersökningar, visade sig några av de analyserade systemen vara så svaga som aritmetik, som till exempel Friedmans system B (Friedman 1977); andra system är lika starka som full klassisk ZF, som IZF (Friedman 1973a). Det finns också system med mellanstyrka, som CZF. Den senare teorins styrka är faktiskt lika med en teori om en induktiv definition som kallas ID (_ 1). Det faktum att CZF har samma styrka som ID (_ 1) tas för att bekräfta den (generaliserade) predikativiteten för uppsättningsteorin och för att bevisa att den överskrider gränsen för predikativitet med tanke på de naturliga siffrorna, eftersom ID (_ 1): s bevisteoretiska ordinal är långt över (Gamma_0). Beeson 1985; Griffor och Rathjen 1994; Rathjen 2012b). Framför allt har realiserbarheten visat sig vara mycket användbar på grund av dess flexibilitet. Beträffande resultaten av dessa undersökningar, visade sig några av de analyserade systemen vara så svaga som aritmetik, som till exempel Friedmans system B (Friedman 1977); andra system är lika starka som full klassisk ZF, som IZF (Friedman 1973a). Det finns också system med mellanstyrka, som CZF. Den senare teorins styrka är faktiskt lika med en teori om en induktiv definition som kallas ID (_ 1). Det faktum att CZF har samma styrka som ID (_ 1) tas för att bekräfta (generaliserad) predikativitet för setteorin, och för att bevisa att den överskrider predicativitetsgränsen med tanke på de naturliga siffrorna, eftersom ID (_ 1): s bevisteoretiska ordinal är långt över (Gamma_0). Rathjen 2012b). Framför allt har realiserbarheten visat sig vara mycket användbar på grund av dess flexibilitet. Beträffande resultaten av dessa undersökningar, visade sig några av de analyserade systemen vara så svaga som aritmetik, som till exempel Friedmans system B (Friedman 1977); andra system är lika starka som full klassisk ZF, som IZF (Friedman 1973a). Det finns också system med mellanstyrka, som CZF. Den senare teorins styrka är faktiskt lika med en teori om en induktiv definition som kallas ID (_ 1). Det faktum att CZF har samma styrka som ID (_ 1) tas för att bekräfta (generaliserad) predikativitet för setteorin, och för att bevisa att den överskrider predicativitetsgränsen med tanke på de naturliga siffrorna, eftersom ID (_ 1): s bevisteoretiska ordinal är långt över (Gamma_0). Rathjen 2012b). Framför allt har realiserbarheten visat sig vara mycket användbar på grund av dess flexibilitet. Beträffande resultaten av dessa undersökningar, visade sig några av de analyserade systemen vara så svaga som aritmetik, som till exempel Friedmans system B (Friedman 1977); andra system är lika starka som full klassisk ZF, som IZF (Friedman 1973a). Det finns också system med mellanstyrka, som CZF. Den senare teorins styrka är faktiskt lika med en teori om en induktiv definition som kallas ID (_ 1). Det faktum att CZF har samma styrka som ID (_ 1) tas för att bekräfta den (generaliserade) predikativiteten för uppsättningsteorin och för att bevisa att den överskrider gränsen för predikativitet med tanke på de naturliga siffrorna, eftersom ID (_ 1): s bevisteoretiska ordinal är långt över (Gamma_0).realiserbarheten har visat sig vara mycket användbar på grund av dess flexibilitet. Beträffande resultaten av dessa undersökningar, visade sig några av de analyserade systemen vara så svaga som aritmetik, som till exempel Friedmans system B (Friedman 1977); andra system är lika starka som full klassisk ZF, som IZF (Friedman 1973a). Det finns också system med mellanstyrka, som CZF. Den senare teorins styrka är faktiskt lika med en teori om en induktiv definition som kallas ID (_ 1). Det faktum att CZF har samma styrka som ID (_ 1) tas för att bekräfta den (generaliserade) predikativiteten för uppsättningsteorin och för att bevisa att den överskrider gränsen för predikativitet med tanke på de naturliga siffrorna, eftersom ID (_ 1): s bevisteoretiska ordinal är långt över (Gamma_0).realiserbarheten har visat sig vara mycket användbar på grund av dess flexibilitet. Beträffande resultaten av dessa undersökningar, visade sig några av de analyserade systemen vara så svaga som aritmetik, som till exempel Friedmans system B (Friedman 1977); andra system är lika starka som full klassisk ZF, som IZF (Friedman 1973a). Det finns också system med mellanstyrka, som CZF. Den senare teorins styrka är faktiskt lika med en teori om en induktiv definition som kallas ID (_ 1). Det faktum att CZF har samma styrka som ID (_ 1) tas för att bekräfta den (generaliserade) predikativiteten för uppsättningsteorin och för att bevisa att den överskrider gränsen för predikativitet med tanke på de naturliga siffrorna, eftersom ID (_ 1): s bevisteoretiska ordinal är långt över (Gamma_0).några av de analyserade systemen visar sig vara lika svaga som aritmetik, som till exempel Friedmans system B (Friedman 1977); andra system är lika starka som full klassisk ZF, som IZF (Friedman 1973a). Det finns också system med mellanstyrka, som CZF. Den senare teorins styrka är faktiskt lika med en teori om en induktiv definition som kallas ID (_ 1). Det faktum att CZF har samma styrka som ID (_ 1) tas för att bekräfta den (generaliserade) predikativiteten för uppsättningsteorin och för att bevisa att den överskrider gränsen för predikativitet med tanke på de naturliga siffrorna, eftersom ID (_ 1): s bevisteoretiska ordinal är långt över (Gamma_0).några av de analyserade systemen visar sig vara lika svaga som aritmetik, som till exempel Friedmans system B (Friedman 1977); andra system är lika starka som full klassisk ZF, som IZF (Friedman 1973a). Det finns också system med mellanstyrka, som CZF. Den senare teorins styrka är faktiskt lika med en teori om en induktiv definition som kallas ID (_ 1). Det faktum att CZF har samma styrka som ID (_ 1) tas för att bekräfta den (generaliserade) predikativiteten för uppsättningsteorin och för att bevisa att den överskrider gränsen för predikativitet med tanke på de naturliga siffrorna, eftersom ID (_ 1): s bevisteoretiska ordinal är långt över (Gamma_0). Det finns också system med mellanstyrka, som CZF. Den senare teorins styrka är faktiskt lika med en teori om en induktiv definition som kallas ID (_ 1). Det faktum att CZF har samma styrka som ID (_ 1) tas för att bekräfta den (generaliserade) predikativiteten för uppsättningsteorin och för att bevisa att den överskrider gränsen för predikativitet med tanke på de naturliga siffrorna, eftersom ID (_ 1): s bevisteoretiska ordinal är långt över (Gamma_0). Det finns också system med mellanstyrka, som CZF. Den senare teorins styrka är faktiskt lika med en teori om en induktiv definition som kallas ID (_ 1). Det faktum att CZF har samma styrka som ID (_ 1) tas för att bekräfta den (generaliserade) predikativiteten för uppsättningsteorin och för att bevisa att den överskrider gränsen för predikativitet med tanke på de naturliga siffrorna, eftersom ID (_ 1): s bevisteoretiska ordinal är långt över (Gamma_0).

Som en sista kommentar: medan styrkan hos CZF ligger långt under den andra ordningens aritmetik, ger det enkla tillskottet av uteslutet mitt till CZF oss (fullständig) ZF. Detta bör kontrasteras med IZF, som redan har styrkan hos ZF (Friedman 1973a). Den begränsade bevisteoretiska styrkan hos CZF jämfört med IZF har ofta betraktats som en av de viktigaste fördelarna med konstruktiv jämfört med intuitionistisk uppsättningsteori. På något sätt verkar det som om CZF utnyttjar sin intuitionistiska logik mest, eftersom den karaktäriserar en uppfattning om (generaliserad) predikativ uppsättning som är tillräckligt stark för att utveckla mycket av konstruktiv matematik men som också är tillräckligt svag för att undvika impredicativity. Intressant nog, när vissa stora setaxiomer har lagts till i konstruktiv setteori, har ett liknande mönster framkommit,eftersom styrkan hos den resulterande teorin ligger långt under den motsvarande klassiska teorin.

5.2 Stora uppsättningar i konstruktiv och intuitionistisk ZF

Ett framstående forskningsområde inom klassisk uppsättningsteori är stora kardinaler (se posten om uppsättningsteori). I konstruktiva sammanhang är ordningarna inte linjärt ordnade. (För begreppet konstruktiv ordinal och en kort diskussion om dess egenskaper, se det kompletterande dokumentet om: Set-teoretiska principer som är oförenliga med intuitionistisk logik.) Som en följd av detta spelar kardinalnummer inte samma roll som i den klassiska miljön.

Man kan ändå studera effekterna av "reflektionsprinciper" av formen av stora uppsatta axiomer. Till exempel kan man lägga till konstruktiva och intuitionistiska uppsättningsteorier en axiom som hävdar att det finns otillgängliga uppsättningar. [2] Tillägget av stora uppsatta axiomer till den intuitionistiska ZF föreslogs först av Friedman och Scedrov (Friedman och Scedrov 1984). Ett av deras mål var att belysa motsvarande klassiska uppfattningar; en annan var att studera påverkan av dessa principer på metatoretiska egenskaper hos de ursprungliga uppsättningsteorierna. Friedman och Scedrov har till exempel visat att tillsatsen av stora inställda axiomer inte äventyrar giltigheten för egenskaperna för disjunktion och numeriska existenser för IZF.

I samband med konstruktiv uppsättningsteori har stora uppsättningar införts av Aczel i form av så kallade vanliga uppsättningar för att möjliggöra induktiva definitioner av uppsättningar (Aczel 1986). Rathjen och Crosilla har betraktat otillgängliga uppsättningar (Rathjen al. 1998; Crosilla och Rathjen 2001) och Mahlo-uppsättningar (Rathjen 2003a). Ändå skulle en invändning kunna tas upp till förlängningar av konstruktiv uppsättningsteori med stora uppsatta axiomer. I klassisk uppsättningsteori kan stora kardinaler ses som en inkarnation av högre oändlighet. Hur motiverar vi dessa principer konstruktivt? Den konstruktiva motiveringen av dessa föreställningar förlitar sig återigen på den teoretiska tolkningen. Tillägget av dessa principer motsvarar faktiskt det för universum och (W) - typer inom konstruktiv typteori. Rättfärdigandet av förlängningar med stora uppsättningar är således bundet till frågan om gränserna för Martin-Löf typteori (Rathjen 2005). Vi noterar också att tillsatsen av oacceptabla uppsatta axiomer till ett svagt delsystem av CZF (utan set-induktion) ger en teori om styrka (Gamma_0), ordinalen som utpekats av Feferman och Schütte som gränsen för predikativitet givet det naturliga nummer (Crosilla och Rathjen 2001; se även avsnitt 1.3). Detta vittnar till det faktum att genom att arbeta i ett konstruktivt, predikativt sammanhang kan vi tämja traditionellt starka setteoretiska uppfattningar.ordinalen utpekade av Feferman och Schütte som gränsen för predikativitet med tanke på de naturliga siffrorna (Crosilla och Rathjen 2001; se även avsnitt 1.3). Detta vittnar till det faktum att genom att arbeta i ett konstruktivt, predikativt sammanhang kan vi tämja traditionellt starka setteoretiska uppfattningar.ordinalen utpekade av Feferman och Schütte som gränsen för predikativitet med tanke på de naturliga siffrorna (Crosilla och Rathjen 2001; se även avsnitt 1.3). Detta vittnar till det faktum att genom att arbeta i ett konstruktivt, predikativt sammanhang kan vi tämja traditionellt starka setteoretiska uppfattningar.

Crosilla och Rathjens uppsättningsteori med otillgängliga uppsättningar (men ingen uppsättning induktion) är beviset teoretiskt ganska svagt, men matematiskt ganska uttrycksfullt. Till exempel har den använts för att verifiera att tillägget av Voevodskys Univalence Axiom till Martin-Löf typteori inte skapar impregicativitet (Rathjen 2017). Axiom of Univalence introducerades av Voevodsky som en del av hans Univalent Foundations-program (Voevodsky 2015). (För Univalent Foundations, se poster om typteori och intuitionistisk typteori). Voevodsky gav en modell av konstruktiv typteori med Univalence Axiom som är baserad på Kan förenklade uppsättningar (se Kapulkin & Lumsdaine 2012, Andra internetresurser). Den förenklade modellen för konstruktiv typteori med univalens utvecklad i ovanstående artikel utförs inom en förlängning av ZFC med otillgängliga kardinaler. Detta ledde till frågan om man kunde ge en mer konstruktiv modell av denna typteori, och särskilt om typteorin är predikativ. Bezem, Coquand och Huber (2014) har nyligen föreslagit en modell av denna typteori i kubiska uppsättningar som är beräkningsmässiga och "kan uttryckas i en konstruktiv metallogik". Rathjen (2017) har verifierat att denna nya modell kan kodifieras i en lämplig förlängning av CZF med otillgängliga uppsättningar, vilket är mycket svagare än klassisk uppsättningsteori med otillgängliga kardinaler. I själva verket visar det sig att om vi tar utgångspunkt från en relativt svag typteori, dvs. en utan W-typer, och utvidgar den med Univalence Axiom,den resulterande teorin har bevisteoretisk styrka (Gamma_0), ordinalen som vanligtvis tas för att representera gränsen för predikativitet med tanke på de naturliga siffrorna (Rathjen 2017). För att visa detta bevisar man att den kubiska modellen av Bezem, Coquand och Huber kan genomföras i en förlängning av systemet som introducerades i Crosilla och Rathjen (2001) av (begränsat) Relativized Dependent Choice. Det följer av (Crosilla och Rathjen 2001) och (Rathjen 2003) att den senare har bevisteoretisk ordinal (Gamma_0). Coquand och Huber kan genomföras i en förlängning av systemet introducerat i Crosilla och Rathjen (2001) av (begränsat) Relativized Dependent Choice. Det följer av (Crosilla och Rathjen 2001) och (Rathjen 2003) att den senare har bevisteoretisk ordinal (Gamma_0). Coquand och Huber kan genomföras i en förlängning av systemet introducerat i Crosilla och Rathjen (2001) av (begränsat) Relativized Dependent Choice. Det följer av (Crosilla och Rathjen 2001) och (Rathjen 2003) att den senare har bevisteoretisk ordinal (Gamma_0).

5.3 Metamatematiska egenskaper hos konstruktiva och intuitionistiska ZF och semantiska tekniker

En mängd olika tolkningar för intuitionistisk logik har utvidgats till intuitionistiska och konstruktiva uppsatta teorier, såsom realiserbarhet, Kripke-modeller och Heyting-värderade semantik. Alla dessa tekniker har använts för att erhålla metamatematiska resultat om uppsättningsteorierna.

5.3.1 Konjunktions- och existensegenskaper hos konstruktiv och intuitionistisk ZF

Vissa intuitionistiska uppsatta teorier tillfredsställer vissa”kännetecken” metamatematiska egenskaper, såsom disjunktionen och existensegenskaperna. Det kan också visas att de överensstämmer med tillägget av principer som går utöver vad vi oftast anser vara konstruktiva. Bland dessa är till exempel kyrkans avhandling och Markovs princip. För en beskrivning av dessa principer i samband med den intuitionistiska logiken kan läsaren vilja se avsnitt 4.2 och 5.2 i posten om intuitionistisk logik eller Troelstra och van Dalens bok Konstruktivism i matematik (Troelstra och van Dalen 1988).

Här minns vi skillnads- och existensegenskaperna, formulerade för en uppsättningsteori (T). Den informella motivationen för disjunktionen och existensegenskaperna är baserad på vår förståelse av de konstruktiva bevisen på disjunktiva och existentiella uttalanden (respektive). I själva verket verkar det rimligt att förvänta sig att om vi konstruktivt bevisar en skillnad (phi / vee / psi), så borde vi också kunna bevisa (phi) eller bevisa (psi). På samma sätt, om vi bevisar ett existensiellt uttalande, borde vi kunna bevisa att ett vittne till det uttalandet är definierbart i vår teori.

Även om sådana egenskaper verkar ganska naturliga och är ganska lätta att fastställa för aritmetiska teorier, visar det sig att de utgör avsevärda tekniska utmaningar när det gäller uppsättningsteorier, på grund av deras transfinite hierarkier av uppsättningar och förlängningsaxiom. Faktum visar sig att framträdande konstruktiva och intuitionistiska uppsättningsteorier inte innehar existensegenskapen, som diskuteras i nästa avsnitt.

Låt (T) vara en teori vars språk, (L (T)), omfattar setteoriens språk. För enkelhets skull kommer vi dessutom att anta att (L (T)) har en konstant (omega) som anger uppsättningen av von Neumann naturliga siffror och för varje (n) en konstant (c_n) som anger det (n) - det elementet i (omega).

En teori (T) har skillnadsegenskapen (DP) om när (T) bevisar ((phi / vee / psi)) för meningar (phi) och (psi) av (L (T)), sedan (T) bevisar (phi) eller (T) bevisar (psi).

Den existens Fastigheten har två olika versioner i samband med inställda teori: den numeriska existens egenskapen (NEP) och förekomsten egenskapen (EP). Låt (theta (x)) vara en formel med högst (x) fri. Vi säger att:

(1) (T) har NEP om när (T) bevisar (existerar x / i / omega / theta (x)), då för något naturligt tal (n, T) bevisar (theta (c_n)).

(2) (T) har EP om när (T) bevisar (finns x / theta) (x), så finns det en formel (phi (x)) med exakt (x) gratis, så att (T) bevisar (finns! x (phi (x) kil / theta (x))).

Eftersom realiserbarhetstekniker har visat sig vara avgörande vid undersökningar om existens och skillnadsegenskaper för konstruktiva och intuitionistiska uppsatta teorier diskuterar vi resultaten av dessa studier i nästa avsnitt.

5.3.2 Realiserbarhet

Realiserbarhet har varit ett av de första och viktigaste verktygen i forskningen kring uppsättningsteorier baserade på intuitionistisk logik, utifrån de tidiga bidragen från Friedman och Myhill (Friedman 1973, Myhill 1973). Förverkligande semantik för intuitionistisk aritmetik föreslogs först av Kleene (Kleene 1945) och utvidgades till högre ordning Heyting aritmetik av Kreisel och Troelstra (Kreisel och Troelstra 1970). För definition av realiserbarhet för aritmetik, se avsnitt 5.2 i posten om intuitionistisk logik. En realiserbarhet liknande Kreisel och Troelstra tillämpades på system med högre ordning aritmetik av Friedman (Friedman 1973). Myhill introducerade en variant av denna realiserbarhet som liknar Kleens snedstreck (Myhill 1973; Kleene 1962, 1963). Han bevisade således att en version av IZF med ersättning istället för samlingen (kallad IZF (_ {Rep})) har DP, NEP och EP. Dessa resultat utvidgades ytterligare (Myhill 1975; Friedman och Scedrov 1983). Medan Friedman och Myhill gav realiseringsmodeller för extensional setteorier, utvecklade Beeson en uppfattning om realiserbarhet för icke-extensional set teorier. Han studerade sedan metateoretiska egenskaper för de extensional set teorier via en tolkning i deras icke-extensional motsvarigheter. Han bevisade således att IZF (med samling) har DP och NEP (Beeson 1985). Därefter introducerade McCarty realiserbarhet för IZF direkt för extensional setteori (McCarty 1984; 1986). Realisabilitetssemantik för varianter av CZF har till exempel beaktats i (Crosilla och Rathjen 2001; Rathjen 2006a). Realiserbarheten i den senare artikeln är inspirerad av McCartys och har den viktiga funktionen att det, som McCarty's för IZF, är en självvaliderande semantik för CZF (det vill säga denna uppfattning om realiserbarhet kan formaliseras i CZF och varje teori för CZF är förverkligas sannolikt i CZF). Rathjen har använt denna uppfattning om realiserbarhet för att visa att CZF (och ett antal förlängningar av det) har DP och NEP (Rathjen 2005b).

En annan typ av realiserbarhet som visat sig vara mycket användbar är Lifschitz-realiserbarhet. Lifschitz (1979) introducerade en modifiering av Kleens realiserbarhet för Heyting aritmetik som har det speciella att validera en svag form av Church's Thesis (CT) med ett unikt tillstånd, men inte CT själv. Lifschitz realiserbarhet utvidgades till andra ordens aritmetik av van Oosten (1990). Därefter utvidgades den till fullständig IZF av Cheng och Rathjen, som anställde den för att få ett antal självständighetsresultat, samt validera det så kallade Lesser Limited Principle of Omniscience (LLPO) (för LLPO se posten i konstruktiv matematik).

Frågan om vilka uppsättningsteorier som uppfyller existensegenskapen visade sig vara särskilt svår att lösa. (Friedman och Scedrov 1985) använde Kripke-modeller för att visa att IZF (det vill säga systemet med insamling) inte har EP, medan som nämnts ovan, systemet IZF (_ {Rep}) (som har ersättning på plats av samlingen) har EP. Detta fick Beeson att ställa frågan [Beeson 1985, IX]:

Har någon rimlig uppsättningsteori med samling existensegenskapen?

Ett första svar på Beesons fråga kom med (Rathjen 2012), där författaren introducerade uppfattningen om svag existensegenskap: fokuset här är att hitta en bevisbart definierbar uppsättning vittnen för varje existensiell teorem. Han introducerade sedan en form för realiserbarhet baserad på allmänna uppsatta rekursiva funktioner, där en realisator för ett existentiellt uttalande ger en uppsättning vittnen för den existentiella kvantifieraren, snarare än ett enda vittne. Rathjen kombinerade denna uppfattning om realiserbarhet med sanningen för att ge att ett antal teorier med samling åtnjuter den svaga existensegenskapen (medan IZF inte gör det). Bland dem, i synnerhet, teorin CZF utan delmängdsamling plus Myhills exponentiation axiom, CZF (_ {Exp}). I själva verket hävdade Rathjen att genom att kombinera dessa resultat med ytterligare arbete han hade utfört,han kunde visa att CZF (_ {Exp}) (och ett antal andra teorier) har existensegenskapen. En slående observation är att dessa teorier är formulerade med samling; följaktligen kan misslyckandet av existerande egendom i fallet med IZF inte endast hänföras till insamlingen utan till samspelet mellan detta schema och obegränsad separering.

När det gäller den framstående frågan om CZF själv har existensegenskapen, har detta lösts negativt av Swan (2014). Där använde författaren tre väl uttänkta realiserbarhetsmodeller och inbäddningar mellan dem för att visa att till och med den svaga existensegenskapen misslyckas för CZF. Därmed visade han också att CZF: s delmängdsamlingsschema är den skyldige. Som tydligt framhävdes i (Swan 2014), det faktum att CZF inte har EP, tyder inte på någon svaghet i CZF som en konstruktiv teori. Även om Swan väsentligen bevisade att CZF hävdar att det finns matematiska föremål som de inte vet hur de ska konstruera, har CZF fortfarande naturliga tolkningar där dessa objekt kan konstrueras, som till exempel Aczels tolkning till typteori (Aczel 1978).

För en undersökning av resultat i intuitionistisk uppsättningsteori, se (Beeson 1985, kapitel IX). För motsvarande utveckling inom CZF, se (Rathjen 2005b, 2006, 2012) och (Swan 2014).

5.3.3 Kripke-modeller och Heyting-värderad semantik

Kripke-modeller för intuitionistiska uppsättningsteorier har använts i (Friedman och Scedrov 1985) för att visa att IZF inte har EP (och att kombinera detta med resultaten i (Myhill 1973) har vi att IZF (_ {Rep}) gör bevisa inte IZF). Kripke-modeller har nyligen använts för att klargöra förhållandet mellan de konstruktiva ersättningarna för kraftuppsättningens axiom: Myhills exponentiation axiom och Aczels insamlingsschema för delmängder. Det är uppenbart att kraftmängdens axiom innebär båda dessa principer, och att delmängdsamlingen innebär exponentiering. Å andra sidan innebär inte vart och ett av de senare två principerna maktuppsättning, eftersom teorin CZF med maktuppsättning istället för delmängdssamling är mycket starkare än CZF och CZF (_ {Exp}) (Rathjen 2012b). I själva verket har CZF och CZF (_ {Exp}) samma bevisteoretiska styrka (Griffor och Rathjen 1994);därför att undersöka förhållandet mellan delmängdsamling och exponentiering i konstruktiv uppsättningsteori behövde man utveckla verktyg andra sedan bevisteoretiska metoder. Lubarsky (2005) använde Kripke-modeller för att visa att Myhills exponentiering axiom inte innebär Aczels undergruppssamling (på basis av CZF minus delmängdsamling plus full delning). I (Lubarsky och Rathjen 2007) använde författarna tekniken för Kripke-modeller för att visa att också konsekvenserna av teorierna CZF och CZF (_ {Exp}) är olika. Aczel och Rathjen (2001) hade visat att klassen Dedekind verkliga siffror bildar en uppsättning i CZF med hjälp av delmängdsamling. Lubarsky och Rathjen (2007) visade att CZF (_ {Exp}) inte räcker för att bevisa samma uttalande. För ytterligare tillämpningar av Kripke-modeller för att separera avgörande konstruktiva uppfattningar, se t.ex.(Diener och Lubarsky 2013).

Heyting-värderad semantik för intuitionistiska uppsättningsteorier erhölls av Grayson (Grayson 1979) som motsvarighet för booleska modeller för klassisk uppsättningsteori. De har generaliserats särskilt via kategorisk semantik (för en introduktion se MacLane och Moerdijk 1992). Heyting-värderad semantik har funnit tillämpning på oberoende resultat i (Scedrov 1981; 1982). En konstruktiv behandling har ges i (Gambino 2006). Se även (Lubarsky 2009). Se även Ziegler (2012) för en generalisering av realiserbarhet och Heyting-modeller för konstruktiv setteori.

5.3.4 Kategoriska modeller av konstruktiv och intuitionistisk uppsättningsteori

Kategoriska modeller av konstruktiva och intuitionistiska uppsättningsteorier har blivit blomstrande genom åren. Uppfattningarna om topos och sheaf spelar en viktig roll här (se t.ex. Fourman 1980 och Fourman och Scott 1980). För en översikt över huvudbegreppen, se posten om kategoriteori och referenser som finns där (se särskilt tillägget Programmatic Reading Guide). För nyare utvecklingar som mer specifikt hänför sig till konstruktiva uppsättningsteorier, se t.ex. (Simpson 2005) och (Awodey 2008), samt webbsidan: algebraisk uppsättningsteori.

5.4 Varianter av konstruktiva och intuitionistiska uppsättningsteorier: Uppsättningsteorier med urelement och icke-extensional uppsättningsteorier

Ibland har system för intuitionistisk och konstruktiv uppsättningsteori presenterats med de naturliga siffrorna som en separat sortering av urelement, det vill säga primitiva objekt utan element (Friedman 1977; Myhill 1975; Beeson 1985). Konstruktivt är detta ett naturligt val som överensstämmer med idéer som till exempel uttrycks av Bishop (1967) (bland andra). I Bishop's monografi tas de naturliga siffrorna som ett grundläggande begrepp som alla andra matematiska begrepp bygger på. Ur teknisk synvinkel, om de naturliga siffrorna tas som primitiva och skiljer sig från deras set-teoretiska framställningar, tar oändlighets axiom då formen: "det finns en uppsättning av naturliga tal (som urelement)". En mer generell form av urelement i konstruktiva uppsättningsteorier har beaktats i (Cantini och Crosilla 2008). Här föreslås en variant av konstruktiv uppsättningsteori som kombinerar en intensiv och partiell uppfattning om drift med CZFs utvidgade uppfattning om uppsättning (se även Cantini och Crosilla 2010).

Utvidgningens axiom är ett vanligt inslag i alla system som hittills diskuterats. Men i ett sammanhang där beräkningsinnehållet i ett uttalande anses vara avgörande, kan en intensivteori vara mer lämplig. Till exempel kapslar konstruktiv typteori och uttrycklig matematik båda av någon form av intensitet. Intuitionistiska uppsättningsteorier utan förlängning har beaktats i litteraturen (Friedman 1973a, Beeson 1985). Deras motivation har emellertid inte varit beräkningsmässigt utan teknisk till sin natur på grund av de svårigheter som extensivitet medför när man studerar metamatematiska egenskaper hos intuitionistiska uppsättningsteorier.

Bibliografi

  • Aczel, P., 1978, "The Type Theoretic Interpretation of Constructive Set Theory", i Logic Colloquium '77, A. MacIntyre, L. Pacholski, J. Paris (red.), Amsterdam och New York: North-Holland, pp. 55–66.
  • ––– 1982,”Typteoretisk tolkning av konstruktiv uppsättningsteori: valprinciper”, i LEJ Brouwer Centenary Symposium, AS Troelstra och D. van Dalen (red.), Amsterdam och New York: North-Holland, pp. 1-40.
  • ––– 1986,”Typteoretisk tolkning av konstruktiv uppsättningsteori: induktiva definitioner”, i logik, metodik och vetenskapsfilosofi VII, RB Marcus, GJ Dorn och GJW Dorn (red.), Amsterdam och New York: Nord-Holland, s. 17–49.
  • –––, 1988, Icke-välgrundade uppsättningar (CSLI Lecture Notes 14), Stanford: CSLI.
  • Aczel, P., och Rathjen, M., 2001, "Notes on Constructive Set Theory", rapport nr 40, 2000/2001, Djursholm: Institut Mittag-Leffler, [tillgängligt online]
  • Aczel, P. och Gambino, N., 2002, "Samlingsprinciper i beroende typteori", i typer för bevis och program (Lecture Notes in Computer Science 2277), P. Callaghan, Z. Luo, J. McKinna, och R. Pollack (red.), Berlin: Springer, s. 1–23.
  • Awodey, S., 2008, "En kort introduktion till algebraisk uppsättningsteori", Bulletin of Symbolic, 14 (3): 281–298.
  • Barwise, J., and Moss, L., 1996, Vicious Circles (CSLI Lecture Notes 60), Stanford: CSLI.
  • Beeson, M., 1985, Foundations of Constructive Mathematics, Berlin: Springer.
  • Bezem, M., Thierry, C. och Huber, S., 2014, "En modell av typteori i kubiska uppsättningar", i den 19: e internationella konferensen om typer för bevis och program (TYPES 2013), Matthes, R. och Schubert, A. (red.), Dagstuhl: Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, s. 107–128.
  • Bishop, E., 1967, Foundations of Constructive Analysis, New York: McGraw-Hill.
  • ––– 1970,”Matematik som ett numeriskt språk”, i Intuitionism and Proof Theory, A. Kino, J. Myhill och RE Vesley (eds.), Amsterdam: North-Holland, s. 53–71.
  • Bishop, E. och Bridges, D., 1985, Constructive Analysis, Berlin och Heidelberg: Springer.
  • Bridges, D., och Richman, F., 1987, Variants of Constructive Mathematics, Cambridge: Cambridge University Press.
  • Buchholz, W., Feferman, S., Pohlers, W. och Sieg, W., 1981, Iterated Inductive Definitions and Subsystems of Analysis, Berlin: Springer.
  • Cantini, A. och Crosilla, L., 2008, "Konstruktiv uppsättningsteori med operationer", i A. Andretta, K. Kearnes, D. Zambella (red.), Logic Colloquium 2004 (Lecture Notes in Logic 29), Cambridge: Cambridge University Press, s. 47–83.
  • Cantini, A. och Crosilla, L., 2010, "Explicit operation set set theory", i R. Schindler (red.), Ways of Proof Theory, Frankfurt: Ontos, s. 199–240.
  • Chen, R.-M. och Rathjen, M., 2012, “Lifschitz Realizability for Intuitionistic Zermelo-Fraenkel Set Theory”, Arkiv för matematisk logik, 51: 789–818.
  • Crosilla, L., 2017, “Predicativity and Feferman”, i G. Jäger och W. Sieg (red.), Feferman on Foundations (Outstanding Contributions to Logic: Volume 13), Cham: Springer, s. 423–447.
  • Crosilla, L. och Rathjen, M., 2001, "Otillgängliga uppsatta axiomer kan ha liten konsistensstyrka", Annals of Pure and Applied Logic, 115: 33–70.
  • Diaconescu, R., 1975, "Axiom of choice and complementation", Proceedings of the American Mathematical Society, 51: 176–178.
  • Diener, H. och Lubarsky, R., 2013, "Separera fanteoremet och dess svagningar", i SN Artemov och A. Nerode (red.), Proceedings of LFCS '13 (Lecture Notes in Computer Science 7734), Dordrecht: Springer, s. 280–295.
  • Dummett, M., 2000, Elements of Intuitionism, andra upplagan, (Oxford Logic Guides 39), New York: Oxford University Press.
  • Feferman, S., 1964, "Systems of predicative analysis", Journal of Symbolic Logic, 29: 1–30.
  • –––, 1975, "Ett språk och axiom för explicit matematik", i Algebra och logik (Lecture Notes in Mathematics 450), J. Crossley (red.), Berlin: Springer, s. 87–139.
  • ––– 1988, “Weyl motiverade: Das Kontinuum sjuttio år senare”, i Temi e prospettive della logica e della scienza contemporanee, C. Cellucci och G. Sambin (eds), s. 59–93.
  • –––, 1993,”Vad beror på vad? Den bevisteoretiska analysen av matematik”, i filosofin för matematik, del I, Proceedings of the 15th International Wittgenstein Symposium. Wien: Verlag Hölder-Pichler-Tempsky.
  • ––– 2005,”Predicativity”, i Handbook of the Philosophy of Mathematics and Logic, S. Shapiro (red.), Oxford: Oxford University Press.
  • Fletcher, P., 2007, "Infinity", i Handbook of the Philosophy of Logic, D. Jacquette, (red.), Amsterdam: Elsevier, s. 523–585.
  • Fourman, MP, 1980, “Sheaf models for set theory”, Journal of Pure Applied Algebra, 19: 91–101.
  • Fourman, MP och Scott, DS, 1980, "Sheaves and logic", i Applications of Sheaves (Lecture Notes in Mathematics 753), MP Fourman, CJ Mulvey och DS Scott (eds.), Berlin: Springer, s. 302– 401.
  • Friedman, H., 1973, "Vissa tillämpningar av Kleens metoder för intuitionistiska system", i Proceedings of the Cambridge Summer School in Mathematical Logic 1971 (Lecture Notes in Mathematics 337), ARD Mathias och H. Rogers (eds.), Berlin: Springer, s. 113–170.
  • –––, 1973a, “Konsistensen av klassisk uppsättningsteori relativt en uppsättningsteori med intuitionistisk logik”, Journal of Symbolic Logic, 38: 315–319.
  • ––– 1977,”Set-teoretiska grunder för konstruktiv analys”, Annals of Mathematics, 105: 1–28.
  • Friedman, H., Scedrov, A., 1983, "Ställ existensegenskap för intuitionistiska teorier med beroende val", Annals of Pure and Applied Logic, 25: 129–140.
  • ––– 1984,”Stora uppsättningar i intuitionistisk uppsättningsteori”, Annals of Pure and Applied Logic, 27: 1–24.
  • –––, 1985,”Bristen på definierbara vittnen och bevisligen rekursiva funktioner i intuitionistisk uppsättningsteori”, Advances in Mathematics, 57: 1–13.
  • Gambino, N., 2006, "Heyting-värderade tolkningar för konstruktiv setteori", Annals of Pure and Applied Logic, 137: 164–188.
  • Goodman, ND och Myhill, J., 1972, "Formaliseringen av Bishop's konstruktiva matematik", i Toposes, Algebraic Geometry and Logic (Lecture Notes in Mathematics 274), FW Lawvere (red.), Berlin: Springer, s. 83 -96.
  • Goodman, ND och Myhill, J., 1978, "Choice implicit excluded middle", Zeitschrift für mathematatische Logik und Grundlagen der Mathematik, 24 (5): 461.
  • Grayson, RJ, 1979, "Heyting-värderade modeller för intuitionistisk uppsättningsteori", i Applications of Sheaves (Lecture Notes in Mathematics 753), MP Fourman, CJ Mulvey och DS Scott (red.), Berlin: Springer, s. 402 -414.
  • Griffor, E. och Rathjen, M., 1994, "Styrken hos vissa teorier av Martin-Löf-typ", Archive Mathematical Logic, 33: 347–385.
  • van Heijenoort, J., 1967, Från Frege till Gödel. En källbok i matematisk logik 1879–1931, Cambridge: Harvard Univ. Tryck.
  • Kleene, SC, 1945, "Om tolkningen av intuitionistisk talteori", Journal of Symbolic Logic, 10: 109–124.
  • –––, 1962,”Disjunction och existens under implikation i elementära intuitionistiska formalismer”, Journal of Symbolic Logic, 27: 11–18.
  • ––– 1963,”Ett tillägg”, Journal of Symbolic Logic, 28: 154–156.
  • Kreisel, G., 1958, "Ordinal logik och karaktärisering av informella bevisbegrepp", Proceedings of the International Congress of Mathematicians (14–21 augusti 1958), Paris: Gauthier-Villars, s. 289–299.
  • Kreisel, G. och Troelstra, A., S., 1970, "Formella system för vissa grenar av intuitionistisk analys", Annals of Mathematical Logic, 1: 229–387.
  • Lifschitz, V., 1979, "CT (_ 0) är starkare än CT (_ 0)!", Proceedings of the American Mathematical Society, 73 (1): 101–106.
  • Lindström, I., 1989, "En konstruktion av icke-välgrundade uppsättningar inom typteorin Martin-Löf", Journal of Symbolic Logic, 54: 57–64.
  • Lipton, J., 1995, "Realizability, set theory and term extraction", i The Curry-Howard isomorphism (Cahiers du Centre de Logique de l'Universite Catholique de Louvain 8), Louvain-la-Neuve: Academia, s. 257 -364.
  • Lorenzen, P. och Myhill, J., 1959, "Konstruktiv definition av vissa analytiska siffror", Journal of Symbolic Logic, 24: 37–49.
  • Lubarsky, R., 2005, "Oberoende resultat kring konstruktiv ZF", Annals of Pure and Applied Logic, 132: 209–225.
  • –––, 2006, “CZF och andra ordningens aritmetik”, Annals of Pure and Applied Logic, 141: 29–34.
  • ––– 2009, “Topological Forcing Semantics with Settling”, i SN Artemov och A. Nerode (red.), Proceedings of LFCS '09 (Lecture Notes in Computer Science 5407), Dordrecht: Springer, s. 309–322.
  • Lubarsky, R., och Rathjen, M., 2007, “On the Constructive Dedekind Reals”, i SN Artemov och A. Nerode (red.), Proceedings of LFCS 2007 (Lecture Notes in Computer Science 4514), Dordrecht: Springer, s. 349–362.
  • MacLane, S. och Moerdijk, I., 1992, "Sheaves in Geometry and Logic", New York: Springer.
  • Maietti, ME, Sambin, G., 2005, "Mot en minimalistisk stiftelse för konstruktiv matematik", från uppsättningar och typer till topologi och analys: Mot praktiska grunder för konstruktiv matematik (Oxford Logic Guides 48), L. Crosilla och P Schuster (red.), Oxford: Oxford University Press.
  • Maietti, ME, 2009, "En minimalistisk grundnivå för konstruktiv matematik", Annals of Pure and Applied Logic, 160 (3): 319–354.
  • Martin-Löf, P., 1975, "En intuitionistisk teori om typer: predikativ del", i HE Rose och J. Sheperdson (red.), Logic Colloquium '73, Amsterdam: North-Holland, s. 73–118.
  • ––– 1984,”Intuitionistic Type Theory”, Neapel: Bibliopolis.
  • McCarty, DC, 1984, "Realisability and Recursive Mathematics", D. Phil. Avhandling, filosofi, Oxford University.
  • –––, 1986,”Realiserbarhet och rekursiv uppsättningsteori”, Annals of Pure and Applied Logic, 32: 153–183.
  • Myhill J. Berlin: Springer, s. 206–231.
  • ––– 1975, “Constructive set theory”, Journal of Symbolic Logic, 40: 347–382.
  • van Oosten, J., 1990, "Lifschitz's Realizability", Journal of Symbolic Logic, 55: 805–821.
  • Powell, W., 1975, "Utöka Gödels negativa tolkning till ZF", Journal of Symbolic Logic, 40: 221–229.
  • Rathjen, M., Griffor, E. och Palmgren, E., 1998, "Inaccessibility in constructive set theory and typ theory", Annals of Pure and Applied Logic, 94: 181–200.
  • Rathjen, M., 1999, "The realm of ordinal analysis", i Sets and Proofs (London Mathematical Society Lecture Notes 258), Cambridge: Cambridge University Press, s. 219–279.
  • –––, 2003,”Anti-foundation axiom in constructive set theories”, i spel, logik och konstruktiva uppsättningar (CSLI Lecture Notes 161), Stanford: CSLI Publication, s. 87–108.
  • –––, 2003a,”Realisering av Mahlo-uppsättningsteori i typteori”, Archive for Mathematical Logic, 42: 89–101.
  • ––– 2004,”Predicativity, circularity and anti-foundation”, i Hundra år av Russells paradox (Logic and its Applications 6), G. Link (red.), Berlin: de Gruyter, s. 191–219.
  • ––– 2005,”Ersättning kontra samling och relaterade ämnen i konstruktiv Zermelo-Fraenkel-setteori”, Annals of Pure and Applied Logic, 136: 156–174.
  • ––– 2005a,”Det konstruktiva Hilbert-programmet och gränserna för Martin-Löf typteori”, Synthese, 147: 81–120.
  • –––, 2005b,”Sambandet och relaterade egenskaper för konstruktiv Zermelo-Fraenkel-setteori”, Journal of Symbolic Logic, 70 (4): 1232–1254.
  • –––, 2006, "Choice principer i konstruktiva och klassiska uppsättningsteorier", Logic Colloquium '02 (Lecture Notes in Logic 27), Z. Chatzidakis, P. Koepke och W. Pohlers (red.), Wellesley, Massachusetts: AK Peters, 299–326.
  • –––, 2006a, "Realiserbarhet för konstruktiv Zermelo-Fraenkel-setteori", i Logic Colloquium '03 (Lecture Notes in Logic 24), V. Stoltenberg-Hansen och J. Väänänen (red.), Wellesley, Massachusets: AK Peters, s. 282–314.
  • –––, 2006b,”Teorier och förordningar i bevisteori”, Synthese, 148 (3): 719–743.
  • ––– 2008,”De naturliga siffrorna i konstruktiv uppsättningsteori”, Matematisk logik kvartalsvis, 54: 287–312.
  • ––– 2012, “Från den svaga till den starka existensegenskapen”, Annals of Pure and Applied Logic, 163: 1400–1418.
  • ––– 2012b, “Konstruktiv Zermelo-Fraenkel-setteori, maktuppsättning och konstruktionsberäkningen”, i Epistemology versus Ontology: Essays on the Philosophy and Foundations of Matematics in Honour of Per Martin-Löf, (Logic, Epistemology and Unity of Science Series), P. Dybjer, S. Lindström, E. Palmgren och G. Sundhölm (red.), New York och Dordrecht: Springer Verlag.
  • –––, 2017, “Proof Theory of Constructive Systems: Inductive Types and Univalence”, i G. Jäger, och W. Sieg (red.), Feferman on Foundations (Outstanding Contributions to Logic: Volume 13), Cham: Springer, s. 385–419.
  • Richman, F., 2000, "Det grundläggande teoremet för algebra: en konstruktiv utveckling utan val", Pacific Journal of Mathematics, 196: 213–230.
  • ––– 2001,”Konstruktiv matematik utan val”, i Reuniting the Antipodes: Constructive and Nonstandard Views of Continuum (Synthese Library 306), P. Schuster, et al. (red.), Dordrecth: Kluwer, s. 199–205.
  • Russell, B., 1908, "Matematisk logik baserad på teorin om typer", American Journal of Mathematics, 30: 222–262. Omtryckt i van Heijenoort (1967), 150–182.
  • Scedrov, A., 1981, "Konsistens och oberoende resulterar i intuitionistisk uppsättningsteori" i konstruktiv matematik (Lecture Notes in Mathematics 873), F. Richman (red.), Berlin: Springer, s. 54–86.
  • ––– 1982,”Fan fanorismens oberoende i närvaro av kontinuitetsprinciper” i LEJ Brouwer Centenary Symposium, AS Troelstra och D. van Dalen (red.), Amsterdam: North-Holland, s. 435–442.
  • –––, 1985,”Intuitionistisk uppsättningsteori” i Harvey Friedmans forskning om matematikens grunder, LA Garrubgtib et al. (red.), Amsterdam: Elsevier.
  • Schütte, K., 1965, "Predicative well-ordering", i formella system och rekursiva funktioner, J. Crossley och M. Dummett (red.), Amsterdam: North-Holland, s. 279–302.
  • –––, 1965a, “Eine Grenze für die Beweisbarkeit der Transfiniten Induktion in der verzweigten Typenlogik”, Archiv für mathematatische Logik und Grundlagenforschung, 7: 45–60.
  • Simpson, A., 2005, "Konstruktiva uppsättningsteorier och deras kategoriteoretiska modeller", från uppsättningar och typer till topologi och analys: mot praktiska grunder för konstruktiv matematik (Oxford Logic Guides 48), L. Crosilla och P. Schuster (red.), Oxford: Oxford University Press.
  • Swan, AW, 2014, “CZF har inte existensegenskapen”, Annals of Pure and Applied Logic, 165: 1115–1147.
  • Troelstra, AS och van Dalen, D., 1988, Constructivism in Mathematics (två volymer), Amsterdam: North Holland.
  • Tupailo, S., 2003, "Förverkligande av konstruktiv uppsättningsteori i explicit matematik: en nedre gräns för imponerande Mahlo-universum", Annals of Pure and Applied Logic, 120: 165–196.
  • Voevodsky, V., 2015, “Ett experimentellt bibliotek med formaliserad matematik baserad på univalenta grunder”, Mathematical Structures in Computer Science, 25: 1278–1294.
  • Weyl, H., 1918, “Das Kontinuum. Kritische Untersuchungen über die Grundlagen der Analysis”, Veit, Leipzig.
  • Ziegler, Albert, 2012, "Generalisering av realiserbarhet och Heyting-modeller för konstruktiv uppsättningsteori", Annals of Pure and Applied Logic, 163 (2): 175–184.
  • ––– 2014,”En kumulativ hierarki av uppsättningar för konstruktiv uppsättningsteori”, Matematisk logik kvartalsvis, 60 (1-2): 21–30.

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

  • Aczel, P. och M. Rathjen, 2010, Notes on Constructive Set Theory, bokutkast, tillgängligt online.
  • Kapulkin, C. och PL Lumsdaine, 2012,”Den enkla modellen för univalenta stiftelser (efter Voevodsky)”, förtryck på arXiv.org.
  • Algebraisk uppsättningsteori, av S. Awodey (Carnegie Mellon).

[Vänligen kontakta författaren för ytterligare förslag.]

Rekommenderas: