Matematika Universitas — Tahun 2 · Bachelor Year 2

1Himpunan dan Struktur

Bab pembuka ini mempertajam landasan yang diletakkan pada jilid Tahun ke-1 menjadi perkakas kerja sehari-hari: kalkulus himpunan dan kuosien, perbandingan himpunan tak hingga (keterbilangan, Cantor–Bernstein), serta teori struktur grup dan ring — teorema Lagrange, grup simetri beserta tanda permutasinya, ideal, dan teorema sisa Cina. Semua yang ada di sini dipakai tiada henti pada sisa buku: tanda permutasi membangun determinan (Bab 2), ring kuosien menggerakkan aritmetika, dan keterbilangan menjadi alas bagi topologi maupun peluang.

1.1 Himpunan, pemetaan, kuosien

Kita memakai dengan bebas bahasa himpunan, pemetaan, serta relasi ekuivalensi dan relasi urutan yang disiapkan pada jilid Tahun ke-1. Dua peningkatan layak dinyatakan secara utuh.

Proposisi 1.1 (Peta dan prapeta suatu keluarga)

Misalkan $f \colon E \to F$ dan misalkan $(A_i)_{i \in I}$ , $(B_j)_{j \in J}$ keluarga himpunan bagian dari $E$ dan dari $F$ berturut-turut. Maka

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{kesamaan bila } f \text{ injektif}).

Bukti. Setiap kesamaan hanyalah penguraian definisi; misalnya $x \in f^{-1}(\bigcap B_j) \iff f(x) \in B_j$ untuk setiap $j$ $\iff x \in f^{-1}(B_j)$ untuk setiap $j$ . Kesamaan untuk peta dan gagalnya kesamaan pada kasus irisan (beserta perbaikan lewat keinjektifan) telah dibuktikan pada jilid Tahun ke-1 untuk dua himpunan; alasannya sama persis untuk keluarga sembarang. ∎

Contoh 1.2 (Ketika pengaitan peta benar-benar tegas)

Ambil $f \colon \R \to \R$ , $f(x) = x^2$ , dengan $A_1 = \intcc{-1}{0}$ dan $A_2 = \intcc{0}{1}$ . Maka

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

pengaitan pada Proposisi 1.1 setegas yang mungkin — kedua prapeta $\pm x$ dari satu nilai yang sama berada di $A_i$ yang berbeda. Keinjektifan justru melarang pemecahan semacam ini, dan itulah sebabnya prapeta (yang tak pernah menyatukan titik) memenuhi keempat kesamaan itu tanpa syarat, sedangkan peta kehilangan kesamaan untuk irisan. Pedoman praktis untuk seluruh buku: dorong prapeta melewati operasi himpunan sesuka hati; perlakukan peta dengan hati-hati.

Definisi 1.3 (Himpunan kuosien)

Misalkan $\mathcal{R}$ relasi ekuivalensi pada $E$ . Himpunan kuosien $E/\mathcal{R}$ adalah himpunan semua kelas ekuivalensi; surjeksi $\pi \colon E \to E/\mathcal{R}$ , $x \mapsto \mathrm{cl}(x)$ , disebut proyeksi kanonik.

Sifat universal (pemfaktoran): jika $f \colon E \to F$ selaras dengan $\mathcal{R}$ (yaitu $x \mathbin{\mathcal{R}} y \implies f(x) = f(y)$ ), maka terdapat tepat satu pemetaan $\overline f \colon E/\mathcal{R} \to F$ dengan $f = \overline f \circ \pi$ .

Bukti sifat universal. Ketunggalan: syarat $f = \overline f \circ \pi$ berbunyi

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

dan karena $\pi$ surjektif, setiap unsur $E/\mathcal{R}$ berbentuk $\mathrm{cl}(x)$ : seluruh nilai $\overline f$ sudah terpaksa. Keberadaan: ambil ungkapan di atas sebagai definisi $\overline f$ ; ungkapan itu tak bermakna ganda justru karena keselarasan — jika $\mathrm{cl}(x) = \mathrm{cl}(y)$ , maka $x \mathbin{\mathcal{R}} y$ , sehingga $f(x) = f(y)$ dan kedua calon nilai berimpit — dan ungkapan itu memfaktorkan $f$ menurut konstruksinya. Perhatikan pembagian tugas: kesurjektifan $\pi$ memberi ketunggalan, keselarasan memberi keberadaan. ∎

Contoh 1.4

$\Z/n\Z$ adalah kuosien $\Z$ oleh kekongruenan modulo $n$ ; pemeriksaan “terdefinisi dengan baik” pada jilid Tahun ke-1 tak lain adalah penerapan sifat universal. Kuosien mengubah “konstruksi yang selaras pada wakil kelas” menjadi pemetaan sejati — kita memakainya terus-menerus di bawah ini.

1.2 Keterbilangan dan kardinalitas

Definisi 1.5 (Ekuipotensi, keterbilangan)

Dua himpunan disebut ekuipoten apabila ada bijeksi yang menghubungkannya. Suatu himpunan disebut terbilang apabila ekuipoten dengan $\N$ (sebagian penulis memasukkan himpunan hingga; kita memakai ungkapan paling banyak terbilang untuk “hingga atau terbilang”).

Proposisi 1.6 (Sifat kestabilan)

Setiap himpunan bagian tak hingga dari $\N$ adalah terbilang; suatu himpunan paling banyak terbilang bila dan hanya bila ia terinjeksi ke $\N$ , bila dan hanya bila ia kosong atau merupakan peta surjektif dari $\N$ .
$\N \times \N$ terbilang; hasil kali dua himpunan yang paling banyak terbilang juga paling banyak terbilang.
Gabungan yang paling banyak terbilang atas himpunan yang paling banyak terbilang tetap paling banyak terbilang.
$\Z$ dan $\Q$ terbilang.

Bukti. (1) Susun $A \subseteq \N$ yang tak hingga lewat minimum berulang: $a_0 = \min A$ , $a_{k+1} = \min\,(A \setminus \{a_0, \dots, a_k\})$ (tak kosong karena $A$ tak hingga); pemetaan $k \mapsto a_k$ naik tegas, injektif, dan surjektif ke $A$ (setiap $a \in A$ hanya melampaui berhingga banyak unsur $A$ , jadi pasti tercapai). Jika $E$ terinjeksi ke $\N$ lewat $\varphi$ , maka $E$ ekuipoten dengan $\varphi(E) \subseteq \N$ : hingga atau terbilang. Jika $s \colon \N \to E$ surjektif, maka $x \mapsto \min s^{-1}(\{x\})$ menginjeksikan $E$ ke $\N$ .

(2) Pemetaan $(p, q) \mapsto 2^p(2q + 1) - 1$ adalah bijeksi $\N^2 \to \N$ (setiap bilangan bulat positif punya pemisahan ganjil–genap tunggal $2^p m$ dengan $m$ ganjil, menurut ketunggalan pemfaktoran). Untuk hasil kali: susun kedua injeksi.

(3) Diberikan himpunan $E_n$ beserta surjeksi $s_n \colon \N \to E_n$ (tak masalah bila ada $E_n$ yang hingga: ulangi saja nilainya), pemetaan $(n, k) \mapsto s_n(k)$ adalah surjeksi dari $\N^2$ yang terbilang ke $\bigcup E_n$ .

(4) $\Z = \N \cup (-\N^*)$ : gabungan terbilang. $\Q$ adalah peta surjektif dari $\Z \times \N^*$ (pemetaan pecahan), jadi paling banyak terbilang, sekaligus tak hingga. ∎

Contoh 1.7 (Fungsi pemasangan, dihitung)

Bijeksi $(p, q) \mapsto 2^p(2q + 1) - 1$ dalam bukti di atas pantas dilihat sedang bekerja. Nilai-nilai pertamanya:

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

Baris $p$ menghimpun bilangan $n$ yang $n + 1$ -nya habis dibagi tepat oleh $2^p$ : setiap bilangan cacah muncul tepat sekali. Pembacaan baliknya segamblang penyandiannya: untuk $n = 43$ , faktorkan $n + 1 = 44 = 2^2\cdot 11 = 2^2(2\cdot5 + 1)$ , sehingga $(p, q) = (2, 5)$ . Pelajaran penutupnya: bukti keterbilangan sering kali berupa algoritme yang menyamar — di sini, “keluarkan semua faktor dua”.

Contoh 1.8 (Bilangan aljabar adalah terbilang)

Suatu bilangan kompleks disebut aljabar apabila ia menolkan suatu polinomial tak nol berkoefisien rasional. Himpunan $\overline\Q$ semua bilangan aljabar adalah terbilang: polinomial berderajat $\leq d$ atas $\Q$ terinjeksi ke $\Q^{d+1}$ , yaitu hasil kali hingga atas himpunan terbilang (Proposisi 1.6 (2)); gabungan atas $d$ menyusun semua polinomial rasional tak nol sebagai $P_0, P_1, P_2, \dots$ ; setiap $P_k$ punya berhingga banyak akar; dan

\overline\Q = \bigcup_{k \in \N}\ \{\text{akar-akar } P_k\}

adalah gabungan terbilang atas himpunan hingga (Proposisi 1.6 (3)), tak hingga karena memuat $\Q$ . Digabungkan dengan ketakterbilangan $\R$ (Teorema 1.9 di bawah), ini membuktikan — tanpa menunjukkan satu pun contohnya — bahwa bilangan transenden memang ada dan justru merupakan mayoritas yang tak terbilang: itulah hujah pencacahan Cantor tahun 1874, keberadaan semata-mata lewat kardinalitas.

Teorema 1.9 (Cantor; ketakterbilangan $\R$ )

Untuk setiap himpunan $E$ , tidak ada surjeksi $E \to \mathcal{P}(E)$ .
$\R$ tidak terbilang.

Bukti. (1) telah dibuktikan pada jilid Tahun ke-1 (lewat himpunan diagonal $D = \{x : x \notin f(x)\}$ ).

(2) Andaikan $(x_n)_{n \in \N}$ mendaftar seluruh $\R$ . Bangun ruas bersarang $I_0 \supseteq I_1 \supseteq \dots$ dengan $\abs{I_n} = 3^{-n}$ dan $x_n \notin I_n$ : bagi ruas yang sedang dipegang menjadi tiga pertigaan tertutup; paling sedikit satu pertigaan menghindari $x_n$ (sebuah titik menyinggung paling banyak dua dari ketiganya). Teorema ruas bersarang (ujung-ujung yang berdampingan) memberi $\ell \in \bigcap_n I_n$ ; tetapi $\ell = x_N$ untuk suatu $N$ , padahal $x_N \notin I_N$ : kontradiksi. ∎

Teorema 1.10 (Cantor–Bernstein)

Jika $E$ terinjeksi ke $F$ dan $F$ terinjeksi ke $E$ , maka $E$ dan $F$ ekuipoten.

Bukti. Misalkan $f \colon E \to F$ dan $g \colon F \to E$ dua injeksi. Untuk setiap titik (di $E$ maupun di $F$ ), telusuri rantai leluhurnya, yakni barisan prapeta berurutan $x \mapsto g^{-1}(x) \mapsto f^{-1}(g^{-1}(x)) \mapsto \dots$ — setiap langkah terdefinisi selama titik yang sedang dipegang terletak di peta injeksi yang bersangkutan, dan langkah itu tunggal berkat keinjektifan. Ada tiga nasib yang saling lepas: rantai berhenti di suatu titik $E \setminus g(F)$ (berpangkal di $E$ ), berhenti di suatu titik $F \setminus f(E)$ (berpangkal di $F$ ), atau tak pernah berhenti. Ini memilah $E = E_E \cup E_F \cup E_\infty$ dan $F = F_E \cup F_F \cup F_\infty$ menurut pangkalnya.

Sekarang amati: $f$ memetakan $E_E$ pada $F_E$ — rantai $f(x)$ adalah rantai $x$ yang didahului satu langkah, jadi pangkalnya sama; dan setiap $y \in F_E$ punya rantai dengan sekurang-kurangnya satu langkah (pangkalnya di $E$ ), sehingga $y = f(x)$ dengan $x \in E_E$ . Alasan yang sama memberi bijeksi $f \colon E_\infty \to F_\infty$ dan $g \colon F_F \to E_F$ . Setelah direkatkan,

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

merupakan bijeksi dari $E$ pada $F = F_E \cup F_\infty \cup F_F$ : ia bijektif sepotong demi sepotong, dan ketiga potongan sasarannya saling lepas. ∎

Contoh 1.11

$\intoo{0}{1}$ dan $\intcc{0}{1}$ ekuipoten: identitas menginjeksikan satu arah, $x \mapsto \frac{x + 1}{3}$ arah sebaliknya; teorema tadi memproduksi bijeksinya (yang mau tak mau tak kontinu). Demikian pula $\R$ , $\intoo{0}{1}$ (lewat bijeksi bertipe $\tanh$ ) dan $\mathcal{P}(\N)$ (uraian biner, Latihan 1.3) semuanya ekuipoten: itulah “kardinalitas kontinum”.

