Verzamelingenleer: Constructieve En Intuïtionistische ZF

2023 Auteur: Noah Black | [email protected]. Laatst gewijzigd: 2023-05-24 11:17

Toegang navigatie

• Inhoud van het item
• Bibliografie
• Academische hulpmiddelen
• Vrienden PDF-voorbeeld
• Info over auteur en citaat
• Terug naar boven

Verzamelingenleer: constructieve en intuïtionistische ZF

Voor het eerst gepubliceerd op 20 februari 2009; inhoudelijke herziening wo 13 feb.2019

Constructieve en intuïtionistische set-theorieën van Zermelo-Fraenkel zijn axiomatische theorieën van sets in de stijl van de set-theorie van Zermelo-Fraenkel (ZF) die gebaseerd zijn op intuïtionistische logica. Ze werden geïntroduceerd in de jaren '70 en ze vertegenwoordigen een formele context waarin wiskunde kan worden gecodificeerd op basis van intuïtionistische logica (zie de vermelding over constructieve wiskunde). Ze zijn geformuleerd op de standaard eerste-orde taal van de Zermelo-Fraenkel verzamelingenleer en maken geen direct gebruik van inherent constructieve ideeën. Bij het werken in constructieve en intuïtionistische ZF kunnen we dus tot op zekere hoogte vertrouwen op onze bekendheid met ZF en zijn heuristieken.

Niettegenstaande de overeenkomsten met de klassieke verzamelingenleer, verschillen de concepten van verzameling gedefinieerd door constructieve en intuïtionistische verzamelingenleer theorieën aanzienlijk van die van de klassieke traditie; ze verschillen ook van elkaar. De technieken die worden gebruikt om erin te werken en om metamathematische resultaten erover te verkrijgen, wijken in sommige opzichten ook af van de klassieke traditie vanwege hun toewijding aan intuïtionistische logica. Zoals gebruikelijk is in intuïtionistische omgevingen, is er in feite een overvloed aan semantische en proof-theoretische methoden beschikbaar voor de studie van constructieve en intuïtionistische verzamelingenleer.

Dit artikel introduceert de belangrijkste kenmerken van constructieve en intuïtionistische verzamelingenleer. Aangezien het veld zich in een snel tempo uitbreidt, kunnen we ons slechts enkele belangrijke aspecten van resultaten en beschikbare technieken kort herinneren. We richten ons meer op de constructieve verzamelingenleer om belangrijke fundamentele problemen die zich daarin voordoen te belichten. Merk op dat we een opvallend deel van de literatuur over constructieve en intuïtionistische ZF weglaten, dat betrekking heeft op hun categorische interpretaties. Dit gebied heeft in de loop der jaren grote ontwikkelingen doorgemaakt, zozeer zelfs dat een adequate behandeling van die vooruitgang een substantiële uitbreiding van deze vermelding zou vereisen. De geïnteresseerde lezer zou het item over categorietheorie en de referenties ervan kunnen raadplegen (zie ook de bijlage Programmatic Reading Guide).

• 1. De essentie van constructieve en intuïtionistische verzamelingenleer

  • 1.1 Axiomatische vrijheid
  • 1.2 Constructieve versus intuïtionistische verzamelingenleer

  • 1.3 Predicativiteit in de constructieve verzamelingenleer

    • 1.3.1 Impredicativiteit van scheiding
    • 1.3.2 Impredicativiteit van Powerset
    • 1.3.3 Het constructieve universum van sets
• 2. Oorsprong van constructieve en intuïtionistische verzamelingenleer
• 3. De Axioms Systems CZF en IZF
• 4. Constructieve keuze principes

• 5. Bewijstheorie en semantiek van constructieve en intuïtionistische ZF

  • 5.1 Bewijs-theoretische kracht
  • 5.2 Grote sets in constructieve en intuïtionistische ZF

  • 5.3 Metamathematische eigenschappen van constructieve en intuïtionistische ZF- en semantische technieken

    • 5.3.1 Disjunctie en existentie-eigenschappen van constructieve en intuïtionistische ZF
    • 5.3.2 Realiseerbaarheid
    • 5.3.3 Kripke-modellen en Heyting-gewaardeerde semantiek
    • 5.3.4 Categorische modellen van constructieve en intuïtionistische verzamelingenleer
    • 5.4 Varianten van constructieve en intuïtionistische set-theorieën: set-theorieën met Urelements en niet-extensieve set-theorieën
• Bibliografie
• Academische hulpmiddelen
• Andere internetbronnen
• Gerelateerde vermeldingen

1. De essentie van constructieve en intuïtionistische verzamelingenleer

Constructieve en intuïtionistische Zermelo-Fraenkel-verzamelingen zijn gebaseerd op intuïtionistische in plaats van klassieke logica en vertegenwoordigen een natuurlijke omgeving waarin wiskunde kan worden gecodificeerd en bestudeerd op basis van intuïtionistische logica. Voor constructieve ZF was de belangrijkste focus het vertegenwoordigen van de wiskundige praktijk van Bishop (Bishop 1967, Bishop and Bridges 1985).

Voor de basisconcepten en de stuwende ideeën van intuïtionistische logica, constructieve wiskunde en intuïtionisme, wil de lezer misschien de volgende vermeldingen raadplegen:

• intuïtionistische logica,
• de ontwikkeling van intuïtionistische logica,
• constructieve wiskunde,
• intuïtionisme in de filosofie van de wiskunde,
• Luitzen Egbertus Jan Brouwer.

Voor klassieke verzamelingenleer, zie de vermelding over verzamelingenleer.

Constructieve en intuïtionistische ZF zijn gebaseerd op dezelfde eerste-orde taal als de klassieke ZF-verzamelingenleer, die alleen het binaire predikaatsymbool (in) (lidmaatschap) heeft als niet-logisch symbool. Dat wil zeggen, ze zijn geformuleerd op basis van intuïtionistische eerste-orde logica met gelijkheid, plus het binaire predikaatsymbool (in). We kunnen dus profiteren van de eenvoud van de set-theoretische taal en van onze bekendheid ermee (Myhill 1975). Net als bij constructieve wiskunde in bisschopstijl, zijn constructieve en intuïtionistische ZF compatibel met de klassieke traditie, in de zin dat al hun stellingen klassiek waar zijn. In feite zijn de twee formele systemen die we zullen overwegen, Constructive Zermelo-Fraenkel (CZF) en Intuitionistic Zermelo-Fraenkel (IZF),geven volledige klassieke ZF door de simpele toevoeging van het principe van het uitgesloten midden.

1.1 Axiomatische vrijheid

Klassieke Zermelo-Fraenkel verzamelingenleer is gebaseerd op klassieke eerste-orde predikaatlogica met gelijkheid. Bovenop de logische principes staan axioma's en schema's die het begrip set beschrijven dat de theorie codificeert. Deze principes kunnen in drie soorten worden ingedeeld. Ten eerste zijn er principes die ons in staat stellen om van bepaalde sets nieuwe sets te vormen. Het axioma van het paar stelt ons bijvoorbeeld in staat om een set te vormen die het paar van twee gegeven sets is. Ten tweede zijn er principes die eigenschappen vastleggen van de verzamelingenleer. Het axioma van extensie duidt bijvoorbeeld alle sets aan met dezelfde elementen. Ten derde, en tot slot, zijn er axioma's die het bestaan van specifieke verzamelingen bevestigen. Het axioma van oneindigheid stelt dus dat er een oneindige verzameling is. Deze principes worden allemaal samen de set-theoretische principes genoemd.

Bij het introduceren van versies van ZF op basis van intuïtionistische logica, is de eerste stap het elimineren van het principe van het uitgesloten midden (EM) uit de logica. De volgende stap is het kiezen van een goede verzameling set-theoretische principes die getrouw het gewenste begrip van constructieve set vertegenwoordigen. Deze taken blijken uitdagender dan men in eerste instantie had verwacht. In feite, zoals bekend, hebben systemen die gebaseerd zijn op een "zwakkere" logica de mogelijkheid om onderscheid te maken tussen uitspraken die equivalent zijn vanuit het oogpunt van een "sterkere" logica. In het geval van verzamelingenleer worden sommige van de ZF-axioma's of schema's vaak gepresenteerd door een van de vele klassiek equivalente formuleringen. Klassiek is het slechts een kwestie van gemak welke je op een bepaald tijdstip moet gebruiken. Bij het werken op basis van intuïtionistische logica,verschillende formuleringen van een klassiek axioma kunnen verschillend (niet-equivalent) blijken te zijn. In feite kan men zich nieuwe uitspraken voorstellen die klassiek equivalent zijn aan een ZF-axioma, maar intuïtionistisch daarvan gescheiden zijn (bijvoorbeeld CZF's verzameling axioma's van de subset (Aczel 1978)).

Wat betreft de eerste stap, namelijk het elimineren van het principe van uitgesloten midden uit de logica, blijkt dat het simpelweg uit de onderliggende logica verwijderen van dit principe niet voldoende is; dat wil zeggen, het is niet voldoende om de intuïtionistische in plaats van de klassieke predikaatrekening als basis te nemen. We moeten er ook voor zorgen dat de verzamelde theoretische axioma's geen ongewenste vormen van uitgesloten midden in onze theorie terugbrengen. Zoals bijvoorbeeld door Myhill (1973) opgemerkt, hebben we extra zorg nodig bij het kiezen van een geschikte verklaring voor het axioma van fundering. Foundation wordt geïntroduceerd in de verzamelingenleer om sets uit te sluiten die lid zijn van zichzelf en dus (in) - ketens van sets. De gebruikelijke formulering van de stichting stelt dat elke bewoonde set (een set met ten minste één element) ten minste een element heeft met betrekking tot de lidmaatschapsrelatie. Deze verklaringAangetoond kan worden dat het constructief onaanvaardbare gevallen van uitgesloten midden oplevert op basis van bescheiden set-theoretische veronderstellingen. Daarom moet de gebruikelijke formulering van de basis worden weggelaten uit een verzamelingenleer gebaseerd op intuïtionistische logica. Zie voor een bewijs het aanvullende document:

Set-theoretische principes onverenigbaar met intuïtionistische logica.

De typische zet bij het formuleren van verzamelingen theorieën gebaseerd op intuïtionistische logica is dan om de fundering te vervangen door het klassiek equivalente schema van verzameling-inductie, dat niet dezelfde "bijwerkingen" heeft, maar vergelijkbare gevolgen heeft. ^[1]

Wat de tweede stap betreft, die verband houdt met de selectie van een goede voorraad set-theoretische principes, hebben de schema's van vervanging en scheiding en het axioma van de vermogensverzameling de meeste aandacht getrokken. Zie het aanvullende document voor de exacte formulering van deze principes:

Axioma's van CZF en IZF.

Hier is het volgende een typisch scenario. Gezien wat klassiek twee varianten zijn van een enkel verzameltheoretisch principe, vereist hun klassieke bewijs van gelijkwaardigheid op een bepaald moment een instantie van het uitgesloten midden. In het algemeen zal dit bewijs van gelijkwaardigheid echter niet doorwerken in een intuïtionistische context, en dus wat klassiek twee vormen van één principe zijn, kunnen bij intuïtionistisch werken resulteren in twee verschillende principes. Het kiezen van de ene in plaats van de andere kan daarom van invloed zijn op het begrip set dat we zo definiëren. In de context van constructieve set-theorieën zoals CZF worden power set en separatie vervangen door intuïtionistisch zwakkere principes. Een reden hiervoor is dat de volledige kracht van het ingestelde vermogen en volledige scheiding als onnodig worden beschouwd,aangezien hun zwakkere vervangers voldoende lijken te zijn voor het uitvoeren van constructieve wiskunde. Een andere reden is dat ze als filosofisch problematisch worden gezien, omdat ze vormen van impredicativiteit binnen de verzamelingenleer kunnen introduceren (zie de paragraaf over Predicativiteit in de constructieve verzamelingenleer). Het geval van vervanging versus inzameling is op de een of andere manier complexer (zie bijvoorbeeld de artikelen (Friedman en Scedrov 1985), (Rathjen 2005) en (Rathjen 2012)). Het is de moeite waard om te benadrukken dat, hoewel het aannemen van de gebruikelijke formulering van de grondslag in strijd is met de veronderstelling van intuïtionistische logica als achtergrondlogica, de principes van scheiding en machtsset helemaal niet onverenigbaar zijn met intuïtionistische logica, zozeer zelfs dat ze integraal deel uitmaken van de intuïtionistische theorie van verzamelingen IZF (Friedman 1973a). Een andere reden is dat ze als filosofisch problematisch worden gezien, omdat ze vormen van impredicativiteit binnen de verzamelingenleer kunnen introduceren (zie de paragraaf over Predicativiteit in de constructieve verzamelingenleer). Het geval van vervanging versus inzameling is op de een of andere manier complexer (zie bijvoorbeeld de artikelen (Friedman en Scedrov 1985), (Rathjen 2005) en (Rathjen 2012)). Het is de moeite waard om te benadrukken dat, hoewel het aannemen van de gebruikelijke formulering van de grondslag in strijd is met de veronderstelling van intuïtionistische logica als achtergrondlogica, de principes van scheiding en machtsset helemaal niet onverenigbaar zijn met intuïtionistische logica, zozeer zelfs dat ze integraal deel uitmaken van de intuïtionistische theorie van verzamelingen IZF (Friedman 1973a). Een andere reden is dat ze als filosofisch problematisch worden gezien, omdat ze vormen van impredicativiteit binnen de verzamelingenleer kunnen introduceren (zie de paragraaf over Predicativiteit in de constructieve verzamelingenleer). Het geval van vervanging versus inzameling is op de een of andere manier complexer (zie bijvoorbeeld de artikelen (Friedman en Scedrov 1985), (Rathjen 2005) en (Rathjen 2012)). Het is de moeite waard om te benadrukken dat, hoewel de gebruikelijke formulering van de basis wordt aangenomen, dit in strijd is met de aanname van intuïtionistische logica als achtergrondlogica, maar de principes van scheiding en machtsset helemaal niet onverenigbaar zijn met intuïtionistische logica, zozeer zelfs dat ze integraal deel uitmaken van de intuïtionistische theorie van verzamelingen IZF (Friedman 1973a).aangezien ze vormen van impredicativiteit binnen de verzamelingenleer kunnen introduceren (zie de paragraaf over Predicativiteit in de constructieve verzamelingenleer). Het geval van vervanging versus inzameling is op de een of andere manier complexer (zie bijvoorbeeld de artikelen (Friedman en Scedrov 1985), (Rathjen 2005) en (Rathjen 2012)). Het is de moeite waard om te benadrukken dat, hoewel het aannemen van de gebruikelijke formulering van de grondslag in strijd is met de veronderstelling van intuïtionistische logica als achtergrondlogica, de principes van scheiding en machtsset helemaal niet onverenigbaar zijn met intuïtionistische logica, zozeer zelfs dat ze integraal deel uitmaken van de intuïtionistische theorie van verzamelingen IZF (Friedman 1973a).aangezien ze vormen van impredicativiteit binnen de verzamelingenleer kunnen introduceren (zie de paragraaf over Predicativiteit in de constructieve verzamelingenleer). Het geval van vervanging versus inzameling is op de een of andere manier complexer (zie bijvoorbeeld de artikelen (Friedman en Scedrov 1985), (Rathjen 2005) en (Rathjen 2012)). Het is de moeite waard om te benadrukken dat, hoewel het aannemen van de gebruikelijke formulering van de grondslag in strijd is met de veronderstelling van intuïtionistische logica als achtergrondlogica, de principes van scheiding en machtsset helemaal niet onverenigbaar zijn met intuïtionistische logica, zozeer zelfs dat ze integraal deel uitmaken van de intuïtionistische theorie van verzamelingen IZF (Friedman 1973a). Het is de moeite waard om te benadrukken dat, hoewel het aannemen van de gebruikelijke formulering van de grondslag in strijd is met de veronderstelling van intuïtionistische logica als achtergrondlogica, de principes van scheiding en machtsset helemaal niet onverenigbaar zijn met intuïtionistische logica, zozeer zelfs dat ze integraal deel uitmaken van de intuïtionistische theorie van verzamelingen IZF (Friedman 1973a). Het is de moeite waard om te benadrukken dat, hoewel het aannemen van de gebruikelijke formulering van de grondslag in strijd is met de veronderstelling van intuïtionistische logica als achtergrondlogica, de principes van scheiding en machtsset helemaal niet onverenigbaar zijn met intuïtionistische logica, zozeer zelfs dat ze integraal deel uitmaken van de intuïtionistische theorie van verzamelingen IZF (Friedman 1973a).

