Het Probleem uit Katowice
De klimaatttop in Katowice verliep/verloopt moeizaam. Maar het klimaat is niet het enige probleem dat aan Katowice verbonden is.
Het probleem uit Katowice gaat over iets totaal anders. Eén manier om het in te leiden is als volgt. Een eenvoudige opgave: stel dat twee verzamelingen evenveel punten hebben, bewijs dat ze evenveel deelverzamelingen hebben.
Dat klinkt voor de hand liggend en het bewijs is, zeker voor een eerstejaarsstudent, niet moeilijk. De juiste wiskundige formulering van `X en Y hebben evenveel elementen’ is er bestaat een bijectie (ook wel een-een-correspondentie genoemd) f:X→Y tusen de twee verzamelingen. Uit die bijectie maak je met gemak een bijectie F tussen de families deelverzamelingen: F(A)=f[A].
Het omgekeerde probleem zou zijn: stel dat twee verzamelingen evenveel deelverzamelingen hebben, bewijs dat ze evenveel punten hebben.
Dat is een stuk lastiger op te lossen; het lukt nog wel voor eindige verzamelingen want een verzameling met n punten heeft 2n deelverzamelingen en als 2m=2n dan volgt m=n. Echter, dat gebruikt extra informatie, meer dan alleen het bestaan van de bijectie F tussen de families deelverzamelingen. En, geloof het of niet: met alleen de informatie dat zo’n F bestaat is de opgave niet te maken. Dat volgt uit het werk dat Paul Cohen heeft gedaan bij zijn deel van de oplossing van Cantor’s Continuumhypothese: daarbij creërde hij een situatie met twee oneindige verzamelingen met evenveel deelverzamelingen maar niet met evenveel punten.
De som wordt maakbaar als we aannemen dat de bijectie wat meer structuur heeft; als je bijvoorbeeld eist dat F en zijn inverse de deelverzamelingrelatie bewaren, dat wil zeggen A⊂B dan en slechts dan als F(A)⊂F(B), dan kun je wel een bijectie tussen de verzamelingen X en Y maken: F moet namelijk de éeacute;npuntsverzamelingen op elkaar afbeelden en dat geeft automatisch de gewenste bijectie.
In de wiskunde is het soms zo dat we `kleine’ verzamelingen verwaarlozen; zo kunnen we afspreken dat we verzamelingen die maar een eindig aantal punten verschillen als gelijk beschouwen. Dat nu leidt ons tot Het Probleem van Katowice: als je weet dat er afbeelding is die bijectief is en ⊂ respecteert, waarbij eindige verschillen er niet toe doen, kun je dan een bijectie tussen de gegeven verzamelingen maken?
Dat probleem is een stuk moeilijker dan de andere maar het is opgelost, bijna: het antwoord is bijna altijd ja, er zijn twee oneindige verzamelingen, met verschillende aantallen elementen, waarvoor we nog niet hebben kunnen bewijzen dat zo’n bijna-bijectie niet bestaat.
Voor wie meer wil weten: hier is een overzicht van het probleem. Met een waarschuwing: zonder een behoorlijke dosis wiskundige basiskennis is het artikel lastig te lezen.
En waarom is dit Het probleem uit Katowice? Het werd opgeworpen door een student aan de Silezische Universiteit in Katowice en omdat het overgebleven geval zo weerbarstig is gebleken heeft het probleem onder wiskundigen deze naam gekregen.
Recent Comments