Contoh 1.12 (Ruas dan persegi)

$\intcc{0}{1}$ dan $\intcc{0}{1}^2$ ekuipoten — dimensi tidak tertangkap oleh kardinalitas. Satu injeksinya sepele: $x \mapsto (x, 0)$ . Untuk arah sebaliknya, kirim $(x, y)$ ke bilangan real yang angka desimalnya menyelang-nyeling angka $x$ dan angka $y$ ,

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

dengan memilih untuk tiap koordinat uraian yang tidak berakhir dengan $9$ berulang: dengan kesepakatan itu angka pada petanya menentukan angka $x$ dan $y$ , jadi pemetaannya injektif (ia tidak harus surjektif — peta tidak pernah memuat, misalnya, bilangan yang angka-angka pada posisi ganjilnya akhirnya selalu $9$ — dan itu tidak menjadi soal). Cantor–Bernstein (Teorema 1.10) lalu merakit bijeksi sejati. Kekontinuan, tentu saja, mustahil: tidak ada bijeksi kontinu di antara keduanya — bab-bab metrik menjelaskan sebabnya (keterhubungan membedakan garis dari bidang, Bab 4).

1.3 Grup

Definisi 1.13 (Subgrup yang dibangun; orde)

Misalkan $G$ grup dan $A \subseteq G$ . Subgrup yang dibangun oleh $A$ , ditulis $\langle A \rangle$ , adalah subgrup terkecil yang memuat $A$ — secara konkret, semua hasil kali hingga atas unsur $A$ dan inversnya. Suatu grup disebut siklik apabila dibangun oleh satu unsur: $\langle a\rangle = \{a^k : k \in \Z\}$ . Adapun orde unsur $a \in G$ adalah $\operatorname{ord}(a) = \abs{\langle a \rangle}$ (boleh jadi tak hingga); bila hingga, ia adalah $n \geq 1$ terkecil dengan $a^n = e$ , dan $a^k = e \iff \operatorname{ord}(a) \mid k$ .

Bukti pencirian orde. Jika ada $a^m = e$ dengan $m \geq 1$ , ambil $n \geq 1$ terkecil dengan $a^n = e$ . Unsur $e, a, \dots, a^{n-1}$ berbeda sepasang demi sepasang ( $a^{i} = a^{j}$ dengan $0 \leq i < j < n$ memberi $a^{j-i} = e$ , yang melawan keminimalan), dan setiap $a^k$ menyusut ke salah satunya lewat pembagian Euklides $k = nq + r$ : jadi $\langle a\rangle$ tepat punya $n$ unsur, dan $a^k = a^r = e \iff r = 0 \iff n \mid k$ . Jika tidak ada pangkat yang trivial, semua $a^k$ ( $k \in \Z$ ) berbeda (dengan alasan pembagian yang sama) dan ordenya tak hingga. ∎

Teorema 1.14 (Lagrange)

Misalkan $G$ grup hingga dan $H$ subgrupnya. Maka $\abs H$ membagi $\abs G$ . Khususnya orde setiap unsur membagi $\abs G$ , dan $a^{\abs G} = e$ untuk setiap $a \in G$ .

Bukti. Relasi $x \sim y \iff x^{-1}y \in H$ adalah relasi ekuivalensi (refleksif: $e \in H$ ; simetris: lewat invers; transitif: lewat hasil kali). Kelas $x$ adalah koset kiri $xH = \{xh : h \in H\}$ , dan $h \mapsto xh$ merupakan bijeksi $H \to xH$ (dengan invers $y \mapsto x^{-1}y$ ): jadi semua kelas punya $\abs H$ unsur. Kelas-kelas itu memilah $G$ (teorema pemilahan umum pada jilid Tahun ke-1), sehingga $\abs G = \abs H \times (\text{banyaknya koset})$ . Untuk sebuah unsur: terapkan hasil ini pada $H = \langle a\rangle$ ; maka $a^{\abs G} = (a^{\operatorname{ord} a})^{\abs G / \operatorname{ord} a} = e$ . ∎

Contoh 1.15 (Koset dalam kerja: $A_3$ di dalam $\mathfrak{S}_3$ )

Ambil $G = \mathfrak{S}_3$ (berorde $6$ ) dan $H = A_3 = \{\mathrm{id},\ (1\,2\,3),\ (1\,3\,2)\}$ . Koset kirinya adalah

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

dua kelas beranggotakan tiga unsur yang memilah $G$ , persis seperti dituntut oleh pencacahan $\abs G = \abs H \times (\text{banyaknya koset})$ — dan tampak jelas bahwa itulah pemilahan atas permutasi genap dan permutasi ganjil. Perhatikan $(1\,3)H = (1\,2)H$ walaupun $(1\,3) \neq (1\,2)$ : koset adalah kelas, bukan sesuatu yang dinamai menurut wakilnya, dan $x^{-1}y \in H$ satu-satunya perbandingan yang sah. Gambaran dua kelas ini berlaku umum untuk tanda permutasi: $A_n$ bersama satu-satunya koset pendampingnya membelah $\mathfrak{S}_n$ tepat menjadi dua, dan begitulah soal akhir pekan bab ini mencacah posisi teka-teki yang terjangkau.

Contoh 1.16

Dua panen langsung. Grup berorde prima pasti siklik: jika $\abs G = p$ prima dan $a \neq e$ , maka $\operatorname{ord}(a)$ membagi $p$ dan tidak sama dengan $1$ , jadi ia sama dengan $p$ : $\langle a\rangle = G$ . Kisi subgrup $\Z/12\Z$ : menurut Proposisi 1.17 di bawah, ada tepat satu subgrup untuk tiap pembagi $12$ — berorde $1, 2, 3, 4, 6, 12$ , yang berturut-turut dibangun oleh $\overline 0$ , $\overline 6$ , $\overline 4$ , $\overline 3$ , $\overline 2$ , $\overline 1$ . Peringatan penutup: konvers teorema Lagrange tidak berlaku umum — $A_4$ berorde $12$ tetapi tidak punya subgrup berorde $6$ , sebagaimana kita buktikan pada soal akhir pekan bab ini (Soal 1.1, pertanyaan 14). Lagrange membatasi orde yang mungkin; ia tidak menjanjikan orde itu ada.

Kisi subgrup ℤ/12ℤ: satu subgrup untuk tiap pembagi 12 (), dengan sebuah rusuk bila yang satu memuat yang lain dengan indeks prima. Pemuatan berjalan berlawanan dengan keterbagian pembangunnya: 4 ⊂eq 2 karena 4 adalah kelipatan 2. — Kisi subgrup $\Z/12\Z$ : satu subgrup untuk tiap pembagi $12$ (Proposisi 1.17), dengan sebuah rusuk bila yang satu memuat yang lain dengan indeks prima. Pemuatan berjalan *berlawanan* dengan keterbagian pembangunnya: $\langle\overline 4\rangle \subseteq \langle\overline2\rangle$ karena $4$ adalah kelipatan $2$ .

Proposisi 1.17 (Grup siklik)

Misalkan $G = \langle a \rangle$ siklik berorde $n$ .

$G$ isomorfik dengan $(\Z/n\Z, +)$ , lewat $\overline k \mapsto a^k$ .
Setiap subgrup $G$ adalah siklik; untuk tiap pembagi $d \mid n$ ada tepat satu subgrup berorde $d$ , yakni $\langle a^{n/d}\rangle$ .
$a^k$ membangun $G$ bila dan hanya bila $\gcd(k, n) = 1$ : jadi $G$ punya $\varphi(n)$ pembangun (fungsi Euler).

Bukti. (1) Pemetaan $k \mapsto a^k$ dari $\Z$ pada $G$ selaras dengan kekongruenan modulo $n$ ( $a^{k} = a^{k'} \iff n \mid k - k'$ , menurut pencirian orde); sifat universal (Definisi 1.3) menghasilkan morfisma bijektif yang terdefinisi dengan baik dari $\Z/n\Z$ .

(2) Misalkan $H \leq G$ tak trivial dan $m$ bilangan $\geq 1$ terkecil dengan $a^m \in H$ . Pembagian Euklides menunjukkan $H = \langle a^m\rangle$ (untuk $a^k \in H$ : dari $k = mq + r$ terpaksa $a^r \in H$ , jadi $r = 0$ ), dan $m \mid n$ (bagilah $n$ oleh $m$ : $a^{n \bmod m} \in H$ ). Akibatnya $\abs H = n/m$ ; dengan mengambil $m = n/d$ setiap pembagi $d$ terwujud. Ketunggalan: menurut uraian di atas, sembarang subgrup berorde $d$ berbentuk $\langle a^m \rangle$ dengan $n/m = d$ — sehingga $m = n/d$ terpaksa dan subgrupnya tertentu.

(3) Kita klaim $\operatorname{ord}(a^k) = \frac{n}{\gcd(k, n)}$ . Tulis $d = \gcd(k, n)$ . Untuk sembarang $m \geq 1$ , pencirian orde pada Definisi 1.13 memberi rantai kesetaraan berikut

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

langkah terakhir memakai lema Gauss, karena $\frac nd$ dan $\frac kd$ saling prima. Bilangan $m$ terkecil yang demikian adalah $\frac nd$ : $\operatorname{ord}(a^k) = \frac n{\gcd(k,n)}$ , yang sama dengan $n$ bila dan hanya bila $\gcd(k, n) = 1$ . Ada $\varphi(n)$ kelas $k$ modulo $n$ yang seperti itu. ∎

1.4 Grup simetri

Definisi 1.18

$\mathfrak{S}_n$ adalah grup permutasi atas $\intint{1}{n}$ (berorde $n!$ ). Sebuah siklus $(a_1\,a_2\,\cdots\,a_k)$ memetakan $a_1 \mapsto a_2 \mapsto \dots \mapsto a_k \mapsto a_1$ dan membiarkan yang lain tetap; $k$ disebut panjangnya, dan siklus berpanjang $2$ disebut transposisi. Dua siklus disebut saling lepas apabila penyangganya (titik yang tidak tetap) saling lepas.

Teorema 1.19 (Penguraian siklus)

Setiap permutasi $\sigma \neq \mathrm{id}$ adalah hasil kali siklus yang saling lepas, tunggal kecuali urutan faktornya. Siklus yang saling lepas komutatif, dan $\operatorname{ord}(\sigma)$ adalah KPK panjang-panjangnya.

Bukti. Tinjau relasi “orbit” pada penyangga $\sigma$ : $x \sim y$ bila $y = \sigma^k(x)$ untuk suatu $k \in \Z$ — sebuah relasi ekuivalensi. Setiap kelasnya berbentuk $\{x, \sigma(x), \dots, \sigma^{k-1}(x)\}$ (hingga, jadi iterasinya pasti berputar kembali — pengulangan pertama mesti kembali ke $x$ berkat keinjektifan) mengusung siklus $(x\ \sigma(x)\ \cdots\ \sigma^{k-1}(x))$ , dan $\sigma$ adalah hasil kali siklus-siklus itu: pada tiap orbit hanya siklus yang bersangkutan yang bekerja. Ketunggalan: sembarang pemfaktoran atas siklus saling lepas melahirkan orbit yang persis sama (siklus lewat $x$ mestilah $(x\ \sigma(x)\ \cdots)$ ). Siklus saling lepas komutatif karena menggerakkan titik yang berbeda; pernyataan tentang orde menyusul karena $\sigma^m = \mathrm{id}$ bila dan hanya bila pangkat ke- $m$ tiap siklus demikian (karena saling lepas), bila dan hanya bila tiap panjang membagi $m$ . ∎

Contoh 1.20 (Tipe siklus sebagai pencacahan)

Ada berapa permutasi di $\mathfrak{S}_9$ bertipe siklus $(4, 3, 2)$ — satu siklus panjang $4$ , satu siklus panjang $3$ , dan satu transposisi? Pilih penyangganya sekaligus urutan siklisnya:

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

jajarkan kesembilan lambang itu dalam satu baris ( $9!$ cara), kurung empat yang pertama, tiga berikutnya, dan dua terakhir menjadi siklus, lalu bagi dengan banyaknya perputaran di dalam tiap kurung ( $4$ , $3$ dan $2$ buah) yang memberi permutasi yang sama. (Panjang siklusnya di sini berbeda-beda, jadi tidak perlu pembagian lagi; panjang yang sama akan menuntut pembagian oleh permutasi antar kurung yang sepanjang itu pula.) Setiap permutasi semacam itu berorde $\operatorname{lcm}(4,3,2) = 12$ dan bertanda $(-1)^3(-1)^2(-1)^1 = +1$ (Teorema 1.19 dan teorema tanda permutasi di bawah). Satu partisi $9$ , satu kelas konjugasi, satu pencacahan — kombinatorika $\mathfrak{S}_n$ tak lain adalah aritmetika partisi.

Teorema 1.21 (Tanda permutasi)

Hanya ada satu morfisma grup $\varepsilon \colon \mathfrak{S}_n \to \{\pm 1\}$ (untuk $n \geq 2$ ) yang bernilai $-1$ pada transposisi: itulah tanda permutasi. Lebih lanjut $\varepsilon(\sigma) = (-1)^{I(\sigma)}$ dengan $I(\sigma)$ menyatakan banyaknya inversi (pasangan $i < j$ dengan $\sigma(i) > \sigma(j)$ ), siklus berpanjang $k$ bertanda $(-1)^{k-1}$ , dan grup alternating $A_n = \ker\varepsilon$ berorde $\frac{n!}{2}$ .

Bukti. Keberadaan. Untuk $\sigma \in \mathfrak{S}_n$ tetapkan

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

Nilai mutlak faktor-faktornya berkali menjadi $1$ (pasangan tak terurut $\{\sigma(i), \sigma(j)\}$ menjelajahi semua pasangan), sehingga $\varepsilon(\sigma) = (-1)^{I(\sigma)} \in \{\pm1\}$ . Morfisma: untuk $\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),

