Universitaire wiskunde — Bachelor jaar 1 · Bachelor Year 1

1Logica, verzamelingen en afbeeldingen

Tot nu toe werden bewijzen geleverd met een informeel maar eerlijk idee van wat “bewijzen” betekent. Dit eerste hoofdstuk van de universitaire wiskunde maakt de spelregels expliciet: wat een wiskundige uitspraak is, hoe de connectieven en kwantoren uitspraken combineren, welke zetten toegelaten zijn in een bewijs — en bouwt vervolgens, op deze basis, de twee universele talen van de wiskunde op: verzamelingen en afbeeldingen.

1.1 Uitspraken en connectieven

Definitie 1.1 (Uitspraak, connectieven)

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

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 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

De waarheidstabel van $P \implies Q$ verdient een pauze: wanneer $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 wat er gebeurt wanneer haar hypothese faalt.

Propositie 1.3 (Rekenregels voor uitspraken)

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

$\lnot(\lnot P) \iff P$ ;
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)$ , 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 wordt gecontroleerd door waarheidstabellen te vergelijken: twee samengestelde uitspraken opgebouwd uit $P$ , $Q$ , $R$ zijn equivalent precies wanneer ze in elk van de (vier of acht) gevallen dezelfde waarheidswaarde aannemen. Laten we één tabel volledig weergeven, 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

Kolommen $4$ en $7$ vallen samen, wat de wet bewijst. Voor de contrapositie is een verbale afkorting sneller: $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), d.w.z. ( $Q$ onwaar, $P$ waar) — hetzelfde ene geval, dus de twee implicaties hebben identieke tabellen. De overige regels worden op dezelfde manier gecontroleerd; merk op dat (3) elke implicatie herleidt tot een disjunctie, zodat (2) mechanisch de negatieregel $\lnot(P \implies Q) \iff P \land (\lnot Q)$ voortbrengt: om een implicatie tegen te spreken moet men een geval aanwijzen waar 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$ , $P(x)$ ”) is waar wanneer elk element van $E$ voldoet aan $P$ ;
$\exists x \in E,\ P(x)$ (“er bestaat $x$ in $E$ zodat $P(x)$ ”) is waar wanneer minstens één element van $E$ voldoet aan $P$ .

Men schrijft $\exists!$ voor “er bestaat een unieke”.

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. Laten we de eerste equivalentie in beide richtingen beargumenteren; de tweede is symmetrisch. Als $\forall x \in E,\ P(x)$ onwaar is, 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 $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$ ” betekent dat de verzameling $\{x : P(x)\}$ leeg is, d.w.z. elke $x$ ligt in haar complement $A$ . In cascade toegepast op een geneste rij kwantoren geven de twee regels de mechanische procedure van Voorbeeld 1.8: de negatie loopt van links naar rechts, verandert elke $\forall$ in $\exists$ en elke $\exists$ in $\forall$ , en negeert ten slotte het binnenste predicaat. ∎

Voorbeeld 1.6 (Alledaagse wiskundige zinnen negeren)

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, via Propositie 1.5 plus 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” $\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, een of ander punt overtreft haar. Het inzicht: een correcte negatie bevat nooit “niet” toegepast op een gekwantificeerd blok — het is een nieuwe positieve uitspraak, waarin de rollen zijn omgewisseld: men produceert nu de getuigen die men voorheen ontving.

Voorbeeld 1.7 (Volgorde van 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ëlen).}

In de eerste uitspraak mag $y$ afhangen van $x$ ; in de tweede moet één enkele $y$ werken voor alle $x$ . Twee identieke kwantoren daarentegen commuteren altijd.

Voorbeeld 1.8 (Een definitie met drie kwantoren lezen)

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

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

Haar negatie, via Propositie 1.5 driemaal toegepast, is

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

Zulke zinnen mechanisch kunnen negeren, zonder na te denken over wat ze betekenen, is een echte vaardigheid: ze scheidt het logische werk van het wiskundige werk.

1.3 Bewijstechnieken

Methode 1.9 (De standaard bewijspatronen)

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 via Propositie 1.3 (4);
via een tegenspraak: neem aan dat de uitspraak onwaar is, leid een tegenspraak af;
een equivalentie: bewijs beide implicaties afzonderlijk (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: geef een getuige aan, of bewijs het bestaan onrechtstreeks;
via inductie: zie Stelling 1.12.

Bij het bewijzen van een uitspraak over een goedgekozen maar willekeurig element mag men het element nooit extra eigenschappen geven: “zij $x \in \R$ ” gevolgd door “aangezien $x > 0$ …” bewijst niets over negatieve $x$ .

Opmerking 1.10 (Veelvoorkomende valkuilen in bewijzen)

Vier klassieke vallen, alle waard om eens te benoemen.

Omgekeerde in plaats van contrapositie. $Q \implies P$ is niet equivalent met $P \implies Q$ ; enkel $\lnot Q \implies \lnot P$ is dat. “Als het regent, is de straat nat” geeft niet het recht om uit een natte straat regen te besluiten.
Een equivalentie bewijzen met één implicatie. Een “desda”-bewering bestaat uit twee stellingen; kondig aan welke richting bewezen wordt, en bewijs beide. Ketens van $\iff$ zijn enkel toegelaten als elke schakel echt omkeerbaar is — een vergelijking kwadrateren, bijvoorbeeld, is dat niet.
Achterstevoren bewijzen. Vertrekken van de gewenste conclusie en een ware uitspraak afleiden bewijst niets (uit $-1 = 1$ leidt men door kwadrateren het ware $1 = 1$ af). Een berekening mag achterstevoren ontdekt worden, maar ze moet voorwaarts opgeschreven worden, of met expliciete equivalenties.
Vaste getuige versus willekeurig element. Om $\exists x,\ P(x)$ te bewijzen mag men één slim gekozen $x$ aanwijzen; om $\forall x,\ P(x)$ te bewijzen moet de gekozen $x$ willekeurig blijven. De twee vermengen — een universele bewering nagaan op een voorbeeld — is de meest voorkomende fout in het werk van beginners.

Voorbeeld 1.11 (Contrapositie en tegenspraak aan het werk)

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

$\sqrt 2$ is irrationaal. Via tegenspraak: veronderstel $\sqrt 2 = p/q$ met $p, q \in \N^*$ en de breuk vereenvoudigd. Dan is $p^2 = 2q^2$ even, dus $p$ is even (vorig punt), $p = 2r$ ; dan is $q^2 = 2r^2$ even, dus $q$ is even — in tegenspraak met de vereenvoudigde vorm.

Stelling 1.12 (Inductie)

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

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

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

Sterke inductie: conclusie onveranderd als (2) vervangen wordt door: voor alle $n$ , $\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). Inderdaad, veronderstel dat (1) en (2) gelden en zij $A = \{n \in \N : P(n) \text{ onwaar}\}$ . Als $A \neq \emptyset$ , heeft ze een kleinste element $m$ ; $m \neq 0$ via (1); dan is $m - 1 \notin A$ , dus $P(m-1)$ geldt, en (2) geeft $P(m)$ — tegenspraak. Dus $A = \emptyset$ . Voor sterke inductie past men hetzelfde argument toe: $P(0), \dots, P(m-1)$ gelden allemaal aangezien $m$ het kleinste element van $A$ is. ∎

