Universitaire wiskunde — Bachelor jaar 2 · Bachelor Year 2

1Verzamelingen en structuren

Dit openingshoofdstuk slijpt de fundamenten uit het Bachelor jaar 1-volume tot werkinstrumenten van het vak: de calculus van verzamelingen en quotiënten, de vergelijking van oneindige verzamelingen (aftelbaarheid, Cantor–Bernstein), en de structurele theorie van groepen en ringen — de stelling van Lagrange, de symmetrische groep met haar signatuur, idealen en de Chinese reststelling. Alles hier wordt onophoudelijk gebruikt in de rest van het boek: de signatuur bouwt de determinant (Hoofdstuk 2), quotiëntringen drijven de rekenkunde, en aftelbaarheid ligt ten grondslag aan zowel topologie als waarschijnlijkheidsrekening.

1.1 Verzamelingen, afbeeldingen, quotiënten

We gebruiken vrijelijk de taal van verzamelingen, afbeeldingen en equivalentie- en orderelaties die in het Bachelor jaar 1-volume is opgezet. Twee verfijningen verdienen een ordentelijke uitspraak.

Propositie 1.1 (Beelden en originelen van families)

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

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 een uitwerking 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 beeldidentiteiten en het falen van de gelijkheid in het doorsnedengeval (met de injectiviteitscorrectie) zijn in het Bachelor jaar 1-volume bewezen voor twee verzamelingen; de argumenten zijn identiek voor families. ∎

Voorbeeld 1.2 (Waar de beeldinclusie 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

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 inclusie van Propositie 1.1 is zo strikt als maar kan — de twee originelen $\pm x$ van een gemeenschappelijke waarde leven in verschillende $A_i$ . Injectiviteit is precies wat deze splitsing verbiedt, en daarom voldoen originelen (die nooit punten samenvoegen) onvoorwaardelijk aan alle vier de identiteiten, terwijl beelden die over doorsneden verliezen. Vuistregel voor het hele boek: duw originelen vrijelijk door verzamelingsoperaties; behandel beelden met zorg.

Definitie 1.3 (Quotiëntverzameling)

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

Universele eigenschap (factorisatie): als $f \colon E \to F$ compatibel is met $\mathcal{R}$ (d.w.z. $x \mathbin{\mathcal{R}} y \implies f(x) = f(y)$ ), bestaat er precies één afbeelding $\overline f \colon E/\mathcal{R} \to F$ met $f = \overline f \circ \pi$ .

Bewijs van de universele eigenschap. Uniciteit: 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)$ : de waarden van $\overline f$ zijn alle gedwongen. Bestaan: neem de weergave als de definitie van $\overline f$ ; ze is eenduidig precies door compatibiliteit — als $\mathrm{cl}(x) = \mathrm{cl}(y)$ , dan $x \mathbin{\mathcal{R}} y$ , dus $f(x) = f(y)$ en de twee kandidaatwaarden stemmen overeen — en ze factoriseert $f$ per constructie. Merk de arbeidsverdeling op: surjectiviteit van $\pi$ geeft uniciteit, compatibiliteit geeft bestaan. ∎

Voorbeeld 1.4

$\Z/n\Z$ is het quotiënt van $\Z$ door congruentie modulo $n$ ; de welgedefinieerdheidscontroles van het Bachelor jaar 1-volume waren gevallen van de universele eigenschap. Quotiënten maken van “compatibele constructies op representanten” eerlijke afbeeldingen — we gebruiken dit voortdurend hieronder.

1.2 Aftelbaarheid en kardinaliteit

Definitie 1.5 (Gelijkmachtigheid, aftelbaarheid)

Twee verzamelingen zijn gelijkmachtig wanneer een bijectie ze verbindt. Een verzameling is aftelbaar wanneer ze gelijkmachtig is met $\N$ (sommige auteurs nemen 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 desda ze injecteert in $\N$ desda ze 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 unie van hoogstens aftelbare verzamelingen is hoogstens aftelbaar.
$\Z$ en $\Q$ zijn aftelbaar.

Bewijs. (1) Sorteer een oneindige $A \subseteq \N$ door herhaalde minima: $a_0 = \min A$ , $a_{k+1} = \min\,(A \setminus \{a_0, \dots, a_k\})$ (niet-leeg omdat $A$ oneindig is); 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$ , dus wordt bereikt). Als $E$ injecteert in $\N$ via $\varphi$ , is $E$ gelijkmachtig met $\varphi(E) \subseteq \N$ : eindig of aftelbaar. Als $s \colon \N \to E$ surjectief is, injecteert $x \mapsto \min s^{-1}(\{x\})$ $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 een unieke oneven–even-splitsing $2^p m$ met $m$ oneven, door unieke factorisatie). Producten: stel injecties samen.

(3) Gegeven verzamelingen $E_n$ met surjecties $s_n \colon \N \to E_n$ (onschadelijk als sommige $E_n$ eindig is: herhaal waarden), is de afbeelding $(n, k) \mapsto s_n(k)$ een surjectie van de aftelbare $\N^2$ op $\bigcup E_n$ .

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

Voorbeeld 1.7 (Een paarfunctie, uitgewerkt)

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 gehele getallen $n$ waarvoor $n + 1$ precies deelbaar is door $2^p$ : elk natuurlijk getal verschijnt precies één keer. Decodering is even expliciet als codering: voor $n = 43$ , factoriseer $n + 1 = 44 = 2^2\cdot 11 = 2^2(2\cdot5 + 1)$ , dus $(p, q) = (2, 5)$ . Het sluitende inzicht: bewijzen van aftelbaarheid zijn vaak algoritmen in vermomming — hier, “factoriseer de tweeën uit”.

Voorbeeld 1.8 (De algebraïsche getallen zijn aftelbaar)

Een complex getal is algebraïsch wanneer het een niet-nulle veelterm met rationale coëfficiënten annuleert. De verzameling $\overline\Q$ van algebraïsche getallen is aftelbaar: veeltermen van graad $\leq d$ over $\Q$ injecteren in $\Q^{d+1}$ , een eindig product van aftelbare verzamelingen (Propositie 1.6 (2)); de unie over $d$ enumereert de niet-nulle rationale veeltermen als $P_0, P_1, P_2, \dots$ ; elke $P_k$ heeft eindig veel wortels; en

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

is een aftelbare unie van eindige verzamelingen (Propositie 1.6 (3)), oneindig aangezien ze $\Q$ bevat. Gecombineerd met de overaftelbaarheid van $\R$ (Stelling 1.9 hieronder) bewijst dit — zonder er een enkele te tonen — dat transcendentale getallen bestaan en een overaftelbare meerderheid vormen: Cantors telargument van 1874, bestaan louter door 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 bewezen in het Bachelor jaar 1-volume (de diagonaalverzameling $D = \{x : x \notin f(x)\}$ ).

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

Stelling 1.10 (Cantor–Bernstein)

Als $E$ injecteert in $F$ en $F$ injecteert in $E$ , dan zijn $E$ en $F$ gelijkmachtig.

Bewijs. Zij $f \colon E \to F$ en $g \colon F \to E$ injecties. Voor elk punt (van $E$ of $F$ ), volg 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 relevante injectie ligt, en is dan uniek door injectiviteit. Drie wederzijds uitsluitende lotgevallen: de keten stopt bij een punt van $E \setminus g(F)$ (oorsprong in $E$ ), stopt bij een punt van $F \setminus f(E)$ (oorsprong in $F$ ), of stopt nooit. Dit partitioneert $E = E_E \cup E_F \cup E_\infty$ en $F = F_E \cup F_F \cup F_\infty$ naar oorsprong.

Merk nu op: $f$ beeldt $E_E$ op $F_E$ af — de keten van $f(x)$ is de keten van $x$ voorafgegaan door één stap, dus oorsprongen matchen; en elke $y \in F_E$ heeft een keten met minstens één stap (haar oorsprong ligt in $E$ ), dus $y = f(x)$ met $x \in E_E$ . Hetzelfde argument levert bijecties $f \colon E_\infty \to F_\infty$ en $g \colon F_F \to E_F$ . Samenplakken,

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}

is een bijectie van $E$ op $F = F_E \cup F_\infty \cup F_F$ : ze is stuksgewijs bijectief, en de drie doelen 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 de (noodzakelijk discontinue) bijectie. Evenzo zijn $\R$ , $\intoo{0}{1}$ (via $\tanh$ -achtige bijecties) en $\mathcal{P}(\N)$ (binaire ontwikkelingen, Oefening 1.3) alle gelijkmachtig: “de kardinaliteit 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. Eén injectie is triviaal: $x \mapsto (x, 0)$ . Voor de andere, stuur $(x, y)$ naar het reële getal waarvan de decimale cijfers die van $x$ en $y$ verweven,

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

kies voor elke coördinaat de ontwikkeling die niet eindigt op louter $9$ ’s: met die conventie bepalen de cijfers van het beeld die van $x$ en $y$ , dus is de afbeelding injectief (ze hoeft niet surjectief te zijn — beelden hebben bijvoorbeeld nooit oneven posities die uiteindelijk $9$ zijn — en dat is in orde). Cantor–Bernstein (Stelling 1.10) stelt een echte bijectie samen. Continuïteit is natuurlijk hopeloos: een continue bijectie ertussen is onmogelijk — de metrische hoofdstukken leggen uit waarom (samenhang onderscheidt de lijn van het vlak, Hoofdstuk 4).