Samenvattend, bij het formuleren van een verzamelingenleer gebaseerd op intuïtionistische logica, is de eerste taak het principe van uitgesloten midden te verdrijven, inclusief de gevallen ervan die verborgen zouden kunnen zijn in bekende formuleringen van verzamelingen-theoretische axioma's. De volgende taak is om één versie van elk klassiek principe te kiezen die het beste het idee van set kenmerkt. Dit opent een reeks keuzes die men kan maken, aangezien meerdere intuïtionistische principes kunnen corresponderen met één klassiek principe. Benadrukt moet worden dat vanuit een constructief oogpunt deze veelheid aan opties (en dus systemen), in plaats van onrust te veroorzaken, een zeer wenselijke situatie is, aangezien het een vorm van "axiomatische vrijheid" vormt. Het stelt ons bijvoorbeeld in staat om onderscheid te maken tussen een aantal wiskundige begrippen, waardoor onze intuïties ervan beter als afzonderlijk kunnen worden vastgelegd. Het geeft ons ook de vrijheid om de begrippen en theorieën te kiezen die het beste passen bij een bepaalde context. Bovendien kunnen we door intuïtionistische logica aan te nemen, in onze theorieën principes opnemen die klassiek zeer sterk zijn, zonder dat we ons hoeven vast te leggen op hun klassieke kracht. Men kan bijvoorbeeld een idee van ontoegankelijke verzameling toevoegen aan een zwakke constructieve verzamelingenleer en een predikatieve theorie verkrijgen, terwijl hetzelfde begrip ingebed in een klassieke context extreem sterk wordt (zie de secties over Predicativiteit in constructieve verzamelingenleer en Grote verzamelingen in constructieve en intuïtionistische ZF). Tenslotte ontstaat natuurlijk een rijk gebied van (meta-theoretische) studie van de relaties tussen de resulterende onderscheiden set-theoretische systemen. Zoals je zou verwachten, heeft deze vrijheid ook een prijs,aangezien een zeer technische studie van de axiomatische theorieën nodig zou kunnen zijn om hun principes te onderscheiden en om enkele van hun subtiliteiten te onthullen. Dit kan weer als een voordeel worden beschouwd, omdat het ons dwingt tot een diepere en duidelijkere analyse van de wiskundige begrippen die erbij betrokken zijn en ons ertoe aanzet nieuwe geavanceerde tools te ontwikkelen.

1.2 Constructieve versus intuïtionistische verzamelingenleer

Hoewel er veel systemen zijn die zijn gebaseerd op intuïtionistische logica, kunnen we twee hoofdtrends binnen de literatuur onderscheiden. Volgens de eerste nemen we alles wat beschikbaar is in de klassieke ZF-verzamelingenleer en wijzigen we alleen die principes, zoals foundation, die een duidelijke onverenigbaarheid hebben met intuïtionistische logica. Dit leidt tot theorieën zoals Intuitionistic Zermelo-Fraenkel, IZF, waarvan een variant al in (Friedman 1973a) werd geïntroduceerd. (Zie Beeson 1985, hoofdstukken 8 en 9 en Scedrov 1985 voor twee onderzoeken over IZF.) De grondgedachte achter deze theorieën lijkt te zijn dat de wiskundige de krachtigste tools wordt gegeven die mogelijk zijn, zolang de compatibiliteit met intuïtionistische logica behouden blijft. Volgens de tweede benadering,naast de aanhankelijkheid aan intuïtionistische logica introduceren we ook beperkingen op de toegelaten set-theoretische principes, voor zover het resulterende systeem voldoet aan de constructieve wiskundige praktijk. Theorieën van deze tweede soort kunnen dus worden gezien als het resultaat van een dubbel beperkingsproces ten opzichte van klassieke ZF. Eerst is er een beperking tot de intuïtionistische logica, daarna wordt er een beperking opgelegd aan de toegestane set-theoretische constructies. Dit laatste is ingegeven door (1) de waarneming dat zwakkere principes lijken te volstaan voor de constructieve wiskundige praktijk en (2) de wens om vast te houden aan een vorm van predicativiteit (zie het volgende deel voor een verduidelijking van dit begrip predicativiteit). Paradigmatische voorbeelden van de laatste soort systemen zijn Myhill's Constructive Set Theory (Myhill 1975),Friedmans systeem B (Friedman 1977) en Aczel's Constructive Zermelo-Fraenkel verzamelingenleer CZF (Aczel 1978; 1982; 1986, Aczel & Rathjen 2001; Aczel & Rathjen 2010, Other Internet Resources). We kunnen ook zeggen dat in deze tweede benadering de fundamentele motivatie de praktijk in grotere mate beïnvloedt.

In het volgende maken we gebruik van een conventie die tegenwoordig vaak van kracht is, volgens welke het adjectief 'intuïtionistisch' verwijst naar die verzamelingen theorieën, zoals IZF, die impredicatief zijn, terwijl 'constructief' verwijst naar verzamelingen theorieën, zoals CZF, die voldoen aan een vorm van predicativiteit. Merk echter op dat deze conventie niet altijd wordt gevolgd in de literatuur. In feite is het bijvoeglijk naamwoord 'constructief' ook gebruikt om indenticatieve theorieën aan te duiden, en 'intuïtionistisch' om te verwijzen naar predicatieve basistheorieën zoals de Martin-Löf-typetheorie (Martin-Löf 1975; 1984). Het is ook vermeldenswaard dat de huidige conventie over het gebruik van de woorden "constructief" en "intuïtionistisch" verschilt van die gemaakt in de context van constructieve wiskunde (zie bijvoorbeeld de vermelding over constructieve wiskunde en ook Bridges en Richman 1987).

1.3 Predicativiteit in de constructieve verzamelingenleer

Het predicativisme vindt zijn oorsprong in de geschriften van Poincaré en Russell, die reageerden op de paradoxen die in de vroege theorieën van Cantor en Frege aan het begin van de 20e eeuw werden ontdekt. Vervolgens leverde Weyl fundamentele bijdragen aan de studie van predicatieve wiskunde (Weyl 1918, zie ook Feferman 1988). Volgens één idee is een definitie dwingend als ze een object definieert door te verwijzen naar een totaliteit die het te definiëren object omvat. Met zijn Vicious Circle Principle (VCP) wilde Russell de circulariteit in de wiskunde elimineren die voortkomt uit dergelijke impredicatieve definities. Russell gaf verschillende formuleringen van de VCP, waaronder:

Wat een schijnbare variabele bevat, mag geen mogelijke waarde van die variabele zijn (Russell 1908, in van Heijenoort 1967, 163).

De fundamentele analyse van predicativiteit door Poincaré, Russell en Weyl heeft de weg vrijgemaakt voor een verscheidenheid aan logische analyses van het begrip. De meest algemeen aanvaarde analyse is te danken aan Feferman en Schütte (onafhankelijk) volgens door Kreisel aangegeven lijnen (Kreisel 1958, Feferman 1964 en Schütte 1965; 1965a). Hier heeft de bewijstheorie een centrale rol gespeeld. In ruwe termen was het de bedoeling om een verzameling theorieën (een transfinite progressie van systemen van vertakte rekenkunde van de tweede orde geïndexeerd door ordinalen) te onderscheiden door middel van het karakteriseren van een bepaalde notie van predicatieve ordinale. Feferman en Schütte's bewijstheoretische analyse van deze theorieën heeft een ordinaal geïdentificeerd, gewoonlijk aangeduid als (Gamma_0), wat volgens dit idee het minst niet-predicatieve ordinale is. Een formeel systeem wordt als predicatief gerechtvaardigd beschouwd als het in theorie theoretisch herleidbaar is tot een systeem van vertakte tweede-orde artmetica, geïndexeerd door een ordinale minder dan (Gamma_0). Daarom wordt in bewijstheorie (Gamma_0) gewoonlijk beschouwd als de limiet van predicativiteit. (Zie Feferman 2005 voor een nauwkeuriger informeel verslag van deze notie van predicativiteit en voor verdere referenties. Zie ook Crosilla 2017. De lezer kan ook de paragraaf over predicativisme raadplegen in de inzending over filosofie van de wiskunde en de inzending over paradoxen en hedendaagse logica).(Zie Feferman 2005 voor een nauwkeuriger informeel verslag van deze notie van predicativiteit en voor verdere referenties. Zie ook Crosilla 2017. De lezer kan ook de paragraaf over predicativisme raadplegen in de inzending over filosofie van de wiskunde en de inzending over paradoxen en hedendaagse logica).(Zie Feferman 2005 voor een nauwkeuriger informeel verslag van deze notie van predicativiteit en voor verdere referenties. Zie ook Crosilla 2017. De lezer kan ook de paragraaf over predicativisme raadplegen in de inzending over filosofie van de wiskunde en de inzending over paradoxen en hedendaagse logica).

Voor constructieve fundamentele theorieën is een meer 'liberale' benadering van predicativisme voorgesteld, te beginnen met werk in de late jaren 50 van Lorenzen, Myhill en Wang (zie bv. Lorenzen en Myhill 1959). Het sturende idee is dat zogenaamde inductieve definities zouden moeten worden toegestaan op het gebied van constructieve wiskunde. De intuïtieve rechtvaardiging van inductieve definities houdt verband met het feit dat ze door middel van eindige regels op een 'bottom-up' manier kunnen worden uitgedrukt. De bewijstheoretische kracht van theorieën over inductieve definities gaat veel verder dan die van Feferman en Schütte (Buchholz, Feferman, Pohlers en Sieg 1981). Dus relatief sterke theorieën worden als predicatief beschouwd in de huidige grondslagen van constructieve wiskunde. Deze meer liberale notie van predicativiteit wordt vaak algemene predicativiteit genoemd. In dit artikel schrijven we eenvoudig predicativiteit voor gegeneraliseerde predicativiteit en noemen we predicativiteit gezien de natuurlijke getallen de bekendere vorm van predicativiteit die in de klassieke context ontstaat en werd geanalyseerd door Kreisel, Feferman en Schütte.

Een voorbeeld van een predicatieve theorie in deze zin is de constructieve verzamelingenleer CZF, aangezien haar bewijstheoretische kracht dezelfde is als die van een theorie van één inductieve definitie die bekend staat als ID (_ 1). Het systeem IZF daarentegen is impredicatief, aangezien de bewijstheoretische kracht ervan gelijk is aan die van de hele klassieke ZF (Friedman 1973a).

In verzamelingen theorieën die gebaseerd zijn op intuïtionistische logica, wordt predicativiteit meestal bereikt door de principes van scheiding en vermogensbeperking te beperken, aangezien deze de belangrijkste bronnen van impredicativiteit lijken te zijn (wanneer wordt aangenomen dat het oneindige axioma wordt aangenomen).

1.3.1 Impredicativiteit van scheiding