Voorbeeld 1.13 (Uniek bestaan bewijzen)

Een uitspraak $\exists!\,x,\ P(x)$ bestaat uit twee uitspraken, afzonderlijk bewezen: bestaan (geef of construeer een $x_0$ met $P(x_0)$ ) en uniciteit (neem $P(x)$ en $P(x')$ aan, leid $x = x'$ af). Voorbeeld: er is een unieke reële $x$ met $x^3 + x = 2$ . Bestaan: $x_0 = 1$ werkt, aangezien $1 + 1 = 2$ . Uniciteit: als $x^3 + x = x'^3 + x'$ , dan

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$ ), dus $x = x'$ . Merk de taakverdeling op: bestaan gebruikte een gelukkige gok, uniciteit gebruikte algebra die geldig is voor willekeurige oplossingen — geen van beide argumenten doet het werk van het andere, en de tweede helft vergeten is een blijvende verleiding zodra een oplossing gevonden is.

Voorbeeld 1.14

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

\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 priem is een geheel getal $\geq 2$ waarvan de enige delers $\geq 1$ gelijk zijn aan $1$ en zichzelf; priemgetallen worden om hun eigen belang bestudeerd in Hoofdstuk 6). Gewone inductie is hier machteloos: 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. Als $n + 1$ priem is, klaar. Anders is $n + 1 = ab$ met $2 \leq a, b \leq n$ ; via de sterke hypothese zijn zowel $a$ als $b$ producten van priemgetallen, dus ook $n + 1$ . Het inzicht: sterke inductie is het juiste gereedschap wanneer de “reden” voor $P(n+1)$ op een of andere onvoorspelbare eerdere rang leeft, niet op rang $n$ .

1.4 Verzamelingen

Definitie 1.16 (Verzamelingbewerkingen)

We nemen het begrip verzameling en de lidmaatschapsrelatie $x \in E$ als primitief. 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$ ;
unie $A \cup B$ , doorsnede $A \cap B$ , verschil $A \setminus B = \{x \in A : x \notin B\}$ , 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\}$ :

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

vier elementen — en merk de typediscipline op: $a \in E$ maar $\{a\} \in \mathcal P(E)$ ; de uitspraken $a \in \mathcal P(E)$ en $\{a\} \subseteq \mathcal P(E)$ zijn beide onwaar zoals geschreven (de tweede zou vereisen dat $a$ een deelverzameling van $E$ is). Itererend vanaf niets: $\mathcal P(\emptyset) = \{\emptyset\}$ heeft één element, $\mathcal P(\mathcal P(\emptyset)) = \{\emptyset, \{\emptyset\}\}$ heeft er twee, de volgende heeft er 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 in oefeningen zoals Oefeningen 1.11 en 1.12.

Propositie 1.18 (Verzamelingalgebra)

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

$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 van Propositie 1.3 via het woordenboek ( $\in A$ of niet) $\leftrightarrow$ (uitspraak waar of onwaar): b.v. $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 voorbeeld, de eerste distributiviteitswet volledig:

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),

via de distributiviteit van Propositie 1.3 (6), en de laatste uitspraak leest als $x \in (A \cap B) \cup (A \cap C)$ . Elke verzamelingidentiteit van deze soort is bewijsbaar met deze ene mechanische vertaling — daarom hoeft geen enkele ervan uit het hoofd geleerd te worden. ∎

Methode 1.19 (Verzamelinggelijkheden bewijzen)

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

De wetten van De Morgan in beelden: het gearceerde gebied links is A ∪ B = A ∩ B (alles buiten beide schijven); rechts, A ∩ B = A ∪ B (alles behalve de lensvormige overlap). Een diagram is geen bewijs, maar het maakt het element-najagende bewijs van onmogelijk om verkeerd te onthouden. — De wetten van De Morgan in beelden: het gearceerde gebied links is $\overline{A \cup B} = \overline A \cap \overline B$ (alles buiten beide schijven); rechts, $\overline{A \cap B} = \overline A \cup \overline B$ (alles behalve de lensvormige overlap). Een diagram is geen bewijs, maar het maakt het element-najagende bewijs van Propositie 1.18 onmogelijk om verkeerd te onthouden.

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$ :

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

zijn het directe 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 gedefinieerd voor elke $f$ . Originelen gedragen zich beter dan beelden: $f^{-1}$ bewaart unies, 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:

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 worden niet berekend uit de eindpunten alleen. Voor het tweede: $1 \leq x^2 \leq 4 \iff 1 \leq \abs x \leq 2$ , wat in twee stukken uiteenvalt. Het derde illustreert dat een origineel leeg kan zijn — $f^{-1}(B)$ heeft altijd zin, hoe klein de doorsnede van $B$ met het beeld ook is. Merk ten slotte op dit voorbeeld het striktheidsverschijnsel van bovenstaande opmerking: met $A = \intcc{-1}0$ en $A' = \intcc01$ heeft men $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$ is:

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 het beide is, d.w.z. elke $y \in F$ heeft precies één origineel.

Stelling 1.24 (Inverse afbeelding)

Een afbeelding $f \colon E \to F$ is bijectief als en slechts 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 $f^{-1}$ geschreven en de inverse van $f$ genoemd, en $f^{-1}$ is zelf bijectief met $(f^{-1})^{-1} = f$ .

Bewijs. ( $\Rightarrow$ ) Als $f$ bijectief is, heeft elke $y \in F$ een uniek origineel; definieer $g(y)$ als dat origineel. Dan is $f(g(y)) = y$ per constructie, en $g(f(x)) = x$ omdat $x$ het origineel van $f(x)$ is.