1.3 Groepen

Definitie 1.13 (Voortgebrachte deelgroep; orde)

Zij $G$ een groep en $A \subseteq G$ . De deelgroep voortgebracht door $A$ , genoteerd $\langle A \rangle$ , is de kleinste deelgroep die $A$ bevat — concreet, alle eindige producten van elementen van $A$ en hun inversen. Een groep is cyclisch wanneer ze 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}$ (mogelijk oneindig); wanneer eindig, is ze de kleinste $n \geq 1$ met $a^n = e$ , en $a^k = e \iff \operatorname{ord}(a) \mid k$ .

Bewijs van de ordekarakterisering. Als $a^m = e$ voor zekere $m \geq 1$ , zij $n \geq 1$ minimaal met $a^n = e$ . De elementen $e, a, \dots, a^{n-1}$ zijn paarsgewijs verschillend ( $a^{i} = a^{j}$ met $0 \leq i < j < n$ geeft $a^{j-i} = e$ , in strijd met minimaliteit), en elke $a^k$ reduceert tot een daarvan door Euclidische deling $k = nq + r$ : $\langle a\rangle$ heeft precies $n$ elementen, en $a^k = a^r = e \iff r = 0 \iff n \mid k$ . Als geen macht triviaal is, zijn alle $a^k$ ( $k \in \Z$ ) verschillend (zelfde delingsargument) en is de orde oneindig. ∎

Stelling 1.14 (Lagrange)

Zij $G$ een eindige groep en $H$ een deelgroep. Dan deelt $\abs H$ $\abs G$ . In het bijzonder deelt de orde van elk element $\abs G$ , en $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: $e \in H$ ; symmetrisch: inversen; transitief: producten). De klasse van $x$ is de linker nevenklasse $xH = \{xh : h \in H\}$ , en $h \mapsto xh$ is een bijectie $H \to xH$ (inverse $y \mapsto x^{-1}y$ ): alle klassen hebben $\abs H$ elementen. Klassen partitioneren $G$ (de algemene partitiestelling van het Bachelor jaar 1-volume), dus $\abs G = \abs H \times (\text{aantal nevenklassen})$ . Voor een element: pas dit toe op $H = \langle a\rangle$ ; dan $a^{\abs G} = (a^{\operatorname{ord} a})^{\abs G / \operatorname{ord} a} = e$ . ∎

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

Neem $G = \mathfrak{S}_3$ (orde $6$ ) en $H = A_3 = \{\mathrm{id},\ (1\,2\,3),\ (1\,3\,2)\}$ . De linker nevenklassen 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$ partitioneren, precies zoals de telling $\abs G = \abs H \times (\text{aantal nevenklassen})$ eist — en zichtbaar de partitie in even en oneven permutaties. Merk op $(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 twee-klassenbeeld is het algemene voor de signatuur: $A_n$ en haar eenzame begeleidende nevenklasse splitsen $\mathfrak{S}_n$ in tweeën, en zo telt het weekendprobleem bereikbare puzzelposities.

Voorbeeld 1.16

Twee onmiddellijke dividenden. Groepen van priemorde zijn cyclisch: als $\abs G = p$ priem is en $a \neq e$ , dan deelt $\operatorname{ord}(a)$ $p$ en is niet $1$ , dus is ze $p$ : $\langle a\rangle = G$ . Het deelgroepenrooster van $\Z/12\Z$ : door Propositie 1.17 hieronder bestaat er precies één deelgroep per deler van $12$ — ordes $1, 2, 3, 4, 6, 12$ , voortgebracht respectievelijk door $\overline 0$ , $\overline 6$ , $\overline 4$ , $\overline 3$ , $\overline 2$ , $\overline 1$ . De sluitende waarschuwing: de omgekeerde van Lagrange faalt in het algemeen — $A_4$ heeft orde $12$ maar geen deelgroep van orde $6$ , zoals we bewijzen in het weekendprobleem van dit hoofdstuk (Probleem 1.1, vraag 14). Lagrange beperkt de mogelijke ordes; ze belooft ze niet.

Het deelgroepenrooster van ℤ/12ℤ: één deelgroep per deler van 12 (), met een rand wanneer de ene de andere bevat met priemindex. Inclusies lopen tegen deelbaarheid van de voortbrenger: 4 ⊂eq 2 omdat 4 een veelvoud van 2 is. — Het deelgroepenrooster van $\Z/12\Z$ : één deelgroep per deler van $12$ (Propositie 1.17), met een rand wanneer de ene de andere bevat met priemindex. Inclusies lopen *tegen* deelbaarheid van de voortbrenger: $\langle\overline 4\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 deelgroep van $G$ is cyclisch; voor elke deler $d \mid n$ bestaat er precies één deelgroep van orde $d$ , namelijk $\langle a^{n/d}\rangle$ .
$a^k$ brengt $G$ voort desda $\gcd(k, n) = 1$ : $G$ heeft $\varphi(n)$ voortbrengers (Eulers totientfunctie).

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

(2) Zij $H \leq G$ niet-triviaal en $m$ minimaal $\geq 1$ met $a^m \in H$ . Euclidische deling toont $H = \langle a^m\rangle$ (voor $a^k \in H$ : $k = mq + r$ dwingt $a^r \in H$ , dus $r = 0$ ), en $m \mid n$ (deel $n$ door $m$ : $a^{n \bmod m} \in H$ ). Dan $\abs H = n/m$ ; met $m = n/d$ realiseert men elke deler $d$ . Uniciteit: elke deelgroep van orde $d$ is, door het voorgaande, van de vorm $\langle a^m \rangle$ met $n/m = d$ — dus $m = n/d$ is gedwongen en de deelgroep is bepaald.

(3) We claimen $\operatorname{ord}(a^k) = \frac{n}{\gcd(k, n)}$ . Schrijf $d = \gcd(k, n)$ . Voor elke $m \geq 1$ geeft de ordekarakterisering van 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 ,

de laatste stap door het lemma van Gauss, omdat $\frac nd$ en $\frac kd$ relatief priem zijn. De kleinste zulke $m$ is $\frac nd$ : $\operatorname{ord}(a^k) = \frac n{\gcd(k,n)}$ , die $n$ gelijk is desda $\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 permutaties van $\intint{1}{n}$ (orde $n!$ ). Een cykel $(a_1\,a_2\,\cdots\,a_k)$ stuurt $a_1 \mapsto a_2 \mapsto \dots \mapsto a_k \mapsto a_1$ en fixteert al het overige; $k$ is haar lengte, een $2$ -cykel is een transpositie. Twee cykels zijn disjunct wanneer hun steunen (niet-gefixeerde punten) dat zijn.

Stelling 1.19 (Cykelontbinding)

Elke permutatie $\sigma \neq \mathrm{id}$ is een product van paarsgewijs disjuncte cykels, uniek op de volgorde van de factoren na. Disjuncte cykels commuteren, en $\operatorname{ord}(\sigma)$ is de kgv van de lengtes.

Bewijs. Beschouw de “baan”-relatie op de steun van $\sigma$ : $x \sim y$ desda $y = \sigma^k(x)$ voor zekere $k \in \Z$ — een equivalentierelatie. Elke klasse $\{x, \sigma(x), \dots, \sigma^{k-1}(x)\}$ (eindig, dus de iteraten keren terug — de eerste herhaling moet naar $x$ terugkeren door injectiviteit) 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 corresponderende cykel. Uniciteit: elke disjuncte-cykel-factorisatie reproduceert precies de banen (de cykel door $x$ moet $(x\ \sigma(x)\ \cdots)$ zijn). Disjuncte cykels commuteren omdat ze disjuncte punten bewegen; de orde-uitspraak volgt omdat $\sigma^m = \mathrm{id}$ desda de $m$ -de macht van elke cykel dat is (disjunctheid), desda elke lengte $m$ deelt. ∎

Voorbeeld 1.20 (Cykeltype als census)

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

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

rangschik de negen symbolen in een rij ( $9!$ manieren), plaats de eerste vier, volgende drie, laatste twee in cykels, en deel door de rotaties binnen elke haak ( $4$ , $3$ en $2$ ervan) die dezelfde permutatie geven. (Hier verschillende cykellengtes, dus geen verdere deling; gelijke lengtes zouden ook delen door de permutaties van de gelijke haken vereisen.) 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 census — de combinatoriek van $\mathfrak{S}_n$ is de rekenkunde van partities.

Stelling 1.21 (Signatuur)

Er is precies één groepsmorfisme $\varepsilon \colon \mathfrak{S}_n \to \{\pm 1\}$ (voor $n \geq 2$ ) dat de waarde $-1$ aanneemt op transposities: 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. Voor $\sigma \in \mathfrak{S}_n$ stel

\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)\}$ lopen over alle paren), dus $\varepsilon(\sigma) = (-1)^{I(\sigma)} \in \{\pm1\}$ . Morfisme: voor $\sigma, \tau$ ,

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

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

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

