Matemática universitária — Graduação 2 · Bachelor Year 2

1Conjuntos 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, 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 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), os anéis quociente fazem a aritmética funcionar e a enumerabilidade 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 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 é 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)

Todo subconjunto infinito de $\N$ é enumerável; um conjunto é no máximo enumerável se e somente se ele injeta em $\N$ , se e somente se é vazio ou imagem sobrejetiva de $\N$ .
$\N \times \N$ é enumerável; um produto de dois conjuntos enumeráveis no máximo enumeráveis é no máximo enumerável.
Uma união no máximo enumerável de conjuntos enumeráveis no máximo enumeráveis é no máximo enumerável.
$\Z$ e $\Q$ são enumeráveis.

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 a $\varphi(E) \subseteq \N$ : finito ou enumerável. 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 $\N^2$ sobre $\bigcup E_n$ .

(4) $\Z = \N \cup (-\N^*)$ : união enumerável. $\Q$ é imagem sobrejetiva de $\Z \times \N^*$ (a aplicação fração), logo no máximo enumerável, 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 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: os polinômios de grau $\leq d$ sobre $\Q$ injetam-se em $\Q^{d+1}$ , produto finito de conjuntos enumeráveis (Proposição 1.6 (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 de conjuntos finitos (Proposição 1.6 (3)), infinita pois contém $\Q$ . Combinado com a não enumerabilidade de $\R$ (Teorema 1.9 adiante), isso prova — sem exibir um único deles — que os números transcendentes existem e formam uma maioria não enumerável: o argumento de contagem de Cantor de 1874, a existência apenas pela cardinalidade.

Teorema 1.9 (Cantor; não enumerabilidade de $\R$ )

Para todo conjunto $E$ , não existe sobrejeção $E \to \mathcal{P}(E)$ .
$\R$ não é enumerável.

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.

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: 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) são todos equipotentes: “a cardinalidade do contínuo”.

Exemplo 1.12 (O segmento e o quadrado)

$\intcc{0}{1}$ e $\intcc{0}{1}^2$ são equipotentes — 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) 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).

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: $A_3$ dentro de $\mathfrak{S}_3$ )

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 prima são cíclicos: 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 adiante, há exatamente um subgrupo por divisor de $12$ — ordens $1, 2, 3, 4, 6, 12$ , gerados 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, questão 14). Lagrange restringe as ordens 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. — O reticulado de subgrupos de $\Z/12\Z$ : um subgrupo por divisor de $12$ (Proposição 1.17), 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 de ordem $n$ .

$G$ é isomorfo a $(\Z/n\Z, +)$ , via $\overline k \mapsto a^k$ .
Todo subgrupo de $G$ é cíclico; para cada divisor $d \mid n$ existe exatamente um subgrupo de ordem $d$ , a saber $\langle a^{n/d}\rangle$ .
$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) 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 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 dois a dois disjuntos, de modo único a menos da ordem dos fatores. Ciclos 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 — a primeira repetição deve retornar a $x$ por injetividade) carrega o ciclo $(x\ \sigma(x)\ \cdots\ \sigma^{k-1}(x))$ , e $\sigma$ é o produto desses ciclos: sobre cada órbita, só age o ciclo correspondente. Unicidade: toda fatoração em ciclos disjuntos reproduz exatamente as órbitas (o ciclo que passa por $x$ tem de ser $(x\ \sigma(x)\ \cdots)$ ). Ciclos 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 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 $(4, 3, 2)$ — um $4$ -ciclo, um $3$ -ciclo, uma transposição? Escolha os suportes e as ordens cíclicas:

\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, 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 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 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: 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 $\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 geram $\mathfrak{S}_n$ (todo ciclo $(a_1\cdots a_k) = (a_1\,a_k)(a_1\,a_{k-1})\cdots(a_1\,a_2)$ , e Teorema 1.19 conclui); um morfismo com valores em $\{\pm1\}$ fica determinado por seus valores em geradores.

Consequências. A identidade de ciclos acima escreve um $k$ -ciclo como produto de $k - 1$ transposições: assinatura $(-1)^{k-1}$ . $A_n$ : o morfismo $\varepsilon$ é sobrejetivo (existem transposições para $n \geq 2$ ), e as duas “classes laterais” $A_n$ e $(1\,2)A_n$ são equipotentes 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.

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: $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 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: $\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 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; 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 por $x$ é $xA = \{xa\}$ (um ideal principal).

Teorema 1.26 (Ideais de $\Z$ e de $K[X]$ )

Todo ideal de $\Z$ é $n\Z$ para um único $n \in \N$ ; todo 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 é em particular um subgrupo, e $n\Z$ é um ideal). Para $K[X]$ : seja $I \neq \{0\}$ um 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 $x\Z + y\Z$ (resp. de seu análogo polinomial) com o ideal principal do mdc — a própria definição de mdc usada no primeiro ano, agora reconhecida como um enunciado sobre ideais. ∎

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: o ideal $(X^3 - 1)\Q[X] + (X^2 - 1)\Q[X]$ é principal (Teorema 1.26); 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 identifica o mdc sem dividir — as raízes comuns localizam o ideal, e Euclides apenas o certifica.

Definição 1.28 (Anel quociente $\Z/n\Z$ , revisitado)

