Universitaire wiskunde — Bachelor jaar 2 · Bachelor Year 2

1Verzamelingen en structuren

Dit openingshoofdstuk slijpt de grondslagen uit het volume van bachelorjaar 1 tot dagelijks gereedschap: het rekenen met verzamelingen en quotiënten, het vergelijken van oneindige verzamelingen (aftelbaarheid, Cantor–Bernstein) en de structuurtheorie van groepen en ringen — de stelling van Lagrange, de symmetrische groep met haar signatuur, idealen en de Chinese reststelling. Alles wat hier staat wordt in de rest van het boek onophoudelijk gebruikt: de signatuur bouwt de determinant (Hoofdstuk 2), quotiëntringen dragen de rekenkunde, en aftelbaarheid ligt zowel aan de topologie als aan de kansrekening ten grondslag.

1.1 Verzamelingen, afbeeldingen, quotiënten

We gebruiken zonder verdere plichtplegingen de taal van verzamelingen, afbeeldingen, equivalentierelaties en orderelaties uit het volume van bachelorjaar 1. Twee punten verdienen een zorgvuldige formulering.

Propositie 1.1 (Beelden en originelen van families)

Zij $f \colon E \to F$ , en zijn $(A_i)_{i \in I}$ , $(B_j)_{j \in J}$ families van deelverzamelingen van $E$ respectievelijk $F$ . Dan geldt

f^{-1}\Bigl(\bigcup_j B_j\Bigr) = \bigcup_j f^{-1}(B_j), \qquad f^{-1}\Bigl(\bigcap_j B_j\Bigr) = \bigcap_j f^{-1}(B_j), \qquad f^{-1}(F \setminus B) = E \setminus f^{-1}(B),

f\Bigl(\bigcup_i A_i\Bigr) = \bigcup_i f(A_i), \qquad f\Bigl(\bigcap_i A_i\Bigr) \subseteq \bigcap_i f(A_i) \quad (\text{gelijkheid voor injectieve } f).

Bewijs. Elke identiteit is niets anders dan het uitschrijven van de definities; bijvoorbeeld $x \in f^{-1}(\bigcap B_j) \iff f(x) \in B_j$ voor alle $j$ $\iff x \in f^{-1}(B_j)$ voor alle $j$ . De identiteiten voor beelden, het falen van de gelijkheid bij de doorsnede en de reparatie via injectiviteit zijn in het volume van bachelorjaar 1 voor twee verzamelingen bewezen; voor families verloopt het argument woordelijk hetzelfde. ∎

Voorbeeld 1.2 (Waar de insluiting voor beelden strikt is)

Neem $f \colon \R \to \R$ , $f(x) = x^2$ , met $A_1 = \intcc{-1}{0}$ en $A_2 = \intcc{0}{1}$ . Dan is

f(A_1 \cap A_2) = f(\{0\}) = \{0\}, \qquad f(A_1) \cap f(A_2) = \intcc{0}{1} \cap \intcc{0}{1} = \intcc{0}{1} :

de insluiting van Propositie 1.1 is zo strikt als maar kan — de twee originelen $\pm x$ van eenzelfde waarde liggen in verschillende $A_i$ . Injectiviteit is precies wat die splitsing verbiedt, en daarom voldoen originelen (die nooit punten samenvoegen) onvoorwaardelijk aan alle vier de identiteiten, terwijl beelden die over doorsneden kwijtraken. Vuistregel voor het hele boek: duw originelen onbekommerd door verzamelingsbewerkingen heen; ga met beelden voorzichtig om.

Definitie 1.3 (Quotiëntverzameling)

Zij $\mathcal{R}$ een equivalentierelatie op $E$ . De quotiëntverzameling $E/\mathcal{R}$ is de verzameling van de equivalentieklassen; de surjectie $\pi \colon E \to E/\mathcal{R}$ , $x \mapsto \mathrm{cl}(x)$ , heet de canonieke projectie.

Universele eigenschap (factorisatie): is $f \colon E \to F$ verenigbaar met $\mathcal{R}$ (dat wil zeggen $x \mathbin{\mathcal{R}} y \implies f(x) = f(y)$ ), dan bestaat er precies één afbeelding $\overline f \colon E/\mathcal{R} \to F$ met $f = \overline f \circ \pi$ .

Bewijs van de universele eigenschap. Eenduidigheid: de eis $f = \overline f \circ \pi$ luidt

\overline f\bigl(\mathrm{cl}(x)\bigr) = f(x) \qquad (x \in E),

en omdat $\pi$ surjectief is, is elk element van $E/\mathcal{R}$ van de vorm $\mathrm{cl}(x)$ : alle waarden van $\overline f$ liggen dus vast. Bestaan: neem de formule hierboven als definitie van $\overline f$ ; zij is ondubbelzinnig juist dankzij de verenigbaarheid — is $\mathrm{cl}(x) = \mathrm{cl}(y)$ , dan geldt $x \mathbin{\mathcal{R}} y$ , dus $f(x) = f(y)$ en de twee kandidaat-waarden vallen samen — en zij factoriseert $f$ per constructie. Merk de taakverdeling op: surjectiviteit van $\pi$ levert de eenduidigheid, verenigbaarheid levert het bestaan. ∎

Voorbeeld 1.4

$\Z/n\Z$ is het quotiënt van $\Z$ naar congruentie modulo $n$ ; de controles op welgedefinieerdheid uit het volume van bachelorjaar 1 waren telkens een toepassing van de universele eigenschap. Quotiënten maken van “constructies op representanten die verenigbaar zijn” echte afbeeldingen — daar leunen we hieronder voortdurend op.

1.2 Aftelbaarheid en kardinaliteit

Definitie 1.5 (Gelijkmachtigheid, aftelbaarheid)

Twee verzamelingen heten gelijkmachtig wanneer er een bijectie tussen beide bestaat. Een verzameling heet aftelbaar wanneer zij gelijkmachtig is met $\N$ (sommige auteurs rekenen de eindige verzamelingen mee; wij zeggen hoogstens aftelbaar voor “eindig of aftelbaar”).

Propositie 1.6 (Stabiliteitseigenschappen)

Elke oneindige deelverzameling van $\N$ is aftelbaar; een verzameling is hoogstens aftelbaar dan en slechts dan als zij in $\N$ injecteert, dan en slechts dan als zij leeg is of een surjectief beeld van $\N$ .
$\N \times \N$ is aftelbaar; een product van twee hoogstens aftelbare verzamelingen is hoogstens aftelbaar.
Een hoogstens aftelbare vereniging van hoogstens aftelbare verzamelingen is hoogstens aftelbaar.
$\Z$ en $\Q$ zijn aftelbaar.

Bewijs. (1) Som een oneindige $A \subseteq \N$ op met herhaalde minima: $a_0 = \min A$ , $a_{k+1} = \min\,(A \setminus \{a_0, \dots, a_k\})$ (niet leeg, want $A$ is oneindig); de afbeelding $k \mapsto a_k$ is strikt stijgend, injectief en surjectief op $A$ (elke $a \in A$ overtreft slechts eindig veel elementen van $A$ en wordt dus bereikt). Injecteert $E$ via $\varphi$ in $\N$ , dan is $E$ gelijkmachtig met $\varphi(E) \subseteq \N$ : eindig of aftelbaar. Is $s \colon \N \to E$ surjectief, dan injecteert $x \mapsto \min s^{-1}(\{x\})$ de verzameling $E$ in $\N$ .

(2) De afbeelding $(p, q) \mapsto 2^p(2q + 1) - 1$ is een bijectie $\N^2 \to \N$ (elk positief geheel getal heeft precies één splitsing $2^p m$ met $m$ oneven, wegens de eenduidige priemfactorisatie). Voor producten: stel injecties samen.

(3) Zijn verzamelingen $E_n$ gegeven met surjecties $s_n \colon \N \to E_n$ (onschadelijk wanneer een $E_n$ eindig is: herhaal waarden), dan is $(n, k) \mapsto s_n(k)$ een surjectie van het aftelbare $\N^2$ op $\bigcup E_n$ .

(4) $\Z = \N \cup (-\N^*)$ : een aftelbare vereniging. En $\Q$ is een surjectief beeld van $\Z \times \N^*$ (de breukafbeelding), dus hoogstens aftelbaar, en oneindig. ∎

Voorbeeld 1.7 (Een koppelfunctie, doorgerekend)

De bijectie $(p, q) \mapsto 2^p(2q + 1) - 1$ uit het bewijs verdient het om aan het werk gezien te worden. Haar eerste waarden:

\begin{array}{c|ccccc} & q = 0 & q = 1 & q = 2 & q = 3 & q = 4\\ \hline p = 0 & 0 & 2 & 4 & 6 & 8\\ p = 1 & 1 & 5 & 9 & 13 & 17\\ p = 2 & 3 & 11 & 19 & 27 & 35\\ p = 3 & 7 & 23 & 39 & 55 & 71 \end{array}

Rij $p$ verzamelt de getallen $n$ waarvoor $n + 1$ precies door $2^p$ deelbaar is: elk natuurlijk getal komt precies één keer voor. Decoderen is even expliciet als coderen: voor $n = 43$ ontbinden we $n + 1 = 44 = 2^2\cdot 11 = 2^2(2\cdot5 + 1)$ , dus $(p, q) = (2, 5)$ . Het inzicht om te onthouden: bewijzen over aftelbaarheid zijn vaak vermomde algoritmen — hier “haal de factoren $2$ eruit”.

Voorbeeld 1.8 (De algebraïsche getallen zijn aftelbaar)

Een complex getal heet algebraïsch wanneer het een nulpunt is van een veelterm ongelijk aan nul met rationale coëfficiënten. De verzameling $\overline\Q$ van de algebraïsche getallen is aftelbaar: de veeltermen van graad $\leq d$ over $\Q$ injecteren in $\Q^{d+1}$ , een eindig product van aftelbare verzamelingen (Propositie 1.6 (2)); de vereniging over $d$ somt de veeltermen ongelijk aan nul op als $P_0, P_1, P_2, \dots$ ; elke $P_k$ heeft eindig veel nulpunten; en

\overline\Q = \bigcup_{k \in \N}\ \{\text{nulpunten van } P_k\}

is een aftelbare vereniging van eindige verzamelingen (Propositie 1.6 (3)), oneindig omdat zij $\Q$ bevat. Samen met de overaftelbaarheid van $\R$ (Stelling 1.9 hieronder) bewijst dit — zonder er ook maar één aan te wijzen — dat er transcendente getallen bestaan en dat zij een overaftelbare meerderheid vormen: het telargument van Cantor uit 1874, bestaan louter op grond van kardinaliteit.

Stelling 1.9 (Cantor; overaftelbaarheid van $\R$ )

Voor elke verzameling $E$ bestaat er geen surjectie $E \to \mathcal{P}(E)$ .
$\R$ is niet aftelbaar.

Bewijs. (1) is in het volume van bachelorjaar 1 bewezen (met de diagonaalverzameling $D = \{x : x \notin f(x)\}$ ).

(2) Stel dat $(x_n)_{n \in \N}$ heel $\R$ opsomt. Bouw geneste segmenten $I_0 \supseteq I_1 \supseteq \dots$ met $\abs{I_n} = 3^{-n}$ en $x_n \notin I_n$ : verdeel het huidige segment in drie gesloten derden; minstens één derde vermijdt $x_n$ (een punt raakt hoogstens twee van de drie). De stelling van de geneste segmenten (aanliggende eindpunten) levert $\ell \in \bigcap_n I_n$ ; maar $\ell = x_N$ voor zekere $N$ , terwijl $x_N \notin I_N$ : tegenspraak. ∎

Stelling 1.10 (Cantor–Bernstein)

Injecteert $E$ in $F$ en $F$ in $E$ , dan zijn $E$ en $F$ gelijkmachtig.

Bewijs. Zijn $f \colon E \to F$ en $g \colon F \to E$ injecties. Volg voor elk punt (van $E$ of van $F$ ) zijn voorouderketen van opeenvolgende originelen, $x \mapsto g^{-1}(x) \mapsto f^{-1}(g^{-1}(x)) \mapsto \dots$ — elke stap is gedefinieerd zolang het huidige punt in het beeld van de betreffende injectie ligt, en is dan eenduidig wegens injectiviteit. Er zijn drie elkaar uitsluitende lotgevallen: de keten stopt in een punt van $E \setminus g(F)$ (oorsprong in $E$ ), zij stopt in een punt van $F \setminus f(E)$ (oorsprong in $F$ ), of zij stopt nooit. Dit verdeelt $E = E_E \cup E_F \cup E_\infty$ en $F = F_E \cup F_F \cup F_\infty$ naar de oorsprong.

Merk nu op dat $f$ de verzameling $E_E$ op $F_E$ afbeeldt: de keten van $f(x)$ is die van $x$ met één stap ervoor, dus de oorsprongen komen overeen; en elke $y \in F_E$ heeft een keten met minstens één stap (haar oorsprong ligt in $E$ ), zodat $y = f(x)$ met $x \in E_E$ . Hetzelfde argument geeft bijecties $f \colon E_\infty \to F_\infty$ en $g \colon F_F \to E_F$ . Aan elkaar geplakt is

h(x) = \begin{cases} f(x) & \text{als } x \in E_E \cup E_\infty,\\ g^{-1}(x) & \text{als } x \in E_F, \end{cases}

