Matemáticas universitarias — Grado 2 · Bachelor Year 2

1Conjuntos y estructuras

Este capítulo inicial agudiza los cimientos establecidos en el Año 1. volumen en herramientas de trabajo del oficio: el cálculo de conjuntos y cocientes, la comparación de conjuntos infinitos (contabilidad, Cantor–Bernstein), y la teoría estructural de grupos y anillos — Teorema de Lagrange, el grupo simétrico con su firma, ideales y el teorema del resto chino. Todo aquí se utiliza sin descanso en El resto del libro: la firma construye el determinante. (Capítulo 2), aritmética de accionamiento anillos cocientes y contabilidad subyace tanto a la topología como a la probabilidad.

1.1 Conjuntos, mapas, cocientes.

Usamos libremente el lenguaje de conjuntos, mapas y equivalencias y orden relaciones establecidas en el volumen del Año 1. Dos actualizaciones merecen una adecuada declaración.

Proposición 1.1 (Imágenes y preimágenes de familias)

Deje $f \colon E \to F$ y deje $(A_i)_{i \in I}$ , $(B_j)_{j \in J}$ ser familias de subconjuntos de $E$ , resp. $F$ . entonces

f^{-1}\Bigl(\bigcup_j B_j\Bigr) = \bigcup_j f^{-1}(B_j), \qquad f^{-1}\Bigl(\bigcap_j B_j\Bigr) = \bigcap_j f^{-1}(B_j), \qquad f^{-1}(F \setminus B) = E \setminus f^{-1}(B),

f\Bigl(\bigcup_i A_i\Bigr) = \bigcup_i f(A_i), \qquad f\Bigl(\bigcap_i A_i\Bigr) \subseteq \bigcap_i f(A_i) \quad (\text{equality for injective } f).

Demostración. Cada identidad es un desenvolvimiento de definiciones; por ejemplo $x \in f^{-1}(\bigcap B_j) \iff f(x) \in B_j$ para todos los $j$ $\iff x \in f^{-1}(B_j)$ para todos los $j$ . Las identidades de imagen y el fracaso de igualdad en el caso de intersección (con la solución de inyectividad) fueron probado en el volumen del Año 1 para dos conjuntos; los argumentos son identicos para familias. ∎

Ejemplo 1.2 (Donde la inclusión de imágenes es estricta)

Tome $f \colon \R \to \R$ , $f(x) = x^2$ , con $A_1 = \intcc{-1}{0}$ y $A_2 = \intcc{0}{1}$ . entonces

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

la inclusión de Proposición 1.1 es tan estricta como puede ser — los dos puntos de preimagen $\pm x$ de un valor común vivir en diferentes $A_i$ . La inyectividad es exactamente lo que prohíbe esta división, razón por la cual las preimágenes (que nunca se fusionan) puntos) satisfacen las cuatro identidades incondicionalmente, mientras que Las imágenes pierden la de las intersecciones. Regla de oro para el libro completo: presione preimágenes a través de operaciones establecidas libremente; maneje las imágenes con cuidado.

Definición 1.3 (conjunto de conscientes)

Sea $\mathcal{R}$ una relación de equivalencia en $E$ . el conjunto cociente $E/\mathcal{R}$ es el conjunto de clases de equivalencia; la sobreyección $\pi \colon E \to E/\mathcal{R}$ , $x \mapsto \mathrm{cl}(x)$ , es el canónico proyección.

Propiedad universal (factorización): si $f \colon E \to F$ es compatible con $\mathcal{R}$ (es decir, $x \mathbin{\mathcal{R}} y \implies f(x) = f(y)$ ), hay exactamente un mapa $\overline f \colon E/\mathcal{R} \to F$ con $f = \overline f \circ \pi$ .

Prueba de propiedad universal. Unicidad: el requisito $f = \overline f \circ \pi$ dice

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

y dado que $\pi$ es sobreyectivo, cada elemento de $E/\mathcal{R}$ es algo de $\mathrm{cl}(x)$ : los valores de $\overline f$ son todos forzados. Existencia: tomar la pantalla como el definición de $\overline f$ ; es inequívoco precisamente por compatibilidad — si $\mathrm{cl}(x) = \mathrm{cl}(y)$ , entonces $x \mathbin{\mathcal{R}} y$ , entonces $f(x) = f(y)$ y los dos valores candidatos concuerdan — y factoriza $f$ por construcción. Nótese la división del trabajo: sobreyectividad de $\pi$ da unicidad, la compatibilidad da existencia. ∎

Ejemplo 1.4

$\Z/n\Z$ es el cociente de $\Z$ por módulo de congruencia $n$ ; el Las comprobaciones de buena definición del volumen del Año 1 fueron ejemplos de la propiedad universal. Los cocientes activan "construcciones compatibles". representantes” en mapas honestos — usamos esto constantemente a continuación.

1.2 Contabilidad y cardinalidad

Definición 1.5 (Equipo, contabilidad)

Dos conjuntos son equipotente cuando una biyección se une a ellos. Un conjunto es contable cuando es equipotente a $\N$ (algunos autores incluyen conjuntos finitos; decimos como máximo contable para "finito o contable").

Proposición 1.6 (Propiedades de estabilidad)

Cada subconjunto infinito de $\N$ es contable; un conjunto es como máximo contable si se inyecta en $\N$ si está vacío o un Imagen sobreyectiva de $\N$ .
$\N \times \N$ es contable; un producto de dos como máximo conjuntos contables es como máximo contable.
Una unión como máximo contable de como máximo conjuntos contables está en la mayoría contable.
$\Z$ y $\Q$ son contable.

Demostración. (1) Enumere un $A \subseteq \N$ infinito por mínimos repetidos: $a_0 = \min A$ , $a_{k+1} = \min\,(A \setminus \{a_0, \dots, a_k\})$ (no vacío ya que $A$ es infinito); el mapa $k \mapsto a_k$ es estrictamente creciente, inyectiva y sobreyectiva en $A$ (cada $a \in A$ excede sólo un número finito de elementos de $A$ , por lo que se alcanza). Si $E$ se inyecta en $\N$ a través de $\varphi$ , luego $E$ es equipotente para $\varphi(E) \subseteq \N$ : finito o contable. Si $s \colon \N \to E$ es sobreyectivo, entonces $x \mapsto \min s^{-1}(\{x\})$ inyecta $E$ . en $\N$ .

(2) El mapa $(p, q) \mapsto 2^p(2q + 1) - 1$ es una biyección $\N^2 \to \N$ (cada entero positivo tiene una división par-impar única $2^p m$ con $m$ impar, por factorización única). Productos: componer inyecciones.

(3) Conjuntos dados $E_n$ con sobreyecciones $s_n \colon \N \to E_n$ (inofensivo cuando algo de $E_n$ es finito: valores repetidos), el mapa $(n, k) \mapsto s_n(k)$ es una sobreyección de contable $\N^2$ a $\bigcup E_n$ .

(4) Unión $\Z = \N \cup (-\N^*)$ : contable. $\Q$ es una sobreyectiva imagen de $\Z \times \N^*$ (el mapa de fracciones), por lo tanto, como máximo contable, e infinito. ∎

Ejemplo 1.7 (Una función de emparejamiento, calculada)

La biyección $(p, q) \mapsto 2^p(2q + 1) - 1$ de la prueba. Merece ser visto en el trabajo. Sus primeros 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}

La fila $p$ recopila los números enteros $n$ para los cuales $n + 1$ es exactamente divisible por $2^p$ : cada número natural aparece exactamente una vez. La decodificación es tan explícita como la codificación: para $n = 43$ , factorice $n + 1 = 44 = 2^2\cdot 11 = 2^2(2\cdot5 + 1)$ , entonces $(p, q) = (2, 5)$ . La idea final: contabilidad las pruebas suelen ser algoritmos disfrazado — aquí, "factoriza los dos".

Ejemplo 1.8 (Los numeros algebraicos son contables)

Un número complejo es algebraico cuando aniquila algunos Polinomio distinto de cero con coeficientes racionales. el conjunto $\overline\Q$ de números algebraicos es contable: polinomios de grado $\leq d$ sobre $\Q$ inyectar en $\Q^{d+1}$ , un finito producto de conjuntos contables (Proposición 1.6 (2)); la unión terminó $d$ enumera los polinomios racionales distintos de cero como $P_0, P_1, P_2, \dots$ ; cada $P_k$ tiene un número finito de raíces; y

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

es una unión contable de conjuntos finitos (Proposición 1.6 (3)), infinito desde contiene $\Q$ . Combinado con la incontabilidad de $\R$ (Teorema 1.9 a continuación), esto prueba — sin exhibiendo uno solo — que existen números trascendentales y formar una mayoría incontable: el argumento contable de Cantor de 1874, existencia únicamente por cardinalidad.

Teorema 1.9 (Cantor; incontabilidad de $\R$ )

Para cada conjunto $E$ , no hay sobreyección $E \to \mathcal{P}(E)$ .
$\R$ es no contable.

Demostración. (1) se demostró en el volumen del Año 1 (el conjunto diagonal $D = \{x : x \notin f(x)\}$ ).

(2) Supongamos que $(x_n)_{n \in \N}$ enumera $\R$ . Construir segmentos anidados $I_0 \supseteq I_1 \supseteq \dots$ con $\abs{I_n} = 3^{-n}$ y $x_n \notin I_n$ : divide el segmento actual en tres tercios cerrados; al menos un tercio evita $x_n$ (un punto cumple como máximo dos de los tres). El teorema de los segmentos anidados (puntos finales adyacentes) proporciona $\ell \in \bigcap_n I_n$ ; pero $\ell = x_N$ para algunos $N$ y $x_N \notin I_N$ : contradicción. ∎

Teorema 1.10 (Cantor–Bernstein)

Si $E$ se inyecta en $F$ y $F$ se inyecta en $E$ , entonces $E$ y $F$ son equipotente.

Demostración. Sean $f \colon E \to F$ y $g \colon F \to E$ inyecciones. Para cada punto (de $E$ o $F$ ), traza su cadena ancestral de preimágenes sucesivas, $x \mapsto g^{-1}(x) \mapsto f^{-1}(g^{-1}(x)) \mapsto \dots$ — cada paso está definido siempre que el punto actual se encuentra en la imagen de la inyección correspondiente, y es entonces único por inyectividad. Tres destinos mutuamente excluyentes: la cadena se detiene en un punto de $E \setminus g(F)$ (origen en $E$ ), se detiene en un punto de $F \setminus f(E)$ (origen en $f$ ) o nunca se detiene. Esto divide $E = E_E \cup E_F \cup E_\infty$ y $F = F_E \cup F_F \cup F_\infty$ de acuerdo con el origen.

Ahora observe: $f$ mapas $E_E$ sobre $F_E$ — la cadena de $f(x)$ es la cadena de $x$ con el prefijo de un paso, por lo que los orígenes coinciden; y cada $y \in F_E$ tiene una cadena con al menos un paso (su origen se encuentra en $E$ ), por lo que $y = f(x)$ con $x \in E_E$ . El mismo argumento da biyecciones $f \colon E_\infty \to F_\infty$ y $g \colon F_F \to E_F$ . pegado,

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

es una biyección de $E$ sobre $F = F_E \cup F_\infty \cup F_F$ : es biyectivo por partes, y las tres piezas objetivo son disjuntas. ∎

Ejemplo 1.11

