Faculteit Letteren en Wijsbegeerte
Academiejaar 2006–2007
De ontstaansgeschiedenis van de axiomatische verzamelingenleer. Een reconstructie aan de hand van adaptieve logica’s
Martijn Windels
Promotor: Prof. dr. Diderik Batens
Scriptie voorgedragen tot het behalen van de graad van Licentiaat in de wijsbegeerte
i
Inhoudsopgave Inleiding
iii
1 De geboorte van de verzamelingenleer 1.1 Het herschrijven van een geschiedenis . . . . . . 1.2 Cantoriaanse verzamelingenleer . . . . . . . . . 1.2.1 Van analyse naar verzamelingenleer . . 1.2.2 Cantoriaanse verzamelingen . . . . . . . 1.3 Verzamelingen en grondslagen . . . . . . . . . . 1.3.1 De pragmatische aanpak van Dedekind . 1.3.2 Logicistische klassentheorie . . . . . . . 1.4 De paradoxen van de verzamelingenleer . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
1 1 2 2 8 9 10 13 16
2 Moderne verzamelingenleer 19 2.1 Zermelo, Fraenkel en Skolem . . . . . . . . . . . . . . . . . . . . 19 2.1.1 Het welordeningstheorema . . . . . . . . . . . . . . . . . . 19 2.1.2 Axiomatische verzamelingenleer . . . . . . . . . . . . . . . 22 2.1.3 Het vervangingsaxioma en de geboorte van moderne ZFC 24 2.2 Klassen en verzamelingen in NBG . . . . . . . . . . . . . . . . . 27 2.2.1 Von Neumann’s ordinale criterium voor verzamelingen . . 27 2.2.2 De verzamelingenleer van Paul Bernays . . . . . . . . . . 32 2.3 De Typentheorie . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.3.1 De typentheorie van Russell . . . . . . . . . . . . . . . . . 35 2.3.2 De vereenvoudigde typentheorie . . . . . . . . . . . . . . . 39 2.3.3 New Foundations . . . . . . . . . . . . . . . . . . . . . . . 41 2.4 Een voorlopige conclusie . . . . . . . . . . . . . . . . . . . . . . . 44 3 Verzamelingenleer gebaseerd op adaptieve logica 3.1 Inleiding . . . . . . . . . . . . . . . . . . . . . . . . 3.2 De logica CLu∃m . . . . . . . . . . . . . . . . . . . 3.3 Van paraconsistent naar adaptief . . . . . . . . . . 3.4 Een adaptieve verzamelingenleer . . . . . . . . . . 3.5 Besluiten . . . . . . . . . . . . . . . . . . . . . . .
ii
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
46 46 47 50 52 56
Inleiding Het wijsgerig statuut van de verzamelingenleer is op zijn zachtst gezegd dubieus. Enerzijds is in de loop van de twintigste eeuw genoeg evidentie verzameld om te stellen dat alle wiskunde in de taal van de verzamelingenleer te formuleren is. Bijgevolg heeft deze theorie een belangrijke funderende rol in de wiskunde. Anderzijds is het ver van duidelijk wat verzamelingen nu net zijn. De verzamelingenleer is het strijdpunt van een succesvolle wiskundige praktijk met een pijnlijk gebrek aan filosofische inzichten. Laat ik om het probleem scherp te stellen de verzamelingenleer confronteren met de klassieke filosofie¨en van de wiskunde teneinde aan te tonen dat ze dat deze allemaal op een of meerdere punten tekort schieten. Een van de centrale kenmerken van de verzamelingenleer is de manier waarop erin met oneindigheden wordt omgesprongen. Een van de cruciale drijfveren in de vroege ontwikkeling van de verzamelingenleer was net dat er verschillende oneindigheden zijn. Het eigenaardige hieraan is dat eens de oneindigheid een plaats had gekregen in de wiskunde bleek dat mensen met hun eindige verstand er een zeker inzicht in kunnen krijgen en er eigenschappen van bewijzen. Het is op dat punt dat de constructivisten tekort schieten. Indien wiskundige objecten (een gevaarlijke term die ik enkel gebruik bij gebrek aan beter) niet meer zouden zijn dan mentale constructies, dan zou de studie van oneindigheden door middel van de verzamelingenleer onmogelijk zijn. Het is bekend dat L.E.J. Brouwer, de vader van het moderne constructivisme net om die reden dacht dat de verzamelingenleer een grote dwaling was. Ikzelf zie niet in waarom een tekort aan filosofisch begrip van een praktijk moet leiden tot het verbieden er van. De zwakte van de formalistische positie is het gevolg van een aantal technische resultaten. Ten eerste weten we dankzij het werk van Kurt G¨odel dat zoals de zaken er nu voor staan een consistentiebewijs voor de verzamelingenleer buiten ons bereik ligt. Wat nog erger is, is dat de verzamelingenleer geen categorische formulering kan krijgen, althans niet in de eerste in de eerste-orde logica. Het gevolg is dat de definitie van verzamelingen als “die dingen die impliciet door de axioma’s van de verzamelingenleer zijn gedefinieerd” tekortschiet. De formalist kan niet weten wat verzamelingen zijn. Platonisten voelen zich goed in het paradijs van Cantor, de titel die David Hilbert aan de verzamelingenleer gaf. De zwakte van de constructivist is namelijk de kracht van hun positie. Het is helemaal niet nodig oneindigheden mentaal te construeren aangezien ze onafhankelijk van de mens bestaan. Het ontstaan van de verzamelingenleer was niets anders dan het ontdekken van een nieuw continent in de wereld van de wiskunde. Maar daar houden de voordelen van deze positie op. Er is geen enkele degelijke theorie over de manier de wiskundigen hun eldorado waarnemen. Bovendien bevat de geschiedenis van de verzameliniii
genleer een mooi voorbeeld van hoe dezelfde wiskundige werkelijkheid indien ze bestaat zich op een verschillende manier laat kennen. Voor Georg Cantor stond het vast dat elke verzameling geordend kon worden, maar kon zijn hypothese niet bewijzen. Voor Bertrand Russell daarentegen was eens het bewijs voor deze stelling geleverd was dit bewijs eerder een argument om aan te nemen dat het bewijs zelf op foute principes steunde. Indien de platonist gelijk heeft, moet hij duidelijk kunnen maken hoe een dergelijke verwarring mogelijk kan zijn. In het licht van het falen van de filosofie zal ik onderzoeken hoe de verzamelingenleer historisch gegroeid is om langs die weg beter te begrijpen wat verzamelingen zijn. Ik ga er van uit dat de verzamelingenleer zoals ze nu bestaat het resultaat is van een lange reeks van pogingen om verschillende problemen op te lossen. Eerder dan de verzamelingenleer te beschouwen als een theorie die langs steriele weg is ontstaan beschouw ze eerder als een methode, een gereedschapskist met sterke principes die zo universeel moesten zijn. Het is slechts door te begrijpen wat de problemen waren die opgelost moesten worden dat we zullen begrijpen wat verzamelingen zijn. Deze geschiedenis is wat ik in het eerste deel zal behandelen. De vraag die ik in het tweede deel zal behandelen is technischer van aard. Zoals bekend werd de verzamelingenleer in haar vroege jaren geconfronteerd met paradoxale resultaten. Er wordt een onderscheid gemaakt tussen de vroege, na¨ıeve, verzamelingenleer en de axiomatische verzamelingenleer. Het is de overgang tussen deze twee theorie¨en die ik zal onderzoeken. In mijn poging de gedachten van de vaders van de moderne verzamelingenleer te vatten zal ik beroep doen op een adaptieve logica.
iv
Hoofdstuk 1
De geboorte van de verzamelingenleer 1.1
Het herschrijven van een geschiedenis
De na¨ıeve verzamelingenleer heeft nooit bestaan. Dat is de stelling die in dit hoofdstuk verdedigd zal worden. Dat deze term ooit in zwang is geraakt heeft te maken met de verwarring van twee projecten die een verschillende notie van wiskundige collecties gebruikten. Langs de ene kant was er Georg Cantor’s notie van menge, die ondanks haar vage definitie nooit getroffen werd door de paradoxen die op het einde van de negentiende eeuw werden ontdekt, en aan de andere kant was er de klassentheorie die uit de logica kwam en die niet met Cantoriaanse ide¨een kon worden gecombineerd zonder tot paradoxen te leiden. Cantor’s theorie na¨ıef noemen berust op de grove misvatting, die haar oorsprong lijkt te vinden bij Bertrand Russell, dat klassen en verzamelingen hetzelfde zijn. Een aandachtige lezing van Cantor’s werk toont aan dat dit een vergissing is. Het is beter de verhouding tussen de verzamelingenleer en de klassentheorie uit het logicisme te vergelijken met die tussen de rekenkunde en de peanoaxioma’s. Enerzijds is er een wiskundige theorie die zonder propere grondslagen ontstaat en ontwikkeld wordt en langs de andere kant een poging die theorie te axiomatiseren. Cantor’s werk had wel een zekere filosofische kracht, maar wat hij net bedoelde met menge heeft hij nooit ten volle duidelijk kunnen maken. Russell heeft in zijn poging om de wiskunde te herleiden tot logica nooit ingezien dat Cantoriaanse verzamelingen eigenschappen hebben die ze ongeschikt maken voor zijn project en dit heeft dan weer geleid tot het onrechtmatig gebruik van resultaten over verzamelingen wanneer het over klassen gaat. Achteraf gezien is het bijna vanzelfsprekend dat dit tot problemen moest leiden. In wat volgt zal ik zowel de verzamelingenleer als de klassentheorie bespreken, de nadruk leggend op de verschillen tussen de aanpak van de wiskundigen en de logici. Een eerste sectie is een poging tot rehabilitatie van Cantor, voor wie verzamelingen in de eerste plaats een middel waren om zijn echte levenswerk, de transfiniete getallen, wiskundig acceptabel te maken. In de tweede afdeling zal besproken worden hoe verzamelingen aangewend werden om de grondslagen van de wiskunde te geven. Daarin hoop ik duidelijk te maken dat een verschillende norm qua rigueur tot verschillende versies van de verzamelingenleer 1
hebben geleid.
1.2
Cantoriaanse verzamelingenleer
De titel van deze afdeling is ten dele misleidend. Aangezien Cantor van nul moest beginnen bij het ontwikkelen van zijn verzamelingenleer is zijn notie van menge vaag en amorf geweest. Bijgevolg gebruikte hij in vrijwel elk artikel dat hij schreef over verzamelingen een andere definitie. Het probleem daarbij is dat de definitie in zijn wiskundig meest mature werk, Beitr¨ age zur Begr¨ undung der transfiniten Mengenlehre, niet langer de restricties bevat die de oorspronkelijke definities wel bevatten. Maar ook dit moet genuanceerd worden aangezien Cantor er regelmatig op blijft wijzen dat zijn menge eigenschappen hebben waardoor ze niet zonder meer aan de klassen van de na¨ıeve verzamelingeleer gelijk gesteld kunnen worden. Cantor was bijvoorbeeld van mening dat elke verzameling een welordening heeft. Aanvankelijk leek dit vanuit de Cantoriaanse conceptie van verzamelingen vanzelfsprekend, maar naarmate hij verder onderzoek deed bleek deze positie hoe langer hoe moeilijker houdbaar. Om dit soort redenen moet er onderscheid worden gemaakt tussen de verzamelingenleer anno 1883 en 1895. Ondanks de verschillen is het belangrijk in het achterhoofd te houden dat Cantor’s verzamelingenleer in de eerste plaats een vehikel bleef om zijn uitbreiding van het getalbegrip te verantwoorden. Hierdoor is het universum van Cantor voor ogen had van een heel andere aard dan het universum van de na¨ıeve verzamelingenleer1 .
1.2.1
Van analyse naar verzamelingenleer
Gezien vanuit het standpunt van Cantor is de verzamelingenleer een uit de hand gelopen zoektocht naar het antwoord op een vraag uit de analyse2 . Om uit te vinden onder welke voorwaarden een functie uniek te schrijven is als een fourrier-reeks diende hij het geval te onderzoeken van een functie die op oneindig veel plaatsen discontinu is en dan komt al snel de vraag op wat die oneindigheid betekent. De verzamelingenleer zag het geboortelicht in 1874, met ¨ de publicatie van Uber eine Eigenschaft des Inbegriffes aller reellen algebra” ischen Zahlen.”[33, p.88], waarin wordt bewezen dat de algebra¨ısche getallen een aftelbare verzameling vormen, terwijl deze van de re¨ele getallen overaftelbaar is. Cantor wist nu dat er verschillende soorten oneindigheid bestaan, maar hij had niet de middelen om de eigenschappen van de verschillende oneindigheden te behandelen. Hoe dan ook, nu Cantor wist dat er verschillende oneindigheden zijn, onderzocht hij enkele courante getalverzamelingen en kwam tot een conclusie die een belangrijke motor achter de rest van zijn onderzoek zou worden. Uit de voorbeelden die hij had onderzocht concludeerde Cantor omstreeks 1878 dat er buiten de oneindigheid van de natuurlijke getallen en deze van het interval [0, 1] geen oneindigheden mogelijk waren[16, p.191]. Dit is de eerste versie van de 1 Laat mij om te beginnen stellen dat deze bewoording niet letterlijk opgevat mag worden. Een van de centrale punten van Cantor’s opvattingen is dat er geen universele verzameling mogelijk is. Dit zal verder duidelijk worden. 2 Dit is niet de plaats om deze historie volledig te herhalen. Voor een overzicht van Cantor’s werk over puntverzamelingen dat is uitgemond in de start van de verzamelingenleer, zie bijvoorbeeld [21, 34].
2
continu¨ umhypothese, het probleem dat duidelijk maakt dat de wortels van de verzamelingenleer in de analyse liggen. Om op een exacte wijze over oneindigheden te kunnen spreken heeft Cantor zijn theorie van de transfiniete getallen uitgevonden. De eerste presentatie van zijn onderzoekingen kunnen we vinden in Grundlagen einer allgemeinen Mannigfaltigkeitslehre[16, pp.165–209], het eerste artikel waarin hij zich niet langer beperkt tot puntverzamelingen maar zich bezighoud met verzamelingenleer. Hierin presenteert Cantor de beginselen van de transfiniete rekenkunde, in de hoop langs deze weg duidelijk te maken dat het actuele oneindige wel degelijk een plaats heeft in de wiskunde en dat we kunnen spreken van de machtigheid van oneindige verzamelingen. Langs deze weg zou het probleem van de continu¨ umhypothese scherper geformuleerd kunnen worden. De Grundlagen is waarschijnlijk een van de meest vernieuwende en revolutionaire teksten uit de geschiedenis van de wiskunde: de oude angst voor het oneindige wordt hier overwonnen en vervangen door een originele theorie. Ik zal deze tekst eerder uitvoerig behandelen, omdat hier duidelijk zal worden dat Cantor’s opvattingen over verzamelingen verre van na¨ıef waren. Cantor begint met de lezer te waarschuwen dat hij bevreemdende idee¨en zal presenteren. Hij zal de getallenrij tot voorbij de oneindigheid aanvullen en dit op een manier die volgens hem uiteindelijk door iedereen als eenvoudig en natuurlijk zal worden beschouwd. Hij vervolgt door te stellen dat hij twee soorten oneindigheid onderscheidt: oneigenlijke oneindigheid, die hij veranderlijke eindigheid noemt en die centraal staat in de analyse, en eigenlijke oneindigheid, de actuele oneindigheid van bijvoorbeeld de volledige verzameling natuurlijke getallen. Het basisidee van de transfiniete getallen is op zich niet anders dan wat in de meetkunde werd gedaan met de introductie van het punt op oneindig van een rechte, maar Cantor veralgemeent en radicaliseert dit idee. In plaats van ´e´en punt op oneindig een oneindige rij punten op oneindig. Deze metafoor, samen met het onderscheid tussen de twee types oneindigheid, lijkt de sleutel tot Cantor’s twee generatieprincipes voor (transfiniete) getallen te zijn: (I) (II)
Indien α een getal is, dan α + 1 ook. Indien α, α + 1, α + 2, α + 3, . . . een oneindige reeks getallen is, dan is de limiet β van deze reeks ook een getal. Anders gezegd is β het kleinste getal dat groter is dan elk getal uit de rij. Cantor noemt de verzameling van de natuurlijke getallen de eerste getalklasse, en voert een beperkingsprincipe(Hemmungsprinzip) in dat stelt dat de tweede getalklasse bestaat uit alle getallen te vormen uit de eerste klasse met behulp van de principes (I)&(II). Dit proces laat verdere uitbreiding toe naar hogere getalklassen, en Cantor benadrukt dan ook dat dit proces geen einde kent[16, p.196]. Om te verduidelijken waarom deze nieuwe getalklassen van belang zijn, wordt het concept van machtigheid besproken. Cantor stelt dat iedere goedgedefinieerde verzameling een machtigheid heeft, en dat voor transfiniete verzamelingen van de n-de machtigheid geldt dat ze gelijkmachtig zijn aan de nde getalklasse. Merk op dat dit impliceert dat het hebben van een machtigheid een noodzakelijke voorwaarde is om een verzameling te kunnen zijn. Dat dit een verwerping inhoudt van de stelling dat de logicistische klassentheorie gelijk is aan de verzamelingenleer is te verdedigen aan de hand van een citaat uit Cantor’s recensie van Die Grundlagen der Arithmetik van Frege. In een kritiek op de getalsdefinitie uit dat werkje zegt hij het volgende: 3
...er u ¨bersieht ganz, daß der Umfang eines Begriffs” quantitativ im ” allgemeinen etwas v¨ ollig Unbestimmtes ist; nur in gewissen F¨allen ist der Umfang eines Begriffs” quantitativ bestimmt, dann kommt ” ihmallerdings, wenn er endlich ist, eine bestimmte Zahl und, falls er unendlich ist, eine bestimmte M¨achtigkeit zu[16, p.441]. En hij vervolgt door te stellen dat een theorie van de kardinaalgetallen moet ontwikkeld worden alvorens men zonder problemen over extensies kan spreken. Kon de waarschuwing nog explicieter worden geformuleerd? Cantor besefte maar al te goed dat een na¨ıef comprehensieprincipe ongeschikt is om de verzamelingenleer op te stoelen. Sterker nog, de verzamelingenleer moet reeds uitgewerkt zijn alvorens de logicistische stap van intensie naar extensie mogelijk is. Het begrip machtigheid laat toe te spreken over de grootte van oneindige verzamelingen. Aangezien nu elke verzameling een machtigheid heeft, en deze uit te drukken is door middel van een (transfiniet) getal hebben we impliciet de mogelijkheid een verzameling te ordenen. Cantor was van mening dat de generatieprincipes voor getallen in zekere zin vanzelfsprekend waren. Daaruit volgt dat de transfiniete getallen een natuurlijke manier bieden om elke goedgedefinieerde verzameling te ordenen. Daß es immer m¨ oglich ist, jede wohldefinierte Menge in die Form einer wohlgeordneten Menge zu bringen, auf dieses, wie mir scheint, grundlegende und folgenreiche, durch seine Allgemeing¨ ultigkeit besonders merkw¨ urdige Denkgesetz werde ich in einer sp¨ateren Abhandlung zur¨ uckkommen.[12, p.169] Indien de continu¨ umhypothese het eerste hoofdprobleem van de verzamelingenleer was, dan is het bewijs van bovenstaande stelling het tweede probleem dat dringend opgelost moest worden. Ik wil kort stilstaan bij dit probleem omdat het ten eerste voor een groot deel heeft bepaald hoe de axiomatische verzamelingenleer is ontstaan maar ook omdat het exemplarisch is voor de manier waarop wiskunde abstracter is geworden mede dankzij de uitvinding van de verzamelingenleer. Het zal ons ook iets leren over Cantor’s filosofie van de wiskunde. Cantor’s werk past in een traditie waarin wiskunde niet langer beperkt moest worden tot constructieve methoden3 . Laat mij om dit te illustreren Cantor’s eerste definitie van Menge aanhalen: Eine Mannigfaltigkeit (ein Inbegriff, eine Menge) von Elementen, die irgendwelcher Begriffssph¨are angeh¨oren, nenne ich wohldefiniert, wenn auf Grund ihrer Definition und infolge des logischen Prinzips vom auschgeslosenen Dritten es als intern bestimmt angesehen muß, sowohl ob irgendein derselben Begrifssph¨are angeh¨origes Object zu der gedachten Mannigfaltigkeit als Element geh¨ort oder nicht, wie auch, ob zwei zur Menge geh¨orige Objekte, trotz formaler Unterschiede in ter Art des Gegebenseins einander gleich sind oder nicht. 3 Een ander voorbeeld van dit fenomeen zijn zuivere existentiebewijzen, zie bijvoorbeeld [23, p.78].
4
Im allgemeinen werde die betreffende Entscheidungen nicht mit den zu Gebote stehende Methoden oder F¨ahigkeiten in Wirklichkeit sicher und genau ausf¨ uhrbar sein; darauf kommt es aber hier durchaus nicht an, sondern allein auf die interne Determination, welche in konkreten F¨ allen, wo es die Zwecke fordern, durch Vervollkommnung der Hilfsmittel zu einer aktuellen (externen) Determination auszubilden ist[16, p.150]. Het is belangrijk dat Cantor enkel verwacht dat het in principe mogelijk moet zijn te bepalen of een element al dan niet tot een verzameling behoort. De verzameling van de re¨ele getallen waarin de cijferreeks 17894 voorkomt zal π al dan niet bevatten, ongeacht of deze sequentie al hebben aangetroffen in de decimale ontwikkeling er van. Iets analoog geldt voor de welordening van een verzameling. Cantor had in 1883 nog maar twee oneindigheden gevonden en hij dacht dat de transfiniete getallen zoals hij ze had gedefinieerd voldoende waren om alle machtigheden uit te drukken. Bijgevolg gaven de transfiniete getallen een manier om, althans in principe, de elementen van eender welke verzameling in een welordening te plaatsen4 . Bovenstaande definitie leert ons bovendien iets bijzonder over Cantor’s opvattingen over verzamelingen. Voor eender welk object geldt dat het ofwel tot een gegeven verzameling behoort, ofwel niet. De verzamelingen die het einde van de na¨ıeve verzamelingenleer waren, zoals de totaliteit alle ordinaalgetallen of de verzameling van alle verzamelingen die zichzelf niet bevatten, zijn volgens deze definitie helemaal geen verzamelingen. In de eindnoten van de grundlagen geeft Cantor een andere definitie van menge, maar de teneur blijft dezelfde: niet elke klasse is een verzameling[12, p.204 - 205]. Alleen redeneert Cantor nu vanuit de stelling dat alle verzamelingen een machtigheid hebben. Cantor begint zijn redenering met een nieuwe definietie van menge: Unter einer “Mannigfaltigkeit” oder “Menge” verstehe ich n¨amlich allgemein jedes Viele, welches sich als Eines denken l¨aßt, d.h. jeden Inbegriff bestimmter Elemente, welcher durch ein Gesetz zu einem Ganzen verbunden werden kann [. . . ] Hij vervolgt door te stellen dat het volgens hem uitgesloten is dat er een einde komt aan de reeks van de opeenvolgende transfiniete getallen. Hoewel het tweede generatieprincipe toelaat over te gaan naar een limietgetal, blijft er een onbereikbare limiet in de vorm van het Goddelijke Absolute5 . Het Absolute kan niet gekend of benaderd worden. De getallenrij is dus niet als geheel te denken, en dus ook geen verzameling. Bijgevolg kan er helemaal geen verzameling van alle ordinaalgetallen bestaan, laat staan een universele verzameling[16, p.205]. In de nasleep van de Grundlagen schreef Cantor een belangrijk werkje dat ongepubliceerd bleef tot 1970, ironisch genoeg omdat Mittag-Leffler, de uitgever van het desbetreffende tijdschrift(Acta Mathematica), van mening was dat het zo’n honderd jaar te vroeg werd geschreven. In Principien einer Theorie der Ordnungstypen presenteert hij een verdere uitbreiding van zijn werk rond transfiniete rekenkunde. In de Grundlagen had Cantor het getalsbegrip uitgebreid om te spreken over de machtigheid van iedere willekeurige verzameling, maar de 4 Michael
Hallett zet een gelijkaardige gedachtengang uit elkaar[34, p. 32–40]. dergelijke terminologie doet nu vreemd aan, maar was dit voor Cantor geenszins. Voor hem gaan metafysica en wiskunde hand in hand[30, p.83]. 5 Een
5
transfinieten waren slechts geschikt om te spreken over de welgeordende verzamelingen. De volgende stap voor Cantor was een uitbreiding van de getallen zodat het mogelijk werd te spreken over de structuur van een verzameling onder hun natuurlijke orde. Wat nu de ordinalen wordt genoemd, is slechts bruikbaar voor welgeordende verzamelingen, en de theorie van de ordetypes vormt een natuurlijke uitbreiding hierop[30, p.84]. Dit is belangrijk omdat het aantoont dat de oorspronkelijke motivatie van Cantor de theorie van de transfiniete getallen bleef en dat ten gevolge van dit het begrip van menge veel specifieker was dan het klassenbegrip van de logicisten. Enkel wat een machtigheid heeft kan een menge zijn; verzamelingen zijn niet los te denken van het getalbegrip. Een ordetype is een koppel hX,
spreekt zelf over het algemene begrip waaronder alle verzamelingen met dezelfde ordestructuur vallen[30, p.87]. Cantor en later Russell hebben uitgebreid gebruik gemaakt van deze methode van definitie door abstractie van wat we nu (om de psychologische connotaties te vermijden?) eenvoudigweg equivalentieklassen noemen. 7 Merk op dat dit past in de tendens van de veralgemening van het functiebegrip. Wanneer Cantor spreekt over alle functies, dan gaat het al lang niet meer om functies waarvoor een regel bestaat. De stap naar het latere keuzeaxioma volgt hier bijna onmiddellijk uit, zie daarvoor[37].
6
In 1895 verschijnt het eerste deel van Beitr¨ age zur Begr¨ undung der transfiniten Mengenlehre[14, p.282–356], het sluitstuk van Cantor’s werk aan de verzamelingenleer. Het verschil met 1883 is enorm: alle filosofische en metafysische verantwoording voor het gebruik van actuele oneindigheden wordt achterwege gelaten ten voordele van een uitgebreide uiteenzetting van het nut ervan. De stijl van het werk is wiskundig superieur, en geeft een overzicht van alle werk van Cantor met betrekking tot verzamelingen. De verzamelingenleer was een aanvaarde deeltak van de wiskunde geworden, en Cantor’s project om de oneindigheid en in het bijzonder continu¨ıteit te beschrijven had volgelingen gevonden, zodat het niet langer noodzakelijk was een uitgebreide apologie neer te schrijven. De meest dringende problemen waren vanaf nu van wiskundige aard. De verzamelingenleer kende twee grote problemen die om een antwoord vroegen: de waar- of valsheid van de continu¨ umhypothese en van de welordeningshypothese8 . Het werk begint met een nieuwe definitie van verzameling, ´e´en die de eisen uit de Grundlagen niet herhaalt9 . Het idee dat een verzameling een collectie is die op de een of andere manier toch een eenheid vormt blijft wel bewaard, maar Cantor benadrukt niet langer dat niet elke collectie zonder meer een verzameling is. Unter einer Menge” verstehen wir jede Zusammenfassung M von ” bestimmten wohlunterschiedenen Objekten m unsrer Anschauung oder unseres Denkens(welche die Elemente” von M genannt werden) ” zu einem Ganzen[16, p.282]. Cantor beweert hier ook, in strijd met wat hij voorheen benadrukte dat de verzameling van alle kardinaalgetallen een welgeordende verzameling is, hoewel dat op te vatten is in uitgebreide betekenis (erweiterten Sinne)[16, p.295]. Dit had hij ook al gedaan in het bewijs van de overaftelbaarheid van de machtsverzameling, en het mag duidelijk zijn dat hij ofwel inexact is in zijn formuleringen, ofwel met tegenstrijdige idee¨en worstelde. Later zou de noodzaak om te verhelderen wat de uitgebreide betekenis van verzamelingen is zich nog meer opdringen aan Cantor. Cantor had omstreeks 1895 de paradox van het grootste kardinaalgetal ontdekt, en zag zich genoodzaakt een verantwoording te vinden die wiskundig meer aanvaardbaar was dan zijn theologische argument van het goddelijke Absolute. Cantor zag zijn heil in het gelijkstellen van het absolute oneindige aan inconsistente verzamelingen, een idee dat later terug intrede zou doen op meer exacte wijze bij Von Neumann(infra.). In [39, p.98] treffen we een brief van Cantor aan Jourdain uit 1904 aan waarin hij de paradox die Russell zoveel kopzorgen bezorgde op eenvoudige wijze aan de kant schuift door verzamelingen gelijk te stellen aan consistente collecties. Welnu, aangezien de Russelverzameling inconsistent is, kan ze ook onmogelijk een verzameling zijn en dus ook geen element van een andere verzameling. In plaats van een paradox ziet Cantor hier een positief resultaat: we weten nu dat de universele klasse geen verzameling is. 8 Dat deze de belangrijkste vragen waren is ten dele af te leiden uit de structuur van het artikel, dat in twee delen verscheen. Het eerste deel bevat een uitvoerige bespreking van de ordetypes en culmineert in een beschrijving van het ordetype van het continu¨ um, terwijl het tweede deel, [15], een studie van de welgeordende verzamelingen bevat. 9 Mijn inziens een jammere zaak omdat het verlies aan subtiliteit Cantor veel diskrediet heeft opgeleverd. Zelfs ernst Zermelo denkt dat de definitie van 1895 de originele definitie is[63, p.200].
7
Een analoge redenering treffen we aan in Cantor’s brief aan Dedekind uit 1899 [52, 16], waarin Cantor de paradox van Burali-Forti en de paradox van het grootste kardinaalgetal behandelt. In de eerste plaats zien we Cantor hier iets constructief doen met de paradoxen: ze verhelderen wat voor hem het wiskundige Absolute is. Cantor geeft bovendien een karakterisering van wat nu klassen worden genoemd, evenals een voorloper van het vervangingsaxioma. Eine Vielheit kann n¨ amlich so beschaffen sein, daß die Ahnnahme eines ”Zusammenzeins”aller ihrer Elemente auf einen Widerspruch f¨ urt, so daßes unm¨ oglich ist, die Vielheit als eine Einheit, als ¨ein fertiges Ding¨ aufzufassen. Solche Vielheiten nenne ich absolut unendliche oder inkonsistente Vielheiten. [. . . ] Zwei ¨aquivalente Vielheiten sind entweder beide ”Mengen”, oder beide inkonsistent. Jede Teilvielheit einer Menge ist eine Menge. Jede Menge von Mengen ist, wenn man die letzteren in ihre Elemente aufl¨ost, auch eine Menge. Deze theorie geeft een eerste mogelijkheid om een algemene karakterisering van inconsistente collecties te geven. We weten dat de verzameling van alle ordinaalgetallen inconsistent is. Uit bovenstaande eigenschappen volgt dat een verzameling die een deelverzameling heeft die af te beelden is op de verzameling van alle ordinalen ook inconsistent is. Bijgevolg zijn de inconsistente collecties gewoon veel te groot[34, p.168]. De identificatie van Absoluut Oneindige met inconsitente collecties heeft een interessant gevolg voor de manier waarop Cantor met bijvoorbeeld de Burali-Forti paradox kon omgaan. In plaats van een bewijs dat de verzamelingenleer inconsistent is, is het een positief resultaat dat aantoont dat de totaliteit van alle ordinalen geen verzameling is. Cantor’s theorie is dus in zekere zin immuun voor paradoxen. Een inconsistentie binnen de verzamelingenleer is onmogelijk aangezien wat inconsistent is helemaal geen verzameling is.
1.2.2
Cantoriaanse verzamelingen
Ik heb in voorgaande afdelingen duidelijk trachten te maken dat Cantor’s verzamelingenleer helemaal niet na¨ıef is. De verzamelingen van Cantor onderscheiden zich op drie punten van de klassen uit het logicisme: ze zijn per definitie consistent, ze zijn “´e´en” en ze hebben een machtigheid. Het eerste criterium is de grootste zwakte van Cantor’s verzamelingenleer ten opzichte van de geaxiomatiseerde versies. Cantor kan zonder al te veel problemen beweren dat de Russellverzameling van alle verzamelingen die zichzelf niet bevatten geen verzameling is, maar het ontbreekt hem aan een criterium om het onderscheid te maken. Het criterium uit de brief aan Dedekind is hiervoor geen remedie: binnen het Cantoriaanse systeem is er vanaf dan wel een verklaring waarom een bepaalde klasse geen verzameling is, maar we hebben geen manier om te voorkomen dat ze gebruikt worden. Dit alles zorgt er voor dat de Cantoriaanse verzamelingenleer in zekere zin uit experimentele, empirische wiskunde bestaat. De axiomatische verzamelingenleer bevat methodes om te voorkomen dat klassen ooit voor verzamelingen worden aanzien[34, p.38]. De definities uit 1883 en 1895 vermelden dat een verzameling als ´e´en moet zijn te denken. Cantor gaat er zelf nogal licht over hoe dit mogelijk kan zijn, en beperkt zich tot te stellen dat een wet verschillende dingen kan bundelen tot een geheel. Tot op dit punt correspondeert zijn theorie overigens perfect met die 8
van Russell, maar deze laatste was van mening dat met elke wet een verzameling correspondeert. Verder zal ik uitgebreider behandelen hoe Russell geworsteld heeft met de problematiek rond het verzamelingsbegrip. Los van de metafysische problemen hoeft het overigens niet meer te betekenen dan dat een verzameling de eigenschap moet hebben dat ze ook als element moet kunnen optreden. Het moderne onderscheid tussen klassen en verzamelingen steunt op dit verschil, en dit lijkt voldoende te zijn om te voorkomen dat de theorie inconsistent is. Bovendien zou dit ook verklaren waarom Cantor geen universele verzameling in zijn theorie toeliet: mocht de universele klasse immers een verzameling zijn en dus tot een andere klasse behoren, dan zou ze helemaal geen universele klasse zijn. De derde cruciale eigenschap is welordening, met het daarbijhorende gevolg dat ze een machtigheid hebben die uitdrukbaar is door middel van een (transfiniet) getal. Mijns inziens speelde welordening bij Cantor (zeker voor de ontdekking van het naar hem vernoemde theorema) eerder de rol van axioma van de verzamelingenleer dan als te bewijzen eigenschap. Cantor heeft verzamelingen in de grundlagen ingevoerd ter illustratie van de mogelijkheden die de transfiniete getallen bieden om machtigheden uit te drukken. De voorwaarde dat een verzameling een welordening heeft is met andere woorden cruciaal. Dit heeft tot gevolg dat er iets van structuur in het Cantoriaanse universum zit die we niet aantreffen in dat van de logicisten. Cantor was zich hier van bewust: Zwischen allen typen einfach geordneter Mengen (also nicht blos zwischen den Typen wohlgeordneter Mengen, den sogenannten Zahlen) herrscht eine strenge, wenn ich mich so ausdr¨ ucken darf, arithmethische Gesetzm¨ assigkeit[30, p.90]. In dat opzicht is het latere model van de cumulatieve hi¨erarchie misschien wel de beste uitwerking van Cantor’s opvattingen over verzamelingen.
1.3
Verzamelingen en grondslagen
Zoals bekend was de wiskunde in de negentiende eeuw het slachtoffer van haar eigen succes geworden. De vruchtbaarheid van de analyse zoals uitgewerkt door Newton en Leibniz had er voor gezorgd dat de betekenis van de basisbegrippen van de discipline, zoals limiet en continu¨ıteit, op een intu¨ıtief niveau was blijven steken. Er was hoegenaamd geen reden om lang stil te staan bij de grondslagen van de analyse. Er was uiteraard de vernietigende kritiek van Berkeley in The Analyst, maar deze had geen impact gehad op de praktijk. Het resultaat van deze geschiedenis was de ontdekking van tegenstrijdige resultaten. Hoe in het werk van onder meer Cauchy en Weierstrass deze paradoxen werden opgelost is een andere geschiedenis dan deze die ik wil vertellen. Het belangrijkste punt voor mijn verhaal is dat wiskundigen tot het inzicht kwamen dat de klassieke methodologie, waarbij bewijzen op de een of andere manier de intu¨ıtie moeten leiden tot inzichten niet streng genoeg was. Een deel van de reactie op deze problematiek was dat er strengere eisen werden gesteld aan definities. Cantor’s werk was oorspronkelijk een poging te verhelderen wat betekent, maar minstens vanaf 1884 kwam bij hem het idee op dat verzamelingenleer dienst kan doen als universele taal van de wiskunde. In deze afdeling zal ik bespreken hoe dit idee het startpunt is van een andere 9
manier om over verzamelingenleer te denken en die in zekere zin als de inverse van Cantor’s denken kan worden gezien. Cantor begon met de (transfiniete) getallen en kwam uit bij een universum van verzamelingen dat de structuur van de getallen had. Cantor’s bewering dat elke verzameling een welordening heeft moet in dit licht worden gezien. Voor de volgende auteurs zijn “verzameling” en “klasse” transparante begrippen die in de eerste plaats moeten dienen om te verduidelijken wat getallen zijn.
1.3.1
De pragmatische aanpak van Dedekind
Richard Dedekind heeft twee korte werkjes geschreven die hem ´e´en van de vaders van het verzameling-reductionisme maken, Stetigkeit und irrationale Zahlen en Was sind und was sollen die Zahlen. Het eerste geeft een definitie van de irrationale getallen door middel van wat nu Dedekind-sneden wordt genoemd en het tweede is een ambitieuze poging de methodes en de begrippen van de rekenkunde te herleiden tot wat hij onbewijsbare logische principes acht te zijn. Dedekind, die ijverig correspondeerde met Cantor, beschouwde in beide gevallen de verzamelingenleer als een degelijk vertrekpunt. Dedekind vermeldt in de beginparagrafen van Stetigkeit und irrationale Zahlen dat hij begon met zijn grondslagenonderzoek toen hij in 1858 vaststelde dat meetkundige intu¨ıties de basis vormen van de differentiaalrekening. Volgens hem kan dit onmogelijk wetenschappelijk worden genoemd10 en moeten de fundamenten van de analyse worden gelegd in de zuivere rekenkunde[22, p.2]. Ondanks deze afkeer van meetkundige denkbeelden in de analyse ontwikkelt hij zijn theorie van de re¨ele getallen door te wijzen op de analogie met een geijkte rechte. Dedekind vertrekt van de opmerking dat er oneindig veel meer punten op een rechte liggen dan er rationale getallen zijn[22, p.9], een stelling die twee jaar later ten volle door Cantor herdacht en bewezen werd. De verklaring hiervoor is dat de re¨ele getallen een continu¨ um vormen. De sleutel tot de definitie van de irrationalen is de definitie van deze laatste eigenschap: volgens Dedekind is een geordende verzameling continu indien ze in twee verzamelingen11 kan worden opgedeeld zodat voor elk element a van de ene klasse geldt dat het kleiner is dan elk willekeurig element b van de tweede klasse. Een Dedekind-snede is niet meer dan een dergelijke opdeling van de verzameling van de rationele getallen. Nu zijn er twee gevallen mogelijk: ofwel wordt de snede bepaalt door een rationeel getal, ofwel niet. In het tweede geval bepaalt de snede een irrationaal getal[22, p.15]. Het basisidee van de Dedekind-sneden is van een verbazende eenvoud maar is filosofisch verdacht. Ten eerste worden de irrationalen gedefinieerd aan de hand van de verzameling waartoe ze behoren. Een dergelijke impredikatieve definitie veronderstelt dat totaliteit van de re¨ele getallen op de een of andere wijze reeds gegeven is en gaat er dus van uit dat wiskundige entiteiten op de een of andere 10 Dit is begrijpelijk aangezien de Euclidische meetkunde net van haar troon was gestoten. Indien de constructie van de irrationale getallen moet rusten op een of andere meetkunde, dan zou er sprake zijn van een even grote proliferatie van differentiaalrekeningen als van meetkundes. Daar komt nog bij dat het door de uitvinding van niet-Euclidische meetkundes duidelijk was geworden dat wiskunde niet beperkt hoeft te worden tot intu¨ıties. Met andere woorden was elke vorm van verantwoording door middel van intu¨ıties vanaf dat moment uit den boze. 11 Dedekind spreekt van klassen
10
manier bestaan los van het denken van mensen. Een tweede probleem is dat de irrationale getallen gedefinieerd worden als een koppel oneindige verzamelingen, wat de de zaken nog meer problematiseert. Tevens betekent dit dat Cantor niet de enige was die van mening was dat actuele oneindigheden een plaats hadden in de wiskunde12 . In Was sind und was sollen die Zahlen? heeft Dedekind de strategie die hij heeft gebruikt voor de irrationalen toegepast om de natuurlijke getallen te defini¨eren. Hiertoe heeft hij de theorie van de klassen een betere uitwerking gegeven in een deels axiomatische aanpak, die later ten volle door Zermelo werd benut. Ik zal dan ook in de eerste plaats zijn behandeling van systemen bespreken, om vervolgens te duiden hoe hij daarmee een definitie voor de verzamelingen van de natuurlijke getallen geeft. Eerst en vooral definieert Dedekind wat hij met een systeem bedoelt: It very frequently happens that different things, a, b, c, ... for some reason can be considered from a common point of view, can be associated in the mind, and we say that they form a system S. [...] Such a system S (an aggregate, a manifold, a totality) as an object of our thought is likewise a thing; it is completely determined when with respect to every thing it is determined wheter it is an element of S or not. [22, p.45, cursief in origineel] In een voetnoot[22, p.45] benadrukt Dedekind dat het helemaal niet noodzakelijk is om een concrete regel te hebben om te bepalen welke elementen tot een verzameling behoren en welke niet. Doch, wanneer hij mathematische inductie behandeldt spreekt hij over systemen die worden bepaald door alles wat een zekere eigenschap φ heeft. Op dit punt is Dedekind niet consequent. Dedekind aanvaard geen lege verzameling, hoewel hij het nut er van inziet[22, p.45]. Nochthans zou hij die door middel van comprehensie zonder veel problemen kunnen invoeren. Vervolgens bepaalt hij een aantal axioma’s waaraan de systemen moeten voldoen. Ten eerste is er het extensionaliteitsaxioma(twee verzamelingen zijn gelijk wanneer ze dezelfde elementen bevatten) en ten tweede wat ik de combinatorische regels van zijn theorie zou willen noemen: de unie en de doorsnede van systemen zijn steeds ook een systeem. Zermelo zou later deze methode veralgemenen, en zo de basis leggen van de moderne, iteratieve conceptie van het wiskundig universum. Voor het hoe en het waarom van Dedekind’s definitie van van de natuurlijke getallen volg ik zijn Brief aan Hans Keferstein[52, pp. 98–103]. Het doel van zijn definitie was niet, zoals bij Frege en Russell, een manier geven om individuele getallen te defini¨eren, maar wel karakteriseren wat de algemene eigenschappen zijn van de natuurlijke getallen[52, p.100]. De eerste eigenschap, de reden waarom hij de notie van systeem invoert, is uiteraard dat de natuurlijke getallen een verzameling vormen. Een tweede eigenschap van de natuurlijke getallen is dat ze een geordende verzameling vormen en dat bijgevolg moet verklaard worden wat orde is. Dedekind bespreekt eerst afbeeldingen van een verzameling op een tweede verza12 Dedekind beweert het idee van de Sneden reeds in 1858 te hebben bedacht [22, p.2], maar blijkbaar was de tijd toen nog niet rijp om zijn idee¨ en aan het grote publiek bekend te maken.
11
meling13 , om dan aan de hand van afbeeldingen binnen een verzameling ordeningen in te voeren. Hiertoe gebruikt hij het begrip van ketting, een geordend paar hX, Φi waarbij X een verzameling is en φ een afbeelding van X op X, zodat φ(X) ⊂ X. Dit stelt hem in staat X0 in te voeren, de verzameling van alle kettingen waartoe X behoort, om aan te tonen dat dit een geordende verzameling is. Dit laat hem toe een theorema te bewijzen dat het gebruik van mathematische inductie verantwoordt[22, p.60]. De derde centrale eigenschap van de verzameling van de natuurlijke getallen is volgens Dedekind dat ze oneindig is. Hij definieert een oneindige verzameling als een verzameling die gelijkmachtig is met een echte deelverzameling van zichzelf en geeft een amusant bewijs voor het bestaan van oneindige verzamelingen. We kunnen immers, zo stelt hij, onze gedachtenwereld als een verzameling beschouwen. Dan kan voor elke gedachte x een nieuwe gedachte y worden gedacht, namelijk de gedachte “x is een gedachte”. En dit kan voor elke willekeurige gedachte. Bijgevolg is de verzameling van mijn gedachten oneindig. Dedekind is verplicht aan te tonen dat oneindige verzamelingen bestaan14 , alvorens hij de oneindige verzameling van de natuurlijke getallen kan invoeren door middel van het begrip eenvoudig oneindige verzameling (simply infinite system), een verzameling zodanig dat er een keten over gedefinieerd is van een element dat geen lid is van die keten. Dit zijn met andere woorden de verzamelingen die door een recursieve operatie ontstaan, wat voldoende is volgens Dedekind om de natuurlijke getallen in te voeren door middel van volgende definitie: If in the consideration of a simply infinite system N set in order by a transformation φ we entirely neglect the special character of the elements; simply retaining their distinguishability and taking into account only the realtions to one another in which they are placed by the order-setting transformation φ, then are these elements called natural numbers or ordinal numbers or simply numbers and the base-element 1 is called the base-number of the number-series N. With reference to this freeing the elements from every other content (abstraction) we are justified in calling numbers a free creation of the human mind. [22, p.68] Aangezien de natuurlijke getallen werden ingevoerd als ketting, is het algemene theorema over inductie ook geldig voor de natuurlijke getallen evenals het gebruik van recursieve definities. Bijgevolg is hij in staat optelling, vermenigvuldiging en machtsverheffing te defini¨eren op de wijze die tegenwoordig aan de naam Peano wordt verbonden. Ik wil nu even kort toelichten op welke manier Dedekind anticipeerde op bredere ontwikkelingen in de grondslagen van de wiskunde. Ten eerste is de invloed van dit werk merkbaar op de manier waarop de latere formalisten de axiomatische methode gebruikten. De methode om een wiskundige entiteit (hier de natuurlijke getallen) impliciet te defini¨eren aan de hand van een aantal structurele eigenschappen zal worden toegepast door Hilbert voor de meetkunde en 13 Hij definieert een afbeelding als een wet die aan eender welk element x van een systeem een elemnt φx associeert. 14 Merk op dat dit bewijs het enige alternatief lijkt te zijn voor een axioma dat stelt dat er een oneindige verzameling bestaat. Russell geeft een analoog bewijs voor het bestaan van een oneindige verzameling in the Principles of Mathematics [47, p.357]
12
door Zermelo in de verzamelingenleer. Dat Dedekind enkel de structuur van de verzameling van de natuurlijke getallen heeft bepaald, en de getallen die dingen noemt die tot die verzameling behoren doopt werd hem door sommige auteurs niet in dank afgenomen. Russell zou bijvoorbeeld klagen dat Dedekind nooit heeft gedefinieerd wat getallen zijn, enkel wat de eigenschappen van een reeks zijn[47, p.249]. In de brief aan Keferstein is het duidelijk dat Dedekind ook bezorgd was over het met het uit het eerste punt samenhangende probleem van niet-standaardmodellen. Hij voorzag de mogelijkheid dat de verzameling die hij had gedefinieerd als getalsverzameling elementen bevatte die geen natuurlijk getal zijn[52, p.100]. Dedekind was van mening dat zijn kettingen voldoende waren om ons er van te verzekeren dat dit niet zo is15 . Een tweede modeltheoretisch aspect is zijn bewijs van het bestaan van oneindige getallen. Dit moet ons er van verzekeren dat er wel degelijk een consistente interpretatie mogelijk is van een theorie die spreekt over een (aftelbaar) oneindige verzameling [52, p.101]. Dedekind heeft aangetoond dat althans een deel van de rekenkunde te interpreteren is in termen van functies en verzamelingen. Het grote probleem van zijn theorie is dat hij deze noties zelf weinig adequaat karakteriseert. De auteurs die ik nu zal bespreken dachten een weg gevonden te hebben om voor eens en voor altijd de fundamentele begrippen van de wiskunde te vatten in logische noties.
1.3.2
Logicistische klassentheorie
Logicisme is de stelling die haar oorsprong vond bij Gottlob Frege en Bertrand Russell dat alle wiskunde herleidbaar is tot logica. Dit betekent dat volgens een logicist wiskundige redeneringen een aaneenschakeling van logische inferenties zijn en dat alle wiskundige basisbegrippen definieerbaar moeten zijn aan de hand van logische begrippen. Het patroon dat deze reductie zou moeten volgen is welbekend. Nadat de rekenkunde herleid werd tot klassentheorie16 moest van daaruit de analyse en de verschillende meetkundes uitgewerkt worden. Volgens Frege zou langs deze weg de consistentie van de wiskunde gegarandeerd worden[28, p.16]. De hoofdreden voor het logicisme is van filosofische aard. Frege probeerde het psychologisme te weerleggen [28, p.14, 42]. Russell probeerde een alternatief te formuleren voor de Kantiaanse stelling dat wiskunde ultiem berust op intu¨ıties van tijd en ruimte [47, p.4]. Hij had ingezien dat deze theorie de nieuwe wiskundige ontwikkelingen, niet-euclidische meetkundes en de verzamelingenleer, niet kon verklaren. Beide auteurs bleven evenwel het Kantiaanse onderscheid tussen analytische en synthetische oordelen hanteren. Voor beiden was de mogelijkheid dat wiskunde een empirische component bevat uitgesloten zodat de enige overblijvende optie was dat de wiskunde uit analytische oordelen bestaat. De stap van die opvatting naar de logicistische klassentheorie is opvallend snel gemaakt. De uitspraken “F x” en “x ∈ F ”leken immers zonder al te veel problemen inwisselbaar. Frege gebruikt voor zover ik weet in Die Grundlagen der Arithmetic enkel de term “concept” om over klassen te spreken, zodat strikt gesproken uitspraken van de vorm “x ∈ F ” overbodig zijn. Hij stelt zelfs 15 Sinds het werk van Skolem over niet-standaardmodellen van de rekenkunde weten we overigens dat dit niet klopt. 16 Ik verkies de term “verzameling” te reserveren voor de theorie van Cantor.
13
expliciet dat volgens hem het niet noodzakelijk is te spreken over de extensie van een concept, maar dat in alle gevallen het voldoende is te spreken over het concept[28, p.102]. In de Grundlagen is Frege met andere woorden van mening dat de predikatenlogica voldoende is om de rekenkunde te reduceren. Russell is zich meer bewust van de spanning tussen de intensioneel bepaalde klassen en de verschuiving richting extensionele methodes in de wiskunde en integreert de theorie van klassen dan ook in zijn systeem. Ik zal de klassentheorie van het logicisme bespreken aan de hand van Russell’s The Principles of Mathematics. Russell stelt in de inleiding dat zijn project twee doelen heeft. Ten eerste wil hij aantonen dat alle wiskundige concepten definieerbaar zijn aan de hand van logische begrippen en dat alle theorema’s afleidbaar zijn aan de hand van logische principes. Het tweede doel is de verheldering van de logische concepten die verder niet definieerbaar zijn. Aangezien Russells bedoeling in de eerste plaats filosofisch was, kon hij niet zo vrij omspringen met de verzamelingenleer zoals de wiskundigen dat hadden gedaan. Erger nog, indien hij werkelijk de volledige wiskunde wil herleiden tot logica, dan is hij in zekere zin verplicht de vrijheid die Cantor zich had gepermiteerd te verzoenen met de filosofisch ge¨ınspireerde beperkingen van het intu¨ıtionisme. Wanneer ik in het volgende hoofdstuk de verdere ontwikkelingen van het logicisme, de reactie op de paradoxen van de verzamelingenleer, zal bespreken zal duidelijk worden dat dit een hopeloze zaak is. Volgens Russell heeft logica drie subdisciplines: de propositionele calculus, de theorie van relaties en de theorie van klassen[47, p.11]. Het is de derde deeltak die ik in deze afdeling zal behandelen. Volgens Russell steunt de klassencalculus op drie basisbegrippen: de relatie ∈, propositionele functies17 en de abstractieoperator zodat[47, p.19]. [...] we require two primitive propositions. The first asserts that if x belongs to the class of terms satisfying a propositional function φx, then φx is true. The second asserts hat if φx and ψx are equivalent propositions for all values of x, then the class of x’s such that φx is true is identical with the class of x’s such that ψx is true [47, p.20]. Om te begrijpen waarom Russell deze axioma’s hanteert en dan in het bijzonder het comprehensie axioma moeten we kijken naar zijn wijsgerige doel en zijn analyse van het klassenbegrip. Russell begint de filosofische bespreking van klassen [47, Hoofdstuk 6] met te verduidelijken wat volgens hem het verschil is tussen extensionele en intensionele klassendefinities. De methode van extensionele definitie is volgens hem gebruikelijk in de wiskunde en bestaat eruit een opsomming te geven van de elementen van de klasse[47, p.67]. De tweede methode is de intensionele definitie aan de hand van de eigenschap die alle elementen van de klasse gemeenschappelijk hebben. Volgens Russell is er een eigenaardige spanning tussen de twee methodes: de eigenlijke wiskundige objecten zijn extensies, maar het wiskundig symbolisme werkt via intensies[47, p.99]. De extensionele methode was steeds prominenter gaan worden in de wiskundige wereld. In de loop van de negentiende eeuw was het functiebegrip veralgemeend van iets regelbepaald tot eender welke verzameling van geordende 17 Russell is allesbehalve duidelijk wat propositionele functies zijn. Het is een van de ondefinieerbare termen van zijn systeem[47, p.83], en lijkt afwisselend te staan voor eigenschappen en de symbolen die voor eigenschappen staan.
14
tweetallen [39, pp.30, 34–35]. Het keuzeaxioma dat Zermelo in 1904 heeft ingevoerd past in dezelfde traditie. Het extensionaliteitsaxioma is mijn inziens de meest centrale eigenschap van de verzamelingenleer en de klassentheorie18 , maar extensionele klassendefinities leven op gespannen voet met het logicisme. Om in zijn doel te slagen moest hij immers a) minstens de rekenkunde kunnen reduceren b) aantonen hoe de nieuwe takken van de wiskunde, in het bijzonder de theorie van het transfiniete, mogelijk waren en c) zich beperken tot het vocabularium van de logica. Voor elk van deze doelen lijkt comprehensie, de intensionele aanpak, noodzakelijk. Om de rekenkunde te reduceren tot de logica had Russell een definitie voor 0 nodig. Russell definieert de natuurlijke getallen, als kardinaalgetallen, op de volgende manier: het kardinaalgetal van een klasse k is de klasse n van alle klassen k 0 zodat er een bijectie tussen k en k 0 bestaat[47, p.115]. Onder deze definitie is 0 de klasse van alle klassen k zodat er een bijectie bestaat tussen de lege verzameling en k[47, p.128]. Het probleem met extensionele klassendefinities is dat de lege klasse zo niet definieerbaar is: een klasse die geen elementen bevat bestaat gewoon niet. Deze wat eigenaardige toestand is waarschijnlijk de reden waarom Dedekind geen lege verzameling gebruikte. Dit is de eerste, praktische reden waarom Russell het comprehensie-axioma nodig heeft. Het is pas door middel van een concept dat naar niets verwijst (bijvoorbeeld niet-zelfidentisch zijn) dat we kunnen spreken over de lege klasse[47, p.74]. Russell noemt Cantor in de inleiding van de Principles een van de belangrijkste wiskundige invloeden op zijn werk. De theorie van het oneindige is volgens hem dan ook een belangrijk onderdeel van de wiskunde. Dit is een tweede reden waarom Russell het comprehensieaxioma gebruikt. De extensionele defintie van klassen is volgens hem logisch mogelijk maar praktisch onmogelijk[47, p.96]. Aangezien we met een beperkte tijd moeten werken kunnen we onmogelijk alle elementen van een oneindige klasse opsommen. De enige manier om te spreken over het oneindige is door middel van concepten en hun extensie[47, p.349]. Russell was hierin voorgegaan door Frege die beweerde dat de verenigende kracht van een concept superieur is[28, p.58]. Naast deze twee praktische redenen is er nog het filosofische motief dat Russell voor ogen had. Aangezien hij wiskunde tot logica wilde herleiden was hij verplicht proposities als primitief te nemen en het klassenbegrip er van af te leiden. Slechts op die manier zou aangetoond worden dat er geen extra-logische elementen in de wiskunde zitten. Dit betekent dat de ∈-relatie waarmee de wiskundigen op de proppen kwamen een logisch begrip was. Hoewel Russell logica veel breder zag dan de theorie van syllogismen en zinnen met de subjectpredikaat structuur, bleef dit wel het meest centrale deel van de logica. Ergens moest de betekenis van ∈ gezocht worden in het verband tussen subject en predikaat19 . Russell’s reactie op de paradoxen van de klassentheorie is in dat opzicht verhelderend. Eerder dan een consistente klassentheorie te ontwikkelen voerde hij in de Principia Mathematica methodes in om elke uitspraak over klassen te vertalen naar uitspraken waarin geen sprake meer is van klassen. Het “verdachte” klassenbegrip werd gewoon opgegeven aangezien de verrijking 18 Zoals in hoofdstuk twee duidelijk zal worden is dit het gemeenschappelijke element van de meest bekende verzamelingenleren. Het lijkt ook een bijzonder statuut te hebben. De theorie van Zermelo zonder het keuzeaxioma is nog steeds een verzamelingenleer. Maar kunnen we nog van een verzamelingenleer spreken wanneer het extensionaliteitsaxioma ontbreekt? 19 Deze laatste relatie noemt Russell logisch fundamenteel[47, p.77]
15
van zijn symbolisme met klassen tot paradoxen heeft geleid20 . Op die manier realiseerde hij Frege’s hoger aangehaalde uitspraak dat extensies overbodig zijn. Hoewel Russell het werk van Cantor kon waarderen, verschilde hij op enkele cruciale punten van mening met hem. Het is de spanning tussen hun opvattingen die er voor gezorgd heeft dat de paradoxen van de klassentheorie de paradoxen van de verzamelingenleer worden genoemd. Russell was van mening dat zijn klassen en de menge van Cantor hetzelfde waren waardoor hij resultaten van de ene theorie gebruikte in de andere, met het gekende gevolg. Russell aanvaardde twee belangrijke opvattingen van Cantor niet: dat elke verzameling een welordening heeft en dat er geen universele verzameling is. Beide gevallen impliceren dat Russell’s universum van klassen rijker was dan dat van de Cantoriaanse menge. Het tweede verschilpunt betekende de doodsteek van het logicisme. Het eerste verschilpunt heeft te maken met de termen die als primitief gekozen worden in een theorie. Cantor vertrok van de transfiniete getallen en beschouwde enkel die verzamelingen die een machtigheid hebben. Dit heeft tot gevolg dat de machtigheid van elke twee verzamelingen met elkaar te vergelijken is. Russell werkt in de omgekeerde richting: hij vertrekt van het bredere klassebegrip en definieert aan de hand daarvan kardinaalgetallen. Voor Russell is het dan ook mogelijk dat er twee klassen bestaan zodat hun kardinaalgetallen niet met elkaar te vergelijken zijn[47, p.364]. Het comprehensie principe garandeert dat er een universele klasse bestaat. In tegenstelling tot Cantor vindt Russell dit dan ook geen problematische notie. Maar uiteraard botst het idee van een universum met Cantor’s bewijs dat er geen grootste kardinaalgetal bestaat. Het universum blijkt in aanwezigheid van het bestaan van een machtsverzameling niet zo universeel te zijn. Voor Russell is deze situatie onaanvaardbaar: The difficulty arises whenever we try to deal with the class of all entities absolutely, or with any equilly numerous class; but for the difficulty of such a view, one would be tempted to say that the conception of the totality of things [. . . ] is in some way illegitimate and inherently contrary to logic. But it is undesirable to adopt so desperate a measure as long as hope remains of some less heroic solution[47, p.362]. Het is bij het zoeken naar een oplossing van deze spanning dat Russell de naar hem vernoemde paradox heeft ontdekt. Russell be¨eindigt zijn discussie van de problemen die Cantor’s theorema hem hebben opgeleverd door te stellen dat hij de oplossing van zijn probleem overlaat aan de vindingrijkheid van de lezer. Na een kort overzicht van de bekendste paradoxen die opduiken in Russell’s klassentheorie zal ik de vindingrijkheid van wiskundigen en logici beschrijven.
1.4
De paradoxen van de verzamelingenleer
Rond de eeuwwisseling van de negentiende naar de twintigste eeuw zat de verzamelingenleer in een precaire situatie. De wiskundige wereld was verdeeld in twee 20 Dit is evenwel slechts het filosofisch aspect van zijn oplossing. De technische kant zal worden besproken in het tweede hoofdstuk.
16
kampen: zij die de innovaties van Cantor hadden aanvaard en zij die Cantor’s werk als een monstrositeit beschouwden[19, p.282]. Naast de wijsgerige kritiek op het werk leek de verzamelingenleer bovendien inconsistent te zijn. De reden hiervoor was dat sommige auteurs te liberaal met verzamelingen begonnen om te springen, en bepaalde klassen als verzamelingen te zien. De eerst gepubliceerde pardox van de verzamelingenleer was Burali-Forti’s antinomie van het grootste ordinaalgetal[52, p.104]. Het is opmerkelijk dat Cantor’s opmerkingen uit 1883 over de totaliteit van de transfiniete getallen zo snel in de vergetelheid zijn geraakt. Burali-Forti gaat hier immers rechtstreeks tegen hem in, en beschouwt de totaliteit van de ordinaalgetallen als een verzameling. Veronderstel nu dat de totaliteit van alle ordinaalgetallen een verzameling is. Dan is het aantoonbaar dat deze verzameling welgeordend is met als ordetype een ordinaalgetal dat groter is dan alle ordinaalgetallen. Een tegenstrijdigheid. Burali-Forti leidde hieruit af dat de ordinaalgetallen slechts partieel geordend zijn, niet dat de na¨ıeve verzamelingeleer inconsistent is[52, p.109]. De standaardinterpretatie van dit resultaat, die stelt dat er geen grootste ordinaalgetal is, is afkomstig van Russell[47, p.323]. De paradox van het grootste kardinaalgetal verloopt analoog. Veronderstel dat er een grootste kardinaalgetal ℵΩ bestaat en bijgevolg een overeenkomstige grootste verzameling. Dan weten we wegens Cantors theorema dat de machtsverzameling van deze verzameling groter is en de kardinaliteit 2ℵΩ heeft. Maar dan is ℵΩ niet het grootste kardinaalgetal. De derde belangrijke paradox is de paradox van Russell. In tegenstelling tot de overige twe paradoxen lijkt deze niet te gaan over een te grote verzameling, maar dit is misleidend. Russell heeft aangetoond dat elke inconsistente klasse de volledige klasse van de ordinalen genereert[34, p.180]. Zoals reeds vermeld heeft Russell deze paradox ontdekt toen hij Cantor’s theorema uit 1891 probeerde te verzoenen met zijn opvatting dat er een universele klasse bestaat21 . Cantor had bewezen dat er geen enkele bijectie bestaat tussen een verzameling en haar machtsverzameling. Maar dit impliceert dat de klasse van alle klassen, die haar eigen machtsverzameling bevat, onmogelijk aan zichzelf gelijk kan zijn. Met Frege deelt Russell de overtuiging dat elke klasse ook moet kunnen optreden als een element. Wanneer we de klasse van alle elementen (Russell spreekt van terms, wij zouden zeggen objecten) aanduiden met V , en de klasse van alle klassen met U , dan bekomen we dat volgens Russell U ⊂ V . Om nu de klasse van alle klassen te bepalen definieert hij een functie {x} indien x ∈ /U f : V → U : f (x) = x indien x ∈ U Volgens Cantor bestaan er klassen die niet tot U behoren. Russell kon deze met zijn functie bepalen: het zijn de klassen {x ∈ U |x ∈ / f (x)}, wat niets minder is dan {x ∈ U |x ∈ / x}. En zo bekwam hij de klasse van alle klassen die zichzelf niet bevatten. Nu, volgens Russell moet dit een klasse zijn, wat tot een contradictie leidt. Overigens had Zermelo deze paradox onafhankelijk van Russell ontdekt, maar hij heeft er nooit zo’n dramatische consequenties als Russell aan verbonden. Zijn reactie zal in het volgende hoofdstuk worden besproken. 21 Ik
volg hier [37, pp.287-288]
17
Wat de eerste twee paradoxen minstens aantonen is dat de methodes die voor verzamelingen toelaatbaar zijn, zoals het nemen van de machtsverzameling, niet gebruikt mogen worden voor elke willekeurige klasse. Ik wil er nogmaals op hameren dat dit niet impliceert dat Cantor’s theorie inconsistent is. Het toont enkel en alleen aan dat het logicistische voorstel een slechte explicatie van de verzamelingenleer is22 . Het grote probleem voor de logicisten was dat ze moesten verklaren hoe wiskunde toepasbaar was, hoe we bijvoorbeeld sommen kunnen maken. De verzamelingenleer beschrijft slechts een deel van het universum dat Russell voor ogen had. Voor de niet-logicist is het enige probleem in dat geval een consistente formulering te geven van de oorspronkelijke Cantoriaanse idee¨en. Voor de logicist betekent dit dat de toepasbaarheid van de wiskunde onverklaarbaar wordt. De paradoxen van de klassentheorie zijn met andere woorden in de eerste plaats een probleem voor logici, niet voor wiskundigen. De Russellparadox maakt dit overduidelijk. Hoewel de bekendste formulering in termen van verzamelingen is, toont deze immers in de eerste plaats aan dat we zelf-contradictorische eigenschappen kunnen formuleren. Neem de eigenschap “niet zelfbeschrijvend zijn”, dan is het duidelijk dat wanneer dat predikaat zichzelf beschrijft dit niet het geval is en vice versa. De les die dan getrokken moet worden uit de Russellparadox is dat er regels moeten worden opgesteld die dergelijke begrippen onmogelijk maken. Maar ook in dat geval gaat het niet om een paradox die in strikte zin tot de verzamelingenleer behoort.
22 Dit kan gebruikt worden als argument tegen de stelling dat wiskunde en logica gelijk zijn. Het falen van het logicisme zou dan samenhangen met een wiskundige redeneervorm die niet zonder meer logisch genoemd kan worden. Voor de intu¨ıtionisten was dit overduidelijk zo, en hun kandidaat voor die rol was het principe van iteratie[58, p.38] en de intu¨ıtie “ en zo voort”[20, p.114] in het tweede hoofdstuk zal duidelijk worden dat dit idee niet beperkt is tot het kamp van de constructivisten.
18
Hoofdstuk 2
Moderne verzamelingenleer Eens de paradoxen aantoonden dat de oorspronkelijke hoop van Frege en Russell, dat verzamelingen betrekkelijk eenvoudige zaken zijn, de grond had ingeboord zagen wiskundigen en logici zich voor de taak geplaatst te redden wat er te redden viel. De tendens die ik in het eerste hoofdstuk heb besproken, het onderscheid tussen de eerder pragmatische aanpak van de wiskundigen en de eis van de logicisten dat alles wijsgerig acceptabel moet zijn, zal hier duidelijker dan voorheen doorwerken. Het verschil in reactie op de paradoxen is in dit opzicht nogal amusant. Het kamp dat nu intu¨ıtionistisch wordt genoemd, vertegenwoordigd door mensen als Borel, Lebesgue en Brouwer verkeerde duidelijk in een toestand van (milde) paniek en probeerde de klok terug te draaien naar de tijd van voor Cantor[34, p.251]. Daar staat het kamp van Hilbert en Zermelo tegenover die in zekere zin hun voeten veegden aan de wijsgerige problemen die volgen uit het steeds abstracter worden van de wiskunde. Met een verwijzing naar Dedekind: voor het ene kamp lijkt de hoofdvraag te zijn wat wiskundige entiteiten zijn, voor de anderen is de hoofdvraag wat we er mee kunnen aanvangen. De paradoxen hadden met andere woorden naast de wiskundige ook een filosofische rol aan de verzamelingenleer opgedrongen. Naast een instrument dat het werk in de analyse moest vereenvoudigen, waarvoor het met Cantor allemaal begonnen was, ging de verzamelingenleer ook meer en meer de rol moeten overnemen die Russell aan klassen had toegeschreven. De eerste generatie van axiomatiseringen van de verzamelingenleer zijn ontstaan vanuit een poging deze twee taken met elkaar te verzoenen. Zowel Zermelo en Russell (hun antwoord op de paradoxen werd in hetzelfde jaar, 1908, gepubliceerd) zagen een belangrijke funderende rol weggelegd voor de verzamelingenleer. De paradoxen van de verzamelingenleer hadden duidelijk gemaakt dat ook het funderend apparaat (de verzamelingenleer) met voldoende zorg behandeld moest worden opdat de remedie niet erger was dan de kwaal.
2.1 2.1.1
Zermelo, Fraenkel en Skolem Het welordeningstheorema
Op 8 augustus 1900 kreeg David Hilbert de eer om op de tweede bijeenkomst van het internationaal congres van mathematici een lezing te geven over de proble19
men die volgens hem het meest dringend om een oplossing vroegen. De verzamelingenleer was op dat moment reeds uitgegroeid tot een belangrijk instrument voor wiskundigen. Dit mag blijken uit het feit dat de continu¨ umhypothese de eerste plaats op Hilbert’s lijst bekleedde. Hilbert voorzag de eerste stap richting het juiste antwoord in een bewijs van Cantor’s bewering uit 1883 dat alle verzamelingen een welordening hebben. Vier jaar later, op het volgende congres van dezelfde vereniging gaf Julius K¨onig een bewijs dat het continu¨ um niet te ordenen is, wat een verschrikkelijke impact op Cantor had. Indien het Continu¨ um niet te ordenen is, dan is het onmogelijk dat de kardinaliteit er van uit te drukken is door middel van een transfiniet getal. In dat geval is een bewijs of een weerlegging van de continu¨ umhypothese onbereikbaar geworden. Gelukkig voor Cantor vond Felix Hausdorff snel een fout in het bewijs van K¨ onig en stond de vraag naar het welordeningstheorema terug open. Net geen twee maanden na K¨ onigs voordracht bewees Ernst Zermelo dat elke verzameling een welordening heeft[62], maar enkel en alleen met de hulp van een zeer krachtige vooronderstelling. De prijs voor het welordeningstheorema is de aanvaarding van het beruchte keuzeaxioma[38, p.491]. Zoals Zermelo later duidelijk maakte had het impliciet al een belangrijke rol gespeeld in de ontwikkeling van de verzamelingenleer, maar hij was de eerste die expliciet vermeldde dat het nodig was. De oorspronkelijke formulering luidt als volgt: ...even for an infinite totality of sets there are always mappings that associate with every set one of its elements, or, expressed formally, that the product of an infinite totality of sets, each containing at least one element, itself differs from zero[62, p.141]. Zermelo stelde zelf de vraag naar de validiteit van het principe, en misschien was er niet zoveel kritiek gekomen indien hij dat niet had gedaan.Maar met het verstrijken van de tijd werd het meer en meer noodzakelijk de gebruikte technieken te rechtvaardigen. Het keuzeaxioma leidt immers tot vreemd aandoende resultaten. Om te beginnen is het allesbehalve duidelijk hoe de welordening van de re¨ele getallen te bepalen is, hoewel er wegens Zermelo’s resultaat ´e´en is. Een tweede eigenaardigheid is dat het keuzeaxioma aanleiding geeft tot het bestaan van onmeetbare verzamelingen(De stelling van Vitali, cite[p.17]Kanamori1996). De manier waarop Zermelo zijn welordeningstheorema verdedigde verriaadde de invloed van zijn leermeester Hilbert. In [64] presenteerde hij een nieuw bewijs van het welordeningstheorema samen met een lijst van de nodige vooronderstellingen en een uitgebreide verantwoording van het keuzeaxioma. Als enige axioma’s heeft Zermelo het scheidingsaxioma nodig samen met het axioma van de machtsverzameling. Het theorema dat hij wil bewijzen is immers dat uit het keuzeaxioma het welorderingstheorema volgt, hoogstwaarschijnlijk omdat deze stelling in tegenstelling tot het keuzeaxioma algemeen aanvaard werd. Inhoudelijk is het bewijs eenvoudiger geworden door te steunen op een veralgemening van de ketens die Dedekind had gedefinieerd in het transfiniete, maar de verdediging van het keuzeaxioma blijft een probleem. De oorspronkelijke formulering is voor Zermelo niet langer aanvaardbaar aangezien ze bevlekt is door subjectiviteit en openstaat voor verkeerde interpretatie[64, p.186]. De nieuwe formulering waarvan Zermelo beweert dat het objectieve karakter er van evident is, luidt als volgt: A set S that can be decomposed into a set of disjoint parts A, B, C, . . ., each containing at least one element, possesses at least one subset 20
S1 having exactly one element in common with each of the parts A, B, C, ... considered[64, p.186]. Na dit wiskundige deel geeft Zermelo een uitgebreide verdediging van het keuzeaxioma. De nieuwe versie van het axioma had wel het voordeel dat er niet over willekeurige afbeeldingen of keuzes werd gesproken, maar dit maakte het nog niet meteen acceptabel. In de eerste plaats wijst hij er op dat het keuzeaxioma misschien wel niet bewijsbaar is, maar dat dit zeker niet zonder meer impliceert dat het ongeldig is. Bovendien is het nog niet bewezen dat het tot tegenstrijdigheden leidt, zodat het voor Zermelo een aanvaardbaar principe blijft. Bovendien is er een belangrijk punt dat in het voordeel van het keuzeaxioma spreekt en dat is de vruchtbaarheid er van. Om te beginnen stelt Zermelo dat eender welke poging tot axiomatiseren slechts kan vertrekken vanuit historische precedenten. Zermelo ziet maar een zinvolle manier om axioma’s voor eender welke tak van de wiskunde te zoeken: Evidently by analyzing the modes of inference that in the course of history have come to be recognized as valid and by pointing out that the principles are intuitively evident and necessary for science[64, p.187]. Hij wijst er vervolgens op dat het keuzeaxioma onder meer door Dedekind, Cantor en Bernstein impliciet werd toegepast en dat dit een indicator is voor de zelfevidentie en intu¨ıtieve waarheid er van. Doch hij benadrukt hierbij dat dit geen bewijs is van de waarheid. Dit kan hooguit een vertrekpunt bieden waarna rigoureuze bewijzen de zaak kunnen beslechten. Na een lijst van theorema’s die enkel bewijsbaar lijken door middel van het keuzeaxioma besluit Zermelo dat het axioma noodzakelijk is niet alleen voor de theorie van de kardinaalgetallen maar ook voor Dedekinds theorie van de natuurlijke getallen, die hij als de fundering van de rekenkunde beschouwt. Hij concludeert dan ook dat zolang er geen alternatief beschikbaar is we niet zonder het keuzeaxioma kunnen. Wiskundigen die het ontoelaatbaar vinden, zadelen zichzelf met een kunstmatig verminkte wiskunde op[64, p.189]. Zermelo wijst tenslotte op de analogie met de meetkunde door te stellen dat het keuzeaxioma a priori uitsluiten gelijk staat aan Euclidische meetkunde te verwerpen omdat het parallellenpostulaat onafhankelijk is van de andere axioma’s. Alleen door de theorie verder te ontwikkelen kunnen we haar waarde ontdekken of tot conclusies komen die ons toelaten haar te verwerpen[62, p.189]. In het bijzonder benadrukt Zermelo dat het keuzeaxioma noodzakelijk is voor het welordeningstheorema en dat de alternatieve bewijzen cruciale fouten bevatten. Jourdain had een bewijs gegeven waarin stapsgewijs een ordening wordt geconstrueerd. Welnu, om daaruit te concluderen dat elke verzameling een welordening heeft is het noodzakelijk te veronderstellen dat er telkens een laatste stap in de constructie is, wat uitgesloten is bij oneindige verzamelingen. Bijgevolg zijn de simultane keuzes die het keuzeaxioma mogelijk maakt noodzakelijk[64, p.193]. Zermelo benadrukte dat het keuzeaxioma wiskunde eenvoudiger maakt en zag daarin een voldoende grond om het toe te laten. Maar hoewel de geschiedenis Zermelo uiteindelijk gelijk heeft gegeven, was het voor velen zo dat dit een onvoldoende grond is om het te aanvaarden. Wanneer Russell in de principles het over ordes heeft, dan stelt hij dat zelfs de almacht zelve niet toelaat een verzameling te ordenen indien die niet van nature in de verzameling 21
zit[47, p.242]. Dit lijkt er op te wijzen dat hij het keuzeaxioma onaanvaardbaar moet hebben gevonden, een bewering die wordt gesteund door Russell’s latere claim dat de beste conclusie die we kunnen trekken uit Zermelo’s bewijs van het welordeningstheorema is dat het keuzeaxioma fout is[31, p.172]. Een gelijkaardige kritiek wordt gegeven door L.E.J Brouwer. Binnen zijn conceptie van de wiskunde is het zo dat we geen kennis hebben van een getal dat niet mentaal geconstrueerd is. Wel nu, aangezien we de meeste elementen van het continu¨ um nog niet hebben geconstrueerd, kunnen we ze zeker ook niet ordenen. Ieder principe dat een welordening van het continu¨ um mogelijk maakt is bijgevolg voor hem onaanvaardbaar[20, pp. 121–122]. Dergelijke kritieken, die uiteindelijk verwant zijn aan de kritieken die Cantor op de transfiniete getallen kreeg, zijn uiteindelijk evenwel niet sterk genoeg gebleken1 , waardoor de filosofie het heeft moeten afleggen van de wiskunde.
2.1.2
Axiomatische verzamelingenleer
Cantor had vanaf het begin benadrukt dat alle verzamelingen een welordening hebben. Zermelo’s axioma drukt met andere woorden een eigenschap van Cantoriaanse verzamelingen uit2 . De paradoxen van de verzamelingenleer hadden bovendien duidelijk gemaakt dat de vage manier waarop Cantor verzamelingen expliciet had gedefinieerd tot verwarring kan leiden. In het G¨otingen van Hilbert had Zermelo de kracht van de axiomatische methode geleerd zodat hij besefte dat een van de manieren om de verzamelingenleer terug credibiliteit te geven een degelijke axiomatisering was. Het belang van deze denkbeweging mag niet worden onderschat. Langs deze weg wordt de verzamelingenleer immers een wiskundige discipline eerder dan een tak van de logica. Dit betekent ook dat Zermelo een grotere vrijheid had dan bijvoorbeeld Russell die de verzamelingenleer moest inpassen in een totaalsysteem van wat hij als de enige ware logica zag. Neem bijvoorbeeld het axioma dat stelt dat er een oneindig grote verzameling bestaat. In het systeem van Zermelo zegt dit enkel iets over de betekenis van het ongedefinieerde begrip verzameling, terwijl voor Russell deze uitspraak ten eerste een empirische claim is en ten tweede dat het herleiden van alle wiskunde tot logica, net omwille van het statuut van het oneindigheidsaxioma, onmogelijk kan lukken. De beste illustratie voor het verschil in houding ten opzichte van de rol van de verzamelingenleer is Zermelo’s reactie op de Russellparadox. Zermelo had deze reeds zelf, in 1901, ontdekt, maar in plaats van er een groot probleem in te zien zag hij zijn heil in een restrictie van het verzamelingbegrip[38, p.489]3 . In [63] presenteert hij de resultaten van zijn arbeid, de eerste versie van axiomatische verzamelingenleer. In het vorige hoofdstuk is reeds duidelijk geworden dat Cantor en Dedekind eerder vaag waren geweest over wat verzamelingen 1 In Quine’s NF is het keuzeaxioma weerlegbaar(infra). Paul Bernays gaat zover te stellen dat dit een anomalie is[10, p.40], wat illustreert dat het keuzeaxioma meer dan aanvaard was. 2 Het keuzeaxioma past op een andere manier ook zeer goed in Cantors visie. Het maakt in het oneindige mogelijk wat zonder problemen kan in het eindige geval. 3 Wanneer hij het keuzeaxioma verdedigt stelde hij reeds het volgende:
..those who champion set theory as a purely mathematical discipline that is not confined to the basic notions of traditional logic are certainly in a position to avoid, by suitably restricting their axioms, all antinomies discovered until now[64, p.189]
22
zijn. Bovendien was de meest heldere definitie, die afkomstig was van Frege, de oorzaak van paradoxen gebleken. Een adequate definitie van verzamelingen lijkt Zermelo dan ook een hopeloze opgave, zodat de beste karakterisering er een is aan de hand van een aantal axioma’s die toelaten zoveel mogelijk van de bestaande verzamelingenleer te redden. Voor Zermelo is dit evenwel niet enkel van belang voor de verzamelingenleer, maar voor de gehele wiskunde. Hij stelt in zijn openingsparagraaf immers expliciet dat de verzamelingenleer nodig is om de logische fundering van de wiskunde te geven[63, p.200]4 . Merk op dat deze opvatting een omkering is van wat historisch is gebeurd: Cantor gebruikte verzamelingen als middel om over transfiniete getallen te kunnen spreken. Ik zal nu kort de verzamelingenleer van Zermelo, vanaf nu ZC genoemd, beschrijven. Ik doe dit opzettelijk niet in een formele taal aangezien de eersteorde formulering die tegenwoordig wordt gegeven niet acceptabel was voor Zermelo aangezien deze voor hem onbruikbaar was om de grondslagen van de wiskunde te geven[38, p.520, 536]. Zoals we verder zullen zien heeft Skolem net om die reden ervoor gekozen de verzamelingenleer in de eerste orde predikatenlogica te formuleren. Een tweede afwijking met de moderne formulering is dat ZC Urelemente toelaat in het domein. • De verzamelingenleer handelt over een domein β, waarover een basisrelatie ∈ tussen sommige objecten van het domein geldt. In dit domein zijn er twee basisrelaties = en ∈. De verzamelingen zijn die objecten b waarvoor geldt dat voor een zekere a geldt dat a ∈ b. Het is dan ook zo dat er objecten zijn die geen verzamelingen zijn. • Extensionaliteitsaxioma: Twee verzamelingen zijn gelijk indien ze dezelfde elementen bevatten. • Axioma van de elementaire verzamelingen: Er bestaat een lege verzameling ∅, en indien a en b verzamelingen zijn, dan {a} en {a, b} ook. • Scheidingsaxioma: Indien a een verzameling is en φ is een goedgedefinieerde eigenschap, dan is de verzameling van alle elementen x waarvoor φ(x) waar is ook een verzameling. Zermelo is onduidelijk over wat hij bedoelt met een goedgedefinieerde eigenschap. Hij zegt dat een goedgedefinieerde eigenschap een eigenschap δ is zodat de fundamentele relaties in het domein door middel van de axioma’s en de unviersele logische wetten bepalen of elk object de eigenschap heeft of niet[63, p.201]. • Axioma van de machtsverzameling: Elke verzameling a heeft een machtsverzameling ℘a die alle deelverzamelingen van a bevat. • Axioma van de unie: Indien a een verzameling is, dan vormen alle elementen van de elementen van a ook een verzameling. • Oneindigheidsaxioma: Het domein bevat minstens een verzameling waartoe ∅ behoort, en voor elke verzameling a die er toe behoort ook de verzameling {a}. 4 Zermelo
is in deze positie zeer radicaal. Voor hem zijn er geen andere wiskundige objecten. Eerder had hij bijvoorbeeld al beweerd dat Cantor’s begrippen kardinaalgetal en ordetype niet meer zijn dan uitdrukkingen voor de vergelijking van verzamelingen[64, P.193]. Men kan zich daarbij afvragen waar wiskundigen de tweeduizendvijfhonderd jaar voor Cantor mee bezig waren geweest.
23
• Keuzeaxioma: Voor elke verzameling a bestaat een keuzefunctie f die uit elke niet lege deelverzameling van a een element selecteert. Het comprehensieaxioma is sterk afgezwakt door Zermelo. In de na¨ıeve verzamelingenleer is het de garantie voor het bestaan van eender welke verzameling, maar in ZC kan het enkel deelverzamelingen van reeds geconstrueerde verzamelingen geven. Om deze reden zijn de paradoxen van de na¨ıeve verzamelingenleer niet afleidbaar. Zermelo’s elementaire verzamelingen zijn van die aard dat de kans klein is dat er ooit inconsistenties uit zullen volgen. Het achterliggende idee is dan dat de operaties die de axioma’s van de unie, de machtsverzameling en dies meer ook nooit tot een tegenstrijdigheid zullen leiden. Het belangrijkste gevolg is dat enkel relatief kleine verzamelingen bewijsbaar zijn in ZC. Zowel de universele verzameling, de verzameling van alle ordinaalgetallen als de verzameling van alle kardinaalgetallen zijn onbestaande, zodat de paradoxen van de na¨ıeve verzamelingenleer vermeden worden. Maar de slinger was iets te ver naar de andere richting doorgeslagen bij Zermelo. Ongeveer dertien jaar na de Publicatie van ZC kwam het besef dat een betrekkelijk groot deel van Cantor’s theorie van ordinaalgetallen hoewel consistent, niet afleidbaar is in de verzamelingenleer van Zermelo. Naast deze wiskundige zwakte is het ook duidelijk dat het niet onzinnig is om ZC een ad hoc collectie van generatieprincipes te noemen die de inconsistentie niet zeker kan ontlopen. Niet enkel ontbreekt het ons aan een absoluut consistentiebewijs, maar het blijkt uit Curry’s paradox dat ZC enkel geschikt is om de paradoxen die samenhangen met grote verzamelingen te vermijden. Op zich is dit niet eigenaardig. Op het moment dat Zermelo zijn axiomatisering bedacht was dit het enige probleem dat opgelost moest worden. Enkel de gekende problemen konden de oplossing helpen vormgeven. Hoewel de scheiding op dat moment nog niet zo duidelijk was, was Zermelo enkel verplicht de axioma’s van de theorie aan te passen zonder aan de achterliggende logica te tornen.
2.1.3
Het vervangingsaxioma en de geboorte van moderne ZFC
De verzameling van Zermelo verschilt op een aantal belangrijke punten van wat tegenwoordig bekend staat als de verzamelingenleer van Zermelo en Fraenkel. Een groot deel van de aanpassingen die het originele systeem heeft ondergaan hebben te maken met de funderende rol die de verzamelingenleer kan spelen. Voor Zermelo was dit zelfs de belangrijkste functie van de verzamelingenleer, een idee dat betrekkelijk lang populair was. De eerste verfijning die we kort willen toelichten is dan ook geen aanpassing van de axiomatische verzamelingenleer maar een toepassing van dit reductionisme. Russell en Whitehead hadden in hun Principia Mathematica de Relatielogica een aparte behandeling moeten geven. In 1914 stelde Norbert Wiener een definitie van geordende paren voor die ten eerste makkelijk uitbreidbaar was voor elk willekeurig geordend n-tal en ten tweede enkel steunde op verzamelingen. Wiener formuleerde zijn resultaat in het formalisme van de Principia, maar het is bruikbaar voor elke verzamelingenleer. Bovendien is dergelijke definitie uitermate geschikt om het functiebegrip te defini¨eren in de algemeenheid die het onder meer bij Cantor vanaf 1891 en Zermelo had gekregen. Wanneer we aan de hand van de definitie Wiener het functiebegrip defini¨eren, dan is het keuzeaxioma niet langer zo problematisch 24
als het oorspronkelijk leek. Een dergelijke reductionistische definitie is dus niet alleen nuttig voor wie alle wiskunde wil herschrijven in de verzamelingenleer, maar perkt ook het aantal abstracte entiteiten in dat voorondersteld wordt. Vreemd genoeg werd de innovatie van Wiener niet ge¨ıncorporeerd in de tweede editie van de Principia. De vereenvoudiging van de theorie die erdoor teweeg gebracht zou worden past nochthans mooi binnen de doelstellingen van het logicisme. Naar het waarom van de afwezigheid van deze simplificatie heb ik het raden. De enige aanwijzing richting verklaring lijkt te zijn dat Russell nooit overtuigd leek van een volledig extensionele logica5 . Naast een uitbreiding van de toepassingen (zie bijvoorbeeld [36, 2] onderging de verzamelingenleer ook intern veranderingen. De hoofdreden waarom Zermelo’s syteem in moderne gedaante zo sterk verschilt van het origineel is de precisering van “goedgedefinieerde eigenschap”. Ik roep in herinnering dat Zermelo nogal vaag was wat hiermee werd bedoeld. Abraham Fraenkel stelt in [27], een artikel waarin hij een model voor de verzamelingenleer van Zermelo beschrijft waarin het keuzeaxioma ongeldig is, voor om het scheidingsaxioma als volgt te herformuleren. Veronderstel dat φ(x) en γ(x) beiden uitdrukkingen zijn waarin naast de vrije variabele x enkel die operaties voorkomen die toegelaten worden door de axioma’s van de verzamelingenleer. Fraenkels’ versie van het scheidingsaxioma luidt dan als volgt: Indien V een verzameling is, dan heeft V een deelverzameling W van alle elementen x van V waarvoor φ(x) een element is van γ(x)[27, p.286]. Het idee blijft uiteraard hetzelfde: we kunnen comprehensie enkel gebruiken om elementen uit een andere verzameling te selecteren. Het voorstel dat het gehaald heeft, is dat van Thoralf Skolem uit 1922 [48]. Onder goedgedefinieerde eigenschappen verstond hij zinnen van de eerste orde predikatenlogica waarin naast de connectieven en variabelen enkel de symbolen ∈ en = voorkomen. Dit heeft enkele onaangename gevolgen voor de geformaliseerde theorie wanneer we het L¨owneheim Skolem theorema in het achterhoofd houden. Binnen de eerste orde formulering van de verzamelingenleer kunnen we in dat geval wel theorema’s bewijzen over overaftelbare verzamelingen terwijl er een aftelbaar oneindig model is. De situatie is evenwel nog iets erger. Dedekind had een oneindige verzameling gedefinieerd als een verzameling zodanig dat ze in een ´e’en op ´e´en afbeelding met een echte deelverzameling van zichzelf te brengen is. Welnu, door middel van de Wiener-Kuratowski definitie van geordend paar weten we dat deze afbeelding ook een verzameling is. Veronderstel nu dat we een aftelbaar model beschouwen van de verzamelingenleer, dan weten we dat daar onmogelijk alle afbeeldingen van N op N kunnen toe behoren aangezien dat een overaftelbaar aantal afbeeldingen is. Bijgevolg is er een dergelijk model zodat alle bijecties van N op een echte deelverzameling van zichzelf er niet toe behoren, en is het binnen het model niet aantoonbaar dat de verzameling van de natuurlijke getallen oneindig is. Deze redenering laat zich veralgemenen: de vraag of een verzameling al dan niet eindig is, is afhankelijk van model tot model[48, pp.295–296]. Welnu, aangezien de verzamelingenleer niet categorisch is, is ze voor Skolem niet geschikt voor de grondslagen van de 5 Later
heeft Russell expliciet het volgende gesteld:
It seemed to me-as indeed, it still seems-that, although from the point of view of a formal calculus one can regard a relation as a set of ordered couples, it is the intension alone which gives unity to the set[36, p.52].
25
wiskunde6 . In dezelfde lezing merkte Skolem op dat bepaalde verzamelingen die geldig zijn in de verzamelingenleer van Cantor niet te vormen zijn in de theorie van Zermelo. In het bijzonder is het niet bewijsbaar dat {N, ℘N, ℘℘N, ...} een verzameling is. Om dit te remedi¨eren gebruikt Skolem het vervangingsaxioma dat stelt dat de afbeelding van een verzameling ook een verzameling is. Correcter verwoord geeft dit: Vervangingsaxioma: Veronderstel dat φ(x, y) een goedgedefinieerde uitdrukking is, dat voor elke x hoogstens een dergelijke y bestaat en beschouw een verzameling a. Dan is het geheel van alle b zodat φ(x, b) met x een element van a ook een verzameling. Cantor had in zijn brief aan Dedekind een eerste vroege vorm van dit axioma gegeven, en Fraenkel had dezelfde opmerking als Skolem gemaakt in 1921. Maar zowel Fraenkel als Skolem deden er verder weinig mee. Het was Von Neumann die de volle kracht van het axioma zou begrijpen en het belang ervan zou aantonen voor de theorie van de ordinaalgetallen en het bewijs van transfiniete inductie[10, p.22]. Dit had als gevolg dat Cantor’s theorie van de transfiniete getallen de prominente plaats terugkreeg die ze onder invloed van Zermelo was kwijtgeraakt[34, p.270]. Hoewel ZFC zowat de standaardverzamelingenleer is, is de theorie zeker niet vrij van problemen. Zeker wanneer het gaat om de rol die de verzamelingenleer voor de grondslagen van de wiskunde moet betekenen, is het zo dat ZFC tekort schiet. Het probleem dat een absoluut consistentiebewijs onmogelijk is, laat ik hier verder buiten beschouwing. Het hoofdprobleem dat ik hier wil aankaarten volgt uit het feit dat de axioma’s van ZFC niet categorisch zijn. Ik volg Fraenkel in [10] in de volgende bespreking. Een eerste collectie van pathologisch aandoende verzamelingen is die van de ongefundeerde verzamelingen. Het is perfect mogelijk dat er een verzameling van de volgende vorm bestaat: ...Sk+1 ∈ Sk ∈ ... ∈ S2 ∈ S1 ∈ S0 , of een analoge circulaire verzameling (stel k gelijk aan nul). Het is niet mogelijk aan de hand van de axioma’s van ZFC een dergelijke verzameling te construeren, maar oorspronkelijk waren ze ook niet uitgesloten. Het was een van de innovaties van John von Neumann om een axioma in te voeren dat ze uitsloot(infra.) Een tweede probleem, is het bestaan van onbereikbare kardinaalgetallen en verzamelingen van een dergelijke kardinaliteit. Deze verzamelingen zijn onmogelijk te construeren aan de hand van de ZFC-axioma’s, maar zijn er wel consistent mee. Het was Felix Hausdorff die de eerste resultaten over dergelijke getallen heeft gepubliceerd(in 1908, zie [36]). Om dergelijke problemen op te lossen zou het handig zijn een axioma zoals Hilbert’s Vollst¨ andigkeitsaxiom ter beschikking te hebben. Verder zal ik bespreken waarom dit onmogelijk is. Naast deze problemen van categoriciteit is er nog een probleem van elegantie, althans voor de eerste-orde formulering. Het vervangingsaxioma en het scheidingsaxioma zijn gegeven in de vorm van een axiomaschema, waardoor ZFC niet eindig te axiomatiseren is in een eerste-ordetaal. Laat me dit illustreren aan de hand van het scheidingsaxioma (analoge beschouwingen gaan op voor het vervangingsaxioma). De eerste-orde formulering ervan luidt: (∀x)(∃y)(∀z)(z ∈ y ≡ z ∈ x ∧ φ(z)), en dit voor elke welgevormde formule φ(z) 6 Wanneer Zermelo in 1930 een nieuw voorstel doet voor de axiomatisering, dan benadrukt hij ten stelligste dat de theorie een tweede orde formulering moet krijgen, net om de verzamelingenleer haar funderende rol te laten behouden[38, par. 6].
26
van de verzamelingenleer waarin z als vrije variabele voorkomt. Aangezien een eindige formulering wenselijker is, en de eerste-orde logica de standaardlogica van de wiskunde lijkt te zijn is deze situatie onbevredigend.
2.2
Klassen en verzamelingen in NBG
Zermelo’s reactie op de paradoxen van de na¨ıeve verzamelingenleer was er een geweest van voorzichtigheid. Door comprehensie enkel toe te laten binnen verzamelingen die geconstrueerd zijn door middel van een aantal elementaire operaties, werd een belangrijk deel van Cantor’s werk onbehandelbaar. Eens de aanvankelijke paniek was weggedeemsterd onder invloed van de waarschijnlijk7 consistente axiomatisering van Zermelo kon men aanvangen met de herovering van de delen van het paradijs van Cantor die te snel verlaten waren. Het vervangingsaxioma van Fraenkel en Skolem was slechts een eerste stap die toeliet de ordinaalgetallen in hun oude glorie te herstellen. Zowel Zermelo als, zoals later zal blijken, Russell hadden door hun voorzichtigheid een aantal collecties uitgebannen die misschien wel tot paradoxen leiden wanneer ze worden behandeld als verzamelingen, maar die voorts legitiem lijken. De verzameling van alle ordinalen geeft maar aanleiding tot de Burali-Forti paradox indien we er van uit gaan dat ze zichzelf bevat8 . Cantor had een onderscheid gemaakt tussen verzamelingen en inconsistente collecties, en dat onderscheid in de reeds geciteerde brief een Dedekind gebruikt om een opmerkelijk eenvoudig bewijs voor het welordeningstheorema te geven. Voor Zermelo was een dergelijke methode onaanvaardbaar. Wat nog maar de vaagste hint van inconsistentie gaf was voor hem wiskundig onaanvaardbaar[34, p.249]. In deze sectie zullen we dan ook een verzamelingenleer behandelen die een natuurlijke uitbreiding vormt op het werk van Zermelo, Fraenkel en Skolem. NBG, de verzamelingenleer van von Neumann, Bernays en G¨odel, staat een heel eind dichter bij de theorie van Cantor. Dit betekent dat de oorspronkelijke reacties op de paradoxen misschien overdreven waren. We zullen zien dat Cantor’s oorspronkelijke theorie wel degelijk te recupereren is in een streng formeel, axiomatisch kader. Met andere woorden waren Cantor’s oorspronkelijke intu¨ıties over het transfiniete en de verzamelingenleer wel degelijk accuraat9 , wat een argument kan zijn voor wiskundig realisme. Doch, dit is niet de plaats om daar dieper op in te gaan.
2.2.1
Von Neumann’s ordinale criterium voor verzamelingen
Het is makkelijk de bijdrage van Von Neumann aan de verzamelingenleer te onderschatten. Ten eerste danken we aan hem de moderne notie van ordinaal en het bewijs van het theorema van de transfiniete recursie. Ten tweede heeft hij de verzamelingenleer van Zermelo verzoend met Cantor’s theorie van het 7 Ik gebruik waarschijnlijk bij gebrek aan beter. Het enige argument dat ik ken pro deze stelling is dat de bekende paradoxen van de verzamelingenleer niet afleidbaar zijn. 8 Dit is het kernidee van de typentheorie. 9 Een dergelijke uitspraak is uiteraard onder voorbehoud. Het is perfect mogelijk dat NBG inconsistent is.
27
oneindige. Deze twee ontwikkelingen hebben bijgedragen aan von Neumann’s uitvinding van wat nu het standaardmodel in de verzamelingenleer is. Hoger heb ik besproken hoe Cantor in private communicatie een criterium van ordinale grootte had ontwikkeld om een onderscheid te maken tussen verzamelingen en inconsistente collecties. Enkel de eerste categorie zag hij als aanvaardbare objecten van wiskundig onderzoek. Zermelo leek wegens de paradox van Burali-Forti negatief te staan tegenover het gebruik van ordinaalgetallen in wat hij zuivere verzamelingenleer noemde10 , en zijn oorspronkelijke theorie gebruikte dan ook een andere manier om te grote verzamelingen onmogelijk te maken. Alvorens over te gaan tot de bespreking van NBG dienen we uit te weiden over de invoering van de ordinaalgetallen door Von Neumann, aangezien de eerste versie van NBG Cantor’s criterium opnieuw introduceert om het onderscheid te maken tussen verzamelingen en klassen. Deze herinvoering van de transfiniete getallen is overigens niet alleen van belang voor de axiomatisering van NBG, maar ook voor de standaardinterpretatie van de verzamelingenleer. Von Neumann’s definitie van de ordinalen betekende de rehabilitatie van Cantor’s theorie van de tranfiniete getallen. In de grundlagen leek Cantor er van uit te gaan dat de transfiniete getallen iets zegden over de structuur van het wiskundig universum. Von Neumann heeft dezelfde stap gezet en een model gegeven van de verzamelingenleer dat steunde op de manier waarop Cantor het domein van het oneindige zag. Cantor had de transfiniete getallen ge¨ıntroduceerd aan de hand van een uitbreiding van het tellen tot voorbij de eindige getallen, en dit als een onderdeel van zijn theorie van ordetypes[30, p.84]. De ordinaalgetallen werden door Cantor gedefinieerd als de ordetypes van de welgeordende verzamelingen. Later verduidelijkte hij dat de ordetypes ontstaan door een daad van abstractie, en Dedekind was hem daarin gevolgd door te stellen dat de natuurlijke getallen volgen door van eenvoudig oneindige verzamelingen abstractie te maken van alles behalve de structuur van de verzameling. In moderne terminologie kunnen we dit psychologisch taalgebruik best vermijden door te spreken over equivalentieklassen van welgeordende verzamelingen. Een dergelijke definitie is moeilijk toepasbaar binnen bijvoorbeeld de theorie van Zermelo, aangezien daarin geen universele verzameling bestaat en bijgevolg de mogelijkheid te spreken over de verzameling van alle verzamelingen met een zeker ordetype afwezig is. Von Neumann’s innovatie bestaat uit twee deelaspecten. In de eerste plaats definieert hij de ordinaalgetallen niet als equivalentieklassen maar als een zekere canonieke representant uit de equivalentieklasse. Ten tweede beschouwt hij elk ordinaalgetal als de verzameling van alle voorgangers ervan, zodat hij een opvolgersfunctie voor ordinaalgetallen bepaalt. De presentatie van deze theorie, [53, 57], is geformuleerd in de na¨ıeve verzamelingenleer, maar kan makkelijk worden vertaald naar een axiomatische verzamelingenleer11 . Uiteraard is de 10 In
[64, p.192] lezen we bijvoorbeeld Already in my 1904 proof [...] I avoided not only all notions that were in any way dubious but also the use of ordinals in general; I clearly restricted myself to principles and devices that have not yet by themselves given rise to any antinomy.
11 Het idee dat von Neumann uitwerkt is niet nieuw. Philip Jourdain werkte in zijn correspondentie met Russell een voorloper van de theorie uit[31, p.85 ev.], en ook Zermelo moet (althans volgens Paul Bernays, zie [4, p.6]), met een analoog idee hebben gespeeld.
28
keuze van een representant uit een equivalentieklasse willekeurig, maar in het specifieke geval van de ordinaalgetallen is het mogelijk een zeer economische en elgante representant te kiezen. Want veronderstel dat we nul defini¨eren als de lege verzameling, dan ontstaat volgende reeks: ∅ {∅} {{∅}, ∅}
0 1 2 ... ω
= = =
12 Zo
adequaat als G¨ odels onvolledigheidstheorema dat toelaat uiteraard.
= {∅, {∅}, {∅, {∅}}, ...} Deze definitie heeft twee voordelen: ten eerste wordt de relatie die de ordinaalgetallen ordent de relatie ∈, zodat een theorie over ordes en geordende verzamelingen overbodig wordt voor de theorie van de ordinaalgetallen en ten tweede is de opvolgersfunctie voor ordinaalgetallen zeer eenvoudig de functie S(x) = x ∪ {x}. Een interessant gevolg van deze definitie is dat het verband tussen verzamelingen en de veralgemeende getaltheorie van Cantor terug overduidelijk wordt. Later zal Paul Bernays benadrukken dat de theorie van de ordinaalgetallen al mogelijk wordt gemaakt onder minimale vooronderstellingen over het bestaan van verzamelingen[4, p.6]. De hierboven geschreven invoering van de ordinaalgetallen kan evenwel niet werken in de theorie van Zermelo. Er is immers geen garantie dat er voor elke verzameling een dergelijke ordinaal bestaat, tenzij het vervangingsaxioma van Fraenkel en Skolem wordt toegevoegd aan de theorie[34, p.275]. Dat laat toe om door middel van transfiniete inductie aan te tonen dat deze eigenschap geldt. In dat geval is het relatief eenvoudig een nummeringsfunctie te defini¨eren. Ik volg von Neumann [53, p.348]. Beschouw een welgeordende verzameling M en een willekeurige functie f die gedefinieerd is voor alle elementen van M . Dan is de verzameling M = {x||x = f (y), met y ∈ M } wegens het vervangingsaxioma ook een verzameling. Noem S(z, M ), het segment van z in M, de verzameling {x||x = f (y), met y ∈ M die voor z in de welordening van M } komen. Nu kunnen we als volgt een functie f bepalen die de elementen van M nummert: f (x) = {y||y ∈ M en y ∈ S(x, M )}. Von Neumann bewijst vervolgens dat een dergelijke nummering uniek is, dat ze de reeds vermelde eigenschappen heeft en dat dergelijke nummeringen eigenschappen hebben die ze geschikt maken om te dienen als ordinalen. Deze theorie sluit in feite een cirkel die begonnen is in het eerste hoofdstuk met de theorie van Dedekind en de hoop van Cantor om de getallenrij maximaal uit te breiden. Het is immers mogelijk om te bewijzen dat het inductietheorema van Dedekind uitbreidbaar is over alle von Neumann ordinalen, zodat langs de ene kant Dedekind wel degelijk een adequate12 beschrijving van de natuurlijke getallen heeft gegeven en langs de andere kant Cantor’s transfinieten een natuurlijke uitbreiding vormen op de theorie van de natuurlijke getallen. Mits het keuzeaxioma (of een van de vele equivalente eigenschappen) en het vervangingsaxioma tot een axiomatisering van de verzamelingenleer behoren, heeft elke verzameling een von Neumann-ordinaal. Het ligt dan ook min of meer voor de hand om deze idee om te keren en de verzamelingen te axiomatiseren op een manier zodat ordinale nummering een noodzakelijke voorwaarde is om tot het domein van de verzamelingen te behoren. Deze terugkeer naar de
29
Cantoriaanse eis dat verzamelingen minstens een machtigheid moeten hebben is dan ook een van de centrale punten van de oorspronkelijke axiomatisering van NBG. De versie geformuleerd door John von Neumann in 1925 [54, 56] en verfijnd door Raphael Robinson in [45] gebeurde in termen van functies. De reden waarom men functies hanteerde in plaats van verzamelingen is tweeledig. De eerste reden is historisch gegroeid en hangt samen met de invoering van het vervangingsaxioma en de precisering van Zermelo’s goedgedefinieerde eigenschappen. Fraenkel had goedegedefinieerde eigenschappen gelijk gesteld aan functies, wat vervolgens door Skolem uitgebreid werd naar willekeurige eersteorde uitspraken. Maar zelfs in het geval dat Skolem’s versie van ZFC wordt gebruikt is het zo dat het functiebegrip via het het axiomaschema van vervanging in de theorie binnensluipt. Nu is het uiteraard nog steeds mogelijk om verzameling als primitief concept te nemen en daar vervolgens een theorie over functies aan toe te voegen, maar het is veel economischer om vanaf het begin een axiomatisering van functies te geven[56, p.396]. Bovendien wordt op die manier het “verdachte” klassenbegrip uit de theorie geweerd. Von Neumann stelde zich tot doel door middel van een eindig aantal axioma’s een aantal operaties te voorzien zodat alle verzamelingen die niet tot paradoxen leiden construeerbaar zijn binnen zijn systeem [54, p.396]. Deze axiomatisering valt uiteen in twee aspecten. De eerste groep axioma’s bestaat uit de constructieprincipes voor functies en volgt de lijn van ZF. Eerder dan een opsomming te geven van deze groep zal ik me dan ook concentreren op de kern van de zaak, het axioma IV.2. In casu gaat het om de voorwaarde waaraan een functie moet voldoen om ook op te kunnen treden als een argument. In von Neumann’s formulering luidt het als volgt: A II-object a is not a I-II-object if and only if there exists a II-object b such that for every object I-object x there exists a y for which both [a, y] 6= A and [b, y] = x[54, p.400]. Wat het zegt is dat een klasse slechts gerepresenteerd wordt door een verzameling indien het niet zo is dat ze even groot is als de universele klasse. De paradox van Burali-Forti had aangetoond dat de klasse van alle ordinalen geen verzameling was, zodat het er weinig toe doet of we nu stellen dat de universele klasse of de klasse van alle ordinalen niet af te beelden mag zijn op een klasse. Cantor had al met dit idee gespeeld, maar nu krijgt het een degelijke formulering. Dit is een zeer sterk axioma dat veel van de mogelijkheden van het na¨ıeve comprehensieschema recupereert. Russell heeft aangetoond dat een inconsistente verzameling een generator voor de verzameling van alle ordinalen genereert[34, p.180], zodat dit axioma garandeert dat alles wat een verzameling kan zijn ook tot het domein van de verzamelingen gerekend kan worden. Von neumann’s axioma combineert het scheidings- en vervangingsaxioma en zorgt voor een manier om om te gaan met verzamelingen die zeer groot zijn. Bovendien wordt het keuzeaxioma erdoor overbodig om het welordeningstheorema te bewijzen[54, p.400]. Want veronderstel dat er een verzameling x bestaat die geen welordening heeft, dan heeft x ook geen ordinaalgetal, of anders gezegd is x groter dan de klasse van alle ordinaalgetallen. Aangezien deze klasse evenwel geen verzameling is, kan x ook geen verzameling zijn, waaruit het gestelde volgt[54, p.398]. Von Neumann beweert dat deze methode ligt in de lijn van Zermelo’s ide¨een, maar dit lijkt een misvatting te zijn. Zermelo’s axioma’s steunen in de eerste 30
plaats op een iteratieprincipe[11, p.219], terwijl NBG eerder lijkt op een selectieprocedure voor wiskundig bruikbare klassen. Dit zal verder nog duidelijk worden. Toch speelt von Neumann met een vroege conceptie van de cumulatieve hi¨erarchie, op zich een combinatorische opvatting over de verzamelingenleer, wanneer hij de modellen voor zijn axioma’s onderzoekt in het tweede deel van zijn [54], een onderzoek waaruit hij verregaande filosofische conclusies trekt. Hoger hebben we al kort gealludeerd op Fraenkel’s hoop op een verzamelingtheoretisch equivalent van Hilberts volledigheidsaxioma voor de meetkunde (Axiom der Beschr¨ anktheit). Na een poging tot exacte formulering van een dergelijk Axiom der Beschr¨ anktheit komt von Neumann tot de conclusie dat dit zou moeten steunen of op een complexere verzamelingenleer, of op de na¨ıeve verzamelingenleer. Daar komt nog bij dat zelfs in dat geval de mogelijkheid bestaat van wat men tegenwoordig aanduid als inner models (denk bijvoorbeeld aan ZC en ZC aangevuld met het funderingsaxioma). Von Neumann is dan ook overtuigd van de onmogelijkheid van een dergelijk axioma13 . For these reasons we believe that we must conclude, first, that the axiom of restriction absolutly has to be rejected and, second, that one can’t possibly succeed in formulating an axiom to the same effect[54, p.405]. Ondanks deze kleine kans op een categorische interpretatie van de axioma’s die hij heeft gegeven, probeert von Neumann dan toch minstens een categorisch deelmodel te bepalen. Daartoe voert hij volgende inperkingen in[54, pp.411412]: 1. Alle objecten van het domein zijn verzamelingen. 2. De oorspronkelijk niet nader gedefinieerde objecten A, B en de paren (u, v) zijn respectievelijk ∅, {∅} en {{u}, {u, v}}. 3. Het funderingsaxioma is waar in het beschouwde model. 4. Het model is iteratief opgebouwd. Dit is het model van de cumulatieve hi¨erarchie, het huidige standaardmodel van de verzamelingenleer dat ook naar voor werd geschoven door Zermelo en wat we later zullen bespreken. Maar zelf voor deze interpretatie vreest von Neumann het ergste, voornamelijk omdat een rijkere verzamelingenleer nodig is om een beperkingsaxioma te geven. Uit dit alles trekt hij negatieve filosofische conclusies. In het licht van het L¨owenheim-Skolem theorema zou men kunnen concluderen dat een categorische verzamelingenleer enkel aftelbare modellen heeft. Dit kan worden ge¨ınterpreteerd als een argument tegen de klassieke en voor een 13 Een
dergelijke skepsis over axiomatische verzamelingenleer hebben we reeds aangetroffen bij Skolem. In verband met het L¨ owenheim-Skolemtheorema merkt von Neumann overigens het volgende op: In these systems, all know cardinalities occur, in their infinite multiplicity, which is larger than any cardinality. But as soon as one applies finer instruments of investigation (”higher” systems P) all this fades away to nothing. Of all the cardinalities only the finite ones and the denumerable one reamain. Only these have real meaning; everything else is formalistic fiction[54, p.408]. Het is betrekkelijk ironisch dat de man die het werk van Cantor nieuw leven heeft ingeblazen het vertrouwen van deze laatste in de kracht van de theorie niet langer kon hebben.
31
intu¨ıtionistische. Von Neumann merkt evenwel terecht op dat het argument van Skolem dat oneindige verzamelingen slechts een relatieve betekenis hebben ook gebruikt kan worden tegen eindige verzamelingen. Anders gezegd is het in principe mogelijk dat een bepaalde verzameling in de ene interpretatie eindig is en in een andere aftelbaar oneindig. Dit heeft uiteraard zeer onaangename gevolgen wanneer we de verzamelingenleer willen gebruiken voor de grondslagen van de wiskunde. In een eerste-orde taal14 zullen we op geen enkele manier een categorische formulering van de verzamelingenleer kunnen geven, waardoor het oorspronkelijke doel van Frege en Russell, de wiskunde een stevige basis in de verzamelingenleer geven, onbereikbaar wordt.
2.2.2
De verzamelingenleer van Paul Bernays
Net zoals Zermelo was Bernays een leerling van Hilbert, maar waar Zermelo’s[63] de geest van Hilbert’s Grundlagen der Geometrie uitademt, treffen we in het werk van Bernays de teneur aan van Hilbert’s project uit de twintiger jaren. Dit is begrijpelijk aangezien Bernays als assistent van 1917 tot 1933 mee aan de wieg stond van de metamathematica, en de impact op zijn werk is duidelijk[61]. Bernays heeft zijn axiomatisering van de verzamelingenleer gepresenteerd in een serie artikels[3, 4, 5, 6, 7, 8, 9] en een monografie [10]. Ik zal me in deze afdeling concentreren op de manier waarop Bernays verzamelingen begrijpt, zonder al te veel in te gaan op technische details. Bernays is de laatste auteur die ik zal behandelen die voortwerkt in de traditie begonnen door Cantor, en aan de hand van het von Neumann universum zal ik trachten aan te tonen dat de logicistische droom en de Cantoriaanse traditie van verzamelingenleer onverzoenbaar zijn gebleven. De theorie van Bernays is een erfgenaam van die van von Neumann in de zin dat ze een onderscheid maakt tussen twee fundamentele begrippen namelijk klassen en verzamelingen. Onder invloed van Hilbert was de eerste orde-logica de standaardtaal van de wiskunde aan het worden en een van de doelstellingen is dan ook dat de axiomatisering formaliseerbaar moet zijn in die logica. Dit laat meteen toe om, via de methode van Skolem, de “goedgedefinieerde eigenschappen” van Zermelo te bepalen. In het geval van ZFC leidt dit tot een oneindige axiomatisering, maar Bernays slaagt er in zijn theorie op een eindige manier te axiomatiseren. Om dit te realiseren laat hij klassen de rol spelen van de eigenschappen en functies die het scheidings - en vervangingsaxioma gebruiken maar gebruikt hij in plaats van het comprehensieschema een eindig aantal instanties er van. Vervolgens toont hij aan dat eender welke klasse die te vormen is aan de hand van comprehensie ook beschikbaar is door combinatie van zijn axioma’s[3, p.72]. De verzamelingen worden bepaald door modificaties van Zermelo’s axioma’s, von Neumann’s principe van de te grote verzamelingen wordt dus verlaten (hoewel het afleidbaar is[10, p.208]). Bernays’ betrachting is zoveel mogelijk van de kracht van de verzamelingenleer van von Neumann bewaren, maar deze om te zetten naar een verzamelingenleer die beter aansluit bij het systeem van Zermelo[3, p.65]. Functies en functies die kunnen optreden als argument worden dan ook vervangen door respectievelijk klassen en verzamelingen. Een klasse is de extensie van 14 Hogere orde logica’s kunnen geen oplossing bieden, de problemen van de verzamelingenleer worden in dat geval enkel verplaatst naar de logica.
32
een predikaat, maar de verzamelingen hebben bovendien de eigenschap dat ze een veelheid zijn die een ding vormt (a multitude forming a proper thing[3, p.66]). Dit idee vonden we reeds terug bij Cantor en wordt formeel gerepresenteerd door de onmogelijkheid van een klasse om als element van een klasse of verzameling op te treden. Bernays ziet twee manieren om uit de impasse van de na¨ıeve verzamelingenleer te raken. De eerste manier, onderscheid maken tussen verschillende soorten klassen, is die van de typentheorie. Bernays ziet meer heil in het onderscheid te maken tussen de extensie van een predikaat en verzamelingen: (Then) we have the advantage that the operation of forming a class {x|U (x)} from a predicate U (c) can be taken as an unrestricted logical operation, not depending on a specyfing comprehension axiom. But from this we have to separate the mathematical processes of set formation which in the way of Cantor are performed as generalizations of our intuitive operations of finite collections[10, p.42, cursivering niet in origineel]. Bernays maakt een onderscheid tussen logische en wiskundige operaties. Verzamelingen, die volgens hem overigens de enige wiskundige objecten zijn, steunen blijkbaar op meer dan de predikatenlogica terwijl klassen behoren tot de logische grammatica van de verzamelingenleer en best beschouwd kunnen worden als ide¨ele objecten[10, p.42, 56]. De vraag naar wat Bernays bedoelt met het specifieke wiskundige aan verzamelingen voert ons terug naar de Cantoriaanse theorie van de transfiniete getallen. Bernays begint zijn axiomatisering van verzamelingen in [10] door te stellen dat het basisidee van zijn verzamelingenleer is dat de constructie van verzamelingen parallel verloopt aan de generatieprocedures die Cantor in de Grundlagen had beschreven. De opvolgersfunctie en de limiet van een getallenrij corresponderen in Bernays’ axiomatisering met een axioma dat toelaat aan een verzameling een element toe te voegen resp. het axioma van de unie[10, p.65]. Het extra ingredi¨ent dat de verzamelingen moet scheiden van klassen is blijkbaar iteratie, een idee dat ver van nieuw was bij Bernays. Het vormde immers de kern van Cantor’s hoger geciteerde kritiek op Frege. Het is nuttig terug even stil te staan bij de cumulatieve hi¨erarchie, het model van de verzamelingenleer dat von Neumann heeft beschreven en dat als ik me niet vergis een standaardmodel van de verzamelingenleer is. Het model steunt op een iteratieve procedure en veronderstelt dat de transfiniete ordinalen aanvaardbaar zijn en steunt op transfiniete recursie en wordt als volgt gedefinieerd: V0 is de lege verzameling. Voor elk ordinaalgetal α, Vα+1 = ℘(Vα ) (2.1) Voor elke limietordinaal β, Vβ =
[
℘(Vα )
(2.2)
α<β
Voor ZFC bepaalt dit verschillende modellen Vi , voor NBG is het mogelijk de universele klasse te vormen als de unie van alle dergelijke verzamelingen. Mijn inziens toont dit model aan dat de verzamelingenleer niet geschikt is om de 33
grondslagen van de wiskunde te geven en wel om twee redenen. Ten eerste is het nemen van de machtsverzameling impredikatief en ten tweede worden de transfiniete getallen veronderstelt. Ik wil de legitimiteit van deze principes niet aanvechten, maar het is na¨ıef te stellen dat langs deze weg wiskunde een filosofisch aanvaardbare fundering heeft gekregen. Beide problemen tonen immers aan dat de verzamelingenleer teveel steunt op een realistische visie op de wiskunde. Bovendien mag het duidelijk zijn dat elke poging de wiskunde te vertalen naar de verzamelingenleer niets anders is dan de kar voor het paard te spannen. Indien we Bernays volgen in zijn opvatting dat de iteratieprocedure het sleutelkenmerk van wiskundig denken is, dan veronderstelt de verzamelingenleer dat wat ze net moet aantonen. Het is vanzelfsprekend dat bijvoorbeeld de structuur van de natuurlijke getallen te beschrijven is aan de hand van een theorie waarvan het standaardmodel opgebouwd is aan de hand van de transfiniete getallen. Bernays bespreekt dit model in [8] en bewijst dat het funderingsaxioma voor zijn systeem impliceert dat elke verzameling behoort tot de cumulatieve hi¨erarchie. Hieruit kan hij dan weer het axioma van de te grote verzamelingen van von Neumann afleiden. Met de cumulatieve hi¨erarchie sluiten we dus weer aan bij Cantor’s opvattingen over verzamelingen. Het idee van welordening behoort er fundamenteel toe, maar wat met die tweede grote vraag van Cantor, de continu¨ umhypothese? Kurt G¨odel heeft aangetoond dat voor de cumulatieve hi¨erarchie geldt dat de veralgemeende continu¨ umhypothese geldt. Langs de andere kant laten de ZFC en NBG nog andere verzamelingen toe, met het gevolg dat de continu¨ umhypothes onbeslisbaar is tenzij er axioma’s aan de respectievelijke theorie¨en worden toegevoegd[36, p.40]. In zekere zin wordt zo een cirkel gesloten. Cantor begint het oneindige te onderzoeken maar komt, ondanks de nieuwe methodes die hij heeft ontwikkeld, relatief snel in de problemen ten gevolge van de Continu¨ umhypothese. Bovendien wordt de notie verzameling verdacht gemaakt door tegenstrijdigheden. Zermelo slaagt er wel in de verzamelingenleer te rehabiliteren, maar angst voor het tranfiniete zorgt er voor dat hij afstand doet van een deel van de Cantoriaanse theorie. Von Neumann heeft evenwel aangetoond dat de paradoxale eigenschappen van de klasse van alle ordinalen positief kon worden aangewend, waarna Bernays deze theorie opnieuw heeft geformuleerd in de taal van Zermelo. De oorspronkelijke motivatie van Cantor, de studie van het transfiniete, bleek zoals duidelijk gemaakt in de cumulatieve hi¨erarchie diep geworteld in de wiskundige conceptie van de verzamelingenleer.
2.3
De Typentheorie
De vraag die Zermelo heeft trachten te beantwoorden was de vraag welke verzamelingen mogen bestaan opdat de verzamelingenleer consistent zou zijn. De leidraad voor het opstellen van zijn axioma’s was een analyse van de historisch gegroeide praxis van de wiskundigen en hoopte dat een consitentiebewijs de validiteit zou garanderen. Dit houdt in dat er een scheiding wordt gemaakt tussen de axioma’s van de verzamelingenleer als wiskundige component en de achterliggende logica. Een dergelijk vertrouwen in de praktijk van de volgelingen van Cantor kon Bertrand Russell niet opbrengen. Het was voor hem duidelijk dat de paradoxen 34
op een fundamenteler niveau moesten worden opgelost. In zijn correspondentie met Phillip Jourdain uit 1905 stelt hij dat de oplossing voor de Burali-Forti paradox moet worden gezocht in de grondslagen van de wiskunde in plaats van in technische wiskundige spitsvondigheden[31, p.49]. De hoofdreden voor zijn werk bleef immers het bewijzen van de stelling dat de wiskunde een tak van de logica vormt, wat haar een zekere en betrouwbare wetenschap maakt. Waar Zermelo zich kon behelpen met een restrictie van de na¨ıeve verzamelingenleer door middel van die axioma’s die nog geen paradoxen hebben opgeleverd, zat Russell vast aan het idee dat klassen bepaald moesten worden door concepten. Wat Russell nodig had was een criterium dat moet toelaten de aanvaardbare predikaten te scheiden van die die een inconsistente klasse bepalen. Zijn blik was gericht op een nobeler doel dan dat van Zermelo: hij was niet van plan slechts een aantal regels op te stellen zodat de praktijk van een groep wiskundigen werd gerechtvaardigd maar een theorie te ontwerpen die het onmogelijk moet maken onzin te verkondigen.
2.3.1
De typentheorie van Russell
As to the finding of criteria for inconsistent aggregates, and as to how to treat such aggregates, probably generations will be necessary[31, p.25]. Russell schreef dit in 1904, en het drukt goed uit hoe wanhopig de situatie voor het logicisme er op dat moment uitzag. Toch had Russell al een mogelijke oplossing gevonden, maar hij was er niet van overtuigd dat ze subtiel genoeg was[47, p.523]. Russell had immers de typentheorie reeds naar voor geschoven in the principles. Hij maakte een onderscheid tussen de class as one en class as many, wat niets anders lijkt te zijn dan het onderscheid tussen verzamelingen en klassen in NBG. Het idee dat deze twee ontologische categori¨en samenvallen moet worden opgegeven. We took it as axiomatic that the class as one is to be found whenever there is a class as many; but this axiom need not be universally admitted, and appears to have been the source of the contradiction[47, p.104]. Russell’s voorstel is om het onderscheid tussen de twee uit te drukken aan de hand van het type. Een verzameling is steeds van hetzelfde logische type als de elementen die er toe behoren, terwijl de klasse van een hoger logisch type is dan zijn elementen. Een klasse kan dus onmogelijk tot zichzelf behoren. In zijn besprekling van Frege’s opvattingen is Russell duidelijker: indien we de mogelijkheid willen bewaren te spreken over klassen, dan is een onderscheid nodig tussen termen 15 , klassen, klassen van klassen, enzovoorts[47, p.517]. Naast een formulering van de typentheorie als klassentheorie behandelt Russell haar ook als theorie van propositionele functies[47, pp.523–528]. De reden hiervoor is de blijvende spanning in zijn werk tussen intensie en extensie. Klassen behoren tot het domein van het extensionele terwijl propositionele functies eigenschappen uitdrukken en dus met intensie te maken hebben. Een propositionele functie φ(x) heeft volgens Russell naast een waarheidsbereik, de 15 Die
dingen die in mooi nederlands urelemente worden genoemd
35
extensie er van, ook een betekenisbereik. Enkel voor variabelen a die binnen het betekenisbereik van φ(x) vallen is φ(a) een propositie. Dit laat Russell toe om de het na¨ıeve comprehensie-axioma te bewaren, alleen zullen sommige uitdrukkingen die over klassen gaan betekenisloos worden. Een type is niets meer dan een betekenisbereik en is, net wegens de aanwezigheid van comprehensie, gelijk te stellen aan een klasse. Het grote verschil is evenwel dat de type-restrictie de klassen opdeelt in een rangorde. Op het laagste niveau staan de individuele elementen van het domein, het tweede type zijn de klassen van elementen etc. en analoge regels gelden voor relaties. De finale versie van de typentheorie, de versie die aangewend is in de Principia Mathematica, verschilt op een belangrijk punt van de versie van de Principles. De paradoxen hadden hem duidelijk gemaakt dat het beter is te stoppen met het verwijzen naar klassen. Het was de verwijzing naar extensies, naar klassen dus, die er voor had gezorgd dat monsters zoals de verzameling van alle verzamelingen die niet tot zichzelf behoren mogelijk werden. Bovendien betekent het comprehensie-axioma niet meer dan dat telkens wanneer een klasse wordt gebruikt er een equivalente uitdrukking is over propositionele functies. Het finale ingredi¨ent was de techniek van het parafraseren die Russell in On Denoting heeft uitgewerkt[43, p.660]. Die techniek laat toe alle uitspraken over klassen te herleiden naar uitspraken over propositionele functies, waarbij klassen in principe overbodig worden[24, p.40, 75]. Russell heeft de mature typentheorie uiteengezet in Mathematical logic as based on the Theory of types. Het artikel begint met een opsomming van de paradoxen die de theorie moet oplossen. De typentheorie moet niet enkel de klassentheorie uit de impasse van de paradoxen van Russell en Burali-Forti helpen, maar ook de leugenaarsparadox en Richard’s paradox moeten erdoor verholpen worden16 . Russell legt het probleem bij de zelfreferentie waarvan sprake is in deze paradoxen. In het bijzonder wordt er iets beweerd over alle elementen van een verzameling zodat de bewering zowel klopt als niet klopt[46, p.224]. Dit is het grote breukpunt met de reeds besproken versies van de verzamelingenleer. Daar werd het verzamelingenbegrip ingeperkt teneinde niet in contradicties te vervallen, terwijl Russell een herinterpretatie zoekt van alle. Wanneer we spreken over de verzameling van alle verzamelingen die zichzelf niet bevatten, wat is dan de logische betekenis van alle? In de principles was het duidelijk geworden dat wanneer het bereik van de universele quantor werkelijk alles beslaat paradoxale resultaten afleidbaar worden. De typentheorie is dan ook een codificatie van een heel ander probleem dan dat wat de axiomatische verzamelingenleer heeft opgelost. Zermelo had geprobeerd te axiomatiseren wat verzamelingen zijn. Aangezien Russell moest blijven vertrekken van klassen bepaald door eigenschappen, was zijn invalshoek de vraag wat een klasse mag bevatten 17 . 16 Ik denk dat de verklaring hiervoor moet worden gezocht in Russell’s idee van De Logica, en het probleem dat Logica als een totaalsysteem moet worden beschouwd [29, p.]. Russell probeert aan de hand van ´ e´ en methode, een regel van De Logica, een familie van paradoxen op te lossen die tegenwoordig op een verschillende manieren worden aangepakt. De Russell- en Burali-Forti paradox worden weggewerkt aan de hand van een axiomatisering van de verzamelingenleer, de leugenaarsparadox door middel van het onderscheid tussen objecttaal en metataal en Richard’s paradox verdwijnt bij het onderscheid tussen de syntax van het systeem en de interpretatie er van. Russell’s typentheorie heeft duidelijk het voordeel van de elegantie. 17 Uit het extensionaliteitsaxioma volgt dat wat een klasse is en wat ze bevat gelijkvalt.
36
Het probleem met de zelfreferenti¨ele paradoxen is volgens Russell dat ze handelen over een collectie die uitbreidbaar is door te refereren naar haar totaliteit. Dit is het duidelijkst in het geval van de Burali-Forti paradox: indien de totaliteit van alle ordinalen een verzameling is, dan ontstaat een nieuw ordinaalgetal. Analoge beschouwingen gelden voor de andere paradoxen: door te spreken over alle klassen of door alles wat definieerbaar is aan de hand van x, ontstaan nieuwe gevallen die andere eigenschappen hebben dan de elementen van de totaliteit waarnaar verwezen wordt. Russell’s conclusie is dan ook dat de sleutel tot de oplossing van de paradoxen het vicious-circle principle is: Whatever involves all of a collection must not be one of the collection[46, p.225]. Deze stelling brengt Russell op twee manieren in de problemen. Ten eerste maakt het vicious-circle principle het onmogelijk om te spreken over logica. Russell maakt immers geen onderscheid tussen zijn logica en de metasystematische eigenschappen ervan, waardoor het opstellen van de axioma’s een problematische aangelegenheid wordt. Aangezien Russell geen onderscheid maakte tussen objecttaal en metataal is het formuleren van de axioma’s van zijn systeem vergelijkbaar met Baron von M¨ unchhausen toen hij zichzelf uit een moeras redde door zich er uit te trekken aan zijn eigen haar. Zijn oplossing voor dit probleem bestond eruit dat axioma’s enkel vrije variabelen mogen bevatten. De vraag of dit een bevredigende oplossing is laat ik open. De typentheorie van 1908 is een complexere theorie dan die uit de principles. De theorie van de principles was enkel bedoeld om de paradoxen van de klassentheorie op te lossen. Een logisch type is nog steeds het domein waarvoor een propositionele functie een waarheidswaarde heeft. Het grote verschil met de originele theorie is de manier waarop een type bepaald wordt. In de originele theorie was het de vrije variabele van de propositionele functie die het type van een klasse bepaalde. Dit aspect, de opdeling in types die verantwoordelijk is voor het verschil tussen klassen, klassen van klassen etc., blijft bewaard maar wordt aangevuld met een opdeling in ordes. Om de paradoxen van de leugenaar en Richard op te lossen was het nodig propositionele functies ook te verdelen op basis van de gebonden variabelen die erin voorkomen, en het zijn dergelijke variabelen die de orde van een propositie bepalen18 . De typenhi¨erarchie wordt nu als volgt bepaald: Type n + 1 bestaat uit de proposities van orde n die enkel gebonden variabelen van orde ten hoogste n − 1 bevat. Voor de klassentheorie betekent dit dat het onmogelijk wordt een klasse te defini¨eren aan de hand van een klasse waartoe ze behoort. Een definitie van een wiskundig object die gebruik maakt van een totaliteit waartoe het behoort wordt een impredikatieve definitie genoemd. Het vicieuse cirkelprincipe verbied dergelijke definities, waardoor Russell in de problemen komt. In de klassieke wiskunde zijn dergelijke definities immers niet ongebruikelijk. Zermelo’s scheidingsaxioma berust duidelijk op impredikatieve methodes, en ook in de analyse komen dergelijke definities voor (denk bijvoorbeeld aan het maximum van een functie). De theorie van ordes maakt het onmogelijk die te recupereren. Hermann Weyl heeft in Das Kontinuum een poging ondernomen De no-class theory laat evenwel toe dit onderscheid te recupereren. Finaal draaide Russell’s logica om intensies. 18 Ter illustratie: “Alles wat ik zeg is onwaar” is binnen de typentheorie een tweede ordeuitspraak waarin gesteld wordt dat alle eerste-orde uitspraken uitgesproken vals zijn.
37
de analyse predikatief op te bouwen vertrekkend vanaf de natuurlijke getallen. Maar hij beseft dat hij langs deze weg een deel van de klassieke analyse verloren zal gaan[58, p.1]. Russell wil van een lager niveau beginnen, hij moet eerst nog de natuurlijke getallen defini¨eren en bovendien aantonen dat alle wiskunde te herleiden is tot logica. Een parti¨ele, want predicatieve, reductie is voor hem dus onaanvaardbaar. De restrictie tot predikatieve definities was inderdaad te streng voor hem. Eerst en vooral maakt het de definitie van Leibniz voor de identiteit onmogelijk. Het is immers slechts mogelijk te spreken over de eigenschappen van orde n, waardoor zeggen dat twee objecten alle eigenschappen gemeen hebben onmogelijk wordt. Ten tweede ziet Russell geen manier om te defini¨eren wat eindige getallen zijn zonder te spreken over alle eigenschappen van x [46, p.242]. Russell’s oplossing is het uiterst problematische axiom of reducibility. De typentheorie had een mate van constructivisme ge¨ıntroduceerd in het logicisme, maar Russell veegt het meteen onder de mat. Bovendien kan hij het enkel verantwoorden aan de hand van het klassenbegrip, net terwijl hij net probeerde daar van verlost te raken. There is no advantage in assuming that there really are such things as classes (...) I shall, therefore, not assume anything of what may seem to be involved in the common-sense admission of classes, except this: that every propositional function is equivalent, for all its values, to some predicative function[46, p.242-243]. Russell’s motivatie voor het axioma is zwak want berust op de na¨ıeve klassentheorie. Het comprehensie-axioma laat toe dat met elke propositionele functie φ(x) een eerste orde functie correspondeert, met name de functie “x behoort tot de klasse a”. Die laatste eigenschap bevat enkel de constante a en is bijgevolg van de eerste orde. Het enige voordeel van het axioma ten opzichte van de aanname dat er klassen bestaan is dat het een zwakkere veronderstelling is. Maar de belangrijkste reden waarom Russell het voor waar aannam is de praktische voordelen die het had: het verantwoordde de resultaten die hij voor waar aannam[24, p.62]. In dat opzicht was Russell uiteindelijk niet beter af dan Zermelo. Russell’s typentheorie heeft een onaangenaam ontologisch gevolg: klassen worden op verschillende niveau’s gedupliceerd. In de na¨ıeve klassentheorie bepaalde de functie x = x juist een klasse. Maar volgens de typentheorie moet rekening worden gehouden met het type van de variabele. Bijgevolg is er een ∅1 voor variabelen van type 0, ∅2 voor type 1 etc. Analoge beschouwingen gelden voor de universele klasse19 en voor de natuurlijke getallen[46, p.257]. Russell stelt voor om dergelijke symbolen een ambigue betekenis te geven. Wanneer hij de universele klasse heeft ingevoerd stelt hij bijvoorbeeld: (...)the proposition Cls ∈ Cls (...) requires that Cls should have a different meaning in the two places where it occurs. The symbol Cls can only be used where it is unnecessary to know the type; it has an ambiguity which adjusts itself to circumstances[46, p.251]. 19 Een echte universele klasse bestaat dus niet langer. Voor elke universele klasse van type n bestaat er een groter universum van type n+1[46, p.249]. Cantor’s idee van een nimmer afgesloten wiskundig universum dat Russell voordien als wanhopig had afgedaan blijkt uiteindelijk dus toch acceptabel voor Russell.
38
Russell geeft een parti¨ele oplossing voor dit probleem. Er bestaat immers een eenvoudige manier om het type van een klasse te verhogen. Elke verzameling α van type n kunnen we vervangen door een verzameling van een type hoger door de verzameling te nemen van alle singletons {x} waarvoor x ∈ α[46, p.257]. Althans notationeel is het dan terug mogelijk de taal van de na¨ıeve verzamelingenleer te gebruiken, maar het ontologische probleem blijft bestaan. Ik neem aan dat deze methode de reden is waarom Russell nergens het type van de variabelen expliciet vermeld. Rudolf Carnap vermeldt een verdergaande methode. Wanneer we de rekenkunde defini¨eren op niveau ω en een regel invoeren dat op het transfiniete niveau alle eindige nivreau’s zonder beperking mogen worden gebruikt, dan zijn de enige getallen die er zijn die op het transfiniete niveau[18, p.113]. Ook deze methode heeft haar problemen: het is verre van duidelijk hoe transfiniet hoge niveaus filosofisch te verantwoorden kunnen zijn. De vraag staat open hoe leefbaar en vooral hoe logisch het logicisme was na de introductie van de Typentheorie. Russell had een aantal extra veronderstellingen ingevoerd: het keuzeaxioma en een vorm van het oneindigheidsaxioma20 bleken noodzakelijk[46, p.258]. Maar vooral het Axiom of Reducibility had duidelijk gemaakt dat Russell niet bereid was alle gevolgen van de typentheorie te dragen. Hermann Weyl, die zijn wijsgerig geweten had laten primeren wanneer het ging over de grondslagen van de wiskunde had er het volgende over te zeggen: (...) in the resulting system mathematics is no longer founded on logic, but on a sort of logician’s paradise, a universe endowed with an “ultimate furniture” of rather complex structure and governed by quite a number of sweeping axioms of closure. The motives are clear, but belief in this transcendental world taxes the strength of our faith hardly less than the doctrines of the early Fathers of the Church or of the scholastic philosophers of the Middle Ages[59, p.6]. Voor zover ik weet was dit de algemene teneur in de beoordeling van de Principia Mathematica, de uitwerking van de typentheorie. Dit betekende evenwel geenszins dat de typentheorie en het logicisme dood waren. Wat nodig was, was een manier vinden om aan te tonen dat deze axioma’s ofwel overbodig ofwel logisch zijn.
2.3.2
De vereenvoudigde typentheorie
Russell was zich bewust van de nadelen van zijn systeem. Reeds in de eerste editie van de Principia Mathematica heeft hij gewezen op de mogelijkheid dat de typentheorie zoals hij ze had uitgewerkt te streng was. Een afgezwakte restrictie kon voldoende zijn en zou hopelijk het Axiom of Reducibility ovebodig maken[24, p.62]. Russell bleek daarin gelijk te hebben. De vereenvoudigde typentheorie wordt gebruikelijk toegeschreven aan Frank Ramsey, maar ik denk dat het adequater is te stellen dat Ramsey enkel een synthese heeft gemaakt van de idee¨en van Ludwig Wittgenstein. Volgens Wittgenstein was de grote fout van Russell dat hij bij het opstellen van de typentheorie de formele regels liet meebepalen door de betekenis van 20 Russell’s axioma stelt dat er oneindig veel urelemente zijn, in tegenstelling tot Zermelo’s axioma dat stelt dat er een aftelbaar oneindig grote verzameling bestaat.
39
de symbolen[60, 5.331]. Het typenonderscheid is voor hem op zuiver formele grond te maken: de uitdrukkingen F x en F (F x) hebben een andere logische vorm. Om deze stelling hard te maken gebruikt hij Russell’s parafrase-techniek, hij bepaalt dat F (F u) eigenlijk staat voor “(∃φ)(F (φu).φu = F u)”. Op zich betekent dit niet meer dan dat in F (F x) het symbool F een dubbele betekenis krijgt. Hij stelt dat deze maatregel voldoende is om Russell’s paradox te vermijden[60, 3.333]. Aangezien het onderscheid tussen functies, functies van functies enzovoorts bewaard wordt, ga ik er van uit dat het niet onzinnig is te stellen dat het typenonderscheid in Wittgenstein’s systeem geldig blijft, maar er is een belangrijk verschil. Russell had het type van een functie gelijk gesteld aan het betekenisbereik ervan. In Wittgenstein’s versie kan deze definitie niet kloppen aangezien spreken over betekenis uit den boze is. Dus hoewel de formele eigenschappen van de typentheorie bewaard blijven, verdwijnt het onderscheid tussen verschillende types. Een tweede implicatie van Wittgenstein’s opvattingen is dat het onderscheid tussen ordes ongeldig is, aangezien ook dat steunde op de betekenis van de termen die voorkomen in een propositionele functie. Ramsey, die in tegenstelling tot Wittgenstein duidelijk een logicist was, heeft de logica van de Tractatus aangewend om het logicisme te redden van de tekorten van de Principia Mathematica. Twee inzichten van Wittgenstein staan hierbij centraal. Het onderscheid tussen het logische en het semantische aspect van de typentheorie is het eerste deel van zijn oplossing. Het tweede element is Wittgenstein’s extensionaliteitsstelling. Volgens deze stelling is elke zin een waarheidsfunctie van elementaire functies[60, 5, 5.3]. Ramsey’s essay The Foundations of Mathematics is dan ook een poging aan te tonen dat beide stellingen impliceren dat het keuzeaxioma, het oneindigheidsaxioma en het axiom of reducibility ofwel tautologi¨en zijn, ofwel ge¨elimineerd kunnen worden. Ik zal me concentreren op zijn behandeling van de typentheorie en het axiom of reducibility21 Ramsey stelt dat de Principia Mathematica de logicistische these heeft bevestigd, op een zware fout na: The Blemish is of course the Axiom of Reducibility, which is, as will be shown below, a genuine proposition, whose truth or falsity is a matter of brute fact, not of logic. It is, therefore, not a tautolofy in any sense, and its introduction into mathematics is inexcusable[44, p.11–12]. Het axiom of reducibility was een reactie op de nodeloze complicaties die de opdeling in ordes teweeg bracht. Indien de theorie van de ordes overbodig blijkt te zijn, dan kan Ramsey meteen ook komaf maken met het axioma. De reden waarom Russell naast het onderscheid tussen de types de verschillen in orde had ingevoerd, was om paradoxen zoals die van de leugenaar en Richard op te lossen. Wittgenstein had voor Ramsey duidelijk gemaakt dat semantische en syntactische aspecten van elkaar moeten worden gescheiden. De twee hi¨erarchie¨en van Russell lossen dus een verschillend probleem op. De weinig elegante reactie van Ramsey hierop is dat hij de oplossingen van semantische paradoxen delegeert. Enkel paradoxen die verwant zijn aan de Russellparadox, 21 Ter volledigheid: het keuzeaxioma is voor hem aanvaardbaar aangezien keuzefuncties extensioneel bepaald kunnen worden[44, p.24]. De zorg van Russell dat de keuze bepaald moet worden door een logische relatie kan hem weinig deren. Een adequate verdediging van het oneindigheidsaxioma blijft Ramsey schuldig.
40
zoals die van Burali-Forti, zijn een logisch probleem. De tweede soort paradoxen zijn volgens Ramsey geen probleem voor de logicus maar, daar ze steunen op de betekenis van semantische termen zoals waarheid en definieerbaarheid, voor linguisten[44, p.24]. Volgens Russell worden hogere orde-functies gegenereerd door een proces van generalisatie. We beginnen met eerste-orde uitspraken F a, die door veralgemening de tweede-orde uitspraak (∀x)F x[46, pp.237–238]. Om aan te tonen dat de opdeling in ordes overbodig is, herinterpreteert Ramsey de universele quantor naar de geest van Wittgenstein. Volgens hem is het proces van veralgemening niets anders dan het maken van een mogelijk oneindige conjunctie, (∀x)F x is niets meer dan een economische manier om F a ∧ F b ∧ F c ∧ . . . neer te schrijven22 . Dit impliceert dat iedere willekeurige uitspraak uiteindelijk te schrijven is als een waarheidsfunctie van eerste-orde functies en dus ook van eerste orde is. Bijgevolg is het axiom of reducibility overbodig: er zijn slechts eerste-orde functies[32, p.497]. De vereenvoudigde typentheorie van Ramsey verschilt op een belangrijk punt van de hedendaagse formulering. Zijn versie haalde immers een opkomende standaard niet. Onder invloed van Hilbert werden de syntactische eigenschappen van een logica langzaamaan de belangrijkste. Alvorens de typentheorie een volwaardige logica kon worden, moest ze een degelijke formalisering krijgen. Deze formalisering gebeurde in twee klassiekers van de twintigste-eeuwse logica: G¨ odel’s artikel over de onvolledigheid van de rekenkunde en Tarski’s definitie van het waarheidsbegrip[25, p.469–470]. De nadruk op de syntactische eigenschappen heeft er voor gezorgd dat de eerste-orde logica, die in tegenstelling tot de typentheorie volledig is, de standaard werd. Het vreemde aan heel deze historie is dat de originele reden waarom de typentheorie werd uitgewerkt onder de mat wordt geveegd. Door het hoofdcriterium waaraan een logica moet voldoen syntactisch te maken, duiken een deel van de eigenaardigheden die de typentheorie moest verhelpen terug logisch mogelijk. Om een voorbeeld van Rudolf Carnap aan te halen, het nummer 5 mag weer blauw zijn.
2.3.3
New Foundations
Strikt gesproken is de typentheorie geen verzamelingenleer, maar een een logica die sterk genoeg is om de verzamelingenleer in te formuleren door middel van kwantificatie over predikaten. Russell voerde in dat systeem klassen in door middel van een contextuele definitie om de link met de verzamelingenleer expliciet te maken, maar strikt gesproken was klassenterminologie overbodig. G¨ odel’s resultaten uit 1930 en 1931 tonen aan dat voor die uitbreiding van de expressieve kracht van de logica een prijs betaald moet worden: de typentheorie is in tegenstelling tot de eerste-orde logica onvolledig. Dit bleek de doodsteek te zijn van het logicisme. Desondanks het wijsgerig failliet van het logicisme, waren er een aantal inzichten in de manier waarop de paradoxen van de verzamelingenleer konden worden vermeden. Het is Willard V.O. Quine geweest die heeft aangetoond dat de inzichten die hebben geleid tot de originele typentheorie te recupereren zijn in een eerste-orde taal. De verzamelingenleer van Quine wordt New Foundations of NF genoemd omdat ze werd beschreven in het artikel “New Foundations for Mathematical 22 Analoog
is een existentieel gekwantificeerde formule een disjunctie.
41
Logic”. De redenen waarom Quine NF heeft ontwikkeld zijn terug te vinden in een artikel uit 1938 getiteld on the theory of types”[42]. Quine deelt de ” typentheorie van Russell op in twee componenten: een ontologische doctrine en een formele restrictie[42, p.129] De ontologische component is de stelling dat een verzameling van type n enkel elementen van type n-1 kan bevatten. De overeenkomstige formele eis is dat uitdrukkingen waarin subformules van de vorm xm ∈ yn waarbij n verschilt van m+1 of waarin wordt beweerd dat twee objecten van een verschillend logisch type identiek zijn geen betekenis hebben. Omwille van notationele overzichtelijkheid had Russell nooit de types expliciet vermeld, zodat de formele eis inhoudt dat formules slechts zinvol kunnen zijn wanneer in principe indexen aan de variabelen van een formule kunnen worden toegevoegd zodat bovenstaande regels gelden. Deze formele eis doet wat hij moet doen: het systeem van de Principia behoeden voor inconsistentie. Welnu, aangezien het type ambigu mag blijven, waarom niet meteen de typenontologie overboord gooien maar wel de eis bewaren dat de types in principe aan de variabelen toe te kennen zijn. Op die manier kunnen een aantal vreemde aspecten van de typentheorie vermeden worden. De typenontologie heeft immers enkele eigenaardigheden die haar voor Quine onaanvaardbaar maken. Zoals reeds vermeld is er de duplicatie van klassen op verschillende niveau’s. Terecht merkt hij op dat dit vooral eigenaardig is in het geval van de lege verzameling. Nu, dat de Principia Mathematica vrij lijkt te zijn van contradicties is volgens Quine helemaal niet te wijten aan de achterliggende metafysica maar aan de voldoende strenge formele regels. De typentheorie kan zonder de logische types. De conclusie ligt dan ook voor de hand: Let us then try abandoning the ontological aspect altogether, retaining only the formal restrictions: for if the theory of types is adequate at all as a safeguard against contradictions, it must be adequate in its formal aspect alone[42, p.132]. Alvorens de technische kant van Quine’s werk toe te lichten wil ik wijzen op een wijsgerige inconsequentie die er in aanwezig is. Van Rudolf Carnap23 heeft hij het idee overgenomen dat enkel formele en notationele criteria aanvaardbaar zijn bij het opstellen van deductieregels en axioma’s. Langs de andere kant beseft hij dat G¨ odel’s theorema duidelijk heeft gemaakt dat een dergelijke aanpak onvoldoende is om de volledige wiskunde te vatten. Quine’s oplossing voor deze spanning is een soort light-versie van het logicisme. Zijn doel is niet zozeer aantonen dat alle wiskunde logica is, maar wel dat de hoofdmoot van de wiskunde logica is. De standaard werd voor hem gezet door de Principia Mathematica, waarin alleen wat hij de randgevallen die steunen op het keuzeaxioma en het oneindigheidsaxioma noemt niet tot logica werd herleid[41, p.76]. Quine’s NF is in zekere zin een maximalisatie van Russell’s methode om het type ambigu te laten. In plaats van (∃xn+1 )(∀yn )(yn ∈ xn+1 ≡ φ(y)) gebruikte hij de notatie van de na¨ıeve verzamelingenleer en liet het aan de lezer over om te controleren of de formule voldeed aan de restricties van de typentheorie. Iedere formule waarin een subformule van de vorm xn ∈ ym met m verschillend 23 Quine verbleef bij Carnap toen deze zijn Logische Syntax der Sprache schreef, een werk waarin hij probeerde aan te tonen dat logica en wiskunde zuiver formeel zijn[17, 1]. In dat opzicht hadden voor Carnap de formalisten gelijk. Langs de andere kant is voor het het logicisme nodig als theorie van de toepassing van de wiskunde[17, 84]. Op analoge wijze wil Quine het logicisme we aanvaarden hoewel hij inziet dat het niet adequaat is.
42
van n + 1 is in dat systeem niet welgevormd. De formules die welgevormd zijn noemt Quine gestratifieerd[41, p.78]. Russell’s ambigu¨ıteitsmethode liet hem toe de stratificatie eis te bewaren terwijl zijn theorie schijnbaar de eenvoud van de na¨ıeve verzamelingenleer bewaarde. Dus kon hij bijvoorbeeld ∼ (∅ ∈ ∅) neerschrijven terwijl de lege klasse waarmee hij werkt iets totaal anders is van die uit de naieve verzamelingenleer. Quine’s inzicht is nu dat het idee van ambigu¨ıteit op een veel natuurlijker manier gecombineerd kan worden met de voordelen van de typentheorie24 . Het is immers niet het gebruik van x ∈ x dat verantwoordelijk is voor de paradoxen van de verzamelingenleer. Het vicious circle principle was door Russell niet alleen te strikt toegepast in de theorie van de ordes, maar ook in het deel van de typentheorie dat enkel over types gaat. Om de paradoxen van de na¨ıeve verzamelingenleer te omzeilen is het voldoende de verzamelingen uit te bannen die worden bepaald door middel van een niet-gestratifieerde formule. Enkel die instanties van het comprehensie-axioma die stratifieerbaar zijn, zijn in NF toelaatbaar[41, p.79]. Langs deze weg bewaart Quine veel meer van de na¨ıeve klassentheorie dan Russell: er is een unieke lege klasse, de duplicatie van klassen wordt ongedaan gemaakt en bovenal is er een universele verzameling. De verzamelingen van NF hebben totaal andere eigenschappen dan de verzamelingen van ZFC. Ten eerste bestaat de universele verzameling, Cantor’s nemesis, in NF. In tegenstelling tot in ZFC zijn dus alle Boolse operaties mogelijk met de verzamelingen van NF[35, p.12]. In dat opzicht is NF eerder een logisch ge¨ınspireerde verzamelingenleer te noemen, in contrast met de iteratieve opvattingen van Cantor en volgelingen. In het eerste hoofdstuk heb ik besproken hoe Russell dacht dat het wiskundig universum veel rijker was dan Cantor het zich voorstelde. Voor hem was het vanzelfsprekend dat er bijvoorbeeld klassen bestaan waarvan de machtigheid niet vergelijkbaar is met die van de gehele getallen. Russell’s argument was dat de stelling dat de machtigheid van alle verzamelingen door middel van een (transfiniet) getal uitdrukbaar is steunt op de hypothese dat alle verzameling een welordening hebben. In de principia deed hij een toegeving aan Cantor door het keuzeaxioma aan zijn systeem toe te voegen. Bijgevolg zijn alle systemen die ik tot nu toe heb besproken axiomatiseringen van de Cantoriaanse intu¨ıtie. Het tweede verschilpunt tussen NF en een verzamelingenleer in de stijl van ZFC is dat binnen NF verzamelingen bestaan die geen welordening hebben. Dit volgt uit Ernst Speckers bewijs uit 1953 dat het keuzeaxioma niet geldt in NF[49]. Een onmiddellijke gevolg van deze stelling is dat NF het oneindigheidsaxioma bewijst25 en dus ook dat NF een sterkere theorie is dan ZFC of NBG. Een ander gevolg is dat het universum van Quine rijker is dan dat dat wordt beschreven door de wiskundige verzamelingenleren. NF vertrekt duidelijk van een andere intu¨ıtie dan ZFC. 24 Quine’s inzicht wordt ondersteund door een technisch resultaat. Veronderstel dat φ een formule is in de typentheorie, en φ+ de formule bekomen door het type van alle variabelen van φ met 1 te verhogen. Ernst Specker heeft aangetoond dat indien typentheorie met het axioma φ ≡ φ+ consistent als en slechts als NF consistent is[26]. 25 Voor eindige verzamelingen geldt het keuzeaxioma triviaal. Indien het vals is moet er dus een oneindige verzameling zijn.
43
2.4
Een voorlopige conclusie
In de inleiding beloofde ik een poging tot verklaring waarover de verzamelingenleer gaat door middel van een analyse waarvoor ze moest dienen. Laat ik dus een aantal inzichten uiteenzetten. Er moet een onderscheid worden gemaakt tussen een wiskundige en een logische conceptie van de verzamelingenleer. De theorie¨en van Cantor, Zermelo en von Neumann behoren hier toe. De logische versies zijn die van Dedekind, Russell en Quine. De sleutel tot het begrip van de wiskundige conceptie is het idee van iteratie. Het idee was impliciet aanwezig in Cantor’s opvatting dat de (transfiniete) ordinalen primitief zijn en dat het universum van verzamelingen volgens hun machtigheid is geordend. De term universum moet hier metaforisch worden opgevat, en ik denk dat dit ook het gevolg is van het iteratie-idee. De wiskundige verzamelingenleer kan worden gezien als het resultaat van een top-down aanpak. Cantor veralgemeende het gangbare getalbegrip, Zermelo onderzocht welke inferenties aanvaard werden, en beiden kwamen uit bij een overkoepelende taal voor alle wiskunde. De implementatie van de wiskunde in die taal komt er achteraf bij. De logische conceptie van de verzamelingenleer werkt omgekeerd. Het logicistische universum kent geen fijnstructuur zoals het wiskundige. Russell begon met het idee van een klasse en ging ervan uit dat dit transparant was. De cruciale fout die hij maakte was te denken dat verzamelingen hetzelfde zijn. Dit verklaart waarom hij zoveel problemen had met de afwezigheid van een universele verzameling. Logisch is het een kleine stap van een lege verzameling naar een universele, maar wiskundig was er een onoverbrugbare kloof. Het is dit onderscheid dat aan de basis ligt van de verschillende oplossingen voor de paradoxen. Er zijn twee verschillende methodes gebruikt om de paradoxen van de na¨ıeve verzamelingenleer op te lossen. De eerste methode bestaat eruit niet alle klassen die comprehensie toelaat als verzameling te behandelen. De tweede methode bestaat eruit dat niet alle klassen als element mogen optreden. Deze twee methodes worden op een verschillende manier behandeld in de besproken systemen. ZFC is een implementatie van het eerste idee. Verzamelingen worden recursief gedefinieerd aan de hand van volgende drie principes: 1. De lege verzameling is een verzameling en er is een aftelbaar oneindige verzameling. 2. Alles wat door middel van de overige ZFC axioma’s uit verzamelingen wordt opgebouwd is een verzameling. 3. Alleen wat bepaald wordt door de eerste twee principes is een verzameling. De axioma’s garanderen dat gegeven bepaalde verzamelingen andere verzamelingen ook bestaan. Deze methode berust, bij gebrek aan consistentiebewijs op twee geloofspunten: dat de beginverzamelingen consistent zijn en dat de operaties die de axioma’s bepalen niet tot inconsistenties leiden. Maar we weten dat minstens de bekende paradoxen niet afleidbaar zijn in dit systeem. Overigens is het derde principe uiterst problematisch. Het is immers enkel formuleerbaar in de metataal van het systeem[18, 179–180]. De methode van Zermelo beperkt de verzamelingenleer tot een enkele ontologische categorie, die van de verzamelingen, en legt restricties op aan dit begrip door middel van de axioma’s. 44
Het idee achter de typentheorie is dat een klasse een andere ontologische status heeft dan de elementen die er toe behoren. Dus is er in plaats van ´e´en enkele basisrelatie ∈ een oneindig aantal relaties i ∈ i + 1. Laat mij een poging doen Russell’s redenering te reconstrueren. Aangezien klassen logische ficties zijn, moeten we wel vertrekken van de propositionele functies (eigenschappen) die de klasse definieert. Doch, in tegenstelling tot klassen zijn eigenschappen niet extensioneel bepaald. De eigenschap, en dus de klasse, moet dus voorop worden gesteld aan de elementen die er toe behoren. Wat dus gevonden moet worden, zijn criteria opdat de bewering dat een zeker element tot een klasse behoort niet tot een inconsistentie leidt. Dit strookt met Russell’s bewering dat de typentheorie een theorie over de universele quantor is. Wanneer we stellen dat (∀x)(x ∈ R ≡∼ (x ∈ x)), dan zijn praktisch alle gevallen niet paradoxaal. Russell’s typentheorie is een antwoord op de vraag welke substituties in dergelijke situaties legitiem zijn. NBG en NF zijn mengvormen van deze twee basisidee¨en. Het systeem van von Neumann maakt gebruik van het systeem van de typentheorie, maar dan enkel voor de problematische gevallen. Het axioma van de te grote verzamelingen is in feite een regel die het typenonderscheid maakt indien een dergelijke combinatie contradictorisch is. De verzamelingen die voor de na¨ıeve verzamelingenleer paradoxaal zijn, zijn volgens dit axioma immers geen verzamelingen, maar van een hoger type. Von Neumann’s systeem maakt ook het onderscheid tussen de logische en de wiskundige conceptie duidelijk. Wiskundige objecten, verzamelingen dus, zijn gekoppeld aan ordinalen. De wiskundige houdt zich volgens von Neumann’s axioma enkel bezig met wat op de een of de andere manier aan de hand van getallen gestructureerd kan worden. Hoewel NF filosofisch de meest directe verwant is van de typentheorie, lijkt zijn methode het meest op die van Zermelo. Om te beginnen is er in NF slechts ´e´en type, dat van de verzamelingen. Het eigenaardige aan NF is dat hij Russell’s criterium, oorspronkelijk bedoeld als voorwaarde voor het lidmaatschap van een verzameling omvormt tot een criterium voor de bepaling van een klasse. Zermelo en Russell lokaliseerden het probleem van de na¨ıeve verzamelingenleer op een andere plaats. Analyse van de paradoxen en van de resultaten die legitiem leken hebben zo een verschillende verzamelingenleer opgeleverd. Ik hoop dat ik in dit hoofdstuk duidelijk heb gemaakt dat Russell’s wijsgerige achtergrond er voor heeft gezorgd dat hij de aanpak van Zermelo niet kon aanvaarden. Het volgende hoofdstuk is een case-study van het ontdekkingsproces van de axiomatische verzamelingenleer26 . Zermelo beweerde dat hij bij zijn axioma’s is uitgekomen door een historische analyse van de gebruikte inferentievormen in de verzamelingenleer. Mijn claim is nu dat Zermelo’s ontdekking van die axioma’s perfect kan worden gekarakteriseerd aan de hand van een specifieke logica.
26 Analoge
beschouwingen als voor de theorie van Zermelo gelden voor de typentheorie.
45
Hoofdstuk 3
Verzamelingenleer gebaseerd op adaptieve logica 3.1
Inleiding
Zermelo beweerde dat zijn axiomatisering tot doel had een dusdanige restrictie op te leggen aan het verzamelingsbegrip zodat de paradoxen van de verzamelingenleer niet langer afleidbaar zouden zijn. Om dit te realiseren was het nodig te redeneren vanuit een inconsistente theorie. Adaptieve logica’s laten toe een dergelijke redenering te formaliseren. In dit hoofdstuk zal ik dan ook een adaptieve logica, ACLu∃ genaamd, gebruiken om te verklaren hoe Zermelo bij zijn axioma’s is uitgekomen. In zekere zin imiteert de logica ACLu∃ wanneer ze wordt toegepast op de na¨ıeve verzamelingenleer Cantor’s procedure uit 1899. Alle verzamelingen die Comprehensie toelaat zullen beschikbaar zijn zolang ze niet tot een inconsistentie leiden. Ik zal evenwel wat strenger zijn dan Cantor. Eens een verzameling inconsistent is gebleken, zal het niet langer mogelijk zijn ze te gebruiken in een redenering. Dat de theorie die ik zal presenteren gelijklopend is met de Cantoriaanse idee¨en is ook de reden waarom ze niet kan dienen als een alternatief voor de bestaande verzamelingenleren. Het belang er van is ook niet gelegen in de eigenschappen van de theorie an sich, maar in de manier waarop er een criterium uit kan worden afgeleid die wel tot een legitieme verzamelingenleer leidt. Eens gebleken dat de na¨ıeve verzamelingenleer inconsistent is, is de klassieke logica een nutteloos instrument geworden om met die theorie verder te werken. Wie van mening is dat enkel de klassieke logica1 de titel logica verdient moet dus veronderstellen dat de theorie¨en die de na¨ıeve verzamelingenleer hebben vervangen hebben zijn ontstaan uit een onlogisch denkproces. Mijn inziens is dit nogal beledigend voor de wiskundigen van deze wereld. Nergens is het verschil tussen onderzoek en presentatie van een wetenschappelijk resultaat zo duidelijk als in de wiskunde. Iedereen die zich ooit de moeite heeft getroost een stelling 1 Ik zal de klassieke logica aanduiden met CL, enkel en alleen om vast te houden aan de conventies van naamgeving binnen het onderzoeksprogramma naar adaptieve logica’s.
46
te bewijzen weet dat de zoektocht naar een bewijs niet weerspiegeld wordt in de deducties die het eindresultaat bevat. Dit betekent niet dat een bewijs zoeken niet volgens een zekere rationaliteit verloopt. Sommige pistes zullen als vruchtbaarder dan andere worden beschouwd, verschillende bewijsmethodes worden uitgeprobeerd etc. Mijn punt is dat er een zeker systeem in dergelijke redeneringen zit maar dat dit niet door middel van de klassieke logica te beschrijven is. De klassieke logica, ontstaan binnen het kader van het logicisme, was bedoeld als logica van wiskundige bewijzen. Het is met andere woorden de logica van het resultaat van het zwoegen van de wiskundige. Adaptieve logica’s zijn ontwikkeld om redeneringen te beschrijven die leiden tot wetenschappelijke resultaten; het zijn de logica’s van de ontdekking[2]. ACLu∃m is een adaptieve logica en is het middel waarmee ik zal beschrijven hoe Zermelo’s axiomatisering is ontstaan. Het inzicht dat de adaptieve logica biedt is hier evenwel slechts partieel. Ik heb reeds uitgelegd hoe filosofische motieven ertoe hebben geleid dat Zermelo en Russell het probleem op een andere plaats zochten. In het geval van Zermelo was het zo dat hij de gebruikelijke inferenties uit de verzamelingenleer wilde bewaren, maar een inperking wilde invoeren op het domein waarin deze geldig zijn. Dit betekent dat operaties als de het nemen van de machtsverzameling van een verzameling of de unie van twee verzamelingen hun na¨ıeve betekenis moeten bewaren, maar niet langer meer mogen gebruikt worden voor bepaalde klassen. Eens dergelijke keuzes gemaakt zijn, lag het kader vast waarbinnen Zermelo naar een oplossing zocht. De ACLu∃m beschrijft hoe het eindresultaat wordt bereikt werd door de veronderstellingen die gemaakt worden bij een redenering expliciet te maken.
3.2
De logica CLu∃m
ˇ die zal Clu∃ is de uitbreiding van de klassieke logica CL met een quantor ∃ toelaten dat een existentieel gekwantificeerde formule en haar negatie tegelijk waar zijn. Laat L de taal van CL zijn, uitgebreid met S, C, V, P r , F, W en W ∃ respectievelijk de verzameling van schematische letters voor zinnen, die van de individuele constanten, van de individuele variabelen, van de predikatieve constanten van rang r, van de formules, van de welgevormde formules zijn en van ˇ de welgevormde formules zijn van de vorm (∃α)A. De verzameling van formules is de kleinste verzameling die recursief bepaald door volgende voorwaarden: (i) (ii) (iii) (iv) (v) (vi) De
S ⊂ F. Als π ∈ P r en α1 , α2 , . . . , αr ∈ C ∪ mathcalV , dan πα1 , α2 , . . . , αr ∈ F. Als α, β ∈ C ∪ V, dan α = β ∈ F. Als A ∈ F, dan ∼ A ∈ F Als A, B ∈ F, dan (A ∨ B), (A ∧ B), (A ⊃ B), (A ≡ B) ∈ F ˇ ∈F Als A ∈ F en α ∈ V , dan ∀αA, ∃αA, ∃A axioma’s van Clu∃ zijn de volgende:
A1 A2 A3 A4
A ⊃ (B ⊃ A) (A ⊃ (B ⊃ C)) ⊃ ((A ⊃ B) ⊃ (A ⊃ B)) ((A ⊃ B) ⊃ A) ⊃ A (A ∧ B) ⊃ A 47
(A ∧ B) ⊃ B (A ⊃ (B ⊃ (A ∧ B)) A ⊃ (A ∨ B) B ⊃ (A ∨ B) (A ⊃ C) ⊃ ((B ⊃ C) ⊃ ((A ∨ B) ⊃ C) (A ≡ B) ⊃ (A ⊃ B) (A ≡ B) ⊃ (B ⊃ A) (A ⊃ B) ⊃ ((B ⊃ A) ⊃ (A ≡ B)) ∼∼ A ⊃ A (A ⊃ B) ⊃ ((A ⊃∼ B) ⊃∼ A) (∀α)A ⊃ A(β/α) ˇ (∃α)A ⊃ (∃α)A α=α β = α ⊃ (A ⊃ (A(α/β) (∃α)A =def ∼ (∀α) ∼ A
A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15 A16 A17 A18 D∃
MP: A ⊃ B, A/B UG: Als ` A ⊃ B(β/α) en β komt niet voor in A (en in B(α)) dan A ⊃ (∀α)B. Wat een bewijs bewijs is, wat de afleidbaarheidsrelatie betekent en wat stellingen zijn wordt gedefinieerd als voor CL. Ik ga over tot de semantiek. Een model M is een koppel hD, vi waarbij D een verzameling is en v een toekenningsfunctie. De toekenningsfunctie v wordt bepaald door: Inferentieregels:
C1.1 C1.2 C1.3 C1.4
v v v v
: S → {0, 1} :C∪O →D : P r → ℘(Dr ) : W ∃ → {0, 1}
met D = {v(α)|α ∈ C ∪ O}
M bepaalt als volgt een valuatiefunctie vM :
C2.1 C2.2 C2.3 C2.4 C2.5 C2.6 C2.7 C2.8 C2.9 C2.10 C2.11
vM : F → {0, 1} Voor alle A ∈ S ∪ W ∃ : vM (A) = v(A) vM (π r α1 α2 . . . αr) = 1 alss. hv(α1 ), v(α2 ), . . . , v(αr )i ∈ v(π r ) vM (α = β) = 1 alss. v(α) = v(β) ˇ vM ((∃α)A) = 1 alss. vM (A(β)) = 1 voor minstens ´e´en ˇ β ∈ C ∪ O of vM ((∃α)A) =1 vM (∼ A) = 1 alss. vM (A) = 0 vM (A ⊃ B) = 1 alss. vM (A) = 0of vM (B) = 1 vM (A ∧ B) = 1 alss. vM (a) = vM (B) = 1 vM (A ∨ B) = 1 alss. vM (A) = 1of vM (B) = 1 vM (A ≡ B) = 1 alss. vM (A) = vM (B) vM ((∀α)A) = 1 alss. vM (A(β)) = 1 voor alle β ∈ C ∪ O
48
Waarheid in een model, semantisch gevolg en geldigheid worden gedefinieerd zoals voor CL Theorema 1 Als Γ `Clu∃ A, dan Γ Clu∃ A. Bewijs. Stel dat Γ `Clu∃ A. Dan zijn er B1 , . . . , Bn ∈ Γ zodat B1 , . . . , Bn `Clu∃ A. Er is dan een CLu∃-bewijs van A uit B1 , . . . , Bn . Beschouw nu een willekeurige valuatiefunctie vM waarvoor vM (B1 , . . . , Bn = 1. We weten (1) vM maakt alle premissen waar (2) vM maakt alle axioma’s en toepassingen van inferentieregels van ACLu∃ waar. Aangezien Clu∃ een uitbreiding is op CL ˇ bewijs ik enkel de waarheid van A16. Stel vM ((∃α) ⊃ A(∃α)A) = 0. Dan is ˇ vM ((∃α)A) = 1 en vM ((∃α)A) = 0. Maar uit C2.5 volgt dat in het geval dat ˇ ˇ vM ((∃α)A) = 1, vM ((∃α)A) = 1. Bijgevolg geldt dat vM ((∃α) ⊃ A(∃α)A) = 1. Elke stap in het bewijs, A incluis, krijgt dus de waarde 1 toegekend. A is dus waar in alle modellen van Γ. 2 Theorema 2 Als Clu∃ A, dan Γ `Clu∃ A. Bewijs. Veronderstel dat Γ 0Clu∃ en beschouw een lijst B1 , B2 , . . . van alle welgevormde formules waarin elke formule van de vorm (∃α)A onmidellijk wordt gevolgd door een instantie met een constante die nog niet voorkomt in Γ, in A of in een vorige formule uit de lijst. We defini¨eren nu als volgt: 40 4i+1
= =
CnClu∃ (Γ) CnClu∃ (4i ∪ {Bi+1 }) indien A ∈ / CnClu∃ (4i ∪ {Bi+1 }) en 4i+1 = 4i in het andere geval. 4 = 41 ∪ 42 ∪ 43 ∪ . . . Dan gelden volgende eigenschappen: Γ ⊆ 4 (wegens de definitie van 4) A∈ / 4 (wegens de definitie van 4) 4 is deductief gesloten (wegens de definitie van 4) 4 is maximaal niet-triviaal. Immers, voor elke willekeurige C is A ⊃ C ∈ 4. Stel dat dit niet zo was, dan is er een 4i waarvoor 4i ∪ {A ⊃ C} ` A. Wegens het deductietheorema hebben we dan ook 4i ` (A ⊃ C) ⊃ A, zodat, wegens A3, 4i ` A, wat strijdig is met de constructie van 4i . Veronderstel nu dat D ∈ / 4, dan zal voor een zekere 4i , 4i ∪ {D} ` A. Aangezien A ⊃ C ∈ 4 voor elke willekeurige C volgt dan dat 4 ∪ {D} triviaal is. (v) 4 is ω-volledig. Net zoals voor de klassieke logica geldt dat dit volgt uit de constructie van de lijst B1 , B2 , . . .. Ik zal nu aantonen dat elke dergelijke verzameling formules 4 een model bepaalt. Als domein nemen we de equivalentieklassen [α], met [α] =def {β|α = β ∈ 4}. De toekenningsfunctie v bepalen we als volgt: (i) (ii) (iii) (iv)
(i) voor α ∈ C ∪ V : v(α) = [α] (ii) indien A ∈ S, v(A) = 1 alss A ∈ 4 (iii) voor π ∈ P van rang n: v(π) = {h[α1 ] , . . . , [αn ]i |πα1 . . . αn ∈ 4} (iv) Indien B ∈ W ∃ : v(B) = 1 alss B ∈ 4. Net zoals voor CL zal ik nu aantonen door middel van inductie over complexiteit van de de formules dat voor alle welgevormde formules C: (*) C ∈ 4 alss vM (C) = 1 49
De inductiebasis wordt gevormd door de schematische letters voor zinnen, welgevormde formules van de vorm πα1 . . . αn, de welgevormde formules van de ˇ vorm α = β en de welgevormde formules van de vorm (∃)A. Voor al deze gevallen klopt (*): de elementen van S wegens (i), wffs van de vorm πα1 . . . αn worden waar gemaakt door (ii), de wffs van de vorm α = β worden verzekerd door de definitie van de equivalentieklassen [α] en (i) en tenslotte geldt (*) voor ˇ wegens (iv). Dat (*) opgaat voor complexere formules de wffs van de vorm(∃)A wordt op dezelfde manier bewezen als voor CL. Aangezien 4 maximaal niettriviaal is en vM (C) = 1 voor alle C ∈ 4, volgt dat 4 = {C|vM (C) = 1} en dus ook dat vM (A) = 0. Aangezien vM (B) = 1 voor alle B ∈ Γ geldt dan ook Γ 2CLu∃ A. 2
3.3
Van paraconsistent naar adaptief
Het basisidee achter adaptieve logica’s is dat we veronderstellen dat een verzameling premissen consistent is zolang het tegendeel niet bewezen is. Indien een inconsistentie ontdekt wordt, dan wordt enkel met betrekking tot die inconsistentie het aantal mogelijke inferenties beperkt zodat de resulterende theorie niet triviaal is. Het is niet de bedoeling hier een algemene studie van adaptieve logica’s te geven, zie daarvoor [1]. Wat ik wel zal doen is een opsomming geven van een minimum aan theorie opdat de bewijzen in de volgende afdeling begrijpelijk worden: (1) hoe een adaptieve logica gedefinieerd wordt en (2) hoe de bewijstheorie er uitziet. Een adaptieve logica wordt gedefinieerd door drie elementen: 1. Een onderlimietlogica die CL bevat en die transitief, monotoon en compact is. 2. Een verzameling abnormaliteiten Ω: een verzameling formules bepaald door een zekere logische vorm F. 3. Een adaptieve strategie. ACLu∃m is gedefinieerd door (1) de onderlimietlogica CLu∃, (2) de verzameling ˇ abnormaliteiten Ω = {(∃α)A(α)∧(∀) ∼ A(α)|A ∈ F}, (3) de strategie: minimale abnormaliteit. Theorema 3 Γ `ACLu∃m A alss Γ ACLu∃m A Bewijs. Onmiddellijk uit de manier waarop ACLu∃m werd gedefinieerd en theorema 9 uit [1]. De hoofdeigenschap van ACLu∃m -bewijzen is dat ze dynamisch zijn. Inferenties die op een bepaald moment legitiem zijn kunnen herroepen worden, en verworpen deductiestappen kunnen terug aanvaardbaar worden. Deze dynamiek is het gevolg van de toevoeging van voorwaarden aan de stappen in een bewijs en van een markeringsdefinitie. Een regel in een ACLu∃m -bewijs bestaat uit een regelnummer, een formule, een verantwoording en een voorwaarde. We bepalden de volgende inferentieregels, die ik geef ze in generische vorm. De toegelaten inferenties zijn het gevolg van de axioma’s van CLu∃ en van de definitie van de abnormaliteit. 50
Laat Dab(∆) staan voor de klassieke disjunctie van een eindig aantal leden van Ω en laat A ∆ afkorten dat A in het bewijs voorkomt onder voorwaarde ∆. PREM
Indien A ∈ Γ
RU
Indien A1 , . . . , An `CLu∃ B
RC
Indien A1 , . . . , An `CLu∃ B ∨ Dab(Θ)
...
...
A A1 ... An
∅ ∆1 ... ∆n
B A1 ... An
∆1 ∪ . . . ∪ ∆n ∆1 ... ∆n
B ∆1 ∪ . . . ∪ ∆n ∪ Θ Om te bepalen wanneer een lijn gemarkeerd moet worden zijn een aantal definities nodig. Dab(∆) is een minimale Dab-formule op stadium s van een bewijs alss het de formule is van een regel afgeleid op voorwaarde ∅ en geen enkele Dab(∆0 ) met ∆ ⊂ ∆0 de formule is van een regel afgeleid op voorwaarde ∅. Een keuzeverzameling van Σ = {∆1 , ∆2 , . . .} is een verzameling dat ´e´en element bevat van elk lid van Σ. A minimale keuzeverzameling van Σ is een keuzeverzameling van Σ waarvan geen echte deelverzameling een keuzeverzameling van Σ is. Indien Dab(∆1 ), . . . , Dab(∆n ) de minimale Dab-formules zijn die afgeleid zijn op voorwaarde ∅ op stadium s, dan is Θs (Γ) de verzameling van minimale keuzeverzamelingen van {∆1 , . . . , ∆n }. Definitie 1 Regel i is gemarkeerd op stadium s alss, indien A afgeleid werd op voorwaarde ∆, (i) er is geen δ ∈ Φs (Γ) zodat δ ∩ ∆ = ∅, of (ii) er zijn δ ∈ Φs (Γ) waarvoor er geen enkele regel is waarop A afgeleid is op voorwaarde Θ waarvoor δ ∩ Θ = ∅. Regels die gemarkeerd zijn kunnen hun markering verliezen. Met andere woorden is, in tegenstelling tot bijvoorbeeld in CL, wat afleidbaar is niet zomaar van een bewijs af te lezen. Daarom worden twee afleidbaarheidsrelaties gedefinieerd voor een adaptieve logica. Definitie 2 A is afgeleid uit Γ op stadium s van een bewijs alss indien A de formule is van een regel die niet gemarkeerd is op stadium s Definitie 3 A is finaal afgeleid van Γ op regel i van een bewijs op stadium s alss (i) A is het tweede element van regel i, (ii) regel i is ongemarkeerd op stadium s, en (iii) iedere uitbreiding van het bewijs waarin i gemarkeerd is kan zodanig worden uitgebreid dat i ongemarkeerd is. Definitie 4 Γ `ACLu∃m A alss A finaal is afgeleid op een regel van een bewijs uit Γ.
51
3.4
Een adaptieve verzamelingenleer
In deze afdeling zal ik de basis uitwerken van een adaptieve verzamelingenleer, waarmee ik niet meer wil zeggen dan dat de achterliggende logica een adaptieve logica is. Het idee is zeer eenvoudig: we veronderstellen dat we alle verzamelingen die na¨ıeve comprehensie ter beschikking hebben. Indien blijkt dat een verzameling zich inconsistent gedraagt, dan worden alle resultaten er over gemarkeerd. Ik zal een aantal bewijzen erin geven die moeten aantonen dat elementaire operaties en verzamelingen uit de na¨ıeve verzamelingenleer niet van betekenis veranderen. Om de theorie te formuleren breiden we de taal van ACLu∃m uit met een ongedefinieerd binair predikaat ∈. Als axioma’s kiezen we een eerste-orde benadering van Russell’s axioma’s uit de principles. We duiden dit systeem aan met R. (∀x)(∀y)((∀z)((z ∈ x ≡ z ∈ y)) ⊃ x = y) ˇ (∃x)(∀y)(y ∈ x ≡ φ(y)) en dit voor elke formule φ(y) in de taal van de verzamelingenleer die welgevorm is en enkel y als vrije variabele heeft. Om een aantal definities te vereenvoudigen voer ik de iota-operator in: ˇ (ιx)P (x) =def (∃α)(P (α) ∧ (∀β)(P (β) ⊃ β = α) Laat ik nu een aantal conventies invoeren die de bewijzen notationeel lichter maken. Het derde element, de voorwaarde, van een regel i zal ik aanduiden met ˇ v(i). φ(α) staat voor de uitdrukking (∃x)(∀y)(y ∈ x ≡ α) ∧ (∀x) ∼ (∀y)(y ∈ x ≡ α) wat betekent dat de verzameling bepaald door α inconsistent is. Tenslotte zal ik ook, zij het enkel in de informele duiding van theorema’s de notatie {x|α} gebruiken. De manier waarop ACLu∃m de theorie2 hR, ACLu∃m i inconsistenties verwerkt zal ik illustreren aan de hand van de Russellparadox. De paradoxen van Burali-Forti en Cantor kunnen op een analoge manier opgelost worden, maar dit vraagt om veel meer werk. Daarvoor zou het nodig zijn een niet onaanzienlijk deel van de theorie van de ordinalen resp. kardinaalgetallen te ontwikkelen. Ext Comp
Stelling 1 De paradox van Russell is niet afleidbaar in hR, ACLu∃m i3 .
1 2 3 4 5 6 7
ˇ (∃x)(∀y)(y ∈ x ≡∼ (y ∈ y)) (∀y)(y ∈ R ≡∼ (y ∈ y)) (R ∈ R ≡∼ (R ∈ R)) (R ∈ R) ∼ (R ∈ R) (R ∈ R) ∨ φ(∼ (y ∈ y)) φ(∼ (y ∈ y))
Comp 1;RC 2;RU 1.3;RU 1.3;RU 4;RU 5, 6;RU
{} {φ(∼ (y {φ(∼ (y {φ(∼ (y {φ(∼ (y {φ(∼ (y {φ(∼ (y
∈ y))} ∈ y))} ∈ y))} ∈ y))} ∈ y))} ∈ y))}
√ √7 √7 √7 √7 7
Alvorens de meest elementaire basis van de verzamelingenleer te geven, wil ik het volgende opmerken. Door middel van Comp kunnen we alle ZFC axioma’s 2 Ik beschouw een theorie als een koppel hA, Li, waarbij A een verzameling axioma’s is en L een logica. 3 Ik noem de eigenschappen van de verzamelingenleer hR, ACLu∃m i stellingen, maar dit is misleidend. Alle resultaten zijn onder voorbehoud.
52
behalve het funderingsaxioma afleiden. De axioma’s zullen daarbij als voorwaarden verschijnen. Om bijvoorbeeld het axioma van de machtsverzameling af te leiden, moet de voorwaarde worden ingevoerd dat voor elke verzameling de machtsverzameling consistent moet zijn. Veronderstel nu dat we een consistentiebewijs van ZFC hadden, dan zouden we weten dat aan deze voorwaarde is voldaan. Dit betekent dat indien ZFC consistent is, alle ZFC-resultaten ook hR, ACLu∃m i-resultaten zijn, waaruit we kunnen concluderen dat ACLu∃m een goede explicatie is van de redeneringen die aan de basis van ZFC liggen. Ik begin met een aantal definities. Ik behoud me ook het recht verzamelingen A, B, . . . in te voeren, met hun corresponderende eigenschap α(y) in te voeren als middel om te kunnen redeneren door middel van de bepalende eigenschap van een verzameling. Uiteraard zullen deze verzamelingen worden behandeld alsof ze net als alle andere verzamelingen door middel van comprehensie en onder een voorwaarde zijn ingevoerd.
Definities:
a t b =def (ιx)(y ∈ x ≡ y ∈ a ∨ y ∈ b) a u b =def (ιx)(y ∈ x ≡ y ∈ a ∧ y ∈ b) a ⊆ b =def (∀x)(x ∈ a ⊃ x ∈ b)
Stelling 2 Eigenschappen van ∅: (i) (ii) (iii) (iv) (v) (vi)
ˇ ∼ (∃x)(x ∈ ∅) (∀x)((∀i) ∼ (y ∈ x) ⊃ x = ∅) (∀x)(∅ ⊆ x) (∀x)(x t ∅ = x) (x u ∅ = ∅) (∀x)((x ⊆ ∅) ⊃ x = ∅)
Bewijs: (het bewijs van (v) verloopt analoog aan dat van (iv) en laat ik over aan de lezer)
1 2 3.1 3.2 3.3 3.4 3.5 4
Het bewijs van (i): ˇ (∃x)(∀y)(y ∈ x ≡∼ y = y) {} (∀y)(y ∈ ∅ ≡∼ y = y) {φ(∼ y = y)} ˇ (∃x)(x ∈ ∅) a∈∅ ˇ v(2) ∪ {(∃x)(x ∈ ∅) ∧ (∀x) ∼ (x ∈ ∅)} a ∈ ∅ ⊃∼ a = a v(3.2) ∼a=a v(3.2) a=a ˇ ∼ (∃x)(x ∈ ∅) v(3.2)
53
Comp 1; RC HYP 3.1; RC 2.2; RU 3.2;3.3; RU Axioma 3.1, 3.4, 3.5; RU
5.1 5.2 5.2.1 5.2.2 5.2.3 5.2.4 5.2.5 5.2.6 5.2.7 5.2.8 5.3 5.4
6.1 6.2 6.3 6.4 6.5 6.6 7 8
9.1 9.2 9.3 9.4 9.5
Het bewijs van (ii): (∀y) ∼ (y ∈ a) {} ∼b∈a {} ∼a=∅ (∀x)(∀y)((∀z)(z ∈ x ≡ z ∈ y) ⊃ z = y {} (∀z)(z ∈ a ≡ z ∈ ∅) ⊃ a = ∅ {} ˇ ∼ (z ∈ a ≡ z ∈ ∅) (∃z) {} ∼ (b ∈ a ≡ b ∈ ∅) ˇ ∼ (z ∈ a ≡ z ∈ ∅) ∧ (∀z)(z ∈ a ≡ z ∈ ∅)} {(∃z) b∈∅ v(5.2.5) ∪ φ∼ y = y ∼b=b v(5.2.6) b=b a=∅ v(5.2.6) (∀x)((∀i) ∼ (y ∈ x) ⊃ x = ∅) v(5.2.6) Het bewijs van (iii): ∼ (∀x)(x ∈ ∅ ⊃ x ∈ a) {} ˇ ∼ (x ∈ ∅ ⊃ x ∈ a) (∃x) {} ∼ (b ∈ ∅ ⊃ b ∈ a) ˇ ∼ (x ∈ ∅ ⊃ x ∈ a)∧ (∀x)(x ∈ ∅ ⊃ x ∈ a) {(∃x) b∈∅ v(6.2) ∼b=b v(6.2) ∪ {φ(∼ y = y)} b=b (∀x)(x ∈ ∅ ⊃ x ∈ a) v(6.5) (∀x)(∅ ⊆ x)) v(6.5) Het bewijs van (iv): a∈At∅ α(a)∨ ∼ a = a {φ((y ∈ a ∨ y ∈ b) ∧ (∀z)(y ∈ x ≡ y ∈ a ∨ y ∈ b) ⊃ z = x)} a=a α(a) v(9.2) a∈A
54
HYP 2.4.1; RU HYP EXT 5.2.2; RU 5.2.1, 5.2.3; RU 5.2.4; RC 5.2, 5.2.5; RU 2, 5.2.6; RU Axioma 5.2.1, 5.2.7, 5.2.8; RU 5.1, 5.3;RU
HYP 6.1; RU 6.2; RC 6.3;RU 6.4, 2;RU axioma 6.1, 6.5, 6.6;RU 7; RU
HYP 9.1; RC axioma 9.2, 9.3; RU 9.4; RU
10 11.1 11.2 11.3 11.4 12 13 14 15 16
17.1 17.2 17.3 17.4 17.5 17.6 18
v(9.2) ∪ φ(α(y)) a∈At∅⊃a∈A v9.5 a∈A {} α(a) {φα(y)} α(a)∨ ∼ a = a v(11.2) a∈At∅ v(11.2) ∪ v(9.2) a∈A⊃a∈At∅ v(11.4) (∀x)(∀y)((∀z)(z ∈ x ≡ z ∈ y) ⊃ x = y)) {} (∀z)((z ∈ A ≡ z ∈ A t ∅) ⊃ x = y) {} (∀z)((z ∈ A ≡ z ∈ A t ∅) v(9.5) ∪ v(11.4) A=At∅ v(9.5) ∪ v(11.4) Het bewijs van (vi): (∀x)(x ∈ a ⊃ x ∈ ∅) {} b∈a⊃b∈∅ {} b ∈ a ⊃∼ b = b φ∼ y = y b=b ∼ (b ∈ a) v(17.3) (∀x) ∼ (x ∈ a) v(17.3) (∀x)((x ⊆ ∅) ⊃ x = ∅) v(5.2.6) ∪ v(17.3)
9.1, 9.5; RU HYP 11.1, RU 11.2, RU 11.3; RU 11.1, 11.4; RU EXT 13; RU 10, 12; RU 14, 15;RU
HYP 17.1; RU 2, 11.3; RU axioma 17.3, 17.4; RU 17.5; RU 5.4, 17.6; RU
We kunnen de lege verzameling ook op een andere wijze invoeren, door middel van de universele verzameling. In dat geval moet de consistentie van de universele verzameling verondersteld worden wanneer we iets beweren over de lege verzameling. Resultaten die minder verzamelingen als consistent veronderstellen zijn uiteraard meer wenselijk.
2.4 2.4.1 2.4.2 2.4.3
ˇ (∃x)(∀y)(y ∈ x ≡ y = y) (∀x)(x ∈ V ≡ x = x) ˇ (∃x)(∀y)(y ∈ x ≡∼ (y ∈ V )) (∀x)(x ∈ ∅ ≡∼ (x ∈ V ))
Comp 2.4; RC Comp 2.4.2; RC
55
{} φ(y = y) {} {φ(y = y), φ(∼ (y ∈ V ))}
Wanneer we veronderstellen dat er zoiets is als een universum, is het natuurlijk te veronderstellen dat elke verzameling een complement heeft. In hR, ACLu∃m i is er niets op tegen deze operatie in te voeren, maar het is duidelijk dat niet elke verzameling een complement heeft. Beschouw immers de verzameling {x|x ∈ x}, die voor zover bekend consistent is. Het complement van deze verzameling is de oorzaak van de Russelparadox. Om deze reden zal ik geen complement invoeren. De overige Boolse operaties blijven hun eigenschappen bewaren. Dit blijkt uit volgende stelling: Stelling 3 De volgende eigenschappen gelden voor ∪ en ∩: (i) (ii) (iii) (iv) (v) (vi)
AtB =BtA AuB =BuA A t (B t C) = (A t B) t C A u (B u C) = (A u B) u C A t (B u C) = (A t B) u (A ∪ C) A u (B t C) = (A u B) t (A u C)
Bewijs. De bewijzen zijn eenvoudig, eerder langdradig en steunen eenvoudigweg op de eigenschappen van ∨ en ∧. Ik zal me dan ook beperken tot het bewijs van (i).
1.1 1.2 1.3 2 3.1 3.2 3.3 4 5 6 7
3.5
a∈AtB {} a∈A∨a∈B {φ((y ∈ A ∨ y ∈ B) ∧ ((∀z)(y ∈ z ≡ (y ∈ A ∨ y ∈ B)) ⊃ z = x))} a∈BtA v(1.2) ∪ {φ((y ∈ B ∨ y ∈ A) ∧ ((∀z)(y ∈ z ≡ (y ∈ B ∨ y ∈ A)) ⊃ z = x))} a∈AtB ⊃a∈BtA v(1.2) ∪ v(1.3) a∈BtA {} a∈B∨a∈A {φ((y ∈ B ∨ y ∈ A) ∧ ((∀z)(y ∈ z ≡ (y ∈ B ∨ y ∈ A)) ⊃ z = x))} a∈AtB v(1.2) ∪ {φ((y ∈ A ∨ y ∈ B) ∧ ((∀z)(y ∈ z ≡ (y ∈ A ∨ y ∈ B)) ⊃ z = x))} a∈BtA⊃a∈AtB v(3.2) ∪ v(3.3) (∀x)(∀y)((∀z)(z ∈ x ≡ z ∈ y) ⊃ x = y) (∀z)(z ∈ A t B ≡ z ∈ B t A) ⊃ A t B = B t A AtB =BtA v(1.2) ∪ v(1.3) ∪ v(3.2) ∪ v(3.3)
Besluiten
Is hR, ACLu∃m i een goede benadering van de geaxiomatiseerde verzamelingenleer? En eerste argument voor deze stelling is dat het volledige extensionaliteitsaxioma bewaard wordt. Er lijkt een vorm van concensus te bestaan rond 56
HYP 1.1; RU 1.2; RU 1.1, 1.3; RU HYP 3.1; RU 3.2; RU
EXT 5; RU 2, 4, 6;RU
de stelling dat van alle axioma’s van de verzamelingenleer het extensionaliteitsaxioma het meest karakteristiek is[40, pp.483–484]. Een systeem dat dit axioma niet aanpast is met andere woorden te verkiezen boven een verzamelingenleer met een beperkt extensionaliteitsprincipe. Ten tweede bewaart de lege verzameling, mits consistent, haar belangrijkste klassieke eigenschappen. Ten derde bewaren ∪ en ∩ hun algebra¨ısche eigenschappen commutativiteit en associativiteit en distributiviteit. De resultaten van mijn uitwerking van de na¨ıeve verzamelingenleer kunnen zeer pessimistisch worden ge¨ınterpreteerd. Wie nogal negatief staat tegenover adaptieve logica’s zou immers kunnen stellen dat ik niets anders heb gedaan dan een deel van de Principia Mathematica imiteren, maar na elke stap in een bewijs de clausule er aan toegevoegd heb dat er geen inconsistenties uit mogen volgen. De vraag is nu of dit zo’n slechte zaak is. Ik denk van niet. We weten dat een absoluut consistentiebewijs voor ZFC met de huidige technieken onmogelijk is. Dat alleen al is een reden om aan te nemen dat CnACLu∃m een goede explicatie is voor de redeneringen die aan de grondslag van de geaxiomatiseerde verzamelingenleer hebben gelegen. In de bewijzen in mijn systeem worden immers voorwaarden van de vorm “indien de gebruikte verzamelingen consistent zijn” voor. Zermelo’s axiomatisering heeft axioma’s van twee types, het extensionaliteitsaxioma buiten beschouwing gelaten. Ten eerste zijn er axioma’s die stellen dat bepaalde basisverzamelingen bestaan, het axioma van de oneindigheid en dat van de lege verzameling. De andere groep van axioma’s stelt dat bepaald operaties wanneer uitgevoerd op verzamelingen nieuw verzamelingen opleveren. Een consistentiebewijs had duidelijk gemaakt dat deze methode legitiem is: de lege verzameling IS een verzameling, de machtsverzameling van een verzameling IS een verzameling enz. Maar er is helemaal geen consistentiebewijs voor ZFC, zodat de vraag nog altijd open staat of Zermelo’s methodes aanvaardbaar zijn. De bewijzen in ACLU∃ maken voorwaarden expliciet waarvan nog altijd niet duidelijk is of ze al dan niet voldaan zijn. De huidige toestand van de verzamelingenleer wordt beter weerspiegeld in een bewijs met een adaptieve logica dan in CL-bewijs.
57
Bibliografie [1] Diderik Batens. A universal logic approach to adaptive logics. Logica Universalis, pages 221–242, 2007. [2] Diderik Batens and Joke Meheus. Recent results by the inconsistencyadaptive labourers. In Jean-Yves B´eziau and Walter A. Carnielli, editors, Paraconsistent Logic with no Frontiers, Studies in Logic and Practical Reasoning. North-Holland/Elsevier, 2006. In print. [3] Paul Bernays. A system of axiomatic set theory – part i. The Journal of Symbolic Logic, 2(1):65–77, 1937. [4] Paul Bernays. A system of axiomatic set theory – part ii. The Journal of Symbolic Logic, 6(1):1–17, 1941. [5] Paul Bernays. A system of axiomatic set theory: Part iii. The Journal of Symbolic Logic, 7(2):65–89, 1942. [6] Paul Bernays. A system of axiomatic set theory: Part iv. The Journal of Symbolic Logic, 7(4):133 – 145, 1942. [7] Paul Bernays. A system of axiomatic set theory: Part v. The Journal of Symbolic Logic, 8(4):89–106, 1943. [8] Paul Bernays. A system of axiomatic set theory – part vi. The Journal of Symbolic Logic, 13(2):65–79, 1948. [9] Paul Bernays. A system of axiomatic set theory – part vii. The Journal of Symbolic Logic, 19(2):81–96, 1954. [10] Paul Bernays. Axiomatic Set Theory. Dover Publications, 1991. [11] George Boolos. The iterative conception of set. The Journal of Philosophy, 68(8):215–231, 1971. [12] Georg Cantor. Uber unendliche, lineare punktmannigfaltigkeiten, 5. In Cantor1932 [16], pages 545–586. [13] Georg Cantor. Uber eine elementare frage der mannigfaltigkeitslehre. In Cantor1932 [16], pages 75–78. [14] Georg Cantor. Beitr¨ age zur begrundung der transfiniten mengenlehre i. In Cantor1932 [16], pages 481–512.
58
[15] Georg Cantor. Beitr¨ age zur begrundung der transfiniten mengenlehre ii. In Cantor1932 [16], pages 207–246. [16] Georg Cantor. Gesammelte Abhandlungen. Georg Olms Verlagsbuchhandlung, Hildesheim, 1962. [17] Rudolf Carnap. The Logical Syntax of Language. Kegan Paul, London, 1937. [18] Rudolf Carnap. Introduction to Symbolic Logic and its Applications. Dover Publications, 1958. [19] Irving Copi. The burali-forti paradox. Philosophy of Science, 25(4):281– 286, 1958. [20] Dirk Van Dalen. L.E.J Brouwer en de grondslagen van de wiskunde. Epsilon Uitgaven, Utrecht, 2005. [21] Joseph Dauben. Georg Cantor : his mathematics and philosophy of the infinite. Harvard University Press, 1979. [22] Richard Dedekind. Essays on the Theory of Numbers. Dover, 1963. [23] Burton Dreben en Akihiro Kanamori. Hilbert and set theory. Synth`ese, 110:77 – 125, 1997. [24] Bertrand Russell en A.N. Whitehead. Principia Mathematica, volume 1. Cambridge University Press, 1910. [25] Jos´e Ferreir´ os. The road to modern logic-an interpretation. The Bulletin of Symbolic Logic, 7(4):441–484, 2001. [26] Thomas Forster. Quine’s nf–60 years on. The American Mathematical Monthly, 104:838–845, 1997. [27] Abraham A. Fraenkel. The notion definite” and the independence of the ” axiom of choice, pages 284–289. In vanHeijenoort1967 [52], 1922. [28] Gottlob Frege. The Foundations of Arithmetic. Pearson Longman, 2007. [29] Warren D. Goldfarb. Logic in the twenties: The nature of the quantifier. The Journal of Symbolic Logic, 44(3):351 – 368, 1979. [30] Ivor Grattan-Guinness. An unpublished paper by Georg Cantor: Principien einer theorie der Ordnungstypen. Acta Mathematica, 124(1):65 – 107, 1970. [31] Ivor Grattan-Guinness. Dear Russell - Dear Jourdain. Columbia University Press, 1977. [32] Ivor Grattan-Guinness. On the development of logics between the two world wars. The American Mathematical monthly, 88(7):495–509, 1981. [33] Ivor Grattan-Guinness. The Search for Mathematical Roots: 1870-1940. Princeton University Press, 2000. [34] Michael Hallett. Cantorian set theory and limitation of size. Oxford Logic Guides, Vol. l0. Clarendon Press, Oxford, 1984. 59
[35] Randall Holmes. Elementary set theory with a universal set. Academia, Louvain-la-Neuve, 1998. [36] Akihiro Kanamori. The mathematical development of set theory from cantor to cohen. The Bulletin of Symbolic Logic, 2(1):1 – 71, 1996. [37] Akihiro Kanamori. The mathematical import of zermelo’s well-ordering theorem. The Bulletin of Symbolic Logic, 3(3):281–331, 1997. [38] Akihiro Kanamori. Zermelo and set theory. The Bulletin of Symbolic Logic, 10(4):487 – 553, 2004. [39] Shaughan Lavine. Understanding the Infinite. Harvard University Press, 1994. [40] Penelope Maddy. Believing the axioms i. The Journal of Symbolic Logic, 53(2):481–511, 1988. [41] W.V. Quine. New foundations for mathematical logic. American Mathematical Monthly, 44:70–80, 1937. [42] W.V. Quine. On the theory of types. The Journal of Symbolic Logic, 3(4):125 – 139, 1938. [43] W.V. Quine. Russell’s ontological development. The Journal of Philosophy, 63(21):657–667, 1966. [44] Frank P. Ramsey. The foundations of mathematics. Proceedings of the London Mathematical Society, 25(5):338–384, 1925. [45] Raphael M. Robinson. The theory of classes a modification of von neumann’s system. The Journal of Symbolic Logic, 2(1):29 – 36, 1937. [46] Bertrand Russell. Mathematical logic as based on the theory of types. American Journal of Mathematics, 30:222–262, 1908. [47] Bertrand Russell. The Principles of Mathematics. W.W. Norton & Company ltd., London, 1996. [48] Thoralf Skolem. Some remarks on axiomatized set theory. In vanHeijenoort1967 [52], pages 290–301. [49] Ernst Specker. The axiom of choice in quine’s new foundations for mathematical logic. Proceedings of the National Academy of Sciences of the U.S.A., 39:972–975, 1953. [50] W.W. Tait. Between Logic and Intu¨ıtion: Essays in Honor of Charles Parsons, chapter Cantors Grundlagen and the Paradoxes of Set Theory, pages 269–290. CUP, Cambridge, 2000. [51] Alfred Tarski. Introduction to logic and to the methodology of deductive sciences. Dover Publications, New York, 19995. [52] Jean van Heijenoort. From Frege to G¨odel. a source book in mathematical logic 1879–1931, 1967. 60
[53] John von Neumann. On the introduction of transfinite numbers. In vanHeijenoort1967 [52], pages 346–354. [54] John von Neumann. An axiomatization of set theory. In vanHeijenoort1967 [52], pages 393–413. [55] John von Neumann. Collected Works Volume 1. Pergamon Press, Oxford, 1961. [56] John von Neumann. Eine axiomatiserung der mengenlehre. [55], pages 35–57. [57] John von Neumann. Zur einf¨ uhrung der transfiniten zahlen. [55], pages 24–34. [58] Herman Weyl. The Continuum: A Critical Examination of the Foundation of Analysis. Dover Publications, New York, 1994. [59] Hermann Weyl. Mathematics and logic. Monthly, 53(1):2–13, 1946.
The American Mathematical
[60] Ludwig Wittgenstein. Tractatus Logico-philosophicus. Polak & Van Gennep, Amsterdam, 1982. [61] Richard Zach. Completeness before post: Bernays, hilbert, and the development of propositional logic. The Bulletin of Symbolic Logic, 5(3):331–366, 1999. [62] Ernst Zermelo. Proof that every set can be well-ordered. In vanHeijenoort1967 [52], pages 139–141. [63] Ernst Zermelo. Investigations in the foundations of set theory i. In vanHeijenoort1967 [52], pages 199–215. [64] Ernst Zermelo. A new proof of the possibility of a well-ordering. In vanHeijenoort1967 [52], pages 183–198.
61