Posts in category verzamelingen
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.
More on machine learning and CH
A few days ago I wrote about a paper establishing an independence result in the field of machine learning. Here I offer a few more comments.
In the paper the authors comment on the relation between their result and actual machine learning. That relation may seem tenuous because none of the functions involved in the arguments is related to any kind of algorithm.
Indeed the constructions of the compression schemes are very non-constructive in that they use repeated applications of the Axiom of Choice.
Now the inequality 2ℵ0>ℵω implies there are no compression schemes whatsoever. But it may be of interest to know that consistent examples of compression schemes must be nonconstructive. It turns out that, with the aid of a few standard results from Descriptive Set Theory it is relatively easy to show outright that there are no Borel measurable monotone compression schemes and hence no Borel measurable learning functions for the class of problems studied in the paper mentioned above either.
The details can be found in this note.
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.
Het Compactheidsbeginsel
Twee recente artikelen op Kennislink hebben iets gemeen. Dat gemeenschappelijke is een belangrijk stuk gereedschap uit de Wiskunde dat bekend staat als het Compactheidsbeginsel.
In 2016 werd een kleuringsprobleem voor de natuurlijke getallen opgelost: is het mogelijk de natuurlijke getallen in tweeën te delen op zo’n manier dat beide delen geen enkel Pythagoreïsch drietal bevatten? Het antwoord is: “nee”. Zoals op Kennislink te lezen is is er iets meer ontdekt: bij elke verdeling van {1,2,3,…7825} in twee delen moet een van de delen een Pythagoreïsch drietal bevatten en er is een verdeling van {1,2,3,…,7824} waarbij geen van de beide delen een bevat.
Voor de goede orde: een Pythagoreïsch drietal is een drietal natuurlijke getallen (a,b,c) dat voldoet aan a2+b2=c2. Ook wordt het probleem vaak in termen van kleuringen geformuleerd: de verdeling wordt weergegeven door elk natuurlijk getal rood of blauw te kleuren.
Begin van deze maand werd vooruitgang geboekt bij een kleuringsprobleem in het platte vlak: in hoeveel verzamelingen moet je de punten in het vlak minimaal verdelen opdat geen enkel deel twee punten bevat die afstand 1 hebben. Er was lang bekend dat dat minimale aantal ten minste 4 en ten hoogste 7 is; nu is bekend dat het ten minste 5 moet zijn. Okk hier is al aan een eindige verzameling punten te zien dat bij elke verdeling in vier stukken er altijd een stuk is dat twee punten met afstand 1 bevat.
Waarom is dat? Het zou toch bij het eerste probleem zo kunnen zijn dat bij verschillende kleuringen de drietallen één kleur krijgen steeds hoger in de natuurlijke getallen moeten zitten. Maar kennelijk is het zo dat, ongeacht de kleuring er al een éénkleurig drietal is in {1,2,3,…,7825}.
Het geheim is een stelling van De Bruijn en Erdös; deze zegt dat bij elk kleurings probleem het volgende geldt: als elke eindige verzameling een `goede’ kleuring heeft dan is er een `goede’ kleuring voor de hele verzameling. Dat kun je ook als volgt contrapositief formuleren: als elke kleuring van de hele verzameling `slecht’ is dan is er een vaste eindige verzameling waarvoor elke kleuring `slecht’ is. In April 2014 is over deze stelling een artikel in Pythagoras verschenen.
Het voordeel van dit Compactheidsbeginsel is dat men voor positieve resultaten alleen naar eindige verzamelingen hoeft te kijken; dat kan de bewijzen aanzienlijk vereenvoudigen. Het nadeel is dat het niet constructief is: het geeft geen enkele informatie over de grootte van de vaste eindige verzameling waarvoor elke kleuring `slecht’ is. Dat laatste is te zien aan de resultaten waarover op Kennislink bericht werd; de zoektochten naar de eindige verzamelingen en de verificaties dat ze werkten kostten veel tijd en moeite.
Het vlak kleuren
Vorige maand (april 2018) is er een stap gezet op weg naar de oplossing van het volgende probleem: “hoeveel kleuren heb je nodig om de punten van het vlak te kleuren en wel zo dat punten op afstand 1 verschillende kleuren krijgen. De titel van het artikel in de Volkskrant is misleidend want het probleem is nog niet opgelost; de titel van het stuk in NRC is correct.
Beide stukken waren niet zo duidelijk als men wellicht hoopte, getuige bijvoorbeeld de commentaren in de facebookgroep ‘Leraar Wiskunde’. De opmerkingen over de voorbeelden in de Volkskrant werden niet altijd begrepen en de pixelmetafoor in NRC leidde tot misverstanden over de aard van het probleem.
Wat bekend was over het probleem tot vorige maand was het volgende. Door middel van een betegeling van het vlak met behulp van regelmatige zeshoeken met diameter 1 kun je een kleuring met zeven kleuren maken. Hierbij moet je wel precies zijn: bij elke zeshoek neem je de randpunten van zes uur tot twaalf uur mee (inclusief zes uur exclusief twaalf uur) en laat je de andere randpunten weg. Elke tegel krijg namelijk een kleur en op deze manier vermijdt je dat randpunten op afstand 1 dezelfde kleur krijgen.
De voorbeelden in het NRC-artikel zijn duidelijk: als je de punten van het vlak met twee kleuren kleurt dan zijn er in een gelijkzijdige driehoek met zijden 1 al twee punten met dezelfde kleur. Daarnaast is er een configuratie van zeven punten te zien waarvoor bij elke kleuring met drie kleuren twee punten met afstand 1 zijn die dezelfde kleur krijgen.
Het nieuwe is een configuratie van 1581 punten, gevonden door Aubrey de Grey waarin hetzelfde geldt, maar nu voor vier kleuren; dus, hoe je die punten ook kleurt met vier kleuren er zullen er altijd twee zijn met afstand 1 en dezelfde kleur. Inmiddels is 1581 teruggebracht tot 633.
De pixelmetafoor uit NRC leidde tot een onderschatting van het probleem; dat kwam door een subtiel verschil tussen pixels en de punten van het vlak: in tegenstelling tot pixels hebben punten in het vlak geen directe buren en geen oppervlakte, ook zijn ze niet vierkant. De echte formulering van het probleem vraagt naar het kleinste natuurlijke getal n met de eigenschap dat er een functie van het vlak naar {1,2,…,n} is met de eigenschap dat als d(x,y)=1 dan f(x)≠f(y). Daar komt geen verf of kwast aan te pas en de vorm of oppervlakte van een punt is ook niet van belang.
Achter de voorbeelden die laten zien dat een bepaald aantal kleuren niet volstaat zit een stelling van De Bruijn en Erdös: als elke eindige deelverzameling van het vlak een goede kleuring met k kleuren toelaat dan laat het vlak ook een goede kleuring toe. Met andere woorden: om te laten zien dat er geen goede kleuring is moet je een eindige verzameling zonder goede kleuring vinden.
Overigens zou dit nog tot twee verschillende oplossingen van het probleem kunnen leiden: de stelling van De Bruijn en Erdös geldt onder aanname van het keuzeaxioma. In dit artikel van Shelah en Soifer is te lezen dat de aard van de gevraagde functie het antwoord kan beïnvloeden. Lang voor het werk van De Grey was bekend dat een Lebesgue-meetbare kleuring ten minste vijf kleuren zou vergen. NB de laatste stelling in het artikel van Shelah en Soifer is nu achterhaald.
Ten slotte: houd de Wikipediapagina over dit probleem in de gaten.
Toevoeging (2018-05-14): het hieronder in een reactie genoemde artikel op Kennislink is ook zeer informatief.
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.
Wat is een verzameling? I
De Wiskunde is doordrenkt van verzamelingen. Nagenoeg elke definitie van een te bestuderen structuur — groep, graaf, interval, … — begint met “een verzameling die …”. De taal en de methoden van de Verzamelingenleer helpen dan ook vaak bij het efficiënt formuleren en noteren van resultaten.
Hierbij gaat men voor het gemak voorbij aan het feit dat de vraag “Wat is een verzameling?” nog niet beantwoord is. Dat klinkt merkwaardig want we herkennen een verzameling wel als we er een zien: postzegels, boeken, vingerhoedjes, …, je kunt het zo gek niet bedenken of iemand heeft er wel een verzameling van.
Echter, in de Wiskunde houden we van precieze definities, zodat op elk moment duidelijk is waar we het over hebben. Hier is een waarschuwing op zijn plaats, mooi geïllustreerd door het volgende citaat
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
Ik heb niet de illusie te weten wat Goethe hier zelf mee bedoelde en door nadere bestudering van zijn is dat wellicht te achterhalen maar ik vind de uitspraak op zichzelf al treffend genoeg. Veel definities van wiskundige begrippen beantwoorden niet aan het idee dat de niet-wiskundige er van heeft.
Hoe zit dat met het begrip `verzameling’? Hoe kijken we daar wiskundig tegenaan. Een van de eersten die een definitie van `verzameling’ formuleerde was Bernard Bolzano.
Einen Inbegriff, den wir einem solchen Begriff unterstellen, bei dem die Anordnung seiner Theile gleichgültig ist (an dem sich also nichts für uns Wesentliches ändert, wenn sich bloss diese ändert) nenne ich eine Menge.
Bernard Bolzano,
Paradoxien des Unendlichen (1851)
Een andere definitie vinden we bij Georg Cantor.
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}
Georg Cantor,
Beiträge zur Begründung der transfiniten Mengenlehre (Erster Artikel) (1895)
Het is, denk ik, geen toeval dat het begrip `Menge’ gedefinieerd werd bij onderzoek naar het begrip `oneindig’. Op dat moment zijn eventueel gegeven relaties tussen de individuen in het geheel van ondergeschikt belang. Op een gegeven moment kies je uit een hele rij synoniemen — collectie, veelheid, Mannigfaltigkeit, aggregate, set, verzameling, … — er eentje en dat wordt dan de naam van het basisbegrip.
Wie de definities nauwkeurig leest ziet dat ze, eigenlijk, niets zeggen: beide gebruiken een synoniem, Inbegriff en Zusammenfassung, als definitie. Daarbij zegt de definitie van Bolzano expliciet en die van Cantor impliciet wat hierboven al is gezegd: bij een verzameling is de onderlinge relatie van de elementen niet van belang. Vlak voor de definitie gaf Bolzano het voorbeeld van een gebroken glas; dat vinden wij iets heel anders dan hetzelfde glas voor het gebroken was omdat de onderlinge relatie tussen de delen verstoord is, als verzameling — atomen, moleculen — is het niet veranderd.
De definities van Bolzano en Cantor hadden ongetwijfeld het doel zo scherp mogelijk af te bakenen over welke zaken er uitspraken gedaan werden. Bolzano nam daarbij een lange aanloop waarvan de definitie een samenvatting was.
Op een naïef niveau kun je met deze afspraken redelijk uit de voeten omdat er niet meer gebeurd is dan dat bekende gehelen nu het predicaat `verzameling’ opgeplakt hebben gekregen. Iets als {1,2,3,4,5} wordt door iedereen herkend als “de verzameling natuurlijke getallen van 1 tot en met 5”. En ook verzamelingen met een beschrijving als {n ∈ N : n ≤ 10100} herkennen we wel, mits we eerst hebben afgesproken dat N de verzameling der natuurlijke getallen voorstelt.
Waar de wiskunde en de dagelijkse praktijk uit elkaar lopen is bij de kleinste verzamelingen: de lege verzameling en de verzamelingen met één element. Als ik zeg dat ik een postzegelverzameling heb en ik laat een album zonder zegels zien dan gelooft niemand mij, ook niet als ik er één laat zien (vlak voor ik hem op een brief plak).
Wiskundig gesproken zouden dat volstrekt legitieme verzamelingen zijn ook al piept de buitenwacht nog zo hard. Bij het werken met en gebruik van verzamelingen komen die kleine verzamelingen zo vaak voor dat het heel vervelend wordt ze iedere keer uit te sluiten van het verzamelingschap. Denk aan vergelijkingen. Heel vaak wordt daar over de oplossingsverzameling gesproken en dat zou ineens niet mogen als er geen of maar één oplossing is? Kom nou!
Maar goed, dit alles gaat nog uit van de opvatting dat we verzamelingen herkennen als we ze zien. Het vertelt ons nog niet wat een verzameling is. Wat de moderne opvatting van verzameling is zien we volgende keer.
Misplacing ones excrement
In the somewhat more colourful language of this site: The Internet is losing its shit over this second grade math problem.
What is the problem?
“There are 49 dogs signed up to compete in the dog show. There are 36 more small dogs than large dogs signed up to compete. How many small dogs are signed up to compete?”
The answers that are discussed on the site are
- 36, with an argument not worthy of the name: 49-36=13, so 13 large dogs, so the answer is 36
- 42.5, because 49-36=13, 13/2=6.5 and 36+6.5=42.5
- 36 once more, but with the added information that 36-13=23, that’s 23 more small dogs
Answers 1 and 3 suffer from something that I observe with many first-year students: I ask something, in a Calculus class it is quite often a primitive function, and many suggestions come flying in, with the expectation that I will deem one of them correct. My reaction then is: you could have checked your answer yourself, in the case of the primitive by differentiation. That is why I asked that question in the first place: to show that they can verify many of their solutions by just substituting back into whatever it was they were solving.
You can verify whether 36 is correct: 36 small dogs is 23 more than 13 large dogs and 23 is definitely not equal to 36. So, no, 36 is not the correct answer.
The second answer — “That’s how I did it in my head.” — is correct, albeit unfortunate for one dog. It is also how I would (try to) explain it to a second-grader.
There are 36 more small dogs than large dogs, so we can set 36 small dogs aside and then look at the remaining dogs. If we want to keep the difference equal to 36 then we must be able to take away two dogs at a time (small and large) from those remaining until we have a group of small and a group of large dogs left. Most likely the second-grader will tell you that that is not going to happen with an odd number of dogs. The conclusion of course is that this is an ill-posed problem.
You can solve this problem — or rather, show it’s unsolvability — in other ways.
The sum of the two numbers in question is odd, that means that they have different parity, i.e., one is odd the and other is even, but then their difference is odd as well and it can’t be 36.
Or you can introduce letters, S and L, and express the demands as equations: S+L=49 and S-L=36. Solving these will lead to the solution done in the head: 2S=85, hence S=42.5 and L=6.5.
I hope that the teacher will admit that there was an error in the problem and that they will turn this into a valuable lesson: you can often check whether your answer is correct or makes sense.
On this day in 1873, II
A little over a week ago I wrote about a letter from Cantor to Dedekind that contained an auspicious question, namely whether the sets of natural and (positive) real numbers could be put into one-to-one correspondence with each other.
On 7 December 1873 Cantor wrote Dedekind with the answer to his question; the answer was (and still is) “no”. The letter contains a proof of the impossibility of a one-to-one correspondence between the two sets.
This was the first time that something like this was done: attempt to compare two infinite entities by pairing off the elements of the sets such that every element of the first was paired with exactly one from the second and vice versa.
Cantor went on to study this idea in depth and he showed how to give a precise meaning to the idea that one set has (strictly) more (or fewer) elements than another set.
To get back to the original question: it is clear that there are at least as many real numbers as there are natural numbers as the latter set is a subset of the former. Cantor’s proof showed that there are strictly more real numbers than there are natural numbers.
There is a difference between this situation and the one mentioned in Cantor’s letter of 29 November, 1873: he mentioned that the natural numbers also form a subset of the positive rational numbers (all fractions of the form p/q with natural numbers p and q). Thus, it seems that there are more such rational numbers than that there are natural numbers. But, we can pair off the members of both sets in such a way that to one member of one set corresponds exactly one member of the other set.
To see this divide the fractions into groups: put fraction p/q into group n if p+q=n. Now observe that group n contains exactly n-1 fractions: 1/(n-1), 2/(n-2), …, (n-1)/1. This makes it easy to arrange the fractions in a nice simple sequence: first group 2, then group 3, then group 4, and so on and inside each group arrange the fractions according to their numerators, as we did above in group n.
The resulting sequence looks like this: 1/1, 1/2, 2/1, 1/3, 2/2, 3/1, 1/4, 2/3, 3/2, 4/1, … and this makes it easy to pair off the natural numbers and the positive fractions as desired.
Exercise Try to devise a formula for the number that goes with the fraction p/q, or, conversely, concoct a formula that tells us what the nth fraction is.
Exercise What would you do if you had to pair off the natural numbers and the positive rational numbers (one rational number corresponds to many fractions).
Here you can read Cantor’s letter in German. It is a scan from Briefwechsel Cantor-Dedekind. And here you can read my translation into English.
Recent Comments