Universitaire wiskunde — Bachelor jaar 1 · Bachelor Year 1

1Logica, verzamelingen en afbeeldingen

Tot nu toe steunden bewijzen op een informeel, maar eerlijk gevoel voor wat “bewijzen” inhoudt. Dit eerste hoofdstuk van de universitaire wiskunde legt de spelregels vast: wat een wiskundige uitspraak is, hoe connectieven en kwantoren uitspraken aan elkaar knopen, welke zetten in een bewijs geoorloofd zijn — en bouwt op dat fundament de twee universele talen van de wiskunde: verzamelingen en afbeeldingen.

1.1 Uitspraken en connectieven

Definitie 1.1 (Uitspraak, connectieven)

Een uitspraak (of propositie) is een zin die waar (W) of onwaar (O) is — precies één van beide. Uit twee uitspraken $P$ en $Q$ vormen we:

de negatie $\lnot P$ (“niet $P$ ”), waar precies wanneer $P$ onwaar is;
de conjunctie $P \land Q$ (“ $P$ en $Q$ ”), waar precies wanneer beide waar zijn;
de disjunctie $P \lor Q$ (“ $P$ of $Q$ ”), waar precies wanneer minstens één van beide waar is (deze “of” is inclusief);
de implicatie $P \implies Q$ , onwaar precies wanneer $P$ waar is en $Q$ onwaar;
de equivalentie $P \iff Q$ , waar precies wanneer $P$ en $Q$ dezelfde waarheidswaarde hebben.

Opmerking 1.2

Bij de waarheidstabel van $P \implies Q$ loont het even stil te staan: zodra $P$ onwaar is, is $P \implies Q$ waar, wat $Q$ ook is. “Als $2 < 1$ , dan $0 = 5$ ” is een ware implicatie. Een implicatie beweert niets over het geval waarin haar hypothese niet opgaat.

Propositie 1.3 (Rekenregels voor uitspraken)

Voor alle uitspraken $P$ , $Q$ , $R$ geldt:

$\lnot(\lnot P) \iff P$ ;
de wetten van De Morgan: $\lnot(P \land Q) \iff (\lnot P) \lor (\lnot Q)$ en $\lnot(P \lor Q) \iff (\lnot P) \land (\lnot Q)$ ;
$(P \implies Q) \iff \bigl((\lnot P) \lor Q\bigr)$ , en dus $\lnot(P \implies Q) \iff P \land (\lnot Q)$ ;
contrapositie: $(P \implies Q) \iff \bigl((\lnot Q) \implies (\lnot P)\bigr)$ ;
$(P \iff Q) \iff \bigl((P \implies Q) \land (Q \implies P)\bigr)$ ;
distributiviteit: $P \land (Q \lor R) \iff (P \land Q) \lor (P \land R)$ en $P \lor (Q \land R) \iff (P \lor Q) \land (P \lor R)$ .

Bewijs. Elke equivalentie controleer je door waarheidstabellen te vergelijken: twee samengestelde uitspraken in $P$ , $Q$ , $R$ zijn equivalent precies wanneer ze in elk van de (vier of acht) gevallen dezelfde waarheidswaarde aannemen. We schrijven één tabel volledig uit, voor de eerste wet van De Morgan:

$P$	$Q$	$P \land Q$	$\lnot(P \land Q)$	$\lnot P$	$\lnot Q$	$(\lnot P) \lor (\lnot Q)$
W	W	W	O	O	O	O
W	O	O	W	O	W	W
O	W	O	W	W	O	W
O	O	O	W	W	W	W

Kolom $4$ en kolom $7$ vallen samen, en dat bewijst de wet. Voor de contrapositie gaat het sneller met woorden: $P \implies Q$ is onwaar precies in het geval ( $P$ waar, $Q$ onwaar), en $(\lnot Q) \implies (\lnot P)$ is onwaar precies in het geval ( $\lnot Q$ waar, $\lnot P$ onwaar), oftewel ( $Q$ onwaar, $P$ waar) — hetzelfde enige geval, dus hebben beide implicaties identieke tabellen. De overige regels gaan net zo. Merk op dat (3) elke implicatie herleidt tot een disjunctie, zodat (2) er werktuiglijk de negatieregel $\lnot(P \implies Q) \iff P \land (\lnot Q)$ uit maakt: wie een implicatie wil weerleggen, moet een geval aanwijzen waarin de hypothese geldt en de conclusie faalt. ∎

1.2 Kwantoren

Definitie 1.4 (Kwantoren)

Zij $P(x)$ een eigenschap van een element $x$ van een verzameling $E$ .

$\forall x \in E,\ P(x)$ (“voor alle $x$ in $E$ geldt $P(x)$ ”) is waar wanneer elk element van $E$ aan $P$ voldoet;
$\exists x \in E,\ P(x)$ (“er bestaat een $x$ in $E$ zodat $P(x)$ ”) is waar wanneer minstens één element van $E$ aan $P$ voldoet.

We schrijven $\exists!$ voor “er bestaat precies één”.

Propositie 1.5 (Negatie van kwantoren)

\lnot\bigl(\forall x \in E,\ P(x)\bigr) \iff \exists x \in E,\ \lnot P(x), \qquad \lnot\bigl(\exists x \in E,\ P(x)\bigr) \iff \forall x \in E,\ \lnot P(x).

Bewijs. We bewijzen de eerste equivalentie in beide richtingen; de tweede gaat symmetrisch. Is $\forall x \in E,\ P(x)$ onwaar, dan voldoet niet elk element aan $P$ : de verzameling $A = \{x \in E : \lnot P(x)\}$ kan niet leeg zijn, en elk van haar elementen getuigt van $\exists x \in E,\ \lnot P(x)$ . Omgekeerd, als een zekere $x_0 \in E$ voldoet aan $\lnot P(x_0)$ , dan is $x_0$ een tegenvoorbeeld en faalt de universele uitspraak. Voor de tweede regel: “geen enkele $x$ voldoet aan $P$ ” zegt dat de verzameling $\{x : P(x)\}$ leeg is, dat wil zeggen dat elke $x$ in haar complement $A$ ligt. Passen we beide regels in cascade toe op een rij geneste kwantoren, dan krijgen we de mechanische procedure van Voorbeeld 1.8: de negatie loopt van links naar rechts, verwisselt elke $\forall$ met $\exists$ en elke $\exists$ met $\forall$ , en ontkent ten slotte het binnenste predicaat. ∎

Voorbeeld 1.6 (Alledaagse wiskundige zinnen ontkennen)

Zij $f \colon \R \to \R$ . De zin “ $f$ is stijgend” luidt

\forall x \in \R,\ \forall y \in \R,\quad x \leq y \implies f(x) \leq f(y) ,

en haar negatie is, volgens Propositie 1.5 samen met de regel $\lnot(P \implies Q) \iff P \land \lnot Q$ :

\exists x \in \R,\ \exists y \in \R,\quad x \leq y \ \text{ en }\ f(x) > f(y) :

één getuigend paar volstaat. Evenzo is “ $f$ is begrensd” de uitspraak $\exists M \in \R,\ \forall x \in \R,\ \abs{f(x)} \leq M$ , met negatie

\forall M \in \R,\ \exists x \in \R,\quad \abs{f(x)} > M :

welke grens ook wordt voorgesteld, er is een punt dat haar overtreft. Het inzicht: een correcte negatie bevat nooit een “niet” vóór een blok kwantoren — ze is een nieuwe, positieve uitspraak waarin de rollen omgedraaid zijn: je levert nu de getuigen die je eerst kreeg aangereikt.

Voorbeeld 1.7 (Volgorde van de kwantoren)

De volgorde van verschillende kwantoren doet ertoe:

\forall x \in \R,\ \exists y \in \R,\ y > x \quad\text{is waar (neem } y = x+1\text{),}

\exists y \in \R,\ \forall x \in \R,\ y > x \quad\text{is onwaar (geen reëel getal overtreft alle reële getallen).}

In de eerste uitspraak mag $y$ van $x$ afhangen; in de tweede moet één enkele $y$ het voor alle $x$ doen. Twee gelijke kwantoren mogen daarentegen altijd van plaats wisselen.

Voorbeeld 1.8 (Een definitie met drie kwantoren lezen)

De zin “de rij $(u_n)$ convergeert naar $\ell$ ” wordt in Hoofdstuk 11 geschreven als

\forall \varepsilon > 0,\ \exists N \in \N,\ \forall n \geq N,\quad \abs{u_n - \ell} \leq \varepsilon .

Haar negatie luidt, na driemaal Propositie 1.5,

\exists \varepsilon > 0,\ \forall N \in \N,\ \exists n \geq N,\quad \abs{u_n - \ell} > \varepsilon .

Zulke zinnen werktuiglijk kunnen ontkennen, zonder na te denken over wat ze betekenen, is een vaardigheid op zich: ze scheidt het logische werk van het wiskundige.

1.3 Bewijstechnieken

Methode 1.9 (De standaardpatronen van een bewijs)

Om te bewijzen…

een implicatie $P \implies Q$ rechtstreeks: neem $P$ aan, leid $Q$ af;
via contrapositie: neem $\lnot Q$ aan, leid $\lnot P$ af — geldig volgens Propositie 1.3 (4);
uit het ongerijmde: neem aan dat de uitspraak onwaar is en leid een tegenspraak af;
een equivalentie: bewijs beide implicaties apart (of rijg bekende equivalenties aaneen);
een “voor alle”-uitspraak: kies een willekeurige $x$ in $E$ (“zij $x \in E$ ”) en bewijs $P(x)$ ;
een “er bestaat”-uitspraak: wijs een getuige aan, of bewijs het bestaan langs een omweg;
met inductie: zie Stelling 1.12.

Bewijs je iets over een goedgekozen maar willekeurig element, geef dat element dan nooit extra eigenschappen: “zij $x \in \R$ ” gevolgd door “omdat $x > 0$ …” bewijst niets over negatieve $x$ .

Opmerking 1.10 (Veelgemaakte fouten in bewijzen)

Vier klassieke valkuilen, die het verdienen één keer bij naam genoemd te worden.

Omkering in plaats van contrapositie. $Q \implies P$ is niet equivalent met $P \implies Q$ ; alleen $\lnot Q \implies \lnot P$ is dat. “Als het regent, is de straat nat” geeft je niet het recht uit een natte straat regen te besluiten.
Een equivalentie met één implicatie bewijzen. Een “dan en slechts dan”-bewering is twee stellingen; zeg welke richting je bewijst, en bewijs ze allebei. Een keten van $\iff$ is alleen geldig als elke schakel werkelijk omkeerbaar is — een vergelijking kwadrateren bijvoorbeeld is dat niet.
Achterstevoren bewijzen. Vertrekken van de gewenste conclusie en daaruit iets waars afleiden bewijst niets (uit $-1 = 1$ volgt na kwadrateren het ware $1 = 1$ ). Een berekening mag achterstevoren gevonden worden, maar ze moet voorwaarts opgeschreven worden, of met expliciete equivalenties.
Vaste getuige tegenover willekeurig element. Voor $\exists x,\ P(x)$ volstaat één slim gekozen $x$ ; voor $\forall x,\ P(x)$ moet de gekozen $x$ willekeurig blijven. Die twee door elkaar halen — een universele bewering op een voorbeeld nagaan — is de meest voorkomende fout in beginnerswerk.