dat is $(b - a - 1) + (b - a - 1) + 1 = 2(b - a) - 1$ ervan, oneven. (Alternatief: controleer $(1\,2)$ direct, met één inversie, en conjugeer — conjugaten hebben gelijke signatuur omdat $\varepsilon$ een morfisme is naar een abelse groep.) Dus $\varepsilon((a\,b)) = (-1)^{2(b-a)-1} = -1$ .

Uniciteit. Transposities brengen $\mathfrak{S}_n$ voort (elke cykel $(a_1\cdots a_k) = (a_1\,a_k)(a_1\,a_{k-1})\cdots(a_1\,a_2)$ , en Stelling 1.19 voltooit); een morfisme naar $\{\pm1\}$ is bepaald door zijn waarden op voortbrengers.

Gevolgen. De cykelidentiteit hierboven schrijft een $k$ -cykel als $k - 1$ transposities: signatuur $(-1)^{k-1}$ . $A_n$ : het morfisme $\varepsilon$ is surjectief (transposities bestaan voor $n \geq 2$ ), en de twee “nevenklassen” $A_n$ en $(1\,2)A_n$ zijn gelijkmachtig en partitioneren $\mathfrak{S}_n$ (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 pariteitscontrole op schudden — en de motor van de determinant in Hoofdstuk 2.

Voorbeeld 1.23 (Drie wegen naar één teken)

Zij $\sigma \in \mathfrak{S}_5$ de afbeelding die $1, 2, 3, 4, 5$ stuurt naar $3, 5, 4, 1, 2$ . 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 uit-volgorde-paren $(3,1)$ , $(3,2)$ , $(5,4)$ , $(5,1)$ , $(5,2)$ , $(4,1)$ , $(4,2)$ : zeven ervan, en $(-1)^7 = -1$ . Via transposities: $\sigma = (1\,4)(1\,3)(2\,5)$ , drie factoren, $(-1)^3 = -1$ . Drie berekeningen, één pariteit: de uniciteit in Stelling 1.21 garandeert dat geen boekhoudschema ze ooit oneens kan maken — precies wat $\varepsilon$ bruikbaar maakt als invariant (zie het weekendprobleem).

Opmerking 1.24 (Waar de signatuur hierheen gaat)

De signatuur is het zaad van drie latere oogsten: ze bouwt de determinant en haar productregel in Hoofdstuk 2; ze drijft pariteitsinvarianten voor combinatorische puzzels (het weekendprobleem van dit hoofdstuk lost de vijftienpuzzel ermee op); en de alternerende groepen $A_n$ die ze definieert worden centraal in het Bachelor jaar 3-volume, waar hun eenvoudigheid voor $n \geq 5$ verklaart waarom vergelijkingen van graad $5$ geen oplossing in radicalen hebben.

1.5 Ringen, idealen, quotiënten

Definitie 1.25 (Ideaal)

Zij $A$ een commutatieve ring. Een ideaal $I \subseteq A$ is een additieve deelgroep zodanig dat $a x \in I$ voor alle $a \in A$ , $x \in I$ . Kernen van ringmorfismen zijn idealen; $I = A$ desda $1 \in I$ desda $I$ een eenheid bevat. Het ideaal voortgebracht door $x$ is $xA = \{xa\}$ (een hoofdideaal).

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

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

Bewijs. Voor $\Z$ was dit de deelgroepstelling van het Bachelor jaar 1-volume (een ideaal is in het bijzonder een deelgroep, en $n\Z$ is een ideaal). Voor $K[X]$ : zij $I \neq \{0\}$ een ideaal en $P \in I$ niet-nul van minimale graad, genormaliseerd monisch. Voor $F \in I$ geeft Euclidische deling $F = PQ + R$ dat $R = F - PQ \in I$ met $\deg R < \deg P$ : minimaliteit dwingt $R = 0$ , dus $I = P\,K[X]$ . Uniciteit: twee monische voortbrengers delen elkaar. De Bézout-uitspraken zijn de gelijkheid van het ideaal $x\Z + y\Z$ (resp. zijn veeltermanaloog) met het hoofdideaal van de ggd — de definitie zelf van ggd uit Jaar 1, nu herkend als een uitspraak over idealen. ∎

Voorbeeld 1.27 (Een veelterm-ggd, op twee manieren)

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

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 terugsubstitutie 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 principaal (Stelling 1.26); het bevat $X - 1$ (de weergave) en is bevat in $(X - 1)\Q[X]$ (beide voortbrengers verdwijnen in $1$ , dus zijn veelvouden van $X - 1$ ): de monische voortbrenger is $X - 1$ . Het sluitende inzicht: het ideaalstandpunt identificeert de ggd zonder te delen — gemeenschappelijke wortels lokaliseren het ideaal, en Euclid certificeert het slechts.

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

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

Stelling 1.29 (Chinese reststelling, ringvorm)

Als $\gcd(m, n) = 1$ , 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 is $\varphi(mn) = \varphi(m)\varphi(n)$ voor relatief prieme $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 (compatibiliteiten zijn onmiddellijk). Injectiviteit: $x \equiv 0$ mod $m$ en mod $n$ met $\gcd(m,n) = 1$ dwingt $mn \mid x$ (Gauss). Surjectiviteit: beide kanten hebben $mn$ elementen, dus injectiviteit volstaat (eindige gelijke kardinaliteiten) — of expliciet: uit een Bézout-relatie $um + vn = 1$ beeldt de klasse van

x = b\,um + a\,vn

af op $(a \bmod m,\ b \bmod n)$ , omdat $vn = 1 - um \equiv 1 \pmod m$ $x \equiv a \pmod m$ maakt, en symmetrisch mod $n$ — het recept numeriek gebruikt in Voorbeeld 1.30. Eenheden corresponderen met paren van eenheden (de eenheden van een productring zijn de paren van eenheden), dus $\varphi(mn) = \varphi(m)\varphi(n)$ . Voor een priemmacht is $\varphi(p^k) = p^k - p^{k-1}$ (de niet-eenheden mod $p^k$ zijn de veelvouden van $p$ ); multiplicativiteit stelt de productformule samen. ∎

Voorbeeld 1.30 (Het Chinese isomorfisme inverteren)

Neem $m = 8$ , $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$ : $k \equiv 1$ , dus $u = 9$ ; uit $v = 8k \equiv 1 \pmod 9$ : $-k \equiv 1$ , $k \equiv 8$ , dus $v = 64$ . Dan is de klasse van $x = 9a + 64b$ modulo $72$ de unieke oplossing van $x \equiv a \pmod 8$ , $x \equiv b \pmod 9$ : voor $a = 3$ , $b = 5$ krijgt men $27 + 320 = 347 \equiv 59 \pmod{72}$ — precies de tussenwaarde gevonden door substitutie in Oefening 1.8. Het sluitende inzicht: $u$ en $v$ voldoen aan $u + v \equiv 1$ , $uv \equiv 0$ , $u^2 \equiv u$ , $v^2 \equiv v$ modulo $72$ ; ze zijn de beelden van $(1, 0)$ en $(0, 1)$ , en elke Chinese ontbinding is in de kern een ontbinding van $1$ in orthogonale idempotenten.

Stelling 1.31 (Euler; Fermat hernomen)

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

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

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

Bewijs. De inverteerbare klassen zijn precies die van gehele getallen relatief priem met $n$ (Bachelor jaar 1-volume): $\varphi(n)$ ervan, die een groep vormen onder vermenigvuldiging. Lagrange (Stelling 1.14): elk element tot de macht van de groepsorde is het neutrale element. ∎

Voorbeeld 1.32 (Een eenhedengroep zonder voortbrenger)

De groep $(\Z/15\Z)^*$ heeft $\varphi(15) = \varphi(3)\varphi(5) = 8$ elementen. Is ze cyclisch? Bereken ordes via het Chinese isomorfisme $(\Z/15\Z)^* \simeq (\Z/3\Z)^* \times (\Z/5\Z)^*$ (een eenheid mod $15$ is een paar eenheden): de factoren hebben ordes $2$ en $4$ , dus deelt de orde van elk element $\operatorname{lcm}(2, 4) = 4 < 8$ — geen 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} :

ordes $4, 2, 4, 2, 2$ en nooit $8$ . Contrast met Oefening 1.10: $(\Z/p\Z)^*$ is cyclisch voor $p$ priem, omdat daar de eenhedengroep in een lichaam zit. De stelling van Euler geldt nog met exponent $\varphi(15) = 8$ , maar de echte universele exponent hier is $4$ — Euler is een bovengrens, niet altijd de scherpe.

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)$ , $\C$ als $\R$ -algebra. Morfismen van algebras 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, dat Hoofdstuk 3 drijft.

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

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

(alleen de constante en lineaire termen van $P$ overleven). Dus $\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 minimale graad in de kern — de minimale veelterm van $A$ , ster van Hoofdstuk 3. Het beeld is de tweedimensionale commutatieve algebra $\{aI + bA\}$ : evaluatiemorfismen krimpen de oneindigdimensionale $\R[X]$ tot kleine, berekenbare algebras.

Opmerking 1.35 (Perspectieven: drie melodieën om te beluisteren)