( $\Leftarrow$ ) Veronderstel dat zo’n $g$ bestaat. Als $f(x) = f(x')$ , levert het toepassen van $g$ op $x = x'$ : $f$ is injectief. Voor $y \in F$ voldoet $x = g(y)$ aan $f(x) = y$ : $f$ is surjectief.

Uniciteit: als $g$ en $h$ beide werken, 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$ , dus $g = f^{-1}$ is bijectief met inverse $f$ . ∎

Voorbeeld 1.25 (Een inverse berekenen in de praktijk)

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

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

waarbij elke stap omkeerbaar is op de aangekondigde domeinen. De berekening levert alles in één keer: voor elke $y$ in het codomein is er 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 let op de equivalenties” is tegelijk het bestaansbewijs, het uniciteitsbewijs en de formule — maar het werkt enkel als het codomein correct werd 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$ .

Als $f$ en $g$ injectief zijn (resp. surjectief, bijectief), dan ook $g \circ f$ ; en dan geldt $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ in het bijectieve geval.
Als $g \circ f$ injectief is, dan is $f$ injectief. Als $g \circ f$ surjectief is, dan is $g$ surjectief.

Bewijs. (1) Als $g(f(x)) = g(f(x'))$ , geeft injectiviteit van $g$ dat $f(x) = f(x')$ , dan geeft injectiviteit van $f$ dat $x = x'$ . Als $z \in G$ , geeft surjectiviteit van $g$ een $y$ met $g(y) = z$ , dan geeft surjectiviteit van $f$ een $x$ met $f(x) = y$ , dus $g(f(x)) = z$ . In het bijectieve geval controleert men rechtstreeks dat $f^{-1} \circ g^{-1}$ een tweezijdige inverse van $g \circ f$ is, en uniciteit in Stelling 1.24 besluit.

(2) Als $f(x) = f(x')$ dan $g(f(x)) = g(f(x'))$ , en injectiviteit van $g \circ f$ geeft $x = x'$ . Als $z \in G$ , geeft 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) kan men de conclusies niet versterken: $g \circ f$ bijectief dwingt niet af dat $f$ surjectief of $g$ injectief is. 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, maar $f$ mist het element $2$ en $g$ klapt beide elementen samen. De moraal is een precieze boekhoudregel: samenstellingsinformatie vloeit naar de binnenste afbeelding voor injectiviteit en naar de buitenste afbeelding voor surjectiviteit, nooit andersom. (Oefening 1.9 bouwt hetzelfde verschijnsel met oneindige verzamelingen, waar het de motor is achter eenzijdige inversen.)

Voorbeeld 1.28

$f \colon \R \to \R$ , $x \mapsto x^2$ is noch injectief ( $f(-1) = f(1)$ ) noch surjectief ( $-1$ heeft geen origineel). Door het domein en codomein te beperken is $f \colon \R_+ \to \R_+$ , $x \mapsto x^2$ bijectief, met inverse $y \mapsto \sqrt y$ . De injectiviteit of surjectiviteit van een afbeelding hangt af van het aangekondigde domein en codomein, niet enkel van de formule.

1.6 Relaties

Definitie 1.29 (Equivalentierelatie)

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

Voorbeeld 1.30 (De drie axioma’s nagaan)

Op $\R$ , verklaar $x \mathbin{\mathcal{R}} y$ wanneer $x - y \in \Z$ . Reflexief: $x - x = 0 \in \Z$ . Symmetrisch: als $x - y \in \Z$ dan $y - x = -(x - y) \in \Z$ . Transitief: als $x - y \in \Z$ en $y - z \in \Z$ , dan $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 representant in $\intco01$ , haar fractioneel deel. Daarentegen is de relatie “ $\abs{x - y} \leq 1$ ” op $\R$ reflexief en symmetrisch maar niet transitief ( $0 \mathbin{\mathcal R} 1$ en $1 \mathbin{\mathcal R} 2$ , maar $\abs{0 - 2} > 1$ ): nabijheid plant zich niet voort, en er bestaat geen partitie in klassen — een nuttig tegenvoorbeeld om in gedachten te houden wanneer het nagaan van de axioma’s routine begint te voelen.

Stelling 1.31 (Klassen vormen een partitie)

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

Bewijs. $x \in \mathrm{cl}(x)$ via reflexiviteit, dus klassen zijn niet-leeg met unie $E$ . Veronderstel $\mathrm{cl}(x) \cap \mathrm{cl}(y) \neq \emptyset$ , zeg $z$ ligt in beide. Dan $x \mathbin{\mathcal{R}} z$ en $y \mathbin{\mathcal{R}} z$ , dus via symmetrie en transitiviteit $x \mathbin{\mathcal{R}} y$ . Nu voor elke $t \in \mathrm{cl}(y)$ geeft transitiviteit $t \in \mathrm{cl}(x)$ , en symmetrisch: de twee klassen zijn gelijk. Voor de omgekeerde richting, zij $(E_i)_{i \in I}$ een partitie van $E$ en definieer $x \mathbin{\mathcal S} y$ als “een of ander stuk bevat zowel $x$ als $y$ ”. Reflexief: $x$ ligt in een of ander stuk, dat dan $x$ tweemaal bevat. Symmetrisch: de definiërende voorwaarde is symmetrisch in $x$ en $y$ . Transitief: als $x, y \in E_i$ en $y, z \in E_j$ , dan $y \in E_i \cap E_j$ , dus $E_i = E_j$ (verschillende stukken zijn disjunct) en $x, z$ delen een stuk. De $\mathcal S$ -klasse van $x$ is precies het stuk dat $x$ bevat, dus de klassen zijn de gegeven stukken. Ten slotte is de relatie bepaald door haar klassen: twee equivalentierelaties met dezelfde klassen relateren dezelfde paren, aangezien elk $x$ en $y$ relateert precies wanneer $y$ tot de klasse van $x$ behoort — vanwaar de uniciteitsbewering. ∎

Voorbeeld 1.32

Op $\Z$ is congruentie modulo $n$ ( $x \equiv y \pmod n$ wanneer $n$ het verschil $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 (Orderelatie)

Een relatie $\preceq$ op $E$ is een orde wanneer ze reflexief, antisymmetrisch ( $x \preceq y$ en $y \preceq x$ impliceren $x = y$ ) en transitief is. De orde is totaal wanneer elke twee elementen vergelijkbaar zijn, partieel anders. 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 wanneer 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 niet vergelijkbaar. De deelverzameling $A = \{\{a\}, \{b\}\}$ van $\mathcal{P}(\{a,b\})$ heeft geen grootste element, maar heeft wel een bovengrens $\{a, b\}$ : het onderscheid tussen grootste elementen en bovengrenzen keert terug, voor $\R$ , in Hoofdstuk 10.

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

Op paren van natuurlijke getallen, vergelijk 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 per coördinaat overgeërfd — maar een partiële: $(1, 3)$ en $(2, 0)$ zijn onvergelijkbaar. Vergelijk nu als een woordenboek: $(a, b) \preceq_{\mathrm{lex}} (a', b')$ wanneer $a < a'$ , of $a = a'$ en $b \leq b'$ (de lexicografische orde). Transitiviteit vereist een controle in twee gevallen maar geldt, en elke twee paren zijn nu vergelijkbaar: de orde is totaal. De twee ordes rangschikken dezelfde verzameling verschillend — $(0, 100) \preceq_{\mathrm{lex}} (1, 0)$ terwijl de productorde niets zegt — een herinnering dat een orde een structuur is die men kiest, niet een eigenschap van de verzameling. Lexicografische vergelijking is ook de standaardtruc om verschillende sorteercriteria in één te verenigen.

Opmerking 1.36 (Tussenspel: grootte als bijectie)

Een stil thema van dit hoofdstuk verdient de aandacht: bijecties zijn het wiskundige begrip van “even groot”. Voor eindige verzamelingen wordt dit de telkalkulus van Hoofdstuk 2, waar elke formule stiekem een bijectie is; voor oneindige verzamelingen wordt het het weekendprobleem hieronder, waar $\N$ , $\Q$ en $\R$ genuine verschillende groottes blijken te hebben. Hetzelfde woordenboek verschijnt nog twee keer in dit deel in verfijnde vormen: rijen (Hoofdstuk 11) zijn niets anders dan afbeeldingen $\N \to \R$ , dus uitspraken over rijen zijn uitspraken over een verzameling afbeeldingen; en lineaire algebra zal vectorruimten niet meten met bijecties maar met lineaire bijecties, waarvan het bestaan bepaald wordt door één enkel getal, de dimensie (Hoofdstuk 19). Telkens een nieuwe “gelijkheid” verschijnt — gelijkmachtigheid, isomorfie van groepen (Hoofdstuk 7), lineaire isomorfie — herhaalt het patroon van Stelling 1.24 zich: gelijkheid is een omkeerbare, structuurbewarende afbeelding.

Opmerking 1.37 (Waar dit hoofdstuk gebruikt wordt)

Overal — maar een paar plaatsen verdienen aandacht. De drie-kwantorengymnastiek van Voorbeeld 1.8 is het dagelijkse brood van Hoofdstukken 11 en 13: elk limietbewijs is een spel gespeeld tegen een willekeurige $\varepsilon$ . Equivalentieklassen verschijnen opnieuw als de congruentieklassen van $\Z/n\Z$ in Hoofdstuk 7, waar de partitie van Stelling 1.31 een eigen algebraïsche structuur verwerft. Orderelaties, bovengrenzen en kleinste bovengrenzen worden het axiomatische hart van $\R$ in Hoofdstuk 10. Injecties, surjecties en bijecties keren terug als de lineaire afbeeldingen van Hoofdstuk 20, waar injectiviteit op één enkele vector getest kan worden (de kern); en het weekendprobleem hieronder verandert het kale begrip bijectie in 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 dan of uitspraken (1) en (2) waar zijn.

Oplossing

Oplossing van Oefening 1.1.

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

$\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: gegeven $x$ , neem $y = -x + 1$ ; dan $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 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

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

Oefening 1.3 ★

Bewijs via contrapositie: voor $x \in \R$ , als $x^3 + x \geq 2$ dan $x \geq 1$ . Bewijs dan via tegenspraak: er is geen kleinste strikt positief reëel getal.

Oplossing

Oplossing van Oefening 1.3.

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

Tegenspraak. Veronderstel dat $a > 0$ het kleinste strikt positief reëel getal is. Dan is $a/2$ strikt positief en $a/2 < a$ (aangezien $a > 0$ ), in tegenspraak met de minimaliteit. Dus zo’n $a$ bestaat niet.

Oefening 1.4 ★

Bewijs via 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: aannemend de identiteit voor $n$ ,

$\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: als $4^n + 5 = 3m$ , dan

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

deelbaar door $3$ .

Oefening 1.5 ★

Vind 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 neem $n+1$ potloden; door het laatste weg te nemen delen de eerste $n$ hun kleur; door het eerste weg te nemen delen de laatste $n$ hun kleur; dus delen alle $n+1$ hun kleur.

Oplossing

Oplossing van Oefening 1.5.

De inductiestap neemt stilzwijgend aan 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 dragen. Voor $n + 1 = 2$ zijn de twee groepen $\{$ eerste potlood $\}$ en $\{$ tweede potlood $\}$ : ze zijn disjunct, en het argument breekt. Dus $P(1) \implies P(2)$ werd nooit bewezen, en de inductie stort in — ook al is $P(n) \implies P(n+1)$ geldig voor elke $n \geq 2$ .

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 distributiviteit (Propositie 1.18): $(A \cup B) \cap \overline{C} = (A \cap \overline{C}) \cup (B \cap \overline{C})$ .
Veronderstel $A \subseteq B$ . Dan $A \cup B \subseteq B$ (beide stukken liggen in $B$ ) en $B \subseteq A \cup B$ altijd, dus $A \cup B = B$ . Veronderstel $A \cup B = B$ : dan $A \cap B \subseteq A$ altijd, en $A \subseteq A \cup B = B$ geeft $A \subseteq A \cap B$ , dus $A \cap B = A$ . Veronderstel $A \cap B = A$ : dan $A = A \cap B \subseteq B$ . De drie voorwaarden zijn dus equivalent (we bewezen een cyclus van implicaties).

Oefening 1.7 ★★

Beslis voor elke afbeelding (met bewijs) of ze injectief, surjectief, 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 om ze bijectief te maken 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: $\frac{x+1}{x-1} = \frac{x'+1}{x'-1}$ geeft $(x+1)(x'-1) = (x'+1)(x-1)$ , d.w.z. $xx' - x + x' - 1 = xx' - x' + x - 1$ , dus $2x' = 2x$ . Ze is niet surjectief op $\R$ : het oplossen van $y = \frac{x+1}{x-1}$ geeft $x(y - 1) = y + 1$ , wat geen oplossing heeft wanneer $y = 1$ (de vergelijking leest als $0 = 2$ ). Met codomein $\R \setminus \{1\}$ geeft dezelfde berekening het unieke origineel $x = \frac{y+1}{y-1}$ , dus $h \colon \R \setminus \{1\} \to \R \setminus \{1\}$ is bijectief en $h^{-1}(y) = \frac{y+1}{y-1} = h(y)$ : $h$ is haar eigen inverse.

Oefening 1.8 ★★

Zij $f \colon E \to F$ , 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 waar de inclusie strikt is.
Bewijs: $f$ is injectief als en slechts 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')$ desda $y = f(x)$ voor een of andere $x$ in $A$ of in $A'$ , desda $y \in f(A)$ of $y \in f(A')$ .
Als $y \in f(A \cap A')$ , dan $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 $f(A \cap A') = f(\emptyset) = \emptyset$ maar $f(A) \cap f(A') = \{1\}$ .
( $\Leftarrow$ ) Met $A = \{x\}$ , $A' = \{x'\}$ voor $x \neq x'$ : als $f(x) = f(x')$ , dan $f(A) \cap f(A') = \{f(x)\}$ terwijl $f(A \cap A') = \emptyset$ , in tegenspraak met de aangenomen gelijkheid; dus $f$ is 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'$ ; injectiviteit geeft $x = x' \in A \cap A'$ , dus $y \in f(A \cap A')$ . Met (2) geldt gelijkheid.

Oefening 1.9 ★★

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

Oplossing

Oplossing van Oefening 1.9.

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

Oefening 1.10 ★★

Op $\R$ , definieer $x \mathbin{\mathcal{R}} y \iff x^2 - y^2 = x - y$ . Bewijs dat $\mathcal{R}$ een equivalentierelatie is en beschrijf de equivalentieklasse van elke reële $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$ werkt. Symmetrisch: de voorwaarde “ $y = x$ of $y = 1 - x$ ” is symmetrisch in $x$ en $y$ (als $y = 1 - x$ dan $x = 1 - y$ ). Transitief: veronderstel $x \mathbin{\mathcal{R}} y$ en $y \mathbin{\mathcal{R}} z$ ; de vier gevallen doorlopend, is $z$ telkens gelijk aan $x$ of $1 - x$ (b.v. $y = 1 - x$ en $z = 1 - y$ geven $z = x$ ). Dus $\mathcal{R}$ is een equivalentierelatie en $\mathrm{cl}(x) = \{x,\, 1 - x\}$ . Deze klasse heeft precies één element wanneer $x = 1 - x$ , d.w.z. voor $x = \frac12$ .

Oefening 1.11 ★★★

(Cantor) Zij $E$ een verzameling. Bewijs dat er geen surjectie van $E$ op $\mathcal{P}(E)$ bestaat. Hint: gegeven $f \colon E \to \mathcal{P}(E)$ , beschouw $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 stel $D = \{x \in E : x \notin f(x)\} \in \mathcal{P}(E)$ . Veronderstel $D = f(a)$ voor een of andere $a \in E$ . Als $a \in D$ , dan per definitie van $D$ , $a \notin f(a) = D$ : tegenspraak. Als $a \notin D$ , dan $a \notin f(a)$ , dus per definitie van $D$ , $a \in D$ : tegenspraak. Dus $D$ ligt niet in het beeld van $f$ , en $f$ is niet surjectief. (In het bijzonder is geen 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 als en slechts als $\Phi$ injectief is.
Bewijs dat $f$ injectief is als en slechts als $\Phi$ surjectief is.

Oplossing

Oplossing van Oefening 1.12.

( $\Rightarrow$ ) Zij $f$ surjectief en $\Phi(B) = \Phi(B')$ . Voor $y \in B$ , kies $x$ met $f(x) = y$ ; dan $x \in f^{-1}(B) = f^{-1}(B')$ , dus $y = f(x) \in B'$ . Dus $B \subseteq B'$ , en symmetrisch $B' \subseteq B$ : $\Phi$ is injectief. ( $\Leftarrow$ ) Als $f$ niet surjectief is, kies $y_0 \in F$ buiten het beeld; dan $f^{-1}(\{y_0\}) = \emptyset = f^{-1}(\emptyset)$ met $\{y_0\} \neq \emptyset$ , dus $\Phi$ is niet injectief.
( $\Rightarrow$ ) Zij $f$ injectief en $A \subseteq E$ . Stel $B = f(A)$ ; dan $f^{-1}(B) = \{x : f(x) \in f(A)\}$ , en injectiviteit geeft $f(x) \in f(A) \iff x \in A$ , dus $\Phi(B) = A$ : $\Phi$ is surjectief. ( $\Leftarrow$ ) Als $f$ niet injectief is, neem $x \neq x'$ met $f(x) = f(x')$ . Elke origineelverzameling $f^{-1}(B)$ bevat $x$ als en slechts als ze $x'$ bevat; dus $\{x\}$ is niet van de vorm $\Phi(B)$ , en $\Phi$ is niet surjectief.

1.8 Probleem: Oneindigheden vergelijken

Probleem 1.1

Wanneer hebben twee verzamelingen “hetzelfde aantal elementen”? Cantors antwoord — wanneer er een bijectie tussen hen bestaat — blijkt zelfs voor oneindige verzamelingen bruikbaar te zijn, en het splitst oneindigheid op in genuine verschillende groottes. Dit probleem bouwt de hele gereedschapskist op uit de kale definities van dit hoofdstuk: de stelling van Cantor–Schröder–Bernstein (twee injecties vervaardigen een bijectie), de aftelbaarheid van $\Q$ , de overaftelbaarheid van $\R$ via het diagonaalargument, en Cantors verbluffende conclusie uit 1874: transcendente getallen bestaan, en massaal zelfs, zonder er ook maar één aan te wijzen. Doorheen, voor verzamelingen $E$ en $F$ , schrijf $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 vocabularium van vergelijking.

Toon aan dat $\approx$ zich gedraagt als een equivalentierelatie: $E \approx E$ ; als $E \approx F$ dan $F \approx E$ ; als $E \approx F$ en $F \approx G$ dan $E \approx G$ . (Citeer precies 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)$ induceert.
Zij $E \neq \emptyset$ . Toon aan dat $E \preceq F$ als en slechts als er een surjectie van $F$ op $E$ bestaat.
Ga na dat $n \mapsto n + 1$ een bijectie van $\N$ op $\N^* = \N \setminus \{0\}$ is, en dat

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

een bijectie van $\N$ op $\Z$ is. Dus het weglaten van een punt, of het verdubbelen naar de negatieve getallen, verandert de grootte van $\N$ 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$ de $x \in C$ naar $f(x)$ sturen, en de $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 $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$ . (Directe beelden commuteren met unies: Oefening 1.8.)
Toon aan dat $h$ injectief is. (Drie gevallen; in het gemengde geval $x \in C$ , $x' \notin C$ , toon aan dat $h(x) = h(x')$ zou afdwingen dat $x' \in g(f(C)) \subseteq C$ .)
Toon aan dat $h$ surjectief is: gegeven $y \in F$ , onderscheid de gevallen $g(y) \notin C$ en $g(y) \in C_n$ voor een of andere $n \geq 1$ (waarom is $g(y) \in C_0$ onmogelijk?), en geef een origineel van $y$ in elk geval aan.
Besluit met de stelling van Cantor–Schröder–Bernstein: als $E \preceq F$ en $F \preceq E$ , dan $E \approx F$ . Becommentarieer in één zin wat deze uitspraak niet-triviaal maakt.
Twee toepassingen. (a) Toon aan $\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 via een pariteitsargument, surjectiviteit via sterke inductie (Stelling 1.12). Dus $\N \times \N \approx \N$ : het vlak van gehele punten is niet groter dan de rechte.

Deel III — Aftelbare verzamelingen. Noem een verzameling $E$ ten hoogste 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, voldoet aan $\varphi(n) \geq n$ , en elk element van $A$ bereikt.)
Leid af dat een verzameling ten hoogste aftelbaar is als en slechts als ze eindig of aftelbaar is, en merk op dat vraag 9 de afkorting geeft: als $E \preceq \N$ en $\N \preceq E$ , dan is $E$ aftelbaar.
Toon aan dat als $E$ en $F$ ten hoogste aftelbaar zijn, dan ook $E \times F$ . Leid af dat $\Z \times \N^*$ aftelbaar is.
Toon aan dat $\Q$ aftelbaar is. (Injecteer $\Q$ in $\Z \times \N^*$ door elk rationaal getal vereenvoudigd te schrijven met positieve noemer — de uniciteit van die voorstelling wordt bewezen in Hoofdstuk 6; pas dan vraag 12 toe.)
Toon aan dat een aftelbare unie van ten hoogste aftelbare verzamelingen ten hoogste aftelbaar is: als elke $E_n$ ( $n \in \N$ ) ten hoogste aftelbaar is, 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 injectiviteit door het grootste element te vergelijken waar twee eindige verzamelingen verschillen, met behulp van $\sum_{k=0}^{m-1} 2^k = 2^m - 1$ uit Oefening 1.4.)

