Het keuzeaxioma is een enigszins controversieel axioma uit de verzamelingenleer, dat in 1904 werd geformuleerd door Ernst Zermelo., Beweis, dass jede Menge wohlgeordnet werden kann, Mathematische Annalen, 1904, vol 59, pag. 514–516. Gearchiveerd op 17 januari 2016. Het keuzeaxioma zegt dat het, gegeven een oneindige verzamelingBij een eindige verzameling is het keuzeaxioma niet nodig van verzamelingen, altijd mogelijk is om uit elk van deze verzamelingen precies één element te kiezen, ook al is er geen keuzeregel gedefinieerd die bepaalt welk element uit ieder van deze verzamelingen gekozen moet worden. Preciezer geformuleerd:
Zij een oneindige verzameling van niet-lege verzamelingen De zijn de namen van de verzamelingen in , de index duidt niet op hun onderlinge ordening, omdat die er niet is. dan kan men uit iedere verzameling een element kiezen, dat wil zeggen dat er een keuzefunctie bestaat, gedefinieerd op , zodanig dat voor elke verzameling in geldt, dat een element is van .
of in formule
Het keuzeaxioma wordt in tal van deelgebieden van de wiskunde gebruikt. Het heet een axioma omdat het niet kan worden bewezen uit de andere axioma's van de verzamelingenleer. Het is er echter ook niet mee in tegenspraak. Het is equivalent met een aantal stellingen, waaronder het lemma van Zorn en de welordeningsstelling. Elk van deze zou dus ook als axioma beschouwd kunnen worden, en het keuzeaxioma een stelling die op basis van dat axioma bewezen kan worden.
Het keuzeaxioma wordt niet vereist als er sprake is van een eindig aantal verzamelingen of als er wel een "keuzeregel" is gedefinieerd.
Geschiedenis Het keuzeaxioma werd in 1904 door Ernst Zermelo opgesteld. Hoewel aanvankelijk omstreden, wordt het keuzeaxioma nu zonder voorbehoud door de meeste wiskundigen gebruikt., 1977, p. 348ff; Martin-Löf 2008, blz. 210. Een motivatie voor dit gebruik is dat een aantal belangrijke wiskundige resultaten, zoals de stelling van Tychonov, het keuzeaxioma voor hun bewijzen vereisen. Hedendaagse verzamelingentheoretici bestuderen ook axioma's die niet compatibel zijn met het keuzeaxioma, zoals het axioma van bepaaldheid. In tegenstelling tot het keuzeaxioma worden deze alternatieven gewoonlijk niet voorgesteld als axioma's van de wiskunde, maar alleen als beginselen met interessante gevolgen in de verzamelingenleer.
Bewering Een keuzefunctie is een functie , gedefinieerd op een verzameling van niet-lege verzamelingen, zodanig dat voor elke verzameling in , een element van is. Met dit concept kan het axioma als volgt worden geformuleerd: Voor elke verzameling van niet-lege verzamelingen bestaat er een keuzefunctie gedefinieerd op .
De ontkenning van het keuzeaxioma stelt dat er een verzameling van niet-lege verzamelingen bestaat die geen keuzefunctie heeft.
Elke keuzefunctie op een verzameling van niet-lege verzamelingen kan worden beschouwd als (of kan worden geïdentificeerd met) een element van het cartesisch product van de verzamelingen in . Dit leidt tot een gelijkwaardige stelling aan het keuzeaxioma: Gegeven enige verzameling van niet-lege verzamelingen is hun cartesisch product een niet-lege verzameling.
Varianten Er zijn vele andere gelijkwaardige formuleringen van het keuzeaxioma. Deze zijn in die zin equivalent dat zij, in het bijzijn van andere fundamentele axioma's van de verzamelingenleer, het keuzeaxioma impliceren en dat omgekeerd het keuzeaxioma door hen geïmpliceerd wordt.
Een variant vermijdt het gebruik van keuzefuncties door elke keuzefunctie in feite te vervangen door haar bereik. Gegeven een willekeurige verzameling van paarsgewijs disjuncte niet-lege verzamelingen, bestaat er ten minste een verzameling , die precies één element gemeen heeft met elk van de verzamelingen in .Herrlich, blz. 9.
Een ander gelijkwaardig axioma beschouwt alleen verzamelingen , die in wezen machtsverzamelingen van andere verzamelingen zijn: Voor elke verzameling heeft de machtsverzameling van (waar de lege verzameling uit is verwijderd) een keuzefunctie.
Auteurs die gebruikmaken van deze formulering, spreken vaak van de keuzefunctie op , maar ga ervan uit dat dit een iets andere notie van een keuzefunctie betreft. Haar domein is de machtsverzameling op (waar de lege verzameling uit is verwijderd), en is dus zinvol voor elke verzameling , terwijl met de definitie, die elders in dit artikel wordt gebruikt, het domein van een keuzefunctie op een verzameling van verzamelingen die verzameling zelf is en dus alleen voor verzamelingen van verzamelingen zinvol is. Met deze alternatieve notie van een keuzefunctie kan het keuzeaxioma compact als volgt worden geformuleerd Elke verzameling heeft een keuzefunctie., "Axiomatic Set Theory", Dover, 1972 (1960), , blz. 240. wat gelijkwaardig is aan Voor elke verzameling is er een functie , zodanig dat voor elke niet-lege deelverzameling van , in ligt. De ontkenning van het keuzeaxioma kan dus uitgedrukt worden als: Er is een verzameling , zodanig dat voor alle functies (op de verzameling van niet-lege deelverzamelingen van ), er een bestaat, zodanig dat niet in ligt.
Beperking tot eindige verzamelingen De gebruikelijke formulering van het keuzeaxioma refereert niet aan enige specifieke oneindige verzameling, en heeft als zodanig een eindige restrictie die beweert dat elke eindige verzameling van niet-lege verzamelingen een (eindige) keuzefunctie heeft. De eindige restrictie is een stelling van de Zermelo-Fraenkel-verzamelingenleer (ZF) en kan gemakkelijk worden bewezen door gebruik te maken van volledige inductie. (2003), pag. 209-210, 215-216. De intuïtiviteit van het keuzeaxioma kan te danken zijn het aan het veralgemenen van dit eindige geval.
Gebruik Hoewel het keuzeaxioma toen nog niet formeel was geformuleerd, werd het in de laat-19de eeuw wel al vaak impliciet gebruikt. Na bijvoorbeeld te hebben vastgesteld dat de verzameling alleen niet-lege verzamelingen bevat, zou een wiskundige gezegd kunnen hebben: "Laat voor alle in een van de elementen van zijn." In het algemeen is het onmogelijk om te bewijzen dat bestaat zonder het keuzeaxioma, maar dit lijkt totdat Zermelo zich hierin verdiepte onopgemerkt te zijn gebleven.
Niet elke situatie vereist het keuzeaxioma. Voor eindige verzamelingen volgt het keuzeaxioma uit de andere axioma's van de verzamelingenleer. In dat geval is het gelijkwaardig met zeggen dat als we meerdere (maar wel een eindig aantal) dozen hebben, die elk ten minste een object bevatten, dat wij dan uit elke doos precies een object kiezen. Uiteraard kunnen we dit doen: We beginnen bij de eerste doos, kiezen een object, gaan naar de tweede doos, kiezen een object, en ga zo maar door. Het aantal dozen is eindig, dus uiteindelijk komt onze keuzeprocedure tot een einde. Het resultaat is een expliciete keuzefunctie: een functie die uit de eerste doos het eerste object geeft dat we kozen, uit de tweede doos het tweede object dat we kozen, en zo verder. (Een formeel bewijs voor alle eindige verzamelingen zou gebruikmaken van het principe van volledige inductie.)
Voor bepaalde oneindige verzamelingen is het ook mogelijk om te voorkomen dat wij de hulp van het keuzeaxioma moeten inroepen. Stel bijvoorbeeld dat de elementen van verzamelingen van natuurlijke getallen zijn. Iedere niet-lege verzameling van natuurlijke getallen heeft een kleinste element, dus om onze keuzefunctie te specificeren kunnen we gewoonweg zeggen dat het elke verzameling afbeeldt op het kleinste element van deze verzameling. Dit geeft ons een definiete keuzefunctie van een element uit elke verzameling en we kunnen een expliciete uitdrukking formuleren, die ons vertelt welke waarde onze keuzefunctie aanneemt. Iedere keer als het mogelijk blijkt te zijn om zo'n expliciete keuze te specificeren, is het niet nodig een beroep te doen op het keuzeaxioma.
De moeilijkheid treedt op wanneer er geen natuurlijke keuze van elementen uit elke verzameling is. Als we geen expliciete keuzes kunnen maken, hoe weten we dat onze verzameling bestaat? Stel bijvoorbeeld dat de verzameling is van alle niet-lege deelverzamelingen van de reële getallen. Allereerst kunnen we proberen net te doen alsof eindig is. Als we proberen om een element uit elke verzameling te kiezen, dan zal, omdat oneindig is, onze keuzeprocedure nooit tot een einde komen, en zullen we dus ook nooit in staat zijn een keuzefunctie voor alle elementen van te produceren. Vervolgens zouden wij kunnen proberen om het kleinste element uit elke verzameling te specificeren. Sommige deelverzamelingen van de reële getallen kennen echter geen kleinste elementen. Bijvoorbeeld, het open interval (0,1) heeft geen kleinste element: als in (0,1) ligt, dan doet dat ook en is strikt genomen altijd kleiner dan . Deze poging mislukt dus ook.
De verklaring voor het feit dat we in staat zijn de kleinste elementen uit deelverzamelingen van de natuurlijke getallen te kiezen, is dat de natuurlijke getallen zijn uitgerust met een welgeordendheid: Iedere niet-lege deelverzameling van de natuurlijke getallen heeft onder deze natuurlijke ordening een uniek kleinste element. Men zou kunnen zeggen, "Zelfs als de gebruikelijke ordening van de reële getallen niet werkt, kan het mogelijk zijn om een andere ordening van de reële getallen te vinden, die welgeordend is. In dat geval kan onze keuzefunctie het kleinste element van elke verzameling vinden met inachtneming van onze ongebruikelijke ordening". Het probleem wordt dan het vinden van de constructie van een welgeordendheid, wanneer die voor haar bestaan het keuzeaxioma blijkt te vereisen. Elke verzameling kan dan en slechts dan welgeordend zijn als het keuzeaxioma waar is.
Niet-constructieve aspecten Een bewijs dat gebruikmaakt van het keuzeaxioma is, in een betekenis van het woord, niet-constructief: zelfs als het bewijs het bestaan van een object staaft, kan het toch onmogelijk zijn om het object in de taal van de verzamelingenleer te definiëren. Terwijl het keuzeaxioma bijvoorbeeld impliceert dat er een welgeordendheid van de reële getallen bestaat, zijn er modellen van de verzamelingenleer met het keuzeaxioma, waarin geen welgeordendheid van de reële getallen kan worden gedefinieerd. Als een ander voorbeeld kan men van een deelverzameling van de reële getallen, die niet Lebesgue-meetbaar is, bewijzen dat deze bestaat door gebruik te maken van het keuzeaxioma, maar is het consistent dat geen enkele van dergelijke verzamelingen definieerbaar is.
Het keuzeaxioma produceert deze ondefinieerbare zaken (objecten waarvan men door gebruik te maken van een niet-constructief bewijs kan bewijzen dat zij bestaan, maar die niet expliciet geconstrueerd kunnen worden), wat in strijd kan zijn met sommige filosofische principes. Omdat er geen welgeordendheid van alle verzamelingen bestaat, hoeft een constructie die zich verlaat op een welgeordendheid geen kanoniek resultaat te produceren, zelfs als een kanoniek resultaat gewenst zou zijn (zoals vaak het geval is in de categorietheorie). In het constructivisme vereist men dat alle existentiebewijzen volledig expliciet zijn. Dat wil zeggen dat men in staat moet zijn om, op een expliciete en canonieke manier, alles te construeren waarvan men kan bewijzen dat het bestaat. Dit raamwerk verwerpt het volledige keuzeaxioma, omdat het keuzeaxioma het bestaan van een object stelt zonder haar structuur op unieke wijze te bepalen. In feite laat de stelling van Diaconescu-Goodman-Myhill zien hoe de constructief onaanvaardbare wet van de uitgesloten derde, of een beperkte vorm daarvan, in de constructieve verzamelingenleer valt af te leiden uit de aanname van het keuzeaxioma.