Drie structurele ideeën uit dit hoofdstuk keren doorheen het volume terug, telkens in zwaardere orkestratie. Factorisatie door een quotiënt (Definitie 1.3): ze bouwt $\Z/n\Z$ hier, definieert afbeeldingen op oplossingsverzamelingen van lineaire stelsels in Hoofdstuk 2, en ligt stilzwijgend ten grondslag aan elk “welgedefinieerd op klassen”-argument. Invarianten: de signatuur is een morfisme naar $\{\pm1\}$ dat geen legale zet kan ontwijken — dezelfde logica geeft de productregel van de determinant (Hoofdstuk 2), de gelijkvormigheidsinvariantie van het spoor, en de behouden grootheden van Hoofdstuk 16. Tellen tegen een structuur: Lagrange telt via nevenklassen, dimensie telt via bases (Hoofdstuk 2), multipliciteit telt via veeltermgraden (Hoofdstuk 3); wanneer een grens wonderbaarlijk lijkt, doet een partitie of graadstructuur het tellen.

Opmerking 1.36 (Veelvoorkomende valkuilen)

Vier klassiekers. (i) Een afbeelding op een quotiënt moet welgedefinieerd worden gecontroleerd: “ $\overline x \mapsto$ (formule op $x$ )” is legitiem alleen als de formule constant is op klassen — de compatibiliteit van Definitie 1.3, geen formaliteit. (ii) $\operatorname{ord}(ab) = \operatorname{lcm}(\operatorname{ord}a, \operatorname{ord}b)$ is vals in het algemeen, zelfs voor commuterende elementen ( $a$ en $a^{-1}$ ); Oefening 1.4 geeft de juiste relatief-priem-en-commuterende uitspraak, en disjuncte cykels de juiste permutatieversie. (iii) Aftelbaarheid overleeft aftelbare unies en eindige producten, maar niet aftelbare producten: $\{0,1\}^{\N}$ is overaftelbaar (Oefening 1.3) hoewel elke factor twee elementen heeft. (iv) Cantor–Bernstein heeft alleen injecties beide kanten nodig, maar de bijectie die ze bouwt is meestal discontinu en niet-expliciet — verwacht geen formule (Voorbeeld 1.11).

Opmerking 1.37 (Waar dit hoofdstuk wordt gebruikt)

Bijna overal. De signatuur bouwt determinanten (Hoofdstuk 2); het evaluatiemorfisme $P \mapsto P(u)$ en de hoofdidealen van $K[X]$ produceren minimale veeltermen en de kernontbindingen van Hoofdstuk 3; aftelbaarheid is het podium waarop Hoofdstuk 21 optreedt (waarschijnlijkheid op aftelbare ruimten) en de reden dat topologie aftelbare dichte verzamelingen blijft produceren (Hoofdstuk 4). De quotiëntconstructie $A/I$ wordt heringezet in het Bachelor jaar 3-volume om lichamen $K[X]/(P)$ te bouwen en, daaruit, Galoistheorie: de hier bewezen universele eigenschap wordt daar woord voor woord gebruikt.

1.6 Oefeningen

Oefening 1.1 ★

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

Oplossing

Oplossing van Oefening 1.1.

Eindige deelverzamelingen van $\N$ : aftelbaar — de verzameling van deelverzamelingen van $\intint{0}{n}$ is eindig, en de eindige deelverzamelingen vormen de aftelbare unie over $n$ van deze (Propositie 1.6 (3)); oneindig omdat ze alle singletons bevat.

Alle deelverzamelingen van $\N$ : niet aftelbaar, door 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 unie 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 unie over $n$ .

Uiteindelijk-nulle binaire rijen: aftelbaar — ze bijecteren met eindige deelverzamelingen van $\N$ (de steun).

Oefening 1.2 ★

In $\mathfrak{S}_7$ , zij $\sigma = (1\,4\,2\,6)(3\,5)$ en $\tau = (2\,3\,7)$ . Bereken $\sigma\tau$ en $\tau\sigma$ in disjuncte-cykel-vorm, de ordes en signaturen van alle vier de permutaties, en $\sigma^{2026}$ .

Oplossing

Oplossing van Oefening 1.2.

Bereken element voor element, de rechterfactor eerst toepassend. $\sigma\tau$ stuurt $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$ $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),

ook een $7$ -cykel (zoals verwacht: $\sigma\tau$ en $\tau\sigma$ zijn geconjugeerd, delen dus hun cykeltype).

Ordes 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}$ : $2026 = 4 \times 506 + 2$ , dus $\sigma^{2026} = \sigma^2 = (1\,2)(4\,6)$ (kwadrateer de $4$ -cykel; de transpositie verdwijnt door kwadrateren).

Oefening 1.3 ★

Construeer expliciete injecties die tonen dat $\mathcal{P}(\N)$ , $\intcc{0}{1}$ en de verzameling $\{0,1\}^{\N}$ van binaire rijen paarsgewijs gelijkmachtig zijn (binaire ontwikkelingen beide kanten op; Cantor–Bernstein absorbeert de dubbele-representatie-hinder).

Oplossing

Oplossing van Oefening 1.3.

$\{0,1\}^{\N} \to \mathcal{P}(\N)$ : een rij beeldt af op haar steun — een bijectie (indicatorfuncties), geen stelling nodig.

$\{0,1\}^{\N} \to \intcc{0}{1}$ : de basis- $3$ -afbeelding $(a_n) \mapsto \sum 2a_n 3^{-n-1}$ is injectief (twee verschillende rijen verschillen eerst op rang $N$ ; de staarten kunnen een gap 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}$ : binaire ontwikkeling, kies (zeg) de ontwikkeling die niet eindigt op louter $1$ ’en: injectief.

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

Oefening 1.4 ★

Zij $G$ een groep en $a, b \in G$ commuterende elementen van eindige relatief prieme ordes $m$ en $n$ . Bewijs dat $\operatorname{ord}(ab) = mn$ . Toon met een voorbeeld in $\mathfrak{S}_3$ dat commutatie essentieel is.

Oplossing

Oplossing van Oefening 1.4.

Zij $c = ab = ba$ en $d = \operatorname{ord}(c)$ . Eerst $c^{mn} = a^{mn} b^{mn} = e$ (commutatie laat de macht splitsen), 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 deelgroep waarvan de orde zowel $m$ als $n$ deelt (Lagrange in elke cyclische groep), dus is triviaal: $a^d = b^d = e$ , dus $m \mid d$ en $n \mid d$ , en door relatieve primaliteit $mn \mid d$ . Dus $d = mn$ .

In $\mathfrak{S}_3$ : neem $a = (1\,2)$ (orde $2$ ) en $b = (1\,2\,3)$ (orde $3$ ), relatief prieme ordes, die niet commuten: $ab = (2\,3)$ heeft orde $2 \neq 6$ — inderdaad heeft $\mathfrak{S}_3$ geen element van orde $6$ . Commutatie is essentieel.

Oefening 1.5 ★★

Zij $G$ een eindige groep van even orde. Bewijs dat $G$ een element van orde $2$ bevat. (Paar elk element met zijn inverse; tel de zelf-gepaarde.)

Oplossing

Oplossing van Oefening 1.5.

Paar elke $x \in G$ met $x^{-1}$ . De paren $\{x, x^{-1}\}$ met $x \neq x^{-1}$ hebben twee elementen en partitioneren hun unie; de overblijvende elementen zijn precies die met $x = x^{-1}$ , d.w.z. $x^2 = e$ . Omdat $\abs G$ even is en de twee-element-paren een even aantal elementen bedekken, heeft de verzameling $\{x : x^2 = e\}$ even kardinaliteit; ze bevat $e$ , dus bevat ze minstens één ander element $x \neq e$ — een element van orde $2$ .

Oefening 1.6 ★★

Bewijs dat $A_n$ ( $n \geq 3$ ) wordt voortgebracht door de $3$ -cykels. (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 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),

(controleer door evaluatie), en $(a\,b)(a\,b) = \mathrm{id}$ . Dus brengen de $3$ -cykels $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 nulle morfisme. 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 deelbaar door elke $n$ is $0$ , dus $f(x) = 0$ voor alle $x$ .

$(\Z/n\Z, +) \to (\Z/m\Z, +)$ : een morfisme is bepaald door $c = f(\overline 1)$ , die moet voldoen aan $n c \equiv 0 \pmod m$ , d.w.z. $c$ is een veelvoud van $\frac{m}{\gcd(m,n)}$ ; er zijn $\gcd(m,n)$ zulke klassen, en elke keuze definieert een morfisme (factoriseer $k \mapsto kc$ door $\Z/n\Z$ via de universele eigenschap).

$(\Q, +) \to (\Q_+^*, \times)$ : alleen de triviale. Als $f(x) = y$ , dan is voor elke $n$ $y = f(n \cdot \frac xn) = f(\frac xn)^n$ een $n$ -de macht in $\Q_+^*$ . Maar een rationaal $y \neq 1$ kan geen $n$ -de macht zijn voor alle $n$ : zekere priem verschijnt in $y$ met niet-nulle exponent $v$ , en $n \nmid v$ voor $n > \abs v$ (exponenten van $n$ -de machten zijn veelvouden van $n$ , door unieke factorisatie). Dus $f \equiv 1$ .