Het schema van scheiding stelt ons in staat om een subset te vormen van een bepaalde set waarvan de elementen voldoen aan een bepaalde eigenschap (uitgedrukt door een formule in de taal van de verzamelingenleer). Gegeven een set (B) en een formule (phi (X)), stelt scheiding ons in staat om een nieuwe set te construeren, de set van die elementen (X) van (B) waarvoor (phi) houdt. Dit wordt meestal informeel weergegeven als: ({X \ in B: \ phi (X) }). Scheiding kan leiden tot ongehoorzaamheid als de formule (phi) onbeperkte kwantoren bevat die zich uitstrekken over het hele universum van verzamelingen; in feite kunnen we bij het definiëren van de nieuwe set door scheiding dus naar deze set verwijzen, in tegenspraak met Russell's VCP. Als we bijvoorbeeld een set (C) door scheiding definiëren als ({X \ in B: \ forall Y \ psi (X, Y) }), dan behoort (C) tot de (Y) 's die moeten worden gecontroleerd voor de eigenschap (psi). Deze vorm van impredicativiteit wordt vermeden in de constructieve verzamelingenleer door het scheidingsschema te beperken: door te eisen dat alle kwantoren die in het formule (phi) -bereik voorkomen, alleen over "eerder geconstrueerde" sets gaan. Syntactisch betekent dit dat we, gegeven een set (B), een nieuwe set ({X \ in B: \ phi (X) }) kunnen vormen door alleen te scheiden als alle kwantoren in (phi) zijn begrensd; dat wil zeggen, alleen als alle kwantoren in (phi) de vorm hebben (forall X (X \ in Y \ rightarrow \ ldots)) of (bestaat X (X \ in Y \ wedge \ ldots)), voor sommige set (Y).\ phi (X) }) alleen door scheiding als alle kwantoren in (phi) begrensd zijn; dat wil zeggen, alleen als alle kwantoren in (phi) de vorm hebben (forall X (X \ in Y \ rightarrow \ ldots)) of (bestaat X (X \ in Y \ wedge \ ldots)), voor sommige set (Y).\ phi (X) }) alleen door scheiding als alle kwantoren in (phi) begrensd zijn; dat wil zeggen, alleen als alle kwantoren in (phi) de vorm hebben (forall X (X \ in Y \ rightarrow \ ldots)) of (bestaat X (X \ in Y \ wedge \ ldots)), voor sommige set (Y).

We kunnen zien dat het op deze manier beperken van separatie impredicativiteit vermijdt, door te observeren dat de bewijstheoretische kracht van CZF, die slechts beperkte separatie heeft, binnen het bereik van predicativiteit valt. Door CZF echter volledig van elkaar te scheiden, verkrijgt men een impredicatieve theorie, in feite een theorie met dezelfde bewijstheoretische kracht als volledige tweede-orde rekenkunde (Lubarsky 2006). Zie ook Sectie 5 voor een bespreking van de rol van bewijstheorie bij het analyseren van constructieve en intuïtionistische verzamelingenleer.

1.3.2 Impredicativiteit van Powerset

Met het vermogensset axioma kunnen we een set van alle subsets van een bepaalde set vormen. Een voorbeeld van een oneigenlijk gebruik van de vermogensset wordt gegeven door de definitie van een subset van de natuurlijke getallen, (N), als volgt: (B: = {n \ in N: \ forall C \ subseteq N \ phi (n, C) }), waarbij (phi) kan worden beschouwd als een begrensde formule. Een vorm van circulariteit ontstaat hier omdat (B) zelf behoort tot de subsets van (N) die moeten worden gecontroleerd op (phi). Zoals benadrukt door Myhill (1975, 354), is vermogensset moeilijk te rechtvaardigen vanuit een constructief oogpunt: het verzamelt alle subsets van een bepaalde set, maar schrijft geen regel voor die de set van eerder gegeven "construeert" sets, zoals predicativiteit lijkt te vereisen.

Myhill schrijft:

Power set lijkt bijzonder niet-constructief en impredicatief in vergelijking met de andere axioma's: het gaat er niet om, zoals de anderen doen, sets te maken of uit elkaar te halen die men al heeft geconstrueerd, maar eerder om uit de totaliteit van alle sets degenen te selecteren die in de relatie staan van opname in een bepaalde set. (Myhill 1975, 351).

Power set lijkt bijzonder problematisch in het geval van oneindige sets, aangezien "we geen idee hebben wat een willekeurige subset van een oneindige set is; er is geen manier om ze allemaal te genereren en dus kunnen we niet de set vormen van alle hen "(Myhill 1975, 354). Als gevolg hiervan lijkt er geen manier te zijn om de set van alle subsets van een oneindige set constructief zin te geven.

Myhill merkt cruciaal op dat power set niet nodig is voor constructieve wiskunde Bishop-stijl, omdat het kan worden vervangen door een van de gevolgen. Dit wordt vaak het exponentiatie-axioma van Myhill genoemd en stelt dat we een set van alle functies van de ene set naar de andere kunnen vormen. Dit axioma is duidelijk equivalent aan een vermogensset in een klassieke context, waar subsets van een bepaalde set kunnen worden vertegenwoordigd door karakteristieke functies. Bij afwezigheid van het principe van uitgesloten midden zijn machtsinstelling en machtsverheffing echter niet equivalent. De fundamentele waarneming van Myhill is dat machtsverheffing voldoende is om de wiskunde van (Bishop 1967) uit te voeren; het maakt bijvoorbeeld de constructie mogelijk van de (Cauchy) reële getallen binnen de constructieve verzamelingenleer. Myhill beweert dat machtsverheffen constructief zinvol is omdat een functie een regel is,een eindig object dat werkelijk gegeven kan worden.

Hij schrijft ook dat het geval van machtsset verschilt van dat van machtsverheffing als:

zelfs in het geval van oneindige sets (A) en (B) hebben we een idee van een willekeurige toewijzing van (A) naar (B). Een willekeurige toewijzing van (mathbf {Z}) naar (mathbf {Z}) is een gedeeltelijke recursieve functie, samen met een bewijs dat de berekening altijd eindigt; een soortgelijk verslag kan worden gegeven van een willekeurige reële functie. Er is geen overeenkomstige uitleg van "willekeurige subset". (Myhill 1975, 354).

Het exponentiatie-axioma van Myhill maakt nu deel uit van alle grote systemen van de constructieve verzamelingenleer. In het geval van CZF heeft men in feite een versterking van de machtsverheffing, bekend als subset-verzameling, wat ook een verzwakking van de machtsverzameling is. Een veralgemening van machtsverheffing is ook te vinden in de constructieve typetheorie.

In het geval van CZF kan de bewering dat het toevoegen van het vermogensset-axioma een vorm van impredicativiteit veroorzaakt, worden onderbouwd door een technisch resultaat. Rathjen (2012b) laat zien dat CZF, vermeerderd met het power set axioma, de kracht van de klassieke Zermelo verzamelingenleer overtreft, en dus de toevoeging van het power set axioma aan CZF brengt ons tot een volledig impredicatieve theorie. Dit toont ook aan dat de implicatie van machtsverzameling tot verzameling van subverzamelingen niet ongedaan kan worden gemaakt, aangezien de bewijstheoretische kracht van CZF ver onder die van de verzamelingenleer van Zermleo ligt. Met andere woorden, het axioma van de vermogensset is veel sterker dan zowel machtsverheffing als verzameling van subgroepen.

1.3.3 Het constructieve universum van sets

Nu we passende beperkingen hadden ingevoerd voor het instellen en scheiden van energie, konden we nu een aanzienlijk bezwaar maken. Constructieve en intuïtionistische verzamelingenleer kan worden gezien als modificaties van de klassieke ZF-verzamelingenleer die worden verkregen door: (1) klassiek te vervangen door intuïtionistische logica, en (2) nauwkeurig te kiezen uit verschillende klassiek equivalente principes, die meer geschikt lijken voor bepaalde doeleinden. We kunnen bijvoorbeeld principes kiezen die voldoende zijn om een bepaalde wiskundige praktijk weer te geven, zoals bijvoorbeeld wiskunde in bisschopstijl. Het resulterende begrip set kan echter onduidelijk worden en de keuze van de set-theoretische principes kan in zekere mate willekeurig lijken. In het geval van intuïtionistische ZF kan men de keuze van de set-theoretische principes rechtvaardigen door de semantische interpretaties ervan te onderzoeken,als Heyting semantiek, of door te kijken naar de categorische modellen. In het geval van de constructieve verzamelingenleer heeft Aczel, om dit soort bezwaar tegen te gaan, een interpretatie van CZF gegeven in een versie van de Martin-Löf-typetheorie (Aczel 1978). De bewering is dat aan CZF's idee van set dus een duidelijke constructieve betekenis wordt toegekend door te kijken naar de betekenis ervan in de Martin-Löf-typetheorie, aangezien deze laatste gewoonlijk wordt beschouwd als een nauwkeurige en volledig gemotiveerde formulering van een constructieve notie van set. Aczel's interpretatie van CZF in de constructieve typetheorie wordt gegeven door interpreterende verzamelingen als bomen in de typetheorie. Dat wil zeggen, in de constructieve typetheorie wordt het universum van verzamelingen van CZF voorgesteld door een type, V, van over het universum gebouwde verzamelingen, U, van kleine typen (Aczel 1978; Martin-Löf 1984). Deze interpretatie benadrukt duidelijk de (algemene) predicativiteit van CZF, waarvan de sets kunnen worden gezien als inductief opgebouwde bomen, en waarvan het set-theoretische universum ook een duidelijke inductieve structuur heeft.

De voorspelbaarheid van CZF en gerelateerde systemen komt overeen met filosofische posities die vaak worden geassocieerd met het gebruik van intuïtionistische logica. In het bijzonder lijkt het erop dat als we de wiskundige objecten construeren, bijvoorbeeld, als de wiskundige objecten een of andere mentale constructie zijn, dan zou een toevlucht tot impredicatieve definities een ongewenste vorm van circulariteit opleveren. Dit staat duidelijk in contrast met een visie die vaak wordt geassocieerd met de klassieke verzamelingenleer, waarvoor onze wiskundige activiteit kan worden gezien als een geleidelijke onthulling van eigenschappen van het universum van verzamelingen, waarvan het bestaan onafhankelijk is van ons. Een dergelijke opvatting hangt meestal samen met het gebruik van klassieke logica en impredicativiteit bij het bestuderen van het verzamelingenleer. Predicativiteit wordt ook vaak gezien als gerelateerd aan het aloude onderscheid tussen werkelijke en potentiële oneindigheid. Predicatieve (en dus in het bijzonder constructieve) theorieën worden vaak gezien als verwijzingen naar de werkelijke oneindigheid, en begaan alleen de potentiële oneindigheid (Dummett 2000, Fletcher 2007). Dit lijkt weer in het bijzonder in harmonie met die filosofische posities die de menselijke dimensie van onze wiskundige activiteit benadrukken, door bijvoorbeeld de wiskundige objecten en de waarheid van uitspraken daarover als afhankelijk van ons te beschouwen. Een ander gerelateerd aspect wordt vaak gezien als met betrekking tot predicativiteit: als het universum van decors in fasen wordt opgebouwd door onze eigen wiskundige activiteit, dan zou het ook natuurlijk zijn om het als een open einde te beschouwen. Om deze reden, in een constructieve context,waar de verwerping van klassieke logica voldoet aan de eis van predicativiteit, wordt het universum van verzamelingen vaak beschreven als een open concept, een universum “in fieri”. Dit idee wordt vooral goed geïllustreerd binnen de constructieve typetheorie, waar Per Martin-Löf het begrip type-theoretisch universum opzettelijk open heeft gelaten (door er geen specifieke eliminatieregels voor te posten). De open aard van het universum van decors heeft de weg vrijgemaakt voor uitbreiding ervan door reflectieprincipes. Deze zijn zowel binnen typetheorie als constructieve verzamelingenleer onderzocht. Zie (Rathjen 2005a) voor een overzicht van resultaten en een fundamentele discussie, en ook paragraaf 5.2. Voor een formele analyse van het constructieve universum van sets en een vergelijking met de Von Neumann-hiërarchie, zie (Ziegler 2014).het universum van decors wordt vaak omschreven als een open concept, een universum “in fieri”. Dit idee wordt vooral goed geïllustreerd binnen de constructieve typetheorie, waar Per Martin-Löf het begrip type-theoretisch universum opzettelijk open heeft gelaten (door er geen specifieke eliminatieregels voor te posten). De open aard van het universum van decors heeft de weg vrijgemaakt voor uitbreiding ervan door reflectieprincipes. Deze zijn zowel binnen typetheorie als constructieve verzamelingenleer onderzocht. Zie (Rathjen 2005a) voor een overzicht van resultaten en een fundamentele discussie, en ook paragraaf 5.2. Voor een formele analyse van het constructieve universum van sets en een vergelijking met de Von Neumann-hiërarchie, zie (Ziegler 2014).het universum van decors wordt vaak omschreven als een open concept, een universum “in fieri”. Dit idee wordt vooral goed geïllustreerd binnen de constructieve typetheorie, waar Per Martin-Löf het begrip type-theoretisch universum opzettelijk open heeft gelaten (door er geen specifieke eliminatieregels voor te posten). De open aard van het universum van decors heeft de weg vrijgemaakt voor uitbreiding ervan door reflectieprincipes. Deze zijn zowel binnen typetheorie als constructieve verzamelingenleer onderzocht. Zie (Rathjen 2005a) voor een overzicht van resultaten en een fundamentele discussie, en ook paragraaf 5.2. Voor een formele analyse van het constructieve universum van sets en een vergelijking met de Von Neumann-hiërarchie, zie (Ziegler 2014).waar het begrip type-theoretisch universum opzettelijk open is gelaten door Per Martin-Löf (door er geen specifieke eliminatieregels voor te posten). De open aard van het universum van decors heeft de weg vrijgemaakt voor uitbreiding ervan door reflectieprincipes. Deze zijn zowel binnen typetheorie als constructieve verzamelingenleer onderzocht. Zie (Rathjen 2005a) voor een overzicht van resultaten en een fundamentele discussie, en ook paragraaf 5.2. Voor een formele analyse van het constructieve universum van sets en een vergelijking met de Von Neumann-hiërarchie, zie (Ziegler 2014).waar het begrip type-theoretisch universum opzettelijk open is gelaten door Per Martin-Löf (door er geen specifieke eliminatieregels voor te posten). De open aard van het universum van decors heeft de weg vrijgemaakt voor uitbreiding ervan door reflectieprincipes. Deze zijn zowel binnen typetheorie als constructieve verzamelingenleer onderzocht. Zie (Rathjen 2005a) voor een overzicht van resultaten en een fundamentele discussie, en ook paragraaf 5.2. Voor een formele analyse van het constructieve universum van sets en een vergelijking met de Von Neumann-hiërarchie, zie (Ziegler 2014). Deze zijn zowel binnen typetheorie als constructieve verzamelingenleer onderzocht. Zie (Rathjen 2005a) voor een overzicht van resultaten en een fundamentele discussie, en ook paragraaf 5.2. Voor een formele analyse van het constructieve universum van sets en een vergelijking met de Von Neumann-hiërarchie, zie (Ziegler 2014). Deze zijn zowel binnen typetheorie als constructieve verzamelingenleer onderzocht. Zie (Rathjen 2005a) voor een overzicht van resultaten en een fundamentele discussie, en ook paragraaf 5.2. Voor een formele analyse van het constructieve universum van sets en een vergelijking met de Von Neumann-hiërarchie, zie (Ziegler 2014).