karena hasil kali di tengah sama dengan $\varepsilon(\sigma)$ setelah diindeks ulang menurut pasangan $\{\tau(i), \tau(j)\}$ (tiap pasangan tak terurut muncul sekali, dan pembilang serta penyebut berganti tanda bersama-sama). Transposisi $\tau = (a\,b)$ dengan $a < b$ punya inversi sebanyak bilangan ganjil; dicacah dengan saksama: pasangan terbalik $(i, j)$ , $i < j$ , dengan $\tau(i) > \tau(j)$ adalah

(a, j) \ \text{untuk } a < j < b, \qquad (i, b) \ \text{untuk } a < i < b, \qquad (a, b) \ \text{sendiri},

yakni sebanyak $(b - a - 1) + (b - a - 1) + 1 = 2(b - a) - 1$ , sebuah bilangan ganjil. (Cara lain: periksa langsung $(1\,2)$ , yang punya satu inversi, lalu konjugasikan — unsur yang sekonjugasi bertanda sama karena $\varepsilon$ adalah morfisma ke grup abelian.) Jadi $\varepsilon((a\,b)) = (-1)^{2(b-a)-1} = -1$ .

Ketunggalan. Transposisi membangun $\mathfrak{S}_n$ (sebab untuk sebarang siklus berlaku $(a_1\cdots a_k) = (a_1\,a_k)(a_1\,a_{k-1})\cdots(a_1\,a_2)$ , lalu Teorema 1.19 merampungkannya); morfisma ke $\{\pm1\}$ ditentukan oleh nilainya pada pembangun.

Akibat. Kesamaan siklus di atas menuliskan siklus berpanjang $k$ sebagai $k - 1$ transposisi: tandanya $(-1)^{k-1}$ . Tentang $A_n$ : morfisma $\varepsilon$ surjektif (transposisi ada untuk $n \geq 2$ ), dan kedua “koset” $A_n$ dan $(1\,2)A_n$ ekuipoten serta memilah $\mathfrak{S}_n$ (dengan hujah Lagrange): jadi $\abs{A_n} = \frac{n!}{2}$ . ∎

Contoh 1.22

$\sigma = \begin{pmatrix} 1&2&3&4&5&6\\ 3&6&5&4&1&2 \end{pmatrix} = (1\,3\,5)(2\,6)$ : berorde $\operatorname{lcm}(3,2) = 6$ , bertanda $(-1)^{2}\cdot(-1)^{1} = -1$ . Tanda permutasi adalah pemeriksaan paritas tercepat atas suatu pengocokan — sekaligus mesin penggerak determinan pada Bab 2.

Contoh 1.23 (Tiga jalan menuju satu tanda)

Misalkan $\sigma \in \mathfrak{S}_5$ mengirim $1, 2, 3, 4, 5$ ke $3, 5, 4, 1, 2$ . Lewat siklus: $1 \mapsto 3 \mapsto 4 \mapsto 1$ dan $2 \mapsto 5 \mapsto 2$ , jadi $\sigma = (1\,3\,4)(2\,5)$ dan $\varepsilon(\sigma) = (-1)^{2}(-1)^{1} = -1$ . Lewat inversi: pada deretan nilai $3, 5, 4, 1, 2$ pasangan yang terbalik adalah $(3,1)$ , $(3,2)$ , $(5,4)$ , $(5,1)$ , $(5,2)$ , $(4,1)$ , $(4,2)$ : tujuh buah, dan $(-1)^7 = -1$ . Lewat transposisi: $\sigma = (1\,4)(1\,3)(2\,5)$ , tiga faktor, $(-1)^3 = -1$ . Tiga perhitungan, satu paritas: ketunggalan pada Teorema 1.21 menjamin tidak ada tata cara pembukuan yang dapat membuat ketiganya berselisih — dan justru itulah yang membuat $\varepsilon$ berguna sebagai invarian (lihat soal akhir pekan).

Catatan 1.24 (Ke mana tanda permutasi melangkah setelah ini)

Tanda permutasi adalah benih tiga panen berikutnya: ia membangun determinan beserta aturan hasil kalinya pada Bab 2; ia menggerakkan invarian paritas untuk teka-teki kombinatorial (soal akhir pekan bab ini menyelesaikan teka-teki lima belas dengannya); dan grup alternating $A_n$ yang didefinisikannya menjadi tokoh utama pada jilid Tahun ke-3, tempat kesederhanaannya untuk $n \geq 5$ menjelaskan mengapa persamaan berderajat $5$ tidak terpecahkan dengan akar.

1.5 Ring, ideal, kuosien

Definisi 1.25 (Ideal)

Misalkan $A$ ring komutatif. Sebuah ideal $I \subseteq A$ adalah subgrup aditif dengan sifat $a x \in I$ untuk setiap $a \in A$ , $x \in I$ . Kernel morfisma ring adalah ideal; $I = A$ bila dan hanya bila $1 \in I$ , bila dan hanya bila $I$ memuat sebuah unit. Ideal yang dibangun oleh $x$ adalah $xA = \{xa\}$ (sebuah ideal utama).

Teorema 1.26 (Ideal pada $\Z$ dan pada $K[X]$ )

Setiap ideal $\Z$ berbentuk $n\Z$ untuk suatu $n \in \N$ yang tunggal; setiap ideal $K[X]$ ( $K$ sebuah lapangan) berbentuk $P\,K[X]$ untuk suatu $P$ monik (atau nol) yang tunggal. Akibatnya FPB ada pada kedua ring itu beserta relasi Bézout: $x\Z + y\Z = \gcd(x,y)\Z$ , demikian pula untuk polinomial.

Bukti. Untuk $\Z$ ini tak lain teorema subgrup pada jilid Tahun ke-1 (sebuah ideal khususnya adalah subgrup, dan $n\Z$ memang ideal). Untuk $K[X]$ : misalkan $I \neq \{0\}$ sebuah ideal dan $P \in I$ tak nol berderajat minimal, dinormalkan menjadi monik. Untuk $F \in I$ , pembagian Euklides $F = PQ + R$ memberi $R = F - PQ \in I$ dengan $\deg R < \deg P$ : keminimalan memaksa $R = 0$ , jadi $I = P\,K[X]$ . Ketunggalan: dua pembangun monik saling membagi. Pernyataan Bézout tak lain kesamaan ideal $x\Z + y\Z$ (atau padanan polinomialnya) dengan ideal utama yang dibangun FPB — persis definisi FPB yang dipakai pada Tahun ke-1, kini dikenali sebagai pernyataan tentang ideal. ∎

Contoh 1.27 (FPB polinomial, dua jalan)

Hitung $\gcd(X^3 - 1,\ X^2 - 1)$ di $\Q[X]$ . Lewat Euklides:

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

jadi FPB-nya $X - 1$ , dan penyulihan balik memberi relasi Bézout

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

Lewat ideal: ideal $(X^3 - 1)\Q[X] + (X^2 - 1)\Q[X]$ bersifat utama (Teorema 1.26); ia memuat $X - 1$ (lihat ungkapan di atas) dan termuat di $(X - 1)\Q[X]$ (kedua pembangunnya nol di $1$ , jadi keduanya kelipatan $X - 1$ ): maka pembangun moniknya adalah $X - 1$ . Pelajaran penutupnya: sudut pandang ideal mengenali FPB tanpa membagi — akar yang sama-sama dimiliki keduanya menempatkan idealnya, dan Euklides sekadar mengesahkannya.

Definisi 1.28 (Ring kuosien $\Z/n\Z$ , ditinjau ulang)

Untuk sebuah ideal $I$ pada $A$ , relasi $x \sim y \iff x - y \in I$ adalah relasi ekuivalensi yang selaras dengan $+$ dan $\times$ ; himpunan kuosien $A/I$ mewarisi struktur ring — itulah ring kuosien — sehingga $\pi \colon A \to A/I$ menjadi morfisma dengan kernel $I$ . Untuk $A = \Z$ , $I = n\Z$ ini tak lain $\Z/n\Z$ pada jilid Tahun ke-1, kini lengkap dengan sifat universalnya: setiap morfisma yang menolkan $I$ terfaktorkan lewat $A/I$ .

Teorema 1.29 (Teorema sisa Cina, bentuk ring)

Jika $\gcd(m, n) = 1$ , maka pemetaan

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

adalah isomorfisma ring. Akibatnya $\varphi(mn) = \varphi(m)\varphi(n)$ untuk $m, n$ saling prima, dan

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

Bukti. Pemetaan itu morfisma ring yang terdefinisi dengan baik (keselarasannya langsung terlihat). Keinjektifan: $x \equiv 0$ modulo $m$ dan modulo $n$ dengan $\gcd(m,n) = 1$ memaksa $mn \mid x$ (Gauss). Kesurjektifan: kedua ruas punya $mn$ unsur, jadi keinjektifan sudah cukup (kardinalitas hingga yang sama) — atau secara gamblang: dari relasi Bézout $um + vn = 1$ , kelas

x = b\,um + a\,vn

terpetakan ke $(a \bmod m,\ b \bmod n)$ , sebab $vn = 1 - um \equiv 1 \pmod m$ membuat $x \equiv a \pmod m$ , dan setangkup untuk modulo $n$ — itulah resep yang dipakai secara numerik pada Contoh 1.30. Unit berpadanan dengan pasangan unit (unit sebuah ring hasil kali adalah pasangan unit), sehingga $\varphi(mn) = \varphi(m)\varphi(n)$ . Untuk pangkat prima, $\varphi(p^k) = p^k - p^{k-1}$ (yang bukan unit modulo $p^k$ adalah kelipatan $p$ ); kemultiplikatifan lalu merakit rumus hasil kalinya. ∎

Contoh 1.30 (Membalik isomorfisma Cina)

Ambil $m = 8$ , $n = 9$ . Invers isomorfisma itu dibuat gamblang lewat dua idempoten: cari $u \equiv 1 \pmod 8$ , $u \equiv 0 \pmod 9$ serta $v \equiv 0 \pmod 8$ , $v \equiv 1 \pmod 9$ . Dari $u = 9k \equiv 1 \pmod 8$ : $k \equiv 1$ , jadi $u = 9$ ; dari $v = 8k \equiv 1 \pmod 9$ : $-k \equiv 1$ , $k \equiv 8$ , jadi $v = 64$ . Maka kelas $x = 9a + 64b$ modulo $72$ adalah satu-satunya penyelesaian $x \equiv a \pmod 8$ , $x \equiv b \pmod 9$ : untuk $a = 3$ , $b = 5$ diperoleh $27 + 320 = 347 \equiv 59 \pmod{72}$ — persis nilai antara yang ditemukan lewat penyulihan pada Latihan 1.8. Pelajaran penutupnya: $u$ dan $v$ memenuhi $u + v \equiv 1$ , $uv \equiv 0$ , $u^2 \equiv u$ , $v^2 \equiv v$ modulo $72$ ; keduanya adalah peta $(1, 0)$ dan $(0, 1)$ , dan setiap penguraian Cina pada dasarnya adalah penguraian $1$ menjadi idempoten yang saling ortogonal.

Teorema 1.31 (Euler; Fermat ditinjau ulang)

Unit-unit $\Z/n\Z$ membentuk grup berorde $\varphi(n)$ ; karenanya untuk $\gcd(a, n) = 1$ berlaku

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

dan teorema kecil Fermat adalah kasus $n = p$ prima, yang kini berjarak satu baris dari teorema Lagrange.

Bukti. Kelas yang punya invers persis kelas bilangan bulat yang saling prima dengan $n$ (jilid Tahun ke-1): ada $\varphi(n)$ buah, dan semuanya membentuk grup terhadap perkalian. Menurut Lagrange (Teorema 1.14): setiap unsur dipangkatkan orde grupnya menghasilkan unsur identitas. ∎

Contoh 1.32 (Grup unit tanpa pembangun)

Grup $(\Z/15\Z)^*$ punya $\varphi(15) = \varphi(3)\varphi(5) = 8$ unsur. Apakah ia siklik? Hitung ordenya lewat isomorfisma Cina $(\Z/15\Z)^* \simeq (\Z/3\Z)^* \times (\Z/5\Z)^*$ (unit modulo $15$ adalah pasangan unit): kedua faktornya berorde $2$ dan $4$ , jadi orde setiap unsur membagi $\operatorname{lcm}(2, 4) = 4 < 8$ — tidak ada unsur yang membangun. Secara konkret:

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