Voorbeeld 1.11 (Contrapositie en ongerijmde aan het werk)

Voor $n \in \N$ : is $n^2$ even, dan is $n$ even. Via contrapositie: is $n$ oneven, $n = 2k+1$ , dan is $n^2 = 4k^2 + 4k + 1$ oneven.

$\sqrt 2$ is irrationaal. Uit het ongerijmde: stel $\sqrt 2 = p/q$ met $p, q \in \N^*$ en de breuk onvereenvoudigbaar. Dan is $p^2 = 2q^2$ even, dus is $p$ even (vorig punt), zeg $p = 2r$ ; dan is $q^2 = 2r^2$ even, dus is $q$ even — in tegenspraak met de onvereenvoudigbaarheid.

Stelling 1.12 (Inductie)

Zij $P(n)$ een eigenschap van het gehele getal $n$ . Als

$P(0)$ waar is, en
voor alle $n \in \N$ geldt $P(n) \implies P(n+1)$ ,

dan is $P(n)$ waar voor alle $n \in \N$ .

Sterke inductie: dezelfde conclusie geldt wanneer (2) vervangen wordt door: voor alle $n$ geldt $\bigl(P(0) \land \dots \land P(n)\bigr) \implies P(n+1)$ .

Bewijs. Dit is een eigenschap van $\N$ zelf, equivalent met: elke niet-lege deelverzameling van $\N$ heeft een kleinste element (wat we als bekend aannemen). Stel immers dat (1) en (2) gelden en zet $A = \{n \in \N : P(n) \text{ onwaar}\}$ . Is $A \neq \emptyset$ , dan heeft $A$ een kleinste element $m$ ; wegens (1) is $m \neq 0$ ; dan is $m - 1 \notin A$ , dus geldt $P(m-1)$ , en (2) levert $P(m)$ — tegenspraak. Dus $A = \emptyset$ . Voor sterke inductie werkt hetzelfde argument: $P(0), \dots, P(m-1)$ gelden alle, omdat $m$ het kleinste element van $A$ is. ∎

Voorbeeld 1.13 (Uniek bestaan bewijzen)