$\intoo{0}{1}$ y $\intcc{0}{1}$ son equipotente: la identidad inyecta de una manera, $x \mapsto \frac{x + 1}{3}$ de la otra; el teorema fabrica la biyección (necesariamente discontinua). igualmente $\R$ , $\intoo{0}{1}$ (vía biyecciones tipo $\tanh$ ) y $\mathcal{P}(\N)$ (expansiones binarias, Ejercicio 1.3) son todos equipotente: “la cardinalidad del continuo”.

Ejemplo 1.12 (El segmento y el cuadrado.)

$\intcc{0}{1}$ y $\intcc{0}{1}^2$ son equipotente — dimensión es invisible a la cardinalidad. Una inyección es trivial: $x \mapsto (x, 0)$ . Por el otro, envía $(x, y)$ al real cuyo los dígitos decimales intercalan los de $x$ y $y$ ,

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

eligiendo para cada coordenada la expansión que no termina en todos los $9$ ’s: con esa convención los dígitos de la imagen determinar los de $x$ y $y$ , por lo que el mapa es inyectivo (necesita no ser sobreyectivo: las imágenes nunca tienen, digamos, una posición impar dígitos eventualmente $9$ — y eso está bien). Cantor–Bernstein (Teorema 1.10) ensambla una biyección genuina. La continuidad, por supuesto, es desesperado: una biyección continua entre ellos es imposible — Los capítulos sobre métricas explican por qué (la conectividad distingue la línea del avión, Capítulo 4).

1.3 Grupos

Definición 1.13 (Subgrupo generado; orden)

Sea $G$ un grupo y $A \subseteq G$ . El subgrupo generado por $A$ , escrito $\langle A \rangle$ , es el subgrupo más pequeño que contiene $A$ — concretamente, todos los productos finitos de elementos de $A$ y sus inversas. Un grupo es cíclico cuando generado por un elemento: $\langle a\rangle = \{a^k : k \in \Z\}$ . El orden de $a \in G$ es $\operatorname{ord}(a) = \abs{\langle a \rangle}$ (posiblemente infinito); cuando es finito, es el mínimo $n \geq 1$ con $a^n = e$ , y $a^k = e \iff \operatorname{ord}(a) \mid k$ .

Prueba de caracterización del pedido. Si hay algo de $a^m = e$ con $m \geq 1$ , dejemos que $n \geq 1$ sea el menor con $a^n = e$ . Los elementos $e, a, \dots, a^{n-1}$ son distintos por pares. ( $a^{i} = a^{j}$ con $0 \leq i < j < n$ da $a^{j-i} = e$ , minimalidad contradictoria), y cada $a^k$ se reduce a uno de ellos por División euclidiana $k = nq + r$ : $\langle a\rangle$ tiene exactamente $n$ elementos, y $a^k = a^r = e \iff r = 0 \iff n \mid k$ . si no hay poder es trivial, todos los $a^k$ ( $k \in \Z$ ) son distintos (misma división argumento) y el orden es infinito. ∎

Teorema 1.14 (Lagrange)

Sea $G$ un grupo finito y $H$ un subgrupo. Entonces $\abs H$ divide $\abs G$ . En particular el orden de cada El elemento divide $\abs G$ y $a^{\abs G} = e$ para todo $a \in G$ .

Demostración. La relación $x \sim y \iff x^{-1}y \in H$ es una equivalencia (reflexivo: $e \in H$ ; simétrico: inversas; transitivo: productos). La clase de $x$ es la clase izquierda $xH = \{xh : h \in H\}$ , and $h \mapsto xh$ is a bijection $H \to xH$ (inverse $y \mapsto x^{-1}y$ ): all classes have $\abs H$ elements. Partición de clases $G$ (el teorema de partición general del volumen del Año 1), entonces $\abs G = \abs H \times (\text{number of cosets})$ . Para un elemento: aplique esto a $H = \langle a\rangle$ ; luego $a^{\abs G} = (a^{\operatorname{ord} a})^{\abs G / \operatorname{ord} a} = e$ . ∎

Ejemplo 1.15 (Cosets en acción: $A_3$ dentro de $\mathfrak{S}_3$ )

Tome $G = \mathfrak{S}_3$ (orden $6$ ) y $H = A_3 = \{\mathrm{id},\ (1\,2\,3),\ (1\,3\,2)\}$ . Las clases laterales izquierdas son

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

dos clases de tres elementos que dividen $G$ , exactamente como el contar $\abs G = \abs H \times (\text{number of cosets})$ demandas — y visiblemente la división en pares e impares permutaciones. Nota $(1\,3)H = (1\,2)H$ aunque $(1\,3) \neq (1\,2)$ : las clases laterales son clases, no etiquetadas por su representantes, y $x^{-1}y \in H$ es el único legítimo comparación. Este cuadro de dos clases es el general para el firma: $A_n$ y su única pareja coset dividida $\mathfrak{S}_n$ por la mitad, que así es el problema del fin de semana cuenta las posiciones de rompecabezas alcanzables.

Ejemplo 1.16

Dos dividendos inmediatos. Groups of prime orden are cíclico: si $\abs G = p$ es primo y $a \neq e$ , entonces $\operatorname{ord}(a)$ divide $p$ y no es $1$ , por lo que es $p$ : $\langle a\rangle = G$ . The subgroup lattice of $\Z/12\Z$ : por Proposición 1.17 a continuación, hay exactamente uno subgrupo por divisor de $12$ — pedidos $1, 2, 3, 4, 6, 12$ , generado respectivamente por $\overline 0$ , $\overline 6$ , $\overline 4$ , $\overline 3$ , $\overline 2$ , $\overline 1$ . el cierre precaución: el conversar de Lagrange falla en general — $A_4$ tiene orden $12$ pero ningún subgrupo de orden $6$ , como demostramos en este Problema de fin de semana del capítulo (Problema 1.1, pregunta 14). Lagrange restringe lo posible pedidos; no les promete.

La red de subgrupos de ℤ/12ℤ: un subgrupo por divisor de 12 (), con un borde cuando uno contiene al otro con índice primo. Se ejecutan inclusiones contra divisibilidad del generador: 4 ⊂eq 2porque 4 es un múltiplo de 2. — La red de subgrupos de $\Z/12\Z$ : un subgrupo por divisor de $12$ (Proposición 1.17), con un borde cuando uno contiene al otro con índice primo. Se ejecutan inclusiones *contra* divisibilidad del generador: $\langle\overline 4\rangle \subseteq \langle\overline2\rangle$ porque $4$ es un múltiplo de $2$ .

Proposición 1.17 (Grupos cíclicos)

Sea $G = \langle a \rangle$ cíclico de orden $n$ .

$G$ es isomorfo a $(\Z/n\Z, +)$ , a través de $\overline k \mapsto a^k$ .
Cada subgrupo de $G$ es cíclico; para cada divisor $d \mid n$ hay exactamente un subgrupo de orden $d$ , a saber, $\langle a^{n/d}\rangle$ .
$a^k$ genera $G$ si y sólo si $\gcd(k, n) = 1$ : $G$ tiene Generadores $\varphi(n)$ (función de Euler).

Demostración. (1) El mapa $k \mapsto a^k$ de $\Z$ a $G$ es compatible con mod de congruencia $n$ ( $a^{k} = a^{k'} \iff n \mid k - k'$ , por el orden caracterización); la propiedad universal (Definición 1.3) produce una biyectiva bien definida morfismo de $\Z/n\Z$ .

(2) Sea $H \leq G$ no trivial y $m$ menos $\geq 1$ con $a^m \in H$ . La división euclidiana muestra $H = \langle a^m\rangle$ (para $a^k \in H$ : $k = mq + r$ fuerza a $a^r \in H$ , por lo que $r = 0$ ) y $m \mid n$ (dividir $n$ por $m$ : $a^{n \bmod m} \in H$ ). Entonces $\abs H = n/m$ ; tomando $m = n/d$ se realiza cada divisor $d$ . Unicidad: cualquier subgrupo de orden $d$ es, por lo anterior, de la forma $\langle a^m \rangle$ con $n/m = d$ — entonces $m = n/d$ es forzado y el subgrupo es determinado.

(3) Reclamamos $\operatorname{ord}(a^k) = \frac{n}{\gcd(k, n)}$ . Escribe $d = \gcd(k, n)$ . Para cualquier $m \geq 1$ , el orden La caracterización de Definición 1.13 da la cadena de equivalencias

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

el último paso por el lema de Gauss, desde $\frac nd$ y $\frac kd$ son coprimos. El mínimo $m$ es $\frac nd$ : $\operatorname{ord}(a^k) = \frac n{\gcd(k,n)}$ , que es igual a $n$ y si $\gcd(k, n) = 1$ . Hay $\varphi(n)$ tales clases $k$ módulo $n$ . ∎

1.4 El grupo simétrico

Definición 1.18

$\mathfrak{S}_n$ es el grupo de permutaciones de $\intint{1}{n}$ (orden $n!$ ). A ciclo $(a_1\,a_2\,\cdots\,a_k)$ mapas $a_1 \mapsto a_2 \mapsto \dots \mapsto a_k \mapsto a_1$ y arregla todo lo demás; $k$ es su longitud, un ciclo $2$ es un transposición. Dos ciclos son desarticular cuando su Los soportes (puntos no fijos) son.

Teorema 1.19 (Descomposicion del ciclo)

Cada permutación $\sigma \neq \mathrm{id}$ es un producto de pares disjunto ciclos, unívocamente hasta el orden de los factores. disjunto ciclos conmuta, y $\operatorname{ord}(\sigma)$ es el mcm del longitudes.

Demostración. Considere la relación “órbita” sobre el soporte de $\sigma$ : $x \sim y$ iff $y = \sigma^k(x)$ para algunos $k \in \Z$ — una equivalencia relación. Cada clase $\{x, \sigma(x), \dots, \sigma^{k-1}(x)\}$ (finito, por lo que itera ciclo hacia atrás — la primera repetición debe regresar a $x$ por inyectividad) lleva el ciclo $(x\ \sigma(x)\ \cdots\ \sigma^{k-1}(x))$ , y $\sigma$ es el producto de estos ciclos: en cada órbita actúa únicamente el ciclo correspondiente. Unicidad: cualquier factorización ciclo disjunto reproduce exactamente la órbitas (de ciclo a $x$ deben ser $(x\ \sigma(x)\ \cdots)$ ). Conmutación disjunta ciclos ya que mueven puntos disjuntos; el orden La declaración sigue porque $\sigma^m = \mathrm{id}$ si cada ciclo $m$ -ésima potencia es (desunión), si cada longitud divide a $m$ . ∎

Ejemplo 1.20 (Tipo de ciclo como censo)

¿Cuántas permutaciones de $\mathfrak{S}_9$ tienen el tipo ciclo? $(4, 3, 2)$ — ¿un ciclo $4$ , un ciclo $3$ , un transposición? Elige los soportes y las órdenes cíclicas:

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

Enumere los nueve símbolos seguidos (formas $9!$ ), ponga entre corchetes el primero. cuatro, los tres siguientes, los dos últimos en ciclos y dividir por el rotaciones dentro de cada soporte ( $4$ , $3$ y $2$ de ellos) que dar la misma permutación. (Distinto ciclo longitudes aquí, así que no hay más división; longitudes iguales también requerirían dividiendo por las permutaciones de los corchetes iguales.) Cada uno de esos la permutación tiene orden $\operatorname{lcm}(4,3,2) = 12$ y firma $(-1)^3(-1)^2(-1)^1 = +1$ (Teorema 1.19 y el teorema de la firma a continuación). Una partición de $9$ , una clase de conjugación, un censo — la combinatoria de $\mathfrak{S}_n$ es la aritmética de particiones.

Teorema 1.21 (Firma)

Hay exactamente un morfismo de grupo $\varepsilon \colon \mathfrak{S}_n \to \{\pm 1\}$ (para $n \geq 2$ ) que toma el valor $-1$ en transposiciones: el firma. Además $\varepsilon(\sigma) = (-1)^{I(\sigma)}$ donde $I(\sigma)$ es el número de inversiones (pareja $i < j$ con $\sigma(i) > \sigma(j)$ ), un ciclo $k$ tiene la firma $(-1)^{k-1}$ y el grupo alterno $A_n = \ker\varepsilon$ tiene orden $\frac{n!}{2}$ .

Demostración. Existencia. Para el conjunto $\sigma \in \mathfrak{S}_n$

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

Los valores absolutos de los factores se multiplican a $1$ (los pares desordenados $\{\sigma(i), \sigma(j)\}$ pasa por todos los pares), por lo que $\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),