een bijectie van $E$ op $F = F_E \cup F_\infty \cup F_F$ : zij is stuksgewijs bijectief en de drie stukken van het doel zijn disjunct. ∎

Voorbeeld 1.11

$\intoo{0}{1}$ en $\intcc{0}{1}$ zijn gelijkmachtig: de identiteit injecteert de ene kant op, $x \mapsto \frac{x + 1}{3}$ de andere; de stelling fabriceert vervolgens de (noodzakelijk discontinue) bijectie. Evenzo zijn $\R$ , $\intoo{0}{1}$ (via bijecties van het type $\tanh$ ) en $\mathcal{P}(\N)$ (binaire ontwikkelingen, Oefening 1.3) alle gelijkmachtig: “de machtigheid van het continuüm”.

Voorbeeld 1.12 (Het segment en het vierkant)

$\intcc{0}{1}$ en $\intcc{0}{1}^2$ zijn gelijkmachtig — dimensie is onzichtbaar voor kardinaliteit. De ene injectie is triviaal: $x \mapsto (x, 0)$ . Stuur voor de andere het paar $(x, y)$ naar het reële getal waarvan de decimalen die van $x$ en $y$ afwisselen,

(0.x_1x_2x_3\dots,\ 0.y_1y_2y_3\dots) \;\longmapsto\; 0.x_1y_1x_2y_2x_3y_3\dots,

waarbij we per coördinaat de ontwikkeling kiezen die niet op louter $9$ ’s eindigt: met die afspraak leggen de cijfers van het beeld die van $x$ en $y$ vast, dus is de afbeelding injectief (surjectief hoeft zij niet te zijn — beelden hebben bijvoorbeeld nooit vanaf zeker moment alleen maar $9$ ’s op de oneven posities — en dat is geen bezwaar). Cantor–Bernstein (Stelling 1.10) stelt daaruit een echte bijectie samen. Continuïteit is uiteraard hopeloos: een continue bijectie tussen beide bestaat niet — de hoofdstukken over metrische ruimten leggen uit waarom (samenhang onderscheidt de rechte van het vlak, Hoofdstuk 4).

1.3 Groepen

Definitie 1.13 (Voortgebrachte ondergroep; orde)

Zij $G$ een groep en $A \subseteq G$ . De door $A$ voortgebrachte ondergroep, genoteerd $\langle A \rangle$ , is de kleinste ondergroep die $A$ bevat — concreet: alle eindige producten van elementen van $A$ en hun inversen. Een groep heet cyclisch wanneer zij door één element wordt voortgebracht: $\langle a\rangle = \{a^k : k \in \Z\}$ . De orde van $a \in G$ is $\operatorname{ord}(a) = \abs{\langle a \rangle}$ (eventueel oneindig); is zij eindig, dan is zij de kleinste $n \geq 1$ met $a^n = e$ , en geldt $a^k = e \iff \operatorname{ord}(a) \mid k$ .

Bewijs van de karakterisering van de orde. Geldt $a^m = e$ voor zekere $m \geq 1$ , zij dan $n \geq 1$ de kleinste met $a^n = e$ . De elementen $e, a, \dots, a^{n-1}$ zijn paarsgewijs verschillend (uit $a^{i} = a^{j}$ met $0 \leq i < j < n$ volgt $a^{j-i} = e$ , in strijd met de minimaliteit), en elke $a^k$ herleidt zich via de deling met rest $k = nq + r$ tot een van hen: $\langle a\rangle$ telt precies $n$ elementen, en $a^k = a^r = e \iff r = 0 \iff n \mid k$ . Is geen enkele macht triviaal, dan zijn alle $a^k$ ( $k \in \Z$ ) verschillend (hetzelfde delingsargument) en is de orde oneindig. ∎

Stelling 1.14 (Lagrange)

Zij $G$ een eindige groep en $H$ een ondergroep. Dan deelt $\abs H$ het getal $\abs G$ . In het bijzonder deelt de orde van elk element $\abs G$ , en geldt $a^{\abs G} = e$ voor alle $a \in G$ .

Bewijs. De relatie $x \sim y \iff x^{-1}y \in H$ is een equivalentie (reflexief omdat $e \in H$ ; symmetrisch via inversen; transitief via producten). De klasse van $x$ is de linkernevenklasse $xH = \{xh : h \in H\}$ , en $h \mapsto xh$ is een bijectie $H \to xH$ (met inverse $y \mapsto x^{-1}y$ ): alle klassen tellen $\abs H$ elementen. De klassen verdelen $G$ (de algemene partitiestelling uit het volume van bachelorjaar 1), dus $\abs G = \abs H \times (\text{aantal nevenklassen})$ . Voor een element: pas dit toe op $H = \langle a\rangle$ ; dan is $a^{\abs G} = (a^{\operatorname{ord} a})^{\abs G / \operatorname{ord} a} = e$ . ∎

Voorbeeld 1.15 (Nevenklassen in actie: $A_3$ binnen $\mathfrak{S}_3$ )

Neem $G = \mathfrak{S}_3$ (orde $6$ ) en $H = A_3 = \{\mathrm{id},\ (1\,2\,3),\ (1\,3\,2)\}$ . De linkernevenklassen zijn

H = \{\mathrm{id},\ (1\,2\,3),\ (1\,3\,2)\}, \qquad (1\,2)H = \{(1\,2),\ (2\,3),\ (1\,3)\} :

twee klassen van drie elementen die $G$ verdelen, precies zoals de telling $\abs G = \abs H \times (\text{aantal nevenklassen})$ voorschrijft — en zichtbaar is dit de opsplitsing in even en oneven permutaties. Merk op dat $(1\,3)H = (1\,2)H$ hoewel $(1\,3) \neq (1\,2)$ : nevenklassen zijn klassen, niet gelabeld door hun representanten, en $x^{-1}y \in H$ is de enige legitieme vergelijking. Dit beeld van twee klassen is het algemene beeld voor de signatuur: $A_n$ en zijn enige begeleidende nevenklasse halveren $\mathfrak{S}_n$ , en zo telt de weekendopgave de bereikbare puzzelstanden.

Voorbeeld 1.16

Twee onmiddellijke opbrengsten. Groepen van priemorde zijn cyclisch: is $\abs G = p$ priem en $a \neq e$ , dan deelt $\operatorname{ord}(a)$ het getal $p$ en is zij niet $1$ , dus is zij $p$ : $\langle a\rangle = G$ . Het ondergroepentralie van $\Z/12\Z$ : volgens Propositie 1.17 hieronder is er precies één ondergroep per deler van $12$ — van orde $1, 2, 3, 4, 6, 12$ , achtereenvolgens voortgebracht door $\overline 0$ , $\overline 6$ , $\overline 4$ , $\overline 3$ , $\overline 2$ , $\overline 1$ . Tot slot een waarschuwing: de omkering van Lagrange faalt in het algemeen — $A_4$ heeft orde $12$ maar geen ondergroep van orde $6$ , zoals we in de weekendopgave van dit hoofdstuk bewijzen (Probleem 1.1, vraag 14). Lagrange beperkt de mogelijke orden; hij belooft ze niet.

Het ondergroepentralie van ℤ/12ℤ: één ondergroep per deler van 12 (), met een rib zodra de ene de andere met priemindex bevat. De insluitingen lopen tegen de deelbaarheid van de voortbrenger in: 4 ⊂eq 2 omdat 4 een veelvoud van 2 is. — Het ondergroepentralie van $\Z/12\Z$ : één ondergroep per deler van $12$ (Propositie 1.17), met een rib zodra de ene de andere met priemindex bevat. De insluitingen lopen *tegen* de deelbaarheid van de voortbrenger in: $\langle \overline4\rangle \subseteq \langle\overline2\rangle$ omdat $4$ een veelvoud van $2$ is.

Propositie 1.17 (Cyclische groepen)

Zij $G = \langle a \rangle$ cyclisch van orde $n$ .

$G$ is isomorf met $(\Z/n\Z, +)$ , via $\overline k \mapsto a^k$ .
Elke ondergroep van $G$ is cyclisch; bij elke deler $d \mid n$ hoort precies één ondergroep van orde $d$ , namelijk $\langle a^{n/d}\rangle$ .
$a^k$ brengt $G$ voort dan en slechts dan als $\gcd(k, n) = 1$ : $G$ heeft $\varphi(n)$ voortbrengers (de functie van Euler).

