---
title: "Sets and Structures"
book: "University Mathematics — Year 2"
subject: math
language: en
chapter: 1
exercises: 12
source: https://one-course.com/books/math/4/en/chapter/1-sets-and-structures
---

# Chapter 1 — Sets and Structures

This opening chapter sharpens the foundations laid in the Year 1 volume into working tools of the trade: the calculus of sets and quotients, the comparison of infinite sets ([countability](#def-b2-structures-countable), Cantor–Bernstein), and the structural theory of groups and rings — Lagrange’s theorem, the symmetric group with its signature, [ideals](#def-b2-structures-ideal) and the Chinese remainder theorem. Everything here is used relentlessly in the rest of the book: the signature builds the determinant ([Chapter 2](https://one-course.com/books/math/4/en/chapter/2-linear-algebra#ch-b2-linalg)), [quotient rings](#def-b2-structures-quotientring) drive arithmetic, and [countability](#def-b2-structures-countable) underlies both topology and probability.

## 1.1 Sets, maps, quotients

We use freely the language of sets, maps, and equivalence and [order](#def-b2-structures-generated) relations set up in the Year 1 volume. Two upgrades deserve a proper statement.

**Proposition 1.1 (Images and preimages of families).**

Let $f \colon E \to F$ and let $(A_i)_{i \in I}$, $(B_j)_{j \in J}$ be families of subsets of $E$, resp. $F$. Then

$$
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{equality for injective } f).
$$

**Proof.** Each identity is an unwinding of definitions; for instance $x \in
f^{-1}(\bigcap B_j) \iff f(x) \in B_j$ for all $j$ $\iff x \in
f^{-1}(B_j)$ for all $j$. The image identities and the failure of equality in the intersection case (with the injectivity fix) were proved in the Year 1 volume for two sets; the arguments are identical for families. ∎

**Example 1.2 (Where the image inclusion is strict).**

Take $f \colon \R \to \R$, $f(x) = x^2$, with $A_1 =
\intcc{-1}{0}$ and $A_2 = \intcc{0}{1}$. Then

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

the inclusion of [Proposition 1.1](#prop-b2-structures-images) is as strict as can be — the two preimage points $\pm x$ of a common value live in different $A_i$. Injectivity is exactly what forbids this splitting, which is why preimages (which never merge points) satisfy all four identities unconditionally while images lose the one about intersections. Rule of thumb for the whole book: push *preimages* through set operations freely; handle images with care.

**Definition 1.3 (Quotient set).**

Let $\mathcal{R}$ be an equivalence relation on $E$. The *quotient set* $E/\mathcal{R}$ is the set of equivalence classes; the surjection $\pi \colon E \to E/\mathcal{R}$, $x \mapsto \mathrm{cl}(x)$, is the *canonical projection*.

*Universal property (factorization):* if $f \colon E \to F$ is *compatible* with $\mathcal{R}$ (i.e. $x \mathbin{\mathcal{R}}
y \implies f(x) = f(y)$), there is exactly one map $\overline f
\colon E/\mathcal{R} \to F$ with $f = \overline f \circ \pi$.

**Proof of the universal property.** Uniqueness: the requirement $f = \overline f \circ \pi$ reads

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

and since $\pi$ is surjective, every element of $E/\mathcal{R}$ is some $\mathrm{cl}(x)$: the values of $\overline f$ are all forced. Existence: take the display as the *definition* of $\overline f$; it is unambiguous precisely by compatibility — if $\mathrm{cl}(x) =
\mathrm{cl}(y)$, then $x \mathbin{\mathcal{R}} y$, so $f(x) =
f(y)$ and the two candidate values agree — and it factorizes $f$ by construction. Note the division of labour: surjectivity of $\pi$ gives uniqueness, compatibility gives existence. ∎

**Example 1.4.**

$\Z/n\Z$ is the quotient of $\Z$ by congruence modulo $n$; the well-definedness checks of the Year 1 volume were instances of the universal property. Quotients turn “compatible constructions on representatives” into honest maps — we use this constantly below.

## 1.2 Countability and cardinality

**Definition 1.5 (Equipotence, countability).**

Two sets are *equipotent* when a bijection joins them. A set is *countable* when it is equipotent to $\N$ (some authors include finite sets; we say *at most countable* for “finite or countable”).

**Proposition 1.6 (Stability properties).**

1. Every infinite subset of $\N$ is [countable](#def-b2-structures-countable) ; a set is at most [countable](#def-b2-structures-countable) iff it injects into $\N$ iff it is empty or a surjective image of $\N$ .
2. $\N \times \N$ is [countable](#def-b2-structures-countable) ; a product of two at most [countable sets](#def-b2-structures-countable) is at most [countable](#def-b2-structures-countable) .
3. An at most [countable](#def-b2-structures-countable) union of at most [countable sets](#def-b2-structures-countable) is at most [countable](#def-b2-structures-countable) .
4. $\Z$ and $\Q$ are [countable](#def-b2-structures-countable) .

**Proof.** (1) List an infinite $A \subseteq \N$ by repeated minima: $a_0 =
\min A$, $a_{k+1} = \min\,(A \setminus \{a_0, \dots, a_k\})$ (nonempty since $A$ is infinite); the map $k \mapsto a_k$ is strictly increasing, injective, and surjective onto $A$ (every $a \in A$ exceeds only finitely many elements of $A$, so it is reached). If $E$ injects into $\N$ via $\varphi$, then $E$ is [equipotent](#def-b2-structures-countable) to $\varphi(E) \subseteq \N$: finite or [countable](#def-b2-structures-countable). If $s \colon \N \to
E$ is surjective, then $x \mapsto \min s^{-1}(\{x\})$ injects $E$ into $\N$.

(2) The map $(p, q) \mapsto 2^p(2q + 1) - 1$ is a bijection $\N^2
\to \N$ (every positive integer has a unique odd–even split $2^p m$ with $m$ odd, by unique factorization). Products: compose injections.

(3) Given sets $E_n$ with surjections $s_n \colon \N \to E_n$ (harmless when some $E_n$ is finite: repeat values), the map $(n, k)
\mapsto s_n(k)$ is a surjection from the [countable](#def-b2-structures-countable) $\N^2$ onto $\bigcup E_n$.

(4) $\Z = \N \cup (-\N^*)$: [countable](#def-b2-structures-countable) union. $\Q$ is a surjective image of $\Z \times \N^*$ (the fraction map), hence at most [countable](#def-b2-structures-countable), and infinite. ∎

**Example 1.7 (A pairing function, computed).**

The bijection $(p, q) \mapsto 2^p(2q + 1) - 1$ of the proof deserves to be seen at work. Its first values:

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

Row $p$ collects the integers $n$ for which $n + 1$ is exactly divisible by $2^p$: every natural number appears exactly once. Decoding is as explicit as encoding: for $n = 43$, factor $n + 1
= 44 = 2^2\cdot 11 = 2^2(2\cdot5 + 1)$, so $(p, q) = (2, 5)$. The closing insight: [countability](#def-b2-structures-countable) proofs are often *algorithms* in disguise — here, “factor out the twos”.

**Example 1.8 (The algebraic numbers are countable).**

A complex number is *algebraic* when it annihilates some nonzero polynomial with rational coefficients. The set $\overline\Q$ of algebraic numbers is [countable](#def-b2-structures-countable): polynomials of degree $\leq d$ over $\Q$ inject into $\Q^{d+1}$, a finite product of [countable sets](#def-b2-structures-countable) ([Proposition 1.6](#prop-b2-structures-countablestable) (2)); the union over $d$ enumerates the nonzero rational polynomials as $P_0, P_1,
P_2, \dots$; each $P_k$ has finitely many roots; and

$$
\overline\Q = \bigcup_{k \in \N}\ \{\text{roots of } P_k\}
$$

is a [countable](#def-b2-structures-countable) union of finite sets ([Proposition 1.6](#prop-b2-structures-countablestable) (3)), infinite since it contains $\Q$. Combined with the uncountability of $\R$ ([Theorem 1.9](#thm-b2-structures-cantor) below), this proves — without exhibiting a single one — that transcendental numbers exist and form an uncountable majority: Cantor’s counting argument of 1874, existence by cardinality alone.

**Theorem 1.9 (Cantor; uncountability of R\RR).**

1. For every set $E$ , there is no surjection $E \to  \mathcal{P}(E)$ .
2. $\R$ is *not* [countable](#def-b2-structures-countable) .

**Proof.** (1) was proved in the Year 1 volume (the diagonal set $D = \{x : x
\notin f(x)\}$).

(2) Suppose $(x_n)_{n \in \N}$ enumerates $\R$. Build nested segments $I_0 \supseteq I_1 \supseteq \dots$ with $\abs{I_n} = 3^{-n}$ and $x_n \notin I_n$: split the current segment into three closed thirds; at least one third avoids $x_n$ (a point meets at most two of the three). The nested-segments theorem (adjacent endpoints) provides $\ell \in \bigcap_n I_n$; but $\ell = x_N$ for some $N$, and $x_N
\notin I_N$: contradiction. ∎

**Theorem 1.10 (Cantor–Bernstein).**

If $E$ injects into $F$ and $F$ injects into $E$, then $E$ and $F$ are [equipotent](#def-b2-structures-countable).

**Proof.** Let $f \colon E \to F$ and $g \colon F \to E$ be injections. For each point (of $E$ or $F$), trace its *ancestor chain* of successive preimages, $x \mapsto g^{-1}(x) \mapsto
f^{-1}(g^{-1}(x)) \mapsto \dots$ — each step is defined as long as the current point lies in the image of the relevant injection, and is then unique by injectivity. Three mutually exclusive fates: the chain stops at a point of $E \setminus g(F)$ (*origin in $E$*), stops at a point of $F \setminus f(E)$ (*origin in $F$*), or never stops. This partitions $E = E_E \cup E_F \cup
E_\infty$ and $F = F_E \cup F_F \cup F_\infty$ according to the origin.

Now observe: $f$ maps $E_E$ *onto* $F_E$ — the chain of $f(x)$ is the chain of $x$ prefixed with one step, so origins match; and every $y \in F_E$ has a chain with at least one step (its origin lies in $E$), so $y = f(x)$ with $x \in E_E$. The same argument gives bijections $f \colon E_\infty \to F_\infty$ and $g \colon F_F
\to E_F$. Gluing,

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

is a bijection from $E$ onto $F = F_E \cup F_\infty \cup F_F$: it is bijective piecewise, and the three target pieces are disjoint. ∎

**Example 1.11.**

$\intoo{0}{1}$ and $\intcc{0}{1}$ are [equipotent](#def-b2-structures-countable): the identity injects one way, $x \mapsto \frac{x + 1}{3}$ the other; the theorem manufactures the (necessarily discontinuous) bijection. Likewise $\R$, $\intoo{0}{1}$ (via $\tanh$-type bijections) and $\mathcal{P}(\N)$ (binary expansions, [Exercise 1.3](#exo-b2-structures-3)) are all [equipotent](#def-b2-structures-countable): “the cardinality of the continuum”.

**Example 1.12 (The segment and the square).**

$\intcc{0}{1}$ and $\intcc{0}{1}^2$ are [equipotent](#def-b2-structures-countable) — dimension is invisible to cardinality. One injection is trivial: $x
\mapsto (x, 0)$. For the other, send $(x, y)$ to the real whose decimal digits interleave those of $x$ and $y$,

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

choosing for each coordinate the expansion that does not end in all $9$’s: with that convention the digits of the image determine those of $x$ and $y$, so the map is injective (it need not be surjective — images never have, say, odd-position digits eventually $9$ — and that is fine). Cantor–Bernstein ([Theorem 1.10](#thm-b2-structures-cantorbernstein)) assembles a genuine bijection. Continuity, of course, is hopeless: a continuous bijection between them is impossible — the metric chapters explain why (connectedness distinguishes the line from the plane, [Chapter 4](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#ch-b2-metric)).

## 1.3 Groups

**Definition 1.13 (Generated subgroup; order).**

Let $G$ be a group and $A \subseteq G$. The subgroup *generated* by $A$, written $\langle A \rangle$, is the smallest subgroup containing $A$ — concretely, all finite products of elements of $A$ and their inverses. A group is *cyclic* when generated by one element: $\langle a\rangle = \{a^k : k \in \Z\}$. The *order* of $a \in G$ is $\operatorname{ord}(a) = \abs{\langle a \rangle}$ (possibly infinite); when finite, it is the least $n \geq 1$ with $a^n = e$, and $a^k = e \iff \operatorname{ord}(a) \mid k$.

**Proof of the order characterization.** If some $a^m = e$ with $m \geq 1$, let $n \geq 1$ be least with $a^n
= e$. The elements $e, a, \dots, a^{n-1}$ are pairwise distinct ($a^{i} = a^{j}$ with $0 \leq i < j < n$ gives $a^{j-i} = e$, contradicting minimality), and every $a^k$ reduces to one of them by Euclidean division $k = nq + r$: $\langle a\rangle$ has exactly $n$ elements, and $a^k = a^r = e \iff r = 0 \iff n \mid k$. If no power is trivial, all $a^k$ ($k \in \Z$) are distinct (same division argument) and the [order](#def-b2-structures-generated) is infinite. ∎

**Theorem 1.14 (Lagrange).**

Let $G$ be a finite group and $H$ a subgroup. Then $\abs H$ divides $\abs G$. In particular the [order](#def-b2-structures-generated) of every element divides $\abs G$, and $a^{\abs G} = e$ for all $a \in G$.

**Proof.** The relation $x \sim y \iff x^{-1}y \in H$ is an equivalence (reflexive: $e \in H$; symmetric: inverses; transitive: products). The class of $x$ is the *left coset* $xH = \{xh : h \in H\}$, and $h \mapsto xh$ is a bijection $H \to xH$ (inverse $y \mapsto
x^{-1}y$): all classes have $\abs H$ elements. Classes partition $G$ (the general partition theorem of the Year 1 volume), so $\abs G =
\abs H \times (\text{number of cosets})$. For an element: apply this to $H = \langle a\rangle$; then $a^{\abs G} = (a^{\operatorname{ord}
a})^{\abs G / \operatorname{ord} a} = e$. ∎

**Example 1.15 (Cosets in action: A3A_3A3​ inside S3\mathfrak{S}_3S3​).**

Take $G = \mathfrak{S}_3$ ([order](#def-b2-structures-generated) $6$) and $H = A_3 =
\{\mathrm{id},\ (1\,2\,3),\ (1\,3\,2)\}$. The left cosets are

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

two classes of three elements partitioning $G$, exactly as the count $\abs G = \abs H \times (\text{number of cosets})$ demands — and visibly the partition into even and odd permutations. Note $(1\,3)H = (1\,2)H$ although $(1\,3) \neq
(1\,2)$: cosets are *classes*, not labelled by their representatives, and $x^{-1}y \in H$ is the only legitimate comparison. This two-class picture is the general one for the signature: $A_n$ and its lone companion coset split $\mathfrak{S}_n$ in half, which is how the weekend problem counts reachable puzzle positions.

**Example 1.16.**

Two immediate dividends. *Groups of prime [order](#def-b2-structures-generated) are [cyclic](#def-b2-structures-generated):* if $\abs G = p$ is prime and $a \neq e$, then $\operatorname{ord}(a)$ divides $p$ and is not $1$, so it is $p$: $\langle a\rangle = G$. *The subgroup lattice of $\Z/12\Z$:* by [Proposition 1.17](#prop-b2-structures-cyclic) below, there is exactly one subgroup per divisor of $12$ — [orders](#def-b2-structures-generated) $1, 2, 3, 4, 6, 12$, [generated](#def-b2-structures-generated) respectively by $\overline 0$, $\overline 6$, $\overline
4$, $\overline 3$, $\overline 2$, $\overline 1$. The closing caution: the *converse* of Lagrange fails in general — $A_4$ has [order](#def-b2-structures-generated) $12$ but no subgroup of [order](#def-b2-structures-generated) $6$, as we prove in this chapter’s weekend problem ([Problem 1.1](#pb-b2-structures-1), question 14). Lagrange restricts the possible [orders](#def-b2-structures-generated); it does not promise them.

![The subgroup lattice of ℤ/12ℤ: one subgroup per divisor of 12 (), with an edge when one contains the other with prime index. Inclusions run against divisibility of the generator: 4 ⊂eq 2 because 4 is a multiple of 2.](https://one-course.com/images/onecourse/chapters/math-4/b2-structures/fig-36c911b182ac.svg)

*The subgroup lattice of $\Z/12\Z$: one subgroup per divisor of $12$ ([Proposition 1.17](#prop-b2-structures-cyclic)), with an edge when one contains the other with prime index. Inclusions run *against* divisibility of the generator: $\langle\overline
4\rangle \subseteq \langle\overline2\rangle$ because $4$ is a multiple of $2$.*

**Proposition 1.17 (Cyclic groups).**

Let $G = \langle a \rangle$ be [cyclic](#def-b2-structures-generated) of [order](#def-b2-structures-generated) $n$.

1. $G$ is isomorphic to $(\Z/n\Z, +)$ , via $\overline k \mapsto  a^k$ .
2. Every subgroup of $G$ is [cyclic](#def-b2-structures-generated) ; for each divisor $d \mid n$ there is exactly one subgroup of [order](#def-b2-structures-generated) $d$ , namely $\langle  a^{n/d}\rangle$ .
3. $a^k$ generates $G$ if and only if $\gcd(k, n) = 1$ : $G$ has $\varphi(n)$ generators (Euler’s function).

**Proof.** (1) The map $k \mapsto a^k$ from $\Z$ onto $G$ is compatible with congruence mod $n$ ($a^{k} = a^{k'} \iff n \mid k - k'$, by the [order](#def-b2-structures-generated) characterization); the universal property ([Definition 1.3](#def-b2-structures-quotient)) yields a well-defined bijective morphism from $\Z/n\Z$.

(2) Let $H \leq G$ be nontrivial and $m$ least $\geq 1$ with $a^m \in
H$. Euclidean division shows $H = \langle a^m\rangle$ (for $a^k \in
H$: $k = mq + r$ forces $a^r \in H$, so $r = 0$), and $m \mid n$ (divide $n$ by $m$: $a^{n \bmod m} \in H$). Then $\abs H = n/m$; taking $m = n/d$ realizes each divisor $d$. Uniqueness: any subgroup of [order](#def-b2-structures-generated) $d$ is, by the above, of the form $\langle a^m \rangle$ with $n/m = d$ — so $m = n/d$ is forced and the subgroup is determined.

(3) We claim $\operatorname{ord}(a^k) = \frac{n}{\gcd(k, n)}$. Write $d = \gcd(k, n)$. For any $m \geq 1$, the [order](#def-b2-structures-generated) characterization of [Definition 1.13](#def-b2-structures-generated) gives the chain of equivalences

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

the last step by Gauss’s lemma, since $\frac nd$ and $\frac kd$ are coprime. The least such $m$ is $\frac nd$: $\operatorname{ord}(a^k) = \frac n{\gcd(k,n)}$, which equals $n$ iff $\gcd(k, n) = 1$. There are $\varphi(n)$ such classes $k$ modulo $n$. ∎

## 1.4 The symmetric group

**Definition 1.18.**

$\mathfrak{S}_n$ is the group of permutations of $\intint{1}{n}$ ([order](#def-b2-structures-generated) $n!$). A *cycle* $(a_1\,a_2\,\cdots\,a_k)$ maps $a_1 \mapsto a_2 \mapsto \dots \mapsto a_k \mapsto a_1$ and fixes everything else; $k$ is its *length*, a $2$-cycle is a *transposition*. Two cycles are *disjoint* when their supports (non-fixed points) are.

**Theorem 1.19 (Cycle decomposition).**

Every permutation $\sigma \neq \mathrm{id}$ is a product of pairwise disjoint [cycles](#def-b2-structures-sn), uniquely up to the order of the factors. Disjoint [cycles](#def-b2-structures-sn) commute, and $\operatorname{ord}(\sigma)$ is the lcm of the lengths.

**Proof.** Consider the “orbit” relation on the support of $\sigma$: $x \sim y$ iff $y = \sigma^k(x)$ for some $k \in \Z$ — an equivalence relation. Each class $\{x, \sigma(x), \dots, \sigma^{k-1}(x)\}$ (finite, so the iterates [cycle](#def-b2-structures-sn) back — the first repetition must return to $x$ by injectivity) carries the [cycle](#def-b2-structures-sn) $(x\ \sigma(x)\
\cdots\ \sigma^{k-1}(x))$, and $\sigma$ is the product of these [cycles](#def-b2-structures-sn): on each orbit, only the corresponding [cycle](#def-b2-structures-sn) acts. Uniqueness: any [disjoint-cycle](#def-b2-structures-sn) factorization reproduces exactly the orbits (the [cycle](#def-b2-structures-sn) through $x$ must be $(x\ \sigma(x)\ \cdots)$). Disjoint [cycles](#def-b2-structures-sn) commute since they move disjoint points; the [order](#def-b2-structures-generated) statement follows because $\sigma^m = \mathrm{id}$ iff each [cycle](#def-b2-structures-sn)’s $m$-th power is (disjointness), iff each length divides $m$. ∎

**Example 1.20 (Cycle type as a census).**

How many permutations of $\mathfrak{S}_9$ have the [cycle](#def-b2-structures-sn) type $(4, 3, 2)$ — one $4$-cycle, one $3$-cycle, one [transposition](#def-b2-structures-sn)? Choose the supports and the cyclic orders:

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

list the nine symbols in a row ($9!$ ways), bracket the first four, next three, last two into [cycles](#def-b2-structures-sn), and divide by the rotations inside each bracket ($4$, $3$ and $2$ of them) which give the same permutation. (Distinct [cycle](#def-b2-structures-sn) *lengths* here, so no further division; equal lengths would also require dividing by the permutations of the equal brackets.) Every such permutation has [order](#def-b2-structures-generated) $\operatorname{lcm}(4,3,2) = 12$ and signature $(-1)^3(-1)^2(-1)^1 = +1$ ([Theorem 1.19](#thm-b2-structures-cycles) and the signature theorem below). One partition of $9$, one conjugacy class, one census — the combinatorics of $\mathfrak{S}_n$ is the arithmetic of partitions.

**Theorem 1.21 (Signature).**

There is exactly one group morphism $\varepsilon \colon
\mathfrak{S}_n \to \{\pm 1\}$ (for $n \geq 2$) taking the value $-1$ on [transpositions](#def-b2-structures-sn): the *signature*. Moreover $\varepsilon(\sigma) = (-1)^{I(\sigma)}$ where $I(\sigma)$ is the number of *inversions* (pairs $i < j$ with $\sigma(i) >
\sigma(j)$), a $k$-cycle has signature $(-1)^{k-1}$, and the *alternating group* $A_n = \ker\varepsilon$ has [order](#def-b2-structures-generated) $\frac{n!}{2}$.

**Proof.** *Existence.* For $\sigma \in \mathfrak{S}_n$ set

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

The factors’ absolute values multiply to $1$ (the unordered pairs $\{\sigma(i), \sigma(j)\}$ run over all pairs), so $\varepsilon(\sigma) = (-1)^{I(\sigma)} \in \{\pm1\}$. Morphism: for $\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),
$$

the middle product being $\varepsilon(\sigma)$ after reindexing by the pairs $\{\tau(i), \tau(j)\}$ (each unordered pair appears once, and numerator and denominator flip sign together). A [transposition](#def-b2-structures-sn) $\tau = (a\,b)$ with $a < b$ has an odd number of inversions; counted exactly: the inverted pairs $(i, j)$, $i < j$, with $\tau(i) > \tau(j)$ are

$$
(a, j) \ \text{for } a < j < b, \qquad
(i, b) \ \text{for } a < i < b, \qquad
(a, b) \ \text{itself},
$$

that is $(b - a - 1) + (b - a - 1) + 1 = 2(b - a) - 1$ of them, odd. (Alternatively: check $(1\,2)$ directly, with one inversion, and conjugate — conjugates have equal signature since $\varepsilon$ is a morphism to an abelian group.) Hence $\varepsilon((a\,b)) = (-1)^{2(b-a)-1} = -1$.

*Uniqueness.* [Transpositions](#def-b2-structures-sn) generate $\mathfrak{S}_n$ (any [cycle](#def-b2-structures-sn) $(a_1\cdots a_k) = (a_1\,a_k)(a_1\,a_{k-1})\cdots(a_1\,a_2)$, and [Theorem 1.19](#thm-b2-structures-cycles) finishes); a morphism to $\{\pm1\}$ is determined by its values on generators.

*Consequences.* The [cycle](#def-b2-structures-sn) identity above writes a $k$-cycle as $k - 1$ [transpositions](#def-b2-structures-sn): signature $(-1)^{k-1}$. $A_n$: the morphism $\varepsilon$ is surjective ([transpositions](#def-b2-structures-sn) exist for $n \geq 2$), and the two “cosets” $A_n$ and $(1\,2)A_n$ are [equipotent](#def-b2-structures-countable) and partition $\mathfrak{S}_n$ (Lagrange’s argument): $\abs{A_n} =
\frac{n!}{2}$. ∎

**Example 1.22.**

$\sigma = \begin{pmatrix} 1&2&3&4&5&6\\ 3&6&5&4&1&2 \end{pmatrix}
= (1\,3\,5)(2\,6)$: [order](#def-b2-structures-generated) $\operatorname{lcm}(3,2) = 6$, signature $(-1)^{2}\cdot(-1)^{1} = -1$. The signature is the fastest parity check on shuffles — and the engine of the determinant in [Chapter 2](https://one-course.com/books/math/4/en/chapter/2-linear-algebra#ch-b2-linalg).

**Example 1.23 (Three roads to one sign).**

Let $\sigma \in \mathfrak{S}_5$ send $1, 2, 3, 4, 5$ to $3, 5, 4,
1, 2$. *Via [cycles](#def-b2-structures-sn):* $1 \mapsto 3 \mapsto 4 \mapsto 1$ and $2
\mapsto 5 \mapsto 2$, so $\sigma = (1\,3\,4)(2\,5)$ and $\varepsilon(\sigma) = (-1)^{2}(-1)^{1} = -1$. *Via inversions:* in the value list $3, 5, 4, 1, 2$ the out-of-order pairs are $(3,1)$, $(3,2)$, $(5,4)$, $(5,1)$, $(5,2)$, $(4,1)$, $(4,2)$: seven of them, and $(-1)^7 = -1$. *Via [transpositions](#def-b2-structures-sn):* $\sigma = (1\,4)(1\,3)(2\,5)$, three factors, $(-1)^3 = -1$. Three computations, one parity: the uniqueness in [Theorem 1.21](#thm-b2-structures-signature) guarantees that no bookkeeping scheme can ever make them disagree — which is exactly what makes $\varepsilon$ usable as an invariant (see the weekend problem).

**Remark 1.24 (Where the signature goes from here).**

The signature is the seed of three later harvests: it builds the determinant and its product rule in [Chapter 2](https://one-course.com/books/math/4/en/chapter/2-linear-algebra#ch-b2-linalg); it powers parity invariants for combinatorial puzzles (this chapter’s weekend problem solves the fifteen puzzle with it); and the alternating groups $A_n$ it defines become central in the Year 3 volume, where their simplicity for $n \geq 5$ explains why degree-$5$ equations have no solution in radicals.

## 1.5 Rings, ideals, quotients

**Definition 1.25 (Ideal).**

Let $A$ be a commutative ring. An *ideal* $I
\subseteq A$ is an additive subgroup such that $a x \in I$ for all $a \in A$, $x \in I$. Kernels of ring morphisms are ideals; $I = A$ iff $1 \in I$ iff $I$ contains a unit. The ideal *[generated](#def-b2-structures-generated)* by $x$ is $xA = \{xa\}$ (a *principal* ideal).

**Theorem 1.26 (Ideals of Z\ZZ and of K[X]K[X]K[X]).**

Every [ideal](#def-b2-structures-ideal) of $\Z$ is $n\Z$ for a unique $n \in \N$; every [ideal](#def-b2-structures-ideal) of $K[X]$ ($K$ a field) is $P\,K[X]$ for a unique monic (or zero) $P$. Consequently gcd’s exist in both rings with Bézout relations: $x\Z +
y\Z = \gcd(x,y)\Z$, and likewise for polynomials.

**Proof.** For $\Z$ this was the subgroup theorem of the Year 1 volume (an [ideal](#def-b2-structures-ideal) is in particular a subgroup, and $n\Z$ is an [ideal](#def-b2-structures-ideal)). For $K[X]$: let $I \neq \{0\}$ be an [ideal](#def-b2-structures-ideal) and $P \in I$ nonzero of minimal degree, normalized monic. For $F \in I$, Euclidean division $F = PQ + R$ gives $R = F - PQ \in I$ with $\deg R < \deg P$: minimality forces $R
= 0$, so $I = P\,K[X]$. Uniqueness: two monic generators divide each other. The Bézout statements are the equality of the [ideal](#def-b2-structures-ideal) $x\Z +
y\Z$ (resp. its polynomial analogue) with the principal [ideal](#def-b2-structures-ideal) of the gcd — the very definition of gcd used in Year 1, now recognized as a statement about [ideals](#def-b2-structures-ideal). ∎

**Example 1.27 (A polynomial gcd, two ways).**

Compute $\gcd(X^3 - 1,\ X^2 - 1)$ in $\Q[X]$. *By Euclid:*

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

so the gcd is $X - 1$, and back-substitution gives the Bézout relation

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

*By [ideals](#def-b2-structures-ideal):* the [ideal](#def-b2-structures-ideal) $(X^3 - 1)\Q[X] + (X^2 - 1)\Q[X]$ is principal ([Theorem 1.26](#thm-b2-structures-principal)); it contains $X -
1$ (the display) and is contained in $(X - 1)\Q[X]$ (both generators vanish at $1$, hence are multiples of $X - 1$): the monic generator is $X - 1$. The closing insight: the [ideal](#def-b2-structures-ideal) viewpoint identifies the gcd *without dividing* — common roots locate the [ideal](#def-b2-structures-ideal), and Euclid merely certifies it.

**Definition 1.28 (Quotient ring Z/nZ\Z/n\ZZ/nZ, revisited).**

For an [ideal](#def-b2-structures-ideal) $I$ of $A$, the relation $x \sim y \iff x - y \in I$ is an equivalence compatible with $+$ and $\times$; the [quotient set](#def-b2-structures-quotient) $A/I$ inherits a ring structure — the *quotient ring* — making $\pi \colon A \to A/I$ a morphism with kernel $I$. For $A = \Z$, $I = n\Z$ this is the $\Z/n\Z$ of the Year 1 volume, now with its universal property: any morphism killing $I$ factors through $A/I$.

**Theorem 1.29 (Chinese remainder theorem, ring form).**

If $\gcd(m, n) = 1$, the map

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

is a ring isomorphism. Consequently $\varphi(mn) = \varphi(m)\varphi(n)$ for coprime $m, n$, and

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

**Proof.** The map is a well-defined ring morphism (compatibilities are immediate). Injectivity: $x \equiv 0$ mod $m$ and mod $n$ with $\gcd(m,n) = 1$ forces $mn \mid x$ (Gauss). Surjectivity: both sides have $mn$ elements, so injectivity suffices (finite equal cardinalities) — or explicitly: from a Bézout relation $um +
vn = 1$, the class of

$$
x = b\,um + a\,vn
$$

maps to $(a \bmod m,\ b \bmod n)$, since $vn = 1 - um \equiv 1
\pmod m$ makes $x \equiv a \pmod m$, and symmetrically mod $n$ — the recipe used numerically in [Example 1.30](#ex-b2-structures-crtinverse). Units correspond to pairs of units (a product ring’s units are the pairs of units), so $\varphi(mn) =
\varphi(m)\varphi(n)$. For a prime power, $\varphi(p^k) = p^k -
p^{k-1}$ (the non-units mod $p^k$ are the multiples of $p$); multiplicativity assembles the product formula. ∎

**Example 1.30 (Inverting the Chinese isomorphism).**

Take $m = 8$, $n = 9$. The inverse of the isomorphism is made explicit by the two *idempotents*: seek $u \equiv 1 \pmod 8$, $u \equiv 0 \pmod 9$ and $v \equiv 0 \pmod 8$, $v \equiv 1 \pmod
9$. From $u = 9k \equiv 1 \pmod 8$: $k \equiv 1$, so $u = 9$; from $v = 8k \equiv 1 \pmod 9$: $-k \equiv 1$, $k \equiv 8$, so $v =
64$. Then the class of $x = 9a + 64b$ modulo $72$ is the unique solution of $x \equiv a \pmod 8$, $x \equiv b \pmod 9$: for $a =
3$, $b = 5$ one gets $27 + 320 = 347 \equiv 59 \pmod{72}$ — exactly the intermediate value found by substitution in [Exercise 1.8](#exo-b2-structures-8). The closing insight: $u$ and $v$ satisfy $u + v \equiv 1$, $uv \equiv 0$, $u^2 \equiv u$, $v^2
\equiv v$ modulo $72$; they are the images of $(1, 0)$ and $(0,
1)$, and every Chinese decomposition is at bottom a decomposition of $1$ into orthogonal idempotents.

**Theorem 1.31 (Euler; Fermat revisited).**

The units of $\Z/n\Z$ form a group of [order](#def-b2-structures-generated) $\varphi(n)$; hence for $\gcd(a, n) = 1$:

$$
a^{\varphi(n)} \equiv 1 \pmod n
\qquad (\text{Euler's theorem}),
$$

and Fermat’s little theorem is the case $n = p$ prime, now one line from Lagrange.

**Proof.** The invertible classes are exactly those of integers coprime to $n$ (Year 1 volume): $\varphi(n)$ of them, forming a group under multiplication. Lagrange ([Theorem 1.14](#thm-b2-structures-lagrange)): every element to the power of the group [order](#def-b2-structures-generated) is the identity. ∎

**Example 1.32 (A unit group without a generator).**

The group $(\Z/15\Z)^*$ has $\varphi(15) = \varphi(3)\varphi(5)
= 8$ elements. Is it [cyclic](#def-b2-structures-generated)? Compute [orders](#def-b2-structures-generated) using the Chinese isomorphism $(\Z/15\Z)^* \simeq (\Z/3\Z)^* \times (\Z/5\Z)^*$ (a unit mod $15$ is a pair of units): the factors have [orders](#def-b2-structures-generated) $2$ and $4$, so every element’s [order](#def-b2-structures-generated) divides $\operatorname{lcm}(2, 4) = 4 < 8$ — no element generates. Concretely:

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

[orders](#def-b2-structures-generated) $4, 2, 4, 2, 2$ and never $8$. Contrast with [Exercise 1.10](#exo-b2-structures-10): $(\Z/p\Z)^*$ *is* [cyclic](#def-b2-structures-generated) for $p$ prime, because there the unit group sits inside a field. Euler’s theorem still applies with exponent $\varphi(15) = 8$, but the true universal exponent here is $4$ — Euler is an upper bound, not always the sharp one.

**Definition 1.33 (Algebra).**

A *$K$-algebra* is a $K$-vector space $A$ with a ring structure whose multiplication is $K$-bilinear. Examples: $K[X]$, $\mathcal{M}_n(K)$, $\mathcal{L}(E)$, function spaces $\mathcal{F}(X, K)$, $\C$ as an $\R$-algebra. Morphisms of algebras are linear ring morphisms; the *evaluation* $P \mapsto P(u)$ from $K[X]$ to $\mathcal{L}(E)$ (or $\mathcal{M}_n(K)$) is the central example, driving [Chapter 3](https://one-course.com/books/math/4/en/chapter/3-reduction-of-endomorphisms#ch-b2-reduction).

**Example 1.34 (An evaluation morphism and its kernel).**

Take $A = \begin{pmatrix}0 & 1\\ 0 & 0\end{pmatrix}$ and the evaluation $\varepsilon_A \colon \R[X] \to \mathcal{M}_2(\R)$, $P \mapsto P(A)$. Since $A^2 = 0$,

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

(only the constant and linear terms of $P$ survive). Hence $\ker\varepsilon_A = \{P : P(0) = P'(0) = 0\} = X^2\,\R[X]$: a principal [ideal](#def-b2-structures-ideal), exactly as [Theorem 1.26](#thm-b2-structures-principal) predicts, [generated](#def-b2-structures-generated) by the monic $X^2$ of least degree in the kernel — the *minimal polynomial* of $A$, star of [Chapter 3](https://one-course.com/books/math/4/en/chapter/3-reduction-of-endomorphisms#ch-b2-reduction). The image is the two-dimensional commutative [algebra](#def-b2-structures-algebra) $\{aI + bA\}$: evaluation morphisms shrink the infinite-dimensional $\R[X]$ onto small, computable [algebras](#def-b2-structures-algebra).

**Remark 1.35 (Perspectives: three melodies to listen for).**

Three structural ideas from this chapter recur throughout the volume, each time in heavier orchestration. *Factorization through a quotient* ([Definition 1.3](#def-b2-structures-quotient)): it builds $\Z/n\Z$ here, defines maps on solution sets of linear systems in [Chapter 2](https://one-course.com/books/math/4/en/chapter/2-linear-algebra#ch-b2-linalg), and silently underlies every “well defined on classes” argument. *Invariants*: the signature is a morphism to $\{\pm1\}$ that no legal move can dodge — the same logic gives the determinant’s product rule ([Chapter 2](https://one-course.com/books/math/4/en/chapter/2-linear-algebra#ch-b2-linalg)), the trace’s similarity invariance, and the conserved quantities of [Chapter 16](https://one-course.com/books/math/4/en/chapter/16-differential-equations#ch-b2-diffeq). *Counting against a structure*: Lagrange counts through cosets, dimension counts through bases ([Chapter 2](https://one-course.com/books/math/4/en/chapter/2-linear-algebra#ch-b2-linalg)), multiplicity counts through polynomial degrees ([Chapter 3](https://one-course.com/books/math/4/en/chapter/3-reduction-of-endomorphisms#ch-b2-reduction)); whenever a bound looks miraculous, some partition or grading is doing the counting.

**Remark 1.36 (Common pitfalls).**

Four classics. (i) A map on a quotient must be checked *well defined*: “$\overline x \mapsto$ (formula on $x$)” is legitimate only if the formula is constant on classes — the compatibility of [Definition 1.3](#def-b2-structures-quotient), not a formality. (ii) $\operatorname{ord}(ab) =
\operatorname{lcm}(\operatorname{ord}a, \operatorname{ord}b)$ is *false* in general, even for commuting elements ($a$ and $a^{-1}$); [Exercise 1.4](#exo-b2-structures-4) gives the correct coprime-and-commuting statement, and disjoint [cycles](#def-b2-structures-sn) the correct permutation version. (iii) [Countability](#def-b2-structures-countable) survives [countable](#def-b2-structures-countable) *unions* and finite *products*, but not [countable](#def-b2-structures-countable) products: $\{0,1\}^{\N}$ is uncountable ([Exercise 1.3](#exo-b2-structures-3)) although each factor has two elements. (iv) Cantor–Bernstein needs only injections both ways, but the bijection it builds is usually discontinuous and non-explicit — do not expect a formula ([Example 1.11](#ex-b2-structures-cbexample)).

**Remark 1.37 (Where this chapter is used).**

Almost everywhere. The signature builds determinants ([Chapter 2](https://one-course.com/books/math/4/en/chapter/2-linear-algebra#ch-b2-linalg)); the evaluation morphism $P \mapsto P(u)$ and the principal [ideals](#def-b2-structures-ideal) of $K[X]$ produce minimal polynomials and the kernel decompositions of [Chapter 3](https://one-course.com/books/math/4/en/chapter/3-reduction-of-endomorphisms#ch-b2-reduction); [countability](#def-b2-structures-countable) is the stage on which [Chapter 21](https://one-course.com/books/math/4/en/chapter/21-probability-on-countable-spaces#ch-b2-proba) performs (probability on [countable](#def-b2-structures-countable) spaces) and the reason topology keeps producing [countable](#def-b2-structures-countable) dense sets ([Chapter 4](https://one-course.com/books/math/4/en/chapter/4-topology-of-metric-spaces#ch-b2-metric)). The quotient construction $A/I$ is redeployed in the Year 3 volume to build fields $K[X]/(P)$ and, from them, Galois theory: the universal property proved here is used there word for word.

## 1.6 Exercises

**Exercise 1.1 ★.**

Which of the following sets are [countable](#def-b2-structures-countable)? The set of finite subsets of $\N$; the set of *all* subsets of $\N$; $\R \setminus \Q$; the set of polynomials with rational coefficients; the set of sequences of $0$’s and $1$’s that are eventually zero.

**Solution of Exercise 1.1.**

*Finite subsets of $\N$:* [countable](#def-b2-structures-countable) — the set of subsets of $\intint{0}{n}$ is finite, and the finite subsets form the [countable](#def-b2-structures-countable) union over $n$ of these ([Proposition 1.6](#prop-b2-structures-countablestable) (3)); infinite since it contains all singletons.

*All subsets of $\N$:* not [countable](#def-b2-structures-countable), by Cantor’s theorem ([Theorem 1.9](#thm-b2-structures-cantor) (1) with $E = \N$).

*$\R \setminus \Q$:* not [countable](#def-b2-structures-countable) — otherwise $\R = \Q \cup
(\R\setminus\Q)$ would be a union of two [countable sets](#def-b2-structures-countable), contradicting [Theorem 1.9](#thm-b2-structures-cantor) (2).

*Polynomials over $\Q$:* [countable](#def-b2-structures-countable) — the polynomials of degree $\leq n$ inject into $\Q^{n+1}$ (finite products of [countable sets](#def-b2-structures-countable)), and take the union over $n$.

*Eventually-zero binary sequences:* [countable](#def-b2-structures-countable) — they biject with finite subsets of $\N$ (the support).

**Exercise 1.2 ★.**

In $\mathfrak{S}_7$, let $\sigma = (1\,4\,2\,6)(3\,5)$ and $\tau =
(2\,3\,7)$. Compute $\sigma\tau$ and $\tau\sigma$ in [disjoint-cycle](#def-b2-structures-sn) form, the [orders](#def-b2-structures-generated) and signatures of all four permutations, and $\sigma^{2026}$.

**Solution of Exercise 1.2.**

Compute element by element, applying the right factor first. $\sigma\tau$ sends $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),
$$

a $7$-cycle. Likewise $\tau\sigma$ sends $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),
$$

also a $7$-cycle (as expected: $\sigma\tau$ and $\tau\sigma$ are conjugate, hence share their [cycle](#def-b2-structures-sn) type).

[Orders](#def-b2-structures-generated) and signatures: $\sigma$ has [cycle](#def-b2-structures-sn) type $(4,2)$: [order](#def-b2-structures-generated) $\operatorname{lcm}(4,2) = 4$, signature $(-1)^3(-1)^1 = +1$; $\tau$ is a $3$-cycle: [order](#def-b2-structures-generated) $3$, signature $+1$; both products are $7$-cycles: [order](#def-b2-structures-generated) $7$, signature $(-1)^6 = +1$.

$\sigma^{2026}$: $2026 = 4 \times 506 + 2$, so $\sigma^{2026} =
\sigma^2 = (1\,2)(4\,6)$ (square the $4$-cycle; the [transposition](#def-b2-structures-sn) squares away).

**Exercise 1.3 ★.**

Construct explicit injections showing that $\mathcal{P}(\N)$, $\intcc{0}{1}$ and the set $\{0,1\}^{\N}$ of binary sequences are pairwise [equipotent](#def-b2-structures-countable) *(binary expansions both ways; Cantor–Bernstein absorbs the double-representation nuisance)*.

**Solution of Exercise 1.3.**

$\{0,1\}^{\N} \to \mathcal{P}(\N)$: a sequence maps to its support — a bijection (indicator functions), no theorem needed.

$\{0,1\}^{\N} \to \intcc{0}{1}$: the base-$3$ map $(a_n) \mapsto
\sum 2a_n 3^{-n-1}$ is injective (two distinct sequences differ first at rank $N$; the tails cannot compensate a gap of $2\cdot
3^{-N-1}$, since $\sum_{n > N} 2\cdot 3^{-n-1} = 3^{-N-1} <
2\cdot3^{-N-1}$).

$\intcc{0}{1} \to \{0,1\}^{\N}$: binary expansion, choosing (say) the expansion not ending in all $1$’s: injective.

By Cantor–Bernstein ([Theorem 1.10](#thm-b2-structures-cantorbernstein)) applied to the last two injections, $\intcc{0}{1}$ and $\{0,1\}^{\N}$ are [equipotent](#def-b2-structures-countable), hence all three sets are.

**Exercise 1.4 ★.**

Let $G$ be a group and $a, b \in G$ commuting elements of finite coprime [orders](#def-b2-structures-generated) $m$ and $n$. Prove that $\operatorname{ord}(ab) =
mn$. Show by an example in $\mathfrak{S}_3$ that commutation is essential.

**Solution of Exercise 1.4.**

Let $c = ab = ba$ and $d = \operatorname{ord}(c)$. First $c^{mn} =
a^{mn} b^{mn} = e$ (commutation allows splitting the power), so $d
\mid mn$. Conversely $c^d = e$ gives $a^d = b^{-d}$; this element lies in $\langle a\rangle \cap \langle b\rangle$, a subgroup whose [order](#def-b2-structures-generated) divides both $m$ and $n$ (Lagrange in each [cyclic group](#def-b2-structures-generated)), hence is trivial: $a^d = b^d = e$, so $m \mid d$ and $n \mid d$, and by coprimality $mn \mid d$. Hence $d = mn$.

In $\mathfrak{S}_3$: take $a = (1\,2)$ ([order](#def-b2-structures-generated) $2$) and $b =
(1\,2\,3)$ ([order](#def-b2-structures-generated) $3$), coprime [orders](#def-b2-structures-generated), which do not commute: $ab =
(2\,3)$ has [order](#def-b2-structures-generated) $2 \neq 6$ — indeed $\mathfrak{S}_3$ has no element of [order](#def-b2-structures-generated) $6$. Commutation is essential.

**Exercise 1.5 ★★.**

Let $G$ be a finite group of even [order](#def-b2-structures-generated). Prove that $G$ contains an element of [order](#def-b2-structures-generated) $2$. *(Pair each element with its inverse; count the self-paired ones.)*

**Solution of Exercise 1.5.**

Pair every $x \in G$ with $x^{-1}$. The pairs $\{x, x^{-1}\}$ with $x \neq x^{-1}$ have two elements and partition their union; the remaining elements are exactly those with $x = x^{-1}$, i.e. $x^2 =
e$. Since $\abs G$ is even and the two-element pairs cover an even number of elements, the set $\{x : x^2 = e\}$ has even cardinality; it contains $e$, so it contains at least one other element $x \neq
e$ — an element of [order](#def-b2-structures-generated) $2$.

**Exercise 1.6 ★★.**

Prove that $A_n$ ($n \geq 3$) is [generated](#def-b2-structures-generated) by the $3$-cycles. *(A product of two [transpositions](#def-b2-structures-sn) is a $3$-cycle or a product of two $3$-cycles.)*

**Solution of Exercise 1.6.**

Every element of $A_n$ is a product of an even number of [transpositions](#def-b2-structures-sn) ([Theorem 1.21](#thm-b2-structures-signature): decompose into [transpositions](#def-b2-structures-sn); the count is even since the signature is $+1$). It suffices to write each product of two [transpositions](#def-b2-structures-sn) with $3$-cycles:

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

(check by evaluation), and $(a\,b)(a\,b) = \mathrm{id}$. So the $3$-cycles generate $A_n$.

**Exercise 1.7 ★★.**

Determine all group morphisms: from $(\Q, +)$ to $(\Z, +)$; from $(\Z/n\Z, +)$ to $(\Z/m\Z, +)$ *(count them: $\gcd(m,n)$)*; from $(\Q, +)$ to $(\Q_+^*, \times)$.

**Solution of Exercise 1.7.**

*$(\Q,+) \to (\Z,+)$:* only the zero morphism. For any $x$ and every $n \geq 1$, $f(x) = n f\bigl(\frac xn\bigr)$ is divisible by $n$ in $\Z$; the only integer divisible by every $n$ is $0$, so $f(x) = 0$ for all $x$.

*$(\Z/n\Z, +) \to (\Z/m\Z, +)$:* a morphism is determined by $c = f(\overline 1)$, which must satisfy $n c \equiv 0 \pmod m$, i.e. $c$ is a multiple of $\frac{m}{\gcd(m,n)}$; there are $\gcd(m,n)$ such classes, and each choice does define a morphism (factor $k \mapsto kc$ through $\Z/n\Z$ by the universal property).

*$(\Q, +) \to (\Q_+^*, \times)$:* only the trivial one. If $f(x) = y$, then for every $n$, $y = f(n \cdot \frac xn) =
f(\frac xn)^n$ is an $n$-th power in $\Q_+^*$. But a rational $y \neq 1$ cannot be an $n$-th power for all $n$: some prime appears in $y$ with a nonzero exponent $v$, and $n \nmid v$ for $n > \abs
v$ (exponents of $n$-th powers are multiples of $n$, by unique factorization). Hence $f \equiv 1$.

**Exercise 1.8 ★★.**

Using the Chinese remainder theorem, compute $\varphi(360)$, find all $x$ with $x \equiv 3 \pmod 8$, $x \equiv 5 \pmod 9$ and $x
\equiv 2 \pmod 5$, and compute the last two digits of $3^{2026}$ *(Euler mod $100$; beware: work mod $4$ and mod $25$)*.

**Solution of Exercise 1.8.**

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

System: moduli $8, 9, 5$ pairwise coprime, total $360$. From $x
\equiv 3 \pmod 8$ and $x \equiv 5 \pmod 9$: $x = 3 + 8k$ with $3 +
8k \equiv 5 \pmod 9$, i.e. $-k \equiv 2$, $k \equiv -2 \equiv 7
\pmod 9$: $x \equiv 3 + 56 = 59 \pmod{72}$. Then $59 + 72\ell \equiv
2 \pmod 5$: $4 + 2\ell \equiv 2$, $2\ell \equiv 3 \equiv 8$, $\ell
\equiv 4 \pmod 5$: $x \equiv 59 + 288 = 347 \pmod{360}$.

Last two digits of $3^{2026}$: mod $4$, $3^{2026} = 9^{1013} \equiv
1$. Mod $25$: $\varphi(25) = 20$ and $2026 = 20\cdot101 + 6$, so $3^{2026} \equiv 3^6 = 729 \equiv 4 \pmod{25}$. Solve $x \equiv 1
\pmod 4$, $x \equiv 4 \pmod{25}$: $x = 4 + 25k \equiv 1 \pmod 4$ gives $k \equiv 1 \pmod 4$: $x \equiv 29 \pmod{100}$. The last two digits are $29$.

**Exercise 1.9 ★★★.**

Prove that a finite integral domain is a field. Deduce that $\Z/n\Z$ is a field iff $n$ is prime (again).

**Solution of Exercise 1.9.**

Let $A$ be a finite integral domain and $a \in A$, $a \neq 0$. The map $x \mapsto ax$ is injective ($ax = ay \implies a(x - y) = 0
\implies x = y$, no zero divisors); an injective map of a finite set to itself is surjective (Year 1 volume, the pigeonhole equivalence). So $1 = ab$ for some $b$: every nonzero element is invertible, $A$ is a field.

$\Z/n\Z$: if $n$ is prime it is an integral domain ($n \mid ab
\implies n \mid a$ or $n \mid b$, Euclid’s lemma), finite, hence a field; if $n = rs$ is composite, $\overline r\,\overline s =
\overline 0$ exhibits zero divisors.

**Exercise 1.10 ★★★.**

(A classic) Let $K$ be a field and $G$ a *finite* subgroup of $(K^*, \times)$. Prove that $G$ is [cyclic](#def-b2-structures-generated). *Hint: let $m$ be the maximal [order](#def-b2-structures-generated) among elements of $G$; show every element’s [order](#def-b2-structures-generated) divides $m$ (using [Exercise 1.4](#exo-b2-structures-4) on suitable coprime parts), so all of $G$ satisfies $x^m = 1$; count roots of $X^m - 1$.* In particular $(\Z/p\Z)^*$ is [cyclic](#def-b2-structures-generated).

**Solution of Exercise 1.10.**

Let $m = \max\{\operatorname{ord}(x) : x \in G\}$, attained at $a$.

*Claim: every $x \in G$ has [order](#def-b2-structures-generated) dividing $m$.* Suppose some $x$ has [order](#def-b2-structures-generated) $q$ with $q \nmid m$: then some prime power $p^k$ divides $q$ but not $m$. Write $m = p^j m'$ with $p \nmid m'$ and $j
< k$. The element $a^{p^j}$ has [order](#def-b2-structures-generated) $m'$; the element $x^{q/p^k}$ has [order](#def-b2-structures-generated) $p^k$; these [orders](#def-b2-structures-generated) are coprime and the two elements commute ($G \subseteq K^*$ is abelian), so by [Exercise 1.4](#exo-b2-structures-4) their product has [order](#def-b2-structures-generated) $p^k m' > p^j m'
= m$: contradicting maximality.

So all $x \in G$ satisfy $x^m = 1$: the polynomial $X^m - 1$ has at least $\abs G$ roots in the field $K$, whence $\abs G \leq m$ (a nonzero polynomial of degree $m$ has at most $m$ roots, Year 1 volume). But $m = \operatorname{ord}(a) \leq \abs G$ by Lagrange. Hence $m = \abs G$ and $\langle a \rangle$, of cardinality $m =
\abs G$, is all of $G$: [cyclic](#def-b2-structures-generated).

For $K = \Z/p\Z$: $(\Z/p\Z)^*$ is a finite subgroup of $K^*$, hence [cyclic](#def-b2-structures-generated) (of [order](#def-b2-structures-generated) $p - 1$).

**Exercise 1.11 ★★★.**

Prove that the group $(\Q, +)$ is not [cyclic](#def-b2-structures-generated), and worse: it is not even finitely [generated](#def-b2-structures-generated). Prove on the other hand that every finitely [generated](#def-b2-structures-generated) subgroup of $(\Q, +)$ is [cyclic](#def-b2-structures-generated).

**Solution of Exercise 1.11.**

*Not [cyclic](#def-b2-structures-generated):* the subgroup $\langle \frac pq\rangle$ consists of the integer multiples of $\frac pq$, all of which have denominator dividing $q$ (in lowest terms); it therefore misses $\frac{1}{2q}$. No single generator can reach the unbounded denominators of $\Q$.

*Not finitely [generated](#def-b2-structures-generated):* the subgroup [generated](#def-b2-structures-generated) by $\frac{p_1}{q_1}, \dots, \frac{p_k}{q_k}$ consists of rationals whose denominators divide $Q = q_1 \cdots q_k$ (integer combinations have denominator dividing $Q$): it misses $\frac{1}{2Q}$.

*Finitely [generated](#def-b2-structures-generated) subgroups are [cyclic](#def-b2-structures-generated):* with $Q$ as above, the subgroup $H = \langle \frac{p_1}{q_1}, \dots,
\frac{p_k}{q_k}\rangle$ is contained in $\frac{1}{Q}\Z$. The map $x
\mapsto Qx$ is an isomorphism from $\frac1Q\Z$ onto $\Z$ carrying $H$ to a subgroup of $\Z$, which is $n\Z$ for some $n$ (Year 1 volume): so $H = \frac{n}{Q}\Z$ is [cyclic](#def-b2-structures-generated), [generated](#def-b2-structures-generated) by $\frac nQ$.

**Exercise 1.12 ★★.**

(Dedekind’s criterion) Prove that every infinite set contains a [countable](#def-b2-structures-countable) subset, and deduce that a set $E$ is infinite if and only if it is [equipotent](#def-b2-structures-countable) to a proper subset of itself. *(For the direct implication, shift a [countable](#def-b2-structures-countable) subset by one step; for the converse, recall the pigeonhole principle.)*

**Solution of Exercise 1.12.**

*A [countable](#def-b2-structures-countable) subset.* Let $E$ be infinite. Construct $a_0,
a_1, a_2, \dots$ inductively: $E$ is nonempty, pick $a_0 \in E$; if $a_0, \dots, a_n$ are chosen, $E \setminus \{a_0, \dots,
a_n\}$ is nonempty ($E$ is not finite), pick $a_{n+1}$ there. The $a_n$ are pairwise distinct by construction, so $A = \{a_n : n
\in \N\}$ is a [countable](#def-b2-structures-countable) subset of $E$.

*Infinite $\implies$ [equipotent](#def-b2-structures-countable) to a proper subset.* Define $f \colon E \to E \setminus \{a_0\}$ by $f(a_n) = a_{n+1}$ and $f(x) = x$ for $x \notin A$. It is injective (the two pieces are injective with disjoint images) and surjective onto $E \setminus
\{a_0\}$: every $a_{n+1}$ is hit, every $x \notin A$ is hit. So $E$ is [equipotent](#def-b2-structures-countable) to the proper subset $E \setminus \{a_0\}$.

*Converse.* If $E$ is finite and $g \colon E \to F$ is a bijection onto $F \subseteq E$ with $F \neq E$, then $g$ is an injection of $E$ into itself that is not surjective, contradicting the pigeonhole principle (Year 1 volume: an injective self-map of a finite set is bijective). So a set [equipotent](#def-b2-structures-countable) to a proper subset is infinite.

## 1.7 Problem: The Fifteen Puzzle

The fifteen puzzle is a $4 \times 4$ tray holding fifteen sliding tiles numbered $1$ to $15$ and one empty cell; a move slides one of the tiles adjacent to the empty cell into it. In the 1890s Sam Loyd popularized the puzzle by offering $1000 to anyone who could exchange the tiles $14$ and $15$ and return every other tile to its place. Nobody ever collected, and this weekend problem proves both halves of the reason: the signature of [Theorem 1.21](#thm-b2-structures-signature) forbids Loyd’s exchange, and — the harder, constructive half — *everything* the signature allows is genuinely solvable. The full statement is the Johnson–Story theorem (1879).

![The solved configuration and Sam Loyd’s 14–15 configuration. The $1000 question: can legal slides turn the right tray into the left one?](https://one-course.com/images/onecourse/chapters/math-4/b2-structures/fig-323c5430ec90.svg)

![The solved configuration and Sam Loyd’s 14–15 configuration. The $1000 question: can legal slides turn the right tray into the left one?](https://one-course.com/images/onecourse/chapters/math-4/b2-structures/fig-be4817cc39e8.svg)

*The solved configuration and Sam Loyd’s $14$–$15$ configuration. The $1000 question: can legal slides turn the right tray into the left one?*

**Problem 1.1.**

Weekend problem — the Johnson–Story solvability theorem

Number the cells $1$ to $16$ in reading order (left to right, top to bottom), so that cell $k$ sits in row $i$ and column $j$ with $k
= 4(i - 1) + j$. Cell $16$ (bottom right) is the *home* of the empty cell; we treat the empty cell as a sixteenth tile, written $b$ and identified with the number $16$. A *configuration* is a bijection $\sigma \colon \intint1{16}
\to \intint1{16}$, cell $\mapsto$ content; the *solved* configuration is $\sigma = \mathrm{id}$. Throughout, $\varepsilon$ is the signature of [Theorem 1.21](#thm-b2-structures-signature) and two cells are *adjacent* when they share an edge of the tray.

**Part I — Configurations, moves, signatures.**

1. Justify that the configurations are exactly the elements of $\mathfrak{S}_{16}$ , so there are $16! =  20\,922\,789\,888\,000$ of them, and that the number of legal moves from a given configuration is $2$ , $3$ or $4$ , according to whether the empty cell lies in a corner, on an edge, or in the interior.
2. Let $\sigma$ be a configuration, $p = \sigma^{-1}(16)$ the cell of the blank, and $c$ a cell adjacent to $p$ . Show that sliding the tile of $c$ into $p$ produces the configuration $\sigma' = \sigma \circ \tau$ with $\tau =  (p\ c)$ , and deduce that every move flips the signature: $\varepsilon(\sigma') = -\varepsilon(\sigma)$ .
3. Checkerboard the tray: $\chi(k) = (-1)^{i+j}$ for the cell $k$ in row $i$ , column $j$ . Show that every move flips $\chi(\text{cell of the blank})$ , and deduce that a sequence of moves returning the blank to its starting cell has even length.
4. Show that $$I(\sigma) = \varepsilon(\sigma)\,  \chi\bigl(\sigma^{-1}(16)\bigr)$$ is invariant under every legal move, and compute $I(\mathrm{id})$.

**Part II — Loyd’s bounty: the invariant at work.**

5. Loyd’s configuration $\sigma_L$ agrees with the solved one except that cells $14$ and $15$ hold tiles $15$ and $14$ . Compute $I(\sigma_L)$ and conclude that no sequence of moves links $\sigma_L$ to the solved configuration: Loyd’s $1000 was never in danger.
6. Show that exactly half of all configurations satisfy $I =  +1$ : $\abs{\{\sigma : I(\sigma) = +1\}} = 16!/2$ . *(For a fixed blank cell, pair configurations by composing with one fixed [transposition](#def-b2-structures-sn) of two other cells.)*
7. Show that every move is undone by a legal move, that “ $\sigma'$ is reachable from $\sigma$ by legal moves” is an equivalence relation, and that the class $R$ of the solved configuration satisfies $R \subseteq \{I = +1\}$ . Conclude that there are at least two classes.
8. Suppose the blank is home: $\sigma(16) = 16$ . Show that $I(\sigma) = \varepsilon(\rho)$ where $\rho \in  \mathfrak{S}_{15}$ is the restriction of $\sigma$ to the cells $1, \dots, 15$ , and that any configuration can be carried by legal moves to one with the blank home. Conclude: to prove $R = \{I = +1\}$ it suffices to realize every *even* permutation of the fifteen non-home cells by a sequence of moves starting and ending with the blank home.

**Part III — Blank tours and the program group.** A *program* is a finite sequence of legal moves, started from a configuration with the blank home, whose final configuration again has the blank home. Its *effect* is the permutation $\pi$ of the cells defined by: the content of cell $x$ ends in cell $\pi(x)$.

9. Show that a program run from $\sigma$ ends at $\sigma  \circ \pi^{-1}$ ; that running two programs in succession composes their effects; and that the set $H$ of all effects is a subgroup of $\mathfrak{S}_{15}$ (permutations of the cells $1, \dots, 15$ ) contained in the alternating group $A_{15}$ .
10. (The elementary tour) From the blank at home, slide the blank around the bottom-right $2 \times 2$ block: cells $16 \to 12 \to 11 \to 15 \to 16$ . Show the effect is the $3$ -cycle $(11\ 12\ 15)$ , and that the reverse tour gives $(11\ 15\ 12)$ . Both lie in $H$ .
11. (The grand tour) Verify that $$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$$ is a closed walk through all sixteen cells (adjacent steps only), and that its effect is the $15$-cycle $$\zeta = (15\ 12\ 11\ 10\ 6\ 7\ 8\ 4\ 3\ 2\ 1\ 5\ 9\ 13\  14) .$$ Writing $x_0 = 15$, $x_1 = 12$, $x_2 = 11$, …, $x_{14}  = 14$ for its [cycle](#def-b2-structures-sn) [order](#def-b2-structures-generated), check that the reverse elementary tour of question 10 is exactly $(x_0\ x_1\  x_2)$.
12. Prove the conjugation formula in any $\mathfrak{S}_n$: for a permutation $g$ and a $3$-cycle, $$g\,(a\ b\ c)\,g^{-1} = \bigl(g(a)\ g(b)\ g(c)\bigr),$$ and note that $H$, being a group, is closed under conjugation by its own elements.
13. Deduce that $H$ contains all fifteen *consecutive* $3$-cycles of the grand tour: $$s_t = (x_t\ x_{t+1}\ x_{t+2}) \qquad (t \in \Z/15\Z,  \text{ indices mod } 15).$$

**Part IV — Generating the alternating group.**

14. (Lemma A) Let $s$ and $t$ be $3$ -cycles whose supports share exactly two points, say supports $\{a, b, c\}$ and $\{b, c, d\}$ . Show that, after replacing $s$ or $t$ by its inverse if necessary (which changes nothing to the [generated](#def-b2-structures-generated) subgroup), the product $st$ is a double [transposition](#def-b2-structures-sn) ; show that $A_4$ contains no subgroup of [order](#def-b2-structures-generated) $6$ *(a subgroup of index $2$ contains every square; count the $3$-cycles among squares)* ; and conclude that $\langle s, t\rangle$ is the whole alternating group of the four letters $\{a, b, c, d\}$ .
15. (Lemma B) Let $X$ be a set of $k \geq 4$ letters, $w  \notin X$ , and let $G$ be a subgroup of some $\mathfrak{S}_n$ containing every even permutation of $X$ and one $3$ -cycle $(u\ v\ w)$ with $u, v \in X$ . Show that for all distinct $a, b \in X$ there is an *even* permutation $g$ of $X$ with $g(u) = a$ , $g(v) = b$ , and deduce $(a\ b\ w) \in G$ .
16. Deduce that the group $G$ of Lemma B contains every even permutation of $X \cup \{w\}$ *(use [Exercise 1.6](#exo-b2-structures-6): the $3$-cycles generate)* . Then, chaining Lemmas A and B along the consecutive $3$ -cycles $s_0, s_1, \dots, s_{12}$ of question 13, prove that $\langle s_0, \dots, s_{12}\rangle = A_{15}$ .
17. Conclude that $H = A_{15}$ : *every even rearrangement of the fifteen tiles is achievable by a program* , and $H$ has $15!/2 = 653\,837\,184\,000$ elements.
18. (The Johnson–Story theorem, 1879) Assemble questions 6, 7, 8 and 17: the configurations reachable from the solved one are *exactly* the $16!/2 =  10\,461\,394\,944\,000$ configurations with $I = +1$ ; and reachability has exactly *two* classes, the class of the solved configuration and the class of Loyd’s $\sigma_L$ . *(For the second point, relabel the tiles $14$ and $15$: show $\sigma \mapsto (14\ 15) \circ  \sigma$ maps move sequences to move sequences and exchanges $\{I = +1\}$ with $\{I = -1\}$.)*

**Part V — Criteria, variants, and the view from above.**

19. (The practical criterion) Read the fifteen tiles in reading order of their cells, skipping the blank, and let $N$ be the number of inversions of this list; let $r$ be the row of the blank counted from the *bottom* . Show that $I(\sigma) = (-1)^{N + r + 1}$ , so that $\sigma$ is solvable if and only if $N + r$ is odd.
20. (Group actions) An *action* of a group $G$ on a set $X$ is a map $G \times X \to X$ , $(g, x) \mapsto g \cdot  x$ , with $e \cdot x = x$ and $g \cdot (h \cdot x) =  (gh) \cdot x$ ; the *orbit* of $x$ is $G \cdot x$ , and the action is *free* when $g \cdot x = x$ forces $g =  e$ . Show that $h \cdot \sigma = \sigma \circ h^{-1}$ defines a free action of $H$ on the set of blank-home configurations, that its orbits are exactly the classes of mutual reachability by programs, and recover from the orbit count that these configurations split into exactly $15!\,/\,\abs H = 2$ classes.
21. (The $3 \times 3$ obstruction) Show that the $3 \times 3$ board admits *no* closed walk visiting every cell exactly once: the grand-tour strategy of Part III fails for the eight puzzle. *(Checkerboard the nine cells.)*
22. (The repair) On the $3 \times 3$ board with cells $1$ to $9$ in reading order and home $9$ : compute the effects of the perimeter tour $9 \to 8 \to 7 \to 4 \to 1 \to 2 \to 3  \to 6 \to 9$ (a $7$ -cycle $\zeta'$ fixing the center $5$ ) and of the corner tour $9 \to 6 \to 5 \to 8 \to 9$ (a $3$ -cycle through the center). Conjugating the latter by the powers of $\zeta'$ and chaining Lemmas A and B, prove that the eight puzzle’s program group is all of $A_8$ , hence that exactly $9!/2 = 181\,440$ of the $9! =  362\,880$ configurations are solvable.
23. (A poor board) Now let the board be a single [cycle](#def-b2-structures-sn) of $n  \geq 4$ cells carrying $n - 1$ tiles. Show that the cyclic order of the tiles is invariant, that each reachability class has exactly $n(n - 1)$ configurations *(the classes are the orbits of a [cyclic group](#def-b2-structures-generated) of [order](#def-b2-structures-generated) $\operatorname{lcm}(n, n-1) = n(n-1)$)* , and that there are $(n - 2)!$ classes — for $n \geq 5$ far more than $2$ : on a thin board the parity invariant captures almost nothing, and geometry rules.
24. Two verdicts by the criterion of question 19: the fully reversed tray (tiles $15, 14, \dots, 1$ in cells $1$ to $15$ , blank home) and the tray with the blank in cell $1$ followed by the tiles $15, 14, \dots, 1$ in cells $2$ to $16$ . Which one is solvable?
25. (Synthesis) The proof has two independent pillars: an *invariant* ( $I$ , built from the signature morphism) showing at most half the configurations are reachable, and an *explicit generation* theorem ( $H = A_{15}$ ) showing at least half are. In one sentence each, say where the following entered: the morphism property of $\varepsilon$ ; Lagrange’s theorem; the generation of $A_n$ by $3$ -cycles; conjugation. State the meta-principle in one line.

**Solution of Problem 1.1.**

**1.** A configuration assigns to each of the $16$ cells one of the $16$ contents (tiles $1$–$15$ or the blank $b = 16$), each exactly once: precisely a bijection $\intint1{16} \to
\intint1{16}$, an element of $\mathfrak{S}_{16}$; there are $16!
= 20\,922\,789\,888\,000$ of them. A legal move slides one tile adjacent to the blank, so the number of moves is the number of neighbours of the blank’s cell: $2$ for the four corner cells, $3$ for the eight edge cells, $4$ for the four interior cells.

**2.** After the slide, cell $p$ holds the former content of $c$ and cell $c$ holds the blank; all other cells are untouched: $\sigma'(p) = \sigma(c)$, $\sigma'(c) = \sigma(p) = 16$, $\sigma' = \sigma$ elsewhere. That is exactly $\sigma' = \sigma
\circ (p\ c)$. Since $\varepsilon$ is a morphism and $\varepsilon\bigl((p\ c)\bigr) = -1$: $\varepsilon(\sigma') = -\varepsilon(\sigma)$.

**3.** Adjacent cells differ by one step in exactly one of the two coordinates, so $i + j$ changes parity: $\chi$ takes opposite values on adjacent cells. A move transfers the blank from $p$ to the adjacent $c$, flipping $\chi(\text{blank cell})$. Along a closed walk of the blank, $\chi$ is flipped once per move and returns to its initial value: the number of moves is even.

**4.** By questions 2 and 3, one move flips both factors of $I(\sigma) = \varepsilon(\sigma)\chi(\sigma^{-1}(16))$; their product is unchanged. For the solved configuration: $\varepsilon(\mathrm{id}) = +1$ and the blank is at cell $16$, row $4$, column $4$: $\chi(16) = (-1)^{8} = +1$, so $I(\mathrm{id}) = +1$.

**5.** $\sigma_L$ is the [transposition](#def-b2-structures-sn) $(14\ 15)$ of cells: $\varepsilon(\sigma_L) = -1$; its blank is home, $\chi(16) = +1$: $I(\sigma_L) = -1 \neq +1 = I(\mathrm{id})$. Since $I$ is preserved by every move, no sequence of moves joins $\sigma_L$ and $\mathrm{id}$. The prize was structurally safe.

**6.** Fix a cell $p$ and two other cells $c \neq d$ distinct from $p$, and set $\tau_0 = (c\ d)$. On the set of configurations with blank at $p$, the map $\sigma \mapsto \sigma
\circ \tau_0$ is an involution (it preserves $\sigma(p) = 16$ since $\tau_0$ fixes $p$) and flips $\varepsilon$, hence flips $I$: it pairs the configurations with $I = +1$ bijectively with those with $I = -1$. So each of the $16$ blank positions contributes $15!/2$ configurations with $I = +1$, and

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

**7.** The move sliding the tile of $c$ into $p$ is undone by sliding that same tile (now in $p$) back into $c$: composing with $(p\ c)$ twice is the identity. Hence: reflexivity (empty sequence), symmetry (reverse the sequence, undoing each move), transitivity (concatenate): an equivalence relation. Every $\sigma \in R$ has $I(\sigma) = I(\mathrm{id}) = +1$ by question 4, so $R \subseteq \{I = +1\}$; and $\sigma_L \notin R$ gives a second class.

**8.** If $\sigma(16) = 16$, then $\sigma$ permutes the cells $1, \dots, 15$; call $\rho$ this restriction. Appending a fixed point changes neither the [cycle](#def-b2-structures-sn) type nor the signature (decompose $\rho$ into [transpositions](#def-b2-structures-sn); the same product works in $\mathfrak{S}_{16}$), so $\varepsilon(\sigma) =
\varepsilon(\rho)$, and $\chi(16) = +1$ gives $I(\sigma) =
\varepsilon(\rho)$. Any configuration can be carried to a blank-home one: the grid is connected, so walk the blank along a path of adjacent cells to cell $16$ (each step is a legal move). Now suppose every even $\rho \in \mathfrak{S}_{15}$ is realized by a program. Given $\sigma$ with $I(\sigma) = +1$: walk the blank home to reach $\widetilde\sigma$ (equivalent to $\sigma$), with $I(\widetilde\sigma) = +1$, i.e. its restriction $\rho$ is even; the program realizing $\rho$ carries $\widetilde\sigma$ to $\widetilde\sigma \circ \rho^{-1} = \mathrm{id}$ (see question 9). By transitivity $\sigma \in R$, whence $\{I = +1\} \subseteq
R$ and equality.

**9.** *Single move:* the content of $c$ ends in $p$ and the blank in $c$: the effect is $\pi = (p\ c)$, and indeed $\sigma' = \sigma \circ (p\ c) = \sigma \circ \pi^{-1}$. *Induction:* if a sequence has effect $\pi_1$ and carries $\sigma$ to $\sigma \circ \pi_1^{-1}$, following it with a move of effect $\pi_2 = (p'\ c')$ yields $(\sigma \circ \pi_1^{-1})
\circ \pi_2^{-1} = \sigma \circ (\pi_2\pi_1)^{-1}$, and contents move by $\pi_2 \circ \pi_1$ (first $\pi_1$, then $\pi_2$). So effects compose, and a program run from $\sigma$ ends at $\sigma
\circ \pi^{-1}$. *Subgroup:* the empty program has effect $\mathrm{id}$; concatenation gives products; reversing a program (question 7) gives inverses. A program’s effect fixes cell $16$ (blank starts and ends home), so $H \leq \mathfrak{S}_{15}$. *Evenness:* a program of $k$ moves has $k$ even (question 3), and $\varepsilon(\sigma \circ \pi^{-1}) =
(-1)^k\varepsilon(\sigma)$ forces $\varepsilon(\pi) = +1$: $H
\subseteq A_{15}$.

**10.** Track the four slides from the blank at $16$: move $16 \to 12$ sends the content of $12$ to $16$; move $12 \to 11$ sends the content of $11$ to $12$; move $11 \to 15$ sends the content of $15$ to $11$; move $15 \to 16$ sends the content parked in $16$ (originally in $12$) to $15$. Net: $11 \mapsto
12$, $12 \mapsto 15$, $15 \mapsto 11$, blank home: the effect is $(11\ 12\ 15)$. The reverse tour undoes it: effect $(11\ 12\
15)^{-1} = (11\ 15\ 12)$. Both are effects of programs, hence in $H$.

**11.** Adjacency of consecutive cells: within each listed pair the cells differ by $1$ in the same row ($16{-}15$, $15{-}14$, $14{-}13$; $1{-}2$, $2{-}3$, $3{-}4$; $8{-}7$, $7{-}6$; $10{-}11$, $11{-}12$) or by $4$ within a column ($13{-}9$, $9{-}5$, $5{-}1$; $4{-}8$; $6{-}10$; $12{-}16$): a closed walk through all $16$ cells, of length $16$. Effect: as in question 10, writing the visited cells $c_0 = 16, c_1 = 15,
\dots, c_{15} = 12$: the content of $c_i$ moves to $c_{i-1}$ for $i = 2, \dots, 15$, and the content of $c_1$, parked in $16$ after the first move, is carried to $c_{15}$ by the last move. So the effect maps $15 \mapsto 12$, and $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$: exactly the $15$-cycle $\zeta$. Its [cycle](#def-b2-structures-sn) [order](#def-b2-structures-generated) starts $x_0 = 15$, $x_1 = 12$, $x_2 = 11$, and $(x_0\ x_1\ x_2)
= (15\ 12\ 11)$ maps $15 \mapsto 12 \mapsto 11 \mapsto 15$ — which is precisely $(11\ 15\ 12)$, the reverse elementary tour.

**12.** Let $\gamma = (a\ b\ c)$ and $x \in \intint1n$. If $x = g(a)$: $g\gamma g^{-1}(x) = g(\gamma(a)) = g(b)$; likewise $g(b) \mapsto g(c)$ and $g(c) \mapsto g(a)$. If $x \notin
\{g(a), g(b), g(c)\}$, then $g^{-1}(x) \notin \{a,b,c\}$ is fixed by $\gamma$, so $x$ is fixed. Hence $g\gamma g^{-1} =
(g(a)\ g(b)\ g(c))$. And for $g, h \in H$, $ghg^{-1} \in H$ by the subgroup axioms.

**13.** $\zeta \in H$ (question 11) and $s_0 = (x_0\ x_1\
x_2) \in H$ (questions 10–11). Since $\zeta(x_i) = x_{i+1}$ (indices mod $15$), question 12 gives

$$
\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.** Up to inverting, assume $s = (a\ b\ c)$ and $t =
(b\ c\ d)$ (a $3$-cycle on $\{a,b,c\}$ is $(a\ b\ c)$ or its inverse; likewise on $\{b,c,d\}$; replacing a generator by its inverse leaves $\langle s, t\rangle$ unchanged). Then, applying $t$ first,

$$
st \colon a \mapsto b,\quad b \mapsto a,\quad c \mapsto d,\quad
d \mapsto c, \qquad\text{i.e.}\quad st = (a\ b)(c\ d),
$$

a double [transposition](#def-b2-structures-sn). The subgroup $G = \langle s, t\rangle$ consists of even permutations of the four letters, so $G \leq
A_4$ and $\abs G \mid 12$; it contains an element of [order](#def-b2-structures-generated) $3$ and one of [order](#def-b2-structures-generated) $2$, so $6 \mid \abs G$ (Lagrange, [Theorem 1.14](#thm-b2-structures-lagrange), applied to the two [cyclic](#def-b2-structures-generated) subgroups). If $A_4$ had a subgroup $K$ of [order](#def-b2-structures-generated) $6$, it would have index $2$, and then $g^2 \in K$ for every $g \in A_4$: for $g \in K$ this is clear; for $g \notin K$ the only cosets are $K$ and $gK$, so the coset $g^2K$ is $K$ or $gK$, and $g^2K =
gK$ would force $g \in K$. So every square lies in $K$. But every $3$-cycle $\gamma$ is a square, $\gamma = (\gamma^2)^2$, and $A_4$ contains eight $3$-cycles: $8 > 6$, contradiction. Hence $\abs G = 12$: $G = A_4$.

**15.** Extend $u \mapsto a$, $v \mapsto b$ to a bijection $g_0$ of $X$ (send the remaining $k - 2$ letters bijectively anywhere onto the complement of $\{a, b\}$). If $g_0$ is odd, pick two distinct letters $s_1, t_1 \in X \setminus \{u, v\}$ (possible: $k \geq 4$) and replace $g_0$ by $g_0 \circ (s_1\
t_1)$, which is even and still maps $u \mapsto a$, $v \mapsto
b$. Extend by the identity off $X$: an even permutation $g \in
G$ (it is an even permutation of $X$). Then question 12:

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

using $g(w) = w$.

**16.** Every $3$-cycle of $X \cup \{w\}$ lies in $G$: those supported in $X$ are even permutations of $X$; one with support $\{a, b, w\}$ is $(a\ b\ w)$ or $(b\ a\ w)$, both delivered by question 15. By [Exercise 1.6](#exo-b2-structures-6), the $3$-cycles of the $(k+1)$-element set $X \cup \{w\}$ generate its alternating group, so $G$ contains every even permutation of $X \cup \{w\}$. *Chaining:* let $G = \langle s_0, \dots,
s_{12}\rangle$. Lemma A applied to $s_0 = (x_0\ x_1\ x_2)$ and $s_1 = (x_1\ x_2\ x_3)$ (supports share $\{x_1, x_2\}$) gives all even permutations of $X_4 = \{x_0, x_1, x_2, x_3\}$. If $G$ contains all even permutations of $X_m = \{x_0, \dots,
x_{m-1}\}$ ($4 \leq m \leq 14$), then $s_{m-2} = (x_{m-2}\
x_{m-1}\ x_m)$ has $u = x_{m-2}, v = x_{m-1} \in X_m$ and new letter $w = x_m$: Lemma B and the first part give all even permutations of $X_{m+1}$. Induction up to $m = 14$: $G \supseteq
A_{15}$ (even permutations of all fifteen cells), and $G
\subseteq A_{15}$ since each $s_t$ is even: $\langle s_0, \dots,
s_{12}\rangle = A_{15}$.

**17.** Questions 13 and 16: $A_{15} = \langle s_0, \dots,
s_{12}\rangle \subseteq H$; question 9: $H \subseteq A_{15}$. So $H = A_{15}$, of [order](#def-b2-structures-generated) $15!/2 = 653\,837\,184\,000$: every even rearrangement of the fifteen tiles is the effect of a program.

**18.** Question 8 reduced $R = \{I = +1\}$ to realizing every even $\rho \in \mathfrak{S}_{15}$ by a program: done by question 17. With question 6, $\abs R = 16!/2 =
10\,461\,394\,944\,000$. *Two classes:* let $t_0 = (14\
15)$ act on *contents*: $\varphi(\sigma) = t_0 \circ
\sigma$. A legal move from $\sigma$ is a legal move from $\varphi(\sigma)$ (the blank cell is unchanged: $(t_0\sigma)^{-1}(16) = \sigma^{-1}(t_0(16)) = \sigma^{-1}(16)$, and the moved cell is the same), and $\varphi(\sigma \circ \tau)
= \varphi(\sigma) \circ \tau$: $\varphi$ maps move sequences to move sequences, bijectively (it is an involution). It flips $I$: $\varepsilon(t_0\sigma) = -\varepsilon(\sigma)$, same blank cell. Hence $\varphi$ maps the class $R = \{I = +1\}$ of $\mathrm{id}$ bijectively onto the class of $\varphi(\mathrm{id})
= \sigma_L$, which is therefore all of $\{I = -1\}$: exactly two classes. This is the Johnson–Story theorem.

**19.** Index the cells in reading order and let $k = 4(i -
1) + j$ be the blank’s cell. Count the inversions of $\sigma$ (pairs of cells $x < y$ with $\sigma(x) > \sigma(y)$): pairs of two tile cells contribute $N$; pairs involving the blank: cells after the blank all hold tiles $< 16$, each inverted ($16 - k$ pairs), cells before it are never inverted. So $\varepsilon(\sigma) = (-1)^{N + 16 - k} = (-1)^{N + k}$. Since $k = 4(i-1) + j \equiv j \pmod 2$,

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

using $i = 5 - r$. By question 18, $\sigma$ is solvable iff $I(\sigma) = +1$ iff $N + r$ is odd. Check: solved, $N = 0$, $r
= 1$: odd, solvable; Loyd, $N = 1$, $r = 1$: even, unsolvable.

**20.** *Action:* $e \cdot \sigma = \sigma \circ
\mathrm{id} = \sigma$ and $g \cdot (h \cdot \sigma) = \sigma
\circ h^{-1} \circ g^{-1} = \sigma \circ (gh)^{-1} = (gh) \cdot
\sigma$; and $\sigma \circ h^{-1}$ is again a blank-home configuration ($h$ fixes cell $16$). *Free:* $\sigma \circ
h^{-1} = \sigma$ gives $h^{-1} = \mathrm{id}$ (compose with $\sigma^{-1}$). *Orbits = program classes:* question 9 says the configurations reachable from $\sigma$ by programs are exactly the $\sigma \circ \pi^{-1}$, $\pi \in H$: the orbit $H
\cdot \sigma$. *Count:* freeness makes $h \mapsto h \cdot
\sigma$ injective, so every orbit has $\abs H = 15!/2$ elements; the $15!$ blank-home configurations therefore split into $15!\,/\,(15!/2) = 2$ orbits — the blank-home shadow of the two Johnson–Story classes.

**21.** The $3 \times 3$ grid is bipartite for the checkerboard colouring: every step of a walk changes colour, so every *closed* walk has even length. A closed walk visiting each of the $9$ cells exactly once would have length $9$, odd: impossible. The grand-tour construction of Part III is therefore unavailable on the eight puzzle.

**22.** *Perimeter tour* $9 \to 8 \to 7 \to 4 \to 1
\to 2 \to 3 \to 6 \to 9$ (all steps adjacent; length $8$, even): by the bookkeeping of question 11 with $c_1 = 8, c_2 = 7, c_3 =
4, c_4 = 1, c_5 = 2, c_6 = 3, c_7 = 6$, the effect is

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

a $7$-cycle fixing the center $5$ (content of $7$ moves to $8$, of $4$ to $7$, of $1$ to $4$, of $2$ to $1$, of $3$ to $2$, of $6$ to $3$, and of $8$ to $6$). *Corner tour* $9 \to 6 \to
5 \to 8 \to 9$: effect $(6\ 8\ 5)$ (content of $5$ moves to $6$, of $8$ to $5$, of $6$ — parked at $9$ — to $8$). Set $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$. Conjugation (question 12):

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

since $\zeta'$ fixes $5$. The supports of $T_0 = (y_1\ y_0\ 5)$ and $T_1 = (y_2\ y_1\ 5)$ share exactly $\{y_1, 5\}$: Lemma A gives all even permutations of $\{y_0, y_1, y_2, 5\}$. Then $T_2 = (y_3\ y_2\ 5)$ adjoins $y_3$ by Lemma B (its letters $y_2, 5$ lie in the current set, $k = 4$), and $T_3, T_4, T_5$ adjoin $y_4, y_5, y_6$ in turn: all even permutations of the eight non-home cells lie in the program group, which also consists of even permutations (the argument of question 9 is board-independent). So $H_{3\times3} = A_8$, and the reasoning of questions 6, 8, 18 — also board-independent — shows the reachable configurations are exactly those with $I = +1$: half of $9!$, i.e. $181\,440$.

**23.** Label the cells $0, \dots, n-1$ around the [cycle](#def-b2-structures-sn). A move swaps the blank with one of its two neighbours. Read the tiles in cyclic order starting just after the blank: a word $w$ listing the $n - 1$ tiles. Moving the blank one step forward replaces $(p, w)$ by $(p + 1, \rho w)$, where $p$ is the blank cell and $\rho$ cyclically rotates the word by one; the backward move is the inverse. The *cyclic* order of the tiles (the word up to rotation) is thus invariant. The reachable class of $(p, w)$ is the orbit of the map $g \colon (p, w) \mapsto (p+1,
\rho w)$, an element of [order](#def-b2-structures-generated) $\operatorname{lcm}(n, n-1) =
n(n-1)$ in the product of the two [cyclic groups](#def-b2-structures-generated) (translations of $\Z/n\Z$ and rotations of the $n-1$ word positions), the lcm being $n(n-1)$ because $\gcd(n, n-1) = 1$: each class has exactly $n(n-1)$ configurations, all with the same necklace. Classes: $n!\,/\,\bigl(n(n-1)\bigr) = (n-2)!$. For $n \geq 5$, $(n-2)! > 2$: the parity invariant (two classes at best) is blind to almost all of the obstruction; the wealth of the $4
\times 4$ board — where parity is the *only* obstruction — is a genuinely geometric fact, not a formal one.

**24.** Both trays have the tiles in fully reversed order, so $N = \binom{15}{2} = 105$ in both cases (every pair of tiles is inverted). *Blank home:* $r = 1$, $N + r = 106$ even: unsolvable. *Blank in cell $1$:* the blank is in the top row, $r = 4$, $N + r = 109$ odd: solvable. Two trays that differ only by where the hole sits fall on opposite sides of the wall.

**25.** *Morphism property:* it converts “one move = one [transposition](#def-b2-structures-sn)” into “one move = one sign flip” (questions 2, 4), making $I$ computable move by move. *Lagrange:* it forced $6 \mid \abs{\langle s, t\rangle}$ in Lemma A and sized the cosets in the order-$6$ exclusion (question 14). *Generation by $3$-cycles:* it converted “$H$ contains enough $3$-cycles” into “$H$ contains all of $A_{15}$” (question 16). *Conjugation:* it manufactured the fifteen consecutive $3$-cycles from a single $2 \times 2$ tour transported by the grand tour (questions 12–13), and the $3$-cycles $(a\ b\ w)$ in Lemma B. *Meta-principle:* an invariant proves impossibility, an explicit construction proves possibility, and a problem is fully solved exactly when the two bounds meet — here, at one half.