2. Oorsprong van constructieve en intuïtionistische verzamelingenleer

Intuitionistische versies van Zermelo-Fraenkel-theorieën werden in de vroege jaren zeventig geïntroduceerd door Friedman en Myhill. In (Friedman 1973) presenteert de auteur een studie van formele eigenschappen van verschillende intuïtionistische systemen en introduceert voor hen een uitbreiding van Kleene's realisatiemethode. De realiseerbaarheidstechniek wordt in (Myhill 1973) toegepast om het bestaan van een versie van de intuïtionistische Zermelo-Fraenkel-verzamelingenleer te tonen (met vervanging in plaats van verzameling). In een andere fundamentele bijdrage breidt Friedman de vertaling van dubbele negatie van intuïtonistische logica uit om klassieke en intuïtionistische verzamelingenleer te relateren (Friedman 1973a). Deze eerste artikelen behandelen al de relatie tussen enkele belangrijke intuïtionistische verzamelingenleer en klassieke ZF. Ze verduidelijken ook een belangrijk kenmerk van verzamelingenleer gebaseerd op intuïtionistische logica,vooral dat het vatbaar is voor krachtige constructieve semantische interpretaties, zoals realiseerbaarheid. Deze technieken worden toegepast bij de studie van cruciale metatheoretische eigenschappen die typerend zijn voor de constructieve benadering en waarvan sommige constructieve theorieën genieten (zie de paragraaf over semantische technieken). Dit baanbrekende werk is volledig benut en aanzienlijk uitgebreid in het werk van Beeson en McCarty (zie Beeson 1985; McCarty 1984). Dit baanbrekende werk is volledig benut en aanzienlijk uitgebreid in het werk van Beeson en McCarty (zie Beeson 1985; McCarty 1984). Dit baanbrekende werk is volledig benut en aanzienlijk uitgebreid in het werk van Beeson en McCarty (zie Beeson 1985; McCarty 1984).

De constructieve verzamelingenleer heeft vanaf het begin een meer onderscheidende fundamentele roeping en is verbonden met de wiskunde van Bishop. In feite publiceerde Bishop in 1967 het boek "Foundations of constructive analysis" (Bishop 1967), dat een nieuw tijdperk voor wiskunde opende op basis van intuïtionistische logica (zie de vermelding over constructieve wiskunde). De monografie stimuleerde nieuwe pogingen in de logische gemeenschap om de principes die door Bishop werden gebruikt te verduidelijken en formeel weer te geven, zij het alleen op informeel niveau. Bij de eerste pogingen van Goodman en Myhill (Goodman en Myhill 1972) werd gebruik gemaakt van versies van Gödel's systeem T (zie ook (Bishop 1970) voor een vergelijkbare poging). Myhill kwam echter tot de conclusie dat de resulterende formalisering te complex en kunstmatig was (Myhill 1975, 347). Myhill stelde in plaats daarvan een systeem voor dat dichter bij de informele notie van set oorspronkelijk door Bishop werd gebruikt en ook dichter bij de set-theoretische traditie. Myhill schrijft (1975, 347):

We weigeren te geloven dat het zo ingewikkeld moet zijn - de argumentatie van (Bishop 1967) ziet er erg soepel uit en lijkt rechtstreeks te vallen uit een bepaald concept van wat sets, functies, enz. Zijn, en we willen een formalisme ontdekken dat isoleert de principes die aan deze opvatting ten grondslag liggen, zoals de verzamelingenleer van Zermelo-Fraenkel de principes isoleert die ten grondslag liggen aan de klassieke (niet-constructieve) wiskunde. We willen dat deze principes het formaliseringsproces volledig triviaal maken, zoals in het klassieke geval.

We zien hier dat Myhill's constructieve verzamelingenleer noties had onderscheiden van functie, natuurlijk aantal en verzameling; het vertegenwoordigde dus nauw een constructieve traditie waarin functies en natuurlijke getallen conceptueel onafhankelijk zijn van decors. Een andere fundamentele stap in de ontwikkeling van de constructieve verzamelingenleer was Friedman's "Set-theoretische grondslagen voor constructieve analyse" (Friedman 1977). Hier wordt onder andere een systeem genaamd B gedefinieerd dat verdere beperkingen heeft op de set-theoretische principes in vergelijking met Myhill's (in het bijzonder heeft het geen set-inductie). Het heeft ook een beperkte vorm van het axioma van afhankelijke keuze. Systeem B blijkt daar expressief genoeg te zijn om de constructieve analyse van Bishop (1967) weer te geven, terwijl het tegelijkertijd theoretisch zeer zwak is (vanwege het ontbreken van vaste inductie). Systeem B is in feite een conservatieve uitbreiding van rekenen (dus het ligt ruim onder de limiet van predicativiteit gezien de natuurlijke getallen die kort worden genoemd in paragraaf 1.3). De systemen van Myhill en Friedman werden vervolgens door Aczel aangepast om een systeem, CZF (Constructive Zermelo-Fraenkel), te verkrijgen dat volledig compatibel is met de ZF-taal (Aczel 1978, 1982, 1986; Aczel en Rathjen 2001; 2010). CZF heeft ook geen keuzeprincipes opgenomen. Aczel gaf een interpretatie van CZF in de Martin-Löf-typetheorie met als doel het constructieve karakter van de verzamelingenleer te bevestigen. Hij versterkte ook enkele van de principes van het Myhill-systeem (namelijk verzameling en machtsverheffing) omdat de sterkere versies nog steeds worden gevalideerd door de interpretatie in de typetheorie.

Andere fundamentele systemen voor constructieve wiskunde in bisschopstijl werden begin jaren 70 geïntroduceerd. Bijvoorbeeld: expliciete wiskunde door S. Feferman (Feferman 1975), en de reeds genoemde Intuitionistic Type Theory (Martin-Löf 1975; 1984). Constructieve typetheorie wordt meestal beschouwd als de meest bevredigende basis voor constructieve wiskunde Bishop-stijl. Zowel typetheorie als expliciete wiskunde kunnen worden gezien als een directere uitdrukking van de computationele inhoud van constructieve wiskunde. Met name de typetheorie kan gelezen worden als een zeer algemene en expressieve programmeertaal. Constructieve en intuïtionistische set-theorieën geven hun computationele inhoud alleen indirect weer door middel van hun semantische interpretaties (zie bv. (Aczel 1977), (Lipton 1995) en de sectie over semantische technieken).

3. De Axioms Systems CZF en IZF

Voor een lezer die al bekend is met de ZF-verzamelingenleer, herinneren we ons nu kort de axioma's van de systemen CZF en IZF. Voor een volledige lijst en een uitleg van hun axioma's verwijzen we in plaats daarvan naar het aanvullende document:

Axioma's van CZF en IZF.

CZF en IZF zijn geformuleerd op basis van intuïtionistische eerste-orde logica met gelijkheid, met slechts (in) (lidmaatschap) als een extra niet-logisch binair predikaatsymbool. Hun set-theoretische axioma's zijn als volgt.

(mathbf {IZF})	(mathbf {CZF})
Extensionality	(dezelfde)
Paar	(dezelfde)
Unie	(dezelfde)
Oneindigheid	(dezelfde)
Scheiding	Beperkte scheiding
Verzameling	Sterke collectie
Powerset	Subset-collectie
Inductie instellen	(dezelfde)

Merk op dat in IZF het schema van scheiding onbeperkt is. In CZF wordt de collectie versterkt om de beperkte scheiding te compenseren. Subset-collectie is een versterking van Myhill's machtsverheffen-axioma, en vervangt daarmee ZF's Powerset.

4. Constructieve keuze principes

Bij het bespreken van de rol van klassieke verzamelingenleer als basis voor wiskunde, beschouwt men meestal de theorie ZFC, dat wil zeggen het axioma-systeem ZF plus het axioma van keuze (AC). Men kan zich daarom afvragen wat de status is van het keuzeaxioma in intuïtionistische omgevingen. De vraag is bijzonder belangrijk omdat het keuzeaxioma bij zijn eerste verschijning vaak als controversieel en zeer niet-constructief werd beschouwd. In constructieve contexten is men echter getuige van een eigenaardig fenomeen. De gebruikelijke vorm van het keuzeaxioma wordt gevalideerd door theorieën van typen zoals de Martin-Löf-typetheorie, waar de Curry-Howard-correspondentie geldt (zie paragraaf 3.4 van de inzending over constructieve wiskunde). Aan de andere kant, de veronderstelling van het keuzeaxioma geeft aanleiding tot gevallen van het uitgesloten midden in extensieve contexten,waar ook een vorm van scheiding mogelijk is. Dit is bijvoorbeeld het geval bij constructieve en intuïtionistische ZF. (Zie voor het bewijs het aanvullende document over Set-theoretic Principles Incompatible with Intuitionistic Logic.) Een bewijs van de incompatibiliteit van AC met extensieve set-theorieën gebaseerd op intuïtionistische logica lijkt voor het eerst te zijn verschenen in (Diaconescu 1975) in een categorische context. Goodman en Myhill geven een argument voor theorieën op basis van intuïtionistische logica (Goodman en Myhill 1978).) Een bewijs van de onverenigbaarheid van AC met extensieve set theorieën gebaseerd op intuïtionistische logica lijkt voor het eerst te zijn verschenen in (Diaconescu 1975) in een categorische context. Goodman en Myhill geven een argument voor theorieën op basis van intuïtionistische logica (Goodman en Myhill 1978).) Een bewijs van de onverenigbaarheid van AC met extensieve set theorieën gebaseerd op intuïtionistische logica lijkt voor het eerst te zijn verschenen in (Diaconescu 1975) in een categorische context. Goodman en Myhill geven een argument voor theorieën op basis van intuïtionistische logica (Goodman en Myhill 1978).

Hoewel het keuzeaxioma niet compatibel is met zowel constructieve als intuïtionistische ZF, kunnen andere keuzeprincipes aan de basissystemen worden toegevoegd zonder dezelfde ongewenste resultaten te produceren. Men zou bijvoorbeeld het principe van telbare keuze (AC (_ 0)) of dat van afhankelijke keuze (DC) kunnen toevoegen. Beide zijn zelfs vaak gebruikt in de constructieve wiskundige praktijk. (Zie voor hun exacte formulering het aanvullende document over Axioma's van CZF en IZF.)

In (Aczel 1978) overwoog de auteur ook een keuzeprincipe genaamd de Presentation Axiom, dat stelt dat elke set het surjectieve beeld is van een zogenaamde basis. Een basis is een verzameling, zeg (B), zodat elke relatie met domein (B) een functie uitbreidt met domein (B).

De compatibiliteit van al deze vormen van keuze met de constructieve verzamelingenleer is door Aczel bewezen door zijn interpretatie van CZF uit te breiden tot de Martin-Löf-typetheorie (Aczel 1982). Rathjen (2006) heeft ook verschillende constructieve keuzeprincipes en hun onderlinge relaties overwogen.

Een laatste opmerking: hoewel constructieve en intuïtionistische set-theorieën compatibel zijn met de zojuist genoemde keuzeprincipes, worden de set-theorieën vaak gedefinieerd zonder enige keuze-principes. Dit heeft tot doel een "pluralistische" fundamentele benadering mogelijk te maken. In het bijzonder zou men een fundamentele theorie willen verkrijgen die compatibel is met die contexten (bijv. Categorische modellen van verzamelingenleer) waarin zelfs deze zwakkere keuzeprincipes mogelijk niet worden gevalideerd. Voor vergelijkbare ideeën in de context van constructieve typetheorie, zie (Maietti en Sambin 2005, Maietti 2009). We willen hier ook Richmans oproep voor constructieve wiskunde vermelden die geen gebruik maakt van keuzeprincipes (Richman 2000; 2001).

5. Bewijstheorie en semantiek van constructieve en intuïtionistische ZF

Bij het beschouwen van een bepaalde wiskundige praktijk (of een theorie die wordt gebruikt om deze te codificeren) vanuit een filosofisch perspectief, moeten we met de grootst mogelijke precisie de aannames die erin worden gedaan en de gevolgen die uit die aannames voortvloeien, verduidelijken. Dit geldt met name bij het werken met theorieën die gebaseerd zijn op een zwakkere logica dan de klassieke, waarvoor een dieper, nauwkeuriger inzicht verplicht is. Er zijn veel technische tools beschikbaar die ons kunnen helpen deze aspecten te verduidelijken. Onder de beschikbare instrumenten zijn er proof-theoretische technieken, zoals proof-theoretische interpretaties, evenals semantische technieken, zoals realiseerbaarheid, Kripke-modellen, door Heyting gewaardeerde semantiek. In feite is men in de literatuur vaak getuige van het samenspel van bewijstheoretische en semantische technieken. We geven hier een vluchtige blik op enkele van deze onderwerpen en stellen voor om verder te lezen.

5.1 Bewijs-theoretische kracht

Een fundamenteel thema in de bewijstheorie (met name in de tak van deze discipline die bekend staat als ordinale analyse) is de classificatie van theorieën door middel van transfinite ordinalen die hun "consistentie-sterkte" en "rekenkracht" meten. Deze ordinalen geven een indicatie van hoe sterk een theorie is en bieden daarom een manier om verschillende theorieën te vergelijken. De ordinale (varepsilon_0) is bijvoorbeeld de proof-theoretische ordinale van Peano Arithmetic en is veel kleiner dan de ordinale (Gamma_0), gewoonlijk "de limiet van predicativiteit" genoemd (zie paragraaf 1.3 hierboven)). Dit is een aanwijzing dat er theoretisch aanvaardbare theorieën zijn die veel sterker zijn dan Peano-rekenkunde.