Deel IV — Diagonalisatie. Laat $\{0,1\}^{\N}$ de verzameling van alle afbeeldingen $u \colon \N \to \{0, 1\}$ aanduiden, d.w.z. 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$ gedefinieerd 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 ten hoogste 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 — als bekend van school, en streng vastgelegd in Hoofdstuk 10 — dat elke $x \in \intco01$ een unieke eigenlijke decimale ontwikkeling $x = 0.d_1 d_2 d_3\dots$ heeft (een die niet eindigt op een oneindige rij $9$ ’s). Gegeven een willekeurige rij $(x_n)_{n \geq 1}$ van elementen van $\intco01$ , construeer $x \in \intco01$ met $x \neq x_n$ voor alle $n$ : kies zijn $n$ -de cijfer gelijk aan $5$ als het $n$ -de cijfer van $x_n$ verschilt van $5$ , en $6$ anders. Rechtvaardig zorgvuldig dat $x$ eigenlijk is en elke $x_n$ vermijdt, en besluit dat $\intco01$ niet ten hoogste aftelbaar is.
Leid af dat $\R$ overaftelbaar is, en dat de verzameling $\R \setminus \Q$ van irrationale getallen eveneens overaftelbaar is. In welke precieze zin zijn “de meeste” reële getallen irrationaal?

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

