---
title: "Conjuntos e estruturas"
book: "Matemática universitária — Graduação 2"
subject: math
language: pt
chapter: 1
exercises: 12
source: https://one-course.com/books/math/4/pt/chapter/1-conjuntos-e-estruturas
---

# Capítulo 1 — Conjuntos e estruturas

Este capítulo de abertura afia os fundamentos lançados no volume do primeiro ano de graduação e os transforma em ferramentas de trabalho correntes: o cálculo dos conjuntos e dos quocientes, a comparação de conjuntos infinitos ([enumerabilidade](#def-b2-structures-countable), Cantor–Bernstein) e a teoria estrutural dos grupos e dos anéis — o teorema de Lagrange, o grupo simétrico e sua assinatura, os [ideais](#def-b2-structures-ideal) e o teorema chinês dos restos. Tudo aqui é usado sem trégua no resto do livro: a assinatura constrói o determinante ([Capítulo 2](https://one-course.com/books/math/4/pt/chapter/2-algebra-linear#ch-b2-linalg)), os [anéis quociente](#def-b2-structures-quotientring) fazem a aritmética funcionar e a [enumerabilidade](#def-b2-structures-countable) está por trás tanto da topologia quanto da probabilidade.

## 1.1 Conjuntos, aplicações, quocientes

Usamos livremente a linguagem dos conjuntos, das aplicações e das relações de equivalência e de [ordem](#def-b2-structures-generated) montada no volume do primeiro ano de graduação. Dois aperfeiçoamentos merecem um enunciado em boa e devida forma.

**Proposição 1.1 (Imagens e imagens inversas de famílias).**

Sejam $f \colon E \to F$ e $(A_i)_{i \in I}$, $(B_j)_{j \in J}$ famílias de partes de $E$, resp. de $F$. Então

$$
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{igualdade para } f \text{ injetiva}).
$$

**Demonstração.** Cada identidade se obtém desdobrando as definições; por exemplo $x \in
f^{-1}(\bigcap B_j) \iff f(x) \in B_j$ para todo $j$ $\iff x \in
f^{-1}(B_j)$ para todo $j$. As identidades sobre imagens e a falha da igualdade no caso da interseção (com a correção pela injetividade) foram demonstradas no volume do primeiro ano de graduação para dois conjuntos; os argumentos são idênticos para famílias. ∎

**Exemplo 1.2 (Onde a inclusão das imagens é estrita).**

Tome $f \colon \R \to \R$, $f(x) = x^2$, com $A_1 =
\intcc{-1}{0}$ e $A_2 = \intcc{0}{1}$. Então

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

a inclusão da [Proposição 1.1](#prop-b2-structures-images) é tão estrita quanto possível — os dois antecedentes $\pm x$ de um mesmo valor vivem em $A_i$ diferentes. A injetividade é exatamente o que proíbe essa separação, e é por isso que as imagens inversas (que nunca fundem pontos) satisfazem as quatro identidades sem condição, ao passo que as imagens perdem a que trata das interseções. Regra prática para todo o livro: faça as *imagens inversas* atravessarem as operações de conjuntos livremente; manipule as imagens com cuidado.

**Definição 1.3 (Conjunto quociente).**

Seja $\mathcal{R}$ uma relação de equivalência sobre $E$. O *conjunto quociente* $E/\mathcal{R}$ é o conjunto das classes de equivalência; a sobrejeção $\pi \colon E \to E/\mathcal{R}$, $x \mapsto \mathrm{cl}(x)$, é a *projeção canônica*.

*Propriedade universal (fatoração):* se $f \colon E \to F$ é *compatível* com $\mathcal{R}$ (isto é, $x \mathbin{\mathcal{R}}
y \implies f(x) = f(y)$), existe exatamente uma aplicação $\overline f
\colon E/\mathcal{R} \to F$ tal que $f = \overline f \circ \pi$.

**Demonstração da propriedade universal.** Unicidade: a condição $f = \overline f \circ \pi$ se escreve

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

e, como $\pi$ é sobrejetiva, todo elemento de $E/\mathcal{R}$ é um certo $\mathrm{cl}(x)$: os valores de $\overline f$ estão todos impostos. Existência: tome a fórmula acima como *definição* de $\overline f$; ela é inequívoca precisamente pela compatibilidade — se $\mathrm{cl}(x) =
\mathrm{cl}(y)$, então $x \mathbin{\mathcal{R}} y$, logo $f(x) =
f(y)$ e os dois valores candidatos coincidem — e ela fatora $f$ por construção. Note a divisão de tarefas: a sobrejetividade de $\pi$ dá a unicidade, a compatibilidade dá a existência. ∎

**Exemplo 1.4.**

$\Z/n\Z$ é o quociente de $\Z$ pela congruência módulo $n$; as verificações de boa definição do volume do primeiro ano de graduação eram casos particulares da propriedade universal. Os quocientes transformam “construções compatíveis com os representantes” em aplicações de verdade — e nos servimos disso constantemente adiante.

## 1.2 Enumerabilidade e cardinalidade

**Definição 1.5 (Equipotência, enumerabilidade).**

Dois conjuntos são *equipotentes* quando uma bijeção os liga. Um conjunto é *enumerável* quando é equipotente a $\N$ (alguns autores incluem os conjuntos finitos; dizemos *no máximo enumerável* para “finito ou enumerável”).

**Proposição 1.6 (Propriedades de estabilidade).**

1. Todo subconjunto infinito de $\N$ é [enumerável](#def-b2-structures-countable) ; um conjunto é no máximo [enumerável](#def-b2-structures-countable) se e somente se ele injeta em $\N$ , se e somente se é vazio ou imagem sobrejetiva de $\N$ .
2. $\N \times \N$ é [enumerável](#def-b2-structures-countable) ; um produto de dois [conjuntos enumeráveis](#def-b2-structures-countable) no máximo [enumeráveis](#def-b2-structures-countable) é no máximo [enumerável](#def-b2-structures-countable) .
3. Uma união no máximo [enumerável](#def-b2-structures-countable) de [conjuntos enumeráveis](#def-b2-structures-countable) no máximo [enumeráveis](#def-b2-structures-countable) é no máximo [enumerável](#def-b2-structures-countable) .
4. $\Z$ e $\Q$ são [enumeráveis](#def-b2-structures-countable) .

**Demonstração.** (1) Enumere um $A \subseteq \N$ infinito por mínimos sucessivos: $a_0 =
\min A$, $a_{k+1} = \min\,(A \setminus \{a_0, \dots, a_k\})$ (não vazio, pois $A$ é infinito); a aplicação $k \mapsto a_k$ é estritamente crescente, injetiva e sobrejetiva sobre $A$ (todo $a \in A$ supera apenas um número finito de elementos de $A$, logo é atingido). Se $E$ injeta em $\N$ por $\varphi$, então $E$ é [equipotente](#def-b2-structures-countable) a $\varphi(E) \subseteq \N$: finito ou [enumerável](#def-b2-structures-countable). Se $s \colon \N \to
E$ é sobrejetiva, então $x \mapsto \min s^{-1}(\{x\})$ injeta $E$ em $\N$.

(2) A aplicação $(p, q) \mapsto 2^p(2q + 1) - 1$ é uma bijeção $\N^2
\to \N$ (todo inteiro positivo admite uma única decomposição $2^p m$ com $m$ ímpar, pela unicidade da fatoração). Produtos: componha injeções.

(3) Dados conjuntos $E_n$ com sobrejeções $s_n \colon \N \to E_n$ (inofensivo quando algum $E_n$ é finito: repita valores), a aplicação $(n, k)
\mapsto s_n(k)$ é uma sobrejeção do [conjunto enumerável](#def-b2-structures-countable) $\N^2$ sobre $\bigcup E_n$.

(4) $\Z = \N \cup (-\N^*)$: união [enumerável](#def-b2-structures-countable). $\Q$ é imagem sobrejetiva de $\Z \times \N^*$ (a aplicação fração), logo no máximo [enumerável](#def-b2-structures-countable), e infinito. ∎

**Exemplo 1.7 (Uma função de emparelhamento, na prática).**

A bijeção $(p, q) \mapsto 2^p(2q + 1) - 1$ da demonstração merece ser vista em ação. Seus primeiros valores:

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

A linha $p$ reúne os inteiros $n$ para os quais $n + 1$ é divisível por $2^p$ exatamente: todo número natural aparece exatamente uma vez. Decodificar é tão explícito quanto codificar: para $n = 43$, fatore $n + 1
= 44 = 2^2\cdot 11 = 2^2(2\cdot5 + 1)$, donde $(p, q) = (2, 5)$. A lição final: as demonstrações de [enumerabilidade](#def-b2-structures-countable) são muitas vezes *algoritmos* disfarçados — aqui, “ponha os fatores dois em evidência”.

**Exemplo 1.8 (Os números algébricos são enumeráveis).**

Um número complexo é *algébrico* quando anula algum polinômio não nulo com coeficientes racionais. O conjunto $\overline\Q$ dos números algébricos é [enumerável](#def-b2-structures-countable): os polinômios de grau $\leq d$ sobre $\Q$ injetam-se em $\Q^{d+1}$, produto finito de [conjuntos enumeráveis](#def-b2-structures-countable) ([Proposição 1.6](#prop-b2-structures-countablestable) (2)); a união sobre $d$ enumera os polinômios racionais não nulos como $P_0, P_1,
P_2, \dots$; cada $P_k$ tem um número finito de raízes; e

$$
\overline\Q = \bigcup_{k \in \N}\ \{\text{raízes de } P_k\}
$$

é uma união [enumerável](#def-b2-structures-countable) de conjuntos finitos ([Proposição 1.6](#prop-b2-structures-countablestable) (3)), infinita pois contém $\Q$. Combinado com a não [enumerabilidade](#def-b2-structures-countable) de $\R$ ([Teorema 1.9](#thm-b2-structures-cantor) adiante), isso prova — sem exibir um único deles — que os números transcendentes existem e formam uma maioria não [enumerável](#def-b2-structures-countable): o argumento de contagem de Cantor de 1874, a existência apenas pela cardinalidade.

**Teorema 1.9 (Cantor; não enumerabilidade de R\RR).**

1. Para todo conjunto $E$ , não existe sobrejeção $E \to  \mathcal{P}(E)$ .
2. $\R$ *não* é [enumerável](#def-b2-structures-countable) .

**Demonstração.** (1) foi demonstrado no volume do primeiro ano de graduação (o conjunto diagonal $D = \{x : x
\notin f(x)\}$).

(2) Suponha que $(x_n)_{n \in \N}$ enumere $\R$. Construa segmentos encaixados $I_0 \supseteq I_1 \supseteq \dots$ com $\abs{I_n} = 3^{-n}$ e $x_n \notin I_n$: divida o segmento atual em três terços fechados; ao menos um terço evita $x_n$ (um ponto encontra no máximo dois dos três). O teorema dos segmentos encaixados (extremidades adjacentes) fornece $\ell \in \bigcap_n I_n$; mas $\ell = x_N$ para algum $N$, e $x_N
\notin I_N$: contradição. ∎

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

Se $E$ injeta em $F$ e $F$ injeta em $E$, então $E$ e $F$ são [equipotentes](#def-b2-structures-countable).

**Demonstração.** Sejam $f \colon E \to F$ e $g \colon F \to E$ injeções. Para cada ponto (de $E$ ou de $F$), siga sua *cadeia de ancestrais* de imagens inversas sucessivas, $x \mapsto g^{-1}(x) \mapsto
f^{-1}(g^{-1}(x)) \mapsto \dots$ — cada passo está definido enquanto o ponto atual pertencer à imagem da injeção correspondente, e é então único por injetividade. Três destinos mutuamente exclusivos: a cadeia para em um ponto de $E \setminus g(F)$ (*origem em $E$*), para em um ponto de $F \setminus f(E)$ (*origem em $F$*) ou nunca para. Isso particiona $E = E_E \cup E_F \cup
E_\infty$ e $F = F_E \cup F_F \cup F_\infty$ conforme a origem.

Observe agora: $f$ leva $E_E$ *sobre* $F_E$ — a cadeia de $f(x)$ é a cadeia de $x$ precedida de um passo, de modo que as origens coincidem; e todo $y \in F_E$ tem uma cadeia com ao menos um passo (sua origem está em $E$), logo $y = f(x)$ com $x \in E_E$. O mesmo argumento dá bijeções $f \colon E_\infty \to F_\infty$ e $g \colon F_F
\to E_F$. Colando,

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

é uma bijeção de $E$ sobre $F = F_E \cup F_\infty \cup F_F$: é bijetiva por pedaços, e as três peças de chegada são disjuntas. ∎

**Exemplo 1.11.**

$\intoo{0}{1}$ e $\intcc{0}{1}$ são [equipotentes](#def-b2-structures-countable): a identidade injeta num sentido, $x \mapsto \frac{x + 1}{3}$ no outro; o teorema fabrica a bijeção (necessariamente descontínua). Do mesmo modo $\R$, $\intoo{0}{1}$ (por bijeções do tipo $\tanh$) e $\mathcal{P}(\N)$ (expansões binárias, [Exercício 1.3](#exo-b2-structures-3)) são todos [equipotentes](#def-b2-structures-countable): “a cardinalidade do contínuo”.

**Exemplo 1.12 (O segmento e o quadrado).**

$\intcc{0}{1}$ e $\intcc{0}{1}^2$ são [equipotentes](#def-b2-structures-countable) — a dimensão é invisível para a cardinalidade. Uma injeção é trivial: $x
\mapsto (x, 0)$. Para a outra, envie $(x, y)$ ao real cujos algarismos decimais intercalam os de $x$ e os de $y$,

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

escolhendo para cada coordenada a expansão que não termina numa sequência infinita de $9$: com essa convenção os algarismos da imagem determinam os de $x$ e os de $y$, de modo que a aplicação é injetiva (ela não precisa ser sobrejetiva — as imagens nunca têm, digamos, os algarismos de posição ímpar iguais a $9$ a partir de certa ordem — e isso não é problema). Cantor–Bernstein ([Teorema 1.10](#thm-b2-structures-cantorbernstein)) monta uma bijeção de verdade. A continuidade, é claro, é impossível: não há bijeção contínua entre eles — os capítulos métricos explicam por quê (a conexidade distingue a reta do plano, [Capítulo 4](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#ch-b2-metric)).

## 1.3 Grupos

**Definição 1.13 (Subgrupo gerado; ordem).**

Seja $G$ um grupo e $A \subseteq G$. O subgrupo *gerado* por $A$, escrito $\langle A \rangle$, é o menor subgrupo que contém $A$ — concretamente, todos os produtos finitos de elementos de $A$ e de seus inversos. Um grupo é *cíclico* quando é gerado por um único elemento: $\langle a\rangle = \{a^k : k \in \Z\}$. A *ordem* de $a \in G$ é $\operatorname{ord}(a) = \abs{\langle a \rangle}$ (possivelmente infinita); quando é finita, é o menor $n \geq 1$ com $a^n = e$, e $a^k = e \iff \operatorname{ord}(a) \mid k$.

**Demonstração da caracterização da ordem.** Se algum $a^m = e$ satisfaz $m \geq 1$, seja $n \geq 1$ o menor com $a^n
= e$. Os elementos $e, a, \dots, a^{n-1}$ são dois a dois distintos ($a^{i} = a^{j}$ com $0 \leq i < j < n$ dá $a^{j-i} = e$, contradizendo a minimalidade), e todo $a^k$ se reduz a um deles pela divisão euclidiana $k = nq + r$: $\langle a\rangle$ tem exatamente $n$ elementos, e $a^k = a^r = e \iff r = 0 \iff n \mid k$. Se nenhuma potência é trivial, todos os $a^k$ ($k \in \Z$) são distintos (mesmo argumento de divisão) e a ordem é infinita. ∎

**Teorema 1.14 (Lagrange).**

Seja $G$ um grupo finito e $H$ um subgrupo. Então $\abs H$ divide $\abs G$. Em particular, a ordem de todo elemento divide $\abs G$, e $a^{\abs G} = e$ para todo $a \in G$.

**Demonstração.** A relação $x \sim y \iff x^{-1}y \in H$ é uma equivalência (reflexiva: $e \in H$; simétrica: inversos; transitiva: produtos). A classe de $x$ é a *classe lateral à esquerda* $xH = \{xh : h \in H\}$, e $h \mapsto xh$ é uma bijeção $H \to xH$ (de inversa $y \mapsto
x^{-1}y$): todas as classes têm $\abs H$ elementos. As classes particionam $G$ (o teorema geral de partição do volume do primeiro ano de graduação), logo $\abs G =
\abs H \times (\text{número de classes laterais})$. Para um elemento: aplique isso a $H = \langle a\rangle$; então $a^{\abs G} = (a^{\operatorname{ord}
a})^{\abs G / \operatorname{ord} a} = e$. ∎

**Exemplo 1.15 (Classes laterais em ação: A3A_3A3​ dentro de S3\mathfrak{S}_3S3​).**

Tome $G = \mathfrak{S}_3$ (ordem $6$) e $H = A_3 =
\{\mathrm{id},\ (1\,2\,3),\ (1\,3\,2)\}$. As classes laterais à esquerda são

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

duas classes de três elementos que particionam $G$, exatamente como a contagem $\abs G = \abs H \times (\text{número de classes laterais})$ exige — e visivelmente a partição entre permutações pares e ímpares. Note que $(1\,3)H = (1\,2)H$ embora $(1\,3) \neq
(1\,2)$: as classes laterais são *classes*, e não são rotuladas por seus representantes; $x^{-1}y \in H$ é a única comparação legítima. Esse retrato em duas classes é o retrato geral da assinatura: $A_n$ e sua única classe lateral companheira cortam $\mathfrak{S}_n$ ao meio, e é assim que o problema de fim de semana conta as posições alcançáveis do quebra-cabeça.

**Exemplo 1.16.**

Dois dividendos imediatos. *Os grupos de [ordem](#def-b2-structures-generated) prima são [cíclicos](#def-b2-structures-generated):* se $\abs G = p$ é primo e $a \neq e$, então $\operatorname{ord}(a)$ divide $p$ e não vale $1$, logo vale $p$: $\langle a\rangle = G$. *O reticulado de subgrupos de $\Z/12\Z$:* pela [Proposição 1.17](#prop-b2-structures-cyclic) adiante, há exatamente um subgrupo por divisor de $12$ — [ordens](#def-b2-structures-generated) $1, 2, 3, 4, 6, 12$, [gerados](#def-b2-structures-generated) respectivamente por $\overline 0$, $\overline 6$, $\overline
4$, $\overline 3$, $\overline 2$, $\overline 1$. A advertência final: a *recíproca* do teorema de Lagrange é falsa em geral — $A_4$ tem ordem $12$ mas nenhum subgrupo de ordem $6$, como demonstramos no problema de fim de semana deste capítulo ([Problema 1.1](#pb-b2-structures-1), questão 14). Lagrange restringe as [ordens](#def-b2-structures-generated) possíveis; não as promete.

![O reticulado de subgrupos de ℤ/12ℤ: um subgrupo por divisor de 12 (), com uma aresta quando um contém o outro com índice primo. As inclusões correm ao contrário da divisibilidade do gerador: 4 ⊂eq 2 porque 4 é múltiplo de 2.](https://one-course.com/images/onecourse/chapters/math-4/b2-structures/fig-b388b4988163.svg)

*O reticulado de subgrupos de $\Z/12\Z$: um subgrupo por divisor de $12$ ([Proposição 1.17](#prop-b2-structures-cyclic)), com uma aresta quando um contém o outro com índice primo. As inclusões correm *ao contrário* da divisibilidade do gerador: $\langle\overline
4\rangle \subseteq \langle\overline2\rangle$ porque $4$ é múltiplo de $2$.*

**Proposição 1.17 (Grupos cíclicos).**

Seja $G = \langle a \rangle$ [cíclico](#def-b2-structures-generated) de ordem $n$.

1. $G$ é isomorfo a $(\Z/n\Z, +)$ , via $\overline k \mapsto  a^k$ .
2. Todo subgrupo de $G$ é [cíclico](#def-b2-structures-generated) ; para cada divisor $d \mid n$ existe exatamente um subgrupo de ordem $d$ , a saber $\langle  a^{n/d}\rangle$ .
3. $a^k$ gera $G$ se e somente se $\gcd(k, n) = 1$ : $G$ tem $\varphi(n)$ geradores (a função totiente de Euler).

**Demonstração.** (1) A aplicação $k \mapsto a^k$ de $\Z$ sobre $G$ é compatível com a congruência módulo $n$ ($a^{k} = a^{k'} \iff n \mid k - k'$, pela caracterização da ordem); a propriedade universal ([Definição 1.3](#def-b2-structures-quotient)) fornece um morfismo bijetivo bem definido a partir de $\Z/n\Z$.

(2) Seja $H \leq G$ não trivial e $m$ o menor $\geq 1$ com $a^m \in
H$. A divisão euclidiana mostra que $H = \langle a^m\rangle$ (para $a^k \in
H$: $k = mq + r$ obriga $a^r \in H$, logo $r = 0$), e $m \mid n$ (divida $n$ por $m$: $a^{n \bmod m} \in H$). Então $\abs H = n/m$; tomar $m = n/d$ realiza cada divisor $d$. Unicidade: todo subgrupo de ordem $d$ é, pelo que precede, da forma $\langle a^m \rangle$ com $n/m = d$ — logo $m = n/d$ fica imposto e o subgrupo está determinado.

(3) Afirmamos que $\operatorname{ord}(a^k) = \frac{n}{\gcd(k, n)}$. Escreva $d = \gcd(k, n)$. Para qualquer $m \geq 1$, a caracterização da ordem de [Definição 1.13](#def-b2-structures-generated) dá a cadeia de equivalências

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

o último passo pelo lema de Gauss, pois $\frac nd$ e $\frac kd$ são coprimos. O menor tal $m$ é $\frac nd$: $\operatorname{ord}(a^k) = \frac n{\gcd(k,n)}$, que é igual a $n$ se e somente se $\gcd(k, n) = 1$. Há $\varphi(n)$ tais classes $k$ módulo $n$. ∎

## 1.4 O grupo simétrico

**Definição 1.18.**

$\mathfrak{S}_n$ é o grupo das permutações de $\intint{1}{n}$ (ordem $n!$). Um *ciclo* $(a_1\,a_2\,\cdots\,a_k)$ leva $a_1 \mapsto a_2 \mapsto \dots \mapsto a_k \mapsto a_1$ e fixa todo o resto; $k$ é seu *comprimento*, e um $2$-ciclo é uma *transposição*. Dois ciclos são *disjuntos* quando seus suportes (os pontos não fixos) o são.

**Teorema 1.19 (Decomposição em ciclos).**

Toda permutação $\sigma \neq \mathrm{id}$ é um produto de [ciclos](#def-b2-structures-sn) dois a dois disjuntos, de modo único a menos da ordem dos fatores. [Ciclos](#def-b2-structures-sn) disjuntos comutam, e $\operatorname{ord}(\sigma)$ é o mmc dos comprimentos.

**Demonstração.** Considere a relação de “órbita” sobre o suporte de $\sigma$: $x \sim y$ se e somente se $y = \sigma^k(x)$ para algum $k \in \Z$ — uma relação de equivalência. Cada classe $\{x, \sigma(x), \dots, \sigma^{k-1}(x)\}$ (finita, de modo que os iterados fecham um [ciclo](#def-b2-structures-sn) — a primeira repetição deve retornar a $x$ por injetividade) carrega o [ciclo](#def-b2-structures-sn) $(x\ \sigma(x)\
\cdots\ \sigma^{k-1}(x))$, e $\sigma$ é o produto desses [ciclos](#def-b2-structures-sn): sobre cada órbita, só age o [ciclo](#def-b2-structures-sn) correspondente. Unicidade: toda fatoração em [ciclos](#def-b2-structures-sn) disjuntos reproduz exatamente as órbitas (o [ciclo](#def-b2-structures-sn) que passa por $x$ tem de ser $(x\ \sigma(x)\ \cdots)$). [Ciclos](#def-b2-structures-sn) disjuntos comutam porque movem pontos disjuntos; a afirmação sobre a ordem segue porque $\sigma^m = \mathrm{id}$ se e somente se a $m$-ésima potência de cada [ciclo](#def-b2-structures-sn) o é (por disjunção), se e somente se cada comprimento divide $m$. ∎

**Exemplo 1.20 (O tipo de ciclo como recenseamento).**

Quantas permutações de $\mathfrak{S}_9$ têm tipo de [ciclo](#def-b2-structures-sn) $(4, 3, 2)$ — um $4$-ciclo, um $3$-ciclo, uma [transposição](#def-b2-structures-sn)? Escolha os suportes e as [ordens](#def-b2-structures-generated) [cíclicas](#def-b2-structures-generated):

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

liste os nove símbolos em fila ($9!$ maneiras), agrupe os quatro primeiros, os três seguintes e os dois últimos em [ciclos](#def-b2-structures-sn), e divida pelas rotações internas de cada grupo ($4$, $3$ e $2$ delas), que dão a mesma permutação. (Os *comprimentos* dos [ciclos](#def-b2-structures-sn) são distintos aqui, logo não há mais nada a dividir; comprimentos iguais exigiriam dividir também pelas permutações dos grupos de mesmo comprimento.) Toda permutação desse tipo tem ordem $\operatorname{lcm}(4,3,2) = 12$ e assinatura $(-1)^3(-1)^2(-1)^1 = +1$ ([Teorema 1.19](#thm-b2-structures-cycles) e o teorema da assinatura adiante). Uma partição de $9$, uma classe de conjugação, um recenseamento — a combinatória de $\mathfrak{S}_n$ é a aritmética das partições.

**Teorema 1.21 (Assinatura).**

Existe exatamente um morfismo de grupos $\varepsilon \colon
\mathfrak{S}_n \to \{\pm 1\}$ (para $n \geq 2$) que assume o valor $-1$ nas [transposições](#def-b2-structures-sn): a *assinatura*. Além disso, $\varepsilon(\sigma) = (-1)^{I(\sigma)}$ em que $I(\sigma)$ é o número de *inversões* (pares $i < j$ com $\sigma(i) >
\sigma(j)$), um $k$-ciclo tem assinatura $(-1)^{k-1}$, e o *grupo alternado* $A_n = \ker\varepsilon$ tem ordem $\frac{n!}{2}$.

**Demonstração.** *Existência.* Para $\sigma \in \mathfrak{S}_n$ ponha

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

Os valores absolutos dos fatores se multiplicam dando $1$ (os pares não ordenados $\{\sigma(i), \sigma(j)\}$ percorrem todos os pares), logo $\varepsilon(\sigma) = (-1)^{I(\sigma)} \in \{\pm1\}$. Morfismo: para $\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),
$$

sendo o produto do meio igual a $\varepsilon(\sigma)$ após reindexação pelos pares $\{\tau(i), \tau(j)\}$ (cada par não ordenado aparece uma vez, e numerador e denominador mudam de sinal juntos). Uma [transposição](#def-b2-structures-sn) $\tau = (a\,b)$ com $a < b$ tem um número ímpar de inversões; contando exatamente: os pares invertidos $(i, j)$, $i < j$, com $\tau(i) > \tau(j)$ são

$$
(a, j) \ \text{para } a < j < b, \qquad
(i, b) \ \text{para } a < i < b, \qquad
(a, b) \ \text{ele mesmo},
$$

isto é, $(b - a - 1) + (b - a - 1) + 1 = 2(b - a) - 1$ deles, um número ímpar. (Alternativamente: verifique $(1\,2)$ diretamente, com uma única inversão, e conjugue — conjugados têm a mesma assinatura, pois $\varepsilon$ é um morfismo com valores em um grupo abeliano.) Logo $\varepsilon((a\,b)) = (-1)^{2(b-a)-1} = -1$.

*Unicidade.* As [transposições](#def-b2-structures-sn) geram $\mathfrak{S}_n$ (todo [ciclo](#def-b2-structures-sn) $(a_1\cdots a_k) = (a_1\,a_k)(a_1\,a_{k-1})\cdots(a_1\,a_2)$, e [Teorema 1.19](#thm-b2-structures-cycles) conclui); um morfismo com valores em $\{\pm1\}$ fica determinado por seus valores em geradores.

*Consequências.* A identidade de [ciclos](#def-b2-structures-sn) acima escreve um $k$-ciclo como produto de $k - 1$ [transposições](#def-b2-structures-sn): assinatura $(-1)^{k-1}$. $A_n$: o morfismo $\varepsilon$ é sobrejetivo (existem [transposições](#def-b2-structures-sn) para $n \geq 2$), e as duas “classes laterais” $A_n$ e $(1\,2)A_n$ são [equipotentes](#def-b2-structures-countable) e particionam $\mathfrak{S}_n$ (o argumento de Lagrange): $\abs{A_n} =
\frac{n!}{2}$. ∎

**Exemplo 1.22.**

$\sigma = \begin{pmatrix} 1&2&3&4&5&6\\ 3&6&5&4&1&2 \end{pmatrix}
= (1\,3\,5)(2\,6)$: ordem $\operatorname{lcm}(3,2) = 6$, assinatura $(-1)^{2}\cdot(-1)^{1} = -1$. A assinatura é o teste de paridade mais rápido para embaralhamentos — e o motor do determinante no [Capítulo 2](https://one-course.com/books/math/4/pt/chapter/2-algebra-linear#ch-b2-linalg).

**Exemplo 1.23 (Três caminhos para um só sinal).**

Seja $\sigma \in \mathfrak{S}_5$ a permutação que leva $1, 2, 3, 4, 5$ em $3, 5, 4,
1, 2$. *Pelos [ciclos](#def-b2-structures-sn):* $1 \mapsto 3 \mapsto 4 \mapsto 1$ e $2
\mapsto 5 \mapsto 2$, logo $\sigma = (1\,3\,4)(2\,5)$ e $\varepsilon(\sigma) = (-1)^{2}(-1)^{1} = -1$. *Pelas inversões:* na lista de valores $3, 5, 4, 1, 2$ os pares fora de [ordem](#def-b2-structures-generated) são $(3,1)$, $(3,2)$, $(5,4)$, $(5,1)$, $(5,2)$, $(4,1)$, $(4,2)$: sete deles, e $(-1)^7 = -1$. *Pelas [transposições](#def-b2-structures-sn):* $\sigma = (1\,4)(1\,3)(2\,5)$, três fatores, $(-1)^3 = -1$. Três cálculos, uma só paridade: a unicidade do [Teorema 1.21](#thm-b2-structures-signature) garante que nenhum esquema de contagem possa fazê-los discordar — e é exatamente isso que torna $\varepsilon$ utilizável como invariante (veja o problema de fim de semana).

**Observação 1.24 (Para onde vai a assinatura daqui).**

A assinatura é a semente de três colheitas posteriores: ela constrói o determinante e sua regra do produto no [Capítulo 2](https://one-course.com/books/math/4/pt/chapter/2-algebra-linear#ch-b2-linalg); alimenta invariantes de paridade para quebra-cabeças combinatórios (o problema de fim de semana deste capítulo resolve com ela o jogo dos quinze); e os grupos alternados $A_n$ que ela define tornam-se centrais no volume do terceiro ano de graduação, onde sua simplicidade para $n \geq 5$ explica por que as equações de grau $5$ não têm solução por radicais.

## 1.5 Anéis, ideais, quocientes

**Definição 1.25 (Ideal).**

Seja $A$ um anel comutativo. Um *ideal* $I
\subseteq A$ é um subgrupo aditivo tal que $a x \in I$ para todos $a \in A$, $x \in I$. Os núcleos de morfismos de anéis são ideais; $I = A$ se e somente se $1 \in I$, se e somente se $I$ contém uma unidade. O ideal *[gerado](#def-b2-structures-generated)* por $x$ é $xA = \{xa\}$ (um ideal *principal*).

**Teorema 1.26 (Ideais de Z\ZZ e de K[X]K[X]K[X]).**

Todo [ideal](#def-b2-structures-ideal) de $\Z$ é $n\Z$ para um único $n \in \N$; todo [ideal](#def-b2-structures-ideal) de $K[X]$ ($K$ um corpo) é $P\,K[X]$ para um único $P$ mônico (ou nulo). Por consequência, existem mdc’s nos dois anéis, com relações de Bézout: $x\Z +
y\Z = \gcd(x,y)\Z$, e analogamente para polinômios.

**Demonstração.** Para $\Z$ esse era o teorema dos subgrupos do volume do primeiro ano de graduação (um [ideal](#def-b2-structures-ideal) é em particular um subgrupo, e $n\Z$ é um [ideal](#def-b2-structures-ideal)). Para $K[X]$: seja $I \neq \{0\}$ um [ideal](#def-b2-structures-ideal) e $P \in I$ não nulo de grau mínimo, normalizado mônico. Para $F \in I$, a divisão euclidiana $F = PQ + R$ dá $R = F - PQ \in I$ com $\deg R < \deg P$: a minimalidade obriga $R
= 0$, logo $I = P\,K[X]$. Unicidade: dois geradores mônicos dividem-se mutuamente. Os enunciados de Bézout são a igualdade do [ideal](#def-b2-structures-ideal) $x\Z +
y\Z$ (resp. de seu análogo polinomial) com o [ideal](#def-b2-structures-ideal) principal do mdc — a própria definição de mdc usada no primeiro ano, agora reconhecida como um enunciado sobre [ideais](#def-b2-structures-ideal). ∎

**Exemplo 1.27 (Um mdc de polinômios, de duas maneiras).**

Calcule $\gcd(X^3 - 1,\ X^2 - 1)$ em $\Q[X]$. *Por Euclides:*

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

logo o mdc é $X - 1$, e a substituição para trás dá a relação de Bézout

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

*Pelos [ideais](#def-b2-structures-ideal):* o [ideal](#def-b2-structures-ideal) $(X^3 - 1)\Q[X] + (X^2 - 1)\Q[X]$ é principal ([Teorema 1.26](#thm-b2-structures-principal)); ele contém $X -
1$ (a fórmula acima) e está contido em $(X - 1)\Q[X]$ (ambos os geradores se anulam em $1$, logo são múltiplos de $X - 1$): o gerador mônico é $X - 1$. A lição final: o ponto de vista dos [ideais](#def-b2-structures-ideal) identifica o mdc *sem dividir* — as raízes comuns localizam o [ideal](#def-b2-structures-ideal), e Euclides apenas o certifica.

**Definição 1.28 (Anel quociente Z/nZ\Z/n\ZZ/nZ, revisitado).**

Para um [ideal](#def-b2-structures-ideal) $I$ de $A$, a relação $x \sim y \iff x - y \in I$ é uma equivalência compatível com $+$ e $\times$; o [conjunto quociente](#def-b2-structures-quotient) $A/I$ herda uma estrutura de anel — o *anel quociente* — que faz de $\pi \colon A \to A/I$ um morfismo de núcleo $I$. Para $A = \Z$, $I = n\Z$ isso é o $\Z/n\Z$ do volume do primeiro ano de graduação, agora com sua propriedade universal: todo morfismo que anula $I$ se fatora por $A/I$.

**Teorema 1.29 (Teorema chinês dos restos, forma anelar).**

Se $\gcd(m, n) = 1$, a aplicação

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

é um isomorfismo de anéis. Por consequência, $\varphi(mn) = \varphi(m)\varphi(n)$ para $m, n$ coprimos, e

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

**Demonstração.** A aplicação é um morfismo de anéis bem definido (as compatibilidades são imediatas). Injetividade: $x \equiv 0$ módulo $m$ e módulo $n$ com $\gcd(m,n) = 1$ obriga $mn \mid x$ (Gauss). Sobrejetividade: os dois lados têm $mn$ elementos, logo a injetividade basta (cardinalidades finitas iguais) — ou explicitamente: a partir de uma relação de Bézout $um +
vn = 1$, a classe de

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

é levada em $(a \bmod m,\ b \bmod n)$, pois $vn = 1 - um \equiv 1
\pmod m$ faz $x \equiv a \pmod m$, e simetricamente módulo $n$ — a receita usada numericamente no [Exemplo 1.30](#ex-b2-structures-crtinverse). As unidades correspondem a pares de unidades (as unidades de um anel produto são os pares de unidades), logo $\varphi(mn) =
\varphi(m)\varphi(n)$. Para uma potência de primo, $\varphi(p^k) = p^k -
p^{k-1}$ (os não invertíveis módulo $p^k$ são os múltiplos de $p$); a multiplicatividade monta a fórmula do produto. ∎

**Exemplo 1.30 (Invertendo o isomorfismo chinês).**

Tome $m = 8$, $n = 9$. A inversa do isomorfismo torna-se explícita pelos dois *idempotentes*: procure $u \equiv 1 \pmod 8$, $u \equiv 0 \pmod 9$ e $v \equiv 0 \pmod 8$, $v \equiv 1 \pmod
9$. De $u = 9k \equiv 1 \pmod 8$: $k \equiv 1$, logo $u = 9$; de $v = 8k \equiv 1 \pmod 9$: $-k \equiv 1$, $k \equiv 8$, logo $v =
64$. Então a classe de $x = 9a + 64b$ módulo $72$ é a única solução de $x \equiv a \pmod 8$, $x \equiv b \pmod 9$: para $a =
3$, $b = 5$ obtém-se $27 + 320 = 347 \equiv 59 \pmod{72}$ — exatamente o valor intermediário encontrado por substituição no [Exercício 1.8](#exo-b2-structures-8). A lição final: $u$ e $v$ satisfazem $u + v \equiv 1$, $uv \equiv 0$, $u^2 \equiv u$, $v^2
\equiv v$ módulo $72$; são as imagens de $(1, 0)$ e $(0,
1)$, e toda decomposição chinesa é, no fundo, uma decomposição de $1$ em idempotentes ortogonais.

**Teorema 1.31 (Euler; Fermat revisitado).**

As unidades de $\Z/n\Z$ formam um grupo de ordem $\varphi(n)$; portanto, para $\gcd(a, n) = 1$:

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

e o pequeno teorema de Fermat é o caso $n = p$ primo, agora a uma linha do teorema de Lagrange.

**Demonstração.** As classes invertíveis são exatamente as dos inteiros coprimos com $n$ (volume do primeiro ano de graduação): há $\varphi(n)$ delas, e formam um grupo para a multiplicação. Lagrange ([Teorema 1.14](#thm-b2-structures-lagrange)): todo elemento elevado à [ordem](#def-b2-structures-generated) do grupo dá a identidade. ∎

**Exemplo 1.32 (Um grupo de unidades sem gerador).**

O grupo $(\Z/15\Z)^*$ tem $\varphi(15) = \varphi(3)\varphi(5)
= 8$ elementos. Ele é [cíclico](#def-b2-structures-generated)? Calcule as [ordens](#def-b2-structures-generated) usando o isomorfismo chinês $(\Z/15\Z)^* \simeq (\Z/3\Z)^* \times (\Z/5\Z)^*$ (uma unidade módulo $15$ é um par de unidades): os fatores têm [ordens](#def-b2-structures-generated) $2$ e $4$, de modo que a ordem de todo elemento divide $\operatorname{lcm}(2, 4) = 4 < 8$ — nenhum elemento gera o grupo. Concretamente:

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

[ordens](#def-b2-structures-generated) $4, 2, 4, 2, 2$ e nunca $8$. Contraste com [Exercício 1.10](#exo-b2-structures-10): $(\Z/p\Z)^*$ *é* [cíclico](#def-b2-structures-generated) para $p$ primo, porque aí o grupo de unidades vive dentro de um corpo. O teorema de Euler continua valendo com expoente $\varphi(15) = 8$, mas o verdadeiro expoente universal aqui é $4$ — Euler dá uma cota superior, nem sempre a exata.

**Definição 1.33 (Álgebra).**

Uma *$K$-álgebra* é um $K$-espaço vetorial $A$ munido de uma estrutura de anel cuja multiplicação é $K$-bilinear. Exemplos: $K[X]$, $\mathcal{M}_n(K)$, $\mathcal{L}(E)$, espaços de funções $\mathcal{F}(X, K)$, $\C$ como $\R$-álgebra. Os morfismos de álgebras são os morfismos de anéis lineares; a *avaliação* $P \mapsto P(u)$ de $K[X]$ em $\mathcal{L}(E)$ (ou $\mathcal{M}_n(K)$) é o exemplo central, motor do [Capítulo 3](https://one-course.com/books/math/4/pt/chapter/3-reducao-de-endomorfismos#ch-b2-reduction).

**Exemplo 1.34 (Um morfismo de avaliação e seu núcleo).**

Tome $A = \begin{pmatrix}0 & 1\\ 0 & 0\end{pmatrix}$ e a avaliação $\varepsilon_A \colon \R[X] \to \mathcal{M}_2(\R)$, $P \mapsto P(A)$. Como $A^2 = 0$,

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

(só sobrevivem os termos constante e linear de $P$). Logo $\ker\varepsilon_A = \{P : P(0) = P'(0) = 0\} = X^2\,\R[X]$: um [ideal](#def-b2-structures-ideal) principal, exatamente como prevê o [Teorema 1.26](#thm-b2-structures-principal), [gerado](#def-b2-structures-generated) pelo polinômio mônico $X^2$ de menor grau no núcleo — o *polinômio minimal* de $A$, estrela do [Capítulo 3](https://one-course.com/books/math/4/pt/chapter/3-reducao-de-endomorfismos#ch-b2-reduction). A imagem é a [álgebra](#def-b2-structures-algebra) comutativa de dimensão dois $\{aI + bA\}$: os morfismos de avaliação encolhem o espaço $\R[X]$, de dimensão infinita, sobre [álgebras](#def-b2-structures-algebra) pequenas e calculáveis.

**Observação 1.35 (Perspectivas: três melodias a escutar).**

Três ideias estruturais deste capítulo reaparecem ao longo do volume, a cada vez com orquestração mais pesada. *A fatoração por um quociente* ([Definição 1.3](#def-b2-structures-quotient)): ela constrói $\Z/n\Z$ aqui, define aplicações sobre os conjuntos de soluções de sistemas lineares no [Capítulo 2](https://one-course.com/books/math/4/pt/chapter/2-algebra-linear#ch-b2-linalg), e sustenta silenciosamente todo argumento de “bem definido nas classes”. *Os invariantes*: a assinatura é um morfismo com valores em $\{\pm1\}$ que nenhum movimento legal consegue driblar — a mesma lógica dá a regra do produto do determinante ([Capítulo 2](https://one-course.com/books/math/4/pt/chapter/2-algebra-linear#ch-b2-linalg)), a invariância do traço por semelhança e as quantidades conservadas do [Capítulo 16](https://one-course.com/books/math/4/pt/chapter/16-equacoes-diferenciais#ch-b2-diffeq). *Contar contra uma estrutura*: Lagrange conta por classes laterais, a dimensão conta por bases ([Capítulo 2](https://one-course.com/books/math/4/pt/chapter/2-algebra-linear#ch-b2-linalg)), a multiplicidade conta por graus de polinômios ([Capítulo 3](https://one-course.com/books/math/4/pt/chapter/3-reducao-de-endomorfismos#ch-b2-reduction)); sempre que uma cota parece milagrosa, alguma partição ou graduação está fazendo a contagem.

**Observação 1.36 (Armadilhas comuns).**

Quatro clássicas. (i) Uma aplicação definida sobre um quociente precisa ser verificada *bem definida*: “$\overline x \mapsto$ (fórmula em $x$)” só é legítimo se a fórmula for constante nas classes — a compatibilidade da [Definição 1.3](#def-b2-structures-quotient), e não uma formalidade. (ii) $\operatorname{ord}(ab) =
\operatorname{lcm}(\operatorname{ord}a, \operatorname{ord}b)$ é *falso* em geral, mesmo para elementos que comutam ($a$ e $a^{-1}$); o [Exercício 1.4](#exo-b2-structures-4) dá o enunciado correto para [ordens](#def-b2-structures-generated) coprimas e elementos que comutam, e os [ciclos](#def-b2-structures-sn) disjuntos dão a versão correta para permutações. (iii) A [enumerabilidade](#def-b2-structures-countable) sobrevive a *uniões* [enumeráveis](#def-b2-structures-countable) e a *produtos* finitos, mas não a produtos [enumeráveis](#def-b2-structures-countable): $\{0,1\}^{\N}$ é não [enumerável](#def-b2-structures-countable) ([Exercício 1.3](#exo-b2-structures-3)) embora cada fator tenha dois elementos. (iv) Cantor–Bernstein precisa apenas de injeções nos dois sentidos, mas a bijeção que ele constrói é em geral descontínua e não explícita — não espere uma fórmula ([Exemplo 1.11](#ex-b2-structures-cbexample)).

**Observação 1.37 (Onde este capítulo é usado).**

Em quase toda parte. A assinatura constrói os determinantes ([Capítulo 2](https://one-course.com/books/math/4/pt/chapter/2-algebra-linear#ch-b2-linalg)); o morfismo de avaliação $P \mapsto P(u)$ e os [ideais](#def-b2-structures-ideal) principais de $K[X]$ produzem os polinômios minimais e as decomposições em núcleos do [Capítulo 3](https://one-course.com/books/math/4/pt/chapter/3-reducao-de-endomorfismos#ch-b2-reduction); a [enumerabilidade](#def-b2-structures-countable) é o palco em que o [Capítulo 21](https://one-course.com/books/math/4/pt/chapter/21-probabilidade-em-espacos-enumeraveis#ch-b2-proba) atua (probabilidade sobre espaços [enumeráveis](#def-b2-structures-countable)) e a razão pela qual a topologia não para de produzir conjuntos densos [enumeráveis](#def-b2-structures-countable) ([Capítulo 4](https://one-course.com/books/math/4/pt/chapter/4-topologia-dos-espacos-metricos#ch-b2-metric)). A construção do quociente $A/I$ é reutilizada no volume do terceiro ano de graduação para construir corpos $K[X]/(P)$ e, a partir deles, a teoria de Galois: a propriedade universal demonstrada aqui é usada lá palavra por palavra.

## 1.6 Exercícios

**Exercício 1.1 ★.**

Quais dos conjuntos seguintes são [enumeráveis](#def-b2-structures-countable)? O conjunto das partes finitas de $\N$; o conjunto de *todas* as partes de $\N$; $\R \setminus \Q$; o conjunto dos polinômios com coeficientes racionais; o conjunto das sequências de $0$ e de $1$ nulas a partir de certa ordem.

**Solução de Exercício 1.1.**

*Partes finitas de $\N$:* [enumerável](#def-b2-structures-countable) — o conjunto das partes de $\intint{0}{n}$ é finito, e as partes finitas formam a união [enumerável](#def-b2-structures-countable) sobre $n$ desses conjuntos ([Proposição 1.6](#prop-b2-structures-countablestable) (3)); infinito, pois contém todos os conjuntos unitários.

*Todas as partes de $\N$:* não [enumerável](#def-b2-structures-countable), pelo teorema de Cantor ([Teorema 1.9](#thm-b2-structures-cantor) (1) com $E = \N$).

*$\R \setminus \Q$:* não [enumerável](#def-b2-structures-countable) — caso contrário $\R = \Q \cup
(\R\setminus\Q)$ seria uma união de dois [conjuntos enumeráveis](#def-b2-structures-countable), contradizendo [Teorema 1.9](#thm-b2-structures-cantor) (2).

*Polinômios sobre $\Q$:* [enumerável](#def-b2-structures-countable) — os polinômios de grau $\leq n$ injetam-se em $\Q^{n+1}$ (produtos finitos de [conjuntos enumeráveis](#def-b2-structures-countable)), e depois tome a união sobre $n$.

*Sequências binárias nulas a partir de certa ordem:* [enumerável](#def-b2-structures-countable) — elas estão em bijeção com as partes finitas de $\N$ (o suporte).

**Exercício 1.2 ★.**

Em $\mathfrak{S}_7$, sejam $\sigma = (1\,4\,2\,6)(3\,5)$ e $\tau =
(2\,3\,7)$. Calcule $\sigma\tau$ e $\tau\sigma$ na forma de [ciclos](#def-b2-structures-sn) disjuntos, as [ordens](#def-b2-structures-generated) e as assinaturas das quatro permutações, e $\sigma^{2026}$.

**Solução de Exercício 1.2.**

Calcule elemento por elemento, aplicando primeiro o fator da direita. $\sigma\tau$ leva $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),
$$

um $7$-ciclo. Do mesmo modo $\tau\sigma$ leva $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),
$$

também um $7$-ciclo (como esperado: $\sigma\tau$ e $\tau\sigma$ são conjugadas, logo têm o mesmo tipo de [ciclo](#def-b2-structures-sn)).

[Ordens](#def-b2-structures-generated) e assinaturas: $\sigma$ tem tipo de [ciclo](#def-b2-structures-sn) $(4,2)$: ordem $\operatorname{lcm}(4,2) = 4$, assinatura $(-1)^3(-1)^1 = +1$; $\tau$ é um $3$-ciclo: ordem $3$, assinatura $+1$; os dois produtos são $7$-ciclos: ordem $7$, assinatura $(-1)^6 = +1$.

$\sigma^{2026}$: $2026 = 4 \times 506 + 2$, logo $\sigma^{2026} =
\sigma^2 = (1\,2)(4\,6)$ (eleve ao quadrado o $4$-ciclo; a [transposição](#def-b2-structures-sn) desaparece ao quadrado).

**Exercício 1.3 ★.**

Construa injeções explícitas mostrando que $\mathcal{P}(\N)$, $\intcc{0}{1}$ e o conjunto $\{0,1\}^{\N}$ das sequências binárias são dois a dois [equipotentes](#def-b2-structures-countable) *(expansões binárias nos dois sentidos; Cantor–Bernstein absorve o incômodo da dupla representação)*.

**Solução de Exercício 1.3.**

$\{0,1\}^{\N} \to \mathcal{P}(\N)$: uma sequência é levada em seu suporte — uma bijeção (funções indicadoras), sem necessidade de teorema.

$\{0,1\}^{\N} \to \intcc{0}{1}$: a aplicação em base $3$ dada por $(a_n) \mapsto
\sum 2a_n 3^{-n-1}$ é injetiva (duas sequências distintas diferem pela primeira vez no posto $N$; as caudas não podem compensar uma diferença de $2\cdot
3^{-N-1}$, pois $\sum_{n > N} 2\cdot 3^{-n-1} = 3^{-N-1} <
2\cdot3^{-N-1}$).

$\intcc{0}{1} \to \{0,1\}^{\N}$: expansão binária, escolhendo (digamos) a expansão que não termina numa sequência infinita de $1$: injetiva.

Por Cantor–Bernstein ([Teorema 1.10](#thm-b2-structures-cantorbernstein)) aplicado às duas últimas injeções, $\intcc{0}{1}$ e $\{0,1\}^{\N}$ são [equipotentes](#def-b2-structures-countable), logo os três conjuntos o são.

**Exercício 1.4 ★.**

Seja $G$ um grupo e $a, b \in G$ elementos que comutam, de [ordens](#def-b2-structures-generated) finitas coprimas $m$ e $n$. Prove que $\operatorname{ord}(ab) =
mn$. Mostre, por um exemplo em $\mathfrak{S}_3$, que a comutatividade é essencial.

**Solução de Exercício 1.4.**

Sejam $c = ab = ba$ e $d = \operatorname{ord}(c)$. Primeiro $c^{mn} =
a^{mn} b^{mn} = e$ (a comutatividade permite separar a potência), logo $d
\mid mn$. Reciprocamente, $c^d = e$ dá $a^d = b^{-d}$; esse elemento pertence a $\langle a\rangle \cap \langle b\rangle$, um subgrupo cuja ordem divide tanto $m$ quanto $n$ (Lagrange em cada [grupo cíclico](#def-b2-structures-generated)), e portanto é trivial: $a^d = b^d = e$, logo $m \mid d$ e $n \mid d$, e pela coprimalidade $mn \mid d$. Portanto $d = mn$.

Em $\mathfrak{S}_3$: tome $a = (1\,2)$ (ordem $2$) e $b =
(1\,2\,3)$ (ordem $3$), de [ordens](#def-b2-structures-generated) coprimas, que não comutam: $ab =
(2\,3)$ tem ordem $2 \neq 6$ — de fato $\mathfrak{S}_3$ não tem elemento de ordem $6$. A comutatividade é essencial.

**Exercício 1.5 ★★.**

Seja $G$ um grupo finito de [ordem](#def-b2-structures-generated) par. Prove que $G$ contém um elemento de ordem $2$. *(Emparelhe cada elemento com seu inverso; conte os que se emparelham consigo mesmos.)*

**Solução de Exercício 1.5.**

Emparelhe cada $x \in G$ com $x^{-1}$. Os pares $\{x, x^{-1}\}$ com $x \neq x^{-1}$ têm dois elementos e particionam sua união; os elementos restantes são exatamente aqueles com $x = x^{-1}$, isto é, $x^2 =
e$. Como $\abs G$ é par e os pares de dois elementos cobrem um número par de elementos, o conjunto $\{x : x^2 = e\}$ tem cardinalidade par; ele contém $e$, logo contém ao menos um outro elemento $x \neq
e$ — um elemento de ordem $2$.

**Exercício 1.6 ★★.**

Prove que $A_n$ ($n \geq 3$) é [gerado](#def-b2-structures-generated) pelos $3$-ciclos. *(Um produto de duas [transposições](#def-b2-structures-sn) é um $3$-ciclo ou um produto de dois $3$-ciclos.)*

**Solução de Exercício 1.6.**

Todo elemento de $A_n$ é um produto de um número par de [transposições](#def-b2-structures-sn) ([Teorema 1.21](#thm-b2-structures-signature): decomponha em [transposições](#def-b2-structures-sn); a contagem é par, pois a assinatura vale $+1$). Basta escrever cada produto de duas [transposições](#def-b2-structures-sn) com $3$-ciclos:

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

(verifique avaliando), e $(a\,b)(a\,b) = \mathrm{id}$. Logo os $3$-ciclos geram $A_n$.

**Exercício 1.7 ★★.**

Determine todos os morfismos de grupos: de $(\Q, +)$ em $(\Z, +)$; de $(\Z/n\Z, +)$ em $(\Z/m\Z, +)$ *(conte-os: $\gcd(m,n)$)*; de $(\Q, +)$ em $(\Q_+^*, \times)$.

**Solução de Exercício 1.7.**

*$(\Q,+) \to (\Z,+)$:* apenas o morfismo nulo. Para qualquer $x$ e todo $n \geq 1$, $f(x) = n f\bigl(\frac xn\bigr)$ é divisível por $n$ em $\Z$; o único inteiro divisível por todo $n$ é $0$, logo $f(x) = 0$ para todo $x$.

*$(\Z/n\Z, +) \to (\Z/m\Z, +)$:* um morfismo fica determinado por $c = f(\overline 1)$, que deve satisfazer $n c \equiv 0 \pmod m$, isto é, $c$ é múltiplo de $\frac{m}{\gcd(m,n)}$; há $\gcd(m,n)$ tais classes, e cada escolha define de fato um morfismo (fatore $k \mapsto kc$ por $\Z/n\Z$ pela propriedade universal).

*$(\Q, +) \to (\Q_+^*, \times)$:* apenas o trivial. Se $f(x) = y$, então, para todo $n$, $y = f(n \cdot \frac xn) =
f(\frac xn)^n$ é uma potência $n$-ésima em $\Q_+^*$. Mas um racional $y \neq 1$ não pode ser uma potência $n$-ésima para todo $n$: algum primo aparece em $y$ com um expoente não nulo $v$, e $n \nmid v$ para $n > \abs
v$ (os expoentes das potências $n$-ésimas são múltiplos de $n$, pela unicidade da fatoração). Logo $f \equiv 1$.

**Exercício 1.8 ★★.**

Usando o teorema chinês dos restos, calcule $\varphi(360)$, determine todos os $x$ com $x \equiv 3 \pmod 8$, $x \equiv 5 \pmod 9$ e $x
\equiv 2 \pmod 5$, e calcule os dois últimos algarismos de $3^{2026}$ *(Euler módulo $100$; atenção: trabalhe módulo $4$ e módulo $25$)*.

**Solução de Exercício 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$.

Sistema: módulos $8, 9, 5$ dois a dois coprimos, produto total $360$. De $x
\equiv 3 \pmod 8$ e $x \equiv 5 \pmod 9$: $x = 3 + 8k$ com $3 +
8k \equiv 5 \pmod 9$, isto é, $-k \equiv 2$, $k \equiv -2 \equiv 7
\pmod 9$: $x \equiv 3 + 56 = 59 \pmod{72}$. Em seguida $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}$.

Dois últimos algarismos de $3^{2026}$: módulo $4$, $3^{2026} = 9^{1013} \equiv
1$. Módulo $25$: $\varphi(25) = 20$ e $2026 = 20\cdot101 + 6$, logo $3^{2026} \equiv 3^6 = 729 \equiv 4 \pmod{25}$. Resolva $x \equiv 1
\pmod 4$, $x \equiv 4 \pmod{25}$: $x = 4 + 25k \equiv 1 \pmod 4$ dá $k \equiv 1 \pmod 4$: $x \equiv 29 \pmod{100}$. Os dois últimos algarismos são $29$.

**Exercício 1.9 ★★★.**

Prove que todo domínio de integridade finito é um corpo. Deduza que $\Z/n\Z$ é um corpo se e somente se $n$ é primo (mais uma vez).

**Solução de Exercício 1.9.**

Seja $A$ um domínio de integridade finito e $a \in A$, $a \neq 0$. A aplicação $x \mapsto ax$ é injetiva ($ax = ay \implies a(x - y) = 0
\implies x = y$, sem divisores de zero); uma aplicação injetiva de um conjunto finito nele mesmo é sobrejetiva (volume do primeiro ano de graduação, a equivalência da casa dos pombos). Logo $1 = ab$ para algum $b$: todo elemento não nulo é invertível, e $A$ é um corpo.

$\Z/n\Z$: se $n$ é primo, ele é um domínio de integridade ($n \mid ab
\implies n \mid a$ ou $n \mid b$, lema de Euclides), finito, logo um corpo; se $n = rs$ é composto, $\overline r\,\overline s =
\overline 0$ exibe divisores de zero.

**Exercício 1.10 ★★★.**

(Um clássico) Seja $K$ um corpo e $G$ um subgrupo *finito* de $(K^*, \times)$. Prove que $G$ é [cíclico](#def-b2-structures-generated). *Sugestão: seja $m$ a ordem máxima entre os elementos de $G$; mostre que a ordem de todo elemento divide $m$ (usando o [Exercício 1.4](#exo-b2-structures-4) em partes coprimas adequadas), de modo que todo $G$ satisfaz $x^m = 1$; conte as raízes de $X^m - 1$.* Em particular, $(\Z/p\Z)^*$ é [cíclico](#def-b2-structures-generated).

**Solução de Exercício 1.10.**

Seja $m = \max\{\operatorname{ord}(x) : x \in G\}$, atingida em $a$.

*Afirmação: todo $x \in G$ tem ordem que divide $m$.* Suponha que algum $x$ tenha ordem $q$ com $q \nmid m$: então alguma potência de primo $p^k$ divide $q$ mas não $m$. Escreva $m = p^j m'$ com $p \nmid m'$ e $j
< k$. O elemento $a^{p^j}$ tem ordem $m'$; o elemento $x^{q/p^k}$ tem ordem $p^k$; essas [ordens](#def-b2-structures-generated) são coprimas e os dois elementos comutam ($G \subseteq K^*$ é abeliano), logo, pelo [Exercício 1.4](#exo-b2-structures-4), seu produto tem ordem $p^k m' > p^j m'
= m$: contradiz a maximalidade.

Assim todo $x \in G$ satisfaz $x^m = 1$: o polinômio $X^m - 1$ tem ao menos $\abs G$ raízes no corpo $K$, donde $\abs G \leq m$ (um polinômio não nulo de grau $m$ tem no máximo $m$ raízes, volume do primeiro ano de graduação). Mas $m = \operatorname{ord}(a) \leq \abs G$ por Lagrange. Logo $m = \abs G$ e $\langle a \rangle$, de cardinalidade $m =
\abs G$, é todo o $G$: [cíclico](#def-b2-structures-generated).

Para $K = \Z/p\Z$: $(\Z/p\Z)^*$ é um subgrupo finito de $K^*$, logo [cíclico](#def-b2-structures-generated) (de ordem $p - 1$).

**Exercício 1.11 ★★★.**

Prove que o grupo $(\Q, +)$ não é [cíclico](#def-b2-structures-generated) e, pior: não é sequer finitamente [gerado](#def-b2-structures-generated). Prove, por outro lado, que todo subgrupo finitamente [gerado](#def-b2-structures-generated) de $(\Q, +)$ é [cíclico](#def-b2-structures-generated).

**Solução de Exercício 1.11.**

*Não [cíclico](#def-b2-structures-generated):* o subgrupo $\langle \frac pq\rangle$ consiste nos múltiplos inteiros de $\frac pq$, todos com denominador que divide $q$ (na forma irredutível); ele portanto não contém $\frac{1}{2q}$. Nenhum gerador único alcança os denominadores ilimitados de $\Q$.

*Não finitamente [gerado](#def-b2-structures-generated):* o subgrupo [gerado](#def-b2-structures-generated) por $\frac{p_1}{q_1}, \dots, \frac{p_k}{q_k}$ consiste nos racionais cujos denominadores dividem $Q = q_1 \cdots q_k$ (as combinações inteiras têm denominador que divide $Q$): ele não contém $\frac{1}{2Q}$.

*Os subgrupos finitamente [gerados](#def-b2-structures-generated) são [cíclicos](#def-b2-structures-generated):* com $Q$ como acima, o subgrupo $H = \langle \frac{p_1}{q_1}, \dots,
\frac{p_k}{q_k}\rangle$ está contido em $\frac{1}{Q}\Z$. A aplicação $x
\mapsto Qx$ é um isomorfismo de $\frac1Q\Z$ sobre $\Z$ que leva $H$ em um subgrupo de $\Z$, o qual é $n\Z$ para algum $n$ (volume do primeiro ano de graduação): logo $H = \frac{n}{Q}\Z$ é [cíclico](#def-b2-structures-generated), [gerado](#def-b2-structures-generated) por $\frac nQ$.

**Exercício 1.12 ★★.**

(Critério de Dedekind) Prove que todo conjunto infinito contém um subconjunto [enumerável](#def-b2-structures-countable) e deduza que um conjunto $E$ é infinito se e somente se é [equipotente](#def-b2-structures-countable) a uma parte própria de si mesmo. *(Para a implicação direta, desloque de um passo um subconjunto [enumerável](#def-b2-structures-countable); para a recíproca, lembre-se do princípio da casa dos pombos.)*

**Solução de Exercício 1.12.**

*Um subconjunto [enumerável](#def-b2-structures-countable).* Seja $E$ infinito. Construa $a_0,
a_1, a_2, \dots$ por indução: $E$ é não vazio, escolha $a_0 \in E$; se $a_0, \dots, a_n$ já foram escolhidos, $E \setminus \{a_0, \dots,
a_n\}$ é não vazio ($E$ não é finito), escolha $a_{n+1}$ aí. Os $a_n$ são dois a dois distintos por construção, logo $A = \{a_n : n
\in \N\}$ é um subconjunto [enumerável](#def-b2-structures-countable) de $E$.

*$\implies$ infinito é [equipotente](#def-b2-structures-countable) a uma parte própria.* Defina $f \colon E \to E \setminus \{a_0\}$ por $f(a_n) = a_{n+1}$ e $f(x) = x$ para $x \notin A$. Ela é injetiva (as duas peças são injetivas com imagens disjuntas) e sobrejetiva sobre $E \setminus
\{a_0\}$: todo $a_{n+1}$ é atingido, todo $x \notin A$ é atingido. Logo $E$ é [equipotente](#def-b2-structures-countable) à parte própria $E \setminus \{a_0\}$.

*Recíproca.* Se $E$ é finito e $g \colon E \to F$ é uma bijeção sobre $F \subseteq E$ com $F \neq E$, então $g$ é uma injeção de $E$ nele mesmo que não é sobrejetiva, contradizendo o princípio da casa dos pombos (volume do primeiro ano de graduação: uma aplicação injetiva de um conjunto finito nele mesmo é bijetiva). Logo um conjunto [equipotente](#def-b2-structures-countable) a uma parte própria é infinito.

## 1.7 Problema: o jogo dos quinze

O jogo dos quinze é um tabuleiro $4 \times 4$ com quinze peças deslizantes numeradas de $1$ a $15$ e uma casa vazia; um movimento faz deslizar para a casa vazia uma das peças adjacentes a ela. Na década de 1890, Sam Loyd popularizou o quebra-cabeça oferecendo $1000 a quem conseguisse trocar as peças $14$ e $15$ e devolver todas as demais ao seu lugar. Ninguém jamais recebeu o prêmio, e este problema de fim de semana demonstra as duas metades da razão: a assinatura de [Teorema 1.21](#thm-b2-structures-signature) proíbe a troca de Loyd e — a metade construtiva, mais difícil — *tudo* o que a assinatura permite é de fato realizável. O enunciado completo é o teorema de Johnson–Story (1879).

![A configuração resolvida e a configuração 14–15 de Sam Loyd. A pergunta de $1000: podem os movimentos legais transformar o tabuleiro da direita no da esquerda?](https://one-course.com/images/onecourse/chapters/math-4/b2-structures/fig-ea836c026666.svg)

![A configuração resolvida e a configuração 14–15 de Sam Loyd. A pergunta de $1000: podem os movimentos legais transformar o tabuleiro da direita no da esquerda?](https://one-course.com/images/onecourse/chapters/math-4/b2-structures/fig-5705907be6e8.svg)

*A configuração resolvida e a configuração $14$–$15$ de Sam Loyd. A pergunta de $1000: podem os movimentos legais transformar o tabuleiro da direita no da esquerda?*

**Problema 1.1.**

Problema de fim de semana — o teorema de resolubilidade de Johnson–Story

Numere as casas de $1$ a $16$ na ordem de leitura (da esquerda para a direita, de cima para baixo), de modo que a casa $k$ fique na linha $i$ e na coluna $j$ com $k
= 4(i - 1) + j$. A casa $16$ (canto inferior direito) é a *casa natural* da casa vazia; tratamos a casa vazia como uma décima sexta peça, escrita $b$ e identificada com o número $16$. Uma *configuração* é uma bijeção $\sigma \colon \intint1{16}
\to \intint1{16}$, casa $\mapsto$ conteúdo; a configuração *resolvida* é $\sigma = \mathrm{id}$. Em todo o problema, $\varepsilon$ é a assinatura de [Teorema 1.21](#thm-b2-structures-signature), e duas casas são *adjacentes* quando compartilham uma aresta do tabuleiro.

**Parte I — Configurações, movimentos, assinaturas.**

1. Justifique que as configurações são exatamente os elementos de $\mathfrak{S}_{16}$ , de modo que há $16! =  20\,922\,789\,888\,000$ delas, e que o número de movimentos legais a partir de uma dada configuração é $2$ , $3$ ou $4$ , conforme a casa vazia esteja num canto, numa borda ou no interior.
2. Seja $\sigma$ uma configuração, $p = \sigma^{-1}(16)$ a casa do vazio e $c$ uma casa adjacente a $p$ . Mostre que deslizar a peça de $c$ para $p$ produz a configuração $\sigma' = \sigma \circ \tau$ com $\tau =  (p\ c)$ , e deduza que todo movimento inverte a assinatura: $\varepsilon(\sigma') = -\varepsilon(\sigma)$ .
3. Pinte o tabuleiro como um damas: $\chi(k) = (-1)^{i+j}$ para a casa $k$ na linha $i$ e coluna $j$ . Mostre que todo movimento inverte $\chi(\text{casa do vazio})$ , e deduza que uma sequência de movimentos que devolve o vazio à casa de partida tem comprimento par.
4. Mostre que $$I(\sigma) = \varepsilon(\sigma)\,  \chi\bigl(\sigma^{-1}(16)\bigr)$$ é invariante por todo movimento legal, e calcule $I(\mathrm{id})$.

**Parte II — A recompensa de Loyd: o invariante em ação.**

5. A configuração $\sigma_L$ de Loyd coincide com a resolvida, exceto que as casas $14$ e $15$ contêm as peças $15$ e $14$ . Calcule $I(\sigma_L)$ e conclua que nenhuma sequência de movimentos liga $\sigma_L$ à configuração resolvida: os $1000 de Loyd nunca correram risco.
6. Mostre que exatamente metade de todas as configurações satisfaz $I =  +1$ : $\abs{\{\sigma : I(\sigma) = +1\}} = 16!/2$ . *(Para uma casa vazia fixada, emparelhe as configurações compondo com uma [transposição](#def-b2-structures-sn) fixa de duas outras casas.)*
7. Mostre que todo movimento é desfeito por um movimento legal, que “ $\sigma'$ é alcançável a partir de $\sigma$ por movimentos legais” é uma relação de equivalência, e que a classe $R$ da configuração resolvida satisfaz $R \subseteq \{I = +1\}$ . Conclua que existem ao menos duas classes.
8. Suponha que o vazio esteja em casa: $\sigma(16) = 16$ . Mostre que $I(\sigma) = \varepsilon(\rho)$ , em que $\rho \in  \mathfrak{S}_{15}$ é a restrição de $\sigma$ às casas $1, \dots, 15$ , e que toda configuração pode ser levada por movimentos legais a uma com o vazio em casa. Conclua: para provar $R = \{I = +1\}$ basta realizar toda permutação *par* das quinze casas não naturais por uma sequência de movimentos que começa e termina com o vazio em casa.

**Parte III — Passeios do vazio e o grupo dos programas.** Um *programa* é uma sequência finita de movimentos legais, iniciada a partir de uma configuração com o vazio em casa, cuja configuração final também tem o vazio em casa. Seu *efeito* é a permutação $\pi$ das casas definida por: o conteúdo da casa $x$ termina na casa $\pi(x)$.

9. Mostre que um programa executado a partir de $\sigma$ termina em $\sigma  \circ \pi^{-1}$ ; que executar dois programas em sucessão compõe seus efeitos; e que o conjunto $H$ de todos os efeitos é um subgrupo de $\mathfrak{S}_{15}$ (permutações das casas $1, \dots, 15$ ) contido no grupo alternado $A_{15}$ .
10. (O passeio elementar) Com o vazio em casa, faça-o percorrer o bloco $2 \times 2$ do canto inferior direito: casas $16 \to 12 \to 11 \to 15 \to 16$ . Mostre que o efeito é o $3$ -ciclo $(11\ 12\ 15)$ e que o passeio no sentido inverso dá $(11\ 15\ 12)$ . Ambos pertencem a $H$ .
11. (O grande passeio) Verifique que $$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$$ é um passeio fechado por todas as dezesseis casas (apenas passos adjacentes), e que seu efeito é o $15$-ciclo $$\zeta = (15\ 12\ 11\ 10\ 6\ 7\ 8\ 4\ 3\ 2\ 1\ 5\ 9\ 13\  14) .$$ Escrevendo $x_0 = 15$, $x_1 = 12$, $x_2 = 11$, …, $x_{14}  = 14$ para a ordem de seu [ciclo](#def-b2-structures-sn), verifique que o passeio elementar inverso da questão 10 é exatamente $(x_0\ x_1\  x_2)$.
12. Prove a fórmula de conjugação em qualquer $\mathfrak{S}_n$: para uma permutação $g$ e um $3$-ciclo, $$g\,(a\ b\ c)\,g^{-1} = \bigl(g(a)\ g(b)\ g(c)\bigr),$$ e note que $H$, sendo um grupo, é fechado por conjugação por seus próprios elementos.
13. Deduza que $H$ contém os quinze $3$-ciclos *consecutivos* do grande passeio: $$s_t = (x_t\ x_{t+1}\ x_{t+2}) \qquad (t \in \Z/15\Z,  \text{ índices módulo } 15).$$

**Parte IV — Gerando o grupo alternado.**

14. (Lema A) Sejam $s$ e $t$ $3$ -ciclos cujos suportes compartilham exatamente dois pontos, digamos suportes $\{a, b, c\}$ e $\{b, c, d\}$ . Mostre que, após substituir $s$ ou $t$ por seu inverso se necessário (o que nada muda no subgrupo [gerado](#def-b2-structures-generated) ), o produto $st$ é uma dupla [transposição](#def-b2-structures-sn) ; mostre que $A_4$ não contém subgrupo de ordem $6$ *(um subgrupo de índice $2$ contém todos os quadrados; conte os $3$-ciclos entre os quadrados)* ; e conclua que $\langle s, t\rangle$ é todo o grupo alternado das quatro letras $\{a, b, c, d\}$ .
15. (Lema B) Seja $X$ um conjunto de $k \geq 4$ letras, $w  \notin X$ , e seja $G$ um subgrupo de algum $\mathfrak{S}_n$ que contém toda permutação par de $X$ e um $3$ -ciclo $(u\ v\ w)$ com $u, v \in X$ . Mostre que, para todos os $a, b \in X$ distintos, existe uma permutação *par* $g$ de $X$ com $g(u) = a$ , $g(v) = b$ , e deduza que $(a\ b\ w) \in G$ .
16. Deduza que o grupo $G$ do Lema B contém toda permutação par de $X \cup \{w\}$ *(use o [Exercício 1.6](#exo-b2-structures-6): os $3$-ciclos geram)* . Em seguida, encadeando os Lemas A e B ao longo dos $3$ -ciclos consecutivos $s_0, s_1, \dots, s_{12}$ da questão 13, prove que $\langle s_0, \dots, s_{12}\rangle = A_{15}$ .
17. Conclua que $H = A_{15}$ : *todo rearranjo par das quinze peças é realizável por um programa* , e $H$ tem $15!/2 = 653\,837\,184\,000$ elementos.
18. (O teorema de Johnson–Story, 1879) Reúna as questões 6, 7, 8 e 17: as configurações alcançáveis a partir da resolvida são *exatamente* as $16!/2 =  10\,461\,394\,944\,000$ configurações com $I = +1$ ; e a alcançabilidade tem exatamente *duas* classes, a classe da configuração resolvida e a classe da configuração $\sigma_L$ de Loyd. *(Para o segundo ponto, renomeie as peças $14$ e $15$: mostre que $\sigma \mapsto (14\ 15) \circ  \sigma$ leva sequências de movimentos em sequências de movimentos e troca $\{I = +1\}$ com $\{I = -1\}$.)*

**Parte V — Critérios, variantes e a vista do alto.**

19. (O critério prático) Leia as quinze peças na ordem de leitura de suas casas, pulando o vazio, e seja $N$ o número de inversões dessa lista; seja $r$ a linha do vazio contada a partir de *baixo* . Mostre que $I(\sigma) = (-1)^{N + r + 1}$ , de modo que $\sigma$ é resolúvel se e somente se $N + r$ é ímpar.
20. (Ações de grupo) Uma *ação* de um grupo $G$ sobre um conjunto $X$ é uma aplicação $G \times X \to X$ , $(g, x) \mapsto g \cdot  x$ , com $e \cdot x = x$ e $g \cdot (h \cdot x) =  (gh) \cdot x$ ; a *órbita* de $x$ é $G \cdot x$ , e a ação é *livre* quando $g \cdot x = x$ obriga $g =  e$ . Mostre que $h \cdot \sigma = \sigma \circ h^{-1}$ define uma ação livre de $H$ sobre o conjunto das configurações com o vazio em casa, que suas órbitas são exatamente as classes de alcançabilidade mútua por programas, e recupere pela contagem de órbitas que essas configurações se repartem em exatamente $15!\,/\,\abs H = 2$ classes.
21. (A obstrução $3 \times 3$ ) Mostre que o tabuleiro $3 \times 3$ *não* admite passeio fechado que visite cada casa exatamente uma vez: a estratégia do grande passeio da Parte III falha para o jogo dos oito. *(Pinte as nove casas como um damas.)*
22. (O conserto) No tabuleiro $3 \times 3$ com casas $1$ a $9$ na ordem de leitura e casa natural $9$ : calcule os efeitos do passeio pelo perímetro $9 \to 8 \to 7 \to 4 \to 1 \to 2 \to 3  \to 6 \to 9$ (um $7$ -ciclo $\zeta'$ que fixa o centro $5$ ) e do passeio pelos cantos $9 \to 6 \to 5 \to 8 \to 9$ (um $3$ -ciclo que passa pelo centro). Conjugando o segundo pelas potências de $\zeta'$ e encadeando os Lemas A e B, prove que o grupo de programas do jogo dos oito é todo o $A_8$ , e portanto que exatamente $9!/2 = 181\,440$ das $9! =  362\,880$ configurações são resolúveis.
23. (Um tabuleiro pobre) Considere agora um tabuleiro que é um único [ciclo](#def-b2-structures-sn) de $n  \geq 4$ casas com $n - 1$ peças. Mostre que a ordem [cíclica](#def-b2-structures-generated) das peças é invariante, que cada classe de alcançabilidade tem exatamente $n(n - 1)$ configurações *(as classes são as órbitas de um [grupo cíclico](#def-b2-structures-generated) de ordem $\operatorname{lcm}(n, n-1) = n(n-1)$)* , e que há $(n - 2)!$ classes — para $n \geq 5$ muito mais do que $2$ : num tabuleiro estreito o invariante de paridade quase nada captura, e é a geometria que manda.
24. Dois veredictos pelo critério da questão 19: o tabuleiro totalmente invertido (peças $15, 14, \dots, 1$ nas casas $1$ a $15$ , vazio em casa) e o tabuleiro com o vazio na casa $1$ seguido das peças $15, 14, \dots, 1$ nas casas $2$ a $16$ . Qual dos dois é resolúvel?
25. (Síntese) A demonstração tem dois pilares independentes: um *invariante* ( $I$ , construído a partir do morfismo assinatura), que mostra que no máximo metade das configurações é alcançável, e um teorema de *geração explícita* ( $H = A_{15}$ ), que mostra que ao menos metade o é. Em uma frase cada, diga onde entraram: a propriedade de morfismo de $\varepsilon$ ; o teorema de Lagrange; a geração de $A_n$ pelos $3$ -ciclos; a conjugação. Enuncie o metaprincípio em uma linha.

**Solução de Problema 1.1.**

**1.** Uma configuração atribui a cada uma das $16$ casas um dos $16$ conteúdos (peças $1$–$15$ ou o vazio $b = 16$), cada um exatamente uma vez: precisamente uma bijeção $\intint1{16} \to
\intint1{16}$, um elemento de $\mathfrak{S}_{16}$; há $16!
= 20\,922\,789\,888\,000$ delas. Um movimento legal desliza uma peça adjacente ao vazio, de modo que o número de movimentos é o número de vizinhos da casa do vazio: $2$ para as quatro casas de canto, $3$ para as oito casas de borda, $4$ para as quatro casas interiores.

**2.** Após o deslizamento, a casa $p$ contém o antigo conteúdo de $c$ e a casa $c$ contém o vazio; todas as outras casas ficam intactas: $\sigma'(p) = \sigma(c)$, $\sigma'(c) = \sigma(p) = 16$, $\sigma' = \sigma$ nas demais. Isso é exatamente $\sigma' = \sigma
\circ (p\ c)$. Como $\varepsilon$ é um morfismo e $\varepsilon\bigl((p\ c)\bigr) = -1$: $\varepsilon(\sigma') = -\varepsilon(\sigma)$.

**3.** Casas adjacentes diferem de um passo em exatamente uma das duas coordenadas, de modo que $i + j$ muda de paridade: $\chi$ assume valores opostos em casas adjacentes. Um movimento transfere o vazio de $p$ para a casa adjacente $c$, invertendo $\chi(\text{casa vazia})$. Ao longo de um passeio fechado do vazio, $\chi$ é invertido uma vez por movimento e retorna a seu valor inicial: o número de movimentos é par.

**4.** Pelas questões 2 e 3, um movimento inverte os dois fatores de $I(\sigma) = \varepsilon(\sigma)\chi(\sigma^{-1}(16))$; o produto fica inalterado. Para a configuração resolvida: $\varepsilon(\mathrm{id}) = +1$ e o vazio está na casa $16$, linha $4$, coluna $4$: $\chi(16) = (-1)^{8} = +1$, logo $I(\mathrm{id}) = +1$.

**5.** $\sigma_L$ é a [transposição](#def-b2-structures-sn) $(14\ 15)$ de casas: $\varepsilon(\sigma_L) = -1$; seu vazio está em casa, $\chi(16) = +1$: $I(\sigma_L) = -1 \neq +1 = I(\mathrm{id})$. Como $I$ é preservado por todo movimento, nenhuma sequência de movimentos liga $\sigma_L$ e $\mathrm{id}$. O prêmio estava estruturalmente a salvo.

**6.** Fixe uma casa $p$ e duas outras casas $c \neq d$ distintas de $p$, e ponha $\tau_0 = (c\ d)$. Sobre o conjunto das configurações com o vazio em $p$, a aplicação $\sigma \mapsto \sigma
\circ \tau_0$ é uma involução (ela preserva $\sigma(p) = 16$, pois $\tau_0$ fixa $p$) e inverte $\varepsilon$, logo inverte $I$: ela emparelha bijetivamente as configurações com $I = +1$ com aquelas com $I = -1$. Assim cada uma das $16$ posições do vazio contribui com $15!/2$ configurações com $I = +1$, e

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

**7.** O movimento que desliza a peça de $c$ para $p$ é desfeito deslizando essa mesma peça (agora em $p$) de volta para $c$: compor duas vezes com $(p\ c)$ dá a identidade. Daí: reflexividade (sequência vazia), simetria (inverta a sequência, desfazendo cada movimento), transitividade (concatene): uma relação de equivalência. Toda $\sigma \in R$ tem $I(\sigma) = I(\mathrm{id}) = +1$ pela questão 4, logo $R \subseteq \{I = +1\}$; e $\sigma_L \notin R$ dá uma segunda classe.

**8.** Se $\sigma(16) = 16$, então $\sigma$ permuta as casas $1, \dots, 15$; chame de $\rho$ essa restrição. Acrescentar um ponto fixo não muda nem o tipo de [ciclo](#def-b2-structures-sn) nem a assinatura (decomponha $\rho$ em [transposições](#def-b2-structures-sn); o mesmo produto serve em $\mathfrak{S}_{16}$), logo $\varepsilon(\sigma) =
\varepsilon(\rho)$, e $\chi(16) = +1$ dá $I(\sigma) =
\varepsilon(\rho)$. Toda configuração pode ser levada a uma com o vazio em casa: a grade é conexa, basta conduzir o vazio ao longo de um caminho de casas adjacentes até a casa $16$ (cada passo é um movimento legal). Suponha agora que toda $\rho \in \mathfrak{S}_{15}$ par seja realizada por um programa. Dada $\sigma$ com $I(\sigma) = +1$: conduza o vazio até casa para chegar a $\widetilde\sigma$ (equivalente a $\sigma$), com $I(\widetilde\sigma) = +1$, isto é, sua restrição $\rho$ é par; o programa que realiza $\rho$ leva $\widetilde\sigma$ em $\widetilde\sigma \circ \rho^{-1} = \mathrm{id}$ (veja a questão 9). Por transitividade $\sigma \in R$, donde $\{I = +1\} \subseteq
R$ e a igualdade.

**9.** *Movimento único:* o conteúdo de $c$ termina em $p$ e o vazio em $c$: o efeito é $\pi = (p\ c)$, e de fato $\sigma' = \sigma \circ (p\ c) = \sigma \circ \pi^{-1}$. *Indução:* se uma sequência tem efeito $\pi_1$ e leva $\sigma$ em $\sigma \circ \pi_1^{-1}$, segui-la de um movimento de efeito $\pi_2 = (p'\ c')$ dá $(\sigma \circ \pi_1^{-1})
\circ \pi_2^{-1} = \sigma \circ (\pi_2\pi_1)^{-1}$, e os conteúdos se deslocam por $\pi_2 \circ \pi_1$ (primeiro $\pi_1$, depois $\pi_2$). Assim os efeitos se compõem, e um programa executado a partir de $\sigma$ termina em $\sigma
\circ \pi^{-1}$. *Subgrupo:* o programa vazio tem efeito $\mathrm{id}$; a concatenação dá os produtos; inverter um programa (questão 7) dá os inversos. O efeito de um programa fixa a casa $16$ (o vazio começa e termina em casa), logo $H \leq \mathfrak{S}_{15}$. *Paridade:* um programa de $k$ movimentos tem $k$ par (questão 3), e $\varepsilon(\sigma \circ \pi^{-1}) =
(-1)^k\varepsilon(\sigma)$ obriga $\varepsilon(\pi) = +1$: $H
\subseteq A_{15}$.

**10.** Acompanhe os quatro deslizamentos a partir do vazio em $16$: o movimento $16 \to 12$ leva o conteúdo de $12$ a $16$; o movimento $12 \to 11$ leva o conteúdo de $11$ a $12$; o movimento $11 \to 15$ leva o conteúdo de $15$ a $11$; o movimento $15 \to 16$ leva o conteúdo estacionado em $16$ (originalmente em $12$) a $15$. Resultado: $11 \mapsto
12$, $12 \mapsto 15$, $15 \mapsto 11$, vazio em casa: o efeito é $(11\ 12\ 15)$. O passeio inverso o desfaz: efeito $(11\ 12\
15)^{-1} = (11\ 15\ 12)$. Ambos são efeitos de programas, logo estão em $H$.

**11.** Adjacência das casas consecutivas: dentro de cada par listado as casas diferem de $1$ na mesma linha ($16{-}15$, $15{-}14$, $14{-}13$; $1{-}2$, $2{-}3$, $3{-}4$; $8{-}7$, $7{-}6$; $10{-}11$, $11{-}12$) ou de $4$ dentro de uma coluna ($13{-}9$, $9{-}5$, $5{-}1$; $4{-}8$; $6{-}10$; $12{-}16$): um passeio fechado por todas as $16$ casas, de comprimento $16$. Efeito: como na questão 10, escrevendo as casas visitadas $c_0 = 16, c_1 = 15,
\dots, c_{15} = 12$: o conteúdo de $c_i$ passa a $c_{i-1}$ para $i = 2, \dots, 15$, e o conteúdo de $c_1$, estacionado em $16$ após o primeiro movimento, é levado a $c_{15}$ pelo último movimento. Assim o efeito leva $15 \mapsto 12$, e $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$: exatamente o $15$-ciclo $\zeta$. A [ordem](#def-b2-structures-generated) de seu [ciclo](#def-b2-structures-sn) começa por $x_0 = 15$, $x_1 = 12$, $x_2 = 11$, e $(x_0\ x_1\ x_2)
= (15\ 12\ 11)$ leva $15 \mapsto 12 \mapsto 11 \mapsto 15$ — que é precisamente $(11\ 15\ 12)$, o passeio elementar inverso.

**12.** Sejam $\gamma = (a\ b\ c)$ e $x \in \intint1n$. Se $x = g(a)$: $g\gamma g^{-1}(x) = g(\gamma(a)) = g(b)$; do mesmo modo $g(b) \mapsto g(c)$ e $g(c) \mapsto g(a)$. Se $x \notin
\{g(a), g(b), g(c)\}$, então $g^{-1}(x) \notin \{a,b,c\}$ é fixado por $\gamma$, logo $x$ é fixado. Portanto $g\gamma g^{-1} =
(g(a)\ g(b)\ g(c))$. E, para $g, h \in H$, $ghg^{-1} \in H$ pelos axiomas de subgrupo.

**13.** $\zeta \in H$ (questão 11) e $s_0 = (x_0\ x_1\
x_2) \in H$ (questões 10–11). Como $\zeta(x_i) = x_{i+1}$ (índices módulo $15$), a questão 12 dá

$$
\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.** A menos de inverter, suponha $s = (a\ b\ c)$ e $t =
(b\ c\ d)$ (um $3$-ciclo sobre $\{a,b,c\}$ é $(a\ b\ c)$ ou seu inverso; do mesmo modo sobre $\{b,c,d\}$; substituir um gerador por seu inverso deixa $\langle s, t\rangle$ inalterado). Então, aplicando $t$ primeiro,

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

uma dupla [transposição](#def-b2-structures-sn). O subgrupo $G = \langle s, t\rangle$ consiste em permutações pares das quatro letras, logo $G \leq
A_4$ e $\abs G \mid 12$; ele contém um elemento de ordem $3$ e um de ordem $2$, logo $6 \mid \abs G$ (Lagrange, [Teorema 1.14](#thm-b2-structures-lagrange), aplicado aos dois subgrupos [cíclicos](#def-b2-structures-generated)). Se $A_4$ tivesse um subgrupo $K$ de ordem $6$, ele teria índice $2$, e então $g^2 \in K$ para todo $g \in A_4$: para $g \in K$ isso é claro; para $g \notin K$ as únicas classes laterais são $K$ e $gK$, de modo que a classe $g^2K$ é $K$ ou $gK$, e $g^2K =
gK$ forçaria $g \in K$. Assim todo quadrado pertence a $K$. Mas todo $3$-ciclo $\gamma$ é um quadrado, $\gamma = (\gamma^2)^2$, e $A_4$ contém oito $3$-ciclos: $8 > 6$, contradição. Logo $\abs G = 12$: $G = A_4$.

**15.** Estenda $u \mapsto a$, $v \mapsto b$ a uma bijeção $g_0$ de $X$ (envie as $k - 2$ letras restantes bijetivamente para o complementar de $\{a, b\}$, de qualquer maneira). Se $g_0$ é ímpar, escolha duas letras distintas $s_1, t_1 \in X \setminus \{u, v\}$ (possível: $k \geq 4$) e substitua $g_0$ por $g_0 \circ (s_1\
t_1)$, que é par e ainda leva $u \mapsto a$, $v \mapsto
b$. Estenda pela identidade fora de $X$: uma permutação par $g \in
G$ (é uma permutação par de $X$). Então a questão 12:

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

usando $g(w) = w$.

**16.** Todo $3$-ciclo de $X \cup \{w\}$ está em $G$: os que têm suporte em $X$ são permutações pares de $X$; um com suporte $\{a, b, w\}$ é $(a\ b\ w)$ ou $(b\ a\ w)$, ambos entregues pela questão 15. Pelo [Exercício 1.6](#exo-b2-structures-6), os $3$-ciclos do conjunto de $(k+1)$ elementos $X \cup \{w\}$ geram seu grupo alternado, logo $G$ contém toda permutação par de $X \cup \{w\}$. *Encadeamento:* seja $G = \langle s_0, \dots,
s_{12}\rangle$. O Lema A aplicado a $s_0 = (x_0\ x_1\ x_2)$ e $s_1 = (x_1\ x_2\ x_3)$ (os suportes compartilham $\{x_1, x_2\}$) dá todas as permutações pares de $X_4 = \{x_0, x_1, x_2, x_3\}$. Se $G$ contém todas as permutações pares de $X_m = \{x_0, \dots,
x_{m-1}\}$ ($4 \leq m \leq 14$), então $s_{m-2} = (x_{m-2}\
x_{m-1}\ x_m)$ tem $u = x_{m-2}, v = x_{m-1} \in X_m$ e nova letra $w = x_m$: o Lema B e a primeira parte dão todas as permutações pares de $X_{m+1}$. Indução até $m = 14$: $G \supseteq
A_{15}$ (permutações pares de todas as quinze casas), e $G
\subseteq A_{15}$, pois cada $s_t$ é par: $\langle s_0, \dots,
s_{12}\rangle = A_{15}$.

**17.** Questões 13 e 16: $A_{15} = \langle s_0, \dots,
s_{12}\rangle \subseteq H$; questão 9: $H \subseteq A_{15}$. Logo $H = A_{15}$, de ordem $15!/2 = 653\,837\,184\,000$: todo rearranjo par das quinze peças é o efeito de um programa.

**18.** A questão 8 reduziu $R = \{I = +1\}$ a realizar toda $\rho \in \mathfrak{S}_{15}$ par por um programa: feito na questão 17. Com a questão 6, $\abs R = 16!/2 =
10\,461\,394\,944\,000$. *Duas classes:* faça $t_0 = (14\
15)$ agir sobre os *conteúdos*: $\varphi(\sigma) = t_0 \circ
\sigma$. Um movimento legal a partir de $\sigma$ é um movimento legal a partir de $\varphi(\sigma)$ (a casa vazia não muda: $(t_0\sigma)^{-1}(16) = \sigma^{-1}(t_0(16)) = \sigma^{-1}(16)$, e a casa movida é a mesma), e $\varphi(\sigma \circ \tau)
= \varphi(\sigma) \circ \tau$: $\varphi$ leva sequências de movimentos em sequências de movimentos, bijetivamente (é uma involução). Ela inverte $I$: $\varepsilon(t_0\sigma) = -\varepsilon(\sigma)$, com a mesma casa vazia. Portanto $\varphi$ leva a classe $R = \{I = +1\}$ de $\mathrm{id}$ bijetivamente sobre a classe de $\varphi(\mathrm{id})
= \sigma_L$, que é então todo o $\{I = -1\}$: exatamente duas classes. Esse é o teorema de Johnson–Story.

**19.** Indexe as casas na ordem de leitura e seja $k = 4(i -
1) + j$ a casa do vazio. Conte as inversões de $\sigma$ (pares de casas $x < y$ com $\sigma(x) > \sigma(y)$): os pares de duas casas com peça contribuem com $N$; os pares que envolvem o vazio: as casas após o vazio contêm todas peças $< 16$, cada uma invertida ($16 - k$ pares), as casas antes dele nunca estão invertidas. Assim $\varepsilon(\sigma) = (-1)^{N + 16 - k} = (-1)^{N + k}$. Como $k = 4(i-1) + j \equiv j \pmod 2$,

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

usando $i = 5 - r$. Pela questão 18, $\sigma$ é resolúvel se e somente se $I(\sigma) = +1$, se e somente se $N + r$ é ímpar. Verificação: resolvida, $N = 0$, $r
= 1$: ímpar, resolúvel; Loyd, $N = 1$, $r = 1$: par, não resolúvel.

**20.** *Ação:* $e \cdot \sigma = \sigma \circ
\mathrm{id} = \sigma$ e $g \cdot (h \cdot \sigma) = \sigma
\circ h^{-1} \circ g^{-1} = \sigma \circ (gh)^{-1} = (gh) \cdot
\sigma$; e $\sigma \circ h^{-1}$ é de novo uma configuração com o vazio em casa ($h$ fixa a casa $16$). *Livre:* $\sigma \circ
h^{-1} = \sigma$ dá $h^{-1} = \mathrm{id}$ (componha com $\sigma^{-1}$). *Órbitas = classes de programas:* a questão 9 diz que as configurações alcançáveis a partir de $\sigma$ por programas são exatamente as $\sigma \circ \pi^{-1}$, $\pi \in H$: a órbita $H
\cdot \sigma$. *Contagem:* a liberdade torna $h \mapsto h \cdot
\sigma$ injetiva, logo toda órbita tem $\abs H = 15!/2$ elementos; as $15!$ configurações com o vazio em casa se repartem portanto em $15!\,/\,(15!/2) = 2$ órbitas — a sombra, com o vazio em casa, das duas classes de Johnson–Story.

**21.** A grade $3 \times 3$ é bipartida para a coloração de damas: todo passo de um passeio muda de cor, logo todo passeio *fechado* tem comprimento par. Um passeio fechado que visitasse cada uma das $9$ casas exatamente uma vez teria comprimento $9$, ímpar: impossível. A construção do grande passeio da Parte III é portanto indisponível no jogo dos oito.

**22.** *Passeio pelo perímetro* $9 \to 8 \to 7 \to 4 \to 1
\to 2 \to 3 \to 6 \to 9$ (todos os passos adjacentes; comprimento $8$, par): pela contabilização da questão 11 com $c_1 = 8, c_2 = 7, c_3 =
4, c_4 = 1, c_5 = 2, c_6 = 3, c_7 = 6$, o efeito é

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

um $7$-ciclo que fixa o centro $5$ (o conteúdo de $7$ vai para $8$, o de $4$ para $7$, o de $1$ para $4$, o de $2$ para $1$, o de $3$ para $2$, o de $6$ para $3$ e o de $8$ para $6$). *Passeio pelos cantos* $9 \to 6 \to
5 \to 8 \to 9$: efeito $(6\ 8\ 5)$ (o conteúdo de $5$ vai para $6$, o de $8$ para $5$, o de $6$ — estacionado em $9$ — para $8$). Ponha $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$. Conjugação (questão 12):

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

pois $\zeta'$ fixa $5$. Os suportes de $T_0 = (y_1\ y_0\ 5)$ e $T_1 = (y_2\ y_1\ 5)$ compartilham exatamente $\{y_1, 5\}$: o Lema A dá todas as permutações pares de $\{y_0, y_1, y_2, 5\}$. Em seguida $T_2 = (y_3\ y_2\ 5)$ junta $y_3$ pelo Lema B (suas letras $y_2, 5$ estão no conjunto atual, $k = 4$), e $T_3, T_4, T_5$ juntam $y_4, y_5, y_6$ por sua vez: todas as permutações pares das oito casas não naturais estão no grupo de programas, que também consiste em permutações pares (o argumento da questão 9 é independente do tabuleiro). Logo $H_{3\times3} = A_8$, e o raciocínio das questões 6, 8 e 18 — também independente do tabuleiro — mostra que as configurações alcançáveis são exatamente aquelas com $I = +1$: metade de $9!$, isto é, $181\,440$.

**23.** Rotule as casas $0, \dots, n-1$ ao longo do [ciclo](#def-b2-structures-sn). Um movimento troca o vazio com um de seus dois vizinhos. Leia as peças em ordem [cíclica](#def-b2-structures-generated) a partir de logo depois do vazio: uma palavra $w$ que lista as $n - 1$ peças. Mover o vazio um passo adiante substitui $(p, w)$ por $(p + 1, \rho w)$, em que $p$ é a casa do vazio e $\rho$ rotaciona ciclicamente a palavra de uma posição; o movimento para trás é o inverso. A [ordem](#def-b2-structures-generated) *[cíclica](#def-b2-structures-generated)* das peças (a palavra a menos de rotação) é portanto invariante. A classe alcançável de $(p, w)$ é a órbita da aplicação $g \colon (p, w) \mapsto (p+1,
\rho w)$, um elemento de ordem $\operatorname{lcm}(n, n-1) =
n(n-1)$ no produto dos dois [grupos cíclicos](#def-b2-structures-generated) (translações de $\Z/n\Z$ e rotações das $n-1$ posições da palavra), sendo o mmc igual a $n(n-1)$ porque $\gcd(n, n-1) = 1$: cada classe tem exatamente $n(n-1)$ configurações, todas com o mesmo colar. Classes: $n!\,/\,\bigl(n(n-1)\bigr) = (n-2)!$. Para $n \geq 5$, $(n-2)! > 2$: o invariante de paridade (duas classes, no melhor dos casos) é cego para quase toda a obstrução; a riqueza do tabuleiro $4
\times 4$ — onde a paridade é a *única* obstrução — é um fato genuinamente geométrico, não formal.

**24.** Os dois tabuleiros têm as peças em ordem totalmente invertida, de modo que $N = \binom{15}{2} = 105$ nos dois casos (todo par de peças está invertido). *Vazio em casa:* $r = 1$, $N + r = 106$ par: não resolúvel. *Vazio na casa $1$:* o vazio está na linha de cima, $r = 4$, $N + r = 109$ ímpar: resolúvel. Dois tabuleiros que diferem apenas pela posição do buraco caem em lados opostos do muro.

**25.** *Propriedade de morfismo:* ela converte “um movimento = uma [transposição](#def-b2-structures-sn)” em “um movimento = uma troca de sinal” (questões 2 e 4), tornando $I$ calculável movimento a movimento. *Lagrange:* ele forçou $6 \mid \abs{\langle s, t\rangle}$ no Lema A e dimensionou as classes laterais na exclusão da ordem $6$ (questão 14). *Geração pelos $3$-ciclos:* ela converteu “$H$ contém $3$-ciclos suficientes” em “$H$ contém todo o $A_{15}$” (questão 16). *Conjugação:* ela fabricou os quinze $3$-ciclos consecutivos a partir de um único passeio $2 \times 2$ transportado pelo grande passeio (questões 12–13), e os $3$-ciclos $(a\ b\ w)$ no Lema B. *Metaprincípio:* um invariante prova a impossibilidade, uma construção explícita prova a possibilidade, e um problema está inteiramente resolvido exatamente quando as duas cotas se encontram — aqui, na metade.