Een uitspraak $\exists!\,x,\ P(x)$ bestaat uit twee uitspraken, die apart bewezen worden: het bestaan (wijs een $x_0$ met $P(x_0)$ aan of construeer er een) en de uniciteit (neem $P(x)$ en $P(x')$ aan en leid $x = x'$ af). Een voorbeeld: er is precies één reëel getal $x$ met $x^3 + x = 2$ . Bestaan: $x_0 = 1$ voldoet, want $1 + 1 = 2$ . Uniciteit: uit $x^3 + x = x'^3 + x'$ volgt

0 = (x^3 - x'^3) + (x - x') = (x - x')\,\bigl(x^2 + xx' + x'^2 + 1\bigr),

en de tweede factor is positief (hij is gelijk aan $\bigl(x + \tfrac{x'}2\bigr)^2 + \tfrac34 x'^2 + 1 \geq 1$ ), zodat $x = x'$ . Let op de werkverdeling: het bestaan berustte op een gelukkige gok, de uniciteit op algebra die geldt voor willekeurige oplossingen — geen van beide argumenten doet het werk van het andere, en de tweede helft vergeten blijft een blijvende verleiding zodra één oplossing gevonden is.

Voorbeeld 1.14

Voor alle $n \in \N^*$ geldt $\;\sum_{k=1}^n k = \frac{n(n+1)}{2}$ . Basisgeval $n = 1$ : beide leden zijn $1$ . Stap: neem de formule aan voor $n$ , dan is

\sum_{k=1}^{n+1} k = \frac{n(n+1)}{2} + (n+1) = (n+1)\Bigl(\frac n2 + 1\Bigr) = \frac{(n+1)(n+2)}{2}. \qedhere

Voorbeeld 1.15 (Sterke inductie aan het werk)

Elk geheel getal $n \geq 2$ is een product van priemgetallen (een priemgetal is een geheel getal $\geq 2$ waarvan $1$ en het getal zelf de enige delers $\geq 1$ zijn; priemgetallen worden om hun eigen wille bestudeerd in Hoofdstuk 6). Gewone inductie helpt hier niet: weten dat $95 = 5 \times 19$ ontbindt, zegt niets over $96$ . Sterke inductie past precies. Basisgeval: $2$ is priem, dus een product van priemgetallen met één factor. Stap: zij $n \geq 2$ en neem aan dat elk geheel getal $m$ met $2 \leq m \leq n$ een product van priemgetallen is. Is $n + 1$ priem, dan zijn we klaar. Zo niet, dan is $n + 1 = ab$ met $2 \leq a, b \leq n$ ; volgens de sterke hypothese zijn $a$ en $b$ producten van priemgetallen, en dus ook $n + 1$ . Het inzicht: sterke inductie is het juiste gereedschap zodra de “reden” voor $P(n+1)$ op een onvoorspelbare eerdere rang ligt en niet op rang $n$ .

1.4 Verzamelingen

Definitie 1.16 (Bewerkingen met verzamelingen)

We nemen het begrip verzameling en de lidmaatschapsrelatie $x \in E$ als primitief aan. Voor verzamelingen $A, B$ binnen een omvattende verzameling $E$ :

inclusie: $A \subseteq B$ wanneer $\forall x,\ x \in A \implies x \in B$ ; gelijkheid $A = B$ wanneer $A \subseteq B$ en $B \subseteq A$ ;
de vereniging $A \cup B$ , de doorsnede $A \cap B$ , het verschil $A \setminus B = \{x \in A : x \notin B\}$ , het complement $\overline{A} = E \setminus A$ ;
de lege verzameling $\emptyset$ , bevat in elke verzameling;
de machtsverzameling $\mathcal{P}(E)$ : de verzameling van alle deelverzamelingen van $E$ ;
het product $E \times F$ : de verzameling van geordende paren $(x, y)$ met $x \in E$ , $y \in F$ .

Voorbeeld 1.17 (Wennen aan de machtsverzameling)

Voor $E = \{a, b\}$ is

\mathcal P(E) = \bigl\{\, \emptyset,\ \{a\},\ \{b\},\ \{a, b\} \,\bigr\},

vier elementen — en let op de typediscipline: $a \in E$ , maar $\{a\} \in \mathcal P(E)$ ; de uitspraken $a \in \mathcal P(E)$ en $\{a\} \subseteq \mathcal P(E)$ zijn zoals ze er staan allebei onwaar (de tweede zou vergen dat $a$ een deelverzameling van $E$ is). Iteratie vanuit het niets: $\mathcal P(\emptyset) = \{\emptyset\}$ heeft één element, $\mathcal P(\mathcal P(\emptyset)) = \{\emptyset, \{\emptyset\}\}$ er twee, de volgende vier — verzamelingen van verzamelingen zijn gewone verzamelingen, en Hoofdstuk 2 zal het verdubbelingspatroon bevestigen: $\abs{\mathcal P(E)} = 2^{\abs E}$ . De niveaus ( $x$ , $\{x\}$ , $\{\{x\}\}$ ) uit elkaar houden is het halve werk bij oefeningen als Oefeningen 1.11 en 1.12.

Propositie 1.18 (Verzamelingenalgebra)

Voor deelverzamelingen $A, B, C$ van $E$ geldt:

$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ en $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ ;
De Morgan: $\overline{A \cup B} = \overline{A} \cap \overline{B}$ en $\overline{A \cap B} = \overline{A} \cup \overline{B}$ ;
$A \subseteq B \iff \overline{B} \subseteq \overline{A}$ .

Bewijs. Elke identiteit vertaalt een regel uit Propositie 1.3 via het woordenboek (wel of niet $\in A$ ) $\leftrightarrow$ (uitspraak waar of onwaar): bijvoorbeeld $x \in \overline{A \cup B} \iff \lnot(x \in A \lor x \in B) \iff (x \notin A) \land (x \notin B) \iff x \in \overline{A} \cap \overline{B}$ . Punt (3) is contrapositie. Als tweede staaltje de eerste distributiviteitswet, volledig uitgeschreven:

x \in A \cap (B \cup C) \iff (x \in A) \land \bigl(x \in B \lor x \in C\bigr) \iff \bigl(x \in A \land x \in B\bigr) \lor \bigl(x \in A \land x \in C\bigr),

wegens de distributiviteit uit Propositie 1.3 (6), en de laatste uitspraak zegt $x \in (A \cap B) \cup (A \cap C)$ . Elke verzamelingsidentiteit van dit type volgt uit diezelfde ene mechanische vertaling — en daarom hoeft er geen enkele uit het hoofd geleerd te worden. ∎

Methode 1.19 (Gelijkheid van verzamelingen bewijzen)

Om $A = B$ te bewijzen, bewijs je de twee inclusies: zij $x \in A$ , toon $x \in B$ ; zij vervolgens $x \in B$ , toon $x \in A$ . Als alternatief rijg je equivalenties aaneen, $x \in A \iff \dots \iff x \in B$ , mits elke stap werkelijk een equivalentie is.

De wetten van De Morgan in beeld: het gearceerde gebied links is A ∪ B = A ∩ B (alles buiten beide schijven); rechts is het A ∩ B = A ∪ B (alles behalve de lensvormige overlap). Een tekening is geen bewijs, maar ze maakt het elementsgewijze bewijs van onvergetelijk. — De wetten van De Morgan in beeld: het gearceerde gebied links is $\overline{A \cup B} = \overline A \cap \overline B$ (alles buiten beide schijven); rechts is het $\overline{A \cap B} = \overline A \cup \overline B$ (alles behalve de lensvormige overlap). Een tekening is geen bewijs, maar ze maakt het elementsgewijze bewijs van Propositie 1.18 onvergetelijk.

1.5 Afbeeldingen

Definitie 1.20 (Afbeelding, beeld, origineel)

Een afbeelding (of functie) $f \colon E \to F$ kent aan elk element $x$ van de verzameling $E$ (het domein) precies één element $f(x)$ van de verzameling $F$ (het codomein) toe. Voor $A \subseteq E$ en $B \subseteq F$ zijn

f(A) = \{f(x) : x \in A\} \subseteq F, \qquad f^{-1}(B) = \{x \in E : f(x) \in B\} \subseteq E

het beeld van $A$ en het origineel van $B$ . De samenstelling van $f \colon E \to F$ en $g \colon F \to G$ is $g \circ f \colon E \to G$ , $x \mapsto g(f(x))$ .

Opmerking 1.21

De notatie $f^{-1}(B)$ veronderstelt geen inverse afbeelding: $f^{-1}(B)$ is voor elke $f$ gedefinieerd. Originelen gedragen zich beter dan beelden: $f^{-1}$ bewaart verenigingen, doorsneden en complementen, terwijl $f(A \cap A') \subseteq f(A) \cap f(A')$ strikt kan zijn (Oefening 1.8).

Voorbeeld 1.22 (Beelden en originelen berekenen)

Zij $f \colon \R \to \R$ , $x \mapsto x^2$ . Dan is

f\bigl(\intcc{-1}{2}\bigr) = \intcc04, \qquad f^{-1}\bigl(\intcc14\bigr) = \intcc{-2}{-1} \cup \intcc12, \qquad f^{-1}(\{-1\}) = \emptyset .

Voor het eerste: elke $x \in \intcc{-1}2$ heeft $x^2 \in \intcc04$ , en elke $y \in \intcc04$ wordt bereikt als $y = (\sqrt y)^2$ met $\sqrt y \in \intcc02 \subseteq \intcc{-1}2$ — merk op dat het beeld niet $\intcc14 = \{(-1)^2, 2^2\}$ is: beelden van intervallen bereken je niet uit de randpunten alleen. Voor het tweede: $1 \leq x^2 \leq 4 \iff 1 \leq \abs x \leq 2$ , wat in twee stukken uiteenvalt. Het derde toont dat een origineel leeg mag zijn — $f^{-1}(B)$ is altijd zinvol, hoe klein de doorsnede van $B$ met het beeld ook is. Bekijk ten slotte op ditzelfde voorbeeld het strengheidsverschijnsel uit de opmerking hierboven: met $A = \intcc{-1}0$ en $A' = \intcc01$ is $f(A \cap A') = f(\{0\}) = \{0\}$ , terwijl $f(A) \cap f(A') = \intcc01$ .

Definitie 1.23 (Injectief, surjectief, bijectief)

Een afbeelding $f \colon E \to F$ heet:

injectief wanneer verschillende elementen verschillende beelden hebben: $\forall x, x' \in E,\ f(x) = f(x') \implies x = x'$ ;
surjectief wanneer elk element van $F$ bereikt wordt: $\forall y \in F,\ \exists x \in E,\ f(x) = y$ ;
bijectief wanneer ze beide is, dat wil zeggen wanneer elke $y \in F$ precies één origineel heeft.

Stelling 1.24 (Inverse afbeelding)

Een afbeelding $f \colon E \to F$ is bijectief dan en slechts dan als er een afbeelding $g \colon F \to E$ bestaat met $g \circ f = \mathrm{id}_E$ en $f \circ g = \mathrm{id}_F$ . In dat geval is $g$ uniek; ze wordt genoteerd $f^{-1}$ en de inverse van $f$ genoemd, en $f^{-1}$ is zelf bijectief met $(f^{-1})^{-1} = f$ .

Bewijs. ( $\Rightarrow$ ) Is $f$ bijectief, dan heeft elke $y \in F$ precies één origineel; definieer $g(y)$ als dat origineel. Dan is $f(g(y)) = y$ per constructie, en $g(f(x)) = x$ omdat $x$ hét origineel van $f(x)$ is.

( $\Leftarrow$ ) Stel dat zo’n $g$ bestaat. Uit $f(x) = f(x')$ volgt na toepassing van $g$ dat $x = x'$ : $f$ is injectief. Voor $y \in F$ voldoet $x = g(y)$ aan $f(x) = y$ : $f$ is surjectief.

Uniciteit: voldoen zowel $g$ als $h$ , dan is $g = g \circ \mathrm{id}_F = g \circ (f \circ h) = (g \circ f) \circ h = h$ . Ten slotte is het paar identiteiten symmetrisch in $f$ en $g$ , zodat $g = f^{-1}$ bijectief is met inverse $f$ . ∎

Voorbeeld 1.25 (Een inverse in de praktijk berekenen)

Zij $f \colon \R \to \intoo0{+\infty}$ , $f(x) = \eu^{2x+1}$ . Om te inverteren los je $y = f(x)$ op naar $x$ , voor gegeven $y > 0$ :

y = \eu^{2x+1} \iff \ln y = 2x + 1 \iff x = \frac{\ln y - 1}2 ,

en elke stap is omkeerbaar op de aangekondigde domeinen. De berekening levert alles tegelijk: bij elke $y$ in het codomein hoort precies één oplossing $x$ , dus $f$ is bijectief, en

f^{-1} \colon \intoo0{+\infty} \to \R, \qquad f^{-1}(y) = \frac{\ln y - 1}2 .

Een snelle controle van beide samenstellingen ( $f^{-1}(f(x)) = \frac{(2x+1) - 1}2 = x$ en $f(f^{-1}(y)) = \eu^{\ln y} = y$ ) bevestigt het criterium van Stelling 1.24. Het inzicht: “los op naar $x$ en houd de equivalenties in het oog” is tegelijk het bestaansbewijs, het uniciteitsbewijs en de formule — maar het werkt alleen als het codomein correct is aangekondigd ( $f$ is niet surjectief op $\R$ ).

Propositie 1.26 (Samenstelling en de drie eigenschappen)

Zij $f \colon E \to F$ en $g \colon F \to G$ .

Zijn $f$ en $g$ injectief (respectievelijk surjectief, bijectief), dan is $g \circ f$ dat ook; en in het bijectieve geval is $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ .
Is $g \circ f$ injectief, dan is $f$ injectief. Is $g \circ f$ surjectief, dan is $g$ surjectief.

Bewijs. (1) Uit $g(f(x)) = g(f(x'))$ volgt met de injectiviteit van $g$ dat $f(x) = f(x')$ , en met die van $f$ dat $x = x'$ . Is $z \in G$ , dan levert de surjectiviteit van $g$ een $y$ met $g(y) = z$ , en die van $f$ een $x$ met $f(x) = y$ , zodat $g(f(x)) = z$ . In het bijectieve geval ga je rechtstreeks na dat $f^{-1} \circ g^{-1}$ een tweezijdige inverse van $g \circ f$ is, waarna de uniciteit in Stelling 1.24 de zaak afmaakt.

(2) Uit $f(x) = f(x')$ volgt $g(f(x)) = g(f(x'))$ , en de injectiviteit van $g \circ f$ geeft $x = x'$ . Is $z \in G$ , dan levert de surjectiviteit van $g \circ f$ een $x$ met $g(f(x)) = z$ : dan voldoet $y = f(x)$ aan $g(y) = z$ . ∎

Voorbeeld 1.27 (Punt (2) is scherp)

In Propositie 1.26 (2) kunnen de conclusies niet versterkt worden: dat $g \circ f$ bijectief is, dwingt $f$ niet surjectief of $g$ injectief te zijn. Neem $E = G = \{1\}$ , $F = \{1, 2\}$ , met $f(1) = 1$ en $g(1) = g(2) = 1$ : dan is $g \circ f = \mathrm{id}_E$ bijectief, terwijl $f$ het element $2$ mist en $g$ beide elementen op elkaar plakt. De moraal is een nauwkeurige boekhoudregel: informatie over de samenstelling stroomt voor injectiviteit naar de binnenste afbeelding en voor surjectiviteit naar de buitenste, nooit andersom. (Oefening 1.9 bouwt hetzelfde verschijnsel op oneindige verzamelingen, waar het de motor is achter eenzijdige inversen.)

Voorbeeld 1.28

$f \colon \R \to \R$ , $x \mapsto x^2$ is injectief noch surjectief ( $f(-1) = f(1)$ , en $-1$ heeft geen origineel). Beperken we domein en codomein, dan is $f \colon \R_+ \to \R_+$ , $x \mapsto x^2$ bijectief, met inverse $y \mapsto \sqrt y$ . Of een afbeelding injectief of surjectief is, hangt dus af van het aangekondigde domein en codomein, niet alleen van het voorschrift.

1.6 Relaties

Definitie 1.29 (Equivalentierelatie)

Een binaire relatie $\mathcal{R}$ op een verzameling $E$ heet een equivalentierelatie wanneer ze reflexief is ( $x \mathbin{\mathcal{R}} x$ voor alle $x$ ), symmetrisch ( $x \mathbin{\mathcal{R}} y \implies y \mathbin{\mathcal{R}} x$ ) en transitief (uit $x \mathbin{\mathcal{R}} y$ en $y \mathbin{\mathcal{R}} z$ volgt $x \mathbin{\mathcal{R}} z$ ). De equivalentieklasse van $x$ is $\mathrm{cl}(x) = \{y \in E : x \mathbin{\mathcal{R}} y\}$ .

Voorbeeld 1.30 (De drie axioma’s nagaan)

Verklaar op $\R$ dat $x \mathbin{\mathcal{R}} y$ wanneer $x - y \in \Z$ . Reflexief: $x - x = 0 \in \Z$ . Symmetrisch: is $x - y \in \Z$ , dan is $y - x = -(x - y) \in \Z$ . Transitief: zijn $x - y \in \Z$ en $y - z \in \Z$ , dan is $x - z = (x - y) + (y - z) \in \Z$ (een som van gehele getallen). Dus $\mathcal R$ is een equivalentierelatie, en $\mathrm{cl}(x) = x + \Z = \{x + k : k \in \Z\}$ : elke klasse bevat precies één vertegenwoordiger in $\intco01$ , haar fractioneel deel. De relatie “ $\abs{x - y} \leq 1$ ” op $\R$ daarentegen is wel reflexief en symmetrisch, maar niet transitief ( $0 \mathbin{\mathcal R} 1$ en $1 \mathbin{\mathcal R} 2$ , terwijl $\abs{0 - 2} > 1$ ): nabijheid plant zich niet voort, en een partitie in klassen bestaat niet — een nuttig tegenvoorbeeld om bij de hand te houden wanneer het nagaan van de axioma’s routine begint te lijken.

Stelling 1.31 (Klassen vormen een partitie)

Zij $\mathcal{R}$ een equivalentierelatie op $E$ . Dan zijn de equivalentieklassen niet-leeg, twee aan twee disjunct of gelijk, en is hun vereniging $E$ : ze vormen een partitie van $E$ . Omgekeerd komt elke partitie van $E$ op deze manier van precies één equivalentierelatie (“in hetzelfde stuk liggen”).

Bewijs. Wegens reflexiviteit is $x \in \mathrm{cl}(x)$ , dus zijn de klassen niet-leeg en is hun vereniging $E$ . Stel $\mathrm{cl}(x) \cap \mathrm{cl}(y) \neq \emptyset$ , zeg dat $z$ in beide ligt. Dan is $x \mathbin{\mathcal{R}} z$ en $y \mathbin{\mathcal{R}} z$ , dus met symmetrie en transitiviteit $x \mathbin{\mathcal{R}} y$ . Voor elke $t \in \mathrm{cl}(y)$ geeft transitiviteit nu $t \in \mathrm{cl}(x)$ , en symmetrisch andersom: beide klassen zijn gelijk. Voor de omkering, zij $(E_i)_{i \in I}$ een partitie van $E$ en definieer $x \mathbin{\mathcal S} y$ als “een zeker stuk bevat zowel $x$ als $y$ ”. Reflexief: $x$ ligt in een stuk, dat $x$ dan tweemaal bevat. Symmetrisch: de voorwaarde is symmetrisch in $x$ en $y$ . Transitief: zijn $x, y \in E_i$ en $y, z \in E_j$ , dan is $y \in E_i \cap E_j$ , dus $E_i = E_j$ (verschillende stukken zijn disjunct) en delen $x$ en $z$ een stuk. De $\mathcal S$ -klasse van $x$ is precies het stuk dat $x$ bevat, zodat de klassen de gegeven stukken zijn. Ten slotte ligt de relatie vast door haar klassen: twee equivalentierelaties met dezelfde klassen verbinden dezelfde paren, want elk van beide verbindt $x$ en $y$ precies wanneer $y$ tot de klasse van $x$ behoort — waarmee de uniciteit bewezen is. ∎

Voorbeeld 1.32

Op $\Z$ is de congruentie modulo $n$ ( $x \equiv y \pmod n$ wanneer $n$ het getal $x - y$ deelt) een equivalentierelatie; haar klassen zijn de $n$ verzamelingen van gehele getallen met een gegeven rest bij deling door $n$ . Dit voorbeeld wordt de ring $\Z/n\Z$ in Hoofdstuk 7.

Definitie 1.33 (Ordeningsrelatie)

Een relatie $\preceq$ op $E$ heet een orde wanneer ze reflexief is, antisymmetrisch (uit $x \preceq y$ en $y \preceq x$ volgt $x = y$ ) en transitief. De orde is totaal wanneer elke twee elementen vergelijkbaar zijn, en anders partieel. Een element $M \in A \subseteq E$ is een grootste element van $A$ wanneer $a \preceq M$ voor alle $a \in A$ ; grootste (en kleinste) elementen zijn uniek zodra ze bestaan.

Voorbeeld 1.34

$(\R, \leq)$ is totaal geordend. $(\mathcal{P}(E), \subseteq)$ is partieel geordend zodra $E$ twee elementen heeft: $\{a\}$ en $\{b\}$ zijn onvergelijkbaar. De deelverzameling $A = \{\{a\}, \{b\}\}$ van $\mathcal{P}(\{a,b\})$ heeft geen grootste element, maar wel een bovengrens $\{a, b\}$ : het onderscheid tussen grootste elementen en bovengrenzen keert voor $\R$ terug in Hoofdstuk 10.

Voorbeeld 1.35 (Twee ordes op het rooster $\N^2$ )

Vergelijk paren natuurlijke getallen componentsgewijs: $(a, b) \preceq (a', b')$ wanneer $a \leq a'$ en $b \leq b'$ (de productorde). Dit is een orde — elk axioma wordt coördinaat voor coördinaat overgeërfd — maar een partiële: $(1, 3)$ en $(2, 0)$ zijn onvergelijkbaar. Vergelijk nu als in een woordenboek: $(a, b) \preceq_{\mathrm{lex}} (a', b')$ wanneer $a < a'$ , of $a = a'$ en $b \leq b'$ (de lexicografische orde). Transitiviteit vraagt een gevalsonderscheid, maar geldt, en nu zijn elke twee paren vergelijkbaar: de orde is totaal. Beide ordes rangschikken dezelfde verzameling verschillend — $(0, 100) \preceq_{\mathrm{lex}} (1, 0)$ terwijl de productorde er niets over zegt — een herinnering dat een orde een structuur is die je kiest en geen eigenschap van de verzameling. Lexicografisch vergelijken is bovendien de standaardtruc om verscheidene sorteercriteria tot één criterium samen te smeden.

Opmerking 1.36 (Tussenspel: grootte als bijectie)

Eén stil thema van dit hoofdstuk verdient de schijnwerper: bijecties zijn het wiskundige begrip van “even groot”. Voor eindige verzamelingen wordt dat de telkunde van Hoofdstuk 2, waarin elke formule stiekem een bijectie is; voor oneindige verzamelingen wordt het de weekendopgave hieronder, waar $\N$ , $\Q$ en $\R$ werkelijk verschillende groottes blijken te hebben. Datzelfde woordenboek duikt in dit volume nog tweemaal in verfijnde vorm op: rijen (Hoofdstuk 11) zijn niets anders dan afbeeldingen $\N \to \R$ , zodat uitspraken over rijen uitspraken over een verzameling afbeeldingen zijn; en de lineaire algebra meet vectorruimten niet met bijecties maar met lineaire bijecties, waarvan het bestaan door één enkel getal wordt geregeld: de dimensie (Hoofdstuk 19). Telkens als er een nieuwe “gelijkheid” opduikt — gelijkmachtigheid, isomorfie van groepen (Hoofdstuk 7), lineaire isomorfie — herhaalt zich het patroon van Stelling 1.24: gelijkheid is een inverteerbare afbeelding die de structuur respecteert.

Opmerking 1.37 (Waar dit hoofdstuk gebruikt wordt)

Overal — maar een paar plaatsen verdienen vermelding. De drie-kwantoren-gymnastiek van Voorbeeld 1.8 is het dagelijks brood van Hoofdstukken 11 en 13: elk limietbewijs is een spel tegen een willekeurige $\varepsilon$ . Equivalentieklassen keren terug als de congruentieklassen van $\Z/n\Z$ in Hoofdstuk 7, waar de partitie van Stelling 1.31 een eigen algebraïsche structuur krijgt. Ordeningsrelaties, bovengrenzen en kleinste bovengrenzen worden het axiomatische hart van $\R$ in Hoofdstuk 10. Injecties, surjecties en bijecties komen terug als de lineaire afbeeldingen van Hoofdstuk 20, waar injectiviteit aan één enkele vector te toetsen valt (de kern); en de weekendopgave hieronder maakt van het kale begrip bijectie een theorie van de groottes van oneindige verzamelingen, waarvan de conclusies (aftelbaarheid van $\Q$ , overaftelbaarheid van $\R$ ) weer opduiken in Hoofdstukken 10 en 12.

1.7 Oefeningen

Oefening 1.1 ★

Schrijf de negatie van elke uitspraak, zonder het woord “niet” te gebruiken:

$\forall x \in \R,\ \exists y \in \R,\ x + y > 0$ ;
$\exists x \in \R,\ \forall y \in \R,\ xy = 0$ ;
$\forall \varepsilon > 0,\ \exists \delta > 0,\ \forall x \in \R,\ \abs{x} \leq \delta \implies \abs{f(x)} \leq \varepsilon$ (voor een vaste afbeelding $f \colon \R \to \R$ ).

Beslis vervolgens of de uitspraken (1) en (2) waar zijn.

Oplossing

Oplossing van Oefening 1.1.

Negaties, waarbij $\lnot$ door elke kwantor geduwd wordt (Propositie 1.5) en de regel $\lnot(P \implies Q) \iff P \land \lnot Q$ gebruikt wordt:

$\exists x \in \R,\ \forall y \in \R,\ x + y \leq 0$ ;
$\forall x \in \R,\ \exists y \in \R,\ xy \neq 0$ ;
$\exists \varepsilon > 0,\ \forall \delta > 0,\ \exists x \in \R,\ \abs{x} \leq \delta \text{ en } \abs{f(x)} > \varepsilon$ .

Uitspraak (1) is waar: neem bij gegeven $x$ het getal $y = -x + 1$ ; dan is $x + y = 1 > 0$ . Uitspraak (2) is waar: $x = 0$ voldoet aan $xy = 0$ voor alle $y$ .

Oefening 1.2 ★

Zij $P, Q$ uitspraken. Bewijs met waarheidstabellen dat $\lnot(P \implies Q) \iff P \land (\lnot Q)$ , en leid daaruit de negatie af van: “als een functie afleidbaar is, dan is ze continu”.

Oplossing

Oplossing van Oefening 1.2.

Waarheidstabel, met W/O voor de vier gevallen $(P, Q)$ :

$P$	$Q$	$P \implies Q$	$\lnot(P \implies Q)$	$\lnot Q$	$P \land \lnot Q$
W	W	W	O	O	O
W	O	O	W	W	W
O	W	W	O	O	O
O	O	W	O	W	O

Kolom $4$ en kolom $6$ vallen samen, wat de equivalentie bewijst. De negatie van “als een functie afleidbaar is, dan is ze continu” luidt dus: “er bestaat een functie die afleidbaar is en niet continu” (een onware uitspraak overigens: de oorspronkelijke implicatie is waar, zie Hoofdstuk 14).

Oefening 1.3 ★

Bewijs via contrapositie: voor $x \in \R$ geldt, als $x^3 + x \geq 2$ , dan $x \geq 1$ . Bewijs vervolgens uit het ongerijmde dat er geen kleinste strikt positief reëel getal bestaat.

Oplossing

Oplossing van Oefening 1.3.

Contrapositie. Neem aan dat $x < 1$ . Dan is $x^3 < 1$ (de derdemachtsfunctie is stijgend) en $x < 1$ , dus $x^3 + x < 2$ . Daarmee is de contrapositie bewezen, en dus de uitspraak.

Ongerijmde. Stel dat $a > 0$ het kleinste strikt positieve reële getal is. Dan is $a/2$ strikt positief en $a/2 < a$ (want $a > 0$ ), in tegenspraak met de minimaliteit. Zo’n $a$ bestaat dus niet.

Oefening 1.4 ★

Bewijs met inductie dat voor alle $n \in \N$ :

$\sum_{k=0}^{n} 2^k = 2^{n+1} - 1$ ;
$4^n + 5$ deelbaar is door $3$ .

Oplossing

Oplossing van Oefening 1.4.

Basisgeval $n = 0$ : $2^0 = 1 = 2^1 - 1$ . Stap: neem de identiteit aan voor $n$ , dan is

$\sum_{k=0}^{n+1} 2^k = (2^{n+1} - 1) + 2^{n+1} = 2 \cdot 2^{n+1} - 1 = 2^{n+2} - 1 .$
Basisgeval $n = 0$ : $4^0 + 5 = 6 = 3 \times 2$ . Stap: is $4^n + 5 = 3m$ , dan is

$4^{n+1} + 5 = 4(4^n + 5) - 15 = 3(4m - 5),$

deelbaar door $3$ .

Oefening 1.5 ★

Zoek de fout in het volgende “bewijs” dat alle potloden dezelfde kleur hebben. Zij $P(n)$ : “in elke verzameling van $n$ potloden hebben alle potloden dezelfde kleur”. $P(1)$ is duidelijk. Neem $P(n)$ aan en beschouw $n+1$ potloden; laat je het laatste weg, dan delen de eerste $n$ hun kleur; laat je het eerste weg, dan delen de laatste $n$ hun kleur; dus delen alle $n+1$ hun kleur.

Oplossing

Oplossing van Oefening 1.5.

De inductiestap veronderstelt stilzwijgend dat de twee groepen (“de eerste $n$ ” en “de laatste $n$ ”) overlappen, zodat de gedeelde potloden de kleur van de ene groep naar de andere overdragen. Voor $n + 1 = 2$ zijn die groepen $\{$ eerste potlood $\}$ en $\{$ tweede potlood $\}$ : ze zijn disjunct, en het argument stort in. $P(1) \implies P(2)$ is dus nooit bewezen, en daarmee valt de hele inductie weg — ook al is $P(n) \implies P(n+1)$ voor elke $n \geq 2$ wel geldig.

Oefening 1.6 ★

Zij $A, B, C$ deelverzamelingen van $E$ . Bewijs:

$A \setminus B = A \cap \overline{B}$ ;
$(A \cup B) \setminus C = (A \setminus C) \cup (B \setminus C)$ ;
$A \subseteq B \iff A \cup B = B \iff A \cap B = A$ .

Oplossing

Oplossing van Oefening 1.6.

$x \in A \setminus B \iff x \in A \land x \notin B \iff x \in A \land x \in \overline{B} \iff x \in A \cap \overline{B}$ .
Met (1) en de distributiviteit (Propositie 1.18): $(A \cup B) \cap \overline{C} = (A \cap \overline{C}) \cup (B \cap \overline{C})$ .
Stel $A \subseteq B$ . Dan is $A \cup B \subseteq B$ (beide stukken liggen in $B$ ) en steeds $B \subseteq A \cup B$ , dus $A \cup B = B$ . Stel $A \cup B = B$ : steeds is $A \cap B \subseteq A$ , en uit $A \subseteq A \cup B = B$ volgt $A \subseteq A \cap B$ , dus $A \cap B = A$ . Stel $A \cap B = A$ : dan is $A = A \cap B \subseteq B$ . De drie voorwaarden zijn dus equivalent (we bewezen een kring van implicaties).

Oefening 1.7 ★★

Ga voor elke afbeelding met bewijs na of ze injectief, surjectief of bijectief is:

$f \colon \N \to \N$ , $n \mapsto n + 1$ ;
$g \colon \Z \to \Z$ , $n \mapsto n + 1$ ;
$h \colon \R \setminus \{1\} \to \R$ , $x \mapsto \frac{x+1}{x-1}$ .

Pas voor $h$ het codomein aan zodat ze bijectief wordt en bereken de inverse.

Oplossing

Oplossing van Oefening 1.7.

$f$ is injectief ( $n + 1 = m + 1 \implies n = m$ ) maar niet surjectief: $0$ heeft geen origineel in $\N$ .
$g$ is bijectief: $n \mapsto n - 1$ is een tweezijdige inverse op $\Z$ .
$h$ is injectief: uit $\frac{x+1}{x-1} = \frac{x'+1}{x'-1}$ volgt $(x+1)(x'-1) = (x'+1)(x-1)$ , dat wil zeggen $xx' - x + x' - 1 = xx' - x' + x - 1$ , dus $2x' = 2x$ . Surjectief op $\R$ is ze niet: $y = \frac{x+1}{x-1}$ oplossen geeft $x(y - 1) = y + 1$ , wat voor $y = 1$ geen oplossing heeft (de vergelijking luidt dan $0 = 2$ ). Met codomein $\R \setminus \{1\}$ levert dezelfde berekening het unieke origineel $x = \frac{y+1}{y-1}$ , zodat $h \colon \R \setminus \{1\} \to \R \setminus \{1\}$ bijectief is met $h^{-1}(y) = \frac{y+1}{y-1} = h(y)$ : $h$ is haar eigen inverse.

Oefening 1.8 ★★

Zij $f \colon E \to F$ , en zij $A, A' \subseteq E$ en $B, B' \subseteq F$ .

Bewijs $f^{-1}(B \cap B') = f^{-1}(B) \cap f^{-1}(B')$ en $f(A \cup A') = f(A) \cup f(A')$ .
Bewijs $f(A \cap A') \subseteq f(A) \cap f(A')$ en geef een voorbeeld waarin de inclusie strikt is.
Bewijs: $f$ is injectief dan en slechts dan als $f(A \cap A') = f(A) \cap f(A')$ voor alle $A, A'$ .

Oplossing

Oplossing van Oefening 1.8.

$x \in f^{-1}(B \cap B') \iff f(x) \in B \cap B' \iff f(x) \in B \land f(x) \in B' \iff x \in f^{-1}(B) \cap f^{-1}(B')$ . Voor beelden: $y \in f(A \cup A')$ precies wanneer $y = f(x)$ voor een zekere $x$ in $A$ of in $A'$ , dus precies wanneer $y \in f(A)$ of $y \in f(A')$ .
Is $y \in f(A \cap A')$ , dan is $y = f(x)$ met $x \in A$ en $x \in A'$ , dus $y \in f(A)$ en $y \in f(A')$ . Striktheid: neem $f \colon \R \to \R$ , $x \mapsto x^2$ , $A = \{-1\}$ , $A' = \{1\}$ : dan is $f(A \cap A') = f(\emptyset) = \emptyset$ , terwijl $f(A) \cap f(A') = \{1\}$ .
( $\Leftarrow$ ) Neem $A = \{x\}$ , $A' = \{x'\}$ met $x \neq x'$ : was $f(x) = f(x')$ , dan zou $f(A) \cap f(A') = \{f(x)\}$ zijn terwijl $f(A \cap A') = \emptyset$ , in tegenspraak met de veronderstelde gelijkheid; dus is $f$ injectief. ( $\Rightarrow$ ) Zij $f$ injectief en $y \in f(A) \cap f(A')$ : $y = f(x) = f(x')$ met $x \in A$ , $x' \in A'$ ; de injectiviteit geeft $x = x' \in A \cap A'$ , dus $y \in f(A \cap A')$ . Samen met (2) is dat de gelijkheid.

Oefening 1.9 ★★

Zij $f \colon E \to F$ en $g \colon F \to E$ met $g \circ f = \mathrm{id}_E$ . Bewijs dat $f$ injectief is en $g$ surjectief. Geef een voorbeeld waarin $f$ noch $g$ bijectief is.

Oplossing

Oplossing van Oefening 1.9.

$g \circ f = \mathrm{id}_E$ is injectief en surjectief, dus is volgens Propositie 1.26 (2) $f$ injectief en $g$ surjectief. Voorbeeld: $E = \N$ , $F = \Z$ , $f$ de inclusie $n \mapsto n$ , en $g \colon \Z \to \N$ met $g(n) = n$ voor $n \geq 0$ en $g(n) = 0$ voor $n < 0$ . Dan is $g(f(n)) = n$ voor alle $n \in \N$ , maar $f$ is niet surjectief en $g$ niet injectief.

Oefening 1.10 ★★

Definieer op $\R$ : $x \mathbin{\mathcal{R}} y \iff x^2 - y^2 = x - y$ . Bewijs dat $\mathcal{R}$ een equivalentierelatie is en beschrijf de equivalentieklasse van elk reëel getal $x$ . Welke klassen hebben precies één element?

Oplossing

Oplossing van Oefening 1.10.

$x^2 - y^2 = x - y \iff (x - y)(x + y) = x - y \iff (x - y)(x + y - 1) = 0 \iff y = x$ of $y = 1 - x$ . Reflexief: $y = x$ voldoet. Symmetrisch: de voorwaarde “ $y = x$ of $y = 1 - x$ ” is symmetrisch in $x$ en $y$ (uit $y = 1 - x$ volgt $x = 1 - y$ ). Transitief: stel $x \mathbin{\mathcal{R}} y$ en $y \mathbin{\mathcal{R}} z$ ; loop de vier gevallen af, en telkens is $z$ gelijk aan $x$ of aan $1 - x$ (uit $y = 1 - x$ en $z = 1 - y$ volgt bijvoorbeeld $z = x$ ). Dus is $\mathcal{R}$ een equivalentierelatie en $\mathrm{cl}(x) = \{x,\, 1 - x\}$ . Die klasse heeft precies één element wanneer $x = 1 - x$ , dat wil zeggen voor $x = \frac12$ .

Oefening 1.11 ★★★

(Cantor) Zij $E$ een verzameling. Bewijs dat er geen surjectie van $E$ op $\mathcal{P}(E)$ bestaat. Aanwijzing: beschouw bij een gegeven $f \colon E \to \mathcal{P}(E)$ de verzameling $D = \{x \in E : x \notin f(x)\}$ .

Oplossing

Oplossing van Oefening 1.11.

Zij $f \colon E \to \mathcal{P}(E)$ een willekeurige afbeelding en zet $D = \{x \in E : x \notin f(x)\} \in \mathcal{P}(E)$ . Stel $D = f(a)$ voor zekere $a \in E$ . Is $a \in D$ , dan is per definitie van $D$ juist $a \notin f(a) = D$ : tegenspraak. Is $a \notin D$ , dan is $a \notin f(a)$ , dus per definitie van $D$ juist $a \in D$ : tegenspraak. Dus ligt $D$ niet in het beeld van $f$ , en $f$ is niet surjectief. (In het bijzonder staat geen enkele verzameling in bijectie met haar machtsverzameling: er zijn “meer” deelverzamelingen van $\N$ dan gehele getallen.)

Oefening 1.12 ★★★

Zij $f \colon E \to F$ een afbeelding. Definieer $\Phi \colon \mathcal{P}(F) \to \mathcal{P}(E)$ door $\Phi(B) = f^{-1}(B)$ .

Bewijs dat $f$ surjectief is dan en slechts dan als $\Phi$ injectief is.
Bewijs dat $f$ injectief is dan en slechts dan als $\Phi$ surjectief is.

Oplossing

Oplossing van Oefening 1.12.

( $\Rightarrow$ ) Zij $f$ surjectief en $\Phi(B) = \Phi(B')$ . Kies bij $y \in B$ een $x$ met $f(x) = y$ ; dan is $x \in f^{-1}(B) = f^{-1}(B')$ , dus $y = f(x) \in B'$ . Bijgevolg is $B \subseteq B'$ , en symmetrisch $B' \subseteq B$ : $\Phi$ is injectief. ( $\Leftarrow$ ) Is $f$ niet surjectief, kies dan een $y_0 \in F$ buiten het beeld; dan is $f^{-1}(\{y_0\}) = \emptyset = f^{-1}(\emptyset)$ terwijl $\{y_0\} \neq \emptyset$ , dus $\Phi$ is niet injectief.
( $\Rightarrow$ ) Zij $f$ injectief en $A \subseteq E$ . Zet $B = f(A)$ ; dan is $f^{-1}(B) = \{x : f(x) \in f(A)\}$ , en de injectiviteit geeft $f(x) \in f(A) \iff x \in A$ , dus $\Phi(B) = A$ : $\Phi$ is surjectief. ( $\Leftarrow$ ) Is $f$ niet injectief, neem dan $x \neq x'$ met $f(x) = f(x')$ . Elk origineel $f^{-1}(B)$ bevat $x$ dan en slechts dan als het $x'$ bevat; bijgevolg is $\{x\}$ niet van de vorm $\Phi(B)$ , en $\Phi$ is niet surjectief.

1.8 Opgave: oneindigheden vergelijken

Probleem 1.1

Wanneer hebben twee verzamelingen “evenveel elementen”? Cantors antwoord — wanneer er een bijectie tussen beide bestaat — blijkt ook voor oneindige verzamelingen bruikbaar, en het splitst de oneindigheid in werkelijk verschillende groottes. Deze opgave bouwt het volledige gereedschap op uit de kale definities van dit hoofdstuk: de stelling van Cantor–Schröder–Bernstein (twee injecties maken samen een bijectie), de aftelbaarheid van $\Q$ , de overaftelbaarheid van $\R$ via het diagonaalargument, en Cantors verbluffende conclusie uit 1874: transcendente getallen bestaan, en wel in overweldigende hoeveelheid — zonder er ook maar één aan te wijzen. Schrijf overal, voor verzamelingen $E$ en $F$ , $E \preceq F$ wanneer er een injectie van $E$ in $F$ bestaat, en $E \approx F$ (“ $E$ en $F$ zijn gelijkmachtig”) wanneer er een bijectie van $E$ op $F$ bestaat.

Deel I — Het vocabulaire van de vergelijking.

Toon aan dat $\approx$ zich als een equivalentierelatie gedraagt: $E \approx E$ ; als $E \approx F$ , dan $F \approx E$ ; als $E \approx F$ en $F \approx G$ , dan $E \approx G$ . (Citeer nauwkeurig Stelling 1.24 en Propositie 1.26.)
Toon aan dat $\preceq$ transitief is, en dat een injectie $f \colon E \to F$ altijd $E \approx f(E)$ oplevert.
Zij $E \neq \emptyset$ . Toon aan dat $E \preceq F$ dan en slechts dan als er een surjectie van $F$ op $E$ bestaat.
Ga na dat $n \mapsto n + 1$ een bijectie is van $\N$ op $\N^* = \N \setminus \{0\}$ , en dat

$\sigma(n) = \frac n2 \ \ (n \text{ even}), \qquad \sigma(n) = -\frac{n+1}2 \ \ (n \text{ oneven})$

een bijectie is van $\N$ op $\Z$ . Een punt weglaten of naar de negatieve getallen verdubbelen verandert de grootte van $\N$ dus niet.

Deel II — De stelling van Cantor–Schröder–Bernstein. Zij $f \colon E \to F$ en $g \colon F \to E$ twee injecties. Definieer

C_0 = E \setminus g(F), \qquad C_{n+1} = g\bigl(f(C_n)\bigr) \ \ (n \in \N), \qquad C = \bigcup_{n \in \N} C_n,

en laat $h \colon E \to F$ elke $x \in C$ naar $f(x)$ sturen, en elke $x \notin C$ naar de unieke $y \in F$ met $g(y) = x$ .

Ga na dat $h$ goed gedefinieerd is: als $x \notin C$ , dan is $x \in g(F)$ , en het element $y$ met $g(y) = x$ is uniek.
Toon aan dat $g\bigl(f(C)\bigr) = \bigcup_{n \geq 1} C_n \subseteq C$ . (Beelden verwisselen met verenigingen: Oefening 1.8.)
Toon aan dat $h$ injectief is. (Drie gevallen; toon in het gemengde geval $x \in C$ , $x' \notin C$ aan dat $h(x) = h(x')$ zou dwingen dat $x' \in g(f(C)) \subseteq C$ .)
Toon aan dat $h$ surjectief is: onderscheid voor gegeven $y \in F$ de gevallen $g(y) \notin C$ en $g(y) \in C_n$ voor zekere $n \geq 1$ (waarom is $g(y) \in C_0$ onmogelijk?), en wijs in elk geval een origineel van $y$ aan.
Besluit met de stelling van Cantor–Schröder–Bernstein: als $E \preceq F$ en $F \preceq E$ , dan $E \approx F$ . Zeg in één zin wat deze uitspraak niet-triviaal maakt.
Twee toepassingen. (a) Toon aan dat $\intcc01 \approx \intoo01$ . (b) Toon aan dat $\varphi(p, q) = 2^p(2q + 1) - 1$ een bijectie van $\N \times \N$ op $\N$ definieert — injectiviteit met een pariteitsargument, surjectiviteit met sterke inductie (Stelling 1.12). Bijgevolg is $\N \times \N \approx \N$ : het rooster van gehele punten in het vlak is niet groter dan de lijn.

Deel III — Aftelbare verzamelingen. Noem een verzameling $E$ hoogstens aftelbaar wanneer $E \preceq \N$ , en aftelbaar wanneer $E \approx \N$ .

Toon aan dat elke oneindige deelverzameling $A \subseteq \N$ aftelbaar is. (Definieer $\varphi(n)$ recursief als het kleinste element van $A \setminus \{\varphi(0), \dots, \varphi(n-1)\}$ ; toon aan dat $\varphi$ strikt stijgend is, dat $\varphi(n) \geq n$ , en dat $\varphi$ elk element van $A$ bereikt.)
Leid af dat een verzameling hoogstens aftelbaar is dan en slechts dan als ze eindig of aftelbaar is, en merk op dat vraag 9 de kortere weg biedt: als $E \preceq \N$ en $\N \preceq E$ , dan is $E$ aftelbaar.
Toon aan dat met $E$ en $F$ ook $E \times F$ hoogstens aftelbaar is. Leid af dat $\Z \times \N^*$ aftelbaar is.
Toon aan dat $\Q$ aftelbaar is. (Injecteer $\Q$ in $\Z \times \N^*$ door elk rationaal getal onvereenvoudigbaar te schrijven met positieve noemer — de uniciteit van die schrijfwijze wordt bewezen in Hoofdstuk 6; pas dan vraag 12 toe.)
Toon aan dat een aftelbare vereniging van hoogstens aftelbare verzamelingen hoogstens aftelbaar is: is elke $E_n$ ( $n \in \N$ ) hoogstens aftelbaar, dan ook $\bigcup_{n \in \N} E_n$ . (Stuur $x$ naar het paar $(n, f_n(x))$ waarbij $n$ de kleinste index is met $x \in E_n$ .)
Toon aan dat de verzameling van eindige deelverzamelingen van $\N$ aftelbaar is. (Beeld een eindige deelverzameling $F$ af op $\sum_{i \in F} 2^i$ ; bewijs de injectiviteit door de grootste plaats te vergelijken waar twee eindige verzamelingen verschillen, met $\sum_{k=0}^{m-1} 2^k = 2^m - 1$ uit Oefening 1.4.)

Deel IV — Diagonalisatie. Noteer met $\{0,1\}^{\N}$ de verzameling van alle afbeeldingen $u \colon \N \to \{0, 1\}$ , dat wil zeggen de verzameling van binaire rijen.

Construeer een bijectie tussen $\mathcal{P}(\N)$ en $\{0,1\}^{\N}$ (indicatorfuncties).
(Het diagonaalargument) Zij $\Phi \colon \N \to \{0,1\}^{\N}$ een willekeurige afbeelding. Beschouw de rij $d$ gegeven door $d(n) = 1 - \Phi(n)(n)$ . Toon aan dat $d$ niet in het beeld van $\Phi$ ligt, en besluit dat $\{0,1\}^{\N}$ niet hoogstens aftelbaar is. Leg in één zin uit waarom dit, via vraag 17, precies de stelling van Cantor (Oefening 1.11) is voor $E = \N$ .
Neem aan — zoals van de middelbare school vertrouwd, en streng vastgelegd in Hoofdstuk 10 — dat elke $x \in \intco01$ precies één eigenlijke decimale ontwikkeling $x = 0.d_1 d_2 d_3\dots$ heeft (een ontwikkeling die niet op een oneindige staart van negens eindigt). Construeer bij een willekeurige rij $(x_n)_{n \geq 1}$ van elementen van $\intco01$ een $x \in \intco01$ met $x \neq x_n$ voor alle $n$ : kies als $n$ -de cijfer een $5$ wanneer het $n$ -de cijfer van $x_n$ van $5$ verschilt, en anders een $6$ . Verantwoord zorgvuldig dat $x$ eigenlijk is en elke $x_n$ ontwijkt, en besluit dat $\intco01$ niet hoogstens aftelbaar is.
Leid af dat $\R$ overaftelbaar is, en dat de verzameling $\R \setminus \Q$ van de irrationale getallen dat evenzeer is. In welke precieze zin zijn “de meeste” reële getallen irrationaal?

Deel V — Cantors stelling van 1874: transcendente getallen bestaan. Een reëel getal $x$ heet algebraïsch wanneer $P(x) = 0$ voor een zekere veelterm $P$ met gehele coëfficiënten die niet nul is, en transcendent in het andere geval. Neem voor dit deel aan — het wordt bewezen in Hoofdstuk 8 — dat een veelterm van graad $n$ die niet nul is hoogstens $n$ reële nulpunten heeft.

Toon aan dat elk rationaal getal algebraïsch is, en geef expliciet veeltermen met gehele coëfficiënten die $\sqrt 2$ en $\sqrt 2 + \sqrt 3$ annuleren.
Toon voor vaste $n \in \N$ aan dat de verzameling van veeltermen van graad hoogstens $n$ met gehele coëfficiënten aftelbaar is. (Injecteer haar in $\Z^{n+1}$ en pas inductie naar $n$ toe met vraag 13.)
Leid af dat de verzameling van alle veeltermen met gehele coëfficiënten aftelbaar is.
Bewijs Cantors stelling over de algebraïsche getallen: de verzameling $\mathcal{A}$ van de algebraïsche reële getallen is aftelbaar.
Besluit: transcendente reële getallen bestaan, en de verzameling van transcendente getallen is overaftelbaar. Maak vervolgens in enkele zinnen de balans op van de hele opgave: de keten $\N \approx \Z \approx \Q \approx \mathcal{A}$ , de strikte sprong naar $\R \approx$ (in wezen) $\mathcal{P}(\N)$ , waar elk gereedschap (Cantor–Schröder–Bernstein, aftelbare verenigingen, de diagonaal) beslissend was — en de filosofische klap van het bewijs dat er overaftelbaar veel transcendente getallen bestaan zonder er ook maar één te noemen. (Van een specifiek getal als $\pi$ bewijzen dat het transcendent is, is veel moeilijker en valt buiten dit volume.)

Oplossing

Oplossing van Probleem 1.1.

1. Reflexief: $\mathrm{id}_E$ is een bijectie van $E$ op zichzelf. Symmetrisch: is $f \colon E \to F$ bijectief, dan levert Stelling 1.24 de eveneens bijectieve $f^{-1} \colon F \to E$ . Transitief: zijn $f \colon E \to F$ en $g \colon F \to G$ bijecties, dan zegt Propositie 1.26 (1) dat $g \circ f \colon E \to G$ een bijectie is. (Het gaat hier slechts om iets dat zich “als” een equivalentierelatie gedraagt: de collectie van alle verzamelingen is zelf geen verzameling, wegens de paradoxen waarnaar Oefening 1.11 verwijst; het zijn de drie eigenschappen die tellen.)

2. Zijn $f \colon E \to F$ en $g \colon F \to G$ injectief, dan is $g \circ f$ injectief volgens Propositie 1.26 (1): $E \preceq G$ . Voor het tweede punt beperk je het codomein van $f$ tot haar beeld: de afbeelding $\tilde f \colon E \to f(E)$ , $x \mapsto f(x)$ , is per constructie van $f(E)$ surjectief en injectief omdat $f$ dat is, dus bijectief: $E \approx f(E)$ .

3. ( $\Rightarrow$ ) Zij $f \colon E \to F$ injectief en kies een vaste $a \in E$ ( $E \neq \emptyset$ ). Definieer $s \colon F \to E$ door: $s(y)$ is de unieke $x$ met $f(x) = y$ wanneer $y \in f(E)$ (uniek wegens de injectiviteit), en $s(y) = a$ in de andere gevallen. Voor elke $x \in E$ is $s(f(x)) = x$ , dus wordt elke $x$ bereikt: $s$ is surjectief. ( $\Leftarrow$ ) Zij $s \colon F \to E$ surjectief. Kies bij elke $x \in E$ één $y_x \in F$ met $s(y_x) = x$ en zet $u(x) = y_x$ . Uit $u(x) = u(x')$ volgt $x = s(u(x)) = s(u(x')) = x'$ : $u \colon E \to F$ is injectief.

4. $n \mapsto n + 1$ beeldt $\N$ af in $\N^*$ , is injectief ( $n + 1 = m + 1 \implies n = m$ ) en surjectief (elke $m \geq 1$ is $(m - 1) + 1$ met $m - 1 \in \N$ ). Voor $\sigma$ : ze stuurt de even getallen $0, 2, 4, \dots$ naar $0, 1, 2, \dots$ en de oneven getallen $1, 3, 5, \dots$ naar $-1, -2, -3, \dots$ Injectiviteit: de even argumenten landen in $\N$ ( $\sigma(n) = n/2 \geq 0$ ) en de oneven in de strikt negatieve gehele getallen ( $\sigma(n) = -(n+1)/2 \leq -1$ ), zodat een botsing binnen één pariteitsklasse moet plaatsvinden, waar $\sigma$ strikt monotoon is (uit $n/2 = m/2$ of $(n+1)/2 = (m+1)/2$ volgt $n = m$ ). Surjectiviteit: $k \geq 0$ is $\sigma(2k)$ ; $k \leq -1$ is $\sigma(-2k - 1)$ met $-2k - 1 \geq 1$ oneven. Dus $\N \approx \N^*$ en $\N \approx \Z$ .

5. Er is $C_0 = E \setminus g(F) \subseteq C$ , dus uit $x \notin C$ volgt $x \notin C_0$ , oftewel $x \in g(F)$ : een zekere $y \in F$ voldoet aan $g(y) = x$ . Geldt ook $g(y') = x$ , dan geeft de injectiviteit van $g$ dat $y' = y$ . De tweede clausule in de definitie van $h$ wijst dus een uniek, welbepaald element $g^{-1}(x)$ aan.

6. Beelden verwisselen met verenigingen (Oefening 1.8 (1), toegepast op $f$ en dan op $g$ ):

g\bigl(f(C)\bigr) = g\Bigl(f\Bigl(\bigcup_{n \in \N} C_n\Bigr)\Bigr) = \bigcup_{n \in \N} g\bigl(f(C_n)\bigr) = \bigcup_{n \in \N} C_{n+1} = \bigcup_{n \geq 1} C_n \subseteq C .

7. Zij $x \neq x'$ in $E$ . Liggen beide in $C$ , dan is $h(x) = f(x) \neq f(x') = h(x')$ wegens de injectiviteit van $f$ . Ligt geen van beide in $C$ , dan is $g(h(x)) = x \neq x' = g(h(x'))$ , dus $h(x) \neq h(x')$ . Is $x \in C$ en $x' \notin C$ (het gemengde geval, op verwisseling van namen na): stel $h(x) = h(x')$ , dat wil zeggen $f(x) = g^{-1}(x')$ . Toepassing van $g$ geeft $x' = g(f(x)) \in g(f(C))$ , en vraag 6 levert $x' \in C$ — tegenspraak. In alle gevallen is dus $h(x) \neq h(x')$ : $h$ is injectief.

8. Zij $y \in F$ . Geval 1: $g(y) \notin C$ . Dan is $h(g(y)) = g^{-1}(g(y)) = y$ : het element $g(y)$ is een origineel. Geval 2: $g(y) \in C$ , zeg $g(y) \in C_n$ . Omdat $g(y) \in g(F)$ , is $g(y) \notin C_0 = E \setminus g(F)$ , zodat $n \geq 1$ en $g(y) \in C_n = g(f(C_{n-1}))$ : er is een $x \in C_{n-1}$ met $g(y) = g(f(x))$ . De injectiviteit van $g$ geeft $y = f(x)$ , en $x \in C_{n-1} \subseteq C$ , dus $h(x) = f(x) = y$ . In beide gevallen wordt $y$ bereikt: $h$ is surjectief, en dus bijectief.

9. Zijn $E \preceq F$ en $F \preceq E$ , kies dan injecties $f \colon E \to F$ en $g \colon F \to E$ ; de vragen 5–8 bouwen een bijectie $h \colon E \to F$ , dus $E \approx F$ . De uitspraak is niet-triviaal omdat de twee gegeven injecties niets met elkaar te maken hebben — geen van beide hoeft surjectief te zijn, en geen enkele naïeve formule in $f$ en $g$ definieert een afbeelding: de hele inhoud zit in de partitie van $E$ in het gebied $C$ (waar je $f$ overneemt) en zijn complement (waar je $g$ achterwaarts doorloopt).

10. (a) De inclusie $\intoo01 \to \intcc01$ is injectief; en $x \mapsto \frac{x + 1}3$ beeldt $\intcc01$ injectief af in $\intcc{\frac13}{\frac23} \subseteq \intoo01$ (ze is affien met richtingscoëfficiënt ongelijk aan nul). Met vraag 9 volgt $\intcc01 \approx \intoo01$ — een bijectie die bijzonder onaangenaam expliciet op te schrijven is. (b) Injectiviteit. Stel $2^p(2q + 1) = 2^{p'}(2q' + 1)$ met bijvoorbeeld $p \leq p'$ . Deling door $2^p$ geeft $2q + 1 = 2^{p' - p}(2q' + 1)$ . Was $p' > p$ , dan zou het rechterlid even en het linkerlid oneven zijn — onmogelijk; dus $p = p'$ , waarna $2q + 1 = 2q' + 1$ en $q = q'$ . Surjectiviteit. We tonen met sterke inductie aan dat elk geheel getal $m \geq 1$ van de vorm $2^p(2q + 1)$ is. Voor $m = 1$ : $p = q = 0$ . Zij $m \geq 1$ en neem de bewering aan voor alle getallen uit $\intint1m$ . Is $m + 1$ oneven, dan is $m + 1 = 2q + 1$ met $p = 0$ . Is $m + 1$ even, dan is $m + 1 = 2m'$ met $1 \leq m' \leq m$ ; volgens de hypothese is $m' = 2^p(2q + 1)$ , dus $m + 1 = 2^{p+1}(2q + 1)$ . Bijgevolg bereikt $\varphi(p, q) = 2^p(2q + 1) - 1$ elke $n \in \N$ , en is $\varphi$ een bijectie $\N \times \N \to \N$ .

11. Omdat $A$ oneindig is, is $A \setminus \{\varphi(0), \dots, \varphi(n - 1)\}$ nooit leeg, en de eigenschap van het kleinste element van $\N$ (gebruikt in het bewijs van Stelling 1.12) maakt de recursieve definitie geoorloofd. Strikt stijgend: $\varphi(n + 1)$ behoort tot $A \setminus \{\varphi(0), \dots, \varphi(n)\} \subseteq A \setminus \{\varphi(0), \dots, \varphi(n - 1)\}$ , waarvan het minimum $\varphi(n)$ is; dus $\varphi(n + 1) \geq \varphi(n)$ , en gelijkheid is uitgesloten, zodat $\varphi(n+1) > \varphi(n)$ . $\varphi(n) \geq n$ : met inductie, want $\varphi(0) \geq 0$ en $\varphi(n + 1) \geq \varphi(n) + 1 \geq n + 1$ . Injectiviteit volgt uit de strikte monotonie. Surjectiviteit op $A$ : stel dat een zekere $a \in A$ nooit bereikt wordt. Omdat $\varphi(a + 1) \geq a + 1 > a$ , is de verzameling van de $n$ met $\varphi(n) > a$ niet leeg; zij $n$ haar kleinste element. Voor elke $k < n$ is $\varphi(k) \leq a$ , en dus $\varphi(k) < a$ ( $a$ wordt niet bereikt). Dan ligt $a$ in $A \setminus \{\varphi(0), \dots, \varphi(n - 1)\}$ met $a < \varphi(n)$ , in tegenspraak met de minimaliteit die $\varphi(n)$ definieert. Dus is $\varphi$ een bijectie $\N \to A$ en is $A$ aftelbaar.

12. Zij $E \preceq \N$ via een injectie $f$ ; dan is $E \approx f(E)$ (vraag 2). Is $f(E)$ eindig, dan is $E$ eindig; is $f(E)$ oneindig, dan geeft vraag 11 dat $f(E) \approx \N$ , dus $E \approx \N$ wegens de transitiviteit (vraag 1). Omgekeerd injecteren eindige en aftelbare verzamelingen uiteraard in $\N$ . De kortere weg: uit $E \preceq \N$ en $\N \preceq E$ volgt $E \approx \N$ rechtstreeks met Cantor–Schröder–Bernstein — zonder enig opsommingsargument.

13. Zij $f \colon E \to \N$ en $g \colon F \to \N$ injecties. Dan is $(x, y) \mapsto \varphi\bigl(f(x), g(y)\bigr)$ een injectie $E \times F \to \N$ : vallen de beelden samen, dan geeft de injectiviteit van $\varphi$ (vraag 10) dat $f(x) = f(x')$ en $g(y) = g(y')$ , en dus $x = x'$ , $y = y'$ . Voor $\Z \times \N^*$ : beide factoren zijn aftelbaar (vraag 4), dus $\Z \times \N^* \preceq \N$ ; de verzameling is oneindig (ze bevat $\{0\} \times \N^*$ ), en dus aftelbaar volgens vraag 12.

14. Elk rationaal getal $r$ heeft precies één schrijfwijze $r = p/q$ met $p \in \Z$ , $q \in \N^*$ en de breuk onvereenvoudigbaar (de uniciteit wordt bewezen in Hoofdstuk 6; voor $r = 0$ neem je $0/1$ ). De afbeelding $r \mapsto (p, q)$ is dan injectief: het paar legt $r = p/q$ vast. Bijgevolg is $\Q \preceq \Z \times \N^* \preceq \N$ volgens vraag 13. Omdat $\N \subseteq \Q$ ook $\N \preceq \Q$ geeft, toont vraag 12 (of rechtstreeks Cantor–Schröder–Bernstein) dat $\Q \approx \N$ : de rationale getallen zijn aftelbaar.

15. Kies bij elke $n$ een injectie $f_n \colon E_n \to \N$ . Zij voor $x \in \bigcup_n E_n$ het getal $n(x)$ de kleinste $n$ met $x \in E_n$ , en zet $u(x) = \varphi\bigl(n(x), f_{n(x)}(x)\bigr) \in \N$ . Uit $u(x) = u(x')$ geeft de injectiviteit van $\varphi$ dat $n(x) = n(x') = n$ en $f_n(x) = f_n(x')$ , dus $x = x'$ wegens de injectiviteit van $f_n$ . De vereniging injecteert dus in $\N$ : ze is hoogstens aftelbaar.

16. Zet $\Psi(F) = \sum_{i \in F} 2^i$ voor eindige $F \subseteq \N$ (met $\Psi(\emptyset) = 0$ ). Stel $F \neq F'$ en zij $m$ het grootste element waarop ze verschillen, zeg $m \in F \setminus F'$ (verwissel zo nodig de namen). Elementen $> m$ behoren tot beide of tot geen van beide en dragen dus even veel bij aan beide sommen; vergelijken we de bijdragen van de elementen $\leq m$ :

\sum_{i \in F,\, i \leq m} 2^i \geq 2^m > 2^m - 1 = \sum_{k=0}^{m-1} 2^k \geq \sum_{i \in F',\, i \leq m} 2^i ,

met de meetkundige som uit Oefening 1.4. Bijgevolg is $\Psi(F) \neq \Psi(F')$ : $\Psi$ is injectief en de verzameling van eindige deelverzamelingen van $\N$ is hoogstens aftelbaar; ze is oneindig (ze bevat alle singletons) en dus aftelbaar.

17. Stuur $A \subseteq \N$ naar haar indicator $\mathbf 1_A \colon \N \to \{0,1\}$ , met $\mathbf 1_A(n) = 1$ als $n \in A$ en $0$ in het andere geval; stuur $u \in \{0,1\}^{\N}$ naar $A_u = \{n \in \N : u(n) = 1\}$ . Beide afbeeldingen zijn elkaars inverse: $A_{\mathbf 1_A} = A$ en $\mathbf 1_{A_u} = u$ (ga de waarde in elke $n$ na). Volgens Stelling 1.24 is elk van beide een bijectie: $\mathcal{P}(\N) \approx \{0,1\}^{\N}$ .

18. Voor elke $n$ is $d(n) = 1 - \Phi(n)(n) \neq \Phi(n)(n)$ , zodat de rijen $d$ en $\Phi(n)$ op de index $n$ verschillen: $d \neq \Phi(n)$ . Geen enkele $\Phi$ is dus surjectief, en volgens vraag 3 bestaat er evenmin een injectie $\{0,1\}^{\N} \to \N$ : $\{0,1\}^{\N}$ is niet hoogstens aftelbaar. Via het woordenboek van vraag 17 is een afbeelding $\Phi \colon \N \to \{0,1\}^{\N}$ een afbeelding $f \colon \N \to \mathcal{P}(\N)$ , en $d$ komt overeen met de verzameling $D = \{n : n \notin f(n)\}$ (immers $d(n) = 1 \iff \Phi(n)(n) = 0 \iff n \notin f(n)$ ): het diagonaalargument is Cantors bewijs van Oefening 1.11 voor $E = \N$ .

19. Schrijf $x_n = 0.d_1(n)\,d_2(n)\,d_3(n)\dots$ in eigenlijke vorm en definieer $\delta_n = 5$ als $d_n(n) \neq 5$ en $\delta_n = 6$ als $d_n(n) = 5$ , en zet $x = 0.\delta_1\delta_2\delta_3\dots$ Deze ontwikkeling gebruikt alleen de cijfers $5$ en $6$ en eindigt dus niet op louter negens: ze is de eigenlijke ontwikkeling van een reëel getal $x \in \intco01$ . Voor elke $n$ verschillen de $n$ -de cijfers van $x$ en $x_n$ ( $\delta_n \neq d_n(n)$ per constructie); omdat eigenlijke ontwikkelingen uniek zijn, is $x \neq x_n$ . Geen enkele rij put $\intco01$ dus uit: opnieuw met vraag 3 is $\intco01$ niet hoogstens aftelbaar.

20. Er geldt $\intco01 \subseteq \R$ , dus een injectie $\R \to \N$ zou tot een injectie op $\intco01$ beperken, in tegenspraak met vraag 19: $\R$ is overaftelbaar. Was $\R \setminus \Q$ hoogstens aftelbaar, dan zou $\R = \Q \cup (\R \setminus \Q)$ een vereniging van twee hoogstens aftelbare verzamelingen zijn en dus hoogstens aftelbaar volgens vraag 15 (neem $E_0 = \Q$ en $E_n = \R \setminus \Q$ voor $n \geq 1$ ) — tegenspraak. De irrationale getallen zijn dus overaftelbaar. Preciezer: binnen $\R$ vormen de rationale getallen een aftelbare verzameling terwijl hun complement overaftelbaar is; geen enkele bijectie kan $\R \setminus \Q$ ooit met $\Q$ laten samenvallen — er zijn strikt “meer” irrationale dan rationale getallen, ook al zijn beide oneindig en beide dicht.

21. $p/q$ (met $q \neq 0$ ) is een nulpunt van $qX - p$ , een veelterm met gehele coëfficiënten die niet nul is. Verder is $\sqrt 2$ een nulpunt van $X^2 - 2$ . Voor $x = \sqrt 2 + \sqrt 3$ : $x^2 = 5 + 2\sqrt 6$ , dus $x^2 - 5 = 2\sqrt 6$ en $(x^2 - 5)^2 = 24$ , oftewel

x^4 - 10x^2 + 1 = 0 :

$\sqrt 2 + \sqrt 3$ is een nulpunt van $X^4 - 10X^2 + 1$ .

22. Beeld $P = a_0 + a_1X + \dots + a_nX^n$ (graad $\leq n$ , gehele coëfficiënten) af op $(a_0, \dots, a_n) \in \Z^{n+1}$ : dit is injectief, want een veelterm ligt vast door zijn coëfficiënten. Met inductie naar $n$ : $\Z^1 = \Z$ is aftelbaar (vraag 4), en $\Z^{n+2} \approx \Z^{n+1} \times \Z$ is hoogstens aftelbaar volgens vraag 13. Elke verzameling van gehele veeltermen van begrensde graad is dus hoogstens aftelbaar; ze is oneindig (ze bevat de constanten) en dus aftelbaar volgens vraag 12.

23. De verzameling van alle gehele veeltermen is

\bigcup_{n \in \N} \{P : \deg P \leq n,\ P \text{ heeft gehele coëfficiënten}\},

een aftelbare vereniging van aftelbare verzamelingen: hoogstens aftelbaar volgens vraag 15, oneindig, en dus aftelbaar.

24. Voor elke gehele veelterm $P$ die niet nul is, is de nulpuntenverzameling $R_P = \{x \in \R : P(x) = 0\}$ eindig (hoogstens $\deg P$ elementen, aangenomen). Volgens vraag 23 kunnen de gehele veeltermen die niet nul zijn opgesomd worden als $P_0, P_1, P_2, \dots$ ; dan is $\mathcal{A} = \bigcup_{n \in \N} R_{P_n}$ een aftelbare vereniging van eindige (dus hoogstens aftelbare) verzamelingen: hoogstens aftelbaar volgens vraag 15. Ze bevat $\Q$ (vraag 21) en is dus oneindig: $\mathcal{A}$ is aftelbaar.

25. Was $\R \setminus \mathcal{A}$ hoogstens aftelbaar, dan zou $\R = \mathcal{A} \cup (\R \setminus \mathcal{A})$ hoogstens aftelbaar zijn (vraag 15), in tegenspraak met vraag 20. Er bestaan dus transcendente getallen, en ze vormen zelfs een overaftelbare verzameling, terwijl de algebraïsche getallen — waaronder elk getal dat uit gehele getallen met worteltrekkingen gebouwd is — slechts een aftelbaar skelet binnen $\R$ vormen. Overzicht van de architectuur: de vragen 1–3 leggen de vergelijkingstaal vast; Cantor–Schröder–Bernstein (vragen 5–9) laat toe gelijkmachtigheid te bewijzen met twee makkelijke injecties in plaats van één slimme bijectie, en werd gebruikt voor $\intcc01 \approx \intoo01$ , voor $\Q$ en overal in Deel V; de koppelingsbijectie (vraag 10) dreef de producten en de aftelbare verenigingen aan (vragen 13 en 15), die op hun beurt $\Q$ , de gehele veeltermen en $\mathcal{A}$ aandreven; het diagonaalargument (vragen 18–19) leverde de ene strikte ongelijkheid $\N \prec \R$ die het hele verhaal niet-triviaal maakt. Cantors conclusie is filosofisch opzienbarend: het bewijs wijst geen enkel transcendent getal aan en toont toch dat in de zin van gelijkmachtigheid bijna elk reëel getal transcendent is. Van één specifiek getal — $\pi$ of $\eu$ — de transcendentie aantonen vergde volstrekt andere wiskunde en nog decennia werk.

Begrippen gedefinieerd in dit hoofdstuk

Bekijk alle 395 begrippen in de begrippenlijst