ordenya $4, 2, 4, 2, 2$ dan tidak pernah $8$ . Bandingkan dengan Latihan 1.10: $(\Z/p\Z)^*$ memang siklik untuk $p$ prima, sebab di sana grup unitnya berada di dalam sebuah lapangan. Teorema Euler tetap berlaku dengan pangkat $\varphi(15) = 8$ , tetapi pangkat semesta yang sebenarnya di sini adalah $4$ — Euler memberi batas atas, tidak selalu batas yang tajam.

Definisi 1.33 (Aljabar)

Sebuah aljabar- $K$ adalah ruang vektor $K$ bernama $A$ yang dilengkapi struktur ring dengan perkalian yang bilinear atas $K$ . Contohnya: $K[X]$ , $\mathcal{M}_n(K)$ , $\mathcal{L}(E)$ , ruang fungsi $\mathcal{F}(X, K)$ , dan $\C$ sebagai aljabar- $\R$ . Morfisma aljabar adalah morfisma ring yang linear; evaluasi $P \mapsto P(u)$ dari $K[X]$ ke $\mathcal{L}(E)$ (atau ke $\mathcal{M}_n(K)$ ) adalah contoh pusatnya, yang menggerakkan Bab 3.

Contoh 1.34 (Morfisma evaluasi dan kernelnya)

Ambil $A = \begin{pmatrix}0 & 1\\ 0 & 0\end{pmatrix}$ dan evaluasi $\varepsilon_A \colon \R[X] \to \mathcal{M}_2(\R)$ , $P \mapsto P(A)$ . Karena $A^2 = 0$ ,

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

(hanya suku tetap dan suku linear $P$ yang bertahan). Karenanya $\ker\varepsilon_A = \{P : P(0) = P'(0) = 0\} = X^2\,\R[X]$ : sebuah ideal utama, persis seperti diramalkan Teorema 1.26, dibangun oleh $X^2$ yang monik dan berderajat terkecil di dalam kernel — itulah polinomial minimal $A$ , bintang Bab 3. Petanya adalah aljabar komutatif berdimensi dua $\{aI + bA\}$ : morfisma evaluasi menciutkan $\R[X]$ yang berdimensi tak hingga menjadi aljabar kecil yang terhitungkan.

Catatan 1.35 (Pandangan ke depan: tiga melodi yang perlu disimak)

Tiga gagasan struktural dari bab ini berulang sepanjang jilid ini, setiap kali dengan orkestrasi yang makin tebal. Pemfaktoran lewat kuosien (Definisi 1.3): ia membangun $\Z/n\Z$ di sini, mendefinisikan pemetaan pada himpunan penyelesaian sistem linear di Bab 2, dan diam-diam menopang setiap hujah “terdefinisi dengan baik pada kelas”. Invarian: tanda permutasi adalah morfisma ke $\{\pm1\}$ yang tak terelakkan oleh langkah sah mana pun — logika yang sama memberi aturan hasil kali determinan (Bab 2), keawetan trace terhadap keserupaan, dan besaran kekal pada Bab 16. Mencacah dengan bersandar pada struktur: Lagrange mencacah lewat koset, dimensi mencacah lewat basis (Bab 2), multiplisitas mencacah lewat derajat polinomial (Bab 3); setiap kali sebuah batas tampak ajaib, pasti ada pemilahan atau penjenjangan yang sedang mencacah.

Catatan 1.36 (Jebakan yang sering muncul)

Empat klasik. (i) Pemetaan pada suatu kuosien wajib diperiksa keterdefinisiannya: “ $\overline x \mapsto$ (rumus dalam $x$ )” sah hanya bila rumusnya tetap pada tiap kelas — itulah keselarasan pada Definisi 1.3, bukan sekadar formalitas. (ii) $\operatorname{ord}(ab) = \operatorname{lcm}(\operatorname{ord}a, \operatorname{ord}b)$ salah secara umum, bahkan untuk unsur yang komutatif ( $a$ dan $a^{-1}$ ); Latihan 1.4 memberi pernyataan yang benar dengan syarat saling prima dan komutatif, sedangkan siklus saling lepas memberi versi permutasinya. (iii) Keterbilangan bertahan terhadap gabungan terbilang dan hasil kali hingga, tetapi tidak terhadap hasil kali terbilang: $\{0,1\}^{\N}$ tidak terbilang (Latihan 1.3) walaupun tiap faktornya hanya punya dua unsur. (iv) Cantor–Bernstein hanya menuntut injeksi dua arah, tetapi bijeksi yang dibangunnya lazimnya tidak kontinu dan tidak gamblang — jangan berharap ada rumusnya (Contoh 1.11).

Catatan 1.37 (Di mana bab ini dipakai)

Hampir di mana-mana. Tanda permutasi membangun determinan (Bab 2); morfisma evaluasi $P \mapsto P(u)$ dan ideal utama pada $K[X]$ melahirkan polinomial minimal serta penguraian kernel pada Bab 3; keterbilangan adalah panggung tempat Bab 21 bermain (peluang pada ruang terbilang) sekaligus alasan mengapa topologi terus-menerus menghasilkan himpunan padat yang terbilang (Bab 4). Konstruksi kuosien $A/I$ dipakai kembali pada jilid Tahun ke-3 untuk membangun lapangan $K[X]/(P)$ dan, dari situ, teori Galois: sifat universal yang dibuktikan di sini dipakai di sana kata demi kata.

1.6 Latihan

Latihan 1.1 ★

Manakah di antara himpunan berikut yang terbilang? Himpunan semua himpunan bagian hingga dari $\N$ ; himpunan semua himpunan bagian $\N$ ; $\R \setminus \Q$ ; himpunan polinomial berkoefisien rasional; himpunan barisan atas $0$ dan $1$ yang akhirnya nol.

Solusi

Solusi Latihan 1.1.

Himpunan bagian hingga dari $\N$ : terbilang — himpunan semua himpunan bagian $\intint{0}{n}$ adalah hingga, dan himpunan bagian yang hingga membentuk gabungan terbilang atas $n$ dari himpunan-himpunan itu (Proposisi 1.6 (3)); tak hingga karena ia memuat semua himpunan tunggal.

Semua himpunan bagian $\N$ : tidak terbilang, menurut teorema Cantor (Teorema 1.9 (1) dengan $E = \N$ ).

$\R \setminus \Q$ : tidak terbilang — sebab jika tidak, $\R = \Q \cup (\R\setminus\Q)$ akan menjadi gabungan dua himpunan terbilang, yang bertentangan dengan Teorema 1.9 (2).

Polinomial atas $\Q$ : terbilang — polinomial berderajat $\leq n$ terinjeksi ke $\Q^{n+1}$ (hasil kali hingga atas himpunan terbilang), lalu ambil gabungan atas $n$ .

Barisan biner yang akhirnya nol: terbilang — barisan itu berpadanan bijektif dengan himpunan bagian hingga $\N$ (lewat penyangganya).

Latihan 1.2 ★

Di $\mathfrak{S}_7$ , misalkan $\sigma = (1\,4\,2\,6)(3\,5)$ dan $\tau = (2\,3\,7)$ . Hitung $\sigma\tau$ dan $\tau\sigma$ dalam bentuk siklus saling lepas, orde dan tanda keempat permutasi tadi, serta $\sigma^{2026}$ .

Solusi

Solusi Latihan 1.2.

Hitung unsur demi unsur, dengan faktor kanan dikerjakan lebih dulu. $\sigma\tau$ mengirim $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),

sebuah siklus berpanjang $7$ . Serupa itu $\tau\sigma$ mengirim $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),

juga siklus berpanjang $7$ (sesuai dugaan: $\sigma\tau$ dan $\tau\sigma$ sekonjugasi, jadi tipe siklusnya sama).

Orde dan tanda: $\sigma$ bertipe siklus $(4,2)$ , jadi berorde $\operatorname{lcm}(4,2) = 4$ dan bertanda $(-1)^3(-1)^1 = +1$ ; $\tau$ adalah siklus berpanjang $3$ , jadi berorde $3$ dan bertanda $+1$ ; kedua hasil kali tadi siklus berpanjang $7$ , jadi berorde $7$ dan bertanda $(-1)^6 = +1$ .

$\sigma^{2026}$ : karena $2026 = 4 \times 506 + 2$ , maka $\sigma^{2026} = \sigma^2 = (1\,2)(4\,6)$ (kuadratkan siklus berpanjang $4$ ; transposisinya lenyap ketika dikuadratkan).

Latihan 1.3 ★

Bangun injeksi yang gamblang untuk menunjukkan bahwa $\mathcal{P}(\N)$ , $\intcc{0}{1}$ dan himpunan barisan biner $\{0,1\}^{\N}$ ekuipoten sepasang demi sepasang (uraian biner dua arah; Cantor–Bernstein menyerap kerepotan penyajian ganda).

Solusi

Solusi Latihan 1.3.

$\{0,1\}^{\N} \to \mathcal{P}(\N)$ : sebuah barisan dipetakan ke penyangganya — sebuah bijeksi (fungsi indikator), tanpa perlu teorema.

$\{0,1\}^{\N} \to \intcc{0}{1}$ : pemetaan basis $3$ , yakni $(a_n) \mapsto \sum 2a_n 3^{-n-1}$ , bersifat injektif (dua barisan yang berbeda mulai berselisih pada peringkat $N$ ; ekornya tak sanggup menutup jurang sebesar $2\cdot 3^{-N-1}$ , sebab $\sum_{n > N} 2\cdot 3^{-n-1} = 3^{-N-1} < 2\cdot3^{-N-1}$ ).

$\intcc{0}{1} \to \{0,1\}^{\N}$ : uraian biner, dengan memilih (misalnya) uraian yang tidak berakhir dengan $1$ berulang: injektif.

Menurut Cantor–Bernstein (Teorema 1.10) yang diterapkan pada dua injeksi terakhir, $\intcc{0}{1}$ dan $\{0,1\}^{\N}$ ekuipoten, jadi ketiga himpunan itu ekuipoten.

Latihan 1.4 ★

Misalkan $G$ sebuah grup dan $a, b \in G$ dua unsur komutatif yang ordenya hingga dan saling prima, yakni $m$ dan $n$ . Buktikan bahwa $\operatorname{ord}(ab) = mn$ . Tunjukkan lewat sebuah contoh di $\mathfrak{S}_3$ bahwa kekomutatifan itu penting.

Solusi

Solusi Latihan 1.4.

Misalkan $c = ab = ba$ dan $d = \operatorname{ord}(c)$ . Pertama, $c^{mn} = a^{mn} b^{mn} = e$ (kekomutatifan memungkinkan pemisahan pangkat), jadi $d \mid mn$ . Sebaliknya $c^d = e$ memberi $a^d = b^{-d}$ ; unsur ini berada di $\langle a\rangle \cap \langle b\rangle$ , yaitu subgrup yang ordenya membagi $m$ sekaligus $n$ (Lagrange pada masing-masing grup siklik), sehingga subgrup itu trivial: $a^d = b^d = e$ , jadi $m \mid d$ dan $n \mid d$ , dan karena saling prima $mn \mid d$ . Maka $d = mn$ .

Di $\mathfrak{S}_3$ : ambil $a = (1\,2)$ (berorde $2$ ) dan $b = (1\,2\,3)$ (berorde $3$ ), yang ordenya saling prima tetapi tidak komutatif: $ab = (2\,3)$ berorde $2 \neq 6$ — memang $\mathfrak{S}_3$ tidak punya unsur berorde $6$ . Kekomutatifan memang penting.

Latihan 1.5 ★★

Misalkan $G$ grup hingga berorde genap. Buktikan bahwa $G$ memuat sebuah unsur berorde $2$ . (Pasangkan tiap unsur dengan inversnya; cacah yang berpasangan dengan dirinya sendiri.)

Solusi

Solusi Latihan 1.5.

Pasangkan setiap $x \in G$ dengan $x^{-1}$ . Pasangan $\{x, x^{-1}\}$ dengan $x \neq x^{-1}$ beranggotakan dua unsur dan memilah gabungannya; unsur yang tersisa persis yang memenuhi $x = x^{-1}$ , yakni $x^2 = e$ . Karena $\abs G$ genap dan pasangan berunsur dua itu meliputi sejumlah genap unsur, himpunan $\{x : x^2 = e\}$ berkardinalitas genap; ia memuat $e$ , jadi ia memuat sedikitnya satu unsur lain $x \neq e$ — yakni sebuah unsur berorde $2$ .

Latihan 1.6 ★★

Buktikan bahwa $A_n$ ( $n \geq 3$ ) dibangun oleh siklus berpanjang $3$ . (Hasil kali dua transposisi adalah siklus berpanjang $3$ atau hasil kali dua siklus berpanjang $3$ .)

Solusi

Solusi Latihan 1.6.

