Posts in category Wiskunde

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:
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’.

Eindexamen wiskunde A, vwo, 2019-05-20

Het eindexamen wiskunde A (vwo) was afgelopen maandag. De opgaven staan hier; ik heb de sommen gemaakt en hier zijn mijn uitwerkingen en opmerkingen.

Het examen leek mij niet echt moeilijk maar ik vond het verband tussen de lange inleidingen en de uiteindelijke sommen vaak wel ver te zoeken.

Eindexamen wiskunde B, vwo, 2019-05-20

Het eindexamen wiskunde B (vwo) was gisteren. De opgaven staan hier; ik heb de sommen gemaakt en hier zijn mijn uitwerkingen en opmerkingen.

Het examen leek mij goed te doen, veel vragen kwamen neer op niet al te moeilijke algebra of gonio. Hier en daar moest wat verder doorgedacht worden. Bij een paar opgaven was de gegeven beschrijving wel erg uitgebreid, vergeleken met het werk dat uiteindelijk gedaan moest worden.

Ik raad iedereen overigens af zo’n examen te maken terwijl je ook een film probeert te bekijken; ik vond vanochtend wel wat ongerechtigheden op mijn blaadjes van gisteravond.

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&uumlr 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:

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:

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.

De eindexamens wiskunde A en B van de havo.

De eindexamens waren al een week geleden maar de blogsite van de TU had deze week inlogproblemen dus ben ik hier een beetje laat.
Ik heb de examens gemaakt en de uitwerkingen staan hier: wiskunde A en wiskunde B.

De examens kwamen op mij niet moeilijk over; op facebook leidden mijn opmerkingen over wiskunde A tot veel discussie, met hier en daar een kanttekening dat wat ik `niet moeilijk’ vond voor veel leerlingen onoverkomelijk bleek.
Wat ik van wiskunde B vond bleek minder controversieel.

Maandag komen de eindexamens van het vwo.

Exacte oplossingen

Een veel voorkomende vraag op de wisfaq is: “Hoe los ik … op?” Op de plaats van de puntjes staat dan een vergelijking die maar niet tot een mooie oplossing wil leiden, zoals bijvoorbeeld -x2+4x-3 = sin(x). Het antwoord op de vraag is vaak: “Het kan niet exact, doe maar een numerieke benadering.” Maar wat betekent `exact’ eigenlijk?

Heel veel wiskundesommen komen uiteindelijk neer op het oplossen van een vergelijking, het invullen van een of meer getallen in een of andere uitdrukking, en/of het daarna vereenvoudigen van de uitkomst tot …, tot wat eigenlijk? Tot een compacte overzichtelijke uitdrukking waarvan wellicht ook makkelijk te controleren of het een oplossing van het probleem is. Wat een compacte overzichtelijke uitdrukking is varieert met de tijd. Het begint met natuurlijke getallen; een antwoord als `3′ is duidelijk en je kunt waarschijnlijk natellen of het klopt. Vrij snel komen (positieve) breuken bij het verdelen van dingen (traditioneel taarten) over personen: drie taarten over vijf personen eerlijk verdelen levert iedereen 3/5 taart op. Nog later komen er negatieve getallen bij, meestal uitgelegd als `schuld’.

Dat is allemaal nog redelijk overzichtelijk maar dan wordt het spannender: als je een vierkant met een oppervlakte van 2 m2 wilt maken dan heb je niks aan al die breuken, positief of niet. Om praktische redenen is het wel gewenst de lengte van de zijden van dat vierkant te benoemen, en dat heeft geleid tot een van de eerste afkortingen die je bij de wiskunde leert: √2. Dat getal is echt nieuw, niet te weer te geven als een breuk. Er is zelfs een heel Zebraboekje aan √2 gewijd.

Het interessante is dat na verloop van tijd dat symbool √ heel vertrouwd wordt en dat we het accepteren als ingredient in die `compacte overzichtelijke’ uitdrukkingen. Met de abc-formule als eerste hoogtepunt. Ondanks het feit dat √D niet meer is dan een afkorting van “het positieve reële getal waarvan het kwadraat gelijk is aan D”.

Een andere bekende afkorting is natuurlijk π: de verhouding tussen omtrek en diameter van een cirkel. Ook π is niet als breuk uit te drukken, erger nog: met π is algebraïsch helemaal geen goed garen te spinnen. Maar π komt in zoveel uitkomsten en formules voor dat het onderhand een vertrouwde vriend geworden is.

Op de middelbare school en later stijgt het aantal `vertrouwde vrienden’ snel, via allerlei nieuwe functies als sinus, cosinus, e-macht, logaritme, … Zo is de lengte van het stukje van de parabool met vergelijking y=x2 tussen de punten (0,0) en (1,1) gelijk aan

en niemand knippert met de ogen. Als je de echte betekenis van die uitdrukking wilt achterhalen zul je vrij diep de wiskunde in moeten duiken want hij hangt van afkortingen aan elkaar.

Even terug naar de vergelijking aan het begin. Heeft die vergelijking wel oplossingen? Ja, daar kun je je van overtuigen door de grafieken van het linker- en rechterlid even te schetsen; je ziet dan dat er een intervalletje is waarop -x2+4x-3 groter is dan sin(x) en de eindpunten van dat intervalletje zijn de oplossingen van de vergelijking. Is er een formule voor de linkeroplossing? Ja:

deze komt direct uit het bewijs van de tussenwaardestelling. Die stelling zegt dat dat minimum bestaat, noem het even a, en dat a daadwerkelijk aan de vergelijking voldoet. Voor wie dit geen mooie formule vindt, bedenk dan dat √2 niets meer is dan een afkorting voor

hetwelk volgens diezelfde tussenwaardestelling bestaat.

Met a en √2 is goed te werken; je kunt ze in allerlei uitdrukkingen stoppen en die weer proberen te vereenvoudigen. In het geval van √2 vervang je telkens (√2)2 door 2; probeer maar eens aan te tonen dat

Wat a betreft: telkens als je sin(a) ziet kun je daar -a2+4a-3 van maken (of omgekeerd); dat gebeurt niet zo vaak en daarom zal a lang niet zo vertrouwd worden als √2 dat al eeuwen is.

BMI en de divergentiestelling? Nou, nee.

Op de wisfaq een vraag: Wat is de link tussen de BMI en de divergentiestelling? Die link is er niet.
Even recapituleren:

  • De body mass index (BMI) of Quetelet index van personen is hun massa gedeeld door het kwadraat van hun lengte, in kg/m2.
  • De divergentiestelling verbindt twee integralen, de een over een lichaam, de ander over de rand van dat lichaam. Losjes gesproken laat het zien welke functie zorgt voor de productie van hetgeen via een vectorveld door de rand naar buiten ontsnapt.

Wat hebben die twee met elkaar te maken? Nou, niks. Je zou denken dat het iets met warmtestroming door de huid en de productie van energie in het lichaam te maken zou kunnen hebben maar de eenheden kloppen daarvoor van geen kant.
De geschiedenis van de BMI laat echter nog veel duidelijker zien dat er geen verband is. Het de zin en onzin van de BMI is tien jaar geleden al mooi door Keith Devlin beschreven in Do You Believe in Fairies, Unicorns, or the BMI?; ik heb daar niets aan toe te voegen.
Een belangrijk citaat uit Devlin’s stuk: “The BMI was formulated, by a mathematician, not a medical physician, to provide a simple, easy-to-apply mathematical formula to give a broad, society-level measure of weight issues. It has absolutely no scientific or medical basis. It is based purely on a crude statistical analysis. It measures a general society trend, it does not predict.” Daar is dus geen divergentiestelling aan te pas gekomen.

Los op. Of toch niet?

Een aardige vraag op de wisfaq die laat zien dat een opgave goed lezen ook belangrijk is.

De vraagsteller had moeite met deze vraag:

“Toon aan dat er een reëel getal t bestaat zodat voor de functie g(x)=(x-a)2(x-b)2+x geldt dat g(t)=(a+b)/2.”

Het oplossen van de vergelijking (t-a)2(t-b)2+t=(a+b)/2 lukte niet helemaal.
Maar hoogstwaarschijnlijk was het helemaal niet de bedoeling die vergelijking op te lossen: de opgave was namelijk “toon aan dat zo’n t bestaat”, niet “bepaal zo’n t”. Dat de vraagsteller een student van een universiteit is suggereert dat het hiet om een toepassing van de Tussenwaardestelling gaat. Die stelling spreekt voor velen bijna voor zichzelf maar een van de eersten, zo niet de eerste, die doorhad dat er iets te bewijzen was was Bernard Bolzano. In een artikel met de welluidende titel Rein analytischer Beweis des Lehrsatzes daß zwischen je zwey Werthen, die ein entgegengesetzetes Resultat gewähren, wenigstens eine reelle Wurzel der Gleichung liege legde hij uit dat de volgende stelling wel degelijk een bewijs nodig had:

Laat f en φ twee continue functies zijn en a en b twee reële getallen zo dat f(a)<φ(a) en f(b)>φ(b); dan ligt er een getal c tussen a en b met f(c)=φ(c)

In een tijd dat `continu’ meetkundig werd geïnterpreteerd als `de grafiek is een ononderbroken kromme’ leek het duidelijk dat de grafieken van f en φ elkaar tussen a en b zouden moeten snijden. Bolzano waste zijn tijdgenoten grondig de oren over deze misvatting; hij wilde een echt analytisch bewijs en geen `kijk maar, er is een snijpunt’. Bolzano had namelijk ook al door dat niet elke continue functie een makkelijk te tekenen grafiek had: hij heeft ook een van de eerste continue nergens differentieerbare functies geconstrueerd. In het artikel van Bolzano vinden we een analytische definitie van continuïteit en een bewijs van de tussenwaardestelling dat zo in de huidige boeken opgenomen kan worden (en eigenlijk opgenomen is).

Met deze stelling in de hand is de opgave zo opgelost: voor de functie van de vraag geldt g(a)=a en g(b)=b; het getal gemiddelde (a+b)/2 van a en b ligt tussen a en b, dus toepassing van Bolzano’s stelling met g en de constante functie ψ met waarde (a+b)/2 levert het bestaan van een t tussen a en b met g(t)=(a+b)/2.

Overigens kan de vergelijking wel opgelost worden: er is een oplosformule voor de vierdegraadsvergelijking maar die staat vrijwel nergens op het programma van een analysecursus.

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 20>ℵω 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.

© 2011 TU Delft