---
title: "Logica, verzamelingen en afbeeldingen"
book: "Universitaire wiskunde — Bachelor jaar 1"
subject: math
language: nl
chapter: 1
exercises: 12
source: https://one-course.com/books/math/3/nl/chapter/1-logica-verzamelingen-en-afbeeldingen
---

# Hoofdstuk 1 — Logica, 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](#def-b1-logic-statement) is, hoe connectieven en kwantoren [uitspraken](#def-b1-logic-statement) aan elkaar knopen, welke zetten in een bewijs geoorloofd zijn — en bouwt op dat fundament de twee universele talen van de wiskunde: [verzamelingen](#def-b1-logic-sets) en [afbeeldingen](#def-b1-logic-map).

## 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](#def-b1-logic-statement) $P$, $Q$, $R$ geldt:

1. $\lnot(\lnot P) \iff P$ ;
2. 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)$ ;
3. $(P \implies Q) \iff \bigl((\lnot P) \lor Q\bigr)$ , en dus $\lnot(P \implies Q) \iff P \land (\lnot Q)$ ;
4. contrapositie: $(P \implies Q) \iff \bigl((\lnot Q) \implies (\lnot P)\bigr)$ ;
5. $(P \iff Q) \iff \bigl((P \implies Q) \land (Q \implies  P)\bigr)$ ;
6. 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](#def-b1-logic-statement) 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](#def-b1-logic-sets) $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](#def-b1-logic-sets) $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](#def-b1-logic-statement). Voor de tweede regel: “geen enkele $x$ voldoet aan $P$” zegt dat de [verzameling](#def-b1-logic-sets) $\{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](#ex-b1-logic-limit): 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](#prop-b1-logic-negquant) 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](#def-b1-logic-statement) $\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](#def-b1-logic-statement) 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](#def-b1-logic-statement) 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](https://one-course.com/books/math/3/nl/chapter/11-rijen#ch-b1-seq) 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](#prop-b1-logic-negquant),

$$
\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…

1. *een implicatie $P \implies Q$ rechtstreeks* : neem $P$ aan, leid $Q$ af;
2. *via contrapositie* : neem $\lnot Q$ aan, leid $\lnot P$ af — geldig volgens [Propositie 1.3](#prop-b1-logic-rules) (4);
3. *uit het ongerijmde* : neem aan dat de [uitspraak](#def-b1-logic-statement) onwaar is en leid een tegenspraak af;
4. *een equivalentie* : bewijs beide implicaties apart (of rijg bekende equivalenties aaneen);
5. *een “voor alle”-uitspraak* : kies een *willekeurige* $x$ in $E$ (“zij $x \in E$ ”) en bewijs $P(x)$ ;
6. *een “er bestaat”-uitspraak* : wijs een getuige aan, of bewijs het bestaan langs een omweg;
7. *met inductie* : zie [Stelling 1.12](#thm-b1-logic-induction) .

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.

1. *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.
2. *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.
3. *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.
4. *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

1. $P(0)$ waar is, en
2. 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](#def-b1-logic-statement) $\exists!\,x,\ P(x)$ bestaat uit *twee* [uitspraken](#def-b1-logic-statement), 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](https://one-course.com/books/math/3/nl/chapter/6-getaltheorie-in-z#ch-b1-arith)). 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](#def-b1-logic-statement) $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](#def-b1-logic-sets) van [verzamelingen](#def-b1-logic-sets) zijn gewone [verzamelingen](#def-b1-logic-sets), en [Hoofdstuk 2](https://one-course.com/books/math/3/nl/chapter/2-telkunde#ch-b1-counting) 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](#exo-b1-logic-11) en [1.12](#exo-b1-logic-12).

**Propositie 1.18 (Verzamelingenalgebra).**

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

1. $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)$ ;
2. De Morgan: $\overline{A \cup B} = \overline{A} \cap  \overline{B}$ en $\overline{A \cap B} = \overline{A} \cup  \overline{B}$ ;
3. $A \subseteq B \iff \overline{B} \subseteq \overline{A}$ .

**Bewijs.** Elke identiteit vertaalt een regel uit [Propositie 1.3](#prop-b1-logic-rules) via het woordenboek (wel of niet $\in A$) $\leftrightarrow$ ([uitspraak](#def-b1-logic-statement) 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](#prop-b1-logic-rules) (6), en de laatste [uitspraak](#def-b1-logic-statement) 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.](https://one-course.com/images/onecourse/chapters/math-3/b1-logic/fig-5465323f1d10.svg)

*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](#prop-b1-logic-setalgebra) 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](#def-b1-logic-sets) $E$ (het *domein*) precies één element $f(x)$ van de [verzameling](#def-b1-logic-sets) $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](#def-b1-logic-map): $f^{-1}(B)$ is voor elke $f$ gedefinieerd. [Originelen](#def-b1-logic-map) 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](#exo-b1-logic-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](#def-b1-logic-map) 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](#def-b1-logic-map) $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](#def-b1-logic-map) heeft.

**Stelling 1.24 (Inverse afbeelding).**

Een [afbeelding](#def-b1-logic-map) $f \colon E \to F$ is [bijectief](#def-b1-logic-inj) dan en slechts dan als er een [afbeelding](#def-b1-logic-map) $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](#def-b1-logic-inj) met $(f^{-1})^{-1} = f$.

**Bewijs.** ($\Rightarrow$) Is $f$ [bijectief](#def-b1-logic-inj), dan heeft elke $y \in F$ precies één [origineel](#def-b1-logic-map); definieer $g(y)$ als dat [origineel](#def-b1-logic-map). Dan is $f(g(y)) = y$ per constructie, en $g(f(x)) = x$ omdat $x$ hét [origineel](#def-b1-logic-map) 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](#def-b1-logic-inj). Voor $y \in F$ voldoet $x = g(y)$ aan $f(x) = y$: $f$ is [surjectief](#def-b1-logic-inj).

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](#def-b1-logic-inj) 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](#def-b1-logic-inj), 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](#thm-b1-logic-inverse). 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](#def-b1-logic-inj) op $\R$).

**Propositie 1.26 (Samenstelling en de drie eigenschappen).**

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

1. Zijn $f$ en $g$ [injectief](#def-b1-logic-inj) (respectievelijk [surjectief](#def-b1-logic-inj) , [bijectief](#def-b1-logic-inj) ), dan is $g \circ f$ dat ook; en in het [bijectieve](#def-b1-logic-inj) geval is $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ .
2. Is $g \circ f$ [injectief](#def-b1-logic-inj) , dan is $f$ [injectief](#def-b1-logic-inj) . Is $g \circ f$ [surjectief](#def-b1-logic-inj) , dan is $g$ [surjectief](#def-b1-logic-inj) .

**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](#def-b1-logic-inj) 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](#thm-b1-logic-inverse) 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](#prop-b1-logic-comp) (2) kunnen de conclusies niet versterkt worden: dat $g \circ f$ [bijectief](#def-b1-logic-inj) is, dwingt $f$ *niet* [surjectief](#def-b1-logic-inj) of $g$ [injectief](#def-b1-logic-inj) 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](#def-b1-logic-inj), 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](#def-b1-logic-map) en voor surjectiviteit naar de *buitenste*, nooit andersom. ([Oefening 1.9](#exo-b1-logic-9) bouwt hetzelfde verschijnsel op oneindige [verzamelingen](#def-b1-logic-sets), waar het de motor is achter eenzijdige inversen.)

**Voorbeeld 1.28.**

$f \colon \R \to \R$, $x \mapsto x^2$ is [injectief](#def-b1-logic-inj) noch [surjectief](#def-b1-logic-inj) ($f(-1) = f(1)$, en $-1$ heeft geen [origineel](#def-b1-logic-map)). Beperken we domein en codomein, dan is $f \colon \R_+ \to \R_+$, $x \mapsto x^2$ [bijectief](#def-b1-logic-inj), met inverse $y \mapsto \sqrt y$. Of een [afbeelding](#def-b1-logic-map) [injectief](#def-b1-logic-inj) of [surjectief](#def-b1-logic-inj) 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](#def-b1-logic-sets) $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](#def-b1-logic-equiv), 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](#thm-b1-logic-partition) 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](#def-b1-logic-equiv) op $E$. Dan zijn de [equivalentieklassen](#def-b1-logic-equiv) niet-leeg, twee aan twee disjunct of gelijk, en is hun vereniging $E$: ze vormen een *partitie* van $E$. Omgekeerd komt elke [partitie](#thm-b1-logic-partition) van $E$ op deze manier van precies één [equivalentierelatie](#def-b1-logic-equiv) (“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](#thm-b1-logic-partition) 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](#def-b1-logic-equiv) 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](#def-b1-logic-equiv); haar klassen zijn de $n$ [verzamelingen](#def-b1-logic-sets) van gehele getallen met een gegeven rest bij deling door $n$. Dit voorbeeld wordt de ring $\Z/n\Z$ in [Hoofdstuk 7](https://one-course.com/books/math/3/nl/chapter/7-algebraische-structuren#ch-b1-structures).

**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](https://one-course.com/books/math/3/nl/chapter/10-reele-getallen#ch-b1-reals).

**Voorbeeld 1.35 (Twee ordes op het rooster N2\N^2N2).**

Vergelijk paren natuurlijke getallen componentsgewijs: $(a, b) \preceq
(a', b')$ wanneer $a \leq a'$ *en* $b \leq b'$ (de *productorde*). Dit is een [orde](#def-b1-logic-order) — 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](#def-b1-logic-order)*). Transitiviteit vraagt een gevalsonderscheid, maar geldt, en nu zijn elke twee paren vergelijkbaar: de [orde](#def-b1-logic-order) is totaal. Beide [ordes](#def-b1-logic-order) rangschikken dezelfde [verzameling](#def-b1-logic-sets) verschillend — $(0, 100) \preceq_{\mathrm{lex}} (1, 0)$ terwijl de productorde er niets over zegt — een herinnering dat een [orde](#def-b1-logic-order) een structuur is die je *kiest* en geen eigenschap van de [verzameling](#def-b1-logic-sets). 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](#def-b1-logic-sets) wordt dat de telkunde van [Hoofdstuk 2](https://one-course.com/books/math/3/nl/chapter/2-telkunde#ch-b1-counting), waarin elke formule stiekem een bijectie is; voor oneindige [verzamelingen](#def-b1-logic-sets) 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](https://one-course.com/books/math/3/nl/chapter/11-rijen#ch-b1-seq)) zijn niets anders dan [afbeeldingen](#def-b1-logic-map) $\N \to \R$, zodat [uitspraken](#def-b1-logic-statement) over rijen [uitspraken](#def-b1-logic-statement) over een [verzameling](#def-b1-logic-sets) [afbeeldingen](#def-b1-logic-map) 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](https://one-course.com/books/math/3/nl/chapter/19-eindige-dimensie#ch-b1-findim)). Telkens als er een nieuwe “gelijkheid” opduikt — gelijkmachtigheid, isomorfie van groepen ([Hoofdstuk 7](https://one-course.com/books/math/3/nl/chapter/7-algebraische-structuren#ch-b1-structures)), lineaire isomorfie — herhaalt zich het patroon van [Stelling 1.24](#thm-b1-logic-inverse): gelijkheid is een inverteerbare [afbeelding](#def-b1-logic-map) 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](#ex-b1-logic-limit) is het dagelijks brood van Hoofdstukken [11](https://one-course.com/books/math/3/nl/chapter/11-rijen#ch-b1-seq) en [13](https://one-course.com/books/math/3/nl/chapter/13-limieten-en-continuiteit#ch-b1-continuity): elk limietbewijs is een spel tegen een willekeurige $\varepsilon$. [Equivalentieklassen](#def-b1-logic-equiv) keren terug als de congruentieklassen van $\Z/n\Z$ in [Hoofdstuk 7](https://one-course.com/books/math/3/nl/chapter/7-algebraische-structuren#ch-b1-structures), waar de [partitie](#thm-b1-logic-partition) van [Stelling 1.31](#thm-b1-logic-partition) een eigen algebraïsche structuur krijgt. [Ordeningsrelaties](#def-b1-logic-order), bovengrenzen en kleinste bovengrenzen worden het axiomatische hart van $\R$ in [Hoofdstuk 10](https://one-course.com/books/math/3/nl/chapter/10-reele-getallen#ch-b1-reals). Injecties, surjecties en bijecties komen terug als de lineaire [afbeeldingen](#def-b1-logic-map) van [Hoofdstuk 20](https://one-course.com/books/math/3/nl/chapter/20-lineaire-afbeeldingen#ch-b1-linmaps), 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](#def-b1-logic-sets)*, waarvan de conclusies (aftelbaarheid van $\Q$, overaftelbaarheid van $\R$) weer opduiken in Hoofdstukken [10](https://one-course.com/books/math/3/nl/chapter/10-reele-getallen#ch-b1-reals) en [12](https://one-course.com/books/math/3/nl/chapter/12-topologie-van-de-reele-rechte#ch-b1-topology).

## 1.7 Oefeningen

**Oefening 1.1 ★.**

Schrijf de negatie van elke [uitspraak](#def-b1-logic-statement), zonder het woord “niet” te gebruiken:

1. $\forall x \in \R,\ \exists y \in \R,\ x + y > 0$ ;
2. $\exists x \in \R,\ \forall y \in \R,\ xy = 0$ ;
3. $\forall \varepsilon > 0,\ \exists \delta > 0,\ \forall x \in  \R,\ \abs{x} \leq \delta \implies \abs{f(x)} \leq \varepsilon$ (voor een vaste [afbeelding](#def-b1-logic-map) $f \colon \R \to \R$ ).

Beslis vervolgens of de [uitspraken](#def-b1-logic-statement) (1) en (2) waar zijn.

**Oplossing van Oefening 1.1.**

Negaties, waarbij $\lnot$ door elke kwantor geduwd wordt ([Propositie 1.5](#prop-b1-logic-negquant)) en de regel $\lnot(P \implies Q) \iff
P \land \lnot Q$ gebruikt wordt:

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

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

**Oefening 1.2 ★.**

Zij $P, Q$ [uitspraken](#def-b1-logic-statement). 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 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](#def-b1-logic-statement) overigens: de oorspronkelijke implicatie is waar, zie [Hoofdstuk 14](https://one-course.com/books/math/3/nl/chapter/14-differentiaalrekening#ch-b1-derivative)).

**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 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](#def-b1-logic-statement).

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

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

**Oplossing van Oefening 1.4.**

1. 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 .$$
2. 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](#def-b1-logic-sets) 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 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:

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

**Oplossing van Oefening 1.6.**

1. $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}$ .
2. Met (1) en de distributiviteit ( [Propositie 1.18](#prop-b1-logic-setalgebra) ): $(A \cup B) \cap \overline{C} = (A \cap \overline{C}) \cup  (B \cap \overline{C})$ .
3. 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](#def-b1-logic-map) met bewijs na of ze [injectief](#def-b1-logic-inj), [surjectief](#def-b1-logic-inj) of [bijectief](#def-b1-logic-inj) is:

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

Pas voor $h$ het codomein aan zodat ze [bijectief](#def-b1-logic-inj) wordt en bereken de inverse.

**Oplossing van Oefening 1.7.**

1. $f$ is [injectief](#def-b1-logic-inj) ( $n + 1 = m + 1 \implies n = m$ ) maar niet [surjectief](#def-b1-logic-inj) : $0$ heeft geen [origineel](#def-b1-logic-map) in $\N$ .
2. $g$ is [bijectief](#def-b1-logic-inj) : $n \mapsto n - 1$ is een tweezijdige inverse op $\Z$ .
3. $h$ is [injectief](#def-b1-logic-inj) : 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](#def-b1-logic-inj) 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](#def-b1-logic-map) $x = \frac{y+1}{y-1}$ , zodat $h \colon \R \setminus \{1\} \to \R \setminus \{1\}$ [bijectief](#def-b1-logic-inj) 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$.

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

**Oplossing van Oefening 1.8.**

1. $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')$ .
2. 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\}$ .
3. ( $\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](#def-b1-logic-inj) . ( $\Rightarrow$ ) Zij $f$ [injectief](#def-b1-logic-inj) 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](#def-b1-logic-inj) is en $g$ [surjectief](#def-b1-logic-inj). Geef een voorbeeld waarin $f$ noch $g$ [bijectief](#def-b1-logic-inj) is.

**Oplossing van Oefening 1.9.**

$g \circ f = \mathrm{id}_E$ is [injectief](#def-b1-logic-inj) en [surjectief](#def-b1-logic-inj), dus is volgens [Propositie 1.26](#prop-b1-logic-comp) (2) $f$ [injectief](#def-b1-logic-inj) en $g$ [surjectief](#def-b1-logic-inj). 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](#def-b1-logic-inj) en $g$ niet [injectief](#def-b1-logic-inj).

**Oefening 1.10 ★★.**

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

**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](#def-b1-logic-equiv) 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](#def-b1-logic-sets). 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](#def-b1-logic-sets) $D = \{x \in E : x \notin
f(x)\}$.*

**Oplossing van Oefening 1.11.**

Zij $f \colon E \to \mathcal{P}(E)$ een willekeurige [afbeelding](#def-b1-logic-map) 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](#def-b1-logic-inj). (In het bijzonder staat geen enkele [verzameling](#def-b1-logic-sets) in bijectie met haar [machtsverzameling](#def-b1-logic-sets): er zijn “meer” deelverzamelingen van $\N$ dan gehele getallen.)

**Oefening 1.12 ★★★.**

Zij $f \colon E \to F$ een [afbeelding](#def-b1-logic-map). Definieer $\Phi \colon
\mathcal{P}(F) \to \mathcal{P}(E)$ door $\Phi(B) = f^{-1}(B)$.

1. Bewijs dat $f$ [surjectief](#def-b1-logic-inj) is dan en slechts dan als $\Phi$ [injectief](#def-b1-logic-inj) is.
2. Bewijs dat $f$ [injectief](#def-b1-logic-inj) is dan en slechts dan als $\Phi$ [surjectief](#def-b1-logic-inj) is.

**Oplossing van Oefening 1.12.**

1. ( $\Rightarrow$ ) Zij $f$ [surjectief](#def-b1-logic-inj) 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](#def-b1-logic-inj) . ( $\Leftarrow$ ) Is $f$ niet [surjectief](#def-b1-logic-inj) , 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](#def-b1-logic-inj) .
2. ( $\Rightarrow$ ) Zij $f$ [injectief](#def-b1-logic-inj) 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](#def-b1-logic-inj) . ( $\Leftarrow$ ) Is $f$ niet [injectief](#def-b1-logic-inj) , neem dan $x \neq x'$ met $f(x) = f(x')$ . Elk [origineel](#def-b1-logic-map) $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](#def-b1-logic-inj) .

## 1.8 Opgave: oneindigheden vergelijken

**Probleem 1.1.**

Wanneer hebben twee [verzamelingen](#def-b1-logic-sets) “evenveel elementen”? Cantors antwoord — wanneer er een bijectie tussen beide bestaat — blijkt ook voor oneindige [verzamelingen](#def-b1-logic-sets) 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](#pb-b1-logic-1) getallen bestaan, en wel in overweldigende hoeveelheid* — zonder er ook maar één aan te wijzen. Schrijf overal, voor [verzamelingen](#def-b1-logic-sets) $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.**

1. Toon aan dat $\approx$ zich als een [equivalentierelatie](#def-b1-logic-equiv) 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](#thm-b1-logic-inverse) en [Propositie 1.26](#prop-b1-logic-comp) .)
2. Toon aan dat $\preceq$ transitief is, en dat een injectie $f  \colon E \to F$ altijd $E \approx f(E)$ oplevert.
3. Zij $E \neq \emptyset$ . Toon aan dat $E \preceq F$ dan en slechts dan als er een surjectie van $F$ op $E$ bestaat.
4. 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$.

5. 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.
6. Toon aan dat $g\bigl(f(C)\bigr) = \bigcup_{n \geq 1} C_n  \subseteq C$ . (Beelden verwisselen met verenigingen: [Oefening 1.8](#exo-b1-logic-8) .)
7. Toon aan dat $h$ [injectief](#def-b1-logic-inj) 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$ .)
8. Toon aan dat $h$ [surjectief](#def-b1-logic-inj) 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](#def-b1-logic-map) van $y$ aan.
9. 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](#def-b1-logic-statement) niet-triviaal maakt.
10. 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](#thm-b1-logic-induction) ). 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](#pb-b1-logic-1).** Noem een [verzameling](#def-b1-logic-sets) $E$ *hoogstens aftelbaar* wanneer $E \preceq \N$, en *aftelbaar* wanneer $E \approx \N$.

11. 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.)
12. Leid af dat een [verzameling](#def-b1-logic-sets) 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.
13. Toon aan dat met $E$ en $F$ ook $E \times F$ hoogstens aftelbaar is. Leid af dat $\Z \times \N^*$ aftelbaar is.
14. 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](https://one-course.com/books/math/3/nl/chapter/6-getaltheorie-in-z#ch-b1-arith) ; pas dan vraag 12 toe.)
15. Toon aan dat een aftelbare vereniging van hoogstens [aftelbare verzamelingen](#pb-b1-logic-1) 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$ .)
16. Toon aan dat de [verzameling](#def-b1-logic-sets) 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](#def-b1-logic-sets) verschillen, met $\sum_{k=0}^{m-1} 2^k =  2^m - 1$ uit [Oefening 1.4](#exo-b1-logic-4) .)

**Deel IV — Diagonalisatie.** Noteer met $\{0,1\}^{\N}$ de [verzameling](#def-b1-logic-sets) van alle [afbeeldingen](#def-b1-logic-map) $u \colon \N \to \{0,
1\}$, dat wil zeggen de [verzameling](#def-b1-logic-sets) van binaire rijen.

17. Construeer een bijectie tussen $\mathcal{P}(\N)$ en $\{0,1\}^{\N}$ (indicatorfuncties).
18. (Het diagonaalargument) Zij $\Phi \colon \N \to \{0,1\}^{\N}$ een willekeurige [afbeelding](#def-b1-logic-map) . 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](#exo-b1-logic-11) ) is voor $E = \N$ .
19. Neem aan — zoals van de middelbare school vertrouwd, en streng vastgelegd in [Hoofdstuk 10](https://one-course.com/books/math/3/nl/chapter/10-reele-getallen#ch-b1-reals) — 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.
20. Leid af dat $\R$ overaftelbaar is, en dat de [verzameling](#def-b1-logic-sets) $\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](#pb-b1-logic-1) 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](https://one-course.com/books/math/3/nl/chapter/8-veeltermen#ch-b1-poly) — dat een veelterm van graad $n$ die niet nul is hoogstens $n$ reële nulpunten heeft.

21. 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.
22. Toon voor vaste $n \in \N$ aan dat de [verzameling](#def-b1-logic-sets) 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.)
23. Leid af dat de [verzameling](#def-b1-logic-sets) van *alle* veeltermen met gehele coëfficiënten aftelbaar is.
24. Bewijs *Cantors stelling over de algebraïsche getallen* : de [verzameling](#def-b1-logic-sets) $\mathcal{A}$ van de algebraïsche reële getallen is aftelbaar.
25. Besluit: [transcendente](#pb-b1-logic-1) reële getallen bestaan, en de [verzameling](#def-b1-logic-sets) van [transcendente](#pb-b1-logic-1) 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](#pb-b1-logic-1) getallen bestaan zonder er ook maar één te noemen. (Van een *specifiek* getal als $\pi$ bewijzen dat het [transcendent](#pb-b1-logic-1) is, is veel moeilijker en valt buiten dit volume.)

**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](#def-b1-logic-inj), dan levert [Stelling 1.24](#thm-b1-logic-inverse) de eveneens [bijectieve](#def-b1-logic-inj) $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](#prop-b1-logic-comp) (1) dat $g \circ f \colon E
\to G$ een bijectie is. (Het gaat hier slechts om iets dat zich “als” een [equivalentierelatie](#def-b1-logic-equiv) gedraagt: de collectie van alle [verzamelingen](#def-b1-logic-sets) is zelf geen [verzameling](#def-b1-logic-sets), wegens de paradoxen waarnaar [Oefening 1.11](#exo-b1-logic-11) verwijst; het zijn de drie eigenschappen die tellen.)

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

**3.** ($\Rightarrow$) Zij $f \colon E \to F$ [injectief](#def-b1-logic-inj) 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](#def-b1-logic-inj). ($\Leftarrow$) Zij $s \colon F \to E$ [surjectief](#def-b1-logic-inj). 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](#def-b1-logic-inj).

**4.** $n \mapsto n + 1$ beeldt $\N$ af in $\N^*$, is [injectief](#def-b1-logic-inj) ($n + 1 = m + 1 \implies n = m$) en [surjectief](#def-b1-logic-inj) (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](#exo-b1-logic-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](#def-b1-logic-inj).

**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](#def-b1-logic-map). *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](#def-b1-logic-inj), en dus [bijectief](#def-b1-logic-inj).

**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](#def-b1-logic-statement) is niet-triviaal omdat de twee gegeven injecties niets met elkaar te maken hebben — geen van beide hoeft [surjectief](#def-b1-logic-inj) te zijn, en geen enkele naïeve formule in $f$ en $g$ definieert een [afbeelding](#def-b1-logic-map): de hele inhoud zit in de [partitie](#thm-b1-logic-partition) 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](#def-b1-logic-inj); en $x
\mapsto \frac{x + 1}3$ beeldt $\intcc01$ [injectief](#def-b1-logic-inj) 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](#thm-b1-logic-induction)) 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](#def-b1-logic-sets) 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](#pb-b1-logic-1) 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](#def-b1-logic-sets) 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](https://one-course.com/books/math/3/nl/chapter/6-getaltheorie-in-z#ch-b1-arith); voor $r = 0$ neem je $0/1$). De [afbeelding](#def-b1-logic-map) $r \mapsto (p, q)$ is dan [injectief](#def-b1-logic-inj): 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](#exo-b1-logic-4). Bijgevolg is $\Psi(F)
\neq \Psi(F')$: $\Psi$ is [injectief](#def-b1-logic-inj) en de [verzameling](#def-b1-logic-sets) 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](#def-b1-logic-map) 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](#thm-b1-logic-inverse) 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](#def-b1-logic-inj), 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](#def-b1-logic-map) $\Phi \colon \N \to \{0,1\}^{\N}$ een [afbeelding](#def-b1-logic-map) $f \colon \N
\to \mathcal{P}(\N)$, en $d$ komt overeen met de [verzameling](#def-b1-logic-sets) $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](#exo-b1-logic-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](#pb-b1-logic-1) 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](#pb-b1-logic-1) 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](#def-b1-logic-inj), 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](#def-b1-logic-sets) 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](#def-b1-logic-sets) 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](#pb-b1-logic-1): 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](#def-b1-logic-sets): 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](#pb-b1-logic-1) getallen, en ze vormen zelfs een overaftelbare [verzameling](#def-b1-logic-sets), 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](#pb-b1-logic-1) aan en toont toch dat in de zin van gelijkmachtigheid *bijna elk* reëel getal [transcendent](#pb-b1-logic-1) is. Van één specifiek getal — $\pi$ of $\eu$ — de transcendentie aantonen vergde volstrekt andere wiskunde en nog decennia werk.