Posts in category Georg Cantor

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.

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.

On this day in 1873

On this day, 29 November, in 1873 Georg Cantor wrote a letter to Richard Dedekind. It contained a question that inaugurated a new mathematical discipline: Set Theory.

Cantor writes:

Allow me to put a question before you that is of some theoretical interest to me, but which I have not been able to answer; maybe you can, and would you be so kind as to write me about this, it concerns the following.

One takes the aggregate of a positive whole numbers n and denotes this by (n); furthermore one considers the aggregate of all positive real numbers x and denotes this by (x); then the question is simply that whether (n) and (x) can be put into some correspondence in such a way that every individual from one aggregate belongs to just one of the other and conversely?

In modern terms: is there a bijection between the set of natural numbers and the set of positive real numbers?

Cantor goes on to say that a simple `no’ “because (n) is discrete and (x) forms a continuum” does not suffice because the same could be said of (n) versus the aggregate of positive rational numbers yet one can create a correspondence as desired between these two entities.

The full letter can be read here in German. It is a scan from Briefwechsel Cantor-Dedekind.

The answer to the question? Watch this space.

© 2011 TU Delft