Zoals besproken in sectie 1, vereist de stap van klassieke ZF naar zijn intuïtionistische varianten dat we een geschikte formulering kiezen voor elk set-theoretisch axioma: één klassiek axioma kan een aantal intuïtionistische varianten hebben die niet gelijkwaardig aan elkaar blijken te zijn. Dit wordt soms weerspiegeld door de bewijstheoretische kracht van de resulterende theorieën, die kunnen variëren afhankelijk van de principes die we kiezen. We hebben bijvoorbeeld al opgemerkt dat we in CZF geen volledige scheiding en vermogensset hebben, die worden vervangen door de predicatief acceptabele principes van respectievelijk begrensde scheiding en subsetverzameling. Als we echter een van deze principes aan CZF toevoegen, verkrijgen we impredicatieve theorieën. De onvoorzichtigheid van de resulterende theorieën blijkt uit het feit dat hun bewijstheoretische kracht veel groter is dan die van CZF.

Het is niet verwonderlijk dat onderzoeken naar de bewijstheoretische kracht van constructieve en intutionistische verzamelingenleer theorieën een cruciaal metatheoretisch instrument zijn geweest om deze theorieën en hun relaties met elkaar te begrijpen. Onderzoeken naar de bewijstheoretische kracht van een theorie zijn rijk en informatief. Feferman (1993) heeft in het bijzonder betoogd dat een proof-theoretische analyse ons kan helpen vast te stellen of een bepaalde theorie voldoet aan een bepaald filosofisch kader: de analyse kan bijvoorbeeld aan het licht brengen dat een theorie predicatief of finitistisch is enz. Bovendien, als een bijproduct van de bewijstheoretische analyse verkrijgen we soms eenvoudige onafhankelijkheidsverklaringen. We kunnen zelfs aantonen dat een theorie een specifiek principe niet kan bewijzen omdat het toevoegen van de theorie aan de theorie van de bewijstheoretische kracht zou toenemen. Bijvoorbeeld,CZF bewijst het powerset-axioma niet, aangezien de toevoeging van powerset aan CZF leidt tot een veel sterkere theorie. Proef-theoretische interpretaties zijn ook gebruikt om constructieve en intuïtionistische ZF-set-theorieën met elkaar te vergelijken, evenals met hun klassieke tegenhangers, en ook met andere fundamentele systemen voor constructieve wiskunde, zoals constructieve typetheorie en expliciete wiskunde (zie bijv. Griffor en Rathjen 1994, Tupailo 2003). Voor een definitie van het begrip bewijstheoretische kracht en voor onderzoeken naar bewijstheorie zie bijvoorbeeld (Rathjen 1999, 2006b).evenals met hun klassieke tegenhangers, en ook met andere fundamentele systemen voor constructieve wiskunde, zoals constructieve typetheorie en expliciete wiskunde (zie bv. Griffor en Rathjen 1994, Tupailo 2003). Voor een definitie van het begrip bewijstheoretische kracht en voor onderzoeken naar bewijstheorie zie bijvoorbeeld (Rathjen 1999, 2006b).evenals met hun klassieke tegenhangers, en ook met andere fundamentele systemen voor constructieve wiskunde, zoals constructieve typetheorie en expliciete wiskunde (zie bv. Griffor en Rathjen 1994, Tupailo 2003). Voor een definitie van het begrip bewijstheoretische kracht en voor onderzoeken naar bewijstheorie zie bijvoorbeeld (Rathjen 1999, 2006b).

Hoewel CZF en IZF de meest bestudeerde systemen zijn, zijn tot dusver in de literatuur tal van andere systemen voor constructieve en intuïtionistische verzamelingenleer overwogen. De bewijstheoretische kracht van een aantal constructieve en intuïtionistische verzamelingenleer is tot stand gebracht door een verscheidenheid aan hulpmiddelen, zoals bijvoorbeeld een uitbreiding op de verzamelingenleer van de dubbele negatie-interpretatie (ontstaan in (Friedman 1973a)) en een verscheidenheid van andere proof-theoretische interpretaties, vaak het resultaat van een zorgvuldige combinatie van semantische en proof-theoretische technieken. In veel gevallen is de bewijstheoretische kracht van een systeem bepaald door een reeks interpretaties tussen constructieve en klassieke systemen, en door gebruik te maken van een verscheidenheid aan instrumenten, van betrouwbaarheid tot meer "traditionele" bewijstheoretische technieken, als ordinale analyse (zie,bijvoorbeeld Beeson 1985; Griffor en Rathjen 1994; Rathjen 2012b). Met name de realisatie is door de flexibiliteit erg nuttig gebleken. Wat de uitkomsten van deze onderzoeken betreft, blijken sommige van de geanalyseerde systemen zo zwak als rekenen, zoals bijvoorbeeld Friedmans systeem B (Friedman 1977); andere systemen zijn even sterk als volledig klassieke ZF, zoals IZF (Friedman 1973a). Er zijn ook systemen met middelmatige sterkte, zoals CZF. De kracht van de laatste theorie is in feite gelijk aan die van een theorie van één inductieve definitie die bekend staat als ID (_ 1). Het feit dat CZF dezelfde sterkte heeft als ID (_ 1) wordt genomen om de (gegeneraliseerde) predicativiteit van de verzamelingenleer te bevestigen en om te bewijzen dat het de limiet van predicativiteit overschrijdt, gegeven de natuurlijke getallen, aangezien ID (_ 1) 's bewijstheoretische ordinal ligt ruim boven (Gamma_0). Beeson 1985; Griffor en Rathjen 1994; Rathjen 2012b). Met name de realisatie is door de flexibiliteit erg nuttig gebleken. Wat de uitkomsten van deze onderzoeken betreft, blijken sommige van de geanalyseerde systemen zo zwak als rekenen, zoals bijvoorbeeld Friedmans systeem B (Friedman 1977); andere systemen zijn even sterk als volledig klassieke ZF, zoals IZF (Friedman 1973a). Er zijn ook systemen met middelmatige sterkte, zoals CZF. De kracht van de laatste theorie is in feite gelijk aan die van een theorie van één inductieve definitie die bekend staat als ID (_ 1). Het feit dat CZF dezelfde sterkte heeft als ID (_ 1) wordt genomen om de (gegeneraliseerde) predicativiteit van de verzamelingenleer te bevestigen en om te bewijzen dat het de limiet van predicativiteit overschrijdt, gegeven de natuurlijke getallen, aangezien ID (_ 1) 's bewijstheoretische ordinal ligt ruim boven (Gamma_0). Beeson 1985; Griffor en Rathjen 1994; Rathjen 2012b). Met name de realisatie is door de flexibiliteit erg nuttig gebleken. Wat de uitkomsten van deze onderzoeken betreft, blijken sommige van de geanalyseerde systemen zo zwak als rekenen, zoals bijvoorbeeld Friedmans systeem B (Friedman 1977); andere systemen zijn even sterk als volledig klassieke ZF, zoals IZF (Friedman 1973a). Er zijn ook systemen met gemiddelde sterkte, zoals CZF. De kracht van de laatste theorie is in feite gelijk aan die van een theorie van één inductieve definitie die bekend staat als ID (_ 1). Het feit dat CZF dezelfde sterkte heeft als ID (_ 1) wordt genomen om de (gegeneraliseerde) predicativiteit van de verzamelingenleer te bevestigen en om te bewijzen dat het de limiet van predicativiteit overschrijdt, gegeven de natuurlijke getallen, aangezien ID (_ 1) 's bewijstheoretische ordinal ligt ruim boven (Gamma_0). Rathjen 2012b). Met name de realisatie is door de flexibiliteit erg nuttig gebleken. Wat de uitkomsten van deze onderzoeken betreft, blijken sommige van de geanalyseerde systemen zo zwak als rekenen, zoals bijvoorbeeld Friedmans systeem B (Friedman 1977); andere systemen zijn even sterk als volledig klassieke ZF, zoals IZF (Friedman 1973a). Er zijn ook systemen met middelmatige sterkte, zoals CZF. De kracht van de laatste theorie is in feite gelijk aan die van een theorie van één inductieve definitie die bekend staat als ID (_ 1). Het feit dat CZF dezelfde sterkte heeft als ID (_ 1) wordt genomen om de (gegeneraliseerde) predicativiteit van de verzamelingenleer te bevestigen en om te bewijzen dat het de limiet van predicativiteit overschrijdt, gegeven de natuurlijke getallen, aangezien ID (_ 1) 's bewijstheoretische ordinal ligt ruim boven (Gamma_0). Rathjen 2012b). Met name de realisatie is door de flexibiliteit erg nuttig gebleken. Wat de uitkomsten van deze onderzoeken betreft, blijken sommige van de geanalyseerde systemen zo zwak als rekenen, zoals bijvoorbeeld Friedmans systeem B (Friedman 1977); andere systemen zijn even sterk als volledig klassieke ZF, zoals IZF (Friedman 1973a). Er zijn ook systemen met gemiddelde sterkte, zoals CZF. De kracht van de laatste theorie is in feite gelijk aan die van een theorie van één inductieve definitie die bekend staat als ID (_ 1). Het feit dat CZF dezelfde sterkte heeft als ID (_ 1) wordt genomen om de (gegeneraliseerde) predicativiteit van de verzamelingenleer te bevestigen en om te bewijzen dat het de limiet van predicativiteit overschrijdt, gegeven de natuurlijke getallen, aangezien ID (_ 1) 's bewijstheoretische ordinal ligt ruim boven (Gamma_0).door de flexibiliteit is de realiseerbaarheid zeer nuttig gebleken. Wat de uitkomsten van deze onderzoeken betreft, blijken sommige van de geanalyseerde systemen zo zwak als rekenen, zoals bijvoorbeeld Friedmans systeem B (Friedman 1977); andere systemen zijn even sterk als volledig klassieke ZF, zoals IZF (Friedman 1973a). Er zijn ook systemen met middelmatige sterkte, zoals CZF. De kracht van de laatste theorie is in feite gelijk aan die van een theorie van één inductieve definitie die bekend staat als ID (_ 1). Het feit dat CZF dezelfde sterkte heeft als ID (_ 1) wordt genomen om de (gegeneraliseerde) predicativiteit van de verzamelingenleer te bevestigen en om te bewijzen dat het de limiet van predicativiteit overschrijdt, gegeven de natuurlijke getallen, aangezien ID (_ 1) 's bewijstheoretische ordinal ligt ruim boven (Gamma_0).door de flexibiliteit is de realiseerbaarheid zeer nuttig gebleken. Wat de uitkomsten van deze onderzoeken betreft, blijken sommige van de geanalyseerde systemen zo zwak als rekenen, zoals bijvoorbeeld Friedmans systeem B (Friedman 1977); andere systemen zijn even sterk als volledig klassieke ZF, zoals IZF (Friedman 1973a). Er zijn ook systemen met middelmatige sterkte, zoals CZF. De kracht van de laatste theorie is in feite gelijk aan die van een theorie van één inductieve definitie die bekend staat als ID (_ 1). Het feit dat CZF dezelfde sterkte heeft als ID (_ 1) wordt genomen om de (gegeneraliseerde) predicativiteit van de verzamelingenleer te bevestigen en om te bewijzen dat het de limiet van predicativiteit overschrijdt, gegeven de natuurlijke getallen, aangezien ID (_ 1) 's bewijstheoretische ordinal ligt ruim boven (Gamma_0).sommige van de geanalyseerde systemen blijken even zwak als rekenen, zoals bijvoorbeeld Friedmans systeem B (Friedman 1977); andere systemen zijn even sterk als volledig klassieke ZF, zoals IZF (Friedman 1973a). Er zijn ook systemen met middelmatige sterkte, zoals CZF. De kracht van de laatste theorie is in feite gelijk aan die van een theorie van één inductieve definitie die bekend staat als ID (_ 1). Het feit dat CZF dezelfde sterkte heeft als ID (_ 1) wordt genomen om de (gegeneraliseerde) predicativiteit van de verzamelingenleer te bevestigen en om te bewijzen dat het de limiet van predicativiteit overschrijdt, gegeven de natuurlijke getallen, aangezien ID (_ 1) 's bewijstheoretische ordinal ligt ruim boven (Gamma_0).sommige van de geanalyseerde systemen blijken even zwak als rekenen, zoals bijvoorbeeld Friedmans systeem B (Friedman 1977); andere systemen zijn even sterk als volledig klassieke ZF, zoals IZF (Friedman 1973a). Er zijn ook systemen met gemiddelde sterkte, zoals CZF. De kracht van de laatste theorie is in feite gelijk aan die van een theorie van één inductieve definitie die bekend staat als ID (_ 1). Het feit dat CZF dezelfde sterkte heeft als ID (_ 1) wordt genomen om de (gegeneraliseerde) predicativiteit van de verzamelingenleer te bevestigen en om te bewijzen dat het de limiet van predicativiteit overschrijdt, gegeven de natuurlijke getallen, aangezien ID (_ 1) 's bewijstheoretische ordinal ligt ruim boven (Gamma_0). Er zijn ook systemen met gemiddelde sterkte, zoals CZF. De kracht van de laatste theorie is in feite gelijk aan die van een theorie van één inductieve definitie die bekend staat als ID (_ 1). Het feit dat CZF dezelfde sterkte heeft als ID (_ 1) wordt genomen om de (gegeneraliseerde) predicativiteit van de verzamelingenleer te bevestigen en om te bewijzen dat het de limiet van predicativiteit overschrijdt, gegeven de natuurlijke getallen, aangezien ID (_ 1) 's bewijstheoretische ordinal ligt ruim boven (Gamma_0). Er zijn ook systemen met middelmatige sterkte, zoals CZF. De kracht van de laatste theorie is in feite gelijk aan die van een theorie van één inductieve definitie die bekend staat als ID (_ 1). Het feit dat CZF dezelfde sterkte heeft als ID (_ 1) wordt genomen om de (gegeneraliseerde) predicativiteit van de verzamelingenleer te bevestigen en om te bewijzen dat het de limiet van predicativiteit overschrijdt, gegeven de natuurlijke getallen, aangezien ID (_ 1) 's bewijstheoretische ordinal ligt ruim boven (Gamma_0).