Oefening 1.8 ★★

Met de Chinese reststelling, bereken $\varphi(360)$ , vind 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 mod $100$ ; let op: werk mod $4$ en mod $25$ ).

Oplossing

Oplossing van Oefening 1.8.

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

Stelsel: moduli $8, 9, 5$ paarsgewijs relatief priem, totaal $360$ . Uit $x \equiv 3 \pmod 8$ en $x \equiv 5 \pmod 9$ : $x = 3 + 8k$ met $3 + 8k \equiv 5 \pmod 9$ , d.w.z. $-k \equiv 2$ , $k \equiv -2 \equiv 7 \pmod 9$ : $x \equiv 3 + 56 = 59 \pmod{72}$ . Dan $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}$ .

Laatste twee cijfers van $3^{2026}$ : mod $4$ , $3^{2026} = 9^{1013} \equiv 1$ . Mod $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: $x = 4 + 25k \equiv 1 \pmod 4$ geeft $k \equiv 1 \pmod 4$ : $x \equiv 29 \pmod{100}$ . De laatste twee cijfers zijn $29$ .

Oefening 1.9 ★★★

Bewijs dat een eindig integriteitsdomein een lichaam is. Leid af dat $\Z/n\Z$ een lichaam is desda $n$ priem is (opnieuw).

Oplossing

Oplossing van Oefening 1.9.

Zij $A$ een eindig integriteitsdomein en $a \in A$ , $a \neq 0$ . De afbeelding $x \mapsto ax$ is injectief ( $ax = ay \implies a(x - y) = 0 \implies x = y$ , geen nuldelers); een injectieve afbeelding van een eindige verzameling naar zichzelf is surjectief (Bachelor jaar 1-volume, de duivenhok-equivalentie). Dus $1 = ab$ voor zekere $b$ : elk niet-nul element is inverteerbaar, $A$ is een lichaam.

$\Z/n\Z$ : als $n$ priem is, is het een integriteitsdomein ( $n \mid ab \implies n \mid a$ of $n \mid b$ , lemma van Euclid), eindig, dus een lichaam; als $n = rs$ samengesteld is, vertoont $\overline r\,\overline s = \overline 0$ nuldelers.

Oefening 1.10 ★★★

(Een klassieker) Zij $K$ een lichaam en $G$ een eindige deelgroep van $(K^*, \times)$ . Bewijs dat $G$ cyclisch is. Hint: zij $m$ de maximale orde onder de elementen van $G$ ; toon dat de orde van elk element $m$ deelt (met Oefening 1.4 op geschikte relatief prieme delen), dus voldoet heel $G$ aan $x^m = 1$ ; tel wortels 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\}$ , bereikt in $a$ .

Bewering: elke $x \in G$ heeft orde die $m$ deelt. Stel dat zekere $x$ orde $q$ heeft met $q \nmid m$ : dan deelt zekere priemmacht $p^k$ $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 ordes zijn relatief priem en de twee elementen commuten ( $G \subseteq K^*$ is abels), dus door Oefening 1.4 heeft hun product orde $p^k m' > p^j m' = m$ : in strijd met maximaliteit.

Dus voldoen alle $x \in G$ aan $x^m = 1$ : de veelterm $X^m - 1$ heeft minstens $\abs G$ wortels in het lichaam $K$ , vandaar $\abs G \leq m$ (een niet-nulle veelterm van graad $m$ heeft hoogstens $m$ wortels, Bachelor jaar 1-volume). Maar $m = \operatorname{ord}(a) \leq \abs G$ door Lagrange. Dus $m = \abs G$ en $\langle a \rangle$ , van kardinaliteit $m = \abs G$ , is heel $G$ : cyclisch.

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

Oefening 1.11 ★★★

Bewijs dat de groep $(\Q, +)$ niet cyclisch is, en erger: ze is niet eens eindig voortgebracht. Bewijs anderzijds dat elke eindig voortgebrachte deelgroep van $(\Q, +)$ cyclisch is.

Oplossing

Oplossing van Oefening 1.11.

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

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

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

Oefening 1.12 ★★

(Criterium van Dedekind) Bewijs dat elke oneindige verzameling een aftelbare deelverzameling bevat, en leid af dat een verzameling $E$ oneindig is desda ze gelijkmachtig is met een echte deelverzameling van zichzelf. (Voor de directe implicatie, verschuif een aftelbare deelverzameling met één stap; voor de omgekeerde, herinner 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$ ; als $a_0, \dots, a_n$ gekozen zijn, is $E \setminus \{a_0, \dots, a_n\}$ niet-leeg ( $E$ is niet eindig), kies $a_{n+1}$ daar. De $a_n$ zijn paarsgewijs verschillend per constructie, dus $A = \{a_n : n \in \N\}$ is 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$ . Ze is injectief (de twee stukken zijn injectief met disjuncte beelden) en surjectief op $E \setminus \{a_0\}$ : elke $a_{n+1}$ wordt geraakt, elke $x \notin A$ wordt geraakt. Dus is $E$ gelijkmachtig met de echte deelverzameling $E \setminus \{a_0\}$ .

Omgekeerde. Als $E$ eindig is 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 (Bachelor jaar 1-volume: een injectieve zelfafbeelding van een eindige verzameling is bijectief). Dus is een verzameling gelijkmachtig met een echte deelverzameling oneindig.

1.7 Probleem: De vijftienpuzzel

De vijftienpuzzel is een $4 \times 4$ -tray met vijftien schuifende tegels genummerd $1$ tot $15$ en één lege cel; een zet schuift een van de tegels die aan de lege cel grenzen erin. In de jaren 1890 populariseerde Sam Loyd de puzzel door $1000 te bieden aan iedereen die de tegels $14$ en $15$ kon verwisselen en elke andere tegel op zijn plaats terugbrengen. Niemand heeft ooit geïncasseerd, en dit weekendprobleem bewijst beide helften van de reden: de signatuur van Stelling 1.21 verbiedt Loyds verwisseling, en — de zwaardere, constructieve helft — is alles wat de signatuur toelaat echt oplosbaar. De volledige uitspraak is de stelling van Johnson–Story (1879).

De opgeloste configuratie en Sam Loyds 14–15-configuratie. De $1000-vraag: kunnen legale schuiven de rechter tray in de linker veranderen? — De opgeloste configuratie en Sam Loyds $14$ – $15$ -configuratie. De $1000-vraag: kunnen legale schuiven de rechter tray in de linker veranderen?

Probleem 1.1

Weekendprobleem — de oplosbaarheidsstelling van Johnson–Story

Nummer de cellen $1$ tot $16$ in leesvolgorde (links naar rechts, boven naar onder), zodat cel $k$ in rij $i$ en kolom $j$ zit met $k = 4(i - 1) + j$ . Cel $16$ (rechtsonder) is het thuis van de lege cel; we behandelen de lege cel als een zestiende tegel, genoteerd $b$ en geïdentificeerd met het getal $16$ . Een configuratie is een bijectie $\sigma \colon \intint1{16} \to \intint1{16}$ , cel $\mapsto$ inhoud; de opgeloste configuratie is $\sigma = \mathrm{id}$ . Overal is $\varepsilon$ de signatuur van Stelling 1.21 en zijn twee cellen aangrenzend wanneer ze een rand van de tray delen.

Deel I — Configuraties, zetten, signaturen.

Rechtvaardig dat de configuraties precies de elementen van $\mathfrak{S}_{16}$ zijn, zodat er $16! = 20\,922\,789\,888\,000$ van zijn, en dat het aantal legale zetten vanuit een gegeven configuratie $2$ , $3$ of $4$ is, al naargelang de lege cel in een hoek, op een rand, of in het inwendige ligt.
Zij $\sigma$ een configuratie, $p = \sigma^{-1}(16)$ de cel van de leegte, en $c$ een cel aangrenzend aan $p$ . Toon dat het schuiven van de tegel van $c$ in $p$ de configuratie $\sigma' = \sigma \circ \tau$ produceert met $\tau = (p\ c)$ , en leid af dat elke zet de signatuur omkeert: $\varepsilon(\sigma') = -\varepsilon(\sigma)$ .
Schaakbord de tray: $\chi(k) = (-1)^{i+j}$ voor de cel $k$ in rij $i$ , kolom $j$ . Toon dat elke zet $\chi(\text{cel van de leegte})$ omkeert, en leid af dat een rij zetten die de leegte terugbrengt naar haar startcel even lengte heeft.
Toon dat

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

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

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