Setiap unsur $A_n$ adalah hasil kali sejumlah genap transposisi (Teorema 1.21: uraikan atas transposisi; banyaknya genap karena tandanya $+1$ ). Cukuplah menuliskan setiap hasil kali dua transposisi memakai siklus berpanjang $3$ :

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

(periksa lewat penilaian), dan $(a\,b)(a\,b) = \mathrm{id}$ . Jadi siklus berpanjang $3$ membangun $A_n$ .

Latihan 1.7 ★★

Tentukan semua morfisma grup: dari $(\Q, +)$ ke $(\Z, +)$ ; dari $(\Z/n\Z, +)$ ke $(\Z/m\Z, +)$ (cacah banyaknya: $\gcd(m,n)$ ); dan dari $(\Q, +)$ ke $(\Q_+^*, \times)$ .

Solusi

Solusi Latihan 1.7.

$(\Q,+) \to (\Z,+)$ : hanya morfisma nol. Untuk sembarang $x$ dan setiap $n \geq 1$ , $f(x) = n f\bigl(\frac xn\bigr)$ habis dibagi $n$ di $\Z$ ; satu-satunya bilangan bulat yang habis dibagi setiap $n$ adalah $0$ , jadi $f(x) = 0$ untuk setiap $x$ .

$(\Z/n\Z, +) \to (\Z/m\Z, +)$ : sebuah morfisma ditentukan oleh $c = f(\overline 1)$ , yang wajib memenuhi $n c \equiv 0 \pmod m$ , yakni $c$ merupakan kelipatan $\frac{m}{\gcd(m,n)}$ ; ada $\gcd(m,n)$ kelas semacam itu, dan tiap pilihan memang mendefinisikan morfisma (faktorkan $k \mapsto kc$ lewat $\Z/n\Z$ dengan sifat universal).

$(\Q, +) \to (\Q_+^*, \times)$ : hanya morfisma trivial. Jika $f(x) = y$ , maka untuk setiap $n$ , $y = f(n \cdot \frac xn) = f(\frac xn)^n$ merupakan pangkat ke- $n$ di $\Q_+^*$ . Namun bilangan rasional $y \neq 1$ tak mungkin menjadi pangkat ke- $n$ untuk setiap $n$ : ada bilangan prima yang muncul di $y$ dengan pangkat $v$ tak nol, dan $n \nmid v$ untuk $n > \abs v$ (pangkat pada suatu pangkat ke- $n$ selalu kelipatan $n$ , menurut ketunggalan pemfaktoran). Jadi $f \equiv 1$ .

Latihan 1.8 ★★

Dengan teorema sisa Cina, hitung $\varphi(360)$ , tentukan semua $x$ dengan $x \equiv 3 \pmod 8$ , $x \equiv 5 \pmod 9$ dan $x \equiv 2 \pmod 5$ , lalu hitung dua angka terakhir $3^{2026}$ (Euler modulo $100$ ; awas: kerjakan modulo $4$ dan modulo $25$ ).

Solusi

Solusi Latihan 1.8.

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

Sistemnya: modulus $8, 9, 5$ saling prima sepasang demi sepasang, dengan hasil kali $360$ . Dari $x \equiv 3 \pmod 8$ dan $x \equiv 5 \pmod 9$ : $x = 3 + 8k$ dengan $3 + 8k \equiv 5 \pmod 9$ , yakni $-k \equiv 2$ , $k \equiv -2 \equiv 7 \pmod 9$ , sehingga $x \equiv 3 + 56 = 59 \pmod{72}$ . Lalu $59 + 72\ell \equiv 2 \pmod 5$ : $4 + 2\ell \equiv 2$ , $2\ell \equiv 3 \equiv 8$ , $\ell \equiv 4 \pmod 5$ , jadi $x \equiv 59 + 288 = 347 \pmod{360}$ .

Dua angka terakhir $3^{2026}$ : modulo $4$ , $3^{2026} = 9^{1013} \equiv 1$ . Modulo $25$ : $\varphi(25) = 20$ dan $2026 = 20\cdot101 + 6$ , jadi $3^{2026} \equiv 3^6 = 729 \equiv 4 \pmod{25}$ . Selesaikan $x \equiv 1 \pmod 4$ , $x \equiv 4 \pmod{25}$ : dari $x = 4 + 25k \equiv 1 \pmod 4$ diperoleh $k \equiv 1 \pmod 4$ , jadi $x \equiv 29 \pmod{100}$ . Dua angka terakhirnya adalah $29$ .

Latihan 1.9 ★★★

Buktikan bahwa daerah integral yang hingga adalah lapangan. Turunkan bahwa $\Z/n\Z$ adalah lapangan bila dan hanya bila $n$ prima (sekali lagi).

Solusi

Solusi Latihan 1.9.

Misalkan $A$ daerah integral yang hingga dan $a \in A$ , $a \neq 0$ . Pemetaan $x \mapsto ax$ bersifat injektif ( $ax = ay \implies a(x - y) = 0 \implies x = y$ , sebab tidak ada pembagi nol); pemetaan injektif dari himpunan hingga ke dirinya sendiri pastilah surjektif (jilid Tahun ke-1, kesetaraan sarang merpati). Jadi $1 = ab$ untuk suatu $b$ : setiap unsur tak nol punya invers, sehingga $A$ adalah lapangan.

$\Z/n\Z$ : jika $n$ prima, ia daerah integral ( $n \mid ab \implies n \mid a$ atau $n \mid b$ , lewat lema Euklides), hingga, jadi lapangan; jika $n = rs$ komposit, maka $\overline r\,\overline s = \overline 0$ memperlihatkan adanya pembagi nol.

Latihan 1.10 ★★★

(Sebuah klasik) Misalkan $K$ sebuah lapangan dan $G$ subgrup hingga dari $(K^*, \times)$ . Buktikan bahwa $G$ siklik. Petunjuk: ambil $m$ orde terbesar di antara unsur $G$ ; tunjukkan orde setiap unsur membagi $m$ (dengan Latihan 1.4 pada bagian saling prima yang sesuai), sehingga seluruh $G$ memenuhi $x^m = 1$ ; lalu cacah akar $X^m - 1$ . Khususnya $(\Z/p\Z)^*$ adalah siklik.

Solusi

Solusi Latihan 1.10.

Misalkan $m = \max\{\operatorname{ord}(x) : x \in G\}$ , yang dicapai di $a$ .

Klaim: orde setiap $x \in G$ membagi $m$ . Andaikan ada $x$ berorde $q$ dengan $q \nmid m$ : maka ada pangkat prima $p^k$ yang membagi $q$ tetapi tidak membagi $m$ . Tulis $m = p^j m'$ dengan $p \nmid m'$ dan $j < k$ . Unsur $a^{p^j}$ berorde $m'$ ; unsur $x^{q/p^k}$ berorde $p^k$ ; kedua orde itu saling prima dan kedua unsurnya komutatif ( $G \subseteq K^*$ abelian), jadi menurut Latihan 1.4 hasil kalinya berorde $p^k m' > p^j m' = m$ : bertentangan dengan kemaksimalan.

Jadi setiap $x \in G$ memenuhi $x^m = 1$ : polinomial $X^m - 1$ punya sedikitnya $\abs G$ akar di lapangan $K$ , sehingga $\abs G \leq m$ (polinomial tak nol berderajat $m$ punya paling banyak $m$ akar, jilid Tahun ke-1). Namun $m = \operatorname{ord}(a) \leq \abs G$ menurut Lagrange. Maka $m = \abs G$ dan $\langle a \rangle$ , yang berkardinalitas $m = \abs G$ , adalah seluruh $G$ : siklik.

Untuk $K = \Z/p\Z$ : $(\Z/p\Z)^*$ adalah subgrup hingga dari $K^*$ , jadi siklik (berorde $p - 1$ ).

Latihan 1.11 ★★★

Buktikan bahwa grup $(\Q, +)$ tidak siklik, dan yang lebih buruk lagi: ia bahkan tidak dibangun oleh berhingga unsur. Buktikan sebaliknya bahwa setiap subgrup $(\Q, +)$ yang dibangun oleh berhingga unsur adalah siklik.

Solusi

Solusi Latihan 1.11.

Tidak siklik: subgrup $\langle \frac pq\rangle$ terdiri atas kelipatan bulat $\frac pq$ , yang semuanya berpenyebut pembagi $q$ (dalam bentuk paling sederhana); karena itu subgrup itu melewatkan $\frac{1}{2q}$ . Tidak ada pembangun tunggal yang mampu menjangkau penyebut $\Q$ yang tak terbatas.

Tidak dibangun oleh berhingga unsur: subgrup yang dibangun oleh $\frac{p_1}{q_1}, \dots, \frac{p_k}{q_k}$ terdiri atas bilangan rasional yang penyebutnya membagi $Q = q_1 \cdots q_k$ (kombinasi bulat berpenyebut pembagi $Q$ ): subgrup itu melewatkan $\frac{1}{2Q}$ .

Subgrup yang dibangun oleh berhingga unsur adalah siklik: dengan $Q$ seperti di atas, subgrup $H = \langle \frac{p_1}{q_1}, \dots, \frac{p_k}{q_k}\rangle$ termuat di $\frac{1}{Q}\Z$ . Pemetaan $x \mapsto Qx$ adalah isomorfisma dari $\frac1Q\Z$ pada $\Z$ yang membawa $H$ ke suatu subgrup $\Z$ , yaitu $n\Z$ untuk suatu $n$ (jilid Tahun ke-1): jadi $H = \frac{n}{Q}\Z$ siklik, dibangun oleh $\frac nQ$ .

Latihan 1.12 ★★

(Kriteria Dedekind) Buktikan bahwa setiap himpunan tak hingga memuat himpunan bagian yang terbilang, lalu turunkan bahwa suatu himpunan $E$ tak hingga bila dan hanya bila ia ekuipoten dengan salah satu himpunan bagian sejatinya. (Untuk arah langsungnya, geser sebuah himpunan bagian terbilang sejauh satu langkah; untuk arah sebaliknya, ingat kembali asas sarang merpati.)

Solusi

Solusi Latihan 1.12.

Sebuah himpunan bagian terbilang. Misalkan $E$ tak hingga. Bangun $a_0, a_1, a_2, \dots$ secara induktif: $E$ tak kosong, jadi pilih $a_0 \in E$ ; jika $a_0, \dots, a_n$ sudah terpilih, maka $E \setminus \{a_0, \dots, a_n\}$ tak kosong ( $E$ tidak hingga), jadi pilih $a_{n+1}$ di sana. Semua $a_n$ berbeda sepasang demi sepasang menurut konstruksinya, jadi $A = \{a_n : n \in \N\}$ himpunan bagian $E$ yang terbilang.

Tak hingga $\implies$ ekuipoten dengan himpunan bagian sejati. Tetapkan $f \colon E \to E \setminus \{a_0\}$ oleh $f(a_n) = a_{n+1}$ dan $f(x) = x$ untuk $x \notin A$ . Pemetaan itu injektif (kedua potongannya injektif dengan peta yang saling lepas) dan surjektif pada $E \setminus \{a_0\}$ : setiap $a_{n+1}$ tercapai, setiap $x \notin A$ tercapai. Jadi $E$ ekuipoten dengan himpunan bagian sejati $E \setminus \{a_0\}$ .

Sebaliknya. Jika $E$ hingga dan $g \colon E \to F$ adalah bijeksi pada $F \subseteq E$ dengan $F \neq E$ , maka $g$ merupakan injeksi $E$ ke dirinya sendiri yang tidak surjektif, dan itu bertentangan dengan asas sarang merpati (jilid Tahun ke-1: pemetaan injektif dari himpunan hingga ke dirinya sendiri pasti bijektif). Jadi himpunan yang ekuipoten dengan himpunan bagian sejatinya pastilah tak hingga.

1.7 Soal: Teka-Teki Lima Belas

Teka-teki lima belas adalah papan $4 \times 4$ yang memuat lima belas ubin geser bernomor $1$ sampai $15$ dan satu sel kosong; satu langkah menggeser salah satu ubin yang bertetangga dengan sel kosong ke sel itu. Sekitar tahun 1890 Sam Loyd memasyhurkan teka-teki ini dengan menawarkan $1000 kepada siapa pun yang sanggup menukar ubin $14$ dan $15$ sambil mengembalikan setiap ubin lain ke tempatnya. Tak seorang pun pernah menagihnya, dan soal akhir pekan ini membuktikan kedua paruh sebabnya: tanda permutasi pada Teorema 1.21 melarang penukaran Loyd, dan — ini paruh yang lebih sulit sekaligus konstruktif — segala hal yang diizinkan tanda permutasi memang benar-benar terselesaikan. Pernyataan lengkapnya adalah teorema Johnson–Story (1879).

Konfigurasi yang tersusun dan konfigurasi 14–15 milik Sam Loyd. Pertanyaan senilai $1000: dapatkah geseran yang sah mengubah papan kanan menjadi papan kiri? — Konfigurasi yang tersusun dan konfigurasi $14$ – $15$ milik Sam Loyd. Pertanyaan senilai $1000: dapatkah geseran yang sah mengubah papan kanan menjadi papan kiri?