el producto medio es $\varepsilon(\sigma)$ después de reindexar por los pares $\{\tau(i), \tau(j)\}$ (cada par desordenado aparece una vez, y numerador y denominador invierten el signo juntos). A transposición $\tau = (a\,b)$ con $a < b$ tiene un número impar de inversiones; contado exactamente: los pares invertidos $(i, j)$ , $i < j$ , con $\tau(i) > \tau(j)$ son

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

ese es $(b - a - 1) + (b - a - 1) + 1 = 2(b - a) - 1$ de ellos, extraño. (Alternativamente: marque $(1\,2)$ directamente, con uno inversión y conjugado — los conjugados tienen la misma firma ya que $\varepsilon$ es un morfismo para un grupo abeliano). Por lo tanto $\varepsilon((a\,b)) = (-1)^{2(b-a)-1} = -1$ .

Unicidad. Transposiciones genera $\mathfrak{S}_n$ (cualquier ciclo $(a_1\cdots a_k) = (a_1\,a_k)(a_1\,a_{k-1})\cdots(a_1\,a_2)$ , y acabados Teorema 1.19); un morfismo para $\{\pm1\}$ está determinado por sus valores en los generadores.

Consecuencias. La identidad ciclo anterior escribe un ciclo $k$ como $k - 1$ transposiciones: firma $(-1)^{k-1}$ . $A_n$ : el morfismo $\varepsilon$ es sobreyectivo (transposiciones existe para $n \geq 2$ ), y los dos “cosets” $A_n$ y $(1\,2)A_n$ son equipotente y partición $\mathfrak{S}_n$ (argumento de Lagrange): $\abs{A_n} = \frac{n!}{2}$ . ∎

Ejemplo 1.22

$\sigma = \begin{pmatrix} 1&2&3&4&5&6\\ 3&6&5&4&1&2 \end{pmatrix} = (1\,3\,5)(2\,6)$ : orden $\operatorname{lcm}(3,2) = 6$ , firma $(-1)^{2}\cdot(-1)^{1} = -1$ . La firma es la más rápida. verificación de paridad en mezclas — y el motor del determinante en Capítulo 2.

Ejemplo 1.23 (Tres caminos para una señal)

Deje que $\sigma \in \mathfrak{S}_5$ envíe $1, 2, 3, 4, 5$ a $3, 5, 4, 1, 2$ . Via ciclos: $1 \mapsto 3 \mapsto 4 \mapsto 1$ y $2 \mapsto 5 \mapsto 2$ , por lo que $\sigma = (1\,3\,4)(2\,5)$ y $\varepsilon(\sigma) = (-1)^{2}(-1)^{1} = -1$ . Vía inversiones: en la lista de valores $3, 5, 4, 1, 2$ el fuera de servicio los pares son $(3,1)$ , $(3,2)$ , $(5,4)$ , $(5,1)$ , $(5,2)$ , $(4,1)$ , $(4,2)$ : siete de ellos, y $(-1)^7 = -1$ . Via transposiciones: $\sigma = (1\,4)(1\,3)(2\,5)$ , tres factores, $(-1)^3 = -1$ . Tres cálculos, una paridad: la unicidad en Teorema 1.21 garantiza que no se realizará ninguna contabilidad. El esquema puede alguna vez hacerlos estar en desacuerdo — que es exactamente lo que los hace $\varepsilon$ utilizable como invariante (ver el problema del fin de semana).

Observación 1.24 (A dónde va la firma desde aquí)

La firma es la semilla de tres cosechas posteriores: construye el determinante y su regla del producto en Capítulo 2; le da poder invariantes de paridad para acertijos combinatorios (el fin de semana de este capítulo problema resuelve los quince rompecabezas con él); y la alternancia Los grupos $A_n$ que define se vuelven centrales en el volumen del Año 3, donde su simplicidad para $n \geq 5$ explica por qué las ecuaciones de grado $5$ no tienen solución en radicales.

1.5 Anillos, ideales, cocientes.

Definición 1.25 (Ideal)

Sea $A$ un anillo conmutativo. Un ideal $I \subseteq A$ es un subgrupo aditivo tal que $a x \in I$ para todos $a \in A$ , $x \in I$ . Los núcleos de morfismos de anillo son ideales; $I = A$ si $1 \in I$ si $I$ contiene una unidad. El generado ideal de $x$ es $xA = \{xa\}$ (un ideal principal).

Teorema 1.26 (Ideales de $\Z$ y de $K[X]$ )

Cada ideal de $\Z$ es $n\Z$ para un $n \in \N$ único; cada ideal de $K[X]$ ( $K$ un campo) es $P\,K[X]$ para un monic único (o cero) $P$ . En consecuencia, los mcd existen en ambos anillos con relaciones de Bézout: $x\Z + y\Z = \gcd(x,y)\Z$ , y lo mismo ocurre con los polinomios.

Demostración. Para $\Z$ este fue el teorema de subgrupo del volumen del Año 1 (un ideal es en particular un subgrupo, y $n\Z$ es un ideal). Para $K[X]$ : deja $I \neq \{0\}$ sea ideal y $P \in I$ distinto de cero de grado mínimo, mónico normalizado. Para $F \in I$ , división euclidiana $F = PQ + R$ da $R = F - PQ \in I$ con $\deg R < \deg P$ : la minimalidad fuerza a $R = 0$ , por lo que $I = P\,K[X]$ . Unicidad: dos generadores mónicos se dividen cada uno otro. Las declaraciones de Bézout son la igualdad del ideal $x\Z + y\Z$ (resp. su análogo polinómico) con el principal ideal del mcd — la definición misma de mcd utilizada en el año 1, ahora reconocida como una declaración sobre ideales. ∎

Ejemplo 1.27 (Un polinomio mcd, dos formas)

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

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

entonces el mcd es $X - 1$ , y la sustitución hacia atrás da el Bézout relación

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

By ideales: el ideal $(X^3 - 1)\Q[X] + (X^2 - 1)\Q[X]$ es principal (Teorema 1.26); contiene $X - 1$ (la pantalla) y está contenido en $(X - 1)\Q[X]$ (ambos los generadores desaparecen en $1$ , por lo tanto son múltiplos de $X - 1$ ): El generador monónico es $X - 1$ . La idea final: el ideal punto de vista identifica el mcd sin dividir — común Las raíces localizan el ideal y Euclid simplemente lo certifica.

Definición 1.28 (Anillo de cociente $\Z/n\Z$ , revisado)

Para un ideal $I$ de $A$ , la relación $x \sim y \iff x - y \in I$ es una equivalencia compatible con $+$ y $\times$ ; el conjunto cociente $A/I$ hereda una estructura de anillo — el cociente anillo — haciendo de $\pi \colon A \to A/I$ un morfismo con kernel $I$ . Para $A = \Z$ , $I = n\Z$ este es el $\Z/n\Z$ del volumen Año 1, ahora con su propiedad universal: cualquiera El morfismo mata los factores $I$ hasta $A/I$ .

Teorema 1.29 (Teorema chino del resto, forma de anillo)

Si $\gcd(m, n) = 1$ , el mapa

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

es un isomorfismo de anillo. En consecuencia $\varphi(mn) = \varphi(m)\varphi(n)$ para coprime $m, n$ , y

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

Demostración. El mapa es un morfismo de anillo bien definido (las compatibilidades son inmediato). Inyectividad: $x \equiv 0$ mod $m$ y mod $n$ con $\gcd(m,n) = 1$ fuerza a $mn \mid x$ (Gauss). Sobreyectividad: ambos lados tienen elementos $mn$ , por lo que la inyectividad es suficiente (finita igual cardinalidades) — o explícitamente: de una relación Bézout $um + vn = 1$ , la clase de

x = b\,um + a\,vn

se asigna a $(a \bmod m,\ b \bmod n)$ , ya que $vn = 1 - um \equiv 1 \pmod m$ hace $x \equiv a \pmod m$ , y modifica simétricamente $n$ — la receta utilizada numéricamente en Ejemplo 1.30. Las unidades corresponden a pares de unidades (el anillo de un producto las unidades son los pares de unidades), por lo que $\varphi(mn) = \varphi(m)\varphi(n)$ . Para una potencia primaria, $\varphi(p^k) = p^k - p^{k-1}$ (el mod $p^k$ que no es unidad son los múltiplos de $p$ ); la multiplicatividad ensambla la fórmula del producto. ∎

Ejemplo 1.30 (Invirtiendo el isomorfismo chino)

Tome $m = 8$ , $n = 9$ . Se hace el inverso del isomorfismo. explícito por los dos idempotentes: buscar $u \equiv 1 \pmod 8$ , $u \equiv 0 \pmod 9$ y $v \equiv 0 \pmod 8$ , $v \equiv 1 \pmod 9$ . De $u = 9k \equiv 1 \pmod 8$ : $k \equiv 1$ , entonces $u = 9$ ; de $v = 8k \equiv 1 \pmod 9$ : $-k \equiv 1$ , $k \equiv 8$ , entonces $v = 64$ . Entonces la clase de $x = 9a + 64b$ módulo $72$ es la única solución de $x \equiv a \pmod 8$ , $x \equiv b \pmod 9$ : para $a = 3$ , $b = 5$ se obtiene $27 + 320 = 347 \equiv 59 \pmod{72}$ — exactamente el valor intermedio encontrado por sustitución en Ejercicio 1.8. La idea final: $u$ y $v$ satisfacer $u + v \equiv 1$ , $uv \equiv 0$ , $u^2 \equiv u$ , $v^2 \equiv v$ módulo $72$ ; son las imágenes de $(1, 0)$ y $(0, 1)$ , y cada descomposición china es en el fondo una descomposición de $1$ en idempotentes ortogonales.

Teorema 1.31 (Euler; Fermat revisitado)

Las unidades de $\Z/n\Z$ forman un grupo de orden $\varphi(n)$ ; por lo tanto para $\gcd(a, n) = 1$ :

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

y el pequeño teorema de Fermat es el caso $n = p$ primo, ahora una línea de Lagrange.

Demostración. Las clases invertibles son exactamente las de los números enteros coprimos a $n$ (Volumen Año 1): $\varphi(n)$ de ellos, formando un grupo bajo multiplicación. Lagrange (Teorema 1.14): cada elemento al poder del grupo orden es la identidad. ∎

Ejemplo 1.32 (Un grupo de unidades sin generador.)

El grupo $(\Z/15\Z)^*$ tiene elementos $\varphi(15) = \varphi(3)\varphi(5) = 8$ . ¿Es cíclico? Calcule pedidos usando el idioma chino. isomorfismo $(\Z/15\Z)^* \simeq (\Z/3\Z)^* \times (\Z/5\Z)^*$ (una unidad mod $15$ es un par de unidades): los factores tienen pedidos $2$ y $4$ , por lo que orden de cada elemento se divide $\operatorname{lcm}(2, 4) = 4 < 8$ — no se genera ningún elemento. 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} :