Loyds configuratie $\sigma_L$ stemt overeen met de opgeloste behalve dat cellen $14$ en $15$ de tegels $15$ en $14$ houden. Bereken $I(\sigma_L)$ en concludeer dat geen rij zetten $\sigma_L$ met de opgeloste configuratie verbindt: Loyds $1000 was nooit in gevaar.
Toon dat precies de helft van alle configuraties $I = +1$ voldoet: $\abs{\{\sigma : I(\sigma) = +1\}} = 16!/2$ . (Voor een vaste lege cel, paar configuraties door samenstellen met één vaste transpositie van twee andere cellen.)
Toon dat elke zet ongedaan wordt gemaakt door een legale zet, dat “ $\sigma'$ is bereikbaar vanuit $\sigma$ door legale zetten” een equivalentierelatie is, en dat de klasse $R$ van de opgeloste configuratie $R \subseteq \{I = +1\}$ voldoet. Concludeer dat er minstens twee klassen zijn.
Stel de leegte is thuis: $\sigma(16) = 16$ . Toon dat $I(\sigma) = \varepsilon(\rho)$ waarbij $\rho \in \mathfrak{S}_{15}$ de restrictie van $\sigma$ tot de cellen $1, \dots, 15$ is, en dat elke configuratie door legale zetten naar een met leegte thuis kan worden gevoerd. Concludeer: om $R = \{I = +1\}$ te bewijzen volstaat het elke even permutatie van de vijftien niet-thuis-cellen te realiseren door een rij zetten die start en eindigt met de leegte thuis.

Deel III — Leegterondes en de programmagroep. Een programma is een eindige rij legale zetten, gestart vanuit een configuratie met de leegte thuis, waarvan de eindconfiguratie weer de leegte thuis heeft. Haar effect is de permutatie $\pi$ van de cellen gedefinieerd door: de inhoud van cel $x$ eindigt in cel $\pi(x)$ .

Toon dat een programma uitgevoerd vanuit $\sigma$ eindigt in $\sigma \circ \pi^{-1}$ ; dat twee programma’s na elkaar uitvoeren hun effecten samenstelt; en dat de verzameling $H$ van alle effecten een deelgroep is van $\mathfrak{S}_{15}$ (permutaties van de cellen $1, \dots, 15$ ) bevat in de alternerende groep $A_{15}$ .
(De elementaire ronde) Vanuit de leegte thuis, schuif de leegte rond het $2 \times 2$ -blok rechtsonder: cellen $16 \to 12 \to 11 \to 15 \to 16$ . Toon dat het effect de $3$ -cykel $(11\ 12\ 15)$ is, en dat de omgekeerde ronde $(11\ 15\ 12)$ geeft. Beide liggen in $H$ .
(De grote ronde) Verifieer 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 is door alle zestien cellen (alleen aangrenzende stappen), en dat haar effect de $15$ -cykel is

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

Schrijvend $x_0 = 15$ , $x_1 = 12$ , $x_2 = 11$ , …, $x_{14} = 14$ voor haar cykelorde, controleer dat de omgekeerde elementaire ronde van 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,

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

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

Deel IV — De alternerende groep voortbrengen.

(Lemma A) Zij $s$ en $t$ $3$ -cykels waarvan de steunen precies twee punten delen, zeg steunen $\{a, b, c\}$ en $\{b, c, d\}$ . Toon dat, na eventuele vervanging van $s$ of $t$ door haar inverse (wat de voortgebrachte deelgroep niet verandert), het product $st$ een dubbele transpositie is; toon dat $A_4$ geen deelgroep van orde $6$ bevat (een deelgroep van index $2$ bevat elk kwadraat; tel de $3$ -cykels onder de kwadraten); en concludeer dat $\langle s, t\rangle$ de hele alternerende groep van 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 deelgroep van zekere $\mathfrak{S}_n$ die elke even permutatie van $X$ bevat en één $3$ -cykel $(u\ v\ w)$ met $u, v \in X$ . Toon dat voor alle verschillende $a, b \in X$ er een even permutatie $g$ van $X$ bestaat met $g(u) = a$ , $g(v) = b$ , en leid af $(a\ b\ w) \in G$ .
Leid af dat de groep $G$ van lemma B elke even permutatie van $X \cup \{w\}$ bevat (gebruik Oefening 1.6: de $3$ -cykels brengen voort). Dan, lemma’s A en B aaneenrijgend langs de opeenvolgende $3$ -cykels $s_0, s_1, \dots, s_{12}$ van vraag 13, bewijs dat $\langle s_0, \dots, s_{12}\rangle = A_{15}$ .
Concludeer dat $H = A_{15}$ : elke even herschikking van de vijftien tegels is haalbaar door een programma, en $H$ heeft $15!/2 = 653\,837\,184\,000$ elementen.
(De stelling van Johnson–Story, 1879) Stel vragen 6, 7, 8 en 17 samen: de configuraties bereikbaar vanuit de opgeloste zijn precies de $16!/2 = 10\,461\,394\,944\,000$ configuraties met $I = +1$ ; en bereikbaarheid heeft precies twee klassen, de klasse van de opgeloste configuratie en de klasse van Loyds $\sigma_L$ . (Voor het tweede punt, herlabel de tegels $14$ en $15$ : toon $\sigma \mapsto (14\ 15) \circ \sigma$ stuurt zetrijen naar zetrijen en verwisselt $\{I = +1\}$ met $\{I = -1\}$ .)

Deel V — Criteria, varianten, en het zicht van boven.