Soal 1.1

Soal akhir pekan — teorema keterselesaian Johnson–Story

Nomori selnya $1$ sampai $16$ menurut urutan baca (kiri ke kanan, atas ke bawah), sehingga sel $k$ terletak pada baris $i$ dan kolom $j$ dengan $k = 4(i - 1) + j$ . Sel $16$ (kanan bawah) adalah rumah sel kosong; sel kosong kita perlakukan sebagai ubin keenam belas, ditulis $b$ dan disamakan dengan bilangan $16$ . Sebuah konfigurasi adalah bijeksi $\sigma \colon \intint1{16} \to \intint1{16}$ , sel $\mapsto$ isinya; konfigurasi yang tersusun adalah $\sigma = \mathrm{id}$ . Di sepanjang soal ini, $\varepsilon$ menyatakan tanda permutasi pada Teorema 1.21, dan dua sel disebut bertetangga apabila keduanya berbagi satu rusuk papan.

Bagian I — Konfigurasi, langkah, tanda.

Berilah alasan bahwa konfigurasi persis sama dengan unsur $\mathfrak{S}_{16}$ , sehingga banyaknya $16! = 20\,922\,789\,888\,000$ , dan bahwa banyaknya langkah sah dari sebuah konfigurasi adalah $2$ , $3$ atau $4$ , bergantung pada apakah sel kosong berada di pojok, di tepi, atau di bagian dalam.
Misalkan $\sigma$ sebuah konfigurasi, $p = \sigma^{-1}(16)$ sel tempat kekosongan berada, dan $c$ sel yang bertetangga dengan $p$ . Tunjukkan bahwa menggeser ubin di $c$ ke $p$ menghasilkan konfigurasi $\sigma' = \sigma \circ \tau$ dengan $\tau = (p\ c)$ , lalu turunkan bahwa setiap langkah membalik tandanya: $\varepsilon(\sigma') = -\varepsilon(\sigma)$ .
Warnai papan bak papan catur: $\chi(k) = (-1)^{i+j}$ untuk sel $k$ pada baris $i$ , kolom $j$ . Tunjukkan bahwa setiap langkah membalik $\chi(\text{sel tempat kekosongan})$ , lalu turunkan bahwa rangkaian langkah yang mengembalikan kekosongan ke sel awalnya pasti berpanjang genap.
Tunjukkan bahwa

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

tidak berubah oleh langkah sah mana pun, lalu hitung $I(\mathrm{id})$ .

Bagian II — Hadiah Loyd: invarian sedang bekerja.

Konfigurasi Loyd $\sigma_L$ sama dengan konfigurasi tersusun kecuali bahwa sel $14$ dan $15$ memuat ubin $15$ dan $14$ . Hitung $I(\sigma_L)$ lalu simpulkan bahwa tidak ada rangkaian langkah yang menghubungkan $\sigma_L$ dengan konfigurasi tersusun: $1000 milik Loyd tidak pernah terancam.
Tunjukkan bahwa tepat separuh dari semua konfigurasi memenuhi $I = +1$ : $\abs{\{\sigma : I(\sigma) = +1\}} = 16!/2$ . (Untuk sel kosong yang tetap, pasangkan konfigurasi dengan menyusunnya bersama satu transposisi tetap atas dua sel yang lain.)
Tunjukkan bahwa setiap langkah dapat dibatalkan oleh sebuah langkah sah, bahwa “ $\sigma'$ terjangkau dari $\sigma$ lewat langkah sah” merupakan relasi ekuivalensi, dan bahwa kelas $R$ milik konfigurasi tersusun memenuhi $R \subseteq \{I = +1\}$ . Simpulkan bahwa kelasnya sedikitnya ada dua.
Andaikan kekosongan berada di rumahnya: $\sigma(16) = 16$ . Tunjukkan bahwa $I(\sigma) = \varepsilon(\rho)$ dengan $\rho \in \mathfrak{S}_{15}$ adalah pembatasan $\sigma$ pada sel $1, \dots, 15$ , dan bahwa sembarang konfigurasi dapat dibawa oleh langkah sah ke konfigurasi yang kekosongannya di rumah. Simpulkan: untuk membuktikan $R = \{I = +1\}$ cukuplah mewujudkan setiap permutasi genap atas kelima belas sel bukan-rumah lewat rangkaian langkah yang berawal dan berakhir dengan kekosongan di rumah.

Bagian III — Perjalanan kekosongan dan grup program. Sebuah program adalah rangkaian langkah sah yang hingga, dimulai dari konfigurasi yang kekosongannya di rumah, dan konfigurasi akhirnya pun berkekosongan di rumah. Efeknya adalah permutasi $\pi$ atas sel yang ditetapkan oleh: isi sel $x$ berakhir di sel $\pi(x)$ .

Tunjukkan bahwa program yang dijalankan dari $\sigma$ berakhir di $\sigma \circ \pi^{-1}$ ; bahwa menjalankan dua program berturut-turut menyusun efek keduanya; dan bahwa himpunan $H$ semua efek adalah subgrup $\mathfrak{S}_{15}$ (permutasi atas sel $1, \dots, 15$ ) yang termuat di grup alternating $A_{15}$ .
(Perjalanan dasar) Dari kekosongan di rumah, geserlah kekosongan mengelilingi blok $2 \times 2$ di kanan bawah: sel $16 \to 12 \to 11 \to 15 \to 16$ . Tunjukkan efeknya adalah siklus berpanjang $3$ , yakni $(11\ 12\ 15)$ , dan bahwa perjalanan sebaliknya memberi $(11\ 15\ 12)$ . Keduanya berada di $H$ .
(Perjalanan agung) Periksalah bahwa

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

adalah jalan tertutup yang melewati keenam belas sel (hanya lewat langkah bertetangga), dan bahwa efeknya adalah siklus berpanjang $15$

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

Dengan menulis $x_0 = 15$ , $x_1 = 12$ , $x_2 = 11$ , …, $x_{14} = 14$ menurut urutan siklusnya, periksalah bahwa perjalanan dasar yang dibalik pada pertanyaan 10 persis sama dengan $(x_0\ x_1\ x_2)$ .
Buktikan rumus konjugasi pada sembarang $\mathfrak{S}_n$ : untuk sebuah permutasi $g$ dan sebuah siklus berpanjang $3$ ,

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

lalu perhatikan bahwa $H$ , karena ia grup, tertutup terhadap konjugasi oleh unsurnya sendiri.
Turunkan bahwa $H$ memuat kelima belas siklus berurutan berpanjang $3$ dari perjalanan agung:

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

Bagian IV — Membangun grup alternating.

(Lema A) Misalkan $s$ dan $t$ dua siklus berpanjang $3$ yang penyangganya berbagi tepat dua titik, katakanlah penyangga $\{a, b, c\}$ dan $\{b, c, d\}$ . Tunjukkan bahwa, setelah $s$ atau $t$ diganti dengan inversnya bila perlu (yang tidak mengubah subgrup yang dibangun), hasil kali $st$ adalah transposisi ganda; tunjukkan bahwa $A_4$ tidak punya subgrup berorde $6$ (subgrup berindeks $2$ memuat setiap kuadrat; cacah siklus berpanjang $3$ di antara kuadrat itu); lalu simpulkan bahwa $\langle s, t\rangle$ adalah seluruh grup alternating atas keempat huruf $\{a, b, c, d\}$ .
(Lema B) Misalkan $X$ himpunan berisi $k \geq 4$ huruf, $w \notin X$ , dan misalkan $G$ subgrup suatu $\mathfrak{S}_n$ yang memuat setiap permutasi genap atas $X$ dan satu siklus berpanjang $3$ , yaitu $(u\ v\ w)$ , dengan $u, v \in X$ . Tunjukkan bahwa untuk setiap $a, b \in X$ yang berbeda ada permutasi genap $g$ atas $X$ dengan $g(u) = a$ , $g(v) = b$ , lalu turunkan $(a\ b\ w) \in G$ .
Turunkan bahwa grup $G$ pada Lema B memuat setiap permutasi genap atas $X \cup \{w\}$ (pakai Latihan 1.6: siklus berpanjang $3$ membangunnya). Lalu, dengan merangkai Lema A dan Lema B sepanjang siklus berpanjang $3$ yang berurutan, yaitu $s_0, s_1, \dots, s_{12}$ pada pertanyaan 13, buktikan bahwa $\langle s_0, \dots, s_{12}\rangle = A_{15}$ .
Simpulkan bahwa $H = A_{15}$ : setiap penataan ulang yang genap atas kelima belas ubin dapat dicapai oleh sebuah program, dan $H$ punya $15!/2 = 653\,837\,184\,000$ unsur.
(Teorema Johnson–Story, 1879) Rakitlah pertanyaan 6, 7, 8 dan 17: konfigurasi yang terjangkau dari konfigurasi tersusun persis sebanyak $16!/2 = 10\,461\,394\,944\,000$ konfigurasi dengan $I = +1$ ; dan keterjangkauan hanya punya dua kelas, yakni kelas konfigurasi tersusun dan kelas $\sigma_L$ milik Loyd. (Untuk butir kedua, tukarlah nama ubin $14$ dan $15$ : tunjukkan $\sigma \mapsto (14\ 15) \circ \sigma$ memetakan rangkaian langkah ke rangkaian langkah dan menukar $\{I = +1\}$ dengan $\{I = -1\}$ .)

Bagian V — Kriteria, ragam, dan pandangan dari atas.