Als laatste opmerking: hoewel de kracht van CZF ver onder die van rekenkunde van de tweede orde ligt, geeft de simpele toevoeging van uitgesloten midden aan CZF ons (volledige) ZF. Dit moet worden vergeleken met IZF, dat al de kracht van ZF heeft (Friedman 1973a). De beperkte theoretische sterkte van CZF vergeleken met IZF wordt vaak beschouwd als een van de belangrijkste voordelen van constructief boven intuïtionistische verzamelingenleer. In zekere zin lijkt CZF het meeste uit haar gebruik van intuïtionistische logica te halen, aangezien het een notie van (gegeneraliseerde) predicatieve set kenmerkt die voldoende sterk is voor de ontwikkeling van veel constructieve wiskunde, maar ook zwak genoeg om impredicativiteit te voorkomen. Interessant is dat wanneer een aantal grote axioma's zijn toegevoegd aan de constructieve verzamelingenleer, een soortgelijk patroon is ontstaan,aangezien de kracht van de resulterende theorie ver onder die van de corresponderende klassieke theorie ligt.

5.2 Grote sets in constructieve en intuïtionistische ZF

Een prominent onderzoeksgebied in de klassieke verzamelingenleer is dat van de grote kardinalen (zie de vermelding over verzamelingenleer). In constructieve contexten zijn de ordinalen niet lineair geordend. (Voor het begrip constructieve ordinaal en een korte bespreking van de eigenschappen ervan, zie het aanvullende document over: Set-theoretic Principles Incompatible with Intuitionistic Logic.) Dientengevolge spelen kardinale getallen niet dezelfde rol als in de klassieke setting.

Desalniettemin kan men de impact van "reflectieprincipes" van de vorm van grote verzameling axioma's bestuderen. Men kan bijvoorbeeld aan constructieve en intuïtionistische set-theorieën een axioma toevoegen dat het bestaan van ontoegankelijke sets beweert. ^[2] De toevoeging van grote set axioma's aan intuïtionistische ZF werd voor het eerst voorgesteld door Friedman en Scedrov (Friedman en Scedrov 1984). Een van hun doelen was om licht te werpen op de corresponderende klassieke noties; een andere was het bestuderen van de impact van deze principes op de metatheoretische eigenschappen van de oorspronkelijke verzamelingenleer. Friedman en Scedrov hebben bijvoorbeeld aangetoond dat de toevoeging van grote set axioma's de geldigheid van de disjunctie en numerieke existentie-eigenschappen voor IZF niet in gevaar brengt.

In het kader van de constructieve verzamelingenleer zijn door Aczel grote verzamelingen geïntroduceerd in de vorm van zogenaamde reguliere verzamelingen om inductieve definities van verzamelingen mogelijk te maken (Aczel 1986). Rathjen en Crosilla hebben ontoegankelijke sets (Rathjen al. 1998; Crosilla en Rathjen 2001) en Mahlo-sets (Rathjen 2003a) overwogen. Desalniettemin zou bezwaar kunnen worden gemaakt tegen uitbreidingen van de constructieve verzamelingenleer door grote verzameling axioma's. In de klassieke verzamelingenleer kunnen grote kardinalen worden gezien als een incarnatie van hogere oneindigheid. Hoe rechtvaardigen we deze principes constructief? De constructieve rechtvaardiging van deze noties berust opnieuw op de typetheoretische interpretatie. De toevoeging van deze principes komt in feite overeen met die van universa en (W) - types binnen de constructieve typetheorie. De rechtvaardiging van uitbreidingen door grote sets hangt dus samen met de kwestie van de grenzen van de Martin-Löf-typetheorie (Rathjen 2005). We merken ook op dat de toevoeging van onbereikbare set-axioma's aan een zwak subsysteem van CZF (zonder set-inductie) een theorie van kracht oplevert (Gamma_0), het ordinaal dat door Feferman en Schütte is uitgekozen als de limiet van predicativiteit gezien de natuurlijke nummers (Crosilla en Rathjen 2001; zie ook paragraaf 1.3). Dit getuigt van het feit dat we door te werken in een constructieve, predicatieve context, traditioneel sterke set-theoretische noties kunnen temmen.het ordinaal door Feferman en Schütte aangewezen als de limiet van predicativiteit gezien de natuurlijke getallen (Crosilla en Rathjen 2001; zie ook paragraaf 1.3). Dit getuigt van het feit dat we door te werken in een constructieve, predicatieve context, traditioneel sterke set-theoretische noties kunnen temmen.het ordinaal door Feferman en Schütte aangewezen als de limiet van predicativiteit gezien de natuurlijke getallen (Crosilla en Rathjen 2001; zie ook paragraaf 1.3). Dit getuigt van het feit dat we door te werken in een constructieve, predicatieve context, traditioneel sterke set-theoretische noties kunnen temmen.

De verzamelingenleer van Crosilla en Rathjen met ontoegankelijke verzamelingen (maar zonder inductie van verzamelingen) is theoretisch nogal zwak, maar wiskundig behoorlijk expressief. Het is bijvoorbeeld gebruikt om te verifiëren dat de toevoeging van Voevodsky's Univalence Axiom aan de Martin-Löf-typetheorie niet leidt tot impredicativiteit (Rathjen 2017). Het axioma van Univalence werd door Voevodsky geïntroduceerd als onderdeel van zijn Univalent Foundations-programma (Voevodsky 2015). (Voor Univalent Foundations, zie de vermeldingen over typetheorie en over intuïtionistische typetheorie). Voevodsky gaf een model van constructieve typetheorie met de Univalence Axiom die is gebaseerd op Kan simplicial sets (zie Kapulkin & Lumsdaine 2012, Other Internet Resources). Het eenvoudige model van constructieve typetheorie met univalentie ontwikkeld in het bovenstaande artikel wordt uitgevoerd binnen een uitbreiding van ZFC met ontoegankelijke kardinalen. Dit leidde tot de vraag of men een constructiever model van deze typetheorie kon geven, en in het bijzonder of de typetheorie predicatief is. Bezem, Coquand en Huber (2014) hebben onlangs een model van deze typetheorie in kubieke verzamelingen voorgesteld dat computationeel is en 'kan worden uitgedrukt in een constructieve metalogie'. Rathjen (2017) heeft geverifieerd dat dit nieuwe model kan worden gecodificeerd in een geschikte uitbreiding van CZF door ontoegankelijke sets die veel zwakker zijn dan de klassieke verzamelingenleer met ontoegankelijke kardinalen. In feite blijkt dat als we een relatief zwakke typetheorie als uitgangspunt nemen, dwz een zonder W-typen, en deze uitbreiden met de Univalence Axiom,de resulterende theorie heeft bewijstheoretische kracht (Gamma_0), de ordinale wordt gewoonlijk beschouwd als de limiet van predicativiteit gegeven de natuurlijke getallen (Rathjen 2017). Om dit aan te tonen, bewijst men dat het kubische model van Bezem, Coquand en Huber kan worden uitgevoerd in een uitbreiding van het systeem dat in Crosilla en Rathjen (2001) is geïntroduceerd door (begrensde) Relativized Dependent Choice. Uit (Crosilla en Rathjen 2001) en (Rathjen 2003) volgt dat deze laatste een theoretische ordinale (Gamma_0) heeft. Coquand en Huber kunnen worden uitgevoerd in een uitbreiding van het systeem dat in Crosilla en Rathjen (2001) is geïntroduceerd door (bounded) Relativized Dependent Choice. Uit (Crosilla en Rathjen 2001) en (Rathjen 2003) volgt dat deze laatste een theoretische ordinale (Gamma_0) heeft. Coquand en Huber kunnen worden uitgevoerd in een uitbreiding van het systeem dat in Crosilla en Rathjen (2001) is geïntroduceerd door (bounded) Relativized Dependent Choice. Uit (Crosilla en Rathjen 2001) en (Rathjen 2003) volgt dat deze laatste een theoretische ordinale (Gamma_0) heeft.

5.3 Metamathematische eigenschappen van constructieve en intuïtionistische ZF- en semantische technieken

Een verscheidenheid aan interpretaties voor intuïtionistische logica is uitgebreid tot intuïtionistische en constructieve set-theorieën, zoals realiseerbaarheid, Kripke-modellen en Heyting-gewaardeerde semantiek. Al deze technieken zijn toegepast om metamathematische resultaten te verkrijgen over de gestelde theorieën.

5.3.1 Disjunctie en existentie-eigenschappen van constructieve en intuïtionistische ZF

Sommige intuïtionistische verzamelingenleerstellingen voldoen aan bepaalde 'kenmerkende' metamathematische eigenschappen, zoals de disjunctie en de existentie-eigenschappen. Er kan ook worden aangetoond dat ze consistent zijn met de toevoeging van principes die verder gaan dan wat we doorgaans als constructief beschouwen. Hiertoe behoren bijvoorbeeld de scriptie van de kerk en het principe van Markov. Voor een beschrijving van deze principes in de context van intuïtionistische logica, kan de lezer de secties 4.2 en 5.2 van de vermelding over intuïtionistische logica of Troelstra en van Dalen's boek Constructivism in Mathematics (Troelstra en van Dalen 1988) raadplegen.

Hier herinneren we ons de eigenschappen van disjunctie en bestaan, geformuleerd voor een verzamelingenleer (T). De informele motivatie voor de disjunctie en de eigenschappen van het bestaan is gebaseerd op ons begrip van de constructieve bewijzen van disjunctieve en existentiële verklaringen (respectievelijk). In feite lijkt het redelijk om te verwachten dat als we constructief een disjunctie (phi \ vee \ psi) bewijzen, we ook (phi) of (psi) moeten kunnen bewijzen. Evenzo, als we een existentiële verklaring bewijzen, dan moeten we kunnen bewijzen dat een getuige van die verklaring definieerbaar is binnen onze theorie.

Hoewel dergelijke eigenschappen vrij natuurlijk lijken en redelijk eenvoudig vast te stellen zijn voor rekenkundige theorieën, blijken ze aanzienlijke technische uitdagingen te vormen in het geval van verzamelingen theorieën, vanwege hun transfinite hiërarchieën van verzamelingen en de extensie axioma. In feite blijken prominente constructieve en intuïtionistische verzamelingenleer theorieën over het bestaan niet te bezitten, zoals besproken in de volgende paragraaf.

Laat (T) een theorie zijn waarvan de taal, (L (T)), de taal van de verzamelingenleer omvat. Bovendien zullen we voor de eenvoud aannemen dat (L (T)) een constante (omega) heeft die de verzameling von Neumann natuurlijke getallen aanduidt en voor elke (n) een constante (c_n) die aangeeft het (n) - het element van (omega).

Een theorie (T) heeft de disjunctie-eigenschap (DP) als (T) bewijst ((phi \ vee \ psi)) voor zinnen (phi) en (psi) van (L (T)), dan bewijst (T) (phi) of (T) bewijst (psi).

De existentie-eigenschap heeft twee verschillende versies in de context van de verzamelingenleer: de numerieke existentie-eigenschap (NEP) en de existentie-eigenschap (EP). Laat (theta (x)) een formule zijn met maximaal (x) gratis. We zeggen dat:

(1) (T) heeft de NEP als wanneer (T) bewijst (bestaat x \ in \ omega \ theta (x)), dan, voor een natuurlijk getal (n, T) bewijst (theta (c_n)).

(2) (T) heeft de EP als wanneer (T) bewijst (bestaat x \ theta) (x), dan is er een formule (phi (x)) met exact (x) gratis, zodat (T) bewijst (bestaat! x (phi (x) wedge \ theta (x))).

Aangezien realiseerbaarheidstechnieken cruciaal zijn gebleken bij onderzoek naar het bestaan en de disjunctie-eigenschappen van constructieve en intuïtionistische verzamelingenleer, bespreken we de resultaten van deze onderzoeken in de volgende sectie.

5.3.2 Realiseerbaarheid

Realiseerbaarheid was een van de eerste en belangrijkste instrumenten in het onderzoek naar set-theorieën gebaseerd op intuïtionistische logica, te beginnen met de vroege bijdragen van Friedman en Myhill (Friedman 1973, Myhill 1973). De realiseerbaarheidssemantiek voor intuïtionistisch rekenen werd voor het eerst voorgesteld door Kleene (Kleene 1945) en werd door Kreisel en Troelstra (Kreisel en Troelstra 1970) uitgebreid tot een hogere rang Heyting-rekenkunde. Voor de definitie van realiseerbaarheid voor rekenen zie sectie 5.2 van de vermelding over intuïtionistische logica. Een realiseerbaarheid vergelijkbaar met Kreisel en Troelstra werd door Friedman toegepast op systemen van hogere orde rekenkunde (Friedman 1973). Myhill introduceerde een variant van deze realiseerbaarheid die lijkt op Kleene's schuine streep (Myhill 1973; Kleene 1962, 1963). Hij bewees daarmee dat een versie van IZF met vervanging in plaats van verzameling (genaamd IZF (_ {Rep})) de DP, de NEP en de EP heeft. Deze resultaten werden verder uitgebreid in (Myhill 1975; Friedman en Scedrov 1983). Terwijl Friedman en Myhill realisatiemodellen voor extensieve set-theorieën gaven, ontwikkelde Beeson een idee van realiseerbaarheid voor niet-extensieve set-theorieën. Vervolgens bestudeerde hij metatheoretische eigenschappen van de extensieve verzamelingen theorieën via een interpretatie in hun niet-dimensionale tegenhangers. Hiermee bewees hij dat IZF (met collectie) de DP en NEP heeft (Beeson 1985). Vervolgens introduceerde McCarty de realiseerbaarheid voor IZF rechtstreeks voor extensieve verzamelingenleer (McCarty 1984; 1986). De realiseerbaarheidssemantiek voor varianten van CZF is bijvoorbeeld overwogen in (Crosilla en Rathjen 2001; Rathjen 2006a). De realiseerbaarheid in het laatste artikel is geïnspireerd door McCarty's en heeft als belangrijk kenmerk dat het, zoals McCarty's voor IZF, een zelf-validerende semantiek is voor CZF (dat wil zeggen, dit idee van realiseerbaarheid kan worden geformaliseerd in CZF en elke stelling van CZF is aantoonbaar gerealiseerd in CZF). Rathjen heeft gebruik gemaakt van dit idee van realiseerbaarheid om aan te tonen dat CZF (en een aantal uitbreidingen daarvan) de DP en de NEP hebben (Rathjen 2005b).