pedidos $4, 2, 4, 2, 2$ y nunca $8$ . Contraste con Ejercicio 1.10: $(\Z/p\Z)^*$ is cíclico para $p$ primo, porque allí el grupo unitario se encuentra dentro de un campo. El teorema de Euler todavía se aplica con el exponente $\varphi(15) = 8$ , pero el verdadero exponente universal aquí es $4$ — Euler es un límite superior, no siempre el más agudo.

Definición 1.33 (Álgebra)

Un $K$ -álgebra es un espacio vectorial $K$ $A$ con un estructura en anillo cuya multiplicación es $K$ -bilineal. Ejemplos: $K[X]$ , $\mathcal{M}_n(K)$ , $\mathcal{L}(E)$ , espacios funcionales $\mathcal{F}(X, K)$ , $\C$ como álgebra $\R$ . Morfismos de álgebras son morfismos de anillos lineales; el evaluación $P \mapsto P(u)$ de $K[X]$ a $\mathcal{L}(E)$ (o $\mathcal{M}_n(K)$ ) es el ejemplo central, conduciendo Capítulo 3.

Ejemplo 1.34 (Un morfismo de evaluación y su núcleo)

Tome $A = \begin{pmatrix}0 & 1\\ 0 & 0\end{pmatrix}$ y el evaluación $\varepsilon_A \colon \R[X] \to \mathcal{M}_2(\R)$ , $P \mapsto P(A)$ . Desde $A^2 = 0$ ,

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

(solo sobreviven los términos constante y lineal de $P$ ). Por lo tanto $\ker\varepsilon_A = \{P : P(0) = P'(0) = 0\} = X^2\,\R[X]$ : un principal ideal, exactamente como Teorema 1.26 predice, generado por el mónico $X^2$ de menor grado en el kernel — el polinomio mínimo de $A$ , estrella de Capítulo 3. La imagen es bidimensional. conmutativo álgebra $\{aI + bA\}$ : los morfismos de evaluación se reducen el $\R[X]$ de dimensión infinita en el pequeño álgebras computable.

Observación 1.35 (Perspectivas: tres melodías para escuchar)

Tres ideas estructurales de este capítulo se repiten a lo largo del volumen, cada vez con una orquestación más pesada. Factorización a través de un cociente (Definición 1.3): es construye $\Z/n\Z$ aquí, define mapas en conjuntos de soluciones de lineal sistemas en Capítulo 2, y subyace silenciosamente a cada Argumento "bien definido en clases". Invariantes: el la firma es un morfismo de $\{\pm1\}$ que ningún movimiento legal puede esquivar — la misma lógica da la regla del producto del determinante (Capítulo 2), la invariancia de similitud de la traza, y las cantidades conservadas de Capítulo 16. Contando contra una estructura: Lagrange cuenta hasta el final clases laterales, recuento de dimensiones a través de bases (Capítulo 2), la multiplicidad cuenta mediante polinomio grados (Capítulo 3); cada vez que un atado mira milagroso, alguna partición o clasificación está haciendo el conteo.

Observación 1.36 (Errores comunes)

Cuatro clásicos. (i) Se debe verificar un mapa en un cociente bien definido: “ $\overline x \mapsto$ (fórmula en $x$ )” es legítimo sólo si la fórmula es constante en las clases — la compatibilidad de Definición 1.3, no un formalidad. (ii) $\operatorname{ord}(ab) = \operatorname{lcm}(\operatorname{ord}a, \operatorname{ord}b)$ es FALSO en general, incluso para elementos conmutantes ( $a$ y $a^{-1}$ ); Ejercicio 1.4 da la respuesta correcta declaración de coprimo y conmutación, y disjunto ciclos el versión de permutación correcta. (iii) Contabilidad sobrevive contable sindicatos y productos finito, pero no Productos contable: $\{0,1\}^{\N}$ es incontable (Ejercicio 1.3) aunque cada factor tiene dos elementos. (iv) Cantor–Bernstein sólo necesita inyecciones tanto maneras, pero la biyección que construye suele ser discontinua y no explícito — no esperes una fórmula (Ejemplo 1.11).

Observación 1.37 (Dónde se utiliza este capítulo)

Casi en todas partes. La firma construye determinantes (Capítulo 2); el morfismo de evaluación $P \mapsto P(u)$ y el principal ideales de $K[X]$ producen polinomios mínimos y las descomposiciones del núcleo de Capítulo 3; contabilidad es el escenario en el que actúa Capítulo 21 (probabilidad en contable espacios) y la razón por la que la topología sigue produciendo contable conjuntos densos (Capítulo 4). La construcción del cociente $A/I$ se redistribuye en el volumen del Año 3 para construir campos $K[X]/(P)$ y, de ellos, la teoría de Galois: la propiedad universal demostrada aquí es utilizado allí palabra por palabra.

1.6 Ceremonias

Ejercicio 1.1 ★

¿Cuál de los siguientes conjuntos es contable? El conjunto de subconjuntos finitos. de $\N$ ; el conjunto de subconjuntos todo de $\N$ ; $\R \setminus \Q$ ; el conjunto de polinomios con coeficientes racionales; el conjunto de secuencias de $0$ y $1$ que finalmente son cero.

Solución

Solución de Ejercicio 1.1.

Finite subsets of $\N$ : contable — el conjunto de subconjuntos de $\intint{0}{n}$ es finito y los subconjuntos finitos forman contable unión sobre $n$ de estos (Proposición 1.6 (3)); infinito ya que contiene todos los singletons.

All subsets of $\N$ : no contable, según el teorema de Cantor (Teorema 1.9 (1) con $E = \N$ ).

$\R \setminus \Q$ : no contable — de lo contrario $\R = \Q \cup (\R\setminus\Q)$ sería una unión de dos conjuntos contables, contradiciendo Teorema 1.9 (2).

Polynomials over $\Q$ : contable — los polinomios de grado $\leq n$ inyectar en $\Q^{n+1}$ (productos finitos de conjuntos contables), y tomar el sindicato sobre $n$ .

Secuencias binarias eventualmente cero: contable — se biyectan con subconjuntos finitos de $\N$ (el soporte).

Ejercicio 1.2 ★

En $\mathfrak{S}_7$ , dejemos $\sigma = (1\,4\,2\,6)(3\,5)$ y $\tau = (2\,3\,7)$ . Calcular $\sigma\tau$ y $\tau\sigma$ en ciclo disjunto formulario, el pedidos y las firmas de las cuatro permutaciones, y $\sigma^{2026}$ .

Solución

Solución de Ejercicio 1.2.

Calcule elemento por elemento, aplicando primero el factor correcto. $\sigma\tau$ envía $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),

un ciclo $7$ . Asimismo $\tau\sigma$ envía $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),

también un ciclo $7$ (como se esperaba: $\sigma\tau$ y $\tau\sigma$ son conjugado, por lo tanto comparten su tipo ciclo).

Órdenes y firmas: $\sigma$ tiene ciclo tipo $(4,2)$ : orden $\operatorname{lcm}(4,2) = 4$ , firma $(-1)^3(-1)^1 = +1$ ; $\tau$ es un ciclo $3$ : orden $3$ , firma $+1$ ; ambos productos son $7$ -ciclos: orden $7$ , firma $(-1)^6 = +1$ .

$\sigma^{2026}$ : $2026 = 4 \times 506 + 2$ , entonces $\sigma^{2026} = \sigma^2 = (1\,2)(4\,6)$ (cuadre el ciclo $4$ ; el transposición cuadrados de distancia).

Ejercicio 1.3 ★

Construya inyecciones explícitas que muestren que $\mathcal{P}(\N)$ , $\intcc{0}{1}$ y el conjunto $\{0,1\}^{\N}$ de secuencias binarias son por pares equipotente (expansiones binarias en ambos sentidos; Cantor–Bernstein absorbe la molestia de la doble representación).

Solución

Solución de Ejercicio 1.3.

$\{0,1\}^{\N} \to \mathcal{P}(\N)$ : una secuencia se asigna a su soporte — una biyección (funciones indicadoras), no se necesita teorema.

$\{0,1\}^{\N} \to \intcc{0}{1}$ : el mapa de base $3$ $(a_n) \mapsto \sum 2a_n 3^{-n-1}$ es inyectivo (dos secuencias distintas difieren primero en el rango $N$ ; las colas no pueden compensar un hueco de $2\cdot 3^{-N-1}$ , ya que $\sum_{n > N} 2\cdot 3^{-n-1} = 3^{-N-1} < 2\cdot3^{-N-1}$ ).

$\intcc{0}{1} \to \{0,1\}^{\N}$ : expansión binaria, eligiendo (digamos) la expansión no termina en todos los $1$ : inyectivo.

Por Cantor–Bernstein (Teorema 1.10) aplicado a las dos últimas inyecciones, $\intcc{0}{1}$ y $\{0,1\}^{\N}$ son equipotente, por lo tanto, los tres conjuntos lo son.

Ejercicio 1.4 ★

Sea $G$ un grupo y $a, b \in G$ elementos conmutadores de elementos finitos coprime pedidos $m$ y $n$ . Demuestre que $\operatorname{ord}(ab) = mn$ . Muestre con un ejemplo en $\mathfrak{S}_3$ que la conmutación es esencial.

Solución

Solución de Ejercicio 1.4.

Deje $c = ab = ba$ y $d = \operatorname{ord}(c)$ . Primero $c^{mn} = a^{mn} b^{mn} = e$ (la conmutación permite dividir la potencia), entonces $d \mid mn$ . Por el contrario, $c^d = e$ da $a^d = b^{-d}$ ; este elemento se encuentra en $\langle a\rangle \cap \langle b\rangle$ , un subgrupo cuyo orden divide $m$ y $n$ (Lagrange en cada grupo cíclico), por lo tanto es trivial: $a^d = b^d = e$ , entonces $m \mid d$ y $n \mid d$ , y por coprimalidad $mn \mid d$ . Por lo tanto $d = mn$ .

En $\mathfrak{S}_3$ : tome $a = (1\,2)$ (orden $2$ ) y $b = (1\,2\,3)$ (orden $3$ ), coprime pedidos, que no conmutan: $ab = (2\,3)$ tiene orden $2 \neq 6$ — de hecho $\mathfrak{S}_3$ no tiene elemento de orden $6$ . La conmutación es esencial.

Ejercicio 1.5 ★★

Sea $G$ un grupo finito de orden pares. Demuestre que $G$ contiene un elemento de orden $2$ . (Empareja cada elemento con su inverso; cuente los que están autoemparejados.)

Solución

Solución de Ejercicio 1.5.

Empareje cada $x \in G$ con $x^{-1}$ . Los pares $\{x, x^{-1}\}$ con $x \neq x^{-1}$ tiene dos elementos y particiona su unión; el Los elementos restantes son exactamente aquellos con $x = x^{-1}$ , es decir, $x^2 = e$ . Dado que $\abs G$ es par y los pares de dos elementos cubren un número de elementos, el conjunto $\{x : x^2 = e\}$ tiene cardinalidad par; contiene $e$ , por lo que contiene al menos otro elemento $x \neq e$ — un elemento de orden $2$ .

Ejercicio 1.6 ★★

Demuestre que $A_n$ ( $n \geq 3$ ) es generado mediante los ciclos $3$ . (A product of two transposiciones is a $3$ -cycle or a product of two $3$ -cycles.)