(Het praktische criterium) Lees de vijftien tegels in leesvolgorde van hun cellen, de leegte overslaand, en zij $N$ het aantal inversies van deze lijst; zij $r$ de rij van de leegte geteld vanonder. Toon dat $I(\sigma) = (-1)^{N + r + 1}$ , zodat $\sigma$ oplosbaar is desda $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 is vrij wanneer $g \cdot x = x$ dwingt $g = e$ . Toon dat $h \cdot \sigma = \sigma \circ h^{-1}$ een vrije actie van $H$ op de verzameling van leegte-thuis-configuraties definieert, dat haar banen precies de klassen van wederzijdse bereikbaarheid door programma’s zijn, en herwin uit de baantelling dat deze configuraties in precies $15!\,/\,\abs H = 2$ klassen splijten.
(De $3 \times 3$ -obstructie) Toon dat het $3 \times 3$ -bord geen gesloten wandeling toelaat die elke cel precies één keer bezoekt: de grote-ronde-strategie van Deel III faalt voor de achtpuzzel. (Schaakbord de negen cellen.)
(De reparatie) Op het $3 \times 3$ -bord met cellen $1$ tot $9$ in leesvolgorde en thuis $9$ : bereken de effecten van de omtreksronde $9 \to 8 \to 7 \to 4 \to 1 \to 2 \to 3 \to 6 \to 9$ (een $7$ -cykel $\zeta'$ die het centrum $5$ fixeert) en van de hoekronde $9 \to 6 \to 5 \to 8 \to 9$ (een $3$ -cykel door het centrum). Conjugatie van de laatste door de machten van $\zeta'$ en aaneenrijgen van lemma’s A en B, bewijs dat de programmagroep van de achtpuzzel heel $A_8$ is, en dus dat precies $9!/2 = 181\,440$ van de $9! = 362\,880$ configuraties oplosbaar zijn.
(Een arm bord) Zij nu het bord een enkele cykel van $n \geq 4$ cellen met $n - 1$ tegels. Toon dat de cyclische orde van de tegels invariant is, dat elke bereikbaarheidsklasse precies $n(n - 1)$ configuraties heeft (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 dun bord vangt de pariteitsinvariant bijna niets, en regeert de meetkunde.
Twee vonnissen door het criterium van vraag 19: de volledig omgekeerde tray (tegels $15, 14, \dots, 1$ in cellen $1$ tot $15$ , leegte thuis) en de tray met de leegte in cel $1$ gevolgd door de tegels $15, 14, \dots, 1$ in cellen $2$ tot $16$ . Welke is oplosbaar?
(Synthese) Het bewijs heeft twee onafhankelijke pijlers: een invariant ( $I$ , gebouwd uit het signatuurmorfisme) die toont dat hoogstens de helft van de configuraties bereikbaar is, en een expliciete voortbrengingsstelling ( $H = A_{15}$ ) die toont dat minstens de helft dat is. In één zin elk, zeg waar het volgende binnentrad: 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 configuratie kent aan elk van de $16$ cellen één van de $16$ inhouden toe (tegels $1$ – $15$ of de leegte $b = 16$ ), elk precies één keer: precies een bijectie $\intint1{16} \to \intint1{16}$ , een element van $\mathfrak{S}_{16}$ ; er zijn $16! = 20\,922\,789\,888\,000$ ervan. Een legale zet schuift één tegel aangrenzend aan de leegte, dus is het aantal zetten het aantal buren van de cel van de leegte: $2$ voor de vier hoekcellen, $3$ voor de acht randcellen, $4$ voor de vier inwendige cellen.

2. Na de schuif houdt cel $p$ de vroegere inhoud van $c$ en cel $c$ de leegte; alle andere cellen zijn onaangeroerd: $\sigma'(p) = \sigma(c)$ , $\sigma'(c) = \sigma(p) = 16$ , $\sigma' = \sigma$ elders. Dat is precies $\sigma' = \sigma \circ (p\ c)$ . Omdat $\varepsilon$ een morfisme is en $\varepsilon\bigl((p\ c)\bigr) = -1$ : $\varepsilon(\sigma') = -\varepsilon(\sigma)$ .

3. Aangrenzende cellen verschillen met één stap in precies één van de twee coördinaten, dus verandert $i + j$ van pariteit: $\chi$ neemt tegengestelde waarden op aangrenzende cellen. Een zet verplaatst de leegte van $p$ naar de aangrenzende $c$ , keert $\chi(\text{lege cel})$ om. Langs een gesloten wandeling van de leegte wordt $\chi$ één keer per zet omgekeerd en keert terug naar haar beginwaarde: het aantal zetten is even.

4. Door vragen 2 en 3 keert één zet beide factoren van $I(\sigma) = \varepsilon(\sigma)\chi(\sigma^{-1}(16))$ om; hun product blijft ongewijzigd. Voor de opgeloste configuratie: $\varepsilon(\mathrm{id}) = +1$ en de leegte is in cel $16$ , rij $4$ , kolom $4$ : $\chi(16) = (-1)^{8} = +1$ , dus $I(\mathrm{id}) = +1$ .

5. $\sigma_L$ is de transpositie $(14\ 15)$ van cellen: $\varepsilon(\sigma_L) = -1$ ; haar leegte is thuis, $\chi(16) = +1$ : $I(\sigma_L) = -1 \neq +1 = I(\mathrm{id})$ . Omdat $I$ door elke zet behouden blijft, verbindt geen rij zetten $\sigma_L$ en $\mathrm{id}$ . De premie was structureel veilig.

6. Fixeer een cel $p$ en twee andere cellen $c \neq d$ verschillend van $p$ , en stel $\tau_0 = (c\ d)$ . Op de verzameling van configuraties met leegte in $p$ is de afbeelding $\sigma \mapsto \sigma \circ \tau_0$ een involutie (ze bewaart $\sigma(p) = 16$ omdat $\tau_0$ $p$ fixeert) en keert $\varepsilon$ om, dus keert $I$ om: ze paart de configuraties met $I = +1$ bijectief met die met $I = -1$ . Dus draagt elk van de $16$ lege posities $15!/2$ configuraties met $I = +1$ bij, en

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

7. De zet die de tegel van $c$ in $p$ schuift wordt ongedaan gemaakt door diezelfde tegel (nu in $p$ ) terug in $c$ te schuiven: samenstellen met $(p\ c)$ tweemaal is de identiteit. Dus: reflexiviteit (lege rij), symmetrie (keer de rij om, maak elke zet ongedaan), transitiviteit (concateneer): een equivalentierelatie. Elke $\sigma \in R$ heeft $I(\sigma) = I(\mathrm{id}) = +1$ door vraag 4, dus $R \subseteq \{I = +1\}$ ; en $\sigma_L \notin R$ geeft een tweede klasse.

8. Als $\sigma(16) = 16$ , dan permuteert $\sigma$ de cellen $1, \dots, 15$ ; noem $\rho$ deze restrictie. Toevoegen van een vast punt verandert noch het cykeltype noch de signatuur (ontbind $\rho$ in transposities; hetzelfde product werkt in $\mathfrak{S}_{16}$ ), dus $\varepsilon(\sigma) = \varepsilon(\rho)$ , en $\chi(16) = +1$ geeft $I(\sigma) = \varepsilon(\rho)$ . Elke configuratie kan naar een leegte-thuis-configuratie worden gevoerd: het rooster is samenhangend, dus wandel de leegte langs een pad van aangrenzende cellen naar cel $16$ (elke stap is een legale zet). Stel nu dat elke even $\rho \in \mathfrak{S}_{15}$ door een programma wordt gerealiseerd. Gegeven $\sigma$ met $I(\sigma) = +1$ : wandel de leegte thuis om $\widetilde\sigma$ te bereiken (equivalent met $\sigma$ ), met $I(\widetilde\sigma) = +1$ , d.w.z. haar restrictie $\rho$ is even; het programma dat $\rho$ realiseert voert $\widetilde\sigma$ naar $\widetilde\sigma \circ \rho^{-1} = \mathrm{id}$ (zie vraag 9). Door transitiviteit $\sigma \in R$ , vandaar $\{I = +1\} \subseteq R$ en gelijkheid.

9. Enkele zet: de inhoud van $c$ eindigt in $p$ en de leegte in $c$ : het effect is $\pi = (p\ c)$ , en inderdaad $\sigma' = \sigma \circ (p\ c) = \sigma \circ \pi^{-1}$ . Inductie: als een rij effect $\pi_1$ heeft en $\sigma$ naar $\sigma \circ \pi_1^{-1}$ voert, levert volgen met een zet van effect $\pi_2 = (p'\ c')$ $(\sigma \circ \pi_1^{-1}) \circ \pi_2^{-1} = \sigma \circ (\pi_2\pi_1)^{-1}$ , en inhouden bewegen met $\pi_2 \circ \pi_1$ (eerst $\pi_1$ , dan $\pi_2$ ). Dus stellen effecten samen, en een programma uitgevoerd vanuit $\sigma$ eindigt in $\sigma \circ \pi^{-1}$ . Deelgroep: het lege programma heeft effect $\mathrm{id}$ ; concatenatie geeft producten; omkeren van een programma (vraag 7) geeft inversen. Het effect van een programma fixeert cel $16$ (leegte start en eindigt thuis), dus $H \leq \mathfrak{S}_{15}$ . Evenheid: 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 schuiven vanuit de leegte in $16$ : zet $16 \to 12$ stuurt de inhoud van $12$ naar $16$ ; zet $12 \to 11$ stuurt de inhoud van $11$ naar $12$ ; zet $11 \to 15$ stuurt de inhoud van $15$ naar $11$ ; zet $15 \to 16$ stuurt de inhoud geparkeerd in $16$ (oorspronkelijk in $12$ ) naar $15$ . Netto: $11 \mapsto 12$ , $12 \mapsto 15$ , $15 \mapsto 11$ , leegte thuis: het effect is $(11\ 12\ 15)$ . De omgekeerde ronde maakt het ongedaan: effect $(11\ 12\ 15)^{-1} = (11\ 15\ 12)$ . Beide zijn effecten van programma’s, dus in $H$ .

11. Aangrenzendheid van opeenvolgende cellen: binnen elk genoemd paar verschillen de cellen met $1$ in dezelfde rij ( $16{-}15$ , $15{-}14$ , $14{-}13$ ; $1{-}2$ , $2{-}3$ , $3{-}4$ ; $8{-}7$ , $7{-}6$ ; $10{-}11$ , $11{-}12$ ) of met $4$ binnen een kolom ( $13{-}9$ , $9{-}5$ , $5{-}1$ ; $4{-}8$ ; $6{-}10$ ; $12{-}16$ ): een gesloten wandeling door alle $16$ cellen, van lengte $16$ . Effect: zoals in vraag 10, schrijvend de bezochte cellen $c_0 = 16, c_1 = 15, \dots, c_{15} = 12$ : de inhoud van $c_i$ beweegt naar $c_{i-1}$ voor $i = 2, \dots, 15$ , en de inhoud van $c_1$ , geparkeerd in $16$ na de eerste zet, wordt naar $c_{15}$ gevoerd door de laatste zet. Dus beeldt het effect $15 \mapsto 12$ af, 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 cykelorde start $x_0 = 15$ , $x_1 = 12$ , $x_2 = 11$ , en $(x_0\ x_1\ x_2) = (15\ 12\ 11)$ beeldt $15 \mapsto 12 \mapsto 11 \mapsto 15$ af — precies $(11\ 15\ 12)$ , de omgekeerde elementaire ronde.

12. Zij $\gamma = (a\ b\ c)$ en $x \in \intint1n$ . Als $x = g(a)$ : $g\gamma g^{-1}(x) = g(\gamma(a)) = g(b)$ ; evenzo $g(b) \mapsto g(c)$ en $g(c) \mapsto g(a)$ . Als $x \notin \{g(a), g(b), g(c)\}$ , dan is $g^{-1}(x) \notin \{a,b,c\}$ gefixeerd door $\gamma$ , dus is $x$ gefixeerd. Dus $g\gamma g^{-1} = (g(a)\ g(b)\ g(c))$ . En voor $g, h \in H$ is $ghg^{-1} \in H$ door de deelgroepaxioma’s.

13. $\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 mod $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 inversie na, neem $s = (a\ b\ c)$ en $t = (b\ c\ d)$ aan (een $3$ -cykel op $\{a,b,c\}$ is $(a\ b\ c)$ of haar inverse; evenzo op $\{b,c,d\}$ ; een voortbrenger door haar inverse vervangen laat $\langle s, t\rangle$ ongewijzigd). Dan, $t$ eerst toepassend,

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

een dubbele transpositie. De deelgroep $G = \langle s, t\rangle$ bestaat uit even permutaties van de vier letters, dus $G \leq A_4$ en $\abs G \mid 12$ ; ze 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 deelgroepen). Als $A_4$ een deelgroep $K$ van orde $6$ had, zou ze index $2$ hebben, en dan $g^2 \in K$ voor elke $g \in A_4$ : voor $g \in K$ is dit duidelijk; voor $g \notin K$ zijn de enige nevenklassen $K$ en $gK$ , dus is de nevenklasse $g^2K$ of $K$ of $gK$ , en $g^2K = gK$ zou $g \in K$ dwingen. Dus ligt elk kwadraat in $K$ . Maar elke $3$ -cykel $\gamma$ is een kwadraat, $\gamma = (\gamma^2)^2$ , en $A_4$ bevat acht $3$ -cykels: $8 > 6$ , contradictie. Dus $\abs G = 12$ : $G = A_4$ .

15. Breid $u \mapsto a$ , $v \mapsto b$ uit tot een bijectie $g_0$ van $X$ (stuur de overblijvende $k - 2$ letters bijectief ergens op het complement van $\{a, b\}$ ). Als $g_0$ oneven is, kies twee verschillende letters $s_1, t_1 \in X \setminus \{u, v\}$ (mogelijk: $k \geq 4$ ) en vervang $g_0$ door $g_0 \circ (s_1\ t_1)$ , die even is en nog $u \mapsto a$ , $v \mapsto b$ stuurt. Breid uit met de identiteit buiten $X$ : een even permutatie $g \in G$ (ze is een even permutatie van $X$ ). Dan vraag 12:

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

gebruikend $g(w) = w$ .

16. Elke $3$ -cykel van $X \cup \{w\}$ ligt in $G$ : die gesteund in $X$ zijn even permutaties van $X$ ; een met steun $\{a, b, w\}$ is $(a\ b\ w)$ of $(b\ a\ w)$ , beide geleverd door vraag 15. Door Oefening 1.6 brengen de $3$ -cykels van de $(k+1)$ -elementverzameling $X \cup \{w\}$ haar alternerende groep voort, dus bevat $G$ elke even permutatie van $X \cup \{w\}$ . Aaneenrijgen: 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)$ (steunen delen $\{x_1, x_2\}$ ) geeft alle even permutaties van $X_4 = \{x_0, x_1, x_2, x_3\}$ . Als $G$ alle even permutaties van $X_m = \{x_0, \dots, x_{m-1}\}$ bevat ( $4 \leq m \leq 14$ ), dan heeft $s_{m-2} = (x_{m-2}\ x_{m-1}\ x_m)$ $u = x_{m-2}, v = x_{m-1} \in X_m$ en 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 cellen), 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: $A_{15} = \langle s_0, \dots, s_{12}\rangle \subseteq H$ ; vraag 9: $H \subseteq A_{15}$ . Dus $H = A_{15}$ , van orde $15!/2 = 653\,837\,184\,000$ : elke even herschikking van de vijftien tegels is het effect van een programma.