Para um 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 $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. 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. 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): todo elemento elevado à ordem 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? Calcule as ordens 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 $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 $4, 2, 4, 2, 2$ e nunca $8$ . Contraste com Exercício 1.10: $(\Z/p\Z)^*$ é cíclico 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.

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 principal, exatamente como prevê o Teorema 1.26, gerado pelo polinômio mônico $X^2$ de menor grau no núcleo — o polinômio minimal de $A$ , estrela do Capítulo 3. A imagem é a álgebra comutativa de dimensão dois $\{aI + bA\}$ : os morfismos de avaliação encolhem o espaço $\R[X]$ , de dimensão infinita, sobre álgebras 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): ela constrói $\Z/n\Z$ aqui, define aplicações sobre os conjuntos de soluções de sistemas lineares no Capítulo 2, 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), a invariância do traço por semelhança e as quantidades conservadas do Capítulo 16. Contar contra uma estrutura: Lagrange conta por classes laterais, a dimensão conta por bases (Capítulo 2), a multiplicidade conta por graus de polinômios (Capítulo 3); 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, 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 dá o enunciado correto para ordens coprimas e elementos que comutam, e os ciclos disjuntos dão a versão correta para permutações. (iii) A enumerabilidade sobrevive a uniões enumeráveis e a produtos finitos, mas não a produtos enumeráveis: $\{0,1\}^{\N}$ é não enumerável (Exercício 1.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).

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

Em quase toda parte. A assinatura constrói os determinantes (Capítulo 2); o morfismo de avaliação $P \mapsto P(u)$ e os ideais principais de $K[X]$ produzem os polinômios minimais e as decomposições em núcleos do Capítulo 3; a enumerabilidade é o palco em que o Capítulo 21 atua (probabilidade sobre espaços enumeráveis) e a razão pela qual a topologia não para de produzir conjuntos densos enumeráveis (Capítulo 4). 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? 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

Solução de Exercício 1.1.

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

Todas as partes de $\N$ : não enumerável, pelo teorema de Cantor (Teorema 1.9 (1) com $E = \N$ ).

$\R \setminus \Q$ : não enumerável — caso contrário $\R = \Q \cup (\R\setminus\Q)$ seria uma união de dois conjuntos enumeráveis, contradizendo Teorema 1.9 (2).

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

Sequências binárias nulas a partir de certa ordem: enumerável — 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 disjuntos, as ordens e as assinaturas das quatro permutações, e $\sigma^{2026}$ .

Solução

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).

Ordens e assinaturas: $\sigma$ tem tipo de ciclo $(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 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 (expansões binárias nos dois sentidos; Cantor–Bernstein absorve o incômodo da dupla representação).

Soluçã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) aplicado às duas últimas injeções, $\intcc{0}{1}$ e $\{0,1\}^{\N}$ são equipotentes, 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 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

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

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 pelos $3$ -ciclos. (Um produto de duas transposições é um $3$ -ciclo ou um produto de dois $3$ -ciclos.)

Solução

Solução de Exercício 1.6.

Todo elemento de $A_n$ é um produto de um número par de transposições (Teorema 1.21: decomponha em transposições; a contagem é par, pois a assinatura vale $+1$ ). Basta escrever cada produto de duas transposições 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

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

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

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

Solução

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 são coprimas e os dois elementos comutam ( $G \subseteq K^*$ é abeliano), logo, pelo Exercício 1.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.

Para $K = \Z/p\Z$ : $(\Z/p\Z)^*$ é um subgrupo finito de $K^*$ , logo cíclico (de ordem $p - 1$ ).

Exercício 1.11 ★★★

Prove que o grupo $(\Q, +)$ não é cíclico e, pior: não é sequer finitamente gerado. Prove, por outro lado, que todo subgrupo finitamente gerado de $(\Q, +)$ é cíclico.

Solução

Solução de Exercício 1.11.

Não cíclico: 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: o subgrupo gerado 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 são cíclicos: 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, gerado por $\frac nQ$ .

Exercício 1.12 ★★

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

Solução

Solução de Exercício 1.12.

Um subconjunto enumerável. 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 de $E$ .

$\implies$ infinito é equipotente 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 à 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 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 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? — 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, e duas casas são adjacentes quando compartilham uma aresta do tabuleiro.

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

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

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.
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 fixa de duas outras casas.)
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.
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)$ .

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}$ .
(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$ .
(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, verifique que o passeio elementar inverso da questão 10 é exatamente $(x_0\ x_1\ x_2)$ .
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.
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.

(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), o produto $st$ é uma dupla transposição; 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\}$ .
(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$ .
Deduza que o grupo $G$ do Lema B contém toda permutação par de $X \cup \{w\}$ (use o Exercício 1.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}$ .
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.
(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.

(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.
(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.
(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.)
(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.
(Um tabuleiro pobre) Considere agora um tabuleiro que é um único ciclo de $n \geq 4$ casas com $n - 1$ peças. Mostre que a ordem cíclica 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 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.
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?
(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

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 $(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 nem a assinatura (decomponha $\rho$ em transposições; 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 de seu ciclo 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. 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, aplicado aos dois subgrupos cíclicos). 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, 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. Um movimento troca o vazio com um de seus dois vizinhos. Leia as peças em ordem cíclica 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 cíclica 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 (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” 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.

Termos definidos neste capítulo

Ver todos os 395 termos do glossário