Een ander soort realiseerbaarheid dat zeer nuttig is gebleken, is Lifschitz-realiseerbaarheid. Lifschitz (1979) introduceerde een wijziging van Kleene's realiseerbaarheid voor Heyting-rekenkunde, die de bijzonderheid heeft een zwakke vorm van Church's Thesis (CT) te valideren met een unieke conditie, maar niet CT zelf. De realiseerbaarheid van Lifschitz werd door van Oosten (1990) uitgebreid tot rekenkunde van de tweede orde. Het werd vervolgens uitgebreid tot volledige IZF door Cheng en Rathjen, die het gebruikten om een aantal onafhankelijkheidsresultaten te verkrijgen, en om het zogenaamde Lesser Limited Principle of Omniscience (LLPO) te valideren (zie voor LLPO de vermelding over constructieve wiskunde).

De vraag welke verzamelingen theorieën aan het bestaanseigendom voldoen, bleek bijzonder moeilijk op te lossen. (Friedman en Scedrov 1985) gebruikten Kripke-modellen om te laten zien dat IZF (dat wil zeggen, het systeem met verzameling) niet de EP heeft, terwijl zoals hierboven vermeld, het systeem IZF (_ {Rep}) (dat vervangen heeft) van collectie) heeft het EP. Dit bracht Beeson ertoe de vraag te stellen [Beeson 1985, IX]:

Heeft een redelijke verzamelingenleer met collectie het bestaanseigenschap?

Een eerste antwoord op de vraag van Beeson kwam met (Rathjen 2012), waar de auteur het idee van een zwak bestaanseigenschap introduceerde: de focus ligt hier op het vinden van een aantoonbaar definieerbare reeks getuigen voor elke existentiële stelling. Vervolgens introduceerde hij een vorm van realiseerbaarheid op basis van algemeen ingestelde recursieve functies, waarbij een realizer voor een existentiële verklaring een set getuigen levert voor de existentiële kwantificeerder, in plaats van een enkele getuige. Rathjen combineerde dit idee van realiseerbaarheid met waarheid om op te leveren dat een aantal theorieën met collectie het zwakke bestaan bezitten (terwijl IZF dat niet doet). Onder hen in het bijzonder de theorie CZF zonder subsetverzameling plus Myhill's machtsverheffen axioma, CZF (_ {Exp}). Rathjen beweerde zelfs dat door deze resultaten te combineren met verder werk dat hij had uitgevoerd,hij kon aantonen dat CZF (_ {Exp}) (en een aantal andere theorieën) de eigenschap exist hebben. Opvallend is dat deze theorieën met collectie zijn geformuleerd; bijgevolg kan het falen van de bestaande eigenschap in het geval van IZF niet alleen worden toegeschreven aan collectie, maar aan het samenspel tussen deze regeling en onbeperkte scheiding.

Wat betreft de prominente vraag of CZF zelf het bestaan bezit, is dit door Swan (2014) negatief opgelost. Daar maakte de auteur gebruik van drie goed uitgedachte realisatiemodellen en inbedding daartussen, om te laten zien dat zelfs het zwakke bestaansgoed voor CZF faalt. Hiermee liet hij ook zien dat het inzamelingsschema van CZF de boosdoener is. Zoals duidelijk benadrukt in (Swan 2014), wijst het feit dat CZF geen EP heeft op enige zwakte in CZF als constructieve theorie. Zelfs als Swan in wezen bewees dat CZF het bestaan beweert van wiskundige objecten die ze niet kan construeren, heeft CZF toch natuurlijke interpretaties waarin deze objecten kunnen worden geconstrueerd, zoals bijvoorbeeld Aczel's interpretatie in typetheorie (Aczel 1978).

Voor een overzicht van resultaten in intuïtionistische verzamelingenleer, zie (Beeson 1985, hoofdstuk IX). Zie voor de overeenkomstige ontwikkelingen in CZF (Rathjen 2005b, 2006, 2012) en (Swan 2014).

5.3.3 Kripke-modellen en Heyting-gewaardeerde semantiek

Kripke-modellen voor intuïtionistische set-theorieën zijn gebruikt in (Friedman en Scedrov 1985) om aan te tonen dat IZF de EP niet heeft (en in combinatie met de resultaten in (Myhill 1973) hebben we dat IZF (_ {Rep}) wel niet bewijzen IZF). Meer recentelijk zijn Kripke-modellen toegepast om de relatie tussen de constructieve substituten van het vermogensset-axioma te verduidelijken: Myhill's machtsverheffing-axioma en Aczel's subset-verzamelingsschema. Het is duidelijk dat het axioma van de vermogensset beide principes impliceert, en dat verzameling van subgroepen machtsverheffing impliceert. Aan de andere kant impliceert elk van de laatste twee principes geen machtsset, aangezien de theorie CZF met krachtsets in plaats van verzameling subsets veel sterker is dan CZF en CZF (_ {Exp}) (Rathjen 2012b). In feite hebben CZF en CZF (_ {Exp}) dezelfde bewijstheoretische kracht (Griffor en Rathjen 1994);daarom moest men, om de relatie tussen subsetverzameling en machtsverheffing in constructieve verzamelingenleer te onderzoeken, andere instrumenten ontwikkelen dan bewijstheoretische methoden. Lubarsky (2005) gebruikte Kripke-modellen om aan te tonen dat het exponentiatie-axioma van Myhill niet de verzameling van Aczel's subset impliceert (op basis van CZF minus subsetcollectie plus volledige scheiding). In (Lubarsky en Rathjen 2007) pasten de auteurs de techniek van Kripke-modellen toe om te laten zien dat ook de gevolgen van de theorieën CZF en CZF (_ {Exp}) verschillend zijn. Aczel en Rathjen (2001) hadden aangetoond dat de klasse van Dedekind-reële getallen een set vormt in CZF, door gebruik te maken van een subsetverzameling. Lubarsky en Rathjen (2007) toonden aan dat CZF (_ {Exp}) niet volstaat om dezelfde bewering te bewijzen. Voor verdere toepassingen van Kripke-modellen om cruciale constructieve begrippen te scheiden, zie bv(Diener en Lubarsky 2013).

Heyting-gewaardeerde semantiek voor intuïtionistische verzamelingenleer werden door Grayson (Grayson 1979) verkregen als tegenhanger van Booleaanse modellen voor klassieke verzamelingenleer. Ze zijn vooral veralgemeend via categorische semantiek (voor een inleiding zie MacLane en Moerdijk 1992). Heyting-gewaardeerde semantiek heeft toepassing gevonden op onafhankelijkheidsresultaten in (Scedrov 1981; 1982). In (Gambino 2006) is een constructieve behandeling gegeven. Zie ook (Lubarsky 2009). Zie ook Ziegler (2012) voor een veralgemening van realiseerbaarheid en Heyting-modellen voor constructieve verzamelingenleer.

5.3.4 Categorische modellen van constructieve en intuïtionistische verzamelingenleer

Categorische modellen van constructieve en intuïtionistische verzamelingenleer zijn in de loop der jaren tot bloei gekomen. Hierbij spelen de begrippen topos en schoof een essentiële rol (zie bv. Fourman 1980 en Fourman en Scott 1980). Voor een overzicht van de belangrijkste concepten, zie de vermelding over de categorietheorie en de daarin verstrekte referenties (zie met name de aanvulling Programmatic Reading Guide). Voor recente ontwikkelingen die meer specifiek betrekking hebben op constructieve verzamelingenleer, zie bv. (Simpson 2005) en (Awodey 2008), evenals de webpagina: algebraïsche verzamelingenleer.

5.4 Varianten van constructieve en intuïtionistische set-theorieën: set-theorieën met Urelements en niet-extensieve set-theorieën

Soms zijn systemen van intuïtionistische en constructieve verzamelingenleer gepresenteerd met de natuurlijke getallen als een apart soort urelements, dat wil zeggen primitieve objecten zonder elementen (Friedman 1977; Myhill 1975; Beeson 1985). Constructief is dit een natuurlijke keuze die in overeenstemming is met de ideeën van bijvoorbeeld Bishop (1967) (onder andere). In Bishop's monografie worden de natuurlijke getallen beschouwd als een fundamenteel concept waarop alle andere wiskundige concepten zijn gebaseerd. Vanuit technisch oogpunt, als de natuurlijke getallen als primitief worden beschouwd en onderscheiden van hun set-theoretische representaties, neemt het axioma van oneindigheid de vorm aan: "er is een set van natuurlijke getallen (als urelements)". Een meer algemene vorm van urelements in constructieve set-theorieën is overwogen in (Cantini en Crosilla 2008). Hier wordt een variant van de constructieve verzamelingenleer voorgesteld die een intensief en gedeeltelijk bedieningsconcept combineert met CZF's extensieve begrip van verzameling (zie ook Cantini en Crosilla 2010).

Het axioma van extensie is een gemeenschappelijk kenmerk van alle tot dusver besproken systemen. In een context waarin de computationele inhoud van een verklaring als cruciaal wordt beschouwd, is een intensietheorie wellicht geschikter. Constructieve typetheorie en expliciete wiskunde omvatten bijvoorbeeld beide een vorm van intensionaliteit. In de literatuur zijn intuïtionistische set-theorieën zonder extensie onderzocht (Friedman 1973a, Beeson 1985). Hun motivatie was echter niet computationeel maar technisch van aard, vanwege de moeilijkheden die extensionaliteit met zich meebrengt bij het bestuderen van metamathematische eigenschappen van intuïtionistische verzamelingenleer.

Bibliografie

