Posts in category Georg Cantor
Lariekoek? II
We gaan het artikel Sets and Sentences van D. Terrence Langendoen en Paul Postal opnieuw lezen. De vorige keer heb ik de inhoud beschreven; nu bekijken we die nogmaals, maar met een wiskundig oog.
Zoals vorige keer beschreven gaat het er in het artikel om te laten zien dat in een Natuurlijke Taal de mogelijke zinnen een zeer grote collectie vormen: te groot om `verzameling’ genoemd te mogen worden. We volgen de redenering stap voor stap.
De definitie van Co-ordinate compound constituent is vorige keer al schematisch weergegeven door het volgende plaatje:
De top T is hier de co-ordinate compound constituent en de andere knopen zijn de conjucten waar T uit gevormd is. Die conjuncten bestaan uit een connectief en `constituent’. Ietwat simplistisch: T ontstaat door de constituents door middel van connectieven aan elkaar te plakken.
In punt (6) van het artikel wordt gedetailleerd beschreven hoe dat plakken in zijjn werk moet gaan, of preciezer: er wordt geformuleerd wat de relatie tussen de verzameling U van constituents en de compound T moet zijn. Uit die formulering zou je een plakmethode kunnen distilleren. Van punt (6) citeer ik deelpunt (d)
if two elements of U occur as subconjuncts of conjuncts C1 and C2 of T then C1 and C2 occur in a fixed order. Where C1 and C2 are of distinct length assume the shorter precedes; where C1 and C2 are the same length, assume some arbitrary order.
Als een student zoiets opschrijft trek ik mijn rode pen: ten eerste om het gebruik van `fixed’ en `arbitrary’ vlak achter elkaar, en ten tweede om dat `arbitrary’. Dat lees ik als “doe maar wat” en daar schrijf ik dus “Hoe dan?” bij. Ik kom straks nog op dit punt terug.
Verder in punt (6) wordt T een `co-ordinate projection’ van U genoemd en U de `projection set’ van U. Inderdaad: U is door T uniek bepaald maar niet andersom; het woord `arbitrary’ lijkt daar op te duiden.
Dan volgt een alinea waarin wordt beargumenteerd dat elke verzameling U een co-ordinate projection heeft. Dit zou `straightforward’ moeten zijn, volgens de schrijvers althans. Hier zijn de stappen (de `category Q’ die ter sprake komt is een niet nader gespecificeerde abstracte categorie van zinnen):
- Neem een verzameling U en laat k de kardinaliteit van U zijn (eindig of oneindig)
- Citaat:
Clearly, from the purely formal point of view, there is a co-ordinate compound W belonging to the category Q.
Dat klinkt mooi maar het heeft geen enkele bewijskracht; geen enkele rechtvaardiging, geen indicatie waar die W vandaan zou moeten komen. - Citaat:
Since there are no size restrictions on co-ordinate compounds, W can have any number, finite (more than one) or transfinite of immediate constituents.
Dit is slechte (wiskundige) stijl: eerst lijkt W vast, dan gaat hij alsnog variëren. Een betere formulering zou zijn: “er zijn co-ordinate compounds van alle mogelijke kardinaliteiten”. Die betere formulering maakt de bewering niet automatisch waar, er is nog steeds geen concrete rechtvaardiging gegeven. - Citaat:
W can then, in particular have exactly k such constituents.
Nogmaals: die vaste W is omgevormd tot een gepaste W. Niet mooi, maar vooruit dan maar. - De deelconjuncts van de conjuncts in W vormen een verzameling V die, volgens de regels in (6), kardinaliteit k heeft. Niks mis mee.
- Citaat:
To show that W is a co-ordinate projection of U, it then in effect suffices that there exist a one-to-one mapping from U to V.
Niet dus. Hoe je definitie (6) ook wendt of keert, dit haal je er niet uit. Wil W een co-ordinate projection van U zijn dan zal de verzameling V exact gelijk aan de verzameling U moeten zijn; een bijectieve afbeelding tussen die twee is echt niet genoeg. - Citaat:
But this is trivial, since the two sets have the same number of elements.
Dit klopt, maar ik verdenk de schrijvers ervan dat ze niet doorhebben wat hier achter zit. Georg Cantor definieerde `kardinaliteit’ op een manier die eigenlijk nietszeggend is, zie de tweede post in deze serie. Hij bewees daarna dat `hebben gelijke kardinaliteit’ equivalent is met `er bestaat een bijectieve afbeelding tussen’, maar tegenwoordig is dat laatste de definitie van het eerste.
Afsluiting
In het artikel formuleren Langendoen en Postal nu een afsluitingsprincipe. Na een waarschuwing dat niet elke co-ordinate projection noodzakelijkerwijs welgevormd is komt het volgende Closure Principle for Co-ordinate Compounding:
If U is a set of constituents each belonging to the collection, Sw, of (well-formed) constituents of category Q of any natural language, then Sw contains the co-ordinate projection of U.
Hoezo “the co-ordinate projection”? Uniciteit van die projecties is nog niet aan de orde geweest en over die collectie Sw is niet (expliciet) gezegd dat elke verzameling zinnen maar op één manier tot een grotere zin samen te voegen is.
Na een opmerking over het recursieve karakter van dit principe noemen de schrijvers de categorie S van zinnen als een categorie waarop het principe van toepassing is, althans: ze beweren dat (maar geven geen bewijs).
Dat weerhoudt ze er niet van het principe twee keer uit te spreken voor S. Eerst via een bijna letterlijke herhaling, met Q vervangen door S, en dan nog een keer met behulp van een formule(!): the co-ordinate projection van een verzameling U noteren we CP(U) en dan krijgen we
(∀U)(U⊂L → CP(U)∈L)
Hierin is L de collectie van alle elementen van de categorie S van een natuurlijke taal (voor mij betekent dat L=S want L en S hebben dezelfde elementen, maar er is misschien een subtiel verschil tussen de collectie van elementen van een categorie en de categorie zelf). Merk op dat hier het onbepaalde lidwoord definitief bepaald geworden is. Zonder het expliciet uit te spreken hebben de schrijvers kennelijk besloten dat compounding maar op één manier kan; de functienotatie CP(U) kan niet anders geïnterpreteerd worden.
Maar hoe is CP(U) gedefinieerd dan? Dat wordt niet duidelijk; een illustratie met met verzamelingen van drie, vier zinnen die tot één worden samengevoegd overtuigt mij niet.
Een soort van hierarchie
Dan komt eindelijk datgene waar ik al lang op zat te wachten: The Cantorian Analogue, waarin bewezen gaat worden dat de zinnen in een natuurlijke taal geen verzameling vormen. Overigens, een definitie van `verzameling’ hebben we nog niet echt gehad.
Het bewijs gaat aanvankelijk met gebruik van een verzameling zinnen als in de vorige post, de schrijvers gebruiken {Babar is happy; I know that Babar is happy; I know that I know that Babar is happy, …}. Die verzameling noemen ze S0.
Ik kort de zinnen even af: z0 is “Babar is happy” en, gegeven zn is zn+1 de zin “I know that zn“.
Onder de aanname dat de natuurlijke taal L aan het afsluitingsprincipe voldoet omvat L ook de verzameling S1 die bestaat uit S0 en de co-ordinate projections van de deelverzamelingen van S0 met twee of meer elementen. De formulering verdient het nauwkeurig gelezen te worden.
Then L also contains a set S1, made up of all the sentences of S0 together with all and only the co-ordinate projections of every subset of S0 with at least two elemente, that is, with a set containing one co-ordinate projection for each member of the power set of S0 whose cardinality is at least 2.
Deze zin deugt niet. De delen voor en na `that is’ spreken elkaar tegen. De eerste versie van S1 bevat alle co-ordinate projections van alle deelverzamelingen van S0 — de projecties van iedere deelverzameling —; de tweede versie bevat van elke deelverzameling (precies) één projectie. Daarnaast is de eerste versie uniek bepaald door het `all and only’, daar is `the set S1‘ dus meer op zijn plaats; in het tweede deel past `a set’ wel.
Je zou het meervoud `projections’ enkelvoud kunnen maken; dat sluit wat beter aan bij de formulering van de afsluitingeigenschap, the projection zou dan telkens de functiewaarde CP(U) kunnen zijn. Maar dan gaat het ook mis: vóór het `that is’ is de keuze van projectie duidelijk vastgelegd, maar na `that is’ zit er nog potentiële willekeur in de keuze van projectie, er staat niet expliciet dat die one projection ook echt CP(U) is.
De schrijvers geven dan een voorbeeld van hoe S1 er uit zou kunnen zien (dus toch geen welbepaalde verzameling):
{z0; z1; z2; …; z0 and z1; z0 and z2; …; z0, z1, and z2 …} (voor alle duidelijkheid: de punt-komma’s scheiden de zinnen en de komma’s dienen als connectieven in de zinnen).
Dan volgt een lange alinea waarin met veel omhaal van woorden de kardinaliteit van S1 wordt bepaald. Door het `één projectie per verzameling’ is dat niet moeilijk: dat is dezelfde kardinaliteit als die van de familie van alle deelverzamelingen van S0 en omdat S0 aftelbaar oneindig is, en dus kardinaliteit ℵ0 (alef-nul) heeft is die kardinaliteit gelijk aan 2ℵ0 (2-tot-de-macht-alef-nul) en niet ℵ1, zoals Langendoen en Postal opschrijven. Ergens bij hun bestudering van de verzamelingenleer is er iets misgegaan en is de Continuümhypothese waar geworden.
Zoals wellicht verwacht wordt dit proces voortgezet. Er komt een rij verzamelingen S0, S1, S2, …, netjes recursief gedefinieerd door Sn+1=Sn∪Kn. Hierbij is Kn telkens de verzameling projecties van deelverzamelingen van Sn. In formule
Kn={x:(∃y)(y⊆Sn ∧ x is the co-ordinate projection of y)}
Hier had dus ook Kn={x:(∃y)(y⊆Sn ∧ x=CP(y))} kunnen staan.
Op deze manier komt er een hierarchie van verzamelingen zinnen tot stand; die zinnen worden steeds complexer en de verzamelingen steeds groter. De schrijvers claimen onterecht dat voor elke n het kardinaalgetal van Sn gelijk is aan ℵn. De juiste formule is een machtsverheffing met een torentje van n tweeën, met bovenaan nog een ℵ0. Dat kardinaalgetal noteren we in de verzamelingenleer als ℶn (beth-n).
Dit verhaal culmineert in wat de schrijvers The NL Vastness Theorem noemen: Natural Languages are not sets.
Het bewijs verloopt uit het ongerijmde. Neem aan dat L een verzameling is. Het proces van co-ordinate projection definieert een injectieve afbeelding van de machtsverzameling van L naar L zelf. Dat kan niet volgens een stelling van Cantor: elke verzameling heeft strikt meer deelverzamelingen dan elementen. Tegenspraak.
Er is echter een groot MAAR, en daar gaan we het nu over hebben.
Ordeningen en lengten
Het `bewijs’ in het artikel staat vol met impliciete aannamen over het gedrag van verzamelingen die een niet-wiskundige waarschijnlijk niet zo snel zullen opvallen. Er zijn twee dingen die nogal schadelijk zijn voor de redenering zoals hierboven beschreven.
Ten eerste de ordening, ik heb er bij de beschrijving van de co-ordinate projection al op gezinspeeld: daar zit, op zijn zachtst gezegd, een onvolledigheid.
Die onvolledigheid duikt op bij de overgang van S1 naar S2, en nog erger bij de stap daarna van S2 naar S3.
Bij de eerste stap, van S0 naar S1, is er niets aan de hand: we hebben onze verzameling S0 genummerd en die nummering ordent elke deelverzameling van S0, waarmee zo’n deelverzameling een natuurlijke projectie heeft, ook als deze oneindig veel elementen heeft. Dit levert natuurlijk wel zinnen zonder einde op.
Daarna, van S1 naar S2, hebben we een probleem: er zijn (overaftelbaar) veel zinnen van oneindige lengte (allemaal even lang als de verzameling der natuurlijke getallen). Daar gaat het `fixed’ en `arbitrary’ van punt (6)(d) dus wringen. Hoe orden je zo’n verzameling zinnen? De heren Langendoen en Postal spreken zich daar niet over uit.
Gelukkig kunnen we hier de lexicografische ordening gebruiken: kijk naar het eerste teken (inclusief spaties) waar de zinnen verschillen en neem een besluit op basis van de ordening van de tekens. Zie ook de post Boekenplanken voor gevorderden waar een aspect van die ordening aan de orde komt dat hier de zaak ook compliceert: er zijn heel veel verzamelingen die de eigenschap hebben dat tussen elk tweetal zinnen oneindig veel zinnen staan en die ook geen eerste zin hebben. Als we die ordening gebruiken om projecties te maken dan krijgen we dus zinnen zonder begin, zonder einde, en met voegwoorden die gaan ten minste één kant niet zien wat ze verbinden.
Het kan nog erger. We kunnen de verzameling S2 opvatten als de familie van alle deelverzamelingen van de reële rechte R. En op die familie kan geen lineaire ordening gedefinieerd worden. Het sleutelbegrip is hier `definiëren’: er is geen formule die de familie deelverzamelingen van R zó sorteert dat elk tweetal verzamelingen vergelijkbaar is. De stap van S2 naar S3 kan eigenlijk niet genomen worden.
Ten tweede is er nog het begrip lengte van een zin. Cantor heeft een hele theorie van orde-typen (`lengten’) van lineair geordende verzamelingen ontwikkeld. Wat daar vooral opvalt is dat er veel onvergelijkbare orde-typen zijn. En die kom je ook tegen bij de stap van S2 naar S3: het voorsorteren op `lengte’ gaat dus ook al niet.
Welordeningen?
“Maar, er zijn toch welordeningen?”, hoor ik degenen die wat verzamelingenleer hebben bestudeerd opwerpen. Dat klopt, en we hebben ook nog Zermelo’s Welordeningsstelling, die zegt dat elke verzameling een welordening heeft. Bij een welordening zijn de elementen zo gesorteert dat elke deelverzameling (niet-leeg) een eerste element heeft. Welordeningen zijn ook nog onderling vergelijkbaar, dus die co-ordinate projections schrijf je zo op.
Inderdaad, maar die welordeningsstelling is equivalent met het Keuzeaxioma en daarmee hoogst niet-constructief. Zoals de verzameling S2 geen definieerbare lineaire ordening heeft heeft S1 geen definieerbare welordening.
Je kunt met welordeningen werken maar dan laat je de willekeur van het Keuzeaxioma binnen en daarmee ben elke zweem van een grammatica kwijt.
Ik weet niet of je dan nog van een natuurlijke taal kunt spreken.
Korte samenvatting
We zijn hier nog niet aan het einde van het artikel Sets and Sentences gekomen. Er gebeurt wiskundig niet veel nieuws meer en het derde deel beargumenteerd dat zo ongeveer alle theoriën over natuurlijke getallen uit de tijd van schrijven niet deug(d)en. De argumenten steunen op The NL Vastness Theorem.
In het bewijs van die stelling zitten gaten. En die gaten bestaan vooral uit ontbrekende definities en aannamen.
Zo wordt nergens echt vastgelegd wat een verzameling eigenlijk is; het dichtst bij een definitie komt men in het bewijs van de Vastness Theorem: het kenmerkende van een verzameling is dat deze een kardinaliteit, een `aantal elementen’, heeft. Dat is de omgekeerde wereld en ook niet echt nodig.
Cantor definieerde eerst `Menge’ en pas daarna `Machtigkeit’; naar moderne maatstaven hebben die definities weinig inhoud maar ze stuurden de intuïtie wel de goede kant op.
De manier waarop ik het `bewijs’ van de stelling heb opgeschreven laat zien dat die aanname over kardinaliteit vermeden kan worden; we hebben alleen goede afspraken over het hebben van meer, minder en evenveel elementen nodig en dat kan zonder die aantallen te definiëren of benoemen. Net als we geen eenheid van lengte nodig hebben om uit te maken of ik langer, korter, of even lang ben als Marc van Oostendorp: zet ons naast elkaar en je weet het.
Zoals al opgemerkt zijn de centrale noties van het artikel niet goed afgesproken; de definities lijken, gezien de gegeven voorbeelden, vooral ingegeven door de eindige situatie. Bij het suggestief opschrijven van de verzameling S1 zien we ook alleen maar eindige zinnen.
Ik vermoed dat niemand de schrijvers heeft gevraagd hoe men het zich moet voorstellen: een collectie zinnen die geordend is als de rationale getallen: zonder begin, zonder eind en met tussen elk tweetal zinnen ondindig veel andere. Hoe maak je daar een goedlopende zin van?
Lariekoek? I
Dit is de vierde in een korte serie blogposts naar aanleiding van een discussie op twitter over dit stuk op Neerlandistiek.nl van Marc van Oostendorp dat zelf weer een reactie op dit artikel van Paul Postal was. In de eerste post kwalificeerde ik een opmerking uit het stuk van Postal als lariekoek. Daar gaat deze post over.
De opmerking van Postal betreft de grootte van de `collectie’ van alle boeken in een taal. Die collectie is niet alleen oneindig groot, niet alleen overaftelbaar, maar zelfs groter dan elke denkbare verzameling. Voor (een idee van) het bewijs van deze bewering verwijst Postal naar het artikel Sets and Sentences en een boek, The Vastness of Natural Languages, beide geschreven door hemzelf en D. Terrence Langendoen.
Ik heb wat met verzamelingen en wilde daarom wel eens zien waarom de collectie boeken in een Natuurlijke Taal zo groot moest zijn. Het boek heb ik niet te pakken kunnen krijgen maar deze recensie beweert dat de kern van de inhoud al in het artikel staat. laten we dat artikel dan maar eens bekijken.
Het artikel bestaat uit drie delen: een korte inleiding, een deel waarin “naar analogie met Cantors’s resultaten” wordt beargumenteerd dat de zinnen in een natuurlijke taal geen verzameling vormen, en een deel met conclusies.
Dat tweede deel begint met wat definities die het beschrijven van constructies van nieuwe `zinnen’ uit oude mogelijk moeten maken. Het hoofdingrediënt is dat van een conjunct, dat is een eenheid die bestaat uit een connectief en een deelconjuct. Die conjuncties kunnen in/tot `co-ordinate compound constituents’ samengevoegd worden. Zo’n co-ordinate compound moet wel echt `compound’ zijn en dus uit ten minste twee conjuncten gevormd worden.
Vervolgens spreken de schrijvers af hoe uit een verzameling U van constituents een co-ordinate compound constituent T gemaakt kan worden; of beter: hoe we kunnen zien dat T uit U gemaakt is. Elke conjuct in T heeft een element van U als deelconjunct, elk element van U is deelconjunct van precies één conjuct van T, en de conjuncten in T zijn geordend (daarover later meer).
In dit geval is T een `co-ordinate projection‘ van U, en U is de `projection set van T. Let op het gebruik van `een’ en `de’ in de vorige zin.
Ik kan begrijpen dat dit allemaal nogal abstract overkomt en ik moest het zelf een paar keer lezen voor ik dacht door te hebben wat er aan de hand is. Achter al die termen zitten plaatjes als het onderstaande verscholen:
De verzameling U bestaat uit de constituents `Marc’ en `KP’; uit elk element van U kunnen we een conjunct maken door er een connectief aan vast te plakken. Dat connectief kan leeg zijn, zoals bij `Marc’ omdat, bijvoorbeeld, je aan het begin van een zin geen voegwoord gebruikt en toch iets nodig hebt om je conjuct te markeren. Daar nemen we dan ∅ maar voor. In de woorden van Langendoen en Postal: C1 en C2 zijn de dochters van T, die zusters zijn elk een conjuct, bestaande uit een connectief en een deelconjuct.
De hoofdaanname, of het hoofdaxioma, is nu dat elke verzameling constituents tot een co-ordinate compound constituent gevormd kan worden. De (co-ordinate compound) constituents waar we het verder over zullen hebben zijn gewoon zinnen, en daarom zal ik ze verder ook maar zo noemen.
Om te beginnen maken we oneindig veel zinnen:
- De reële rechte is overaftelbaar
- Ik weet dat de reële rechte overaftelbaar is
- Ik weet dat ik weet dat de reële rechte overaftelbaar is
- Ik weet dat ik weet dat ik weet dat de reële rechte overaftelbaar is
- …
Niet erg opwindende zinnen maar daar gaat het niet om: er is een duidelijke procedure die voor elk natuurlijk getal n een zin Z(n) construeert. Dit is een voorbeeld van een recursieve definitie: als we een beginobject beschrijven en een recept aangeven om elk volgende object te maken dan beschouwen we de constructie als voltooid.
Voor elke deelverzameling U van deze verzameling {Z(n):n∈N} van zinnen bestaat er dus een zin waarvan de deelconjucten precies de zinnen uit U zijn. Dat geeft ons dan overaftelbaar veel zinnen.
Daarmee is het hek van de dam: we kunnen blijven doorgaan en elke deelverzameling van de nieuwe verzameling zinnen weer samensmeden tot een nieuwe zin. En weer, en weer, en weer, …
De conclusie van Langendoen en Postal is nu dat alle zinnen die we zo kunnen maken geen verzameling vormen. Hier komt de analogie met Cantor’s resultaten om de hoek kijken. Cantor bewees namelijk dat elke verzameling strikt meer deelverzamelingen heeft dan elementen. Als je dit toepast op `de verzameling van alle verzamelingen’ kom je in de knoop: de elementen van die `verzameling’ zijn precies zijn deelverzamelingen, maar dat kan niet omdat er meer deelverzamelingen dan elementen zijn. De entiteit `de verzameling van alle verzamelingen’ bestaat dus niet.
Dezelfde redenering is nu van toepassing op `de verzameling van alle zinnen in een natuurlijke taal’: elke deelverzameling bepaalt een zin en verschillende deelverzamelingen bepalen verschillende zinnen en dat druist in tegen de conclusie van Cantor: altijd strikt meer deelverzamelingen dan elementen.
Waarom Lariekoek?
Waarom denk ik dat dit lariekoek is? Dat heeft vooral te maken met de manier waarop Langendoen en Postal hun `bewijs’ presenteren. Daar is wiskundig veel op af te dingen. Maar deze post is al behoorlijk lang en ik bewaar mijn wiskundige opmerkingen, bijvoorbeeld over de bovengenoemde ordeningen daarom maar voor deel twee.
Getallen bestaan (eigenlijk) niet
Dit is de derde in een korte serie blogposts naar aanleiding van een discussie op twitter over dit stuk op Neerlandistiek.nl van Marc van Oostendorp dat zelf weer een rectaie op dit artikel van Paul Postal was. De eerdere delen staan hier en hier.
Tussen al die tweets maakte ik de volgende opmerkingen:
Daar komt nog bij dat `getal' als aantal’ strikt genomen gedefinieerd moet worden; verzamelingen hebben geen intrinsiek `aantal elementen'. Boeken zijn inderdaad eerder stellingen. https://t.co/Mjjth2qDKd
— (((K P Hart))) (@hartkp) October 15, 2019
Daar wil ik het vandaag even over hebben. Wat zijn getallen eigenlijk? Die vraag werd zelfs op de Nationale Wetenschapsagenda gesteld en ik heb daar al eens een antwoord op gegeven. Ik wil dat hier wat uitgebreider doen.
Getallen
Om te beginnen: in de discussie en de stukken ging het over natuurlijke getallen en die werden vereenzelvigd met hun decimale schrijfwijze. Dat is, in deze tijd, heel natuurlijk: afgezien van jaartallen in Romeinse notatie op gevels van gebouwen (en als paginanummers in boeken vóór de echte inhoud begint) zien we getallen eigenlijk alleen opgeschreven met behulp van de indo-arabische cijfers en de positionele schrijfwijze.
Gegeven deze vereenzelviging is er wel iets te zeggen voor het idee dat boeken en getallen iets gemeen hebben: rijen symbolen met een welgedefinieerde inhoud.
Aan de andere kant: getallen zijn in zekere zin absoluut: ze zijn bestand tegen vertalingen. Twaalf, twelve, douze, tolv, dvanást’, teyan-a-bub, … verwijzen allemaal naar exact dezelfde hoeveelheid streepjes: ||||||||||||.
Als ik een stuk tekst van mezelf in het Engels vertaal is die exactheid weg. Sommige nederlandse woorden en uitdrukkingen doen het niet zo goed in letterlijke vertaling (“laat maar” versus “let but”) en een equivalent-bij-benadering is slechts dat: een benadering. Vergelijk deze twee stukken over de Gulden Snede maar: nederlands versus engels.
Meer, minder, even veel
Maar goed, terug naar de vraag over de aard, of het bestaan, van getallen. Ik denk/vind dat getallen, in de zin van aantallen, niet bestaan.
“Maar we tellen toch dagelijks dingen”, hoor ik u zeggen. Inderdaad, maar de zaken die we daarbij gebruiken zijn bedacht, ze bestaan niet in het wild. Ooit `het getal dat wij in het Nederlands drie noemen’ gezien? En hierbij wel de gebruikelijke notaties loslaten, het symbool 3 telt niet, en III ook niet, en γ’ ook niet.
Maar er is meer: in de verzamelingenleer is het na invoering van de bekende soorten afbeeldingen, injectief, surjectie, en bijectie een koud kunstje te definiëren wanneer de ene verzameling minder, meer, of even veel elementen heeft als een andere. Kleine kinderen weten dat al heel snel, en zonder tellen: haal uit beider zakje snoepjes telkens tegelijkertijd één snoepje. Het zakje dat het eerst leeg is bevatte minder snoepjes dan het andere en gelijk leegraken betekent even veel. Probeer het zelf maar eens: neem twee lepels hagelslag en zoek zo uit welke lepel de meeste korrels heeft.
Maar als je in de verzamelingen een antwoord wilt geven op de vraag “Hoeveel elementen?” sta je in het begin met de mond vol tanden. Na vrij veel werk lukt het een klasse van standaardverzamelingen af te zonderen waarmee andere verzamelingen gemeten kunnen worden en zo een `aantal elementen’ opgeplakt kunnen krijgen. Dat wil zeggen: dit werkt voor eindige verzamelingen, waarbij `eindig’ zo wordt gedefinieerd dat `het’ ook inderdaad werkt.
Hoeveel?
Hoe zit het met willekeurige verzamelingen? Georg Cantor dacht dat er zoiets als `het aantal elementen’ moest zijn; hij had zelfs een definitie:
,Mächtigkeit` oder ,Cardinalzahl` von M nennen wir den Allgemeinbegriff, welcher mit Hülfe unseres activen Denkvermögens dadurch aus der Menge M hervorgeht, dass von der Beschaffenheit ihrer verschiedenen Elemente m und von der Ordnung ihres Gegebenseins abstrahirt wird.
Uit die definitie halen we de volgende eisen waar dat Kardinaalgetal C(M) aan zou moeten voldoen:
- M en C(M) hebben even veel elementen (als bij de zakjes snoep), in vaktaal: er is een bijectie tussen M en C(M) — C(M) is dus ook een verzameling
- als er tussen M en N een bijectie bestaan dan C(M)=C(N)
Als er dus zo’n functie is dan kunnen we C(M) `het aantal elementen’ van M noemen.
En, helaas, zo’n functie kun je niet definiëren. Het bewijs van die ondefinieerbaarheid hoop ik maandag 16 december tijdens het laatste college van de Mastermath-cursus Set Theory af te ronden.
Wat betekent dit? Dat verzamelingen geen `intrinsiek’ aantal elementen hebben. Je kunt niet meer doen dan zelf een hoeveelheid standaardverzamelingen af te spreken waarmee je op zinvolle wijze betekenis aan `het aantal elementen’ kunt geven. Getallen zijn geen natuurverschijnselen maar mensenwerk.
Dit gebeurde vaker
De vraag wie van twee mensen langer of korter is is zo beantwoord: hou ze tegen elkaar aan en je ziet het. Om de vraag “Hoe lang zijn die twee mensen?” te beantwoorden zijn in de loop der tijd veel systemen bedacht, sommigen wat logischer dan de andere. Ons metrieke stelsel is overgebleven, ongetwijfeld door de voor de hand liggende definitie van de meter: neem de halve meridiaan van de noordpool door Parijs naar de evenaar en hak die in 10.000.000 even grote stukjes; elk stukje is, per definitie, één meter lang.
Oh, en `teyan-a-bub’? Dat gebruik je bij het tellen van schapen in Weardale.
Strictly between
This is the third in a short series of blog posts intended to explain the terms in red in the following sentence, that succinctly describes the Continuum Hypothesis.
There is no set whose cardinality is strictly between that of the integers and the real numbers.
These are, in the words of John Lloyd, the bits that he does not understand.
Thus far we have dealt with set in this post and this one, and with the notion of cardinality in this one.
To recap our findings: we first came to the disappointing realisation that the definitions proposed by Georg Cantor, very strictly speaking, did not deliver on their promises. There is a way out of this via the development of Axiomatic Set Theory but that would take us too far afield.
In the spirit of Cantor we can define a set to be a well-defined collection of objects as long as we furnish a good description/definition of that collection.
As to cardinality: we consider it a property that every set has and that leads to two derived properties of pairs of sets that are defined unambiguously.
Two sets, X and Y, are said to have the same cardinality if “it is possible to put them, by some law, in such a relation to one another that to every element of each one of them corresponds one and only one element of the other” (Cantor, translation by Jourdain). We simply abbreviate this as |X|=|Y|. Additionally we can define what |X|≤|Y| (“the cardinality of X is less than or equal to that of Y”) means that there is a subset Z of Y such that |X|=|Z| (“X has the same cardinality as some subset of Y”).
In this post there are some examples of sets with the same cardinality (provinces of the Netherlands, and months of the year) and with different cardinalities (two teaspoons of chocolate sprinkles).
It is now actually quite straightforward to come to the definition of strictly between. First we define `strictly less’; then `strictly between’ is a combination of twice `strictly less’.
In the example of the chocolate sprinkles the cardinality of the sprinkles in the left hand spoon was strictly less that the cardinality on the right hand side. I paired off the sprinkles on the left with a subset of the sprinkles on the right and it was at once clear that there was no way to pair off both sets with each other. In short, we saw that |L|≤|R| and that |L|≠|R|. And this will be our definition of “the cardinality of X is strictly less than that of Y”, in symbols |X|<|Y|: it is the conjuction of |X|≤|Y| and |X|≠|Y|.
Cantor’s seminal theorem from 1873 can be summarized as |N|<|R|, where N and R denote the sets of natural and real numbers respectively (more on the definition of these in later posts).
Since N is a subset of R it is clear that |N|≤|R|; the hard part of Cantor’s proof was to show that |N|≠|R|, i.e., that there is no way to pair off the natural numbers and the real numbers with each other.
So “the cardinality of Y is strictly between the cardinalities of X and Z” is the conjuction of |X|<|Y| and |Y|<|Z| and ultimately comes down to the following four statements:
- X can be put into one-to-one correspondentce with a subset of Y,
- Y can be put into one-to-one correspondentce with a subset of Z,
- X cannot be put into one-to-one correspondentce with Y, and
- Y cannot be put into one-to-one correspondentce with Z
For explicitly given sets it is often not too difficult to establish whether this state of affairs holds or not; certainly not with all the tools that Cantor and his followers have developed.
In the case of the Continuum Hypothesis matters lie differently: two of the three sets are there; one should produce the third in the middle, or show that no third exists. At the beginning of the 20th century either possibility probably seemed like an insurmountable task, although Cantor strongly believed in the second alternative.
What is cardinality?
This is the second in a short series of blog posts intended to explain the terms in red in the following sentence, that succinctly describes the Continuum Hypothesis.
There is no set whose cardinality is strictly between that of the integers and the real numbers.
These are, in the words of John Lloyd, the bits that he does not understand.
In the first post and its addendum we dealt with the difficulty that any definition of the notion `set’ must, to some extent, be circuitous: one cannot avoid the use of a synonym, such as `collection’, `aggregate’, …
The next term in red in the sentence above is `cardinality’. Here the difficulty is worse.
To see why this is we turn to Georg Cantor again in his Beiträge zur Begründung der transfiniten Mengenlehre he gave the following definition.
,Mächtigkeit` oder ,Cardinalzahl` von M nennen wir den Allgemeinbegriff, welcher mit Hülfe unseres activen Denkvermögens dadurch aus der Menge M hervorgeht, dass von der Beschaffenheit ihrer verschiedenen Elemente m und von der Ordnung ihres Gegebenseins abstrahirt wird.
Das Resultat dieses zweifachen Abstractionsacts, die Kardinalzahl oder Mächtigkeit von M, bezeichnen wir mit |M|.
In the translation by Philip E. B. Jourdain this becomes
We will call by the name “power” or “cardinal number” of M the general concept which, by means of our active faculty of thought, arises from the aggregate M when we make abstraction of the nature of its various elements m and of the order in which they are given.
We denote the result of this double act of abstraction, the cardinal number or power of M by |M|.
As beautiful as this may sound it is actually meaningless. The phrases “active faculty of thought” and “abstraction of the nature” have no mathematical meaning. When one reads the next few pages of Cantor’s paper it becomes quite clear that this is an attempt to define `the number of elements’ of the set. Those next pages establish that two sets have the same power if and only if “it is possible to put them, by some law, in such a relation to one another that to every element of each one of them corresponds one and only one elemen of the other” (translation by Jourdain).
By way of example the sets of provinces of the Netherlands and of months of the year have the same power; the following relation between provinces and months establishes this:
(January,Groningen),
(February,Drente),
(March,Friesland),
(April,Overijssel),
(May,Flevoland),
(June,Gelderland),
(July,Utrecht),
(August,Noord-Holland),
(September,Zuid-Holland),
(October,Zeeland),
(November,Noord-Brabant),
(December,Limburg).
Every month corresponds to one and only one province and every province corresponds to one and only one month.
Before we continue: `cardinality’ is just another term for `power’.
The definition of power, or cardinality, or cardinal number is more incomplete than that of `set’. At least in the latter definition we had a synonym to fall back on; the definition of cardinality does not even have that contingency. However, and this is very important for what follows, even though `cardinality’ does not have a good definition the notion that two sets have the same cardinality does have a mathematically sound and workable definition: nowadays Cantor’s characterization of when two sets have the same power is taken as its definition.
As an aside: a similar thing can be said of the notion of length. If we ever come face to face it will be clear immediately whether the length of John Lloyd is larger or smaller than mine (or equal even) but unless we happen to have a tape measure handy we will not know our lengths, expressed in the local units.
Small children know how to compare the cardinalities of sets: a practical instance is given by chocolate sprinkles, a favourite Dutch breakfast item. If one takes two spoonfuls of these items it is quite easy to check whether these contain the same number of sprinkles. Here are two heaps of them:
I personally did the following: take one from each heap and eat them, and again, and again, and again, … after a while the … was empty and the other one was not. This means that the heaps did not contain the same number of sprinkles and I we can even say that the cardinality of the other heap of sprinkles was larger than that of the … one. This process was quite easy I could walk away and resume again later; I did not worry about losing my count because I did not count.
Thus we find ourselves in the strange situation that we have an undefined notion `cardinality of a set’, yet when we are given two sets we have a way of potentially deciding whether they have the same cardinality. We can even say when the cardinalities of two sets are comparable: if M has the same cardinality as some subset of N we can express this by saying that the cardinality of M is less than or equal to that of N, we can even write |M|≤|N| in that case. In the next installment we shall see that the next bit, strictly between, actually does have an unambiguous definition.
What is a set? (revisited)
This is an addendum to the first in a short series of blog posts intended to explain the terms in red in the following sentence, that succinctly describes the Continuum Hypothesis.
There is no set whose cardinality is strictly between that of the integers and the real numbers.
These are, in the words of John Lloyd, the bits that he does not understand.
The gist of the post referred to above was that, very strictly speaking, sets have no proper mathematical definition. The definitions that were quoted from the works of Bolzano and Cantor were, to a large extent, by synonym: “a set is a collection …”. The ellipsis would contain some conditions what the collection should satisfy to be deemed a set. But the definition would be incomplete because `collection’ remained undefined. Many definitions in mathematics suffer from a similar `defect’: at some point there is a primitive notion that is not further defined. In most every branch of mathematics that primitive notion turns out to be `set’ in some form or another.
That looks bad: Mathematics seems to be based on a badly defined notion. However not all is lost. Most of the time we know exactly what we are talking about. It is true that `collection’ is undefined but, as mentioned in the original post, we recognize one when we see one and in Mathematics we are very particular about how we work with them.
By way of example consider the books currently in our house. They form a well-defined collection: it is very clear which books are in that collection and which books are not. That collection forms what Bolzano and Cantor consider to be a set. It has an unambiguous definition. Just like the set of books in our house that have exactly 250 pages: everyone that we to gather `the books with exactly 250 pages’ will come back with the same collection. And the unambiguity separates the sets from the arbitrary collections. If I were to ask John Lloyd to gather the interesting books in our house he would most likely come out with a different collection than I would. The phrase `the interesting books in our house’ does not define a set.
What determines a set in mathematics is the unambigiuty of its definition: no matter who we set the task of determining what is in it, the answer should always be the same. That does not mean that that task is easy or doable in a (very) short time. The prime numbers form a set, a subset of the set of natural numbers, and for every individual natural number it is straightforward to determine whether it is prime or not, but separating them from the other natural numbers by hand is not an option.
Because of this and other examplese have developed the curly-braces notation for sets.
P = {n : n is a prime number}
is a properly defined set and for every natural number n we can decide whether n∈P (`n is in P’) or not.
And that is how mathematicians consider sets: as collections where membership can be checked unambiguously. Thus the advisoy committee of Episode 2, series 10 of the Museum of Curiosity forms a set, the funny members of that committee most likely do not. There is, alas, no unambiguous definition of `funny’.
What is a set?
This is the first in a short series of blog posts intended to explain the terms in red in the following sentence, that succinctly describes the Continuum Hypothesis.
There is no set whose cardinality is strictly between that of the integers and the real numbers.
These are, in the words of John Lloyd, the bits that he does not understand.
Sets pervade mathematics. Basically every definition of a mathematical structure contains the phrase “… a set such that …”. The language and tools of Set Theory generally make it possible to formulate results efficiently.
It may therefore come as a bit of a surprise that the question “What is a set?” does not have a straightforward answer. That sounds strange because we generally recognise a set when we see one: thimbles, forks, railway-shares …,(but not care, hope and soap) you name it, someone will have a set (collection) of it.
However, in Mathematics we like precise definitions, so that at every moment it is clear what we are talking about. A word of warning is needed here, nicely illustrated by this quote from Goethe.
1005. Die Mathematiker sind eine Art Franzosen; redet man mit ihnen, so übersetzen sie es in ihre Sprache, und dann ist es alsobald ganz etwas anderes.
Johann Wolfgang von Goethe, Maximen und Reflexionen, Nachlass, Über Natur und Naturwissenschaft
I do not have the illusion to know what Goethe actually meant to say with this and further study of his work may reveal that, but for me this quote is very apt all by itself. Many definitions of mathematical notions do not conform to the expectations of non-mathematicians. Things that are nigh on synonymous in the dictionary may have rather different meanings in mathematics.
To define what a set is we turn to two pioneers of the study of the infinite, Bernard Bolzano and Georg Cantor.
In his Paradoxieen des Unendlichen Bolzano wrote this on page 4, after a short introduction wherein he exlained the need for a definition of Menge.
Einen Inbegriff, den wir einem solchen Begriffe unterstellen, bei dem die Anordnung seiner Teile gleichgültig ist (an dem sich also nichts für uns Wesentliches ändert, wenn sich bloß diese ändert), nenne ich eine Menge;
In the translation of this work by Donald A. Steele and the above definition is rendered as follows.
An aggregate whose basic conception renders the arrangement of its members a matter of indifference, and whose permutation therefore produces no essential change from the current point of view, I shall call a set (Menge),
The very first words written by Georg Cantor in his Beiträge zur Begründung der transfiniten Mengenlehre are
Unter einer ,Menge` verstehen wir jede Zusammenfassung M von bestimmten wohlunterschiedenen Objecten m unserer Anschauung oder unseres Denkens (welche die ,Elemente` von M genannt werden) zu einem Ganzen.
In Zeichen drücken wir dies so aus:
M={m}
In the translation by Philip E. B. Jourdain we find:
By an “aggregate” (Menge) we are to understand any collection into a whole (Zusammenfassung zu einem Ganzen) M of definite and separate objects m of our intuition or our thought. These objects are called the “elements” of M.
In signs we express this thus:
M={m}
I think it is no coincidence that the notion `Menge’ was defined during investigations of the notion of `infinite’. At that moment the relations between the individuals that make up the whole are of secondary importance. And at some point one chooses one out of many synonyms &mdsah; collection, multitude, Mannigfaltigkeit, aggregate, set, verzameling, &hellip — and that becomes that name of the basic object of investigation.
If you read the definitions closely then you will see that they, strictly speaking, define nothing: both use a synonym, Inbegriff or Zusammenfassung, as a definition. However, Bolzano explicitly adds a condition (and Cantor does so implicitly, as witnessed by the rest of his paper) that was also mentioned above: the relations, if any, between the elements of the sets are not important. A few paragraphs before the definition Bolzano used the example of a broken tumbler; we tend to view that as different from that same tumbler before it was broken because the relations between the constituents have changed, as a set — of atoms, molecules — it has not changed.
It is this condition that tell us what the goal of Bolzano and Cantor undoubtedly was: delineate as sharply as possible about which objects they make their pronouncements. Bolzano’s definition was the summary of a long run-up where he discussed what properties a Menge should have. Cantor jumped right in because he had been considering sets for two decades already.
On a naïve level these definitions are quite workable because all that happens is that certain entities now have the label `set’ applied to them. Something like {1,2,3,4,5} is recognised by everyone as a “the set of natural numbers from 1 through 5”. And also sets with a description like {n ∈ N : n ≤ 10100} is fine, provided we have learned some of the language of mathematics. Here ∈ means `is element of’, ≤ means `less than or equal’ and N represents the set of natural numbers.
Mathematics differs from `daily life’ in one seemingly innocuous point: mathematicians give set status to a few things that some people do not recognise as sets. The empty set and sets with (exactly) one element are perfectly acceptable mathematically. But, if I were to tell you that I have a set of stamps and show you an album without any in it you would not consider me a stamp collector, nor if a were to show you just one stamp (right before I stick it on an envelope).
Mathematically speaking these are legitimate sets and they are also quite necessary because it would become quite cumbersome to exclude them as results of operations on sets. Think of equations. Very often we speak of solution sets and that would suddenly be illegal is the equation had no or just one solution? Really?
But still, this all assumes that we recognize a set when we see one: a collection of things thrown together between curly braces for a certain purpose. It’s the thirteen cards in your hand at bridge before you inspect and order them; it’s the points on a line where it is immaterial which point lies to the left or right of another point. All this does not tell us what a set is. For that we should define first what a collection is …
So, where does that leave us? The tools and language of Set Theory pervade mathematics and are quite powerful, yet we do not have a fully satisfactory definition of what a set actually is. For day-to-day mathematics that is no big problem because, as I said above, we recognise many familiar entities as `sets’ and treat them as such.
But what about those of us who want to know what a set really is? Who do not want to `recognise a set when they see it’? Well, we can satisfy them by setting up Set Theory purely logically and thus define what our objects are. The resulting `sets’ are not quite like those we learned to recognise but every one of our familiar sets has a faithful logical copy. This means that we can, with a bit of care, keep on using sets in the naïve way we have always done.
We may come back to that logical approach in a later post.
Machine Learning and the Continuum Hypothesis
Not even Machine Learning is safe from Set Theory, or so it seems. On the website of the journal Nature there is an article about a paper in Nature Machine Intelligence that connects a certain kind of learnability to the Continuum Hypothesis. The conclusion of the paper is that certain abstract learnability questions are undecidable on the basis of the normal ZFC axioms of Set Theory.
The article tries to explain what is going on but seems to confuse two disparate things: Gödel’s (First) Incompleteness Theorem on the one hand and the undecidability of the Continuum Hypothesis on the other hand.
The first is a very general statement about first-order theories; it states that for every theory that satisfies a number of technical conditions there are statements that have no formal proof and neither do their negations. Elementary number theory is subject to this theorem, as is ZFC Set Theory.
The second is a Set-theoretical statement for which we can prove that there is no formal proof, nor for its negation. It is also more interesting than Gödel’s statements; the latter `simply’ assert their own unprovability, whereas the Continuum Hypothesis is a fundamental statement/question about the set of real numbers.
The confusion manifests itself when the Continuum Hypothesis is called a paradox. It is not. The statements from the Incompleteness Theorem on the other hand are usually likened to the Liar Paradox in that “This formula if unprovable” looks a lot like the paradox that is “This sentence is false”.
The paper itself also alludes to the Incompleteness Theorem; it even states that is used in the argument. It is not. No use is made of Gödel’s abstract unprovable sentences.
The Set Theory
So, what is the Set Theory in the paper? The learnability question is shown to be equivalent to the existence of a natural number m and a map η from the family of m-element subsets of [0,1] to the family F of finite subsets of [0,1] that satisfies the following condition: if A is a subset of [0,1] with m+1 elements then it has a subset B with m elements such that η(B) contains A.
The main theorem of the paper states that an arbitrary set X admits such a map with m=k+1 if and only if X has cardinality at most ℵk.
If the Continuum Hypothesis holds then [0,1] has cardinality ℵ1, hence there is a map as required with m=2. More generally there is a map as required if the cardinality of [0,1] is equal to ℵk for some natural number k. These possibilities do not lead to contradictions, hence neither does the learnability statement. On the other hand, the statement that the cardinality of [0,1] is larger than all these ℵk does not lead to contradictions either, hence neither does the negation of the learnability statement.
The derivation of the main statement parallells that of the main result of the paper Sur une caractérisation des alephs by Kuratowski from 1951: a set X has cardinality at most ℵk if and only if its power Xk+2 can be written as the union of k+2 sets A1, …, Ak+2 such that for every i and every point (x1,…,xk+2) in the power the set of points y in Ai that satisfy yj=xj for j≠i is finite; in Kuratowski’s words “Ai is finite in the direction of the ith axis”.
Indeed one can even construct of a map η for m=k+1 from this decomposition of the canonical set ωk of cardinality ℵk.
For notational simplicity we take k=2, so m=3, and ω24 has a decomposition into four sets A1, A2, A3, and A4. Given a subset F of ω2 of 3 elements enumerate it in increasing order: x1<x2<x3. The set η(F) will consist of F itself together with
- all x for which (x,x1,x2,x3) belongs to A1,
- all x for which (x1,x,x2,x3) belongs to A2,
- all x for which (x1,x2,x,x3) belongs to A3,
- all x for which (x1,x2,x3,x) belongs to A4
To see that this works let G be a four-element subset of ω2, enumerate it as y1<y2<y3<y4. Then (y1,y2,y3,y4) belongs to one of the four sets, say it belongs to A2; then G is a subset of η({y1,y3,y4}): the point y2 is included in the second line in the list above.
Note. The proof of the main theorem (Theorem 1) of the paper is not quite correct: it fails for k=1 for example as one encounters the cardinal number ℵ-1. Worse: in that case the ordering <1 seems to have order type ω1 and ω0 simultaneously. All this can be repaired with a better write-up.
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.
Wat is een verzameling? II
We zetten de zoektocht naar het begrip `verzameling’ voort.
In de vorige blogpost hebben we de definities die Bolzano en Cantor van `verzameling’ gaven geciteerd. Die kwamen eigenlijk neer op “een verzameling is een verzameling”. Nu is het nogal lastig om een definitie van verzameling in woorden op te schrijven zonder te vervallen in synomiemen maar het kan wel.
Rond de eeuwisseling (die van 1900) begon men ernstig over de aard van definities na te denken. De eerste stap was het vastleggen van de taal waarin die definities vastgelegd zouden worden. En met `taal’ bedoelde men niet zoiets als Grieks, Latijn, of Swahili maar een meer formele constructie. Deze gaat uit van een beperkt aantal symbolen. Sommige zijn algemeen, zoals ∧ (en), ∨ (of), ¬ (niet), ∀ (voor alle) ∃ (er is) enzovoort; en sommige zijn specifiek voor het onderhavige onderdeel van de wiskunde, in de verzamelingenleer kunnen we toe met ∈ (is element van) en = (is gelijk aan).
In deze taal kunnen we vrijwel alles beschrijven wat we willen. De taal is sterk genoeg om dingen als
- “x is een priemgetal”
- “x is een reëel getal”
- “x is een rechte lijn in het vlak”
en nog veel meer uit te drukken. Op deze manier kunnen we afspreken dat we iets alleen een verzameling noemen als het bestaat uit x-en met een eigenschap die in onze taal is uit te drukken. Dus
{x : x is een priemgetal}
is een verzameling (waarbij “x is een priemgetal” in de taal is geformuleerd). Dit komt vrij dicht in de buurt van Cantor’s definitie van verzameling: de accolades {} representeren de `Zusammenfassung zu einen Ganzen’, en we hebben `Annschauung’ en `Denken’ vervangen door `beschrijfbaar in de taal’.
De lege verzameling ∅ is uit te drukken door {x : x≠x} en telt dus mee als verzameling. Andere dingen leken iets dubieuzer, zoals {x : x=x}, de verzameling, V, van alle verzamelingen(?). Die gaf aanleiding tot een paradoxale toetand: Cantor had bewezen dat elke verzameling strikt minder elementen dan deelverzamelingen heeft (zie deze en de daarop volgende post voor de betekenis van meer en minder), maar voor deze V geldt dat niet, want elke deelverzameling is automatisch ook een element.
De oplossing, van Cantor, was onderscheid te maken tussen gewone en `oneigenlijke’ verzamelingen. En V was dus oneigenlijk; te groot om als gewone verzameling mee te tellen. Dat dit niet de schoonheidsprijs verdient lijkt me duidelijk want wie bepaald wat gewoon en oneigenlijk is?
Het kon nog erger: Bertrand Russell schreef de volgende verzameling, R, op: {x : x∉x}. Deze R leidt tot een wel heel eenvoudige paradox/tegenspraak, namelijk “$R∈R dan en slechts dan als R∉R”. Hier zijn geen diepe stellingen voor nodig; de afspraak hierboven was vanaf het begin al dubieus.
De uiteindelijke oplossing kwam van Ernst Zermelo. Deze formuleerde een een lijst axioma’s (spelregels) die we in acht moeten nemen als we met verzamelingen omgaan. Deze geven vooral aan hoe nieuwe verzamelingen uit oude gevormd kunnen/mogen worden. Die regels zijn redelijk natuurlijk; zo mogen we, gegeven twee verzamelingen x en y de verzameling {x,y} vormen.
Een van de belangrijkste regels is het Afscheidingsaxioma; dit zwakt onze eerste beschrijving wat af. Als x een gegeven verzameling is en φ is een formule in onze taal dat is {y:y∈x ∧ φ} weer een verzameling. Het verschil is dus dat we al een verzameling moeten hebben en daarbinnen elementen met een bepaalde eigenschap bijeen nemen.
Wat voor veel mensen in begin nog even wennen is is dat elk individu waar uitspraken over worden gedaan een verzameling is. Dus de elementen van verzamelingen zijn zelf ook weer verzamelingen enzovoort. Dat impliceert ook dat dingen als natuurlijke en reële getallen beschrijvingen krijgen die niet lijken op wat we gewend zijn maar dat went uiteindelijk wel.
Maar goed, dit leidt dan tot de volgnde definitie van verzameling: iets waarvan het bestaan uitgaande van de axioma’s te bewijzen is.
En wat dan allemaal uitgaande van die axioma’s mogelijk is kunt u in elk boek over Verzamelingenleer lezen en ook in het dictaat van de cursus Verzamelingenleer die ik zelf gegeven heb.
Recent Comments