Bewijs. (1) De afbeelding $k \mapsto a^k$ van $\Z$ op $G$ is verenigbaar met de congruentie modulo $n$ ( $a^{k} = a^{k'} \iff n \mid k - k'$ , volgens de karakterisering van de orde); de universele eigenschap (Definitie 1.3) levert een welgedefinieerd bijectief morfisme vanuit $\Z/n\Z$ .

(2) Zij $H \leq G$ niet triviaal en $m$ de kleinste $\geq 1$ met $a^m \in H$ . Deling met rest geeft $H = \langle a^m\rangle$ (voor $a^k \in H$ dwingt $k = mq + r$ dat $a^r \in H$ , dus $r = 0$ ), en $m \mid n$ (deel $n$ door $m$ : $a^{n \bmod m} \in H$ ). Dan is $\abs H = n/m$ ; met $m = n/d$ wordt elke deler $d$ gerealiseerd. Eenduidigheid: elke ondergroep van orde $d$ is volgens het voorgaande van de vorm $\langle a^m \rangle$ met $n/m = d$ — dus ligt $m = n/d$ vast en daarmee de ondergroep.

(3) We beweren dat $\operatorname{ord}(a^k) = \frac{n}{\gcd(k, n)}$ . Schrijf $d = \gcd(k, n)$ . Voor elke $m \geq 1$ geeft de karakterisering van de orde uit Definitie 1.13 de keten van equivalenties

(a^k)^m = e \iff n \mid km \iff \frac{n}{d} \,\Big|\, \frac{k}{d}\,m \iff \frac{n}{d} \,\Big|\, m ,

waarbij de laatste stap op het lemma van Gauss steunt, want $\frac nd$ en $\frac kd$ zijn onderling ondeelbaar. De kleinste zulke $m$ is $\frac nd$ : $\operatorname{ord}(a^k) = \frac n{\gcd(k,n)}$ , en dat is gelijk aan $n$ precies wanneer $\gcd(k, n) = 1$ . Er zijn $\varphi(n)$ zulke klassen $k$ modulo $n$ . ∎

1.4 De symmetrische groep

Definitie 1.18

$\mathfrak{S}_n$ is de groep van de permutaties van $\intint{1}{n}$ (orde $n!$ ). Een cykel $(a_1\,a_2\,\cdots\,a_k)$ beeldt $a_1 \mapsto a_2 \mapsto \dots \mapsto a_k \mapsto a_1$ af en laat al het overige vast; $k$ is haar lengte, en een $2$ -cykel heet een transpositie. Twee cykels zijn disjunct wanneer hun dragers (de niet-vaste punten) dat zijn.

Stelling 1.19 (Ontbinding in cykels)

Elke permutatie $\sigma \neq \mathrm{id}$ is een product van paarsgewijs disjuncte cykels, eenduidig op de volgorde van de factoren na. Disjuncte cykels commuteren, en $\operatorname{ord}(\sigma)$ is het kleinste gemene veelvoud van de lengten.

Bewijs. Beschouw op de drager van $\sigma$ de “baanrelatie”: $x \sim y$ zodra $y = \sigma^k(x)$ voor zekere $k \in \Z$ — een equivalentierelatie. Elke klasse $\{x, \sigma(x), \dots, \sigma^{k-1}(x)\}$ (eindig, zodat de iteraties terugkeren — de eerste herhaling moet wegens injectiviteit $x$ zelf zijn) draagt de cykel $(x\ \sigma(x)\ \cdots\ \sigma^{k-1}(x))$ , en $\sigma$ is het product van deze cykels: op elke baan werkt alleen de bijbehorende cykel. Eenduidigheid: elke ontbinding in disjuncte cykels reproduceert precies de banen (de cykel door $x$ moet $(x\ \sigma(x)\ \cdots)$ zijn). Disjuncte cykels commuteren omdat zij disjuncte punten verplaatsen; de uitspraak over de orde volgt omdat $\sigma^m = \mathrm{id}$ dan en slechts dan als de $m$ -de macht van elke cykel dat is (disjunctheid), dan en slechts dan als elke lengte $m$ deelt. ∎

Voorbeeld 1.20 (Cykeltype als telling)

Hoeveel permutaties van $\mathfrak{S}_9$ hebben cykeltype $(4, 3, 2)$ — één $4$ -cykel, één $3$ -cykel, één transpositie? Kies de dragers en de cyclische volgorden:

\frac{9!}{4\cdot 3\cdot 2} = \frac{362\,880}{24} = 15\,120 :

zet de negen symbolen op een rij ( $9!$ manieren), haak de eerste vier, de volgende drie en de laatste twee in cykels, en deel door de rotaties binnen elk haakje ( $4$ , $3$ en $2$ stuks) die dezelfde permutatie opleveren. (De cykellengten zijn hier verschillend, dus is er geen verdere deling nodig; bij gelijke lengten zou men ook nog door de permutaties van de gelijke haakjes moeten delen.) Elke zulke permutatie heeft orde $\operatorname{lcm}(4,3,2) = 12$ en signatuur $(-1)^3(-1)^2(-1)^1 = +1$ (Stelling 1.19 en de signatuurstelling hieronder). Eén partitie van $9$ , één conjugatieklasse, één telling — de combinatoriek van $\mathfrak{S}_n$ is de rekenkunde van de partities.

Stelling 1.21 (Signatuur)

Er bestaat precies één groepsmorfisme $\varepsilon \colon \mathfrak{S}_n \to \{\pm 1\}$ (voor $n \geq 2$ ) dat op transposities de waarde $-1$ aanneemt: de signatuur. Bovendien is $\varepsilon(\sigma) = (-1)^{I(\sigma)}$ , waarbij $I(\sigma)$ het aantal inversies is (paren $i < j$ met $\sigma(i) > \sigma(j)$ ), heeft een $k$ -cykel signatuur $(-1)^{k-1}$ , en heeft de alternerende groep $A_n = \ker\varepsilon$ orde $\frac{n!}{2}$ .

Bewijs. Bestaan. Zet voor $\sigma \in \mathfrak{S}_n$

\varepsilon(\sigma) = \prod_{1 \leq i < j \leq n} \frac{\sigma(j) - \sigma(i)}{j - i} .

De absolute waarden van de factoren vermenigvuldigen tot $1$ (de ongeordende paren $\{\sigma(i), \sigma(j)\}$ doorlopen alle paren), dus $\varepsilon(\sigma) = (-1)^{I(\sigma)} \in \{\pm1\}$ . Morfisme: voor $\sigma, \tau$ is

\varepsilon(\sigma\tau) = \prod_{i<j} \frac{\sigma(\tau(j)) - \sigma(\tau(i))}{j - i} = \prod_{i<j} \frac{\sigma(\tau(j)) - \sigma(\tau(i))}{\tau(j) - \tau(i)} \cdot \prod_{i<j} \frac{\tau(j) - \tau(i)}{j - i} = \varepsilon(\sigma)\,\varepsilon(\tau),

waarbij het middelste product gelijk is aan $\varepsilon(\sigma)$ na herindexering langs de paren $\{\tau(i), \tau(j)\}$ (elk ongeordend paar komt één keer voor, en teller en noemer wisselen samen van teken). Een transpositie $\tau = (a\,b)$ met $a < b$ heeft een oneven aantal inversies; precies geteld zijn de geïnverteerde paren $(i, j)$ , $i < j$ , met $\tau(i) > \tau(j)$ :

(a, j) \ \text{voor } a < j < b, \qquad (i, b) \ \text{voor } a < i < b, \qquad (a, b) \ \text{zelf},

dat wil zeggen $(b - a - 1) + (b - a - 1) + 1 = 2(b - a) - 1$ stuks, dus oneven. (Alternatief: reken $(1\,2)$ rechtstreeks na, met één inversie, en conjugeer — geconjugeerden hebben dezelfde signatuur, want $\varepsilon$ is een morfisme naar een abelse groep.) Bijgevolg is $\varepsilon((a\,b)) = (-1)^{2(b-a)-1} = -1$ .

Eenduidigheid. Transposities brengen $\mathfrak{S}_n$ voort (elke cykel voldoet aan $(a_1\cdots a_k) = (a_1\,a_k)(a_1\,a_{k-1})\cdots(a_1\,a_2)$ , en Stelling 1.19 maakt het af); een morfisme naar $\{\pm1\}$ ligt vast door zijn waarden op voortbrengers.

Gevolgen. De cykelidentiteit hierboven schrijft een $k$ -cykel als $k - 1$ transposities: signatuur $(-1)^{k-1}$ . Voor $A_n$ : het morfisme $\varepsilon$ is surjectief (transposities bestaan zodra $n \geq 2$ ), en de twee “nevenklassen” $A_n$ en $(1\,2)A_n$ zijn gelijkmachtig en verdelen $\mathfrak{S}_n$ (het argument van Lagrange): $\abs{A_n} = \frac{n!}{2}$ . ∎

Voorbeeld 1.22

$\sigma = \begin{pmatrix} 1&2&3&4&5&6\\ 3&6&5&4&1&2 \end{pmatrix} = (1\,3\,5)(2\,6)$ : orde $\operatorname{lcm}(3,2) = 6$ , signatuur $(-1)^{2}\cdot(-1)^{1} = -1$ . De signatuur is de snelste pariteitstest op schuifelingen — en de motor achter de determinant in Hoofdstuk 2.

Voorbeeld 1.23 (Drie wegen naar één teken)

Zij $\sigma \in \mathfrak{S}_5$ de permutatie die $1, 2, 3, 4, 5$ naar $3, 5, 4, 1, 2$ stuurt. Via cykels: $1 \mapsto 3 \mapsto 4 \mapsto 1$ en $2 \mapsto 5 \mapsto 2$ , dus $\sigma = (1\,3\,4)(2\,5)$ en $\varepsilon(\sigma) = (-1)^{2}(-1)^{1} = -1$ . Via inversies: in de waardenlijst $3, 5, 4, 1, 2$ zijn de paren buiten volgorde $(3,1)$ , $(3,2)$ , $(5,4)$ , $(5,1)$ , $(5,2)$ , $(4,1)$ , $(4,2)$ : zeven stuks, en $(-1)^7 = -1$ . Via transposities: $\sigma = (1\,4)(1\,3)(2\,5)$ , drie factoren, $(-1)^3 = -1$ . Drie berekeningen, één pariteit: de eenduidigheid in Stelling 1.21 garandeert dat geen enkel boekhoudschema ze ooit kan laten botsen — en juist dat maakt $\varepsilon$ bruikbaar als invariant (zie de weekendopgave).

Opmerking 1.24 (Waar de signatuur vandaan verder gaat)

De signatuur is het zaad van drie latere oogsten: zij bouwt de determinant en haar productregel in Hoofdstuk 2; zij levert pariteitsinvarianten voor combinatorische puzzels (de weekendopgave van dit hoofdstuk lost er de vijftienpuzzel mee op); en de alternerende groepen $A_n$ die zij definieert worden centraal in het volume van bachelorjaar 3, waar hun enkelvoudigheid voor $n \geq 5$ verklaart waarom vergelijkingen van graad $5$ niet met wortelvormen op te lossen zijn.

1.5 Ringen, idealen, quotiënten

Definitie 1.25 (Ideaal)

Zij $A$ een commutatieve ring. Een ideaal $I \subseteq A$ is een additieve ondergroep zodanig dat $a x \in I$ voor alle $a \in A$ en $x \in I$ . Kernen van ringmorfismen zijn idealen; er geldt $I = A$ dan en slechts dan als $1 \in I$ , dan en slechts dan als $I$ een eenheid bevat. Het door $x$ voortgebrachte ideaal is $xA = \{xa\}$ (een hoofdideaal).

Stelling 1.26 (Idealen van $\Z$ en van $K[X]$ )

Elk ideaal van $\Z$ is $n\Z$ voor een unieke $n \in \N$ ; elk ideaal van $K[X]$ ( $K$ een lichaam) is $P\,K[X]$ voor een unieke monische (of nul) $P$ . Bijgevolg bestaan er in beide ringen grootste gemene delers met Bézout-relaties: $x\Z + y\Z = \gcd(x,y)\Z$ , en evenzo voor veeltermen.

Bewijs. Voor $\Z$ is dit de ondergroepenstelling uit het volume van bachelorjaar 1 (een ideaal is in het bijzonder een ondergroep, en $n\Z$ is een ideaal). Voor $K[X]$ : zij $I \neq \{0\}$ een ideaal en $P \in I$ ongelijk aan nul van minimale graad, monisch genormeerd. Voor $F \in I$ geeft de deling met rest $F = PQ + R$ dat $R = F - PQ \in I$ met $\deg R < \deg P$ : de minimaliteit dwingt $R = 0$ , dus $I = P\,K[X]$ . Eenduidigheid: twee monische voortbrengers delen elkaar. De uitspraken van Bézout zijn de gelijkheid van het ideaal $x\Z + y\Z$ (respectievelijk zijn veeltermtegenhanger) met het hoofdideaal van de grootste gemene deler — precies de definitie van de ggd die in bachelorjaar 1 gebruikt werd, nu herkend als een uitspraak over idealen. ∎

Voorbeeld 1.27 (Een ggd van veeltermen, langs twee wegen)

Bereken $\gcd(X^3 - 1,\ X^2 - 1)$ in $\Q[X]$ . Via Euclides:

X^3 - 1 = X\,(X^2 - 1) + (X - 1), \qquad X^2 - 1 = (X + 1)(X - 1) + 0 ,

dus de ggd is $X - 1$ , en terugsubstitueren geeft de Bézout-relatie

X - 1 = 1\cdot(X^3 - 1) - X\cdot(X^2 - 1).

Via idealen: het ideaal $(X^3 - 1)\Q[X] + (X^2 - 1)\Q[X]$ is een hoofdideaal (Stelling 1.26); het bevat $X - 1$ (zie de formule hierboven) en het ligt in $(X - 1)\Q[X]$ (beide voortbrengers verdwijnen in $1$ en zijn dus veelvouden van $X - 1$ ): de monische voortbrenger is $X - 1$ . Het inzicht om te onthouden: het idealenstandpunt herkent de ggd zonder te delen — de gemeenschappelijke nulpunten lokaliseren het ideaal, en Euclides bevestigt het slechts.

Definitie 1.28 (Quotiëntring $\Z/n\Z$ , opnieuw bekeken)

Voor een ideaal $I$ van $A$ is de relatie $x \sim y \iff x - y \in I$ een equivalentie die verenigbaar is met $+$ en $\times$ ; de quotiëntverzameling $A/I$ erft een ringstructuur — de quotiëntring — die van $\pi \colon A \to A/I$ een morfisme met kern $I$ maakt. Voor $A = \Z$ en $I = n\Z$ is dit de $\Z/n\Z$ uit het volume van bachelorjaar 1, nu met haar universele eigenschap: elk morfisme dat $I$ doodt, factoriseert over $A/I$ .

Stelling 1.29 (Chinese reststelling, ringvorm)

Als $\gcd(m, n) = 1$ , dan is de afbeelding

\Z/mn\Z \longrightarrow \Z/m\Z \times \Z/n\Z, \qquad \overline{x} \longmapsto (x \bmod m,\; x \bmod n)

een ringisomorfisme. Bijgevolg geldt $\varphi(mn) = \varphi(m)\varphi(n)$ voor onderling ondeelbare $m, n$ , en

\varphi(n) = n \prod_{p \mid n} \Bigl(1 - \frac 1p\Bigr) \quad (p \text{ priem}).

Bewijs. De afbeelding is een welgedefinieerd ringmorfisme (de verenigbaarheden zijn onmiddellijk). Injectiviteit: uit $x \equiv 0$ modulo $m$ en modulo $n$ met $\gcd(m,n) = 1$ volgt $mn \mid x$ (Gauss). Surjectiviteit: beide leden tellen $mn$ elementen, dus volstaat de injectiviteit (gelijke eindige aantallen) — of expliciet: uit een Bézout-relatie $um + vn = 1$ gaat de klasse van

x = b\,um + a\,vn

naar $(a \bmod m,\ b \bmod n)$ , want $vn = 1 - um \equiv 1 \pmod m$ maakt $x \equiv a \pmod m$ , en symmetrisch modulo $n$ — het recept dat numeriek wordt uitgevoerd in Voorbeeld 1.30. Eenheden komen overeen met paren eenheden (de eenheden van een productring zijn juist de paren eenheden), zodat $\varphi(mn) = \varphi(m)\varphi(n)$ . Voor een priemmacht is $\varphi(p^k) = p^k - p^{k-1}$ (de niet-eenheden modulo $p^k$ zijn de veelvouden van $p$ ); de multiplicativiteit zet daaruit de productformule in elkaar. ∎

Voorbeeld 1.30 (Het Chinese isomorfisme omkeren)

Neem $m = 8$ en $n = 9$ . De inverse van het isomorfisme wordt expliciet gemaakt door de twee idempotenten: zoek $u \equiv 1 \pmod 8$ , $u \equiv 0 \pmod 9$ en $v \equiv 0 \pmod 8$ , $v \equiv 1 \pmod 9$ . Uit $u = 9k \equiv 1 \pmod 8$ volgt $k \equiv 1$ , dus $u = 9$ ; uit $v = 8k \equiv 1 \pmod 9$ volgt $-k \equiv 1$ , $k \equiv 8$ , dus $v = 64$ . De klasse van $x = 9a + 64b$ modulo $72$ is dan de unieke oplossing van $x \equiv a \pmod 8$ , $x \equiv b \pmod 9$ : voor $a = 3$ en $b = 5$ krijgt men $27 + 320 = 347 \equiv 59 \pmod{72}$ — precies de tussenwaarde die substitutie oplevert in Oefening 1.8. Het inzicht om te onthouden: $u$ en $v$ voldoen modulo $72$ aan $u + v \equiv 1$ , $uv \equiv 0$ , $u^2 \equiv u$ en $v^2 \equiv v$ ; zij zijn de beelden van $(1, 0)$ en $(0, 1)$ , en elke Chinese ontbinding is uiteindelijk een ontbinding van $1$ in orthogonale idempotenten.

Stelling 1.31 (Euler; Fermat opnieuw)

De eenheden van $\Z/n\Z$ vormen een groep van orde $\varphi(n)$ ; bijgevolg geldt voor $\gcd(a, n) = 1$

a^{\varphi(n)} \equiv 1 \pmod n \qquad (\text{de stelling van Euler}),

en de kleine stelling van Fermat is het geval $n = p$ priem, nu één regel verwijderd van Lagrange.

Bewijs. De inverteerbare klassen zijn precies die van de gehele getallen die onderling ondeelbaar zijn met $n$ (volume van bachelorjaar 1): $\varphi(n)$ stuks, en zij vormen een groep onder de vermenigvuldiging. Lagrange (Stelling 1.14): elk element tot de macht de orde van de groep is de eenheid. ∎

Voorbeeld 1.32 (Een eenhedengroep zonder voortbrenger)

De groep $(\Z/15\Z)^*$ telt $\varphi(15) = \varphi(3)\varphi(5) = 8$ elementen. Is zij cyclisch? Bereken de orden met behulp van het Chinese isomorfisme $(\Z/15\Z)^* \simeq (\Z/3\Z)^* \times (\Z/5\Z)^*$ (een eenheid modulo $15$ is een paar eenheden): de factoren hebben orde $2$ en $4$ , dus deelt de orde van elk element $\operatorname{lcm}(2, 4) = 4 < 8$ — geen enkel element brengt voort. Concreet:

2^4 = 16 \equiv 1, \qquad 4^2 = 16 \equiv 1, \qquad 7^4 \equiv 1, \qquad 11^2 = 121 \equiv 1, \qquad 14^2 \equiv 1 \pmod{15} :

orden $4, 2, 4, 2, 2$ en nooit $8$ . Vergelijk dit met Oefening 1.10: $(\Z/p\Z)^*$ is cyclisch voor priem $p$ , omdat de eenhedengroep daar in een lichaam ligt. De stelling van Euler blijft gelden met exponent $\varphi(15) = 8$ , maar de werkelijke universele exponent is hier $4$ — Euler geeft een bovengrens, niet altijd de scherpste.

Definitie 1.33 (Algebra)

Een $K$ -algebra is een $K$ -vectorruimte $A$ met een ringstructuur waarvan de vermenigvuldiging $K$ -bilineair is. Voorbeelden: $K[X]$ , $\mathcal{M}_n(K)$ , $\mathcal{L}(E)$ , functieruimten $\mathcal{F}(X, K)$ , en $\C$ als $\R$ -algebra. Morfismen van algebra’s zijn lineaire ringmorfismen; de evaluatie $P \mapsto P(u)$ van $K[X]$ naar $\mathcal{L}(E)$ (of $\mathcal{M}_n(K)$ ) is het centrale voorbeeld, en de motor van Hoofdstuk 3.

Voorbeeld 1.34 (Een evaluatiemorfisme en zijn kern)

Neem $A = \begin{pmatrix}0 & 1\\ 0 & 0\end{pmatrix}$ en de evaluatie $\varepsilon_A \colon \R[X] \to \mathcal{M}_2(\R)$ , $P \mapsto P(A)$ . Omdat $A^2 = 0$ is

P(A) = P(0)\,I + P'(0)\,A = \begin{pmatrix} P(0) & P'(0)\\ 0 & P(0)\end{pmatrix},

(alleen de constante en de lineaire term van $P$ overleven). Bijgevolg is $\ker\varepsilon_A = \{P : P(0) = P'(0) = 0\} = X^2\,\R[X]$ : een hoofdideaal, precies zoals Stelling 1.26 voorspelt, voortgebracht door de monische $X^2$ van kleinste graad in de kern — de minimale veelterm van $A$ , hoofdrolspeler in Hoofdstuk 3. Het beeld is de tweedimensionale commutatieve algebra $\{aI + bA\}$ : evaluatiemorfismen krimpen het oneindigdimensionale $\R[X]$ tot kleine, berekenbare algebra’s.

Opmerking 1.35 (Vooruitblik: drie melodieën om op te letten)

Drie structurele ideeën uit dit hoofdstuk keren in het hele volume terug, telkens zwaarder georkestreerd. Factoriseren over een quotiënt (Definitie 1.3): het bouwt hier $\Z/n\Z$ , het definieert afbeeldingen op oplossingsruimten van lineaire stelsels in Hoofdstuk 2, en het ligt stil onder elk argument van het type “welgedefinieerd op klassen”. Invarianten: de signatuur is een morfisme naar $\{\pm1\}$ waar geen enkele toegestane zet omheen kan — dezelfde logica geeft de productregel van de determinant (Hoofdstuk 2), de invariantie van het spoor onder gelijkvormigheid, en de behouden grootheden van Hoofdstuk 16. Tellen tegen een structuur in: Lagrange telt via nevenklassen, dimensie telt via basissen (Hoofdstuk 2), multipliciteit telt via veeltermgraden (Hoofdstuk 3); zodra een grens wonderbaarlijk lijkt, doet ergens een partitie of een gradering het telwerk.

Opmerking 1.36 (Klassieke valkuilen)

Vier klassiekers. (i) Van een afbeelding op een quotiënt moet worden nagegaan dat zij welgedefinieerd is: “ $\overline x \mapsto$ (formule in $x$ )” is alleen legitiem wanneer de formule constant is op de klassen — de verenigbaarheid uit Definitie 1.3, geen formaliteit. (ii) $\operatorname{ord}(ab) = \operatorname{lcm}(\operatorname{ord}a, \operatorname{ord}b)$ is in het algemeen onjuist, zelfs voor commuterende elementen ( $a$ en $a^{-1}$ ); Oefening 1.4 geeft de juiste uitspraak onder commutatie en onderlinge ondeelbaarheid, en disjuncte cykels de juiste versie voor permutaties. (iii) Aftelbaarheid overleeft aftelbare verenigingen en eindige producten, maar geen aftelbare producten: $\{0,1\}^{\N}$ is overaftelbaar (Oefening 1.3) hoewel elke factor twee elementen heeft. (iv) Cantor–Bernstein heeft alleen injecties in beide richtingen nodig, maar de bijectie die de stelling bouwt is doorgaans discontinu en niet expliciet — verwacht er geen formule voor (Voorbeeld 1.11).

Opmerking 1.37 (Waar dit hoofdstuk wordt gebruikt)

Vrijwel overal. De signatuur bouwt determinanten (Hoofdstuk 2); het evaluatiemorfisme $P \mapsto P(u)$ en de hoofdidealen van $K[X]$ leveren de minimale veeltermen en de kernontbindingen van Hoofdstuk 3; aftelbaarheid is het toneel waarop Hoofdstuk 21 speelt (kansrekening op aftelbare ruimten) en de reden dat de topologie telkens weer aftelbare dichte verzamelingen produceert (Hoofdstuk 4). De quotiëntconstructie $A/I$ wordt in het volume van bachelorjaar 3 opnieuw ingezet om lichamen $K[X]/(P)$ te bouwen en daaruit de Galoistheorie: de universele eigenschap die hier bewezen is, wordt daar woordelijk gebruikt.

1.6 Oefeningen

Oefening 1.1 ★

Welke van de volgende verzamelingen zijn aftelbaar? De verzameling van de eindige deelverzamelingen van $\N$ ; de verzameling van alle deelverzamelingen van $\N$ ; $\R \setminus \Q$ ; de verzameling van de veeltermen met rationale coëfficiënten; de verzameling van de rijen van $0$ ’en en $1$ ’en die vanaf zeker moment nul zijn.

Oplossing

Oplossing van Oefening 1.1.

Eindige deelverzamelingen van $\N$ : aftelbaar — de verzameling van de deelverzamelingen van $\intint{0}{n}$ is eindig, en de eindige deelverzamelingen vormen de aftelbare vereniging daarvan over $n$ (Propositie 1.6 (3)); oneindig, want zij bevat alle eenpuntsverzamelingen.

Alle deelverzamelingen van $\N$ : niet aftelbaar, wegens de stelling van Cantor (Stelling 1.9 (1) met $E = \N$ ).

$\R \setminus \Q$ : niet aftelbaar — anders zou $\R = \Q \cup (\R\setminus\Q)$ een vereniging van twee aftelbare verzamelingen zijn, in strijd met Stelling 1.9 (2).

Veeltermen over $\Q$ : aftelbaar — de veeltermen van graad $\leq n$ injecteren in $\Q^{n+1}$ (eindige producten van aftelbare verzamelingen), en neem de vereniging over $n$ .

Binaire rijen die vanaf zeker moment nul zijn: aftelbaar — zij staan in bijectie met de eindige deelverzamelingen van $\N$ (hun drager).

Oefening 1.2 ★

Zij in $\mathfrak{S}_7$ gegeven $\sigma = (1\,4\,2\,6)(3\,5)$ en $\tau = (2\,3\,7)$ . Bereken $\sigma\tau$ en $\tau\sigma$ in disjuncte cykels, de orden en signaturen van alle vier de permutaties, en $\sigma^{2026}$ .

Oplossing

Oplossing van Oefening 1.2.

Reken element voor element, met de rechterfactor eerst. Nu stuurt $\sigma\tau$ de elementen $1 \mapsto \sigma(1) = 4$ , $\;2 \mapsto \sigma(3) = 5$ , $\;3 \mapsto \sigma(7) = 7$ , $\;4 \mapsto \sigma(4) = 2$ , $\;5 \mapsto \sigma(5) = 3$ , $\;6 \mapsto \sigma(6) = 1$ , $\;7 \mapsto \sigma(2) = 6$ :

\sigma\tau = (1\,4\,2\,5\,3\,7\,6),

een $7$ -cykel. Evenzo stuurt $\tau\sigma$ de elementen $1 \mapsto \tau(4) = 4$ , $\;2 \mapsto \tau(6) = 6$ , $\;3 \mapsto \tau(5) = 5$ , $\;4 \mapsto \tau(2) = 3$ , $\;5 \mapsto \tau(3) = 7$ , $\;6 \mapsto \tau(1) = 1$ , $\;7 \mapsto \tau(7) = 2$ :

\tau\sigma = (1\,4\,3\,5\,7\,2\,6),

eveneens een $7$ -cykel (zoals te verwachten was: $\sigma\tau$ en $\tau\sigma$ zijn geconjugeerd en hebben dus hetzelfde cykeltype).

Orden en signaturen: $\sigma$ heeft cykeltype $(4,2)$ : orde $\operatorname{lcm}(4,2) = 4$ , signatuur $(-1)^3(-1)^1 = +1$ ; $\tau$ is een $3$ -cykel: orde $3$ , signatuur $+1$ ; beide producten zijn $7$ -cykels: orde $7$ , signatuur $(-1)^6 = +1$ .

$\sigma^{2026}$ : uit $2026 = 4 \times 506 + 2$ volgt $\sigma^{2026} = \sigma^2 = (1\,2)(4\,6)$ (kwadrateer de $4$ -cykel; de transpositie kwadrateert weg).

Oefening 1.3 ★

Construeer expliciete injecties die aantonen dat $\mathcal{P}(\N)$ , $\intcc{0}{1}$ en de verzameling $\{0,1\}^{\N}$ van de binaire rijen paarsgewijs gelijkmachtig zijn (binaire ontwikkelingen in beide richtingen; Cantor–Bernstein neemt het ongemak van de dubbele voorstelling weg).

Oplossing

Oplossing van Oefening 1.3.

$\{0,1\}^{\N} \to \mathcal{P}(\N)$ : een rij gaat naar haar drager — een bijectie (indicatorfuncties), geen stelling nodig.

$\{0,1\}^{\N} \to \intcc{0}{1}$ : de afbeelding in grondtal $3$ , $(a_n) \mapsto \sum 2a_n 3^{-n-1}$ , is injectief (twee verschillende rijen verschillen voor het eerst op rang $N$ ; de staarten kunnen een sprong van $2\cdot 3^{-N-1}$ niet compenseren, want $\sum_{n > N} 2\cdot 3^{-n-1} = 3^{-N-1} < 2\cdot3^{-N-1}$ ).

$\intcc{0}{1} \to \{0,1\}^{\N}$ : de binaire ontwikkeling, waarbij we (zeg) de ontwikkeling kiezen die niet op louter $1$ ’en eindigt: injectief.

Cantor–Bernstein (Stelling 1.10) toegepast op de laatste twee injecties geeft dat $\intcc{0}{1}$ en $\{0,1\}^{\N}$ gelijkmachtig zijn, en dus alle drie de verzamelingen.

Oefening 1.4 ★

Zij $G$ een groep en zijn $a, b \in G$ commuterende elementen van eindige, onderling ondeelbare orden $m$ en $n$ . Bewijs dat $\operatorname{ord}(ab) = mn$ . Toon met een voorbeeld in $\mathfrak{S}_3$ aan dat de commutatie onmisbaar is.

Oplossing

Oplossing van Oefening 1.4.

Zij $c = ab = ba$ en $d = \operatorname{ord}(c)$ . Om te beginnen is $c^{mn} = a^{mn} b^{mn} = e$ (dankzij de commutatie mag de macht worden gesplitst), dus $d \mid mn$ . Omgekeerd geeft $c^d = e$ dat $a^d = b^{-d}$ ; dit element ligt in $\langle a\rangle \cap \langle b\rangle$ , een ondergroep waarvan de orde zowel $m$ als $n$ deelt (Lagrange in elk van beide cyclische groepen) en die dus triviaal is: $a^d = b^d = e$ , zodat $m \mid d$ en $n \mid d$ , en wegens de onderlinge ondeelbaarheid $mn \mid d$ . Bijgevolg is $d = mn$ .

In $\mathfrak{S}_3$ : neem $a = (1\,2)$ (orde $2$ ) en $b = (1\,2\,3)$ (orde $3$ ), met onderling ondeelbare orden, die niet commuteren: $ab = (2\,3)$ heeft orde $2 \neq 6$ — $\mathfrak{S}_3$ heeft immers geen element van orde $6$ . De commutatie is dus onmisbaar.

Oefening 1.5 ★★

Zij $G$ een eindige groep van even orde. Bewijs dat $G$ een element van orde $2$ bevat. (Koppel elk element aan zijn inverse en tel de elementen die aan zichzelf gekoppeld zijn.)

Oplossing

Oplossing van Oefening 1.5.

Koppel elke $x \in G$ aan $x^{-1}$ . De paren $\{x, x^{-1}\}$ met $x \neq x^{-1}$ tellen twee elementen en verdelen hun vereniging; de overige elementen zijn precies die met $x = x^{-1}$ , dat wil zeggen $x^2 = e$ . Omdat $\abs G$ even is en de tweetallige paren een even aantal elementen bedekken, heeft de verzameling $\{x : x^2 = e\}$ een even aantal elementen; zij bevat $e$ , dus bevat zij minstens nog één ander element $x \neq e$ — een element van orde $2$ .

Oefening 1.6 ★★

Bewijs dat $A_n$ ( $n \geq 3$ ) door de $3$ -cykels wordt voortgebracht. (Een product van twee transposities is een $3$ -cykel of een product van twee $3$ -cykels.)

Oplossing

Oplossing van Oefening 1.6.

Elk element van $A_n$ is een product van een even aantal transposities (Stelling 1.21: ontbind in transposities; het aantal is even omdat de signatuur $+1$ is). Het volstaat dus elk product van twee transposities met $3$ -cykels te schrijven:

(a\,b)(a\,c) = (a\,c\,b), \qquad (a\,b)(c\,d) = (a\,c\,b)(a\,c\,d) \quad (\text{verschillende } a,b,c,d),

(na te gaan door te evalueren), en $(a\,b)(a\,b) = \mathrm{id}$ . De $3$ -cykels brengen dus $A_n$ voort.

Oefening 1.7 ★★

Bepaal alle groepsmorfismen: van $(\Q, +)$ naar $(\Z, +)$ ; van $(\Z/n\Z, +)$ naar $(\Z/m\Z, +)$ (tel ze: $\gcd(m,n)$ ); van $(\Q, +)$ naar $(\Q_+^*, \times)$ .

Oplossing

Oplossing van Oefening 1.7.

$(\Q,+) \to (\Z,+)$ : alleen het nulmorfisme. Voor elke $x$ en elke $n \geq 1$ is $f(x) = n f\bigl(\frac xn\bigr)$ deelbaar door $n$ in $\Z$ ; het enige gehele getal dat door elke $n$ deelbaar is, is $0$ , dus $f(x) = 0$ voor alle $x$ .

$(\Z/n\Z, +) \to (\Z/m\Z, +)$ : een morfisme ligt vast door $c = f(\overline 1)$ , dat aan $n c \equiv 0 \pmod m$ moet voldoen, dat wil zeggen: $c$ is een veelvoud van $\frac{m}{\gcd(m,n)}$ ; er zijn $\gcd(m,n)$ zulke klassen, en elke keuze definieert ook werkelijk een morfisme (factoriseer $k \mapsto kc$ over $\Z/n\Z$ met de universele eigenschap).

$(\Q, +) \to (\Q_+^*, \times)$ : alleen het triviale. Is $f(x) = y$ , dan is $y = f(n \cdot \frac xn) = f(\frac xn)^n$ voor elke $n$ een $n$ -de macht in $\Q_+^*$ . Maar een rationaal getal $y \neq 1$ kan niet voor alle $n$ een $n$ -de macht zijn: een zeker priemgetal komt in $y$ voor met een exponent $v \neq 0$ , en $n \nmid v$ zodra $n > \abs v$ (exponenten van $n$ -de machten zijn veelvouden van $n$ , wegens de eenduidige factorisatie). Bijgevolg is $f \equiv 1$ .

Oefening 1.8 ★★

Bereken met de Chinese reststelling $\varphi(360)$ , bepaal alle $x$ met $x \equiv 3 \pmod 8$ , $x \equiv 5 \pmod 9$ en $x \equiv 2 \pmod 5$ , en bereken de laatste twee cijfers van $3^{2026}$ (Euler modulo $100$ ; let op: werk modulo $4$ en modulo $25$ ).

Oplossing

Oplossing van Oefening 1.8.

Uit $360 = 2^3 \cdot 3^2 \cdot 5$ volgt $\varphi(360) = 360\bigl(1 - \tfrac12\bigr)\bigl(1 - \tfrac13\bigr)\bigl(1 - \tfrac15\bigr) = 360 \cdot \tfrac12 \cdot \tfrac23 \cdot \tfrac45 = 96$ .

Het stelsel: de moduli $8, 9, 5$ zijn paarsgewijs onderling ondeelbaar, met product $360$ . Uit $x \equiv 3 \pmod 8$ en $x \equiv 5 \pmod 9$ : $x = 3 + 8k$ met $3 + 8k \equiv 5 \pmod 9$ , dus $-k \equiv 2$ , $k \equiv -2 \equiv 7 \pmod 9$ : $x \equiv 3 + 56 = 59 \pmod{72}$ . Vervolgens $59 + 72\ell \equiv 2 \pmod 5$ : $4 + 2\ell \equiv 2$ , $2\ell \equiv 3 \equiv 8$ , $\ell \equiv 4 \pmod 5$ : $x \equiv 59 + 288 = 347 \pmod{360}$ .

De laatste twee cijfers van $3^{2026}$ : modulo $4$ is $3^{2026} = 9^{1013} \equiv 1$ . Modulo $25$ : $\varphi(25) = 20$ en $2026 = 20\cdot101 + 6$ , dus $3^{2026} \equiv 3^6 = 729 \equiv 4 \pmod{25}$ . Los $x \equiv 1 \pmod 4$ , $x \equiv 4 \pmod{25}$ op: uit $x = 4 + 25k \equiv 1 \pmod 4$ volgt $k \equiv 1 \pmod 4$ , dus $x \equiv 29 \pmod{100}$ . De laatste twee cijfers zijn $29$ .

Oefening 1.9 ★★★

Bewijs dat een eindig integriteitsgebied een lichaam is. Leid daaruit (opnieuw) af dat $\Z/n\Z$ een lichaam is dan en slechts dan als $n$ priem is.

Oplossing

Oplossing van Oefening 1.9.

Zij $A$ een eindig integriteitsgebied en $a \in A$ met $a \neq 0$ . De afbeelding $x \mapsto ax$ is injectief ( $ax = ay \implies a(x - y) = 0 \implies x = y$ , want er zijn geen nuldelers); een injectieve afbeelding van een eindige verzameling naar zichzelf is surjectief (volume van bachelorjaar 1, de equivalentie met het duivenhokprincipe). Dus is $1 = ab$ voor zekere $b$ : elk element ongelijk aan nul is inverteerbaar en $A$ is een lichaam.

Voor $\Z/n\Z$ : is $n$ priem, dan is het een integriteitsgebied ( $n \mid ab \implies n \mid a$ of $n \mid b$ , het lemma van Euclides), eindig, en dus een lichaam; is $n = rs$ samengesteld, dan levert $\overline r\,\overline s = \overline 0$ nuldelers.

Oefening 1.10 ★★★

(Een klassieker) Zij $K$ een lichaam en $G$ een eindige ondergroep van $(K^*, \times)$ . Bewijs dat $G$ cyclisch is. Aanwijzing: zij $m$ de maximale orde onder de elementen van $G$ ; toon aan dat de orde van elk element $m$ deelt (gebruik Oefening 1.4 op geschikte onderling ondeelbare delen), zodat heel $G$ aan $x^m = 1$ voldoet; tel vervolgens de nulpunten van $X^m - 1$ . In het bijzonder is $(\Z/p\Z)^*$ cyclisch.

Oplossing

Oplossing van Oefening 1.10.

Zij $m = \max\{\operatorname{ord}(x) : x \in G\}$ , aangenomen in $a$ .

Bewering: de orde van elke $x \in G$ deelt $m$ . Stel dat een zekere $x$ orde $q$ heeft met $q \nmid m$ : dan deelt een zekere priemmacht $p^k$ wel $q$ maar niet $m$ . Schrijf $m = p^j m'$ met $p \nmid m'$ en $j < k$ . Het element $a^{p^j}$ heeft orde $m'$ ; het element $x^{q/p^k}$ heeft orde $p^k$ ; deze orden zijn onderling ondeelbaar en de twee elementen commuteren ( $G \subseteq K^*$ is abels), dus heeft hun product volgens Oefening 1.4 orde $p^k m' > p^j m' = m$ : in strijd met de maximaliteit.

Alle $x \in G$ voldoen dus aan $x^m = 1$ : de veelterm $X^m - 1$ heeft minstens $\abs G$ nulpunten in het lichaam $K$ , waaruit $\abs G \leq m$ volgt (een veelterm van graad $m$ ongelijk aan nul heeft hoogstens $m$ nulpunten, volume van bachelorjaar 1). Maar $m = \operatorname{ord}(a) \leq \abs G$ volgens Lagrange. Dus is $m = \abs G$ en is $\langle a \rangle$ , met $m = \abs G$ elementen, heel $G$ : cyclisch.

Voor $K = \Z/p\Z$ : $(\Z/p\Z)^*$ is een eindige ondergroep van $K^*$ en dus cyclisch (van orde $p - 1$ ).

Oefening 1.11 ★★★

Bewijs dat de groep $(\Q, +)$ niet cyclisch is, en sterker nog: dat zij niet eens eindig voortgebracht is. Bewijs anderzijds dat elke eindig voortgebrachte ondergroep van $(\Q, +)$ cyclisch is.

Oplossing

Oplossing van Oefening 1.11.

Niet cyclisch: de ondergroep $\langle \frac pq\rangle$ bestaat uit de gehele veelvouden van $\frac pq$ , en die hebben alle een noemer die $q$ deelt (in vereenvoudigde vorm); zij mist dus $\frac{1}{2q}$ . Geen enkele voortbrenger kan de onbegrensde noemers van $\Q$ bereiken.

Niet eindig voortgebracht: de ondergroep voortgebracht door $\frac{p_1}{q_1}, \dots, \frac{p_k}{q_k}$ bestaat uit rationale getallen waarvan de noemer $Q = q_1 \cdots q_k$ deelt (gehele combinaties hebben een noemer die $Q$ deelt): zij mist $\frac{1}{2Q}$ .

Eindig voortgebrachte ondergroepen zijn cyclisch: met $Q$ als hierboven ligt de ondergroep $H = \langle \frac{p_1}{q_1}, \dots, \frac{p_k}{q_k}\rangle$ in $\frac{1}{Q}\Z$ . De afbeelding $x \mapsto Qx$ is een isomorfisme van $\frac1Q\Z$ op $\Z$ dat $H$ naar een ondergroep van $\Z$ brengt, en die is $n\Z$ voor zekere $n$ (volume van bachelorjaar 1): dus is $H = \frac{n}{Q}\Z$ cyclisch, voortgebracht door $\frac nQ$ .

Oefening 1.12 ★★

(Criterium van Dedekind) Bewijs dat elke oneindige verzameling een aftelbare deelverzameling bevat, en leid daaruit af dat een verzameling $E$ oneindig is dan en slechts dan als zij gelijkmachtig is met een echte deelverzameling van zichzelf. (Voor de rechtstreekse implicatie: verschuif een aftelbare deelverzameling één stap; voor de omkering: denk aan het duivenhokprincipe.)

Oplossing

Oplossing van Oefening 1.12.

Een aftelbare deelverzameling. Zij $E$ oneindig. Construeer $a_0, a_1, a_2, \dots$ inductief: $E$ is niet leeg, kies $a_0 \in E$ ; zijn $a_0, \dots, a_n$ gekozen, dan is $E \setminus \{a_0, \dots, a_n\}$ niet leeg ( $E$ is niet eindig), kies daarin $a_{n+1}$ . De $a_n$ zijn per constructie paarsgewijs verschillend, dus is $A = \{a_n : n \in \N\}$ een aftelbare deelverzameling van $E$ .

Oneindig $\implies$ gelijkmachtig met een echte deelverzameling. Definieer $f \colon E \to E \setminus \{a_0\}$ door $f(a_n) = a_{n+1}$ en $f(x) = x$ voor $x \notin A$ . Zij is injectief (beide stukken zijn injectief met disjuncte beelden) en surjectief op $E \setminus \{a_0\}$ : elke $a_{n+1}$ wordt bereikt en elke $x \notin A$ ook. Dus is $E$ gelijkmachtig met de echte deelverzameling $E \setminus \{a_0\}$ .

Omkering. Is $E$ eindig en $g \colon E \to F$ een bijectie op $F \subseteq E$ met $F \neq E$ , dan is $g$ een injectie van $E$ in zichzelf die niet surjectief is, in strijd met het duivenhokprincipe (volume van bachelorjaar 1: een injectieve afbeelding van een eindige verzameling naar zichzelf is bijectief). Een verzameling die gelijkmachtig is met een echte deelverzameling, is dus oneindig.

1.7 Probleem: De vijftienpuzzel

De vijftienpuzzel is een bakje van $4 \times 4$ met vijftien schuivende plaatjes, genummerd van $1$ tot $15$ , en één lege plek; een zet schuift een plaatje dat aan de lege plek grenst daarin. In de jaren 1890 maakte Sam Loyd de puzzel beroemd door $1000 uit te loven aan wie de plaatjes $14$ en $15$ zou verwisselen en alle overige plaatjes op hun plaats zou terugzetten. Niemand heeft dat geld ooit opgehaald, en deze weekendopgave bewijst beide helften van de reden: de signatuur uit Stelling 1.21 verbiedt Loyds verwisseling, en — de moeilijkere, constructieve helft — alles wat de signatuur toelaat is werkelijk oplosbaar. De volledige uitspraak is de stelling van Johnson en Story (1879).

De opgeloste stand en de 14–15-stand van Sam Loyd. De vraag van $1000: kunnen toegestane zetten het rechterbakje in het linker veranderen? — De opgeloste stand en de $14$ – $15$ -stand van Sam Loyd. De vraag van $1000: kunnen toegestane zetten het rechterbakje in het linker veranderen?

Probleem 1.1

Weekendopgave — de oplosbaarheidsstelling van Johnson en Story

Nummer de vakjes van $1$ tot $16$ in leesvolgorde (van links naar rechts, van boven naar beneden), zodat vakje $k$ in rij $i$ en kolom $j$ ligt met $k = 4(i - 1) + j$ . Vakje $16$ (rechtsonder) is het thuis van de lege plek; we behandelen de lege plek als een zestiende plaatje, geschreven als $b$ en vereenzelvigd met het getal $16$ . Een stand is een bijectie $\sigma \colon \intint1{16} \to \intint1{16}$ , vakje $\mapsto$ inhoud; de opgeloste stand is $\sigma = \mathrm{id}$ . Overal is $\varepsilon$ de signatuur uit Stelling 1.21, en twee vakjes heten buren wanneer zij een rib van het bakje delen.

Deel I — Standen, zetten, signaturen.

Verantwoord dat de standen precies de elementen van $\mathfrak{S}_{16}$ zijn, zodat er $16! = 20\,922\,789\,888\,000$ van zijn, en dat het aantal toegestane zetten vanuit een gegeven stand $2$ , $3$ of $4$ bedraagt, naargelang de lege plek in een hoek, aan een rand of in het inwendige ligt.
Zij $\sigma$ een stand, $p = \sigma^{-1}(16)$ het vakje van de lege plek en $c$ een vakje dat aan $p$ grenst. Toon aan dat het schuiven van het plaatje van $c$ naar $p$ de stand $\sigma' = \sigma \circ \tau$ oplevert met $\tau = (p\ c)$ , en leid af dat elke zet de signatuur omklapt: $\varepsilon(\sigma') = -\varepsilon(\sigma)$ .
Kleur het bakje als een schaakbord: $\chi(k) = (-1)^{i+j}$ voor het vakje $k$ in rij $i$ en kolom $j$ . Toon aan dat elke zet $\chi(\text{vakje van de lege plek})$ omklapt, en leid af dat een reeks zetten die de lege plek naar haar beginvakje terugbrengt, een even lengte heeft.
Toon aan dat

$I(\sigma) = \varepsilon(\sigma)\, \chi\bigl(\sigma^{-1}(16)\bigr)$

onder elke toegestane zet invariant is, en bereken $I(\mathrm{id})$ .

Deel II — Loyds prijsvraag: de invariant aan het werk.

Loyds stand $\sigma_L$ stemt met de opgeloste stand overeen, behalve dat de vakjes $14$ en $15$ de plaatjes $15$ en $14$ dragen. Bereken $I(\sigma_L)$ en besluit dat geen enkele reeks zetten $\sigma_L$ met de opgeloste stand verbindt: Loyds $1000 heeft nooit gevaar gelopen.
Toon aan dat precies de helft van alle standen aan $I = +1$ voldoet: $\abs{\{\sigma : I(\sigma) = +1\}} = 16!/2$ . (Koppel, bij vast vakje voor de lege plek, de standen aan elkaar door met één vaste transpositie van twee andere vakjes samen te stellen.)
Toon aan dat elke zet door een toegestane zet ongedaan wordt gemaakt, dat “ $\sigma'$ is vanuit $\sigma$ bereikbaar met toegestane zetten” een equivalentierelatie is, en dat de klasse $R$ van de opgeloste stand voldoet aan $R \subseteq \{I = +1\}$ . Besluit dat er minstens twee klassen zijn.
Neem aan dat de lege plek thuis is: $\sigma(16) = 16$ . Toon aan dat $I(\sigma) = \varepsilon(\rho)$ , waarbij $\rho \in \mathfrak{S}_{15}$ de beperking van $\sigma$ tot de vakjes $1, \dots, 15$ is, en dat elke stand met toegestane zetten naar een stand met de lege plek thuis kan worden gebracht. Besluit: om $R = \{I = +1\}$ te bewijzen volstaat het elke even permutatie van de vijftien niet-thuisvakjes te realiseren met een reeks zetten die begint en eindigt met de lege plek thuis.

Deel III — Rondgangen van de lege plek en de programmagroep. Een programma is een eindige reeks toegestane zetten, gestart vanuit een stand met de lege plek thuis, waarvan de eindstand de lege plek opnieuw thuis heeft. Het effect ervan is de permutatie $\pi$ van de vakjes gedefinieerd door: de inhoud van vakje $x$ eindigt in vakje $\pi(x)$ .

Toon aan dat een programma dat vanuit $\sigma$ wordt uitgevoerd in $\sigma \circ \pi^{-1}$ eindigt; dat twee programma’s na elkaar hun effecten samenstellen; en dat de verzameling $H$ van alle effecten een ondergroep van $\mathfrak{S}_{15}$ is (permutaties van de vakjes $1, \dots, 15$ ) die in de alternerende groep $A_{15}$ ligt.
(De elementaire rondgang) Schuif, met de lege plek thuis, de lege plek rond het blok van $2 \times 2$ rechtsonder: vakjes $16 \to 12 \to 11 \to 15 \to 16$ . Toon aan dat het effect de $3$ -cykel $(11\ 12\ 15)$ is, en dat de omgekeerde rondgang $(11\ 15\ 12)$ geeft. Beide liggen in $H$ .
(De grote rondgang) Ga na dat

$16 \to 15 \to 14 \to 13 \to 9 \to 5 \to 1 \to 2 \to 3 \to 4 \to 8 \to 7 \to 6 \to 10 \to 11 \to 12 \to 16$

een gesloten wandeling door alle zestien vakjes is (uitsluitend stappen tussen buren), en dat het effect ervan de $15$ -cykel

$\zeta = (15\ 12\ 11\ 10\ 6\ 7\ 8\ 4\ 3\ 2\ 1\ 5\ 9\ 13\ 14)$

is. Schrijf $x_0 = 15$ , $x_1 = 12$ , $x_2 = 11$ , …, $x_{14} = 14$ voor haar cyclische volgorde, en ga na dat de omgekeerde elementaire rondgang uit vraag 10 precies $(x_0\ x_1\ x_2)$ is.
Bewijs de conjugatieformule in elke $\mathfrak{S}_n$ : voor een permutatie $g$ en een $3$ -cykel geldt

$g\,(a\ b\ c)\,g^{-1} = \bigl(g(a)\ g(b)\ g(c)\bigr),$

en merk op dat $H$ , als groep, gesloten is onder conjugatie door haar eigen elementen.
Leid af dat $H$ alle vijftien opeenvolgende $3$ -cykels van de grote rondgang bevat:

$s_t = (x_t\ x_{t+1}\ x_{t+2}) \qquad (t \in \Z/15\Z, \text{ indices modulo } 15).$

Deel IV — De alternerende groep voortbrengen.

(Lemma A) Zijn $s$ en $t$ $3$ -cykels waarvan de dragers precies twee punten gemeen hebben, zeg de dragers $\{a, b, c\}$ en $\{b, c, d\}$ . Toon aan dat, na eventueel $s$ of $t$ door zijn inverse te vervangen (wat aan de voortgebrachte ondergroep niets verandert), het product $st$ een dubbele transpositie is; toon aan dat $A_4$ geen ondergroep van orde $6$ bevat (een ondergroep van index $2$ bevat elk kwadraat; tel de $3$ -cykels onder de kwadraten); en besluit dat $\langle s, t\rangle$ de volledige alternerende groep op de vier letters $\{a, b, c, d\}$ is.
(Lemma B) Zij $X$ een verzameling van $k \geq 4$ letters, $w \notin X$ , en zij $G$ een ondergroep van een $\mathfrak{S}_n$ die elke even permutatie van $X$ bevat en bovendien één $3$ -cykel $(u\ v\ w)$ met $u, v \in X$ . Toon aan dat er voor alle verschillende $a, b \in X$ een even permutatie $g$ van $X$ bestaat met $g(u) = a$ en $g(v) = b$ , en leid af dat $(a\ b\ w) \in G$ .
Leid af dat de groep $G$ uit Lemma B elke even permutatie van $X \cup \{w\}$ bevat (gebruik Oefening 1.6: de $3$ -cykels brengen voort). Bewijs vervolgens, door de Lemma’s A en B aaneen te schakelen langs de opeenvolgende $3$ -cykels $s_0, s_1, \dots, s_{12}$ uit vraag 13, dat $\langle s_0, \dots, s_{12}\rangle = A_{15}$ .
Besluit dat $H = A_{15}$ : elke even herschikking van de vijftien plaatjes is met een programma te bereiken, en $H$ telt $15!/2 = 653\,837\,184\,000$ elementen.
(De stelling van Johnson en Story, 1879) Zet de vragen 6, 7, 8 en 17 aaneen: de standen die vanuit de opgeloste stand bereikbaar zijn, zijn precies de $16!/2 = 10\,461\,394\,944\,000$ standen met $I = +1$ ; en de bereikbaarheid heeft precies twee klassen, die van de opgeloste stand en die van Loyds $\sigma_L$ . (Voor het tweede punt: hernoem de plaatjes $14$ en $15$ en toon aan dat $\sigma \mapsto (14\ 15) \circ \sigma$ reeksen zetten op reeksen zetten afbeeldt en $\{I = +1\}$ met $\{I = -1\}$ verwisselt.)

Deel V — Criteria, varianten en het uitzicht van bovenaf.

(Het praktische criterium) Lees de vijftien plaatjes in de leesvolgorde van hun vakjes, sla de lege plek over, en zij $N$ het aantal inversies van deze lijst; zij $r$ de rij van de lege plek, geteld vanaf onderen. Toon aan dat $I(\sigma) = (-1)^{N + r + 1}$ , zodat $\sigma$ oplosbaar is dan en slechts dan als $N + r$ oneven is.
(Groepsacties) Een actie van een groep $G$ op een verzameling $X$ is een afbeelding $G \times X \to X$ , $(g, x) \mapsto g \cdot x$ , met $e \cdot x = x$ en $g \cdot (h \cdot x) = (gh) \cdot x$ ; de baan van $x$ is $G \cdot x$ , en de actie heet vrij wanneer uit $g \cdot x = x$ volgt dat $g = e$ . Toon aan dat $h \cdot \sigma = \sigma \circ h^{-1}$ een vrije actie van $H$ op de verzameling van de standen met de lege plek thuis definieert, dat haar banen precies de klassen van wederzijdse bereikbaarheid met programma’s zijn, en haal uit het aantal banen terug dat deze standen in precies $15!\,/\,\abs H = 2$ klassen uiteenvallen.
(De hindernis bij $3 \times 3$ ) Toon aan dat het bord van $3 \times 3$ geen gesloten wandeling toelaat die elk vakje precies één keer bezoekt: de strategie met de grote rondgang uit Deel III faalt voor de achtpuzzel. (Kleur de negen vakjes als een schaakbord.)
(De reparatie) Op het bord van $3 \times 3$ met de vakjes $1$ tot $9$ in leesvolgorde en thuis $9$ : bereken de effecten van de rondgang langs de rand $9 \to 8 \to 7 \to 4 \to 1 \to 2 \to 3 \to 6 \to 9$ (een $7$ -cykel $\zeta'$ die het midden $5$ vasthoudt) en van de hoekrondgang $9 \to 6 \to 5 \to 8 \to 9$ (een $3$ -cykel door het midden). Bewijs, door de laatste met de machten van $\zeta'$ te conjugeren en de Lemma’s A en B aaneen te schakelen, dat de programmagroep van de achtpuzzel heel $A_8$ is, en dus dat precies $9!/2 = 181\,440$ van de $9! = 362\,880$ standen oplosbaar zijn.
(Een arm bord) Zij het bord nu één enkele cykel van $n \geq 4$ vakjes met $n - 1$ plaatjes. Toon aan dat de cyclische volgorde van de plaatjes invariant is, dat elke bereikbaarheidsklasse precies $n(n - 1)$ standen telt (de klassen zijn de banen van een cyclische groep van orde $\operatorname{lcm}(n, n-1) = n(n-1)$ ), en dat er $(n - 2)!$ klassen zijn — voor $n \geq 5$ veel meer dan $2$ : op een smal bord vangt de pariteitsinvariant vrijwel niets, en heerst de meetkunde.
Twee uitspraken volgens het criterium van vraag 19: het volledig omgekeerde bakje (plaatjes $15, 14, \dots, 1$ in de vakjes $1$ tot $15$ , lege plek thuis) en het bakje met de lege plek in vakje $1$ , gevolgd door de plaatjes $15, 14, \dots, 1$ in de vakjes $2$ tot $16$ . Welk van beide is oplosbaar?
(Synthese) Het bewijs rust op twee onafhankelijke pijlers: een invariant ( $I$ , gebouwd op het signatuurmorfisme) die aantoont dat hoogstens de helft van de standen bereikbaar is, en een stelling over expliciete voortbrenging ( $H = A_{15}$ ) die aantoont dat minstens de helft dat is. Zeg in telkens één zin waar de volgende zaken zijn binnengekomen: de morfisme-eigenschap van $\varepsilon$ ; de stelling van Lagrange; de voortbrenging van $A_n$ door $3$ -cykels; conjugatie. Formuleer het metaprincipe in één regel.

Oplossing

Oplossing van Probleem 1.1.

1. Een stand kent aan elk van de $16$ vakjes precies één van de $16$ inhouden toe (de plaatjes $1$ – $15$ of de lege plek $b = 16$ ), elk precies één keer: dat is juist een bijectie $\intint1{16} \to \intint1{16}$ , een element van $\mathfrak{S}_{16}$ ; er zijn er $16! = 20\,922\,789\,888\,000$ . Een toegestane zet schuift één plaatje dat aan de lege plek grenst, dus is het aantal zetten gelijk aan het aantal buren van het vakje van de lege plek: $2$ voor de vier hoekvakjes, $3$ voor de acht randvakjes en $4$ voor de vier inwendige vakjes.

2. Na het schuiven draagt vakje $p$ de vroegere inhoud van $c$ en draagt vakje $c$ de lege plek; alle andere vakjes blijven onaangeroerd: $\sigma'(p) = \sigma(c)$ , $\sigma'(c) = \sigma(p) = 16$ en $\sigma' = \sigma$ elders. Dat is precies $\sigma' = \sigma \circ (p\ c)$ . Omdat $\varepsilon$ een morfisme is en $\varepsilon\bigl((p\ c)\bigr) = -1$ , volgt $\varepsilon(\sigma') = -\varepsilon(\sigma)$ .

3. Buurvakjes verschillen precies in één van de twee coördinaten één stap, dus verandert $i + j$ van pariteit: $\chi$ neemt op buurvakjes tegengestelde waarden aan. Een zet brengt de lege plek van $p$ naar het aangrenzende $c$ en klapt daarmee $\chi(\text{vakje van de lege plek})$ om. Langs een gesloten wandeling van de lege plek wordt $\chi$ per zet één keer omgeklapt en keert zij terug naar haar beginwaarde: het aantal zetten is even.

4. Volgens de vragen 2 en 3 klapt één zet beide factoren van $I(\sigma) = \varepsilon(\sigma)\chi(\sigma^{-1}(16))$ om; hun product verandert dus niet. Voor de opgeloste stand: $\varepsilon(\mathrm{id}) = +1$ en de lege plek ligt in vakje $16$ , rij $4$ , kolom $4$ : $\chi(16) = (-1)^{8} = +1$ , dus $I(\mathrm{id}) = +1$ .

5. $\sigma_L$ is de transpositie $(14\ 15)$ van vakjes: $\varepsilon(\sigma_L) = -1$ ; haar lege plek is thuis, $\chi(16) = +1$ : $I(\sigma_L) = -1 \neq +1 = I(\mathrm{id})$ . Omdat $I$ door elke zet bewaard blijft, verbindt geen enkele reeks zetten $\sigma_L$ met $\mathrm{id}$ . De prijs was structureel veilig.

6. Leg een vakje $p$ vast en twee andere vakjes $c \neq d$ verschillend van $p$ , en zet $\tau_0 = (c\ d)$ . Op de verzameling van de standen met de lege plek in $p$ is $\sigma \mapsto \sigma \circ \tau_0$ een involutie (zij bewaart $\sigma(p) = 16$ omdat $\tau_0$ het vakje $p$ vasthoudt) die $\varepsilon$ omklapt en dus ook $I$ : zij koppelt de standen met $I = +1$ bijectief aan die met $I = -1$ . Elk van de $16$ posities van de lege plek levert dus $15!/2$ standen met $I = +1$ , en

\abs{\{I = +1\}} = 16 \cdot \frac{15!}{2} = \frac{16!}{2}.

7. De zet die het plaatje van $c$ naar $p$ schuift, wordt ongedaan gemaakt door datzelfde plaatje (nu in $p$ ) terug naar $c$ te schuiven: twee keer met $(p\ c)$ samenstellen geeft de identiteit. Daaruit volgen reflexiviteit (de lege reeks), symmetrie (draai de reeks om en maak elke zet ongedaan) en transitiviteit (plak de reeksen aan elkaar): een equivalentierelatie. Elke $\sigma \in R$ voldoet volgens vraag 4 aan $I(\sigma) = I(\mathrm{id}) = +1$ , dus $R \subseteq \{I = +1\}$ ; en $\sigma_L \notin R$ levert een tweede klasse.

8. Is $\sigma(16) = 16$ , dan permuteert $\sigma$ de vakjes $1, \dots, 15$ ; noem $\rho$ die beperking. Een vast punt toevoegen verandert noch het cykeltype noch de signatuur (ontbind $\rho$ in transposities; hetzelfde product werkt in $\mathfrak{S}_{16}$ ), dus $\varepsilon(\sigma) = \varepsilon(\rho)$ , en met $\chi(16) = +1$ krijgen we $I(\sigma) = \varepsilon(\rho)$ . Elke stand kan naar een stand met de lege plek thuis worden gebracht: het rooster is samenhangend, dus wandel de lege plek langs een pad van buurvakjes naar vakje $16$ (elke stap is een toegestane zet). Neem nu aan dat elke even $\rho \in \mathfrak{S}_{15}$ door een programma wordt gerealiseerd. Zij $\sigma$ gegeven met $I(\sigma) = +1$ : wandel de lege plek naar huis en bereik zo $\widetilde\sigma$ (equivalent met $\sigma$ ), met $I(\widetilde\sigma) = +1$ , dat wil zeggen: haar beperking $\rho$ is even; het programma dat $\rho$ realiseert brengt $\widetilde\sigma$ naar $\widetilde\sigma \circ \rho^{-1} = \mathrm{id}$ (zie vraag 9). Wegens de transitiviteit is $\sigma \in R$ , waaruit $\{I = +1\} \subseteq R$ en dus de gelijkheid.

9. Eén zet: de inhoud van $c$ belandt in $p$ en de lege plek in $c$ : het effect is $\pi = (p\ c)$ , en inderdaad is $\sigma' = \sigma \circ (p\ c) = \sigma \circ \pi^{-1}$ . Inductie: heeft een reeks effect $\pi_1$ en brengt zij $\sigma$ naar $\sigma \circ \pi_1^{-1}$ , dan geeft een daaropvolgende zet met effect $\pi_2 = (p'\ c')$ het resultaat $(\sigma \circ \pi_1^{-1}) \circ \pi_2^{-1} = \sigma \circ (\pi_2\pi_1)^{-1}$ , en de inhouden verplaatsen zich volgens $\pi_2 \circ \pi_1$ (eerst $\pi_1$ , dan $\pi_2$ ). Effecten stellen zich dus samen, en een programma dat vanuit $\sigma$ wordt uitgevoerd eindigt in $\sigma \circ \pi^{-1}$ . Ondergroep: het lege programma heeft effect $\mathrm{id}$ ; aaneenschakelen geeft producten; een programma omdraaien (vraag 7) geeft inversen. Het effect van een programma houdt vakje $16$ vast (de lege plek begint en eindigt thuis), dus $H \leq \mathfrak{S}_{15}$ . Pariteit: een programma van $k$ zetten heeft $k$ even (vraag 3), en $\varepsilon(\sigma \circ \pi^{-1}) = (-1)^k\varepsilon(\sigma)$ dwingt $\varepsilon(\pi) = +1$ : $H \subseteq A_{15}$ .

10. Volg de vier schuifbewegingen vanuit de lege plek in $16$ : de zet $16 \to 12$ brengt de inhoud van $12$ naar $16$ ; de zet $12 \to 11$ brengt de inhoud van $11$ naar $12$ ; de zet $11 \to 15$ brengt de inhoud van $15$ naar $11$ ; de zet $15 \to 16$ brengt de inhoud die in $16$ geparkeerd stond (oorspronkelijk die van $12$ ) naar $15$ . Netto: $11 \mapsto 12$ , $12 \mapsto 15$ , $15 \mapsto 11$ , lege plek thuis: het effect is $(11\ 12\ 15)$ . De omgekeerde rondgang maakt dit ongedaan: effect $(11\ 12\ 15)^{-1} = (11\ 15\ 12)$ . Beide zijn effecten van programma’s en liggen dus in $H$ .

11. Aangrenzendheid van de opeenvolgende vakjes: binnen elk genoemd paar verschillen de vakjes $1$ binnen dezelfde rij ( $16{-}15$ , $15{-}14$ , $14{-}13$ ; $1{-}2$ , $2{-}3$ , $3{-}4$ ; $8{-}7$ , $7{-}6$ ; $10{-}11$ , $11{-}12$ ) of $4$ binnen dezelfde kolom ( $13{-}9$ , $9{-}5$ , $5{-}1$ ; $4{-}8$ ; $6{-}10$ ; $12{-}16$ ): een gesloten wandeling door alle $16$ vakjes, van lengte $16$ . Effect: net als in vraag 10, met de bezochte vakjes $c_0 = 16, c_1 = 15, \dots, c_{15} = 12$ , gaat de inhoud van $c_i$ naar $c_{i-1}$ voor $i = 2, \dots, 15$ , en wordt de inhoud van $c_1$ , na de eerste zet geparkeerd in $16$ , door de laatste zet naar $c_{15}$ gebracht. Het effect stuurt dus $15 \mapsto 12$ , en $14 \mapsto 15$ , $13 \mapsto 14$ , $9 \mapsto 13$ , $5 \mapsto 9$ , $1 \mapsto 5$ , $2 \mapsto 1$ , $3 \mapsto 2$ , $4 \mapsto 3$ , $8 \mapsto 4$ , $7 \mapsto 8$ , $6 \mapsto 7$ , $10 \mapsto 6$ , $11 \mapsto 10$ , $12 \mapsto 11$ : precies de $15$ -cykel $\zeta$ . Haar cyclische volgorde begint met $x_0 = 15$ , $x_1 = 12$ , $x_2 = 11$ , en $(x_0\ x_1\ x_2) = (15\ 12\ 11)$ stuurt $15 \mapsto 12 \mapsto 11 \mapsto 15$ — en dat is precies $(11\ 15\ 12)$ , de omgekeerde elementaire rondgang.

12. Zij $\gamma = (a\ b\ c)$ en $x \in \intint1n$ . Is $x = g(a)$ , dan $g\gamma g^{-1}(x) = g(\gamma(a)) = g(b)$ ; evenzo gaat $g(b) \mapsto g(c)$ en $g(c) \mapsto g(a)$ . Is $x \notin \{g(a), g(b), g(c)\}$ , dan ligt $g^{-1}(x) \notin \{a,b,c\}$ vast onder $\gamma$ , dus ligt ook $x$ vast. Bijgevolg is $g\gamma g^{-1} = (g(a)\ g(b)\ g(c))$ . En voor $g, h \in H$ is $ghg^{-1} \in H$ volgens de ondergroepaxioma’s.

13. Er geldt $\zeta \in H$ (vraag 11) en $s_0 = (x_0\ x_1\ x_2) \in H$ (vragen 10–11). Omdat $\zeta(x_i) = x_{i+1}$ (indices modulo $15$ ), geeft vraag 12

\zeta^{t}\,s_0\,\zeta^{-t} = \bigl(\zeta^t(x_0)\ \zeta^t(x_1)\ \zeta^t(x_2)\bigr) = (x_t\ x_{t+1}\ x_{t+2}) = s_t \in H \qquad (t = 0, 1, \dots, 14).

14. Op inverteren na mogen we aannemen dat $s = (a\ b\ c)$ en $t = (b\ c\ d)$ (een $3$ -cykel op $\{a,b,c\}$ is $(a\ b\ c)$ of haar inverse; evenzo op $\{b,c,d\}$ ; een voortbrenger door zijn inverse vervangen laat $\langle s, t\rangle$ ongemoeid). Met $t$ eerst toegepast is dan

st \colon a \mapsto b,\quad b \mapsto a,\quad c \mapsto d,\quad d \mapsto c, \qquad\text{dus}\quad st = (a\ b)(c\ d),

een dubbele transpositie. De ondergroep $G = \langle s, t\rangle$ bestaat uit even permutaties van de vier letters, dus $G \leq A_4$ en $\abs G \mid 12$ ; zij bevat een element van orde $3$ en een van orde $2$ , dus $6 \mid \abs G$ (Lagrange, Stelling 1.14, toegepast op de twee cyclische ondergroepen). Had $A_4$ een ondergroep $K$ van orde $6$ , dan zou die index $2$ hebben, en dan zou $g^2 \in K$ gelden voor elke $g \in A_4$ : voor $g \in K$ is dat duidelijk; voor $g \notin K$ zijn $K$ en $gK$ de enige nevenklassen, dus is $g^2K$ gelijk aan $K$ of aan $gK$ , en $g^2K = gK$ zou $g \in K$ afdwingen. Elk kwadraat ligt dus in $K$ . Maar elke $3$ -cykel $\gamma$ is een kwadraat, $\gamma = (\gamma^2)^2$ , en $A_4$ bevat acht $3$ -cykels: $8 > 6$ , tegenspraak. Bijgevolg is $\abs G = 12$ , dus $G = A_4$ .

15. Breid $u \mapsto a$ , $v \mapsto b$ uit tot een bijectie $g_0$ van $X$ (stuur de overige $k - 2$ letters bijectief waarheen dan ook op het complement van $\{a, b\}$ ). Is $g_0$ oneven, kies dan twee verschillende letters $s_1, t_1 \in X \setminus \{u, v\}$ (mogelijk want $k \geq 4$ ) en vervang $g_0$ door $g_0 \circ (s_1\ t_1)$ , dat even is en nog steeds $u \mapsto a$ , $v \mapsto b$ stuurt. Breid buiten $X$ uit met de identiteit: een even permutatie $g \in G$ (het is een even permutatie van $X$ ). Vraag 12 geeft dan

g\,(u\ v\ w)\,g^{-1} = (g(u)\ g(v)\ g(w)) = (a\ b\ w) \in G,

met gebruik van $g(w) = w$ .

16. Elke $3$ -cykel van $X \cup \{w\}$ ligt in $G$ : die met drager binnen $X$ zijn even permutaties van $X$ ; een met drager $\{a, b, w\}$ is $(a\ b\ w)$ of $(b\ a\ w)$ , en beide worden door vraag 15 geleverd. Volgens Oefening 1.6 brengen de $3$ -cykels van de $(k+1)$ -elementige verzameling $X \cup \{w\}$ haar alternerende groep voort, dus bevat $G$ elke even permutatie van $X \cup \{w\}$ . Aaneenschakelen: zij $G = \langle s_0, \dots, s_{12}\rangle$ . Lemma A toegepast op $s_0 = (x_0\ x_1\ x_2)$ en $s_1 = (x_1\ x_2\ x_3)$ (de dragers delen $\{x_1, x_2\}$ ) geeft alle even permutaties van $X_4 = \{x_0, x_1, x_2, x_3\}$ . Bevat $G$ alle even permutaties van $X_m = \{x_0, \dots, x_{m-1}\}$ ( $4 \leq m \leq 14$ ), dan heeft $s_{m-2} = (x_{m-2}\ x_{m-1}\ x_m)$ de letters $u = x_{m-2}, v = x_{m-1} \in X_m$ en de nieuwe letter $w = x_m$ : Lemma B en het eerste deel geven alle even permutaties van $X_{m+1}$ . Inductie tot $m = 14$ : $G \supseteq A_{15}$ (even permutaties van alle vijftien vakjes), en $G \subseteq A_{15}$ omdat elke $s_t$ even is: $\langle s_0, \dots, s_{12}\rangle = A_{15}$ .

17. Vragen 13 en 16 geven $A_{15} = \langle s_0, \dots, s_{12}\rangle \subseteq H$ ; vraag 9 geeft $H \subseteq A_{15}$ . Dus $H = A_{15}$ , van orde $15!/2 = 653\,837\,184\,000$ : elke even herschikking van de vijftien plaatjes is het effect van een programma.

18. Vraag 8 herleidde $R = \{I = +1\}$ tot het realiseren van elke even $\rho \in \mathfrak{S}_{15}$ door een programma: dat is met vraag 17 gedaan. Samen met vraag 6 geeft dit $\abs R = 16!/2 = 10\,461\,394\,944\,000$ . Twee klassen: laat $t_0 = (14\ 15)$ op de inhouden werken: $\varphi(\sigma) = t_0 \circ \sigma$ . Een toegestane zet vanuit $\sigma$ is een toegestane zet vanuit $\varphi(\sigma)$ (het vakje van de lege plek verandert niet: $(t_0\sigma)^{-1}(16) = \sigma^{-1}(t_0(16)) = \sigma^{-1}(16)$ , en het verschoven vakje is hetzelfde), en $\varphi(\sigma \circ \tau) = \varphi(\sigma) \circ \tau$ : $\varphi$ beeldt reeksen zetten bijectief op reeksen zetten af (het is een involutie). Zij klapt $I$ om: $\varepsilon(t_0\sigma) = -\varepsilon(\sigma)$ , bij hetzelfde vakje voor de lege plek. Bijgevolg beeldt $\varphi$ de klasse $R = \{I = +1\}$ van $\mathrm{id}$ bijectief af op de klasse van $\varphi(\mathrm{id}) = \sigma_L$ , die dus heel $\{I = -1\}$ is: precies twee klassen. Dat is de stelling van Johnson en Story.

19. Nummer de vakjes in leesvolgorde en zij $k = 4(i - 1) + j$ het vakje van de lege plek. Tel de inversies van $\sigma$ (paren vakjes $x < y$ met $\sigma(x) > \sigma(y)$ ): paren van twee plaatjesvakjes leveren $N$ ; voor de paren waarin de lege plek voorkomt geldt dat alle vakjes na de lege plek plaatjes $< 16$ dragen en dus geïnverteerd zijn ( $16 - k$ paren), terwijl de vakjes ervóór nooit geïnverteerd zijn. Dus is $\varepsilon(\sigma) = (-1)^{N + 16 - k} = (-1)^{N + k}$ . Omdat $k = 4(i-1) + j \equiv j \pmod 2$ , volgt

I(\sigma) = (-1)^{N + j}\,(-1)^{i + j} = (-1)^{N + i} = (-1)^{N + r + 1}

met $i = 5 - r$ . Volgens vraag 18 is $\sigma$ oplosbaar dan en slechts dan als $I(\sigma) = +1$ , dan en slechts dan als $N + r$ oneven is. Controle: opgelost, $N = 0$ , $r = 1$ : oneven, dus oplosbaar; Loyd, $N = 1$ , $r = 1$ : even, dus onoplosbaar.

20. Actie: $e \cdot \sigma = \sigma \circ \mathrm{id} = \sigma$ en $g \cdot (h \cdot \sigma) = \sigma \circ h^{-1} \circ g^{-1} = \sigma \circ (gh)^{-1} = (gh) \cdot \sigma$ ; bovendien is $\sigma \circ h^{-1}$ opnieuw een stand met de lege plek thuis ( $h$ houdt vakje $16$ vast). Vrij: uit $\sigma \circ h^{-1} = \sigma$ volgt $h^{-1} = \mathrm{id}$ (stel samen met $\sigma^{-1}$ ). Banen = programmaklassen: vraag 9 zegt dat de standen die vanuit $\sigma$ met programma’s bereikbaar zijn precies de $\sigma \circ \pi^{-1}$ met $\pi \in H$ zijn: de baan $H \cdot \sigma$ . Telling: de vrijheid maakt $h \mapsto h \cdot \sigma$ injectief, dus telt elke baan $\abs H = 15!/2$ elementen; de $15!$ standen met de lege plek thuis vallen daarmee uiteen in $15!\,/\,(15!/2) = 2$ banen — de schaduw, bij lege plek thuis, van de twee klassen van Johnson en Story.

21. Het rooster van $3 \times 3$ is bipartiet voor de schaakbordkleuring: elke stap van een wandeling verandert de kleur, dus heeft elke gesloten wandeling een even lengte. Een gesloten wandeling die elk van de $9$ vakjes precies één keer bezoekt zou lengte $9$ hebben, oneven: onmogelijk. De constructie met de grote rondgang uit Deel III is dus niet beschikbaar voor de achtpuzzel.

22. Rondgang langs de rand $9 \to 8 \to 7 \to 4 \to 1 \to 2 \to 3 \to 6 \to 9$ (alle stappen tussen buren; lengte $8$ , even): met de boekhouding van vraag 11 en $c_1 = 8, c_2 = 7, c_3 = 4, c_4 = 1, c_5 = 2, c_6 = 3, c_7 = 6$ is het effect

\zeta' = (8\ 6\ 3\ 2\ 1\ 4\ 7),

een $7$ -cykel die het midden $5$ vasthoudt (de inhoud van $7$ gaat naar $8$ , die van $4$ naar $7$ , die van $1$ naar $4$ , die van $2$ naar $1$ , die van $3$ naar $2$ , die van $6$ naar $3$ , en die van $8$ naar $6$ ). Hoekrondgang $9 \to 6 \to 5 \to 8 \to 9$ : effect $(6\ 8\ 5)$ (de inhoud van $5$ gaat naar $6$ , die van $8$ naar $5$ , en die van $6$ — geparkeerd in $9$ — naar $8$ ). Zet $y_t = \zeta'^{\,t}(8)$ : $y_0 = 8, y_1 = 6, y_2 = 3, y_3 = 2, y_4 = 1, y_5 = 4, y_6 = 7$ . Conjugatie (vraag 12) geeft

\zeta'^{\,t}\,(6\ 8\ 5)\,\zeta'^{-t} = (y_{t+1}\ y_t\ 5) =: T_t \in H_{3\times3},

want $\zeta'$ houdt $5$ vast. De dragers van $T_0 = (y_1\ y_0\ 5)$ en $T_1 = (y_2\ y_1\ 5)$ delen precies $\{y_1, 5\}$ : Lemma A geeft alle even permutaties van $\{y_0, y_1, y_2, 5\}$ . Vervolgens voegt $T_2 = (y_3\ y_2\ 5)$ met Lemma B de letter $y_3$ toe (haar letters $y_2, 5$ liggen in de huidige verzameling, $k = 4$ ), en voegen $T_3, T_4, T_5$ achtereenvolgens $y_4, y_5, y_6$ toe: alle even permutaties van de acht niet-thuisvakjes liggen in de programmagroep, die zelf ook uit even permutaties bestaat (het argument van vraag 9 hangt niet van het bord af). Dus is $H_{3\times3} = A_8$ , en de redenering van de vragen 6, 8 en 18 — eveneens onafhankelijk van het bord — laat zien dat de bereikbare standen precies die met $I = +1$ zijn: de helft van $9!$ , dat wil zeggen $181\,440$ .

23. Nummer de vakjes $0, \dots, n-1$ langs de cykel. Een zet verwisselt de lege plek met een van haar twee buren. Lees de plaatjes in cyclische volgorde, beginnend net na de lege plek: een woord $w$ dat de $n - 1$ plaatjes opsomt. De lege plek één stap vooruit bewegen vervangt $(p, w)$ door $(p + 1, \rho w)$ , waarbij $p$ het vakje van de lege plek is en $\rho$ het woord cyclisch één plaats roteert; de zet achteruit is de inverse. De cyclische volgorde van de plaatjes (het woord op rotatie na) is dus invariant. De bereikbaarheidsklasse van $(p, w)$ is de baan van de afbeelding $g \colon (p, w) \mapsto (p+1, \rho w)$ , een element van orde $\operatorname{lcm}(n, n-1) = n(n-1)$ in het product van de twee cyclische groepen (translaties van $\Z/n\Z$ en rotaties van de $n-1$ woordposities), waarbij het kleinste gemene veelvoud $n(n-1)$ is omdat $\gcd(n, n-1) = 1$ : elke klasse telt precies $n(n-1)$ standen, alle met hetzelfde halssnoer. Aantal klassen: $n!\,/\,\bigl(n(n-1)\bigr) = (n-2)!$ . Voor $n \geq 5$ is $(n-2)! > 2$ : de pariteitsinvariant (hoogstens twee klassen) is blind voor bijna de hele hindernis; de rijkdom van het bord van $4 \times 4$ — waar de pariteit de enige hindernis is — is een echt meetkundig feit, geen formeel feit.

24. Beide bakjes hebben de plaatjes in volledig omgekeerde volgorde, dus is in beide gevallen $N = \binom{15}{2} = 105$ (elk paar plaatjes is geïnverteerd). Lege plek thuis: $r = 1$ , $N + r = 106$ even: onoplosbaar. Lege plek in vakje $1$ : de lege plek staat in de bovenste rij, $r = 4$ , $N + r = 109$ oneven: oplosbaar. Twee bakjes die alleen verschillen in waar het gat zit, vallen aan weerszijden van de muur.

25. Morfisme-eigenschap: zij zet “één zet = één transpositie” om in “één zet = één tekenwissel” (vragen 2 en 4), en maakt $I$ zo zet voor zet berekenbaar. Lagrange: hij dwong $6 \mid \abs{\langle s, t\rangle}$ af in Lemma A en bepaalde de grootte van de nevenklassen bij het uitsluiten van orde $6$ (vraag 14). Voortbrenging door $3$ -cykels: zij zette “ $H$ bevat genoeg $3$ -cykels” om in “ $H$ bevat heel $A_{15}$ ” (vraag 16). Conjugatie: zij fabriceerde de vijftien opeenvolgende $3$ -cykels uit één enkele rondgang van $2 \times 2$ , meegevoerd door de grote rondgang (vragen 12–13), en de $3$ -cykels $(a\ b\ w)$ in Lemma B. Metaprincipe: een invariant bewijst onmogelijkheid, een expliciete constructie bewijst mogelijkheid, en een probleem is pas volledig opgelost wanneer de twee grenzen elkaar raken — hier op precies de helft.

Begrippen gedefinieerd in dit hoofdstuk

Bekijk alle 395 begrippen in de begrippenlijst