(Kriteria praktis) Bacalah kelima belas ubin itu menurut urutan baca selnya, lewati kekosongannya, dan misalkan $N$ banyaknya inversi pada deretan itu; misalkan $r$ nomor baris kekosongan dihitung dari bawah. Tunjukkan bahwa $I(\sigma) = (-1)^{N + r + 1}$ , sehingga $\sigma$ terselesaikan bila dan hanya bila $N + r$ ganjil.
(Aksi grup) Sebuah aksi grup $G$ pada himpunan $X$ adalah pemetaan $G \times X \to X$ , $(g, x) \mapsto g \cdot x$ , dengan $e \cdot x = x$ dan $g \cdot (h \cdot x) = (gh) \cdot x$ ; orbit $x$ adalah $G \cdot x$ , dan aksinya disebut bebas apabila $g \cdot x = x$ memaksa $g = e$ . Tunjukkan bahwa $h \cdot \sigma = \sigma \circ h^{-1}$ mendefinisikan aksi bebas $H$ pada himpunan konfigurasi yang kekosongannya di rumah, bahwa orbitnya persis kelas keterjangkauan bersama lewat program, lalu peroleh kembali dari pencacahan orbit bahwa konfigurasi itu terbelah menjadi tepat $15!\,/\,\abs H = 2$ kelas.
(Halangan pada papan $3 \times 3$ ) Tunjukkan bahwa papan $3 \times 3$ tidak punya jalan tertutup yang menyinggahi setiap sel tepat sekali: siasat perjalanan agung pada Bagian III gagal untuk teka-teki delapan. (Warnai kesembilan selnya bak papan catur.)
(Perbaikannya) Pada papan $3 \times 3$ dengan sel $1$ sampai $9$ menurut urutan baca dan rumah di $9$ : hitunglah efek perjalanan keliling $9 \to 8 \to 7 \to 4 \to 1 \to 2 \to 3 \to 6 \to 9$ (sebuah siklus berpanjang $7$ , yaitu $\zeta'$ , yang membiarkan pusat $5$ tetap) dan efek perjalanan pojok $9 \to 6 \to 5 \to 8 \to 9$ (siklus berpanjang $3$ yang melewati pusat). Dengan mengonjugasikan yang terakhir oleh pangkat-pangkat $\zeta'$ lalu merangkai Lema A dan Lema B, buktikan bahwa grup program teka-teki delapan adalah seluruh $A_8$ , sehingga tepat $9!/2 = 181\,440$ dari $9! = 362\,880$ konfigurasinya terselesaikan.
(Papan yang miskin) Kini ambil papan berupa satu siklus beranggotakan $n \geq 4$ sel yang mengusung $n - 1$ ubin. Tunjukkan bahwa urutan siklis ubinnya tidak berubah, bahwa tiap kelas keterjangkauan punya tepat $n(n - 1)$ konfigurasi (kelasnya adalah orbit grup siklik berorde $\operatorname{lcm}(n, n-1) = n(n-1)$ ), dan bahwa kelasnya ada $(n - 2)!$ — untuk $n \geq 5$ jauh lebih banyak daripada $2$ : pada papan yang tipis invarian paritas nyaris tak menangkap apa pun, dan geometrilah yang berkuasa.
Dua vonis menurut kriteria pertanyaan 19: papan yang seluruhnya terbalik (ubin $15, 14, \dots, 1$ pada sel $1$ sampai $15$ , kekosongan di rumah) dan papan yang kekosongannya di sel $1$ lalu disusul ubin $15, 14, \dots, 1$ pada sel $2$ sampai $16$ . Manakah yang terselesaikan?
(Rangkuman) Buktinya bertumpu pada dua pilar yang saling bebas: sebuah invarian ( $I$ , yang dibangun dari morfisma tanda permutasi) yang menunjukkan paling banyak separuh konfigurasi terjangkau, dan sebuah teorema pembangunan gamblang ( $H = A_{15}$ ) yang menunjukkan sedikitnya separuh terjangkau. Dengan satu kalimat untuk masing-masing, sebutkan di mana berikut ini masuk: sifat morfisma $\varepsilon$ ; teorema Lagrange; pembangunan $A_n$ oleh siklus berpanjang $3$ ; dan konjugasi. Nyatakan asas umumnya dalam satu baris.

Solusi

Solusi Soal 1.1.

1. Sebuah konfigurasi memberikan kepada masing-masing dari $16$ sel satu dari $16$ isi (ubin $1$ – $15$ atau kekosongan $b = 16$ ), masing-masing tepat sekali: itu persis sebuah bijeksi $\intint1{16} \to \intint1{16}$ , yakni unsur $\mathfrak{S}_{16}$ ; banyaknya $16! = 20\,922\,789\,888\,000$ . Satu langkah sah menggeser satu ubin yang bertetangga dengan kekosongan, jadi banyaknya langkah sama dengan banyaknya tetangga sel kekosongan: $2$ untuk keempat sel pojok, $3$ untuk kedelapan sel tepi, dan $4$ untuk keempat sel dalam.

2. Setelah geseran, sel $p$ memuat isi lama $c$ dan sel $c$ memuat kekosongan; semua sel lain tak tersentuh: $\sigma'(p) = \sigma(c)$ , $\sigma'(c) = \sigma(p) = 16$ , dan $\sigma' = \sigma$ pada sel lainnya. Itu persis $\sigma' = \sigma \circ (p\ c)$ . Karena $\varepsilon$ adalah morfisma dan $\varepsilon\bigl((p\ c)\bigr) = -1$ , kita peroleh $\varepsilon(\sigma') = -\varepsilon(\sigma)$ .

3. Sel bertetangga berselisih satu langkah tepat pada salah satu dari kedua koordinatnya, jadi paritas $i + j$ berubah: $\chi$ bernilai berlawanan pada sel yang bertetangga. Satu langkah memindahkan kekosongan dari $p$ ke $c$ yang bertetangga, sehingga membalik $\chi(\text{sel kekosongan})$ . Sepanjang jalan tertutup yang ditempuh kekosongan, $\chi$ terbalik sekali tiap langkah lalu kembali ke nilai awalnya: jadi banyaknya langkah genap.

4. Menurut pertanyaan 2 dan 3, satu langkah membalik kedua faktor $I(\sigma) = \varepsilon(\sigma)\chi(\sigma^{-1}(16))$ , sehingga hasil kalinya tak berubah. Untuk konfigurasi tersusun: $\varepsilon(\mathrm{id}) = +1$ dan kekosongan berada di sel $16$ , baris $4$ , kolom $4$ , jadi $\chi(16) = (-1)^{8} = +1$ , sehingga $I(\mathrm{id}) = +1$ .

5. $\sigma_L$ adalah transposisi $(14\ 15)$ atas sel: $\varepsilon(\sigma_L) = -1$ ; kekosongannya di rumah, jadi $\chi(16) = +1$ dan $I(\sigma_L) = -1 \neq +1 = I(\mathrm{id})$ . Karena $I$ terpelihara oleh setiap langkah, tidak ada rangkaian langkah yang menghubungkan $\sigma_L$ dengan $\mathrm{id}$ . Hadiahnya aman secara struktural.

6. Tetapkan sebuah sel $p$ dan dua sel lain $c \neq d$ yang berbeda dari $p$ , lalu ambil $\tau_0 = (c\ d)$ . Pada himpunan konfigurasi yang kekosongannya di $p$ , pemetaan $\sigma \mapsto \sigma \circ \tau_0$ adalah involusi (ia memelihara $\sigma(p) = 16$ karena $\tau_0$ membiarkan $p$ tetap) dan membalik $\varepsilon$ , sehingga membalik $I$ : pemetaan itu memasangkan konfigurasi ber- $I = +1$ secara bijektif dengan konfigurasi ber- $I = -1$ . Jadi tiap satu dari $16$ kedudukan kekosongan menyumbang $15!/2$ konfigurasi ber- $I = +1$ , dan

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

7. Langkah yang menggeser ubin di $c$ ke $p$ dibatalkan dengan menggeser ubin yang sama (kini di $p$ ) kembali ke $c$ : menyusun $(p\ c)$ dua kali menghasilkan identitas. Karena itu: refleksif (dengan rangkaian kosong), simetris (balik rangkaiannya, batalkan tiap langkah), transitif (sambung rangkaiannya) — sebuah relasi ekuivalensi. Setiap $\sigma \in R$ memenuhi $I(\sigma) = I(\mathrm{id}) = +1$ menurut pertanyaan 4, jadi $R \subseteq \{I = +1\}$ ; dan $\sigma_L \notin R$ memberi kelas kedua.

8. Jika $\sigma(16) = 16$ , maka $\sigma$ mempermutasikan sel $1, \dots, 15$ ; sebut $\rho$ pembatasan itu. Menambahkan satu titik tetap tidak mengubah tipe siklus maupun tandanya (uraikan $\rho$ atas transposisi; hasil kali yang sama berlaku di $\mathfrak{S}_{16}$ ), jadi $\varepsilon(\sigma) = \varepsilon(\rho)$ , dan $\chi(16) = +1$ memberi $I(\sigma) = \varepsilon(\rho)$ . Sembarang konfigurasi dapat dibawa ke konfigurasi yang kekosongannya di rumah: papannya terhubung, jadi jalankan kekosongan menyusuri lintasan sel bertetangga sampai sel $16$ (tiap langkahnya sah). Kini andaikan setiap $\rho \in \mathfrak{S}_{15}$ yang genap terwujud oleh sebuah program. Diberikan $\sigma$ dengan $I(\sigma) = +1$ : jalankan kekosongan pulang ke rumah sehingga tercapai $\widetilde\sigma$ (yang setara dengan $\sigma$ ), dengan $I(\widetilde\sigma) = +1$ , yakni pembatasannya $\rho$ genap; program yang mewujudkan $\rho$ membawa $\widetilde\sigma$ ke $\widetilde\sigma \circ \rho^{-1} = \mathrm{id}$ (lihat pertanyaan 9). Menurut ketransitifan $\sigma \in R$ , sehingga $\{I = +1\} \subseteq R$ dan keduanya sama.

9. Satu langkah: isi $c$ berakhir di $p$ dan kekosongan di $c$ , jadi efeknya $\pi = (p\ c)$ , dan memang $\sigma' = \sigma \circ (p\ c) = \sigma \circ \pi^{-1}$ . Induksi: jika sebuah rangkaian berefek $\pi_1$ dan membawa $\sigma$ ke $\sigma \circ \pi_1^{-1}$ , maka menyusulinya dengan langkah berefek $\pi_2 = (p'\ c')$ menghasilkan $(\sigma \circ \pi_1^{-1}) \circ \pi_2^{-1} = \sigma \circ (\pi_2\pi_1)^{-1}$ , dan isinya berpindah menurut $\pi_2 \circ \pi_1$ (mula-mula $\pi_1$ , lalu $\pi_2$ ). Jadi efeknya tersusun, dan program yang dijalankan dari $\sigma$ berakhir di $\sigma \circ \pi^{-1}$ . Subgrup: program kosong berefek $\mathrm{id}$ ; penyambungan memberi hasil kali; pembalikan program (pertanyaan 7) memberi invers. Efek sebuah program membiarkan sel $16$ tetap (kekosongan berawal dan berakhir di rumah), jadi $H \leq \mathfrak{S}_{15}$ . Kegenapan: program dengan $k$ langkah punya $k$ genap (pertanyaan 3), dan $\varepsilon(\sigma \circ \pi^{-1}) = (-1)^k\varepsilon(\sigma)$ memaksa $\varepsilon(\pi) = +1$ : jadi $H \subseteq A_{15}$ .

10. Runut keempat geseran dari kekosongan di $16$ : langkah $16 \to 12$ mengirim isi $12$ ke $16$ ; langkah $12 \to 11$ mengirim isi $11$ ke $12$ ; langkah $11 \to 15$ mengirim isi $15$ ke $11$ ; langkah $15 \to 16$ mengirim isi yang terparkir di $16$ (semula di $12$ ) ke $15$ . Hasil bersihnya: $11 \mapsto 12$ , $12 \mapsto 15$ , $15 \mapsto 11$ , kekosongan di rumah, jadi efeknya $(11\ 12\ 15)$ . Perjalanan sebaliknya membatalkannya, dengan efek $(11\ 12\ 15)^{-1} = (11\ 15\ 12)$ . Keduanya efek sebuah program, jadi keduanya di $H$ .

11. Ketetanggaan sel berurutan: di dalam tiap pasangan yang didaftar, selnya berselisih $1$ pada baris yang sama ( $16{-}15$ , $15{-}14$ , $14{-}13$ ; $1{-}2$ , $2{-}3$ , $3{-}4$ ; $8{-}7$ , $7{-}6$ ; $10{-}11$ , $11{-}12$ ) atau berselisih $4$ di dalam satu kolom ( $13{-}9$ , $9{-}5$ , $5{-}1$ ; $4{-}8$ ; $6{-}10$ ; $12{-}16$ ): jadi ia jalan tertutup lewat seluruh $16$ sel, sepanjang $16$ . Efeknya: seperti pada pertanyaan 10, dengan menulis sel yang disinggahi $c_0 = 16, c_1 = 15, \dots, c_{15} = 12$ , isi $c_i$ berpindah ke $c_{i-1}$ untuk $i = 2, \dots, 15$ , dan isi $c_1$ , yang terparkir di $16$ setelah langkah pertama, terbawa ke $c_{15}$ oleh langkah terakhir. Jadi efeknya memetakan $15 \mapsto 12$ , lalu $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$ : persis siklus berpanjang $15$ bernama $\zeta$ . Urutan siklusnya berawal $x_0 = 15$ , $x_1 = 12$ , $x_2 = 11$ , dan $(x_0\ x_1\ x_2) = (15\ 12\ 11)$ memetakan $15 \mapsto 12 \mapsto 11 \mapsto 15$ — dan itu persis $(11\ 15\ 12)$ , yakni perjalanan dasar yang dibalik.

12. Misalkan $\gamma = (a\ b\ c)$ dan $x \in \intint1n$ . Jika $x = g(a)$ : $g\gamma g^{-1}(x) = g(\gamma(a)) = g(b)$ ; serupa itu $g(b) \mapsto g(c)$ dan $g(c) \mapsto g(a)$ . Jika $x \notin \{g(a), g(b), g(c)\}$ , maka $g^{-1}(x) \notin \{a,b,c\}$ dibiarkan tetap oleh $\gamma$ , sehingga $x$ pun tetap. Jadi $g\gamma g^{-1} = (g(a)\ g(b)\ g(c))$ . Dan untuk $g, h \in H$ , berlaku $ghg^{-1} \in H$ menurut aksioma subgrup.

13. Kita punya $\zeta \in H$ (pertanyaan 11) dan $s_0 = (x_0\ x_1\ x_2) \in H$ (pertanyaan 10–11). Karena $\zeta(x_i) = x_{i+1}$ (indeks modulo $15$ ), pertanyaan 12 memberi

\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. Kecuali pembalikan, andaikan $s = (a\ b\ c)$ dan $t = (b\ c\ d)$ (siklus berpanjang $3$ pada $\{a,b,c\}$ adalah $(a\ b\ c)$ atau inversnya; demikian pula pada $\{b,c,d\}$ ; mengganti sebuah pembangun dengan inversnya tidak mengubah $\langle s, t\rangle$ ). Maka, dengan $t$ dikerjakan lebih dulu,

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

yakni sebuah transposisi ganda. Subgrup $G = \langle s, t\rangle$ terdiri atas permutasi genap atas keempat huruf, jadi $G \leq A_4$ dan $\abs G \mid 12$ ; ia memuat unsur berorde $3$ dan unsur berorde $2$ , jadi $6 \mid \abs G$ (Lagrange, Teorema 1.14, diterapkan pada kedua subgrup siklik itu). Seandainya $A_4$ punya subgrup $K$ berorde $6$ , subgrup itu berindeks $2$ , dan akibatnya $g^2 \in K$ untuk setiap $g \in A_4$ : untuk $g \in K$ hal ini jelas; untuk $g \notin K$ satu-satunya koset adalah $K$ dan $gK$ , jadi koset $g^2K$ sama dengan $K$ atau $gK$ , sedangkan $g^2K = gK$ akan memaksa $g \in K$ . Jadi setiap kuadrat terletak di $K$ . Namun setiap siklus berpanjang $3$ , sebut saja $\gamma$ , adalah kuadrat, sebab $\gamma = (\gamma^2)^2$ , dan $A_4$ memuat delapan siklus berpanjang $3$ : $8 > 6$ , kontradiksi. Maka $\abs G = 12$ , yakni $G = A_4$ .

15. Perpanjang $u \mapsto a$ , $v \mapsto b$ menjadi bijeksi $g_0$ atas $X$ (kirim $k - 2$ huruf sisanya secara bijektif ke mana pun pada komplemen $\{a, b\}$ ). Jika $g_0$ ganjil, pilihlah dua huruf yang berbeda $s_1, t_1 \in X \setminus \{u, v\}$ (mungkin sebab $k \geq 4$ ) lalu ganti $g_0$ dengan $g_0 \circ (s_1\ t_1)$ , yang genap dan tetap memetakan $u \mapsto a$ , $v \mapsto b$ . Perpanjang dengan identitas di luar $X$ : diperoleh permutasi genap $g \in G$ (ia permutasi genap atas $X$ ). Lalu menurut pertanyaan 12:

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

dengan memakai $g(w) = w$ .

16. Setiap siklus berpanjang $3$ atas $X \cup \{w\}$ terletak di $G$ : yang tertumpu di $X$ adalah permutasi genap atas $X$ ; yang berpenyangga $\{a, b, w\}$ adalah $(a\ b\ w)$ atau $(b\ a\ w)$ , dan keduanya diberikan pertanyaan 15. Menurut Latihan 1.6, siklus berpanjang $3$ atas himpunan berhuruf $(k+1)$ , yaitu $X \cup \{w\}$ , membangun grup alternatingnya, jadi $G$ memuat setiap permutasi genap atas $X \cup \{w\}$ . Perangkaian: misalkan $G = \langle s_0, \dots, s_{12}\rangle$ . Lema A yang diterapkan pada $s_0 = (x_0\ x_1\ x_2)$ dan $s_1 = (x_1\ x_2\ x_3)$ (penyangganya berbagi $\{x_1, x_2\}$ ) memberi seluruh permutasi genap atas $X_4 = \{x_0, x_1, x_2, x_3\}$ . Jika $G$ memuat setiap permutasi genap atas $X_m = \{x_0, \dots, x_{m-1}\}$ ( $4 \leq m \leq 14$ ), maka $s_{m-2} = (x_{m-2}\ x_{m-1}\ x_m)$ punya $u = x_{m-2}, v = x_{m-1} \in X_m$ serta huruf baru $w = x_m$ : Lema B dan bagian pertama tadi memberi seluruh permutasi genap atas $X_{m+1}$ . Induksi sampai $m = 14$ memberi $G \supseteq A_{15}$ (permutasi genap atas kelima belas sel), sedangkan $G \subseteq A_{15}$ karena tiap $s_t$ genap: jadi $\langle s_0, \dots, s_{12}\rangle = A_{15}$ .

17. Pertanyaan 13 dan 16 memberi $A_{15} = \langle s_0, \dots, s_{12}\rangle \subseteq H$ ; pertanyaan 9 memberi $H \subseteq A_{15}$ . Jadi $H = A_{15}$ , berorde $15!/2 = 653\,837\,184\,000$ : setiap penataan ulang yang genap atas kelima belas ubin adalah efek sebuah program.

18. Pertanyaan 8 menyusutkan $R = \{I = +1\}$ menjadi mewujudkan setiap $\rho \in \mathfrak{S}_{15}$ yang genap oleh sebuah program, dan itu diselesaikan pertanyaan 17. Bersama pertanyaan 6, $\abs R = 16!/2 = 10\,461\,394\,944\,000$ . Dua kelas: biarkan $t_0 = (14\ 15)$ bekerja pada isi: $\varphi(\sigma) = t_0 \circ \sigma$ . Langkah sah dari $\sigma$ juga langkah sah dari $\varphi(\sigma)$ (sel kekosongannya tak berubah, sebab $(t_0\sigma)^{-1}(16) = \sigma^{-1}(t_0(16)) = \sigma^{-1}(16)$ , dan sel yang digeser pun sama), lalu $\varphi(\sigma \circ \tau) = \varphi(\sigma) \circ \tau$ : jadi $\varphi$ memetakan rangkaian langkah ke rangkaian langkah, secara bijektif (ia involusi). Ia membalik $I$ , sebab $\varepsilon(t_0\sigma) = -\varepsilon(\sigma)$ dengan sel kekosongan yang sama. Maka $\varphi$ memetakan kelas $R = \{I = +1\}$ milik $\mathrm{id}$ secara bijektif pada kelas $\varphi(\mathrm{id}) = \sigma_L$ , yang karenanya seluruhnya $\{I = -1\}$ : jadi tepat ada dua kelas. Inilah teorema Johnson–Story.

19. Indekskan selnya menurut urutan baca dan misalkan $k = 4(i - 1) + j$ sel kekosongan. Cacah inversi $\sigma$ (pasangan sel $x < y$ dengan $\sigma(x) > \sigma(y)$ ): pasangan atas dua sel berubin menyumbang $N$ ; pasangan yang melibatkan kekosongan: sel sesudah kekosongan semuanya memuat ubin $< 16$ , masing-masing terbalik (ada $16 - k$ pasangan), sedangkan sel sebelumnya tak pernah terbalik. Jadi $\varepsilon(\sigma) = (-1)^{N + 16 - k} = (-1)^{N + k}$ . Karena $k = 4(i-1) + j \equiv j \pmod 2$ , kita peroleh

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

dengan memakai $i = 5 - r$ . Menurut pertanyaan 18, $\sigma$ terselesaikan bila dan hanya bila $I(\sigma) = +1$ , bila dan hanya bila $N + r$ ganjil. Periksa: tersusun, $N = 0$ , $r = 1$ : ganjil, terselesaikan; Loyd, $N = 1$ , $r = 1$ : genap, tidak terselesaikan.

20. Aksi: $e \cdot \sigma = \sigma \circ \mathrm{id} = \sigma$ dan $g \cdot (h \cdot \sigma) = \sigma \circ h^{-1} \circ g^{-1} = \sigma \circ (gh)^{-1} = (gh) \cdot \sigma$ ; dan $\sigma \circ h^{-1}$ tetap konfigurasi yang kekosongannya di rumah ( $h$ membiarkan sel $16$ tetap). Bebas: dari $\sigma \circ h^{-1} = \sigma$ diperoleh $h^{-1} = \mathrm{id}$ (susun dengan $\sigma^{-1}$ ). Orbit = kelas program: pertanyaan 9 mengatakan konfigurasi yang terjangkau dari $\sigma$ lewat program persis semua $\sigma \circ \pi^{-1}$ , $\pi \in H$ , yakni orbit $H \cdot \sigma$ . Pencacahan: sifat bebas membuat $h \mapsto h \cdot \sigma$ injektif, jadi setiap orbit punya $\abs H = 15!/2$ unsur; karenanya $15!$ konfigurasi berkekosongan di rumah terbelah menjadi $15!\,/\,(15!/2) = 2$ orbit — bayangan kedua kelas Johnson–Story pada konfigurasi berkekosongan di rumah.

21. Papan $3 \times 3$ bersifat bipartit terhadap pewarnaan papan catur: setiap langkah pada suatu jalan mengubah warnanya, jadi setiap jalan tertutup berpanjang genap. Jalan tertutup yang menyinggahi masing-masing dari $9$ sel tepat sekali akan berpanjang $9$ , sebuah bilangan ganjil: mustahil. Karena itu konstruksi perjalanan agung pada Bagian III tidak tersedia untuk teka-teki delapan.

22. Perjalanan keliling $9 \to 8 \to 7 \to 4 \to 1 \to 2 \to 3 \to 6 \to 9$ (semua langkahnya bertetangga; berpanjang $8$ , genap): dengan pembukuan pertanyaan 11 memakai $c_1 = 8, c_2 = 7, c_3 = 4, c_4 = 1, c_5 = 2, c_6 = 3, c_7 = 6$ , efeknya adalah

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

yaitu siklus berpanjang $7$ yang membiarkan pusat $5$ tetap (isi $7$ berpindah ke $8$ , isi $4$ ke $7$ , isi $1$ ke $4$ , isi $2$ ke $1$ , isi $3$ ke $2$ , isi $6$ ke $3$ , dan isi $8$ ke $6$ ). Perjalanan pojok $9 \to 6 \to 5 \to 8 \to 9$ berefek $(6\ 8\ 5)$ (isi $5$ berpindah ke $6$ , isi $8$ ke $5$ , isi $6$ — yang terparkir di $9$ — ke $8$ ). Ambil $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$ . Konjugasi (pertanyaan 12) memberi

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

karena $\zeta'$ membiarkan $5$ tetap. Penyangga $T_0 = (y_1\ y_0\ 5)$ dan $T_1 = (y_2\ y_1\ 5)$ berbagi tepat $\{y_1, 5\}$ , jadi Lema A memberi seluruh permutasi genap atas $\{y_0, y_1, y_2, 5\}$ . Lalu $T_2 = (y_3\ y_2\ 5)$ menambahkan $y_3$ lewat Lema B (kedua hurufnya $y_2, 5$ berada di himpunan yang sedang dipegang, dengan $k = 4$ ), dan $T_3, T_4, T_5$ menambahkan $y_4, y_5, y_6$ berturut-turut: jadi seluruh permutasi genap atas kedelapan sel bukan-rumah berada di grup program, yang juga hanya terdiri atas permutasi genap (hujah pertanyaan 9 tidak bergantung pada bentuk papan). Maka $H_{3\times3} = A_8$ , dan penalaran pertanyaan 6, 8, 18 — yang juga tak bergantung pada papan — menunjukkan konfigurasi yang terjangkau persis yang ber- $I = +1$ : separuh dari $9!$ , yakni $181\,440$ .

23. Berilah nama sel $0, \dots, n-1$ sepanjang siklus itu. Satu langkah menukar kekosongan dengan salah satu dari dua tetangganya. Bacalah ubin itu menurut urutan siklis mulai tepat sesudah kekosongan: diperoleh kata $w$ yang mendaftar $n - 1$ ubin. Menggeser kekosongan satu langkah maju mengganti $(p, w)$ dengan $(p + 1, \rho w)$ , dengan $p$ menyatakan sel kekosongan dan $\rho$ memutar kata itu satu posisi; langkah mundurnya adalah inversnya. Jadi urutan siklis ubinnya (yakni katanya kecuali perputaran) bersifat invarian. Kelas terjangkau milik $(p, w)$ adalah orbit pemetaan $g \colon (p, w) \mapsto (p+1, \rho w)$ , yaitu unsur berorde $\operatorname{lcm}(n, n-1) = n(n-1)$ di hasil kali kedua grup siklik itu (translasi $\Z/n\Z$ dan perputaran atas $n-1$ posisi kata), dengan KPK-nya sama dengan $n(n-1)$ karena $\gcd(n, n-1) = 1$ : jadi tiap kelas punya tepat $n(n-1)$ konfigurasi, semuanya berkalung sama. Banyaknya kelas: $n!\,/\,\bigl(n(n-1)\bigr) = (n-2)!$ . Untuk $n \geq 5$ berlaku $(n-2)! > 2$ : invarian paritas (paling banyak dua kelas) buta terhadap hampir seluruh halangannya; kekayaan papan $4 \times 4$ — tempat paritas menjadi satu-satunya halangan — adalah fakta yang sungguh geometris, bukan fakta formal.

24. Kedua papan memuat ubin dalam urutan yang seluruhnya terbalik, jadi $N = \binom{15}{2} = 105$ pada kedua kasus (setiap pasangan ubin terbalik). Kekosongan di rumah: $r = 1$ , sehingga $N + r = 106$ genap: tidak terselesaikan. Kekosongan di sel $1$ : kekosongan berada di baris teratas, $r = 4$ , sehingga $N + r = 109$ ganjil: terselesaikan. Dua papan yang hanya berbeda letak lubangnya jatuh di sisi tembok yang berlawanan.

25. Sifat morfisma: ia mengubah “satu langkah = satu transposisi” menjadi “satu langkah = satu pembalikan tanda” (pertanyaan 2 dan 4), sehingga $I$ terhitungkan langkah demi langkah. Lagrange: ia memaksa $6 \mid \abs{\langle s, t\rangle}$ pada Lema A dan menakar koset pada penyingkiran subgrup berorde $6$ (pertanyaan 14). Pembangunan oleh siklus berpanjang $3$ : ia mengubah “ $H$ memuat cukup banyak siklus berpanjang $3$ ” menjadi “ $H$ memuat seluruh $A_{15}$ ” (pertanyaan 16). Konjugasi: ia memproduksi kelima belas siklus berurutan berpanjang $3$ dari satu perjalanan $2 \times 2$ yang diangkut perjalanan agung (pertanyaan 12–13), dan juga siklus berpanjang $3$ bertulis $(a\ b\ w)$ pada Lema B. Asas umumnya: sebuah invarian membuktikan kemustahilan, sebuah konstruksi gamblang membuktikan kemungkinan, dan sebuah masalah tuntas terpecahkan tepat ketika kedua batas itu bertemu — di sini, pada seperdua.

Istilah yang didefinisikan dalam bab ini

Lihat semua 395 istilah di glosarium