18. Vraag 8 reduceerde $R = \{I = +1\}$ tot het realiseren van elke even $\rho \in \mathfrak{S}_{15}$ door een programma: gedaan door vraag 17. Met vraag 6, $\abs R = 16!/2 = 10\,461\,394\,944\,000$ . Twee klassen: laat $t_0 = (14\ 15)$ op inhouden werken: $\varphi(\sigma) = t_0 \circ \sigma$ . Een legale zet vanuit $\sigma$ is een legale zet vanuit $\varphi(\sigma)$ (de lege cel is ongewijzigd: $(t_0\sigma)^{-1}(16) = \sigma^{-1}(t_0(16)) = \sigma^{-1}(16)$ , en de bewogen cel is dezelfde), en $\varphi(\sigma \circ \tau) = \varphi(\sigma) \circ \tau$ : $\varphi$ stuurt zetrijen naar zetrijen, bijectief (ze is een involutie). Ze keert $I$ om: $\varepsilon(t_0\sigma) = -\varepsilon(\sigma)$ , zelfde lege cel. Dus beeldt $\varphi$ de klasse $R = \{I = +1\}$ van $\mathrm{id}$ bijectief af op de klasse van $\varphi(\mathrm{id}) = \sigma_L$ , die daarom heel $\{I = -1\}$ is: precies twee klassen. Dit is de stelling van Johnson–Story.

19. Indexeer de cellen in leesvolgorde en zij $k = 4(i - 1) + j$ de cel van de leegte. Tel de inversies van $\sigma$ (paren van cellen $x < y$ met $\sigma(x) > \sigma(y)$ ): paren van twee tegelcellen dragen $N$ bij; paren die de leegte betreffen: cellen na de leegte houden alle tegels $< 16$ , elk geïnverteerd ( $16 - k$ paren), cellen ervoor zijn nooit geïnverteerd. Dus $\varepsilon(\sigma) = (-1)^{N + 16 - k} = (-1)^{N + k}$ . Omdat $k = 4(i-1) + j \equiv j \pmod 2$ ,

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

gebruikend $i = 5 - r$ . Door vraag 18 is $\sigma$ oplosbaar desda $I(\sigma) = +1$ desda $N + r$ oneven is. Controle: opgelost, $N = 0$ , $r = 1$ : oneven, oplosbaar; Loyd, $N = 1$ , $r = 1$ : even, 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$ ; en $\sigma \circ h^{-1}$ is weer een leegte-thuis-configuratie ( $h$ fixeert cel $16$ ). Vrij: $\sigma \circ h^{-1} = \sigma$ geeft $h^{-1} = \mathrm{id}$ (stel samen met $\sigma^{-1}$ ). Banen = programmaklassen: vraag 9 zegt dat de configuraties bereikbaar vanuit $\sigma$ door programma’s precies de $\sigma \circ \pi^{-1}$ zijn, $\pi \in H$ : de baan $H \cdot \sigma$ . Telling: vrijheid maakt $h \mapsto h \cdot \sigma$ injectief, dus heeft elke baan $\abs H = 15!/2$ elementen; de $15!$ leegte-thuis-configuraties splijten daarom in $15!\,/\,(15!/2) = 2$ banen — de leegte-thuis-schaduw van de twee Johnson–Story-klassen.

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

22. Omtreksronde $9 \to 8 \to 7 \to 4 \to 1 \to 2 \to 3 \to 6 \to 9$ (alle stappen aangrenzend; lengte $8$ , even): door de boekhouding van vraag 11 met $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 centrum $5$ fixeert (inhoud van $7$ beweegt naar $8$ , van $4$ naar $7$ , van $1$ naar $4$ , van $2$ naar $1$ , van $3$ naar $2$ , van $6$ naar $3$ , en van $8$ naar $6$ ). Hoekronde $9 \to 6 \to 5 \to 8 \to 9$ : effect $(6\ 8\ 5)$ (inhoud van $5$ beweegt naar $6$ , van $8$ naar $5$ , van $6$ — geparkeerd bij $9$ — naar $8$ ). Stel $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):

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

omdat $\zeta'$ $5$ fixeert. De steunen 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\}$ . Dan voegt $T_2 = (y_3\ y_2\ 5)$ $y_3$ toe door lemma B (haar letters $y_2, 5$ liggen in de huidige verzameling, $k = 4$ ), en $T_3, T_4, T_5$ voegen $y_4, y_5, y_6$ beurtelings toe: alle even permutaties van de acht niet-thuis-cellen liggen in de programmagroep, die ook uit even permutaties bestaat (het argument van vraag 9 is bord-onafhankelijk). Dus $H_{3\times3} = A_8$ , en de redenering van vragen 6, 8, 18 — eveneens bord-onafhankelijk — toont dat de bereikbare configuraties precies die met $I = +1$ zijn: de helft van $9!$ , d.w.z. $181\,440$ .

23. Label de cellen $0, \dots, n-1$ rond de cykel. Een zet verwisselt de leegte met een van haar twee buren. Lees de tegels in cyclische orde startend net na de leegte: een woord $w$ dat de $n - 1$ tegels opsomt. De leegte één stap vooruit bewegen vervangt $(p, w)$ door $(p + 1, \rho w)$ , waarbij $p$ de lege cel is en $\rho$ het woord cyclisch met één roteert; de achterwaartse zet is de inverse. De cyclische orde van de tegels (het woord op rotatie na) is dus invariant. De bereikbare klasse 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), de kgv is $n(n-1)$ omdat $\gcd(n, n-1) = 1$ : elke klasse heeft precies $n(n-1)$ configuraties, alle met dezelfde ketting. 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 alle obstructie; de rijkdom van het $4 \times 4$ -bord — waar pariteit de enige obstructie is — is een echt meetkundig feit, geen formeel.

24. Beide trays hebben de tegels in volledig omgekeerde orde, dus $N = \binom{15}{2} = 105$ in beide gevallen (elk paar tegels is geïnverteerd). Leegte thuis: $r = 1$ , $N + r = 106$ even: onoplosbaar. Leegte in cel $1$ : de leegte is in de bovenste rij, $r = 4$ , $N + r = 109$ oneven: oplosbaar. Twee trays die alleen verschillen in waar het gat zit vallen aan tegengestelde kanten van de muur.

25. Morfisme-eigenschap: ze zet “één zet = één transpositie” om in “één zet = één tekenwisseling” (vragen 2, 4), waardoor $I$ zet voor zet berekenbaar is. Lagrange: ze dwong $6 \mid \abs{\langle s, t\rangle}$ in lemma A en mat de nevenklassen in de orde- $6$ -uitsluiting (vraag 14). Voortbrenging door $3$ -cykels: ze zette “ $H$ bevat genoeg $3$ -cykels” om in “ $H$ bevat heel $A_{15}$ ” (vraag 16). Conjugatie: ze fabriceerde de vijftien opeenvolgende $3$ -cykels uit een enkele $2 \times 2$ -ronde vervoerd door de grote ronde (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 volledig opgelost precies wanneer de twee grenzen samenkomen — hier, op de helft.