Toon aan dat elk rationaal getal algebraïsch is, en vind expliciete veeltermen met gehele coëfficiënten die $\sqrt 2$ en $\sqrt 2 + \sqrt 3$ annihileren.
Toon voor vaste $n \in \N$ aan dat de verzameling van veeltermen van graad ten hoogste $n$ met gehele coëfficiënten aftelbaar is. (Injecteer ze in $\Z^{n+1}$ en pas inductie op $n$ toe met vraag 13.)
Leid af dat de verzameling van alle veeltermen met gehele coëfficiënten aftelbaar is.
Bewijs Cantors stelling over algebraïsche getallen: de verzameling $\mathcal{A}$ van algebraïsche reële getallen is aftelbaar.
Besluit: transcendente reële getallen bestaan, en de verzameling van transcendente getallen is overaftelbaar. Maak dan de balans op van het hele probleem in een paar zinnen: 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 unies, de diagonaal) beslissend was — en de filosofische slagkracht van het bewijzen dat overaftelbaar veel transcendente getallen bestaan zonder er ook maar één te noemen. (Bewijzen dat een specifiek getal zoals $\pi$ transcendent is, is veel moeilijker en valt buiten dit deel.)

Oplossing

Oplossing van Probleem 1.1.

1. Reflexief: $\mathrm{id}_E$ is een bijectie van $E$ op zichzelf. Symmetrisch: als $f \colon E \to F$ bijectief is, levert Stelling 1.24 de $f^{-1} \colon F \to E$ , zelf bijectief. Transitief: als $f \colon E \to F$ en $g \colon F \to G$ bijecties zijn, zegt Propositie 1.26 (1) dat $g \circ f \colon E \to G$ een bijectie is. (Dit is enkel “zoals” een equivalentierelatie: de collectie van alle verzamelingen is zelf geen verzameling, door de paradoxen waar Oefening 1.11 op zinspeelt; de drie eigenschappen zijn wat telt.)