• Aczel, P., 1978, "The Type Theoretic Interpretation of Constructive Set Theory", in Logic Colloquium '77, A. MacIntyre, L. Pacholski, J. Paris (red.), Amsterdam en New York: Noord-Holland, pp 55–66.
• –––, 1982, “The type theoretic interpretation of constructive set theory: choice principles”, in The LEJ Brouwer Centenary Symposium, AS Troelstra en D. van Dalen (red.), Amsterdam en New York: Noord-Holland, pp. 1–40.
• –––, 1986, "The type theoretic interpretation of constructive set theory: inductive definitions", in Logic, Methodology, and Philosophy of Science VII, RB Marcus, GJ Dorn en GJW Dorn (red.), Amsterdam en New York: Noord-Holland, pp. 17–49.
• –––, 1988, Niet-gegronde sets (CSLI-toelichting 14), Stanford: CSLI.
• Aczel, P., en Rathjen, M., 2001, "Notes on Constructive Set Theory", Report No. 40, 2000/2001, Djursholm: Institut Mittag-Leffler, [online beschikbaar]
• Aczel, P., en Gambino, N., 2002, "Collectieprincipes in afhankelijke typetheorie", in Typen voor bewijzen en programma's (Aantekeningen in informatica 2277), P. Callaghan, Z. Luo, J. McKinna, en R. Pollack (redactie), Berlijn: Springer, pp. 1–23.
• Awodey, S., 2008, 'A Brief Introduction to Algebraic Set Theory', The Bulletin of Symbolic, 14 (3): 281–298.
• Barwise, J., en Moss, L., 1996, Vicious Circles (CSLI Lecture Notes 60), Stanford: CSLI.
• Beeson, M., 1985, Foundations of Constructive Mathematics, Berlin: Springer.
• Bezem, M., Thierry, C. en Huber, S., 2014, "A model of type theory in cubical sets", in 19e International Conference on Types for Proofs and Programs (TYPES 2013), Matthes, R. en Schubert, A. (redactie), Dagstuhl: Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, pp. 107–128.
• Bishop, E., 1967, Foundations of Constructive Analysis, New York: McGraw-Hill.
• –––, 1970, "Wiskunde als numerieke taal", in Intuitionism and Proof Theory, A. Kino, J. Myhill, en RE Vesley (red.), Amsterdam: Noord-Holland, pp. 53–71.
• Bishop, E., en Bridges, D., 1985, Constructive Analysis, Berlin en Heidelberg: Springer.
• Bridges, D., en Richman, F., 1987, Varieties of Constructive Mathematics, Cambridge: Cambridge University Press.
• Buchholz, W., Feferman, S., Pohlers, W. en Sieg, W., 1981, Iterated Inductive Definitions and Subsystems of Analysis, Berlin: Springer.
• Cantini, A., en Crosilla, L., 2008, "Constructive set theory with operations", in A. Andretta, K. Kearnes, D. Zambella (red.), Logic Colloquium 2004 (Lezingen in Logic 29), Cambridge: Cambridge University Press, blz. 47-83.
• Cantini, A., en Crosilla, L., 2010, “Explicit operational set theory”, in R. Schindler (red.), Ways of Proof Theory, Frankfurt: Ontos, pp. 199–240.
• Chen, R.-M. en Rathjen, M., 2012, "Lifschitz Realizability for Intuitionistic Zermelo-Fraenkel Set Theory", Archive for Mathematical Logic, 51: 789–818.
• Crosilla, L., 2017, 'Predicativity and Feferman', in G. Jäger en W. Sieg (red.), Feferman on Foundations (Outstanding Contributions to Logic: Volume 13), Cham: Springer, pp 423–447.
• Crosilla, L., en Rathjen, M., 2001, "Ontoegankelijke verzamelde axioma's hebben mogelijk weinig consistentie", 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., en Lubarsky, R., 2013, "Separating the Fan Theorem and Its Verzwakkingen", in SN Artemov en A. Nerode (red.), Proceedings of LFCS '13 (Lecture Notes in Computer Science 7734), Dordrecht: Springer, pp. 280–295.
• Dummett, M., 2000, Elements of Intuitionism, tweede editie, (Oxford Logic Guides 39), New York: Oxford University Press.
• Feferman, S., 1964, "Systemen voor predicatieve analyse", Journal of Symbolic Logic, 29: 1–30.
• –––, 1975, "Een taal en axioma's voor expliciete wiskunde", in Algebra and Logic (Lecture Notes in Mathematics 450), J. Crossley (red.), Berlin: Springer, pp. 87–139.
• –––, 1988, “Weyl betuigde: Das Kontinuum zeventig jaar later”, in Temi e prospettive della logica e della scienza contemporananee, C. Cellucci en G. Sambin (eds), pp. 59–93.
• –––, 1993: “Wat berust op wat? De proof-theoretische analyse van wiskunde”, in Philosophy of Mathematics, Part I, Proceedings of the 15th International Wittgenstein Symposium. Wenen: Verlag Hölder-Pichler-Tempsky.
• –––, 2005, "Predicativity", in Handbook of the Philosophy of Mathematics and Logic, S. Shapiro (red.), Oxford: Oxford University Press.
• Fletcher, P., 2007, 'Infinity', in Handbook of the Philosophy of Logic, D. Jacquette, (ed.), Amsterdam: Elsevier, pp. 523–585.
• Fourman, MP, 1980, "Schoofmodellen voor verzamelingenleer", Journal of Pure Applied Algebra, 19: 91–101.
• Fourman, MP en Scott, DS, 1980, "Sheaves and logic", in Applications of Sheaves (Aantekeningen bij wiskunde 753), MP Fourman, CJ Mulvey en DS Scott (red.), Berlin: Springer, pp. 302– 401.
• Friedman, H., 1973, "Enkele toepassingen van Kleene's methoden voor intuïtionistische systemen", in Proceedings of the 1971 Cambridge Summer School in Mathematical Logic (Lecture Notes in Mathematics 337), ARD Mathias en H. Rogers (red.), Berlijn: Springer, pp. 113–170.
• –––, 1973a, “De consistentie van klassieke verzamelingenleer ten opzichte van een verzamelingenleer met intuïtionistische logica”, Journal of Symbolic Logic, 38: 315–319.
• –––, 1977, “Set-theoretische grondslagen voor constructieve analyse”, Annals of Mathematics, 105: 1–28.
• Friedman, H., Scedrov, A., 1983, "Stel bestaanseigenschappen in voor intuïtionistische theorieën met afhankelijke keuze", Annals of Pure and Applied Logic, 25: 129–140.
• –––, 1984, "Grote sets in intuïtionistische verzamelingenleer", Annals of Pure en Applied Logic, 27: 1–24.
• –––, 1985, "Het gebrek aan definieerbare getuigen en aantoonbaar recursieve functies in de intuïtionistische verzamelingenleer", Advances in Mathematics, 57: 1–13.
• Gambino, N., 2006, "Heyting-gewaardeerde interpretaties voor constructieve verzamelingenleer", Annals of Pure and Applied Logic, 137: 164–188.
• Goodman, ND, en Myhill, J., 1972, "The formalization of Bishop's constructive mathematics", in Toposes, Algebraic Geometry and Logic (Lecture Notes in Mathematics 274), FW Lawvere (red.), Berlin: Springer, pp. 83 –96.
• Goodman, ND, en Myhill, J., 1978, "Keuze impliceert uitgesloten midden", Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 24 (5): 461.
• Grayson, RJ, 1979, "Heyting-gewaardeerde modellen voor intuïtionistische verzamelingenleer", in Applications of Sheaves (Lecture Notes in Mathematics 753), MP Fourman, CJ Mulvey en DS Scott (red.), Berlin: Springer, pp. 402 –414.
• Griffor, E., en Rathjen, M., 1994, "The strength of some Martin-Löf type theories", Archive Mathematical Logic, 33: 347–385.
• van Heijenoort, J., 1967, From Frege to Gödel. A Source Book in Mathematical Logic 1879–1931, Cambridge: Harvard Univ. Druk op.
• Kleene, SC, 1945, "Over de interpretatie van intuïtionistische getaltheorie", Journal of Symbolic Logic, 10: 109–124.
• –––, 1962, “Disjunctie en bestaan impliciet in elementaire intuïtionistische formalismen”, Journal of Symbolic Logic, 27: 11–18.
• –––, 1963, “An addendum”, Journal of Symbolic Logic, 28: 154–156.
• Kreisel, G., 1958, "Ordinal logics and the characterization of informal concepts of proof", Proceedings of the International Congress of Mathematicians (14–21 augustus 1958), Paris: Gauthier-Villars, pp. 289–299.
• Kreisel, G., en Troelstra, A., S., 1970, "Formele systemen voor enkele takken van intuïtionistische analyse", Annals of Mathematical Logic, 1: 229–387.
• Lifschitz, V., 1979, "CT (_ 0) is sterker dan CT (_ 0)!", Proceedings of the American Mathematical Society, 73 (1): 101–106.
• Lindström, I., 1989, "Een constructie van niet-gefundeerde verzamelingen binnen de Martin-Löf-typetheorie", Journal of Symbolic Logic, 54: 57–64.
• Lipton, J., 1995, "Realiseerbaarheid, verzamelingenleer en term-extractie", in The Curry-Howard isomorfisme (Cahiers du Centre de Logique de l'Universite Catholique de Louvain 8), Louvain-la-Neuve: Academia, pp. 257 –364.
• Lorenzen, P., en Myhill, J., 1959, "Constructieve definitie van bepaalde analytische reeksen getallen", Journal of Symbolic Logic, 24: 37–49.
• Lubarsky, R., 2005, "Independence results around constructive ZF", Annals of Pure and Applied Logic, 132: 209–225.
• –––, 2006, “CZF en rekenkunde van de tweede orde”, Annals of Pure en Applied Logic, 141: 29–34.
• –––, 2009, "Topological Forcing Semantics with Settling", in SN Artemov en A. Nerode (eds.), Proceedings of LFCS '09 (Lecture Notes in Computer Science 5407), Dordrecht: Springer, pp. 309–322.
• Lubarsky, R., en Rathjen, M., 2007, "On the Constructive Dedekind Reals", in SN Artemov en A. Nerode (eds.), Proceedings of LFCS 2007 (Lecture Notes in Computer Science 4514), Dordrecht: Springer, blz. 349-362.
• MacLane, S., en Moerdijk, I., 1992, "Sheaves in Geometry and Logic", New York: Springer.
• Maietti, ME, Sambin, G., 2005, "Toward a Minimalist Foundation for Constructive Mathematics", van sets en types tot topologie en analyse: naar praktische grondslagen voor constructieve wiskunde (Oxford Logic Guides 48), L. Crosilla en P Schuster (red.), Oxford: Oxford University Press.
• Maietti, ME, 2009, "Een minimalistische basis op twee niveaus voor constructieve wiskunde", Annals of Pure en Applied Logic, 160 (3): 319–354.
• Martin-Löf, P., 1975, "An intuitionistic theory of types: predicative part", in HE Rose en J. Sheperdson (red.), Logic Colloquium '73, Amsterdam: Noord-Holland, pp. 73–118.
• –––, 1984, "Intuitionistic Type Theory", Napels: Bibliopolis.
• McCarty, DC, 1984, "Realisability and Recursive Mathematics", D. Phil. Dissertatie, filosofie, Oxford University.
• –––, 1986, “Realizability and recursive set theory”, Annals of Pure and Applied Logic, 32: 153–183.
• Myhill, J., 1973, "Some properties of Intuitionistic Zermelo-Fraenkel set theory", in Proceedings of the 1971 Cambridge Summer School in Mathematical Logic (Lecture Notes in Mathematics 337), ARD Mathias, en H. Rogers (red.), Berlijn: Springer, pp. 206–231.
• –––, 1975, “Constructive set theory”, Journal of Symbolic Logic, 40: 347–382.
• van Oosten, J., 1990, "Lifschitz's Realizability", The Journal of Symbolic Logic, 55: 805–821.
• Powell, W., 1975, "Uitbreiding van de negatieve interpretatie van Gödel tot ZF", Journal of Symbolic Logic, 40: 221–229.
• Rathjen, M., Griffor, E., en Palmgren, E., 1998, "Inaccessibility in constructive set theory and type theory", Annals of Pure and Applied Logic, 94: 181-200.
• Rathjen, M., 1999, "The realm of ordinal analysis", in Sets and Proofs (London Mathematical Society Lecture Notes 258), Cambridge: Cambridge University Press, pp. 219–279.
• –––, 2003, "The anti-foundation axiom in constructive set theories", in Games, logic and constructive sets (CSLI Lecture Notes 161), Stanford: CSLI Publication, pp. 87–108.
• –––, 2003a, “Realiseren van Mahlo verzamelingenleer in typetheorie”, Archief voor wiskundige logica, 42: 89–101.
• –––, 2004, “Predicativity, circularity, and anti-foundation”, in Honderd jaar Russell's paradox (Logic and its Applications 6), G. Link (red.), Berlin: de Gruyter, pp. 191–219.
• –––, 2005, “Vervanging versus verzameling en aanverwante onderwerpen in de constructieve Zermelo-Fraenkel-verzamelingenleer”, Annals of Pure and Applied Logic, 136: 156–174.
• –––, 2005a, “Het constructieve Hilbert-programma en de grenzen van de Martin-Löf-typetheorie”, Synthese, 147: 81–120.
• –––, 2005b, “De disjunctie en gerelateerde eigenschappen voor constructieve Zermelo-Fraenkel verzamelingenleer”, Journal of Symbolic Logic, 70 (4): 1232–1254.
• –––, 2006, "Keuzeprincipes in constructieve en klassieke verzamelingenleer", Logic Colloquium '02 (Aantekeningen in Logic 27), Z. Chatzidakis, P. Koepke, en W. Pohlers (red.), Wellesley, Massachusetts: AK Peters, 299–326.
• –––, 2006a, "Realizability for constructive Zermelo-Fraenkel set theory", in Logic Colloquium '03 (Lecture Notes in Logic 24), V. Stoltenberg-Hansen en J. Väänänen (red.), Wellesley, Massachusets: AK Peters, blz. 282-314.
• –––, 2006b, “Theorieën en ordinalen in bewijstheorie”, Synthese, 148 (3): 719–743.
• –––, 2008, “The natural numbers in constructive set theory”, Mathematical Logic Quarterly, 54: 287–312.
• –––, 2012, “From the weak to the strong exist property”, Annals of Pure and Applied Logic, 163: 1400–1418.
• –––, 2012b, "Constructive Zermelo-Fraenkel Set Theory, Power Set, and the Calculus of Constructions", in Epistemology versus Ontology: Essays on the Philosophy and Foundations of Mathematics ter ere van Per Martin-Löf, (Logic, Epistemology and the Unity of Science Series), P. Dybjer, S. Lindström, E. Palmgren en G. Sundhölm (red.), New York en Dordrecht: Springer Verlag.
• –––, 2017, "Proof Theory of Constructive Systems: Inductive Types and Univalence", in G. Jäger, en W. Sieg (red.), Feferman on Foundations (Outstanding Contributions to Logic: Volume 13), Cham: Springer, pp. 385–419.
• Richman, F., 2000, "De fundamentele stelling van algebra: een constructieve ontwikkeling zonder keuze", Pacific Journal of Mathematics, 196: 213–230.
• –––, 2001, "Constructieve wiskunde zonder keuze", in Hereniging van de antipoden: constructieve en niet-standaard weergaven van het continuüm (Synthese Library 306), P. Schuster, et al. (redactie), Dordrecth: Kluwer, pp. 199–205.
• Russell, B., 1908, "Mathematical logic as based on the theory of types", American Journal of Mathematics, 30: 222–262. Herdrukt in van Heijenoort (1967), 150–182.
• Scedrov, A., 1981, "Consistentie en onafhankelijkheid resulteert in intuïtionistische verzamelingenleer" in constructieve wiskunde (aantekeningen bij wiskunde 873), F. Richman (red.), Berlijn: Springer, pp. 54–86.
• –––, 1982, “Independence of the fan theorem in the presence of continuity principles” in The LEJ Brouwer Centenary Symposium, AS Troelstra, en D. van Dalen (red.), Amsterdam: Noord-Holland, pp. 435–442.
• –––, 1985, “Intuitionistic set theory” in Harvey Friedman's onderzoek naar de grondslagen van de wiskunde, LA Garrubgtib et al. (redactie), Amsterdam: Elsevier.
• Schütte, K., 1965, "Predicative well-orderings", in Formal Systems and Recursive Functions, J. Crossley en M. Dummett (red.), Amsterdam: Noord-Holland, pp. 279–302.
• –––, 1965a, “Eine Grenze für die Beweisbarkeit der Transfiniten Induktion in der verzweigten Typenlogik”, Archiv für mathematische Logik und Grundlagenforschung, 7: 45–60.
• Simpson, A., 2005, "Constructive set theories and their category-theoretic models", in From Sets and Types to Topology and Analysis: Towards Practicable Foundations for Constructive Mathematics (Oxford Logic Guides 48), L. Crosilla en P. Schuster (red.), Oxford: Oxford University Press.
• Swan, AW, 2014, "CZF heeft niet het bestaande eigendom", Annals of Pure and Applied Logic, 165: 1115–1147.
• Troelstra, AS, en van Dalen, D., 1988, Constructivism in Mathematics (twee delen), Amsterdam: Noord-Holland.
• Tupailo, S., 2003, "Realisatie van constructieve verzamelingenleer in Explicit Mathematics: a lower bound for impredicative Mahlo universe", Annals of Pure and Applied Logic, 120: 165–196.
• Voevodsky, V., 2015, 'Een experimentele bibliotheek van geformaliseerde wiskunde op basis van univalente grondslagen', 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, "Generalize realizability and Heyting models for constructive set theory", Annals of Pure and Applied Logic, 163 (2): 175–184.
• –––, 2014, “Een cumulatieve hiërarchie van verzamelingen voor constructieve verzamelingenleer”, Mathematical Logic Quarterly, 60 (1-2): 21–30.

Academische hulpmiddelen

	Hoe deze vermelding te citeren.
	Bekijk een voorbeeld van de PDF-versie van dit item bij de Vrienden van de SEP Society.
	Zoek dit itemonderwerp op bij het Internet Philosophy Ontology Project (InPhO).
	Verbeterde bibliografie voor dit item op PhilPapers, met links naar de database.

Andere internetbronnen

• Aczel, P. en M. Rathjen, 2010, Notes on Constructive Set Theory, boekversie, online beschikbaar.
• Kapulkin, C. en PL Lumsdaine, 2012, "The simplicial model of univalent foundations (after Voevodsky)", voordruk op arXiv.org.
• Algebraïsche verzamelingenleer, door S. Awodey (Carnegie Mellon).

[Neem contact op met de auteur voor verdere suggesties.]