---
title: "Himpunan dan Struktur"
book: "Matematika Universitas — Tahun 2"
subject: math
language: id
chapter: 1
exercises: 12
source: https://one-course.com/books/math/4/id/chapter/1-himpunan-dan-struktur
---

# Bab 1 — Himpunan 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](#def-b2-structures-ideal), dan teorema sisa Cina. Semua yang ada di sini dipakai tiada henti pada sisa buku: tanda permutasi membangun determinan ([Bab 2](https://one-course.com/books/math/4/id/chapter/2-aljabar-linear#ch-b2-linalg)), [ring kuosien](#def-b2-structures-quotientring) 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](#prop-b2-structures-images) 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).**

1. Setiap himpunan bagian tak hingga dari $\N$ adalah [terbilang](#def-b2-structures-countable) ; suatu himpunan paling banyak [terbilang](#def-b2-structures-countable) bila dan hanya bila ia terinjeksi ke $\N$ , bila dan hanya bila ia kosong atau merupakan peta surjektif dari $\N$ .
2. $\N \times \N$ [terbilang](#def-b2-structures-countable) ; hasil kali dua himpunan yang paling banyak [terbilang](#def-b2-structures-countable) juga paling banyak [terbilang](#def-b2-structures-countable) .
3. Gabungan yang paling banyak [terbilang](#def-b2-structures-countable) atas himpunan yang paling banyak [terbilang](#def-b2-structures-countable) tetap paling banyak [terbilang](#def-b2-structures-countable) .
4. $\Z$ dan $\Q$ [terbilang](#def-b2-structures-countable) .

**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](#def-b2-structures-countable) dengan $\varphi(E) \subseteq
\N$: hingga atau [terbilang](#def-b2-structures-countable). 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](#def-b2-structures-countable) ke $\bigcup E_n$.

(4) $\Z = \N \cup (-\N^*)$: gabungan [terbilang](#def-b2-structures-countable). $\Q$ adalah peta surjektif dari $\Z \times \N^*$ (pemetaan pecahan), jadi paling banyak [terbilang](#def-b2-structures-countable), 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](#def-b2-structures-algebra)* apabila ia menolkan suatu polinomial tak nol berkoefisien rasional. Himpunan $\overline\Q$ semua bilangan [aljabar](#def-b2-structures-algebra) adalah [terbilang](#def-b2-structures-countable): polinomial berderajat $\leq d$ atas $\Q$ terinjeksi ke $\Q^{d+1}$, yaitu hasil kali hingga atas [himpunan terbilang](#def-b2-structures-countable) ([Proposisi 1.6](#prop-b2-structures-countablestable) (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](#def-b2-structures-countable) atas himpunan hingga ([Proposisi 1.6](#prop-b2-structures-countablestable) (3)), tak hingga karena memuat $\Q$. Digabungkan dengan ketakterbilangan $\R$ ([Teorema 1.9](#thm-b2-structures-cantor) di bawah), ini membuktikan — tanpa menunjukkan satu pun contohnya — bahwa bilangan transenden memang ada dan justru merupakan mayoritas yang tak [terbilang](#def-b2-structures-countable): itulah hujah pencacahan Cantor tahun 1874, keberadaan semata-mata lewat kardinalitas.

**Teorema 1.9 (Cantor; ketakterbilangan R\RR).**

1. Untuk setiap himpunan $E$ , tidak ada surjeksi $E \to  \mathcal{P}(E)$ .
2. $\R$ *tidak* [terbilang](#def-b2-structures-countable) .

**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](#def-b2-structures-countable).

**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](#def-b2-structures-countable): 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](#exo-b2-structures-3)) semuanya [ekuipoten](#def-b2-structures-countable): itulah “kardinalitas kontinum”.

**Contoh 1.12 (Ruas dan persegi).**

$\intcc{0}{1}$ dan $\intcc{0}{1}^2$ [ekuipoten](#def-b2-structures-countable) — 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](#thm-b2-structures-cantorbernstein)) 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](https://one-course.com/books/math/4/id/chapter/4-topologi-ruang-metrik#ch-b2-metric)).

## 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](#def-b2-structures-generated) tak hingga. ∎

**Teorema 1.14 (Lagrange).**

Misalkan $G$ grup hingga dan $H$ subgrupnya. Maka $\abs H$ membagi $\abs G$. Khususnya [orde](#def-b2-structures-generated) 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: A3A_3A3​ di dalam S3\mathfrak{S}_3S3​).**

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](#def-b2-structures-generated):* 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](#prop-b2-structures-cyclic) di bawah, ada tepat satu subgrup untuk tiap pembagi $12$ — berorde $1, 2, 3, 4,
6, 12$, yang berturut-turut [dibangun](#def-b2-structures-generated) 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](#pb-b2-structures-1), pertanyaan 14). Lagrange membatasi [orde](#def-b2-structures-generated) yang mungkin; ia tidak menjanjikan [orde](#def-b2-structures-generated) 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.](https://one-course.com/images/onecourse/chapters/math-4/b2-structures/fig-8a06f3f8215b.svg)

*Kisi subgrup $\Z/12\Z$: satu subgrup untuk tiap pembagi $12$ ([Proposisi 1.17](#prop-b2-structures-cyclic)), 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](#def-b2-structures-generated) berorde $n$.

1. $G$ isomorfik dengan $(\Z/n\Z, +)$ , lewat $\overline k \mapsto  a^k$ .
2. Setiap subgrup $G$ adalah [siklik](#def-b2-structures-generated) ; untuk tiap pembagi $d \mid n$ ada tepat satu subgrup berorde $d$ , yakni $\langle  a^{n/d}\rangle$ .
3. $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](#def-b2-structures-generated)); sifat universal ([Definisi 1.3](#def-b2-structures-quotient)) 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](#def-b2-structures-generated) pada [Definisi 1.13](#def-b2-structures-generated) 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](#def-b2-structures-sn) yang saling lepas, tunggal kecuali urutan faktornya. [Siklus](#def-b2-structures-sn) 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](#def-b2-structures-sn) $(x\
\sigma(x)\ \cdots\ \sigma^{k-1}(x))$, dan $\sigma$ adalah hasil kali [siklus-siklus](#def-b2-structures-sn) itu: pada tiap orbit hanya [siklus](#def-b2-structures-sn) yang bersangkutan yang bekerja. Ketunggalan: sembarang pemfaktoran atas [siklus](#def-b2-structures-sn) saling lepas melahirkan orbit yang persis sama ([siklus](#def-b2-structures-sn) lewat $x$ mestilah $(x\
\sigma(x)\ \cdots)$). [Siklus](#def-b2-structures-sn) saling lepas komutatif karena menggerakkan titik yang berbeda; pernyataan tentang [orde](#def-b2-structures-generated) menyusul karena $\sigma^m =
\mathrm{id}$ bila dan hanya bila pangkat ke-$m$ tiap [siklus](#def-b2-structures-sn) 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](#def-b2-structures-sn) $(4, 3, 2)$ — satu [siklus](#def-b2-structures-sn) panjang $4$, satu [siklus](#def-b2-structures-sn) panjang $3$, dan satu [transposisi](#def-b2-structures-sn)? 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](#def-b2-structures-sn), 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](#thm-b2-structures-cycles) 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](#def-b2-structures-sn): 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](#def-b2-structures-sn) 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](#def-b2-structures-sn) $\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](#def-b2-structures-sn) membangun $\mathfrak{S}_n$ (sebab untuk sebarang [siklus](#def-b2-structures-sn) berlaku $(a_1\cdots a_k) = (a_1\,a_k)(a_1\,a_{k-1})\cdots(a_1\,a_2)$, lalu [Teorema 1.19](#thm-b2-structures-cycles) merampungkannya); morfisma ke $\{\pm1\}$ ditentukan oleh nilainya pada pembangun.

*Akibat.* Kesamaan [siklus](#def-b2-structures-sn) di atas menuliskan [siklus](#def-b2-structures-sn) berpanjang $k$ sebagai $k - 1$ [transposisi](#def-b2-structures-sn): tandanya $(-1)^{k-1}$. Tentang $A_n$: morfisma $\varepsilon$ surjektif ([transposisi](#def-b2-structures-sn) ada untuk $n \geq 2$), dan kedua “koset” $A_n$ dan $(1\,2)A_n$ [ekuipoten](#def-b2-structures-countable) 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](https://one-course.com/books/math/4/id/chapter/2-aljabar-linear#ch-b2-linalg).

**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](#def-b2-structures-sn):* $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](#def-b2-structures-sn):* $\sigma = (1\,4)(1\,3)(2\,5)$, tiga faktor, $(-1)^3 = -1$. Tiga perhitungan, satu paritas: ketunggalan pada [Teorema 1.21](#thm-b2-structures-signature) 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](https://one-course.com/books/math/4/id/chapter/2-aljabar-linear#ch-b2-linalg); 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](#def-b2-structures-generated)* oleh $x$ adalah $xA = \{xa\}$ (sebuah ideal *utama*).

**Teorema 1.26 (Ideal pada Z\ZZ dan pada K[X]K[X]K[X]).**

Setiap [ideal](#def-b2-structures-ideal) $\Z$ berbentuk $n\Z$ untuk suatu $n \in \N$ yang tunggal; setiap [ideal](#def-b2-structures-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](#def-b2-structures-ideal) khususnya adalah subgrup, dan $n\Z$ memang [ideal](#def-b2-structures-ideal)). Untuk $K[X]$: misalkan $I \neq \{0\}$ sebuah [ideal](#def-b2-structures-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](#def-b2-structures-ideal) $x\Z + y\Z$ (atau padanan polinomialnya) dengan [ideal](#def-b2-structures-ideal) utama yang [dibangun](#def-b2-structures-generated) FPB — persis definisi FPB yang dipakai pada Tahun ke-1, kini dikenali sebagai pernyataan tentang [ideal](#def-b2-structures-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](#def-b2-structures-ideal):* [ideal](#def-b2-structures-ideal) $(X^3 - 1)\Q[X] + (X^2 - 1)\Q[X]$ bersifat utama ([Teorema 1.26](#thm-b2-structures-principal)); 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](#def-b2-structures-ideal) mengenali FPB *tanpa membagi* — akar yang sama-sama dimiliki keduanya menempatkan [idealnya](#def-b2-structures-ideal), dan Euklides sekadar mengesahkannya.

**Definisi 1.28 (Ring kuosien Z/nZ\Z/n\ZZ/nZ, ditinjau ulang).**

Untuk sebuah [ideal](#def-b2-structures-ideal) $I$ pada $A$, relasi $x \sim y \iff x - y \in I$ adalah relasi ekuivalensi yang selaras dengan $+$ dan $\times$; [himpunan kuosien](#def-b2-structures-quotient) $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](#ex-b2-structures-crtinverse). 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](#exo-b2-structures-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](#thm-b2-structures-lagrange)): setiap unsur dipangkatkan [orde](#def-b2-structures-generated) 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](#def-b2-structures-generated)? Hitung [ordenya](#def-b2-structures-generated) 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](#def-b2-structures-generated) 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](#def-b2-structures-generated) $4, 2, 4, 2, 2$ dan tidak pernah $8$. Bandingkan dengan [Latihan 1.10](#exo-b2-structures-10): $(\Z/p\Z)^*$ *memang* [siklik](#def-b2-structures-generated) 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](https://one-course.com/books/math/4/id/chapter/3-reduksi-endomorfisma#ch-b2-reduction).

**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](#def-b2-structures-ideal) utama, persis seperti diramalkan [Teorema 1.26](#thm-b2-structures-principal), [dibangun](#def-b2-structures-generated) oleh $X^2$ yang monik dan berderajat terkecil di dalam kernel — itulah *polinomial minimal* $A$, bintang [Bab 3](https://one-course.com/books/math/4/id/chapter/3-reduksi-endomorfisma#ch-b2-reduction). Petanya adalah [aljabar](#def-b2-structures-algebra) komutatif berdimensi dua $\{aI + bA\}$: morfisma evaluasi menciutkan $\R[X]$ yang berdimensi tak hingga menjadi [aljabar](#def-b2-structures-algebra) 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](#def-b2-structures-quotient)): ia membangun $\Z/n\Z$ di sini, mendefinisikan pemetaan pada himpunan penyelesaian sistem linear di [Bab 2](https://one-course.com/books/math/4/id/chapter/2-aljabar-linear#ch-b2-linalg), 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](https://one-course.com/books/math/4/id/chapter/2-aljabar-linear#ch-b2-linalg)), keawetan trace terhadap keserupaan, dan besaran kekal pada [Bab 16](https://one-course.com/books/math/4/id/chapter/16-persamaan-diferensial#ch-b2-diffeq). *Mencacah dengan bersandar pada struktur*: Lagrange mencacah lewat koset, dimensi mencacah lewat basis ([Bab 2](https://one-course.com/books/math/4/id/chapter/2-aljabar-linear#ch-b2-linalg)), multiplisitas mencacah lewat derajat polinomial ([Bab 3](https://one-course.com/books/math/4/id/chapter/3-reduksi-endomorfisma#ch-b2-reduction)); 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](#def-b2-structures-quotient), 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](#exo-b2-structures-4) memberi pernyataan yang benar dengan syarat saling prima dan komutatif, sedangkan [siklus](#def-b2-structures-sn) saling lepas memberi versi permutasinya. (iii) Keterbilangan bertahan terhadap *gabungan* [terbilang](#def-b2-structures-countable) dan *hasil kali* hingga, tetapi tidak terhadap hasil kali [terbilang](#def-b2-structures-countable): $\{0,1\}^{\N}$ tidak [terbilang](#def-b2-structures-countable) ([Latihan 1.3](#exo-b2-structures-3)) walaupun tiap faktornya hanya punya dua unsur. (iv) Cantor–Bernstein hanya menuntut injeksi dua arah, tetapi bijeksi yang [dibangunnya](#def-b2-structures-generated) lazimnya tidak kontinu dan tidak gamblang — jangan berharap ada rumusnya ([Contoh 1.11](#ex-b2-structures-cbexample)).

**Catatan 1.37 (Di mana bab ini dipakai).**

Hampir di mana-mana. Tanda permutasi membangun determinan ([Bab 2](https://one-course.com/books/math/4/id/chapter/2-aljabar-linear#ch-b2-linalg)); morfisma evaluasi $P \mapsto P(u)$ dan [ideal](#def-b2-structures-ideal) utama pada $K[X]$ melahirkan polinomial minimal serta penguraian kernel pada [Bab 3](https://one-course.com/books/math/4/id/chapter/3-reduksi-endomorfisma#ch-b2-reduction); keterbilangan adalah panggung tempat [Bab 21](https://one-course.com/books/math/4/id/chapter/21-peluang-pada-ruang-terbilang#ch-b2-proba) bermain (peluang pada ruang [terbilang](#def-b2-structures-countable)) sekaligus alasan mengapa topologi terus-menerus menghasilkan himpunan padat yang [terbilang](#def-b2-structures-countable) ([Bab 4](https://one-course.com/books/math/4/id/chapter/4-topologi-ruang-metrik#ch-b2-metric)). 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](#def-b2-structures-countable)? 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 Latihan 1.1.**

*Himpunan bagian hingga dari $\N$:* [terbilang](#def-b2-structures-countable) — himpunan semua himpunan bagian $\intint{0}{n}$ adalah hingga, dan himpunan bagian yang hingga membentuk gabungan [terbilang](#def-b2-structures-countable) atas $n$ dari himpunan-himpunan itu ([Proposisi 1.6](#prop-b2-structures-countablestable) (3)); tak hingga karena ia memuat semua himpunan tunggal.

*Semua himpunan bagian $\N$:* tidak [terbilang](#def-b2-structures-countable), menurut teorema Cantor ([Teorema 1.9](#thm-b2-structures-cantor) (1) dengan $E = \N$).

*$\R \setminus \Q$:* tidak [terbilang](#def-b2-structures-countable) — sebab jika tidak, $\R = \Q
\cup (\R\setminus\Q)$ akan menjadi gabungan dua [himpunan terbilang](#def-b2-structures-countable), yang bertentangan dengan [Teorema 1.9](#thm-b2-structures-cantor) (2).

*Polinomial atas $\Q$:* [terbilang](#def-b2-structures-countable) — polinomial berderajat $\leq n$ terinjeksi ke $\Q^{n+1}$ (hasil kali hingga atas [himpunan terbilang](#def-b2-structures-countable)), lalu ambil gabungan atas $n$.

*Barisan biner yang akhirnya nol:* [terbilang](#def-b2-structures-countable) — 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](#def-b2-structures-sn) saling lepas, [orde](#def-b2-structures-generated) dan tanda keempat permutasi tadi, serta $\sigma^{2026}$.

**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](#def-b2-structures-sn) 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](#def-b2-structures-sn) berpanjang $7$ (sesuai dugaan: $\sigma\tau$ dan $\tau\sigma$ sekonjugasi, jadi tipe siklusnya sama).

[Orde](#def-b2-structures-generated) dan tanda: $\sigma$ bertipe [siklus](#def-b2-structures-sn) $(4,2)$, jadi berorde $\operatorname{lcm}(4,2) = 4$ dan bertanda $(-1)^3(-1)^1 = +1$; $\tau$ adalah [siklus](#def-b2-structures-sn) berpanjang $3$, jadi berorde $3$ dan bertanda $+1$; kedua hasil kali tadi [siklus](#def-b2-structures-sn) 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](#def-b2-structures-sn) berpanjang $4$; [transposisinya](#def-b2-structures-sn) 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](#def-b2-structures-countable) sepasang demi sepasang *(uraian biner dua arah; Cantor–Bernstein menyerap kerepotan penyajian ganda)*.

**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](#thm-b2-structures-cantorbernstein)) yang diterapkan pada dua injeksi terakhir, $\intcc{0}{1}$ dan $\{0,1\}^{\N}$ [ekuipoten](#def-b2-structures-countable), jadi ketiga himpunan itu [ekuipoten](#def-b2-structures-countable).

**Latihan 1.4 ★.**

Misalkan $G$ sebuah grup dan $a, b \in G$ dua unsur komutatif yang [ordenya](#def-b2-structures-generated) 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 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](#def-b2-structures-generated) membagi $m$ sekaligus $n$ (Lagrange pada masing-masing [grup siklik](#def-b2-structures-generated)), 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](#def-b2-structures-generated) 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 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](#def-b2-structures-generated) oleh [siklus](#def-b2-structures-sn) berpanjang $3$. *(Hasil kali dua [transposisi](#def-b2-structures-sn) adalah [siklus](#def-b2-structures-sn) berpanjang $3$ atau hasil kali dua [siklus](#def-b2-structures-sn) berpanjang $3$.)*

**Solusi Latihan 1.6.**

Setiap unsur $A_n$ adalah hasil kali sejumlah genap [transposisi](#def-b2-structures-sn) ([Teorema 1.21](#thm-b2-structures-signature): uraikan atas [transposisi](#def-b2-structures-sn); banyaknya genap karena tandanya $+1$). Cukuplah menuliskan setiap hasil kali dua [transposisi](#def-b2-structures-sn) memakai [siklus](#def-b2-structures-sn) 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](#def-b2-structures-sn) 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 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 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 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](#def-b2-structures-generated). *Petunjuk: ambil $m$ [orde](#def-b2-structures-generated) terbesar di antara unsur $G$; tunjukkan [orde](#def-b2-structures-generated) setiap unsur membagi $m$ (dengan [Latihan 1.4](#exo-b2-structures-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](#def-b2-structures-generated).

**Solusi Latihan 1.10.**

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

*Klaim: [orde](#def-b2-structures-generated) 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](#def-b2-structures-generated) itu saling prima dan kedua unsurnya komutatif ($G \subseteq K^*$ abelian), jadi menurut [Latihan 1.4](#exo-b2-structures-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](#def-b2-structures-generated).

Untuk $K = \Z/p\Z$: $(\Z/p\Z)^*$ adalah subgrup hingga dari $K^*$, jadi [siklik](#def-b2-structures-generated) (berorde $p - 1$).

**Latihan 1.11 ★★★.**

Buktikan bahwa grup $(\Q, +)$ tidak [siklik](#def-b2-structures-generated), dan yang lebih buruk lagi: ia bahkan tidak [dibangun](#def-b2-structures-generated) oleh berhingga unsur. Buktikan sebaliknya bahwa setiap subgrup $(\Q, +)$ yang [dibangun](#def-b2-structures-generated) oleh berhingga unsur adalah [siklik](#def-b2-structures-generated).

**Solusi Latihan 1.11.**

*Tidak [siklik](#def-b2-structures-generated):* 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](#def-b2-structures-generated) oleh berhingga unsur:* subgrup yang [dibangun](#def-b2-structures-generated) 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](#def-b2-structures-generated) oleh berhingga unsur adalah [siklik](#def-b2-structures-generated):* 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](#def-b2-structures-generated), [dibangun](#def-b2-structures-generated) oleh $\frac nQ$.

**Latihan 1.12 ★★.**

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

**Solusi Latihan 1.12.**

*Sebuah himpunan bagian [terbilang](#def-b2-structures-countable).* 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](#def-b2-structures-countable).

*Tak hingga $\implies$ [ekuipoten](#def-b2-structures-countable) 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](#def-b2-structures-countable) 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](#def-b2-structures-countable) 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](#thm-b2-structures-signature) 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?](https://one-course.com/images/onecourse/chapters/math-4/b2-structures/fig-1d273e45c191.svg)

![Konfigurasi yang tersusun dan konfigurasi 14–15 milik Sam Loyd. Pertanyaan senilai $1000: dapatkah geseran yang sah mengubah papan kanan menjadi papan kiri?](https://one-course.com/images/onecourse/chapters/math-4/b2-structures/fig-fbca61dbb9bd.svg)

*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](#thm-b2-structures-signature), dan dua sel disebut *bertetangga* apabila keduanya berbagi satu rusuk papan.

**Bagian I — Konfigurasi, langkah, tanda.**

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

5. 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.
6. 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](#def-b2-structures-sn) tetap atas dua sel yang lain.)*
7. 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.
8. 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)$.

9. 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}$ .
10. (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](#def-b2-structures-sn) berpanjang $3$ , yakni $(11\ 12\ 15)$ , dan bahwa perjalanan sebaliknya memberi $(11\ 15\ 12)$ . Keduanya berada di $H$ .
11. (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](#def-b2-structures-sn) 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)$.
12. Buktikan rumus konjugasi pada sembarang $\mathfrak{S}_n$: untuk sebuah permutasi $g$ dan sebuah [siklus](#def-b2-structures-sn) 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.
13. Turunkan bahwa $H$ memuat kelima belas [siklus](#def-b2-structures-sn) *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.**

14. (Lema A) Misalkan $s$ dan $t$ dua [siklus](#def-b2-structures-sn) 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](#def-b2-structures-generated) ), hasil kali $st$ adalah [transposisi](#def-b2-structures-sn) ganda; tunjukkan bahwa $A_4$ tidak punya subgrup berorde $6$ *(subgrup berindeks $2$ memuat setiap kuadrat; cacah [siklus](#def-b2-structures-sn) berpanjang $3$ di antara kuadrat itu)* ; lalu simpulkan bahwa $\langle s, t\rangle$ adalah seluruh grup alternating atas keempat huruf $\{a, b, c, d\}$ .
15. (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](#def-b2-structures-sn) 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$ .
16. Turunkan bahwa grup $G$ pada Lema B memuat setiap permutasi genap atas $X \cup \{w\}$ *(pakai [Latihan 1.6](#exo-b2-structures-6): [siklus](#def-b2-structures-sn) berpanjang $3$ membangunnya)* . Lalu, dengan merangkai Lema A dan Lema B sepanjang [siklus](#def-b2-structures-sn) 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}$ .
17. 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.
18. (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.**

19. (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.
20. (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.
21. (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.)*
22. (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](#def-b2-structures-sn) berpanjang $7$ , yaitu $\zeta'$ , yang membiarkan pusat $5$ tetap) dan efek perjalanan pojok $9 \to 6  \to 5 \to 8 \to 9$ ( [siklus](#def-b2-structures-sn) 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.
23. (Papan yang miskin) Kini ambil papan berupa satu [siklus](#def-b2-structures-sn) 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](#def-b2-structures-generated) 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.
24. 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?
25. (Rangkuman) Buktinya bertumpu pada dua pilar yang saling bebas: sebuah *invarian* ( $I$ , yang [dibangun](#def-b2-structures-generated) 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](#def-b2-structures-sn) berpanjang $3$ ; dan konjugasi. Nyatakan asas umumnya dalam satu baris.

**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](#def-b2-structures-sn) $(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](#def-b2-structures-sn) maupun tandanya (uraikan $\rho$ atas [transposisi](#def-b2-structures-sn); 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](#def-b2-structures-sn) 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](#def-b2-structures-sn) 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](#def-b2-structures-sn) 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](#thm-b2-structures-lagrange), diterapkan pada kedua subgrup [siklik](#def-b2-structures-generated) 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](#def-b2-structures-sn) berpanjang $3$, sebut saja $\gamma$, adalah kuadrat, sebab $\gamma = (\gamma^2)^2$, dan $A_4$ memuat delapan [siklus](#def-b2-structures-sn) 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](#def-b2-structures-sn) 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](#exo-b2-structures-6), [siklus](#def-b2-structures-sn) 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](#def-b2-structures-sn) 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](#def-b2-structures-sn) 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](#def-b2-structures-generated) 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](#def-b2-structures-sn)” 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](#def-b2-structures-sn) berpanjang $3$:* ia mengubah “$H$ memuat cukup banyak [siklus](#def-b2-structures-sn) berpanjang $3$” menjadi “$H$ memuat seluruh $A_{15}$” (pertanyaan 16). *Konjugasi:* ia memproduksi kelima belas [siklus](#def-b2-structures-sn) berurutan berpanjang $3$ dari satu perjalanan $2 \times 2$ yang diangkut perjalanan agung (pertanyaan 12–13), dan juga [siklus](#def-b2-structures-sn) 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.