Solución

Solución de Ejercicio 1.6.

Cada elemento de $A_n$ es producto de un número par de transposiciones (Teorema 1.21: descomponer en transposiciones; el conteo es par ya que la firma es $+1$ ). eso basta con escribir cada producto de dos transposiciones con $3$ -ciclos:

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

(verificar por evaluación), y $(a\,b)(a\,b) = \mathrm{id}$ . Entonces el Los ciclos $3$ generan $A_n$ .

Ejercicio 1.7 ★★

Determine todos los morfismos de grupo: de $(\Q, +)$ a $(\Z, +)$ ; de $(\Z/n\Z, +)$ a $(\Z/m\Z, +)$ (count them: $\gcd(m,n)$ ); de $(\Q, +)$ a $(\Q_+^*, \times)$ .

Solución

Solución de Ejercicio 1.7.

$(\Q,+) \to (\Z,+)$ : sólo el morfismo cero. Para cualquier $x$ y cada $n \geq 1$ , $f(x) = n f\bigl(\frac xn\bigr)$ es divisible por $n$ en $\Z$ ; el único número entero divisible por cada $n$ es $0$ , por lo que $f(x) = 0$ para todos los $x$ .

$(\Z/n\Z, +) \to (\Z/m\Z, +)$ : un morfismo está determinado por $c = f(\overline 1)$ , que debe satisfacer $n c \equiv 0 \pmod m$ , es decir, $c$ es un múltiplo de $\frac{m}{\gcd(m,n)}$ ; hay $\gcd(m,n)$ tales clases, y cada elección define un morfismo (factor $k \mapsto kc$ a $\Z/n\Z$ por la propiedad universal).

$(\Q, +) \to (\Q_+^*, \times)$ : sólo el trivial. si $f(x) = y$ , entonces por cada $n$ , $y = f(n \cdot \frac xn) = f(\frac xn)^n$ es una potencia $n$ en $\Q_+^*$ . Pero un racional $y \neq 1$ no puede ser una potencia $n$ para todos los $n$ : aparece algún primo en $y$ con un exponente distinto de cero $v$ , y $n \nmid v$ para $n > \abs v$ (los exponentes de $n$ -ésima potencia son múltiplos de $n$ , por único factorización). Por lo tanto $f \equiv 1$ .

Ejercicio 1.8 ★★

Usando el teorema del resto chino, calcule $\varphi(360)$ , encuentre todo $x$ con $x \equiv 3 \pmod 8$ , $x \equiv 5 \pmod 9$ y $x \equiv 2 \pmod 5$ , y calcula los dos últimos dígitos de $3^{2026}$ (Euler mod $100$ ; cuidado: funciona mod $4$ y mod $25$ ).

Solución

Solución de Ejercicio 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$ coprimo por pares, total $360$ . De $x \equiv 3 \pmod 8$ y $x \equiv 5 \pmod 9$ : $x = 3 + 8k$ con $3 + 8k \equiv 5 \pmod 9$ , es decir $-k \equiv 2$ , $k \equiv -2 \equiv 7 \pmod 9$ : $x \equiv 3 + 56 = 59 \pmod{72}$ . Luego $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}$ .

Los dos últimos dígitos de $3^{2026}$ : mod $4$ , $3^{2026} = 9^{1013} \equiv 1$ . Mod $25$ : $\varphi(25) = 20$ y $2026 = 20\cdot101 + 6$ , entonces $3^{2026} \equiv 3^6 = 729 \equiv 4 \pmod{25}$ . Resuelva $x \equiv 1 \pmod 4$ , $x \equiv 4 \pmod{25}$ : $x = 4 + 25k \equiv 1 \pmod 4$ da $k \equiv 1 \pmod 4$ : $x \equiv 29 \pmod{100}$ . los dos ultimos Los dígitos son $29$ .

Ejercicio 1.9 ★★★

Demuestre que un dominio integral finito es un campo. deducir eso $\Z/n\Z$ es un campo si $n$ es primo (nuevamente).

Solución

Solución de Ejercicio 1.9.

Sea $A$ un dominio integral finito y $a \in A$ , $a \neq 0$ . el el mapa $x \mapsto ax$ es inyectivo ( $ax = ay \implies a(x - y) = 0 \implies x = y$ , sin divisores de cero); un mapa inyectivo de un conjunto finito en sí mismo es sobreyectivo (volumen del año 1, la equivalencia del casillero). Entonces $1 = ab$ para algunos $b$ : cada elemento distinto de cero es invertible, $A$ es un campo.

$\Z/n\Z$ : si $n$ es primo es un dominio integral ( $n \mid ab \implies n \mid a$ o $n \mid b$ , lema de Euclides), finito, por lo tanto un campo; si $n = rs$ es compuesto, $\overline r\,\overline s = \overline 0$ presenta divisores cero.

Ejercicio 1.10 ★★★

(Un clásico) Sea $K$ un campo y $G$ un subgrupo finito de $(K^*, \times)$ . Demuestre que $G$ es cíclico. Hint: let $m$ be the maximal orden among elements of $G$ ; show every element’s orden divides $m$ (using Ejercicio 1.4 on suitable coprime parts), so all of $G$ satisfies $x^m = 1$ ; count roots of $X^m - 1$ . En particular, $(\Z/p\Z)^*$ es cíclico.

Solución

Solución de Ejercicio 1.10.

Sea $m = \max\{\operatorname{ord}(x) : x \in G\}$ , alcanzado en $a$ .

Claim: every $x \in G$ has orden dividing $m$ . Supongamos que algunos $x$ tiene orden $q$ con $q \nmid m$ : entonces algo de poder primario $p^k$ divide $q$ pero no $m$ . Escriba $m = p^j m'$ con $p \nmid m'$ y $j < k$ . El elemento $a^{p^j}$ tiene orden $m'$ ; el elemento $x^{q/p^k}$ tiene orden $p^k$ ; estos pedidos son coprimos y los dos los elementos conmutan ( $G \subseteq K^*$ es abeliano), por lo que por Ejercicio 1.4 su producto tiene orden $p^k m' > p^j m' = m$ : maximalidad contradictoria.

Entonces todo $x \in G$ satisface $x^m = 1$ : el polinomio $X^m - 1$ tiene en menos raíces $\abs G$ en el campo $K$ , de donde $\abs G \leq m$ (un polinomio distinto de cero de grado $m$ tiene como máximo raíces $m$ , Año 1 volumen). Pero $m = \operatorname{ord}(a) \leq \abs G$ de Lagrange. Por lo tanto $m = \abs G$ y $\langle a \rangle$ , de cardinalidad $m = \abs G$ , son todos de $G$ : cíclico.

Para $K = \Z/p\Z$ : $(\Z/p\Z)^*$ es un subgrupo finito de $K^*$ , por lo tanto cíclico (de orden $p - 1$ ).

Ejercicio 1.11 ★★★

Demostrar que el grupo $(\Q, +)$ no es cíclico, y peor aún: no lo es incluso finitamente generado. Demuestre por otro lado que cada finitamente El subgrupo generado de $(\Q, +)$ es cíclico.

Solución

Solución de Ejercicio 1.11.

Not cíclico: el subgrupo $\langle \frac pq\rangle$ está formado de los múltiplos enteros de $\frac pq$ , todos los cuales tienen denominador que divide $q$ (en términos más bajos); por lo tanto se pierde $\frac{1}{2q}$ . Ningún generador por sí solo puede alcanzar lo ilimitado denominadores de $\Q$ .

Not finitely generado: el subgrupo generado por $\frac{p_1}{q_1}, \dots, \frac{p_k}{q_k}$ consta de racionales cuyos denominadores dividen a $Q = q_1 \cdots q_k$ (combinaciones de números enteros tiene denominador dividiendo $Q$ ): falta $\frac{1}{2Q}$ .

Finitely generado subgroups are cíclico: con $Q$ como arriba, el subgrupo $H = \langle \frac{p_1}{q_1}, \dots, \frac{p_k}{q_k}\rangle$ está contenido en $\frac{1}{Q}\Z$ . El mapa $x \mapsto Qx$ es un isomorfismo de $\frac1Q\Z$ a $\Z$ que lleva $H$ a un subgrupo de $\Z$ , que es $n\Z$ para algunos $n$ (Año 1 volumen): entonces $H = \frac{n}{Q}\Z$ es cíclico, generado por $\frac nQ$ .

Ejercicio 1.12 ★★

(Criterio de Dedekind) Demuestre que todo conjunto infinito contiene un subconjunto contable, y deducir que un conjunto $E$ es infinito si y sólo si es equipotente a un subconjunto adecuado de sí mismo. (For the direct implication, shift a contable subset by one step; for the converse, recall the pigeonhole principle.)

Solución

Solución de Ejercicio 1.12.

A contable subset. Sea $E$ infinito. Construya $a_0, a_1, a_2, \dots$ de forma inductiva: $E$ no está vacío, elija $a_0 \in E$ ; si se elige $a_0, \dots, a_n$ , $E \setminus \{a_0, \dots, a_n\}$ no está vacío ( $E$ no es finito), elija $a_{n+1}$ allí. el $a_n$ se distinguen por pares por construcción, por lo que $A = \{a_n : n \in \N\}$ es un subconjunto contable de $E$ .

Infinite $\implies$ equipotente to a proper subset. Definir $f \colon E \to E \setminus \{a_0\}$ por $f(a_n) = a_{n+1}$ y $f(x) = x$ para $x \notin A$ . Es inyectivo (las dos piezas son inyectiva con imágenes disjuntas) y sobreyectiva en $E \setminus \{a_0\}$ : cada $a_{n+1}$ es alcanzado, cada $x \notin A$ es alcanzado. entonces $E$ es equipotente para el subconjunto adecuado $E \setminus \{a_0\}$ .

Conversar. Si $E$ es finito y $g \colon E \to F$ es un biyección en $F \subseteq E$ con $F \neq E$ , entonces $g$ es un inyección de $E$ en sí mismo que no es sobreyectiva, contradiciendo el principio del casillero (volumen del año 1: una el automapa inyectivo de un conjunto finito es biyectivo). Entonces un conjunto equipotente a un subconjunto adecuado es infinito.

1.7 Problema: El rompecabezas de los quince

El rompecabezas de quince es una bandeja $4 \times 4$ que contiene quince rompecabezas deslizantes. mosaicos numerados $1$ a $15$ y una celda vacía; un movimiento desliza uno de las fichas adyacentes a la celda vacía en ella. En la década de 1890 Sam Loyd popularizó el rompecabezas ofreciendo $1000 a cualquiera que pudiera intercambie los mosaicos $14$ y $15$ y devuelva cada dos mosaicos a su lugar. Nadie cobró nunca, y este problema del fin de semana demuestra ambas cosas. mitades del motivo: la firma de Teorema 1.21 prohíbe el intercambio de Loyd, y — la mitad más dura y constructiva — todo la la firma lo permite es realmente solucionable. La declaración completa es la Johnson–Teorema de la historia (1879).

La configuración resuelta y 14–15 de Sam Loyd configuración. La pregunta $1000: ¿pueden las diapositivas legales girar a la derecha? bandeja en la izquierda? — La configuración resuelta y $14$ – $15$ de Sam Loyd configuración. La pregunta $1000: ¿pueden las diapositivas legales girar a la derecha? bandeja en la izquierda?

Problema 1.1

Problema del fin de semana — la historia de Johnson teorema de solubilidad