2. Als $f \colon E \to F$ en $g \colon F \to G$ injectief zijn, is $g \circ f$ injectief via Propositie 1.26 (1): $E \preceq G$ . Voor het tweede punt, corestrict $f$ tot haar beeld: de afbeelding $\tilde f \colon E \to f(E)$ , $x \mapsto f(x)$ , is surjectief per constructie van $f(E)$ en injectief omdat $f$ het is, dus bijectief: $E \approx f(E)$ .

3. ( $\Rightarrow$ ) Zij $f \colon E \to F$ injectief en fixeer $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)$ (uniciteit via injectiviteit), en $s(y) = a$ anders. Voor elke $x \in E$ , $s(f(x)) = x$ , dus elke $x$ wordt bereikt: $s$ is surjectief. ( $\Leftarrow$ ) Zij $s \colon F \to E$ surjectief. Voor elke $x \in E$ kies één $y_x \in F$ met $s(y_x) = x$ , en stel $u(x) = y_x$ . Als $u(x) = u(x')$ dan $x = s(u(x)) = s(u(x')) = x'$ : $u \colon E \to F$ is injectief.

4. $n \mapsto n + 1$ beeldt $\N$ in $\N^*$ af, 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 beeldt de even getallen $0, 2, 4, \dots$ af op $0, 1, 2, \dots$ en de oneven getallen $1, 3, 5, \dots$ op $-1, -2, -3, \dots$ Injectiviteit: de even inputs landen in $\N$ ( $\sigma(n) = n/2 \geq 0$ ) en de oneven inputs landen in de strikt negatieve gehele getallen ( $\sigma(n) = -(n+1)/2 \leq -1$ ), dus een botsing moet gebeuren binnen één pariteitsklasse, waar $\sigma$ strikt monotoon is ( $n/2 = m/2$ of $(n+1)/2 = (m+1)/2$ dwingt $n = m$ af). 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. $C_0 = E \setminus g(F) \subseteq C$ , dus $x \notin C$ impliceert $x \notin C_0$ , d.w.z. $x \in g(F)$ : een of andere $y \in F$ voldoet aan $g(y) = x$ . Als ook $g(y') = x$ , geeft injectiviteit van $g$ dat $y' = y$ . Dus de tweede clausule van de definitie van $h$ selecteert een uniek, goed gedefinieerd element $g^{-1}(x)$ .

6. Directe beelden commuteren met unies (Oefening 1.8 (1), toegepast op $f$ 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$ . Als beide in $C$ liggen, dan $h(x) = f(x) \neq f(x') = h(x')$ via injectiviteit van $f$ . Als geen van beide in $C$ ligt, dan $g(h(x)) = x \neq x' = g(h(x'))$ , dus $h(x) \neq h(x')$ . Als $x \in C$ en $x' \notin C$ (het gemengde geval, op verwisseling van namen na): veronderstel $h(x) = h(x')$ , d.w.z. $f(x) = g^{-1}(x')$ . Het toepassen van $g$ : $x' = g(f(x)) \in g(f(C))$ , en vraag 6 geeft $x' \in C$ — tegenspraak. Dus $h(x) \neq h(x')$ in alle gevallen: $h$ is injectief.

8. Zij $y \in F$ . Geval 1: $g(y) \notin C$ . Dan $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$ . Aangezien $g(y) \in g(F)$ , hebben we $g(y) \notin C_0 = E \setminus g(F)$ , dus $n \geq 1$ en $g(y) \in C_n = g(f(C_{n-1}))$ : er is $x \in C_{n-1}$ met $g(y) = g(f(x))$ . 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, dus bijectief.

9. Als $E \preceq F$ en $F \preceq E$ , kies injecties $f \colon E \to F$ en $g \colon F \to E$ ; 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 niet verwant zijn — geen van beide hoeft surjectief te zijn, en geen enkele formule die $f$ en $g$ naïef mengt definieert een afbeelding: de hele inhoud is de partitie van $E$ in het gebied $C$ (waar men $f$ kopieert) en haar complement (waar men $g$ achterstevoren draait).

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 niet-nul richtingscoëfficiënt). Via vraag 9, $\intcc01 \approx \intoo01$ — een bijectie die vrij onaangenaam is om expliciet neer te schrijven. (b) Injectiviteit. Veronderstel $2^p(2q + 1) = 2^{p'}(2q' + 1)$ met, zeg, $p \leq p'$ . Delen door $2^p$ : $2q + 1 = 2^{p' - p}(2q' + 1)$ . Als $p' > p$ is het rechterlid even en het linkerlid oneven — onmogelijk; dus $p = p'$ , dan $2q + 1 = 2q' + 1$ en $q = q'$ . Surjectiviteit. We tonen via 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 gehele getallen van $\intint1m$ . Als $m + 1$ oneven is, $m + 1 = 2q + 1$ met $p = 0$ . Als $m + 1$ even is, $m + 1 = 2m'$ met $1 \leq m' \leq m$ ; via hypothese $m' = 2^p(2q + 1)$ , dus $m + 1 = 2^{p+1}(2q + 1)$ . Dus $\varphi(p, q) = 2^p(2q + 1) - 1$ raakt elke $n \in \N$ , en $\varphi$ is een bijectie $\N \times \N \to \N$ .

11. Aangezien $A$ oneindig is, is $A \setminus \{\varphi(0), \dots, \varphi(n - 1)\}$ nooit leeg, en de kleinste-element-eigenschap van $\N$ (gebruikt om Stelling 1.12 te bewijzen) maakt de recursieve definitie legitiem. 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, vanwaar $\varphi(n+1) > \varphi(n)$ . $\varphi(n) \geq n$ : via inductie, $\varphi(0) \geq 0$ , en $\varphi(n + 1) \geq \varphi(n) + 1 \geq n + 1$ . Injectiviteit volgt uit strikte monotonie. Surjectiviteit op $A$ : veronderstel dat een of andere $a \in A$ nooit bereikt wordt. Aangezien $\varphi(a + 1) \geq a + 1 > a$ , is de verzameling van $n$ met $\varphi(n) > a$ niet-leeg; zij $n$ haar kleinste element. Voor elke $k < n$ , $\varphi(k) \leq a$ , dus $\varphi(k) < a$ ( $a$ wordt niet bereikt). Dan ligt $a$ in $A \setminus \{\varphi(0), \dots, \varphi(n - 1)\}$ en $a < \varphi(n)$ , in tegenspraak met de minimaliteit die $\varphi(n)$ definieert. Dus $\varphi$ is een bijectie $\N \to A$ , en $A$ is aftelbaar.

12. Zij $E \preceq \N$ via een injectie $f$ ; dan $E \approx f(E)$ (vraag 2). Als $f(E)$ eindig is, is $E$ eindig; als $f(E)$ oneindig is, geeft vraag 11 $f(E) \approx \N$ , dus $E \approx \N$ via transitiviteit (vraag 1). Omgekeerd injecteren eindige verzamelingen en aftelbare verzamelingen uiteraard in $\N$ . De afkorting: $E \preceq \N$ en $\N \preceq E$ geven $E \approx \N$ rechtstreeks via Cantor–Schröder–Bernstein — geen opsommingsargument nodig.

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$ : als de beelden samenvallen, geeft injectiviteit van $\varphi$ (vraag 10) $f(x) = f(x')$ en $g(y) = g(y')$ , dan $x = x'$ , $y = y'$ . Voor $\Z \times \N^*$ : beide factoren zijn aftelbaar (vraag 4), dus $\Z \times \N^* \preceq \N$ ; ze is oneindig (ze bevat $\{0\} \times \N^*$ ), dus aftelbaar via vraag 12.

14. Elk rationaal getal $r$ heeft een unieke voorstelling $r = p/q$ met $p \in \Z$ , $q \in \N^*$ en de breuk vereenvoudigd (uniciteit wordt bewezen in Hoofdstuk 6; voor $r = 0$ neem $0/1$ ). De afbeelding $r \mapsto (p, q)$ is dan injectief: het paar bepaalt $r = p/q$ . Dus $\Q \preceq \Z \times \N^* \preceq \N$ via vraag 13. Aangezien $\N \subseteq \Q$ geeft $\N \preceq \Q$ , toont vraag 12 (of Cantor–Schröder–Bernstein rechtstreeks) $\Q \approx \N$ : de rationale getallen zijn aftelbaar.

15. Voor elke $n$ fixeer een injectie $f_n \colon E_n \to \N$ . Voor $x \in \bigcup_n E_n$ , zij $n(x)$ de kleinste $n$ met $x \in E_n$ , en stel $u(x) = \varphi\bigl(n(x), f_{n(x)}(x)\bigr) \in \N$ . Als $u(x) = u(x')$ , geeft injectiviteit van $\varphi$ dat $n(x) = n(x') = n$ en $f_n(x) = f_n(x')$ , dus $x = x'$ via injectiviteit van $f_n$ . Dus de unie injecteert in $\N$ : ze is ten hoogste aftelbaar.

16. Zij $\Psi(F) = \sum_{i \in F} 2^i$ voor $F \subseteq \N$ eindig ( $\Psi(\emptyset) = 0$ ). Veronderstel $F \neq F'$ en zij $m$ het grootste element waarop ze verschillen, zeg $m \in F \setminus F'$ (verwissel namen indien nodig). Elementen $> m$ behoren tot beide of geen van beide, dus ze dragen gelijk bij aan beide sommen; de bijdragen van elementen $\leq m$ vergelijkend:

\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 behulp van de meetkundige som van Oefening 1.4. Dus $\Psi(F) \neq \Psi(F')$ : $\Psi$ is injectief en de verzameling van eindige deelverzamelingen van $\N$ is ten hoogste aftelbaar; ze is oneindig (ze bevat alle singletons), dus aftelbaar.

17. Stuur $A \subseteq \N$ naar haar indicator $\mathbf 1_A \colon \N \to \{0,1\}$ , $\mathbf 1_A(n) = 1$ als $n \in A$ en $0$ anders; stuur $u \in \{0,1\}^{\N}$ naar $A_u = \{n \in \N : u(n) = 1\}$ . De twee afbeeldingen zijn elkaars inverse: $A_{\mathbf 1_A} = A$ en $\mathbf 1_{A_u} = u$ (controleer de waarde bij elke $n$ ). Via Stelling 1.24 is elk een bijectie: $\mathcal{P}(\N) \approx \{0,1\}^{\N}$ .

18. Voor elke $n$ , $d(n) = 1 - \Phi(n)(n) \neq \Phi(n)(n)$ , dus de rijen $d$ en $\Phi(n)$ verschillen op de index $n$ : $d \neq \Phi(n)$ . Dus is geen enkele $\Phi$ surjectief, en via vraag 3 is er ook geen injectie $\{0,1\}^{\N} \to \N$ : $\{0,1\}^{\N}$ is niet ten hoogste 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$ correspondeert met de verzameling $D = \{n : n \notin f(n)\}$ (inderdaad $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$ , $\delta_n = 6$ als $d_n(n) = 5$ , dan $x = 0.\delta_1\delta_2\delta_3\dots$ Deze ontwikkeling gebruikt enkel de cijfers $5$ en $6$ , dus ze eindigt niet op allemaal $9$ ’s: ze is de eigenlijke ontwikkeling van een reële $x \in \intco01$ . Voor elke $n$ verschillen de $n$ -de cijfers van $x$ en $x_n$ ( $\delta_n \neq d_n(n)$ per constructie); aangezien eigenlijke ontwikkelingen uniek zijn, $x \neq x_n$ . Dus geen enkele rij put $\intco01$ uit: via vraag 3 opnieuw is $\intco01$ niet ten hoogste aftelbaar.

20. $\intco01 \subseteq \R$ , dus een injectie $\R \to \N$ zou beperken tot een op $\intco01$ , in tegenspraak met vraag 19: $\R$ is overaftelbaar. Als $\R \setminus \Q$ ten hoogste aftelbaar was, dan zou $\R = \Q \cup (\R \setminus \Q)$ een unie van twee ten hoogste aftelbare verzamelingen zijn, dus ten hoogste aftelbaar via vraag 15 (neem $E_0 = \Q$ , $E_n = \R \setminus \Q$ voor $n \geq 1$ ) — tegenspraak. Dus de irrationale getallen zijn overaftelbaar. Precies: binnen $\R$ vormen de rationale getallen een aftelbare verzameling terwijl hun complement overaftelbaar is; geen bijectie kan ooit $\R \setminus \Q$ met $\Q$ koppelen — 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 wortel van $qX - p$ , een niet-nul veelterm met gehele coëfficiënten. $\sqrt 2$ is een wortel 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$ , d.w.z.

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

$\sqrt 2 + \sqrt 3$ is een wortel 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, aangezien een veelterm bepaald wordt door haar coëfficiënten. Via inductie op $n$ : $\Z^1 = \Z$ is aftelbaar (vraag 4), en $\Z^{n+2} \approx \Z^{n+1} \times \Z$ is ten hoogste aftelbaar via vraag 13. Dus elke verzameling van integer-veeltermen van begrensde graad is ten hoogste aftelbaar; ze is oneindig (ze bevat de constanten), dus aftelbaar via vraag 12.

23. De verzameling van alle integer-veeltermen is $\bigcup_{n \in \N} \{P : \deg P \leq n,\ P \text{ heeft gehele coëfficiënten}\}$ , een aftelbare unie van aftelbare verzamelingen: ten hoogste aftelbaar via vraag 15, oneindig, dus aftelbaar.

24. Voor elke niet-nul integer-veelterm $P$ is de wortelset $R_P = \{x \in \R : P(x) = 0\}$ eindig (ten hoogste $\deg P$ elementen, aangenomen). Via vraag 23 kunnen de niet-nul integer-veeltermen worden opgesomd $P_0, P_1, P_2, \dots$ ; dan is $\mathcal{A} = \bigcup_{n \in \N} R_{P_n}$ een aftelbare unie van eindige (dus ten hoogste aftelbare) verzamelingen: ten hoogste aftelbaar via vraag 15. Ze bevat $\Q$ (vraag 21), dus ze is oneindig: $\mathcal{A}$ is aftelbaar.

25. Als $\R \setminus \mathcal{A}$ ten hoogste aftelbaar was, zou $\R = \mathcal{A} \cup (\R \setminus \mathcal{A})$ ten hoogste aftelbaar zijn (vraag 15), in tegenspraak met vraag 20. Dus transcendente getallen bestaan en vormen zelfs een overaftelbare verzameling, terwijl de algebraïsche getallen — die elk getal bevatten opgebouwd uit gehele getallen door worteltrekking — een louter aftelbaar skelet binnen $\R$ vormen. Samenvatting van de architectuur: vragen 1–3 zetten de vergelijkingstaal op; Cantor–Schröder–Bernstein (vragen 5–9) laat ons gelijkmachtigheid bewijzen door twee makkelijke injecties in plaats van één slimme bijectie, en werd gebruikt voor $\intcc01 \approx \intoo01$ , voor $\Q$ en doorheen Deel V; de koppelingsbijectie (vraag 10) dreef producten en aftelbare unies aan (vragen 13, 15), die op hun beurt $\Q$ , de integer-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 opvallend: het bewijs wijst helemaal geen transcendent getal aan, maar toont toch dat in de zin van gelijkmachtigheid bijna elk reëel getal transcendent is. Eén specifiek transcendent getal noemen — $\pi$ of $\eu$ — vereiste geheel andere wiskunde en decennia meer werk.