Numere las celdas $1$ a $16$ en orden de lectura (de izquierda a derecha, arriba hacia abajo), de modo que la celda $k$ se encuentre en la fila $i$ y en la columna $j$ con $k = 4(i - 1) + j$ . La celda $16$ (abajo a la derecha) es la hogar de la celda vacía; tratamos la celda vacía como un decimosexto mosaico, escrito $b$ e identificado con el número $16$ . un configuración es una biyección $\sigma \colon \intint1{16} \to \intint1{16}$ , contenido de la celda $\mapsto$ ; el resuelto La configuración es $\sigma = \mathrm{id}$ . A lo largo, $\varepsilon$ es la firma de Teorema 1.21 y dos celdas son adyacente cuando comparten un borde de la bandeja.

Parte I — Configurations, moves, signatures.

Justificar que las configuraciones son exactamente los elementos de $\mathfrak{S}_{16}$ , por lo que hay $16! = 20\,922\,789\,888\,000$ de ellos, y que el número de Los movimientos legales desde una configuración determinada son $2$ , $3$ o $4$ , según si la celda vacía se encuentra en una esquina, en un borde, o en el interior.
Sea $\sigma$ una configuración, $p = \sigma^{-1}(16)$ la celda del espacio en blanco y $c$ una celda adyacente a $p$ . Mostrar que deslizar el mosaico de $c$ en $p$ produce el configure $\sigma' = \sigma \circ \tau$ con $\tau = (p\ c)$ , y deduzca que cada movimiento invierte la firma: $\varepsilon(\sigma') = -\varepsilon(\sigma)$ .
Tablero de ajedrez de la bandeja: $\chi(k) = (-1)^{i+j}$ para la celda $k$ en la fila $i$ , columna $j$ . Demuestra que cada movimiento cambia $\chi(\text{cell of the blank})$ , y deducir que un secuencia de movimientos que devuelven el espacio en blanco a su celda inicial tiene longitud uniforme.
Demuestra que

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

es invariante bajo cada movimiento legal, y calcula $I(\mathrm{id})$ .

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

La configuración de Loyd $\sigma_L$ concuerda con la resuelta excepto que las celdas $14$ y $15$ contienen los mosaicos $15$ y $14$ . Calcule $I(\sigma_L)$ y concluya que no hay secuencia de mueve los enlaces $\sigma_L$ a la configuración resuelta: El $1000 de Loyd nunca estuvo en peligro.
Demuestre que exactamente la mitad de todas las configuraciones satisfacen $I = +1$ : $\abs{\{\sigma : I(\sigma) = +1\}} = 16!/2$ . (For a fixed blank cell, pair configurations by composing with one fixed transposición of two other cells.)
Demuestre que cada movimiento se deshace mediante un movimiento legal, que “ $\sigma'$ es accesible desde $\sigma$ mediante movimientos legales” es una relación de equivalencia, y que la clase $R$ del La configuración resuelta satisface $R \subseteq \{I = +1\}$ . Concluya que hay al menos dos clases.
Supongamos que el espacio en blanco es el hogar: $\sigma(16) = 16$ . mostrar eso $I(\sigma) = \varepsilon(\rho)$ donde $\rho \in \mathfrak{S}_{15}$ es la restricción de $\sigma$ al celdas $1, \dots, 15$ , y que cualquier configuración puede ser llevado por movimientos legales a uno con la casa en blanco. Conclusión: para probar $R = \{I = +1\}$ basta con darse cuenta cada permutación incluso de los quince no hogareños celdas mediante una secuencia de movimientos que comienzan y terminan con el casa en blanco.

Parte III — Blank tours and the program group. A programa es una secuencia finita de movimientos legales, Se partió de una configuración con la vivienda en blanco, cuyo final La configuración nuevamente tiene el inicio en blanco. Su efecto es el permutación $\pi$ de las celdas definidas por: el contenido de la celda $x$ termina en la celda $\pi(x)$ .

Muestra que un programa ejecutado desde $\sigma$ termina en $\sigma \circ \pi^{-1}$ ; que ejecutar dos programas seguidos compone sus efectos; y que el conjunto $H$ de todos efectos es un subgrupo de $\mathfrak{S}_{15}$ (permutaciones de las celdas $1, \dots, 15$ ) contenidas en la alternancia grupo $A_{15}$ .
(El recorrido elemental) Desde el espacio en blanco en casa, deslice el espacio en blanco alrededor del bloque $2 \times 2$ inferior derecho: celdas $16 \to 12 \to 11 \to 15 \to 16$ . Mostrar el efecto es el $3$ -ciclo $(11\ 12\ 15)$ , y que el recorrido inverso da $(11\ 15\ 12)$ . Ambos se encuentran en $H$ .
(El gran recorrido) Verifica 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$

es un paseo cerrado a través de las dieciséis celdas (pasos adyacentes solamente), y que su efecto es el ciclo $15$

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

Escribiendo $x_0 = 15$ , $x_1 = 12$ , $x_2 = 11$ , …, $x_{14} = 14$ por su ciclo orden, comprobar que al revés El recorrido elemental de la pregunta 10 es exactamente $(x_0\ x_1\ x_2)$ .
Demuestre la fórmula de conjugación en cualquier $\mathfrak{S}_n$ : para una permutación $g$ y un ciclo $3$ ,

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

y tenga en cuenta que $H$ , al ser un grupo, está cerrado bajo conjugación por sus propios elementos.
Deduzca que $H$ contiene los quince consecutivo $3$ -ciclos del gran recorrido:

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

Parte IV — Generating the alternating group.

(Lema A) Sean $s$ y $t$ ciclos $3$ cuyos soportes comparte exactamente dos puntos, digamos que admite $\{a, b, c\}$ y $\{b, c, d\}$ . Demuestre que, después de reemplazar $s$ o $t$ por es inverso si es necesario (lo que no cambia nada al subgrupo generado), el producto $st$ es un doble transposición; mostrar que $A_4$ no contiene ningún subgrupo de orden $6$ (un subgrupo del índice $2$ contiene cada cuadrado; contar los $3$ -ciclos entre cuadrados); y concluir que $\langle s, t\rangle$ es todo el grupo alterno de las cuatro letras $\{a, b, c, d\}$ .
(Lema B) Sea $X$ un conjunto de letras $k \geq 4$ , $w \notin X$ y $G$ sea un subgrupo de algunas $\mathfrak{S}_n$ que contiene todas las permutaciones pares de $X$ y un ciclo $3$ $(u\ v\ w)$ con $u, v \in X$ . mostrar eso para todos los $a, b \in X$ distintos hay un incluso permutación $g$ de $X$ con $g(u) = a$ , $g(v) = b$ y deducir $(a\ b\ w) \in G$ .
Deduzca que el grupo $G$ del Lema B contiene todos los pares permutación de $X \cup \{w\}$ (use Ejercicio 1.6: the $3$ -cycles generate). Luego, encadenando los Lemas A y B a lo largo del consecutivo $3$ -ciclos $s_0, s_1, \dots, s_{12}$ de la pregunta 13, demostrar que $\langle s_0, \dots, s_{12}\rangle = A_{15}$ .
Concluye que $H = A_{15}$ : cada reordenamiento par de los quince mosaicos se puede lograr mediante un programa y $H$ tiene elementos $15!/2 = 653\,837\,184\,000$ .
(Teorema de la historia de Johnson, 1879) Reúna las preguntas 6, 7, 8 y 17: las configuraciones alcanzables desde el resuelto una son las configuraciones exactamente y $16!/2 = 10\,461\,394\,944\,000$ con $I = +1$ ; y accesibilidad tiene exactamente clases dos, la clase de la configuración resuelta y la clase de Loyd $\sigma_L$ . (For the second point, relabel the tiles $14$ and $15$ : show $\sigma \mapsto (14\ 15) \circ \sigma$ maps move sequences to move sequences and exchanges $\{I = +1\}$ with $\{I = -1\}$ .)

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

(El criterio práctico) Lee los quince mosaicos en orden de lectura de sus celdas, omitiendo el espacio en blanco y dejando $N$ sea el número de inversiones de esta lista; sea $r$ la fila del espacio en blanco contada desde abajo. Mostrar que $I(\sigma) = (-1)^{N + r + 1}$ , por lo que $\sigma$ es solucionable si y sólo si $N + r$ es impar.
(Acciones grupales) Un acción de un grupo $G$ en un conjunto $X$ es un mapa $G \times X \to X$ , $(g, x) \mapsto g \cdot x$ , con $e \cdot x = x$ y $g \cdot (h \cdot x) = (gh) \cdot x$ ; el órbita de $x$ es $G \cdot x$ , y la acción es libre cuando $g \cdot x = x$ fuerza a $g = e$ . Muestra que $h \cdot \sigma = \sigma \circ h^{-1}$ define una acción gratuita de $H$ en el conjunto de inicio en blanco configuraciones, que sus órbitas son exactamente las clases de accesibilidad mutua por programas, y recuperarse de la recuento de órbitas que estas configuraciones se dividen en exactamente $15!\,/\,\abs H = 2$ clases.
(La obstrucción $3 \times 3$ ) Demuestre que $3 \times 3$ junta admite paseo cerrado no visitando cada celda exactamente una vez: la estrategia de gran gira de la Parte III falla para el rompecabezas de ocho. (Tablero de ajedrez los nueve células.)
(La reparación) En la placa $3 \times 3$ con celdas $1$ a $9$ en orden de lectura y inicio $9$ : calcula los efectos de el recorrido perimetral $9 \to 8 \to 7 \to 4 \to 1 \to 2 \to 3 \to 6 \to 9$ (un ciclo $7$ $\zeta'$ que fija el centro $5$ ) y del recorrido de la esquina $9 \to 6 \to 5 \to 8 \to 9$ (a $3$ -ciclo por el centro). Conjugando este último por los poderes de $\zeta'$ y encadenando los Lemas A y B, prueban que el grupo de programas del ocho rompecabezas es todo $A_8$ , por lo tanto, exactamente $9!/2 = 181\,440$ de las configuraciones $9! = 362\,880$ se pueden resolver.
(Un tablero pobre) Ahora deje que el tablero sea un único ciclo de celdas $n \geq 4$ que llevan mosaicos $n - 1$ . Demuestre que el cíclico El orden de los mosaicos es invariante, por lo que cada accesibilidad clase tiene exactamente configuraciones $n(n - 1)$ (the classes are the orbits of a grupo cíclico of orden $\operatorname{lcm}(n, n-1) = n(n-1)$ ), y que hay son clases $(n - 2)!$ — para $n \geq 5$ mucho más que $2$ : en un tablero delgado el invariante de paridad captura casi nada, y la geometría manda.
Dos veredictos por el criterio de la pregunta 19: la plena bandeja invertida (mosaicos $15, 14, \dots, 1$ en celdas $1$ a $15$ , inicio en blanco) y la bandeja con el espacio en blanco en la celda $1$ seguido de los mosaicos $15, 14, \dots, 1$ en las celdas $2$ a $16$ . ¿Cuál tiene solución?
(Síntesis) La prueba tiene dos pilares independientes: un invariante ( $I$ , construido a partir del morfismo característico) mostrando como máximo la mitad de las configuraciones son accesibles, y un teorema generación explícita ( $H = A_{15}$ ) mostrando que al menos la mitad lo son. En una oración cada uno, diga dónde se ingresó lo siguiente: la propiedad del morfismo de $\varepsilon$ ; teorema de Lagrange; la generación de $A_n$ por $3$ -ciclos; conjugación. Enuncie el metaprincipio en una línea.

Solución

Solución de Problema 1.1.

1. Una configuración asigna a cada una de las celdas $16$ una del contenido $16$ (mosaicos $1$ – $15$ o el $b = 16$ en blanco), cada uno exactamente una vez: precisamente una biyección $\intint1{16} \to \intint1{16}$ , un elemento de $\mathfrak{S}_{16}$ ; hay $16! = 20\,922\,789\,888\,000$ de ellos. Un movimiento legal desliza una ficha adyacente al espacio en blanco, por lo que el número de movimientos es el número de vecinos de la celda del espacio en blanco: $2$ para las cuatro celdas de las esquinas, $3$ para las ocho celdas de borde, $4$ para las cuatro celdas interiores.

2. Después de la diapositiva, la celda $p$ contiene el contenido anterior de $c$ y la celda $c$ contienen el espacio en blanco; todas las demás células están intactas: $\sigma'(p) = \sigma(c)$ , $\sigma'(c) = \sigma(p) = 16$ , $\sigma' = \sigma$ en otro lugar. Eso es exactamente $\sigma' = \sigma \circ (p\ c)$ . Dado que $\varepsilon$ es un morfismo y $\varepsilon\bigl((p\ c)\bigr) = -1$ : $\varepsilon(\sigma') = -\varepsilon(\sigma)$ .

3. Las celdas adyacentes difieren en un paso exactamente en uno de las dos coordenadas, por lo que $i + j$ cambia la paridad: $\chi$ toma valores opuestos en celdas adyacentes. Un movimiento transfiere el espacio en blanco. de $p$ al $c$ adyacente, volteando $\chi(\text{blank cell})$ . A lo largo de un recorrido cerrado del espacio en blanco, $\chi$ se voltea una vez por movimiento. y vuelve a su valor inicial: el número de movimientos es par.

4. En las preguntas 2 y 3, un movimiento invierte ambos factores de $I(\sigma) = \varepsilon(\sigma)\chi(\sigma^{-1}(16))$ ; su El producto no ha cambiado. Para la configuración resuelta: $\varepsilon(\mathrm{id}) = +1$ y el espacio en blanco está en la celda $16$ , fila $4$ , columna $4$ : $\chi(16) = (-1)^{8} = +1$ , entonces $I(\mathrm{id}) = +1$ .

5. $\sigma_L$ es el transposición $(14\ 15)$ de las celdas: $\varepsilon(\sigma_L) = -1$ ; su espacio en blanco es casa, $\chi(16) = +1$ : $I(\sigma_L) = -1 \neq +1 = I(\mathrm{id})$ . Dado que $I$ es preservado por cada movimiento, ninguna secuencia de movimientos se une a $\sigma_L$ y $\mathrm{id}$ . El premio era estructuralmente seguro.

6. Reparar una celda $p$ y otras dos celdas $c \neq d$ distinto de $p$ y establezca $\tau_0 = (c\ d)$ . en el set de configuraciones con espacio en blanco en $p$ , el mapa $\sigma \mapsto \sigma \circ \tau_0$ es una involución (conserva $\sigma(p) = 16$ ya que $\tau_0$ corrige $p$ ) y voltea $\varepsilon$ , por lo tanto voltea $I$ : empareja las configuraciones con $I = +1$ biyectivamente con aquellos con $I = -1$ . Entonces cada una de las posiciones en blanco $16$ aporta configuraciones $15!/2$ con $I = +1$ , y

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

7. Se deshace el movimiento que desliza el mosaico de $c$ hacia $p$ . deslizando ese mismo mosaico (ahora en $p$ ) nuevamente en $c$ : componiendo con $(p\ c)$ dos veces es la identidad. Por lo tanto: reflexividad (vacío secuencia), simetría (invertir la secuencia, deshaciendo cada movimiento), transitividad (concatenar): una relación de equivalencia. cada $\sigma \in R$ tiene $I(\sigma) = I(\mathrm{id}) = +1$ por pregunta 4, entonces $R \subseteq \{I = +1\}$ ; y $\sigma_L \notin R$ da un segunda clase.

8. Si $\sigma(16) = 16$ , entonces $\sigma$ permuta el celdas $1, \dots, 15$ ; Llame a $\rho$ esta restricción. Agregando un punto fijo no cambia ni el tipo ciclo ni la firma (descomponer $\rho$ en transposiciones; el mismo producto funciona en $\mathfrak{S}_{16}$ ), por lo que $\varepsilon(\sigma) = \varepsilon(\rho)$ y $\chi(16) = +1$ dan $I(\sigma) = \varepsilon(\rho)$ . Cualquier configuración se puede llevar a un uno de casa en blanco: la red está conectada, así que recorra el espacio en blanco a lo largo de un ruta de las celdas adyacentes a la celda $16$ (cada paso es un movimiento legal). Ahora supongamos que se realiza cada $\rho \in \mathfrak{S}_{15}$ par. por un programa. Dado $\sigma$ con $I(\sigma) = +1$ : recorre el inicio en blanco para llegar a $\widetilde\sigma$ (equivalente a $\sigma$ ), con $I(\widetilde\sigma) = +1$ , es decir su restricción $\rho$ es incluso; el programa que realiza $\rho$ lleva $\widetilde\sigma$ a $\widetilde\sigma \circ \rho^{-1} = \mathrm{id}$ (ver pregunta 9). Por transitividad $\sigma \in R$ , de donde $\{I = +1\} \subseteq R$ e igualdad.

9. Un solo movimiento: el contenido de $c$ termina en $p$ y el espacio en blanco en $c$ : el efecto es $\pi = (p\ c)$ , y de hecho $\sigma' = \sigma \circ (p\ c) = \sigma \circ \pi^{-1}$ . Inducción: si una secuencia tiene efecto $\pi_1$ y lleva $\sigma$ a $\sigma \circ \pi_1^{-1}$ , siguiéndolo con un movimiento del efecto $\pi_2 = (p'\ c')$ produce $(\sigma \circ \pi_1^{-1}) \circ \pi_2^{-1} = \sigma \circ (\pi_2\pi_1)^{-1}$ y el contenido pasar por $\pi_2 \circ \pi_1$ (primero $\pi_1$ , luego $\pi_2$ ). entonces Los efectos se componen y un programa ejecutado desde $\sigma$ termina en $\sigma \circ \pi^{-1}$ . Subgrupo: el programa vacío tiene efecto $\mathrm{id}$ ; la concatenación da productos; revertir un programa (pregunta 7) da inversas. El efecto de un programa repara la celda $16$ (el espacio en blanco comienza y termina en casa), entonces $H \leq \mathfrak{S}_{15}$ . Igualdad: un programa de movimientos $k$ tiene $k$ par (pregunta 3), y $\varepsilon(\sigma \circ \pi^{-1}) = (-1)^k\varepsilon(\sigma)$ fuerza a $\varepsilon(\pi) = +1$ : $H \subseteq A_{15}$ .

10. Realice un seguimiento de las cuatro diapositivas desde el espacio en blanco en $16$ : mover $16 \to 12$ envía el contenido de $12$ a $16$ ; mover $12 \to 11$ envía el contenido de $11$ a $12$ ; mover $11 \to 15$ envía el contenido de $15$ a $11$ ; move $15 \to 16$ envía el contenido estacionado en $16$ (originalmente en $12$ ) a $15$ . Neto: $11 \mapsto 12$ , $12 \mapsto 15$ , $15 \mapsto 11$ , inicio en blanco: el efecto es $(11\ 12\ 15)$ . El recorrido inverso lo deshace: efecto $(11\ 12\ 15)^{-1} = (11\ 15\ 12)$ . Ambos son efectos de los programas, por lo que en $H$ .

11. Adyacencia de celdas consecutivas: dentro de cada una listada par las celdas difieren en $1$ en la misma fila ( $16{-}15$ , $15{-}14$ , $14{-}13$ ; $1{-}2$ , $2{-}3$ , $3{-}4$ ; $8{-}7$ , $7{-}6$ ; $10{-}11$ , $11{-}12$ ) o por $4$ dentro de una columna ( $13{-}9$ , $9{-}5$ , $5{-}1$ ; $4{-}8$ ; $6{-}10$ ; $12{-}16$ ): un Paseo cerrado por todas las celdas $16$ , de longitud $16$ . Efecto: como en la pregunta 10, escribiendo las celdas visitadas $c_0 = 16, c_1 = 15, \dots, c_{15} = 12$ : el contenido de $c_i$ se mueve a $c_{i-1}$ para $i = 2, \dots, 15$ , y el contenido de $c_1$ , estacionado en $16$ después del primer movimiento, se lleva a $c_{15}$ en el último movimiento. Entonces, el efecto asigna $15 \mapsto 12$ y $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$ : exactamente el ciclo $15$ $\zeta$ . Es ciclo orden inicia los mapas $x_0 = 15$ , $x_1 = 12$ , $x_2 = 11$ y $(x_0\ x_1\ x_2) = (15\ 12\ 11)$ $15 \mapsto 12 \mapsto 11 \mapsto 15$ — que es precisamente $(11\ 15\ 12)$ , el recorrido elemental inverso.

12. Dejemos $\gamma = (a\ b\ c)$ y $x \in \intint1n$ . si $x = g(a)$ : $g\gamma g^{-1}(x) = g(\gamma(a)) = g(b)$ ; igualmente $g(b) \mapsto g(c)$ y $g(c) \mapsto g(a)$ . Si $x \notin \{g(a), g(b), g(c)\}$ , entonces $g^{-1}(x) \notin \{a,b,c\}$ es arreglado por $\gamma$ , por lo que $x$ está arreglado. Por lo tanto $g\gamma g^{-1} = (g(a)\ g(b)\ g(c))$ . Y para $g, h \in H$ , $ghg^{-1} \in H$ por los axiomas de subgrupos.

13. $\zeta \in H$ (pregunta 11) y $s_0 = (x_0\ x_1\ x_2) \in H$ (preguntas 10–11). Desde $\zeta(x_i) = x_{i+1}$ (índices mod $15$ ), la pregunta 12 da

\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. Hasta invertir, supongamos $s = (a\ b\ c)$ y $t = (b\ c\ d)$ (un ciclo $3$ en $\{a,b,c\}$ es $(a\ b\ c)$ o su inversa; igualmente en $\{b,c,d\}$ ; sustitución de un generador por su el inverso deja $\langle s, t\rangle$ sin cambios). Luego, aplicando $t$ primero,

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

un doble transposición. El subgrupo $G = \langle s, t\rangle$ consta de permutaciones pares de las cuatro letras, por lo que $G \leq A_4$ y $\abs G \mid 12$ ; contiene un elemento de orden $3$ y uno de orden $2$ , por lo que $6 \mid \abs G$ (Lagrange, Teorema 1.14, aplicado a los dos cíclico subgrupos). Si $A_4$ tuviera un subgrupo $K$ de orden $6$ , sería tener índice $2$ , y luego $g^2 \in K$ para cada $g \in A_4$ : para $g \in K$ esto está claro; para $g \notin K$ las únicas clases laterales son $K$ y $gK$ , por lo que la clase lateral $g^2K$ es $K$ o $gK$ , y $g^2K = gK$ forzaría a $g \in K$ . Entonces cada cuadrado se encuentra en $K$ . pero cada $3$ -ciclo $\gamma$ es un cuadrado, $\gamma = (\gamma^2)^2$ , y $A_4$ contiene ocho ciclos $3$ : $8 > 6$ , contradicción. Por lo tanto $\abs G = 12$ : $G = A_4$ .

15. Extender $u \mapsto a$ , $v \mapsto b$ a una biyección $g_0$ de $X$ (enviar las letras $k - 2$ restantes biyectivamente en cualquier parte del complemento de $\{a, b\}$ ). Si $g_0$ es impar, elige dos letras distintas $s_1, t_1 \in X \setminus \{u, v\}$ (posible: $k \geq 4$ ) y reemplace $g_0$ por $g_0 \circ (s_1\ t_1)$ , que es par y aún asigna $u \mapsto a$ , $v \mapsto b$ . Extender por la identidad de $X$ : una permutación par $g \in G$ (es una permutación par de $X$ ). Luego la pregunta 12:

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

utilizando $g(w) = w$ .

16. Cada ciclo $3$ de $X \cup \{w\}$ se encuentra en $G$ : los admitidos en $X$ son incluso permutaciones de $X$ ; uno con el soporte $\{a, b, w\}$ es $(a\ b\ w)$ o $(b\ a\ w)$ , ambos entregado por la pregunta 15. Por Ejercicio 1.6, el $3$ ciclos del conjunto de elementos $(k+1)$ $X \cup \{w\}$ generan su grupo alterno, por lo que $G$ contiene cada permutación par de $X \cup \{w\}$ . Encadenamiento: deja que $G = \langle s_0, \dots, s_{12}\rangle$ . Lema A aplicado a $s_0 = (x_0\ x_1\ x_2)$ y $s_1 = (x_1\ x_2\ x_3)$ (admite compartir $\{x_1, x_2\}$ ) proporciona todas las permutaciones pares de $X_4 = \{x_0, x_1, x_2, x_3\}$ . Si $G$ contiene todas las permutaciones pares de $X_m = \{x_0, \dots, x_{m-1}\}$ ( $4 \leq m \leq 14$ ), luego $s_{m-2} = (x_{m-2}\ x_{m-1}\ x_m)$ tiene $u = x_{m-2}, v = x_{m-1} \in X_m$ y new letra $w = x_m$ : Lema B y la primera parte dan todo par permutaciones de $X_{m+1}$ . Inducción hasta $m = 14$ : $G \supseteq A_{15}$ (permutaciones pares de las quince celdas) y $G \subseteq A_{15}$ ya que cada $s_t$ es par: $\langle s_0, \dots, s_{12}\rangle = A_{15}$ .

17. Preguntas 13 y 16: $A_{15} = \langle s_0, \dots, s_{12}\rangle \subseteq H$ ; pregunta 9: $H \subseteq A_{15}$ . entonces $H = A_{15}$ , de orden $15!/2 = 653\,837\,184\,000$ : cada par La reorganización de los quince mosaicos es el efecto de un programa.

18. Pregunta 8 reducida $R = \{I = +1\}$ a darme cuenta cada par $\rho \in \mathfrak{S}_{15}$ por un programa: hecho por pregunta 17. Con la pregunta 6, $\abs R = 16!/2 = 10\,461\,394\,944\,000$ . Dos clases: deja que $t_0 = (14\ 15)$ actúe sobre contenido: $\varphi(\sigma) = t_0 \circ \sigma$ . Un movimiento legal desde $\sigma$ es un movimiento legal desde $\varphi(\sigma)$ (la celda en blanco no cambia: $(t_0\sigma)^{-1}(16) = \sigma^{-1}(t_0(16)) = \sigma^{-1}(16)$ , y la celda movida es la misma), y $\varphi(\sigma \circ \tau) = \varphi(\sigma) \circ \tau$ : $\varphi$ asigna secuencias de movimiento a mover secuencias, biyectivamente (es una involución). Se voltea $I$ : $\varepsilon(t_0\sigma) = -\varepsilon(\sigma)$ , mismo espacio en blanco celular. Por lo tanto, $\varphi$ asigna la clase $R = \{I = +1\}$ de $\mathrm{id}$ biyectivamente en la clase de $\varphi(\mathrm{id}) = \sigma_L$ , que por lo tanto es toda $\{I = -1\}$ : exactamente dos clases. Este es el teorema de Johnson-Story.

19. Indexe las celdas en orden de lectura y deje que $k = 4(i - 1) + j$ sea la celda en blanco. Cuente las inversiones de $\sigma$ (pares de celdas $x < y$ con $\sigma(x) > \sigma(y)$ ): pares de dos celdas de mosaico contribuyen $N$ ; pares que involucran el espacio en blanco: celdas después del espacio en blanco, todos contienen mosaicos $< 16$ , cada uno invertido ( $16 - k$ pares), las celdas anteriores nunca se invierten. entonces $\varepsilon(\sigma) = (-1)^{N + 16 - k} = (-1)^{N + k}$ . desde $k = 4(i-1) + j \equiv j \pmod 2$ ,

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

utilizando $i = 5 - r$ . Por la pregunta 18, $\sigma$ tiene solución si y así $I(\sigma) = +1$ si $N + r$ es impar. Verificar: resuelto, $N = 0$ , $r = 1$ : impar, solucionable; Loyd, $N = 1$ , $r = 1$ : uniforme, irresoluble.

20. Acción: $e \cdot \sigma = \sigma \circ \mathrm{id} = \sigma$ y $g \cdot (h \cdot \sigma) = \sigma \circ h^{-1} \circ g^{-1} = \sigma \circ (gh)^{-1} = (gh) \cdot \sigma$ ; y $\sigma \circ h^{-1}$ vuelve a ser una casa en blanco. configuración ( $h$ corrige la celda $16$ ). Gratis: $\sigma \circ h^{-1} = \sigma$ da $h^{-1} = \mathrm{id}$ (componer con $\sigma^{-1}$ ). Órbitas = clases de programa: pregunta 9 dice que las configuraciones accesibles desde $\sigma$ por los programas son exactamente el $\sigma \circ \pi^{-1}$ , $\pi \in H$ : la órbita $H \cdot \sigma$ . La libertad Contar: hace que $h \mapsto h \cdot \sigma$ sea inyectiva, por lo que cada órbita tiene elementos $\abs H = 15!/2$ ; Por lo tanto, las configuraciones de inicio en blanco $15!$ se dividen en $15!\,/\,(15!/2) = 2$ orbita — la sombra de la casa en blanco del dos clases de cuentos de Johnson.

21. La grilla $3 \times 3$ es bipartita para el Coloración del tablero de ajedrez: cada paso de una caminata cambia de color, por lo que cada caminata cerrado tiene una longitud uniforme. Un paseo cerrado visitando cada una de las celdas $9$ exactamente una vez tendría una longitud $9$ , impar: imposible. Por lo tanto, la construcción del gran recorrido de la Parte III es no disponible en el rompecabezas ocho.

22. Recorrido perimetral $9 \to 8 \to 7 \to 4 \to 1 \to 2 \to 3 \to 6 \to 9$ (todos los pasos adyacentes; longitud $8$ , par): por la contabilidad de la pregunta 11 con $c_1 = 8, c_2 = 7, c_3 = 4, c_4 = 1, c_5 = 2, c_6 = 3, c_7 = 6$ , el efecto es

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

un ciclo $7$ que fija el centro $5$ (el contenido de $7$ se mueve a $8$ , de $4$ a $7$ , de $1$ a $4$ , de $2$ a $1$ , de $3$ a $2$ , de $6$ a $3$ , y de $8$ a $6$ ). recorrido por la esquina $9 \to 6 \to 5 \to 8 \to 9$ : efecto $(6\ 8\ 5)$ (el contenido de $5$ se mueve a $6$ , de $8$ a $5$ , de $6$ — estacionado en $9$ — a $8$ ). conjunto $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$ . Conjugación (pregunta 12):

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

ya que $\zeta'$ corrige $5$ . Los soportes de $T_0 = (y_1\ y_0\ 5)$ y $T_1 = (y_2\ y_1\ 5)$ comparten exactamente $\{y_1, 5\}$ : Lema A da todas las permutaciones pares de $\{y_0, y_1, y_2, 5\}$ . entonces $T_2 = (y_3\ y_2\ 5)$ linda con $y_3$ por el Lema B (sus letras $y_2, 5$ se encuentran en el conjunto actual, $k = 4$ ) y $T_3, T_4, T_5$ contigua a $y_4, y_5, y_6$ a su vez: todas las permutaciones pares del ocho células no domiciliarias se encuentran en el grupo del programa, que también consta de permutaciones pares (el argumento de la pregunta 9 es independiente del consejo). Entonces $H_{3\times3} = A_8$ , y el razonamiento. de las preguntas 6, 8, 18 — también independientes del consejo — muestra la Las configuraciones accesibles son exactamente aquellas con $I = +1$ : la mitad de $9!$ , es decir $181\,440$ .

23. Etiquete las celdas $0, \dots, n-1$ alrededor de ciclo. Un movimiento intercambia el espacio en blanco con uno de sus dos vecinos. Lea el mosaicos en orden cíclico comenzando justo después del espacio en blanco: una palabra $w$ enumerando los mosaicos $n - 1$ . Moviendo el espacio en blanco un paso adelante reemplaza $(p, w)$ por $(p + 1, \rho w)$ , donde $p$ es el espacio en blanco celda y $\rho$ rota cíclicamente la palabra en uno; el atrasado el movimiento es el inverso. El orden cíclico de los mosaicos (el palabra hasta la rotación) es, por tanto, invariante. La clase alcanzable de $(p, w)$ es la órbita del mapa $g \colon (p, w) \mapsto (p+1, \rho w)$ , un elemento de orden $\operatorname{lcm}(n, n-1) = n(n-1)$ en el producto de los dos grupos cíclicos (traducciones de $\Z/n\Z$ y rotaciones de las posiciones de palabras $n-1$ ), el mcm siendo $n(n-1)$ porque $\gcd(n, n-1) = 1$ : cada clase tiene exactamente configuraciones $n(n-1)$ , todas con el mismo collar. Clases: $n!\,/\,\bigl(n(n-1)\bigr) = (n-2)!$ . Para $n \geq 5$ , $(n-2)! > 2$ : la invariante de paridad (dos clases en el mejor de los casos) es ciego a casi toda la obstrucción; la riqueza del tablero $4 \times 4$ — donde la paridad es la obstrucción solo — es un hecho genuinamente geométrico, no formal.

24. Ambas bandejas tienen los mosaicos en orden completamente invertido, entonces $N = \binom{15}{2} = 105$ en ambos casos (cada par de mosaicos está invertida). Casa en blanco: $r = 1$ , $N + r = 106$ incluso: irresoluble. En blanco en la celda $1$ : el espacio en blanco está en la parte superior fila, $r = 4$ , $N + r = 109$ impar: solucionable. Dos bandejas que se diferencian sólo por donde se asienta el agujero caen en lados opuestos de la pared.

25. Propiedad del morfismo: convierte “un movimiento = un transposición” en “un movimiento = un cambio de signo” (preguntas 2, 4), haciendo que $I$ sea computable movimiento por movimiento. Lagrange: eso forzado $6 \mid \abs{\langle s, t\rangle}$ en el Lema A y dimensionado las clases laterales en el orden- $6$ exclusión (pregunta 14). Generación por $3$ -ciclos: convirtió “ $H$ contiene suficientes ciclos $3$ ” en “ $H$ contiene todo $A_{15}$ ” (pregunta 16). Conjugación: fabricó los quince ciclos $3$ consecutivos de un único recorrido $2 \times 2$ transportado por el gran recorrido (preguntas 12–13), y el $3$ ciclos $(a\ b\ w)$ en el Lema B. Metaprincipio: y invariante prueba imposibilidad, una construcción explícita prueba posibilidad, y un problema se resuelve completamente exactamente cuando los dos Los límites se encuentran — aquí, en la mitad.