Capítulo 11 — Familias, productos, cocientes y tamaño
En el capítulo 4 aprendimos a expresar afirmaciones mediante conjuntos, relaciones y funciones. Ahora necesitamos organizar conjuntos que varían con un parámetro, reunir condiciones, conservar varias coordenadas o identificar objetos según una relación. También necesitamos decir con precisión cuándo dos conjuntos tienen igual tamaño, aun cuando no podamos terminar de contar sus elementos.
Estas operaciones aparecen en álgebra, cálculo y matemática discreta. Aquí construiremos su lenguaje común. Las pruebas usan pertenencia, funciones y las obligaciones ya estudiadas; no requieren teoría axiomática avanzada de conjuntos ni categorías.
La pregunta que guiará el capítulo es: ¿qué datos conserva una construcción y qué hay que comprobar para utilizarla? Una familia conserva etiquetas; una intersección conserva condiciones simultáneas; un producto conserva coordenadas; un cociente conserva clases; una biyección conserva la correspondencia exacta entre elementos. Confundir estas funciones puede hacer falsa una afirmación aparentemente familiar.
Mantendremos \(\mathbb N=\{0,1,2,\ldots\}\). Cuando trabajemos con complementos o con una intersección de índice vacío, declararemos un conjunto ambiente. No usaremos «el conjunto de todos los conjuntos».
11.1. Familias indexadas: etiquetas y valores
Una familia indexada de conjuntos \((A_i)_{i\in I}\) asigna a cada elemento \(i\) de un conjunto \(I\) un conjunto \(A_i\). El conjunto \(I\) es el conjunto de índices; \(i\) es una etiqueta y \(A_i\) es el valor correspondiente. Se puede expresar formalmente como una función cuyo dominio es \(I\) y cuyos valores son los conjuntos considerados. Para una familia ya dada, basta como codominio su conjunto de valores: no necesitamos reunir todos los conjuntos posibles.
Por ejemplo, con \(I=\{\mathrm{norte},\mathrm{sur},\mathrm{centro}\}\), fijemos
\[ A_{\mathrm{norte}}=\{1,4\},\qquad A_{\mathrm{sur}}=\{4\},\qquad A_{\mathrm{centro}}=\{1,4\}. \]
Los tres índices son distintos, aunque dos valores coinciden. La familia no es el conjunto \(\{\{1,4\},\{4\}\}\): ese conjunto no indica qué valor corresponde a cada etiqueta. La diferencia importará especialmente al formar productos, donde cada etiqueta determina una coordenada.
Una sucesión \((A_n)_{n\in\mathbb N}\) es una familia con índices naturales. No toda familia es una sucesión: un conjunto de índices puede ser finito, estar formado por pares o ser un intervalo real. Por ejemplo, \((\{x\in\mathbb R:x<t\})_{t\in\mathbb R}\) tiene un conjunto de índices distinto de \(\mathbb N\).
Reindexar exige una función
Sea \(r:J\to I\). La familia \((A_{r(j)})_{j\in J}\) está reindexada por \(r\). Si \(r\) no es sobreyectiva, algunos índices originales pueden no aparecer. Si \(r\) no es inyectiva, un mismo índice puede aparecer varias veces. Una biyección cambia las etiquetas sin perder ni repetir posiciones.
En el ejemplo anterior, si \(J=\{0,1\}\) y \(r(0)=\mathrm{norte}\), \(r(1)=\mathrm{centro}\), la familia reindexada tiene ambos valores iguales a \(\{1,4\}\) y no incluye la posición sur. No podemos afirmar que recupera toda la familia original.
Una igualdad de familias con el mismo conjunto de índices significa \(A_i=B_i\) para cada \(i\in I\). Igualdad de sus conjuntos de valores es una afirmación más débil: no identifica qué conjunto aparece en cada posición. Si los dominios índice son distintos, antes de comparar hay que declarar cómo se relacionan sus etiquetas.
Comprobación. Sean \(U_0=\{a\}\), \(U_1=\{b\}\), \(V_0=\{b\}\) y \(V_1=\{a\}\), con \(a\ne b\). ¿Son iguales las familias?
Respuesta. No: sus valores en el índice \(0\) difieren. Sus conjuntos de valores sí coinciden. La biyección que intercambia \(0\) y \(1\) permite obtener una familia a partir de la otra por reindexación; no establece igualdad con las etiquetas originales.
11.2. Uniones e intersecciones: alguna condición o todas
Sea \((A_i)_{i\in I}\) una familia de subconjuntos de un conjunto \(X\). La unión reúne los elementos que pertenecen a alguno de los conjuntos:
\[ \bigcup_{i\in I}A_i =\{x\in X:\exists i\in I\;(x\in A_i)\}. \]
La intersección, relativa al ambiente declarado \(X\), reúne los que pertenecen a todos:
\[ \bigcap_{i\in I}^{X}A_i =\{x\in X:\forall i\in I\;(x\in A_i)\}. \]
Usaremos el superíndice \(X\) cuando haga falta recordar el ambiente, especialmente con índice vacío. Con índice no vacío podemos omitirlo: elegir \(i_0\in I\) obliga a que cualquier elemento de la intersección pertenezca a \(A_{i_0}\), y ampliar el ambiente no añade elementos.
En la familia norte/sur/centro de §11.1 la unión es \(\{1,4\}\) y la intersección es \(\{4\}\). Repetir el valor \(\{1,4\}\) no cambia ninguna de las dos operaciones. Para demostrarlo no contamos índices: comprobamos qué condiciones satisface cada elemento.
El índice vacío no significa lo mismo en ambas operaciones
Si \(I=\varnothing\), no existe un índice que pueda servir de testigo. Por tanto,
\[ \bigcup_{i\in\varnothing}A_i=\varnothing. \]
En cambio, no hay ninguna condición indexada que incumplir. Todo \(x\in X\) satisface la condición universal vacía; así,
\[ \bigcap_{i\in\varnothing}^{X}A_i=X. \]
Esto no define un conjunto de todos los conjuntos ni de todos los objetos posibles. Si no se ha declarado \(X\), escribir una intersección vacía deja pendiente una convención necesaria. El capítulo 3 explica la semántica de los cuantificadores vacíos; aquí aplicamos esa semántica a una construcción de conjuntos.
Inclusiones y testigos
Para cada \(k\in I\) se cumple
\[ \bigcap_{i\in I}^{X}A_i\subseteq A_k \subseteq\bigcup_{i\in I}A_i. \]
Si \(x\) está en la intersección, la condición universal se puede aplicar al índice \(k\). Si \(x\in A_k\), ese mismo \(k\) es testigo para la unión. Ambas justificaciones requieren disponer de \(k\in I\); no podemos extraer uno de un conjunto índice vacío.
Comprobación. En ambiente \(X=\{a,b\}\), ¿puede ocurrir que la intersección vacía tenga más elementos que la unión vacía?
Respuesta. Sí. La intersección vacía es \(X\) y la unión vacía es \(\varnothing\). No contradice las inclusiones anteriores: éstas están formuladas para cada \(k\in I\), y aquí no existe tal índice.
11.3. Operaciones finitas e infinitas: controlar las condiciones
Las reglas de las operaciones indexadas se comprueban traduciendo pertenencia. La diferencia entre finito e infinito puede cambiar el resultado, aunque no cambie la forma de esa traducción.
Si \(A_i\subseteq B_i\subseteq X\) para cada \(i\in I\), entonces
\[ \bigcup_{i\in I}A_i\subseteq\bigcup_{i\in I}B_i, \qquad \bigcap_{i\in I}^{X}A_i\subseteq\bigcap_{i\in I}^{X}B_i. \]
En la primera inclusión, un testigo \(k\) con \(x\in A_k\) también da \(x\in B_k\). En la segunda, para cada índice la pertenencia a \(A_i\) implica pertenencia a \(B_i\). El ambiente común importa con índice vacío: las dos intersecciones son entonces el mismo \(X\).
De Morgan conserva el ambiente
Bajo lógica clásica, para cualquier conjunto índice, incluido el vacío,
\[ X\setminus\bigcup_{i\in I}A_i =\bigcap_{i\in I}^{X}(X\setminus A_i), \]
\[ X\setminus\bigcap_{i\in I}^{X}A_i =\bigcup_{i\in I}(X\setminus A_i). \]
Para la primera igualdad, un elemento de \(X\) no está en la unión exactamente cuando no pertenece a ningún \(A_i\); eso equivale a pertenecer a cada complemento relativo. Para la segunda, no satisfacer todas las pertenencias equivale a que alguna falle. En ambos argumentos fijamos primero \(x\in X\). Si \(I\) es vacío, las igualdades se reducen respectivamente a \(X\setminus\varnothing=X\) y \(X\setminus X=\varnothing\).
También, si \(B\subseteq X\),
\[ B\cap\bigcup_{i\in I}A_i =\bigcup_{i\in I}(B\cap A_i). \]
En efecto, estar a la izquierda significa estar en \(B\) y en algún \(A_i\). Ese mismo índice testimonia la pertenencia al lado derecho; en sentido inverso, el testigo proporciona ambas pertenencias. No hace falta que \(I\) sea finito.
Un límite de la intuición finita
Consideremos en \(\mathbb N\) los conjuntos \(T_n=\{m\in\mathbb N:m\ge n\}\). Cada \(T_n\) es no vacío, y cualquier cantidad finita no vacía de ellos tiene intersección no vacía: si \(M\) es el mayor de sus índices, la intersección es \(T_M\).
Pero la intersección de todos los \(T_n\) es vacía. Si un natural \(m\) perteneciera a ella, tendría que pertenecer a \(T_{m+1}\); eso exigiría \(m\ge m+1\), lo cual es falso. El índice que detecta el fallo depende del candidato \(m\). No se está buscando un índice único que excluya a todos los candidatos a la vez.
Por tanto, «todas las intersecciones finitas son no vacías» no autoriza aquí «la intersección total es no vacía». Otros cursos estudiarán hipótesis que sí permiten conclusiones de esa forma; no las suponemos en este libro.
Reindexación sobreyectiva
Si \(r:J\to I\) es sobreyectiva, la unión y la intersección de \((A_{r(j)})_{j\in J}\) coinciden con las de \((A_i)_{i\in I}\), con el mismo ambiente. Todo índice original tiene una preimagen, y cada índice nuevo apunta a uno original. En una unión esto permite transportar testigos; en una intersección permite recuperar cada condición. La repetición de índices no añade condiciones distintas.
Comprobación. ¿Basta que \(r\) sea inyectiva para conservar una unión?
Respuesta. No. Tomemos \(I=\{0,1\}\), \(J=\{0\}\), \(r(0)=0\), \(A_0=\{a\}\) y \(A_1=\{b\}\), con \(a\ne b\). La unión original es \(\{a,b\}\) y la reindexada es \(\{a\}\). La inyectividad impide repeticiones, pero no garantiza cubrir todos los índices.
11.4. Productos finitos: conservar las coordenadas
El producto \(A\times B\) del capítulo 4 reúne pares ordenados \((a,b)\) con \(a\in A\) y \(b\in B\). Para \(n\ge1\), el producto de \(A_1,\ldots,A_n\) reúne tuplas \((a_1,\ldots,a_n)\) con \(a_i\in A_i\) en cada posición. Dos tuplas son iguales exactamente cuando coinciden todas sus coordenadas.
También podemos describir una tupla como una función \(f:\{1,\ldots,n\}\to\bigcup_{i=1}^n A_i\) tal que \(f(i)\in A_i\). La correspondencia envía \((a_1,\ldots,a_n)\) a la función \(f(i)=a_i\); su inversa lee los valores \(f(1),\ldots,f(n)\). No confunde un objeto \(a_i\) con la posición \(i\).
Para un conjunto índice finito de etiquetas cualesquiera usamos directamente esta descripción funcional. Si \(I=\{\mathrm{entrada},\mathrm{salida}\}\), un elemento de \(\prod_{i\in I}A_i\) especifica un valor admisible de entrada y uno de salida. Aunque ambos factores sean el mismo conjunto, las posiciones siguen siendo distintas.
Vacío en el índice y vacío en un factor
El producto de una familia vacía contiene exactamente una función, la función vacía \(e_{\varnothing}:\varnothing\to\varnothing\). Su grafo no tiene pares y no hay restricciones de coordenadas que verificar. Es un conjunto con un elemento:
\[ \prod_{i\in\varnothing}A_i=\{e_{\varnothing}\}. \]
Si identificáramos una función con su grafo, podríamos escribir también \(\{\varnothing\}\). Sin embargo, en este libro (§4.5 y §4.7) declaramos dominio y codominio como parte de los datos de cada función. Bajo esa convención, el elemento \(e_{\varnothing}\) no es literalmente el conjunto vacío: es la función de \(\varnothing\) en \(\varnothing\) cuyo grafo es vacío. El producto, en cualquier caso, tiene un elemento, no cero. Esta precisión será útil en §11.5, cuando comparemos productos vacíos y potencias \(A^{\varnothing}\) con codominios declarados distintos.
En cambio, si \(k\in I\) y \(A_k=\varnothing\), el producto es vacío. Un elemento del producto tendría que asignar a \(k\) un valor en \(A_k\), lo cual es imposible. La conclusión requiere un factor vacío con índice existente; no se aplica a la familia sin índices.
Si hay un número finito de posiciones y todos los factores son no vacíos, el producto es no vacío. Para justificarlo, empezamos con la tupla vacía. Al añadir un factor no vacío elegimos un elemento de ese factor y lo añadimos a una tupla ya construida. Inducción sobre el número de factores da una tupla completa. Cada etapa hace una elección dentro de una construcción finita; no estamos afirmando existencia para una familia arbitraria infinita.
Asociar y cambiar orden
La función \(((a,b),c)\mapsto(a,(b,c))\) es una biyección de \((A\times B)\times C\) a \(A\times(B\times C)\): su inversa devuelve \(((a,b),c)\). Esta correspondencia permite identificar ambas presentaciones cuando la convención esté declarada; no afirma igualdad literal de pares anidados.
Análogamente, \((a,b)\mapsto(b,a)\) da una biyección entre \(A\times B\) y \(B\times A\). Las coordenadas intercambian posición y dominio. No se puede conservar la misma fórmula de una función que utiliza la primera coordenada sin ajustar esa fórmula al intercambio.
Comprobación. Sean \(A=\{u,v\}\) y \(B=\{w\}\), con tres objetos distintos. ¿Son iguales \(A\times B\) y \(B\times A\)?
Respuesta. No: \((u,w)\) pertenece al primero y no al segundo. Tienen igual número de elementos y la función de intercambio es una biyección. Igualdad de conjuntos y existencia de una biyección son afirmaciones diferentes.
11.5. Productos indexados: un elemento es una selección completa
Sea \((A_i)_{i\in I}\) una familia de conjuntos y sea \(U=\bigcup_{i\in I}A_i\). Definimos su producto indexado mediante
\[ \prod_{i\in I}A_i =\{f:I\to U:\forall i\in I\;(f(i)\in A_i)\}. \]
La definición vale para índices finitos o infinitos. Un elemento del producto es una sola función que asigna simultáneamente un valor permitido a cada posición. Con índice vacío \(U=\varnothing\) y existe una única función de \(\varnothing\) en \(\varnothing\), como establecimos en §11.4.
Si todos los factores son un mismo conjunto \(A\), usamos \(A^I\) para el conjunto de funciones \(I\to A\); tiene la misma descripción de coordenadas. Con índice vacío, el producto usa la función vacía con codominio \(\varnothing\), mientras \(A^{\varnothing}\) usa codominio \(A\): sus únicos grafos coinciden, y la identificación es por grafo, no una igualdad de funciones con codominios declarados distintos. Para \(I=\mathbb N\), un elemento de \(A^{\mathbb N}\) es una sucesión de elementos de \(A\). Si \(I\) es vacío, la función vacía existe cualquiera que sea \(A\).
Construir una selección
Definamos \(A_n=\{n,n+2\}\) para \(n\in\mathbb N\). La fórmula \(f(n)=n+2\) define un elemento del producto. Hay que comprobar dos cosas: que proporciona una función en todo \(\mathbb N\) y que su valor pertenece al factor correcto para cada \(n\). La segunda es inmediata por la definición de \(A_n\); la primera se apoya en una regla única definida en cada natural.
No basta decir «cada factor tiene algún elemento». Esa afirmación tiene forma \(\forall i\in I\;\exists a\in A_i\). Un elemento del producto exige una función \(f\) que reúna todas las selecciones. Para familias arbitrarias, el principio que garantiza esa existencia es el axioma de elección. No lo desarrollaremos ni usaremos aquí como una hipótesis tácita. En los ejemplos donde necesitamos un elemento, lo construiremos por una fórmula o una regla ya justificada. Con factores finitos en número, §11.4 dio una construcción finita.
Qué permite recuperar una coordenada
Para cada \(k\in I\) existe una función de proyección
\[ \pi_k:\prod_{i\in I}A_i\to A_k, \qquad \pi_k(f)=f(k). \]
Es función porque cada \(f\) tiene un único valor en \(k\), y ese valor pertenece a \(A_k\). No afirmamos sin hipótesis que la proyección sea sobreyectiva. Si ya tenemos un elemento \(g\) del producto, podemos probarlo: para \(a\in A_k\), definimos \(f(k)=a\) y \(f(i)=g(i)\) en los demás índices. Esa modificación produce un elemento del producto cuya proyección es \(a\). Si el producto está vacío pero \(A_k\) no lo está, la proyección no es sobreyectiva.
La construcción distingue entre contar con una selección completa y limitarse a saber que cada factor tiene elementos. Esa diferencia no es un detalle de notación.
Comprobación. Para \(I=\mathbb N\) y \(A_n=\{n+1\}\), determine el producto.
Respuesta. Contiene exactamente la función \(f(n)=n+1\). La fórmula produce una selección admisible. Cualquier otra función del producto debe tener en cada posición el único valor del factor, por lo que coincide con \(f\). No se necesita un principio de elección para esta familia: la regla ya está dada.
11.6. Equivalencias y particiones: agrupar sin solapamientos
Una relación \(\sim\) sobre un conjunto \(X\) es una relación de equivalencia si es reflexiva, simétrica y transitiva: para \(x,y,z\in X\), se cumplen \(x\sim x\), \(x\sim y\Rightarrow y\sim x\) y \((x\sim y\ \text{y}\ y\sim z)\Rightarrow x\sim z\).
La clase de equivalencia de \(x\in X\) es
\[ [x]=\{y\in X:y\sim x\}. \]
La reflexividad garantiza \(x\in[x]\), de modo que ninguna clase de un elemento existente es vacía. Además,
\[ x\sim y\quad\Longleftrightarrow\quad[x]=[y]. \]
Para probar la dirección directa, supongamos \(x\sim y\). Si \(z\in[x]\), tenemos \(z\sim x\) y por transitividad \(z\sim y\), así que \(z\in[y]\). La simetría da \(y\sim x\) y el mismo argumento prueba la inclusión opuesta. Para la dirección inversa, si \([x]=[y]\), la pertenencia \(x\in[x]\) implica \(x\in[y]\), esto es, \(x\sim y\).
Dos clases que se encuentran son la misma
Si \(z\in[x]\cap[y]\), entonces \(z\sim x\) y \(z\sim y\). Por simetría \(x\sim z\) y por transitividad \(x\sim y\). La equivalencia anterior da \([x]=[y]\). Por tanto, dos clases distintas son disjuntas. Toda persona que manipule clases necesita esta propiedad: no basta que los conjuntos se parezcan o tengan un elemento en común sin haber probado equivalencia.
Una partición de \(X\) es un conjunto \(\mathcal P\) de subconjuntos no vacíos de \(X\), disjuntos dos a dos, cuya unión es \(X\). Cada elemento pertenece a exactamente un bloque. Las clases de una relación de equivalencia forman una partición: son no vacías, cubren \(X\) por reflexividad y son iguales o disjuntas por el argumento anterior. Al reunirlas como conjunto, las repeticiones \([x]=[y]\) aparecen una sola vez.
A la inversa, dada una partición, definimos \(x\sim y\) cuando ambos pertenecen al mismo bloque. Es reflexiva porque cada elemento está en un bloque; simétrica porque compartir bloque es simétrico; transitiva porque los dos bloques que contienen a \(y\) deben ser el mismo. Sus clases son exactamente los bloques de la partición.
Cuando \(X=\varnothing\), la partición vacía cumple las condiciones: su unión es vacía y no tiene bloques vacíos. La relación vacía es una equivalencia sobre \(X\), puesto que no existen elementos que violen ninguna de las tres condiciones. No aparece una clase vacía: no hay elementos de los que formar clases.
Ejemplo por una característica compartida
En \(\mathbb Z\times\mathbb Z\), declaremos \((a,b)\sim(c,d)\) si \(a+b=c+d\). Igualdad de las sumas prueba las tres propiedades. La clase de \((a,b)\) reúne todos los pares cuya suma es \(a+b\). Un par distinto puede pertenecer a la misma clase; por ejemplo, \((2,5)\) y \((4,3)\). El criterio identifica sumas, no coordenadas individuales. El capítulo siguiente en la ruta algebraica podrá añadir estructuras a cocientes; aquí sólo construimos sus conjuntos.
Comprobación. En la equivalencia por suma del ejemplo, un editor propone reemplazar las clases de \((2,5)\) y \((4,3)\) por su unión, como si estuviera reuniendo dos bloques distintos. ¿Qué debe corregir?
Respuesta. Ambos pares tienen suma \(7\), por lo que sus clases ya son el mismo bloque. La unión no reúne dos bloques distintos: devuelve ese único bloque. La partición recoge clases como conjuntos, sin duplicar un bloque por cada representante que lo nombra.
11.7. Cocientes: comprobar independencia del representante
El conjunto cociente de \(X\) por una equivalencia \(\sim\) es
\[ X/{\sim}=\{[x]:x\in X\}. \]
Sus elementos son clases, no los elementos originales de \(X\). La proyección \(q:X\to X/{\sim}\), definida por \(q(x)=[x]\), es sobreyectiva: cada clase del cociente tiene por definición al menos un representante. Para justificar esa sobreyectividad tomamos una clase particular y un representante de ella; no elegimos simultáneamente un representante de todas las clases.
Qué significa que una regla esté bien definida
Antes de preguntar si una fórmula define una función, debemos precisar qué son sus entradas y sus salidas. Hay al menos dos controles diferentes.
El primero es el control de dominio y unicidad del valor. Una regla propuesta como \(f:A\to B\) debe asignar a cada \(x\in A\) un valor que exista, pertenezca a \(B\) y sea único. Cuando la regla se presenta mediante operaciones, también debemos comprobar que éstas están definidas para las entradas permitidas. Esto no exige un algoritmo para calcular cada valor: la existencia y la unicidad son requisitos matemáticos, distintos de la computabilidad. Por ejemplo, la fórmula
\[ f(x)=\frac{1}{x-1} \]
define una función \(\mathbb R\setminus\{1\}\to\mathbb R\), pero no define una función \(\mathbb R\to\mathbb R\) mediante la misma regla, porque en \(x=1\) el denominador es cero. No se corrige ese defecto demostrando que la fórmula funciona en muchos valores: la definición de función exige una salida para cada entrada del dominio declarado.
El segundo control aparece cuando una entrada puede escribirse con representantes distintos, como ocurre en un conjunto cociente. Aun si la fórmula puede evaluarse para cada representante, habrá que demostrar que todos los representantes de una misma clase producen el mismo valor. De otro modo no se ha definido una función sobre las clases. La independencia del representante no es una condición adicional de inyectividad o sobreyectividad; es anterior a ambas, porque determina si la aplicación misma existe.
De este modo, «estar bien definida» no significa simplemente «tener una fórmula conocida»: significa que la regla determina inequívocamente un objeto del tipo anunciado para cada entrada legítima. En el caso de los cocientes, veremos enseguida cómo se traduce esta exigencia a una implicación precisa.
Una fórmula con clases puede ser ambigua
Si proponemos \(\overline F([x])=F(x)\), dos representantes \(x\) e \(y\) de una misma clase deben dar el mismo resultado. La condición precisa es
\[ x\sim y\quad\Longrightarrow\quad F(x)=F(y). \]
Supongamos que \(F:X\to Y\) satisface esa condición. Para cada clase \(C\), existe un valor \(F(x)\) con \(x\in C\), y ese valor es único: cualquier otro \(y\in C\) verifica \(y\sim x\), así que \(F(y)=F(x)\). Existencia y unicidad por clase definen una función \(\overline F:X/{\sim}\to Y\). Se dice que \(F\) desciende al cociente.
La identidad \(\overline F(q(x))=F(x)\) vale para cada \(x\), es decir, \(\overline F\circ q=F\). Además, la función descendida es única con esa propiedad. Si \(G\circ q=F\) y \(C=[x]\), entonces \(G(C)=G(q(x))=F(x)=\overline F(C)\). Cada clase tiene representante, de modo que las funciones coinciden en todo su dominio. La prueba usa representantes locales para verificar una propiedad, no una función global de elección de representantes.
Una fórmula que sí desciende y otra que no
Para la equivalencia por suma de §11.6, \(F(a,b)=a+b\) es constante en clases y desciende a una función del cociente en \(\mathbb Z\). En cambio, \(H(a,b)=a\) no desciende: \((2,5)\) y \((4,3)\) son equivalentes, pero dan valores \(2\) y \(4\). El escrito «\(\overline H([(a,b)])=a\)» no define una función del cociente. No es un problema de falta de inyectividad: falta un valor único para una misma entrada.
Si después queremos definir una operación entre clases, habrá que comprobar independencia de cada representante que interviene. No basta con que la fórmula se pueda calcular en representantes particulares. Esa obligación será decisiva en álgebra; aquí la reconocemos sin desarrollar cocientes de grupos o anillos.
Dos clases como entradas: la independencia se comprueba dos veces
Sea \(Q=(\mathbb Z\times\mathbb Z)/{\sim}\) el cociente por igualdad de sumas de §11.6. Queremos proponer una función \(\Theta:Q\times Q\to\mathbb Z\). Si escribimos dos de sus entradas como \(C=[(a,b)]\) y \(D=[(c,d)]\), una fórmula posible es
\[ \Theta(C,D)=(a+b)+(c+d). \]
¿Depende de cómo escribamos cada clase? Supongamos que elegimos otros representantes \((a',b')\) y \((c',d')\) de \(C\) y \(D\), respectivamente. Por la definición de equivalencia,
\[ a+b=a'+b',\qquad c+d=c'+d'. \]
Sumar esas dos igualdades da
\[ (a+b)+(c+d)=(a'+b')+(c'+d'). \]
Por tanto, cambiar el representante de cualquiera de las dos entradas, o de ambas a la vez, conserva el resultado. La regla determina una función \(Q\times Q\to\mathbb Z\) bien definida. Su salida es un entero, no una clase: no estamos introduciendo aquí una operación algebraica sobre \(Q\).
En cambio, la propuesta \(\Lambda(C,D)=a+c\) no está bien definida. Para la primera clase podemos escribir tanto \([(2,5)]\) como \([(4,3)]\), que son iguales porque ambas sumas valen \(7\). Fijando como segunda entrada \(D=[(0,0)]\), la fórmula daría respectivamente \(2\) y \(4\). Una misma pareja de clases recibiría dos valores distintos, aun cuando en cada cálculo individual no haya ninguna operación ilegítima.
Comprobación. ¿Define \(\Omega(C,D)=(a+b)-(c+d)\) una función de \(Q\times Q\) en \(\mathbb Z\)?
Respuesta razonada. Sí. Si cambiamos las representaciones de \(C\) y \(D\), las dos sumas permanecen iguales a sus valores iniciales, y por tanto también permanece igual su diferencia. Todas las operaciones son legítimas en \(\mathbb Z\) y para cada pareja de clases se determina un único entero. No necesitamos elegir de antemano un representante privilegiado de cada clase.
Comprobación. En el cociente por suma, ¿desciende \(K(a,b)=2(a+b)+1\)?
Respuesta. Sí. Si \((a,b)\sim(c,d)\), sus sumas son iguales y por ello \(2(a+b)+1=2(c+d)+1\). La función descendida tiene dominio el cociente y codominio \(\mathbb Z\); no es sobreyectiva en ese codominio porque sólo alcanza enteros impares. Buena definición y sobreyectividad son comprobaciones distintas.
11.8. Igual tamaño, finitud e infinitud
Decimos que \(A\) y \(B\) son equipotentes, o que tienen igual tamaño, si existe una biyección \(A\to B\). Escribiremos \(A\approx B\). La afirmación no exige que los elementos sean los mismos ni que los conjuntos sean iguales. En conjuntos finitos corresponde al resultado de contar; en conjuntos infinitos proporciona una definición que no necesita terminar una lista.
La equipotencia es reflexiva, simétrica y transitiva. La identidad prueba reflexividad; la inversa de una biyección prueba simetría; componer dos biyecciones prueba transitividad. Se aplican las propiedades de funciones de §4.7. No formaremos un cociente de «todos los conjuntos» por esta relación: sólo comparamos los conjuntos de los que estamos hablando.
Contar finitamente y demostrar que el número es único
Para \(n\in\mathbb N\) fijamos \(I_n=\{0,\ldots,n-1\}\), con \(I_0=\varnothing\). Un conjunto \(A\) es finito si hay alguna biyección \(I_n\to A\). En ese caso escribimos \(|A|=n\). Para que esa notación sea legítima tenemos que demostrar que el número no depende de cómo se haya contado.
La herramienta es el siguiente resultado, que merece una demostración completa porque la unicidad del tamaño finito dependerá de él.
Lema (no caben más entradas distintas que posiciones disponibles). Si existe una inyección \(u:I_m\to I_n\), entonces \(m\le n\).
Demostración. Procedemos por inducción sobre \(n\); en cada etapa la afirmación comprende todos los posibles tamaños \(m\) del dominio.
Base \(n=0\). El codominio es \(I_0=\varnothing\). Si existe una función \(I_m\to\varnothing\), su dominio necesariamente es vacío. Por tanto \(m=0\) y se cumple \(m\le0\).
Paso de \(n\) a \(n+1\). Supongamos que el lema vale para cualquier inyección con codominio \(I_n\). Sea \(u:I_m\to I_{n+1}\) una inyección. Si \(m=0\), ya tenemos \(m\le n+1\). Supongamos \(m\ge1\) y fijemos la última posición del dominio, \(m-1\). Su imagen es algún índice \(j=u(m-1)\in I_{n+1}\).
Podemos intercambiar las etiquetas \(j\) y \(n\) del codominio, dejando fijas las demás. Esa permutación \(\sigma:I_{n+1}\to I_{n+1}\) es una biyección (si \(j=n\), es la identidad). La composición \(v=\sigma\circ u\) sigue siendo inyectiva y satisface \(v(m-1)=n\).
Ahora retiremos la última posición del dominio. Para todo \(k\in I_{m-1}\) tenemos \(k\ne m-1\), de modo que la inyectividad de \(v\) implica \(v(k)\ne n\). Por tanto, la restricción de \(v\) a \(I_{m-1}\) toma valores sólo en \(I_n\) y sigue siendo inyectiva:
\[ v\vert_{I_{m-1}}:I_{m-1}\longrightarrow I_n. \]
Por la hipótesis inductiva, \(m-1\le n\); sumando \(1\) obtenemos \(m\le n+1\). Concluye la inducción. \(\square\)
Lectura de la prueba. No hemos supuesto que el codominio tenga exactamente tantas posiciones como el dominio. Hemos elegido una entrada existente, trasladado su imagen a una posición conveniente y retirado ambas sin destruir la inyectividad. Lo que queda es un problema del mismo tipo, con un codominio de tamaño menor: por eso puede aplicarse la hipótesis inductiva. La permutación sólo cambia nombres de posiciones; no crea ni elimina imágenes.
Una biyección \(I_m\to I_n\) y su inversa dan \(m\le n\) y \(n\le m\); por tanto \(m=n\). Si hay biyecciones \(I_m\to A\) e \(I_n\to A\), componemos la primera con la inversa de la segunda y aplicamos el resultado. Así el tamaño finito está bien definido.
Un subconjunto de un conjunto finito también es finito. Veamos por qué sin presuponer que podemos «contarlo» antes de haber construido la biyección. Basta probarlo para subconjuntos de cada \(I_n\) y transportar después el resultado mediante una biyección.
Procedemos por inducción sobre \(n\). Para \(n=0\), el único subconjunto de \(I_0\) es \(\varnothing\), equipotente a \(I_0\). Supongamos que todo subconjunto de \(I_n\) es finito y tomemos \(S\subseteq I_{n+1}\). Si \(n\notin S\), entonces \(S\subseteq I_n\) y aplicamos la hipótesis inductiva. Si \(n\in S\), el conjunto \(T=S\setminus\{n\}\) está contenido en \(I_n\) y, por hipótesis inductiva, existe alguna biyección \(h:I_k\to T\). La ampliamos a \(I_{k+1}\) mediante la misma regla en las primeras \(k\) posiciones y asignando a la nueva posición \(k\) el valor \(n\). La ampliación es biyectiva sobre \(S\): las imágenes anteriores eran exactamente \(T\) y la nueva imagen \(n\) no pertenece a \(T\). Así también \(S\) es finito. Si \(A\) es finito y \(S\subseteq A\), transportamos \(S\) por la inversa de una biyección \(I_n\to A\) y aplicamos lo demostrado.
Comprobación. ¿Por qué no basta afirmar que la restricción \(v\vert_{I_{m-1}}\) sigue siendo inyectiva, sin explicar además cuál es su codominio?
Respuesta razonada. La hipótesis inductiva se refiere a inyecciones en \(I_n\), no a inyecciones en \(I_{n+1}\). Debemos comprobar que ninguna de las entradas restantes llega a \(n\), para poder restringir de verdad el codominio a \(I_n\). Esa comprobación es el paso que conecta el argumento con la hipótesis inductiva.
Ser infinito no significa tener un último número muy grande
Un conjunto es infinito si no es finito. Los naturales son infinitos. Si hubiera una biyección \(\mathbb N\to I_n\), su restricción a \(I_{n+1}\) sería una inyección en \(I_n\), contraria al principio finito anterior. La afirmación excluye cada posible tamaño finito mediante un argumento, no mediante una lista muy larga.
La función \(f:\mathbb N\to\mathbb N\setminus\{0\}\), \(f(n)=n+1\), es una biyección: su inversa envía \(m\ge1\) a \(m-1\). Por tanto un conjunto infinito puede ser equipotente a un subconjunto propio. Esto no cambia la inclusión: \(\mathbb N\setminus\{0\}\ne\mathbb N\).
Para un conjunto finito ocurre lo contrario, y podemos justificarlo con el lema anterior. Sea \(A\) finito, con \(|A|=n\), y tomemos un subconjunto propio \(S\subsetneq A\). Si \(n=0\), \(A=\varnothing\) y no existe tal subconjunto propio, de modo que el caso sólo puede presentarse con \(n\ge1\). Fijemos una biyección \(e:I_n\to A\) y elijamos \(a\in A\setminus S\). El índice \(j=e^{-1}(a)\) no pertenece a \(e^{-1}(S)\). La permutación de \(I_n\) que intercambia \(j\) con \(n-1\) lleva todos los índices de \(e^{-1}(S)\) a \(I_{n-1}\), pues la única posición que podría transformarse en \(n-1\) es \(j\), que hemos excluido.
Ya sabemos que \(S\) es finito; sea \(|S|=k\) y fijemos una biyección \(h:I_k\to S\). Al componer \(h\) con \(e^{-1}\) y con la permutación anterior, obtenemos una inyección \(I_k\to I_{n-1}\). Nuestro lema obliga a que \(k\le n-1<n\). Por tanto, ningún conjunto finito puede ser equipotente a un subconjunto propio. La intuición «quitar elementos reduce necesariamente el tamaño» requiere la hipótesis de finitud, y ahora hemos probado exactamente dónde interviene.
Comprobación. Una función inyectiva \(I_5\to A\) y otra inyectiva \(A\to I_5\) están dadas. ¿Qué tamaño tiene \(A\)?
Respuesta. La segunda identifica \(A\) con un subconjunto de \(I_5\), así que \(A\) es finito, digamos de tamaño \(k\). Transportando ambas inyecciones a conjuntos de índices, el principio finito da \(5\le k\le5\). Por ello \(|A|=5\). La justificación usa finitud; no invoca un teorema general sobre dos inyecciones entre conjuntos infinitos.
11.9. Numerabilidad y convenciones de tamaño
Un conjunto es numerablemente infinito si es equipotente a \(\mathbb N\). Diremos que es a lo sumo numerable si admite una inyección en \(\mathbb N\). Usaremos «numerable» como abreviatura de «a lo sumo numerable», no como sinónimo de infinito. Así, \(\varnothing\) y todos los conjuntos finitos son numerables. Cuando necesitemos infinitud, lo diremos.
Estas convenciones importan al comparar fuentes: algunos autores reservan «numerable» para conjuntos infinitos. Una diferencia terminológica no es una diferencia matemática si las condiciones están explícitas.
Enumerar un subconjunto infinito de los naturales
Todo subconjunto infinito \(S\subseteq\mathbb N\) es numerablemente infinito. Por buen orden y recursión, tomamos \(s_0=\min S\) y \(s_{n+1}\) como el menor elemento de \(S\) mayor que \(s_n\). Ese conjunto de candidatos es no vacío: si ninguno fuera mayor, \(S\) estaría contenido en el conjunto finito \(\{0,\ldots,s_n\}\) y sería finito por §11.8.
La sucesión es estrictamente creciente, luego inyectiva. Además \(s_n\ge n\), por inducción. Para comprobar que no omite \(m\in S\), supongamos que nunca lo alcanza. El primer término es menor que \(m\); mientras un término sea menor que \(m\), la regla del menor candidato hace que el siguiente sea a lo sumo \(m\), y bajo la suposición de omisión será menor. Se seguiría \(s_n<m\) para todo \(n\), contradiciendo \(s_m\ge m\). Así la función \(n\mapsto s_n\) es sobreyectiva en \(S\).
Si un conjunto infinito \(A\) admite una inyección \(j:A\to\mathbb N\), su imagen \(S=j(A)\) es infinita: una cuenta finita de \(S\) y la biyección \(j:A\to S\) harían finito a \(A\). La enumeración anterior, seguida de la inversa de \(j\) con codominio restringido a \(S\), da una biyección \(\mathbb N\to A\). Hemos probado que «a lo sumo numerable» equivale a «finito o numerablemente infinito» sin usar elección de representantes arbitrarios.
Una enumeración explícita
Los enteros son numerablemente infinitos. Una biyección \(e:\mathbb N\to\mathbb Z\) se define por
\[ e(0)=0,\qquad e(2k+1)=k+1, \qquad e(2k+2)=-(k+1) \quad(k\in\mathbb N). \]
Cada natural distinto de cero cae en exactamente una de las dos formas; los valores recorren respectivamente los enteros positivos y negativos, sin repetirlos ni incluir de nuevo el cero. La inversa envía \(z>0\) a \(2z-1\), \(z<0\) a \(-2z\) y \(0\) a \(0\). Escribir el dominio, la regla y su verificación aporta más que decir «se pueden poner en una lista».
Un tamaño que no cabe en una lista natural
No todo conjunto infinito es numerable. Sea \(D=\{0,1\}^{\mathbb N}\), el conjunto de sucesiones binarias. Si alguien propone una lista \(d_0,d_1,\ldots\) que pretenda cubrir \(D\), definimos una nueva sucesión por
\[ b(n)=1-d_n(n)\qquad(n\in\mathbb N). \]
Cada valor es \(0\) o \(1\), por lo que \(b\in D\). Para cada \(n\), la sucesión \(b\) difiere de \(d_n\) en la coordenada \(n\); no aparece en la lista. No existe, por tanto, sobreyección \(\mathbb N\to D\).
Esto excluye tanto una cuenta infinita como una finita: \(D\) es no vacío, y una lista finita que cubriera \(D\) podría prolongarse repitiendo valores para producir tal sobreyección. Por la equivalencia demostrada arriba, \(D\) no es a lo sumo numerable. No necesitamos comparar todos los tamaños infinitos ni construir una teoría de cardinales para obtener esta conclusión.
Conjuntos, clases y ambientes
Los índices, dominios, familias y cocientes de este capítulo son conjuntos especificados. Un ambiente \(X\) fija el complemento y la intersección vacía; no es un universo que contenga automáticamente todo objeto matemático. «Clase de equivalencia» significa aquí un subconjunto concreto \([x]\subseteq X\), no una clase propia de teoría axiomática de conjuntos. Cuando una teoría posterior necesite otras convenciones, deberá declararlas allí.
Comprobación. ¿Basta que una lista de sucesiones binarias permita calcular cada entrada para que incluya todas las sucesiones?
Respuesta. No. Que la lista esté bien definida permite calcular \(d_n(n)\) y construir \(b(n)=1-d_n(n)\), pero esa construcción exhibe una sucesión fuera de la lista. La buena definición de una enumeración propuesta no demuestra su sobreyectividad.
11.10. Ejercicios y soluciones desarrolladas
Los primeros cinco ejercicios controlan etiquetas y pertenencia; los siguientes cinco construyen productos, particiones y cocientes; los últimos cinco combinan buena definición y tamaño. En cada solución conviene separar los datos conservados por la construcción de las propiedades que todavía hay que probar.
Ejercicios
Ejercicio 1. Tres etiquetas, dos valores. Sea \(I=\{r,s,t\}\), con \(A_r=\{0,2\}\), \(A_s=\{2\}\) y \(A_t=\{0,2\}\). Determine unión, intersección y conjunto de valores de la familia. Un editor cambia \(A_r\) por \(\{2\}\) y \(A_s\) por \(\{0,2\}\), dejando \(A_t\) igual. ¿Qué construcciones permanecen iguales y cuál cambia?
Ejercicio 2. Un ambiente omitido. Una familia tiene índice vacío. Dos lectores calculan su intersección usando ambientes \(X=\{a,b\}\) e \(Y=\{a,b,c\}\), con objetos distintos. Compare sus resultados y sus uniones. ¿Puede resolver la diferencia diciendo que uno olvidó un factor?
Ejercicio 3. Una condición que se aleja. Para \(n\in\mathbb N\), sea \(A_n=\{m\in\mathbb N:m\ge n+2\}\). Determine unión e intersección total, y la intersección de \(A_0,A_1,A_2,A_3\). Explique por qué las dos intersecciones no tienen que coincidir.
Ejercicio 4. Una condición que se amplía. Sea \(B_n=\{m\in\mathbb N:m\le2n+1\}\). Determine unión e intersección de toda la familia. En una prueba de la unión, alguien escribe «para cada \(m\) elijo \(n=m\)». Compruebe si ese testigo sirve, incluidos los valores iniciales.
Ejercicio 5. Repetición y pérdida de posiciones. Use la familia del ejercicio 1. Sea \(J=\{0,1,2,3\}\) y \(r:J\to I\) dada por \(r(0)=r(1)=r\), \(r(2)=s\), \(r(3)=t\); en esta fórmula la letra \(r\) a la derecha de las igualdades representa la etiqueta de \(I\). Compare unión e intersección antes y después de reindexar. Si eliminamos del dominio las posiciones \(2\) y \(3\), ¿qué cambia? Proponga un nombre para la función que evite el doble uso de \(r\).
Ejercicio 6. Un registro con tres campos. Para \(I=\{p,q,r\}\), los factores son \(X_p=\{1,4\}\), \(X_q=\{0,3\}\) y \(X_r=\{2\}\). Liste los elementos del producto dando sus valores en cada etiqueta. Determine las imágenes de las tres proyecciones y explique por qué el conjunto unión de los factores no describe el mismo objeto.
Ejercicio 7. Dos vacíos distintos. Compare el producto sin posiciones con el producto de la familia \(Y_p=\{7\}\), \(Y_q=\varnothing\). Escriba sus elementos si existen. Un informe les asigna a ambos tamaño \(0\); corrija el informe y justifique cada corrección.
Ejercicio 8. Selección y modificación. Sea \(X_n=\{2n,2n+3\}\) para \(n\in\mathbb N\). Construya un elemento \(f\) del producto usando siempre el segundo valor. Modifíquelo sólo en la coordenada \(4\) para que tome allí el primer valor, obteniendo \(g\). Compruebe que ambos pertenecen al producto y determine si \(f=g\).
Ejercicio 9. Bloques y nombres repetidos. Sea \(X=\{a,b,c,d,e,f\}\), con todos los objetos distintos, y \(\mathcal P=\{\{a,d\},\{b,e,f\},\{c\}\}\). Defina la equivalencia por pertenecer a un mismo bloque y liste el cociente. Una lista de sus elementos es \([a],[b],[c],[d],[e],[f]\). Explique por qué no es una cuenta de seis elementos distintos.
Ejercicio 10. Un cociente de registros enteros. En \(\mathbb Z^2\), defina \((a,b)\sim(c,d)\) si \(2a+5b=2c+5d\). Compruebe que es una equivalencia y que \(h(a,b)=2a+5b\) induce una biyección \(\overline h:\mathbb Z^2/{\sim}\to\mathbb Z\). Para la sobreyectividad, construya un representante a partir de cada entero \(t\).
Ejercicio 11. Qué información permite el cociente. En el cociente del ejercicio 10, examine las propuestas \(F([(a,b)])=a+b\) y \(G([(a,b)])=3(2a+5b)-4\). Decida cuáles definen funciones a \(\mathbb Z\) y determine la imagen de las que sí lo hacen. Distinga buena definición de sobreyectividad.
Ejercicio 12. Dos cotas finitas. Se dan una inyección \(I_5\to A\) y una inyección \(A\to I_7\). Demuestre que \(A\) es finito y determine todos los tamaños posibles. Para cada tamaño posible, muestre un conjunto y funciones que cumplan los datos.
Ejercicio 13. Un registro que comienza en 3. Sea \(S=\{4n+3:n\in\mathbb N\}\). Demuestre que \(S\) es numerablemente infinito mediante una biyección explícita. Un lector propone \(u(n)=4n-1\) desde \(\mathbb N\) a \(S\). Localice el defecto y dé dos reparaciones: una de la fórmula y otra del dominio.
Ejercicio 14. Dos canales de un mismo cociente. Sea \(Q\) el cociente del ejercicio 10, y sean \(p,q\) etiquetas distintas. Use la biyección \(\overline h:Q\to\mathbb Z\) y la enumeración \(e:\mathbb N\to\mathbb Z\) de §11.9 para construir una biyección \(Q\times\{p,q\}\to\mathbb N\). Declare todas las funciones auxiliares y verifique que cada natural tiene exactamente una preimagen.
Ejercicio 15. Selecciones completas y listas propuestas. En el producto \(P=\prod_{k\in\mathbb N}\{2k,2k+3\}\), alguien afirma que basta enumerar todas sus funciones como \(f_0,f_1,\ldots\) porque cada coordenada ofrece sólo dos opciones. Construya, a partir de cualquier lista propuesta, una función \(g\in P\) que no aparezca en ella. Explique por qué la no vaciedad de \(P\) y la finitud de los factores no demuestran numerabilidad.
Soluciones desarrolladas
Solución 1. La unión es \(\{0,2\}\): el índice \(r\) ya aporta ambos elementos y ningún factor añade otro. La intersección es \(\{2\}\), pues \(2\) está en los tres factores y \(0\) falta en \(A_s\). El conjunto de valores es \(\{\{0,2\},\{2\}\}\). Tras el cambio permanecen iguales las tres construcciones: sigue habiendo valores de ambos tipos y el único elemento común es \(2\). Cambia la familia, porque cambia su valor en las etiquetas \(r\) y \(s\). Las operaciones no recuperan todas las asignaciones originales.
Solución 2. En ambiente \(X\) la intersección vacía es \(\{a,b\}\) y en ambiente \(Y\) es \(\{a,b,c\}\). Ambas uniones son \(\varnothing\), pues no existe índice testigo. No hay un factor olvidado: las familias no tienen posiciones. La diferencia corresponde al ambiente en la definición de intersección vacía. Para compararlas hay que acordar ese ambiente o mostrarlo como superíndice; no declarar erróneo un cálculo correcto bajo otra convención explícita.
Solución 3. La unión es \(\{m\in\mathbb N:m\ge2\}\). Todo elemento de algún \(A_n\) satisface \(m\ge n+2\ge2\); a la inversa, si \(m\ge2\), pertenece a \(A_0\). La intersección total es vacía: para un candidato \(m\) el índice \(n=m\) exigiría \(m\ge m+2\). La intersección de los cuatro factores es \(A_3=\{m:m\ge5\}\), porque la condición más restrictiva es la de índice \(3\). Las cuatro condiciones no cubren las exigencias arbitrariamente grandes de la familia completa. Cada candidato que satisface las primeras puede fallar en una condición posterior.
Solución 4. La unión es \(\mathbb N\). Para \(m\in\mathbb N\) el testigo \(n=m\) sirve, porque \(m\le2m+1\); también para \(m=0\). No hay elementos fuera de \(\mathbb N\) por definición de cada factor. La intersección es \(\{0,1\}\). Pertenecer a todos los \(B_n\) exige pertenecer a \(B_0=\{0,1\}\); esos dos valores satisfacen \(m\le2n+1\) para todo \(n\ge0\). El testigo de la unión puede variar con \(m\); no estamos fijando una cota uniforme para todos los naturales.
Solución 5. La función cubre las tres etiquetas de \(I\), así que la unión sigue siendo \(\{0,2\}\) y la intersección \(\{2\}\). Repetir el índice \(r\) no modifica las condiciones de pertenencia. Si dejamos sólo las posiciones \(0,1\), ambos valores son \(\{0,2\}\): la unión no cambia, pero la intersección se amplía a \(\{0,2\}\) porque desaparece la condición restrictiva de etiqueta \(s\). La pérdida de sobreyectividad permite un cambio, aunque no obliga a que cambien todas las operaciones. Un nombre como \(\rho:J\to I\) evita usar \(r\) simultáneamente para función y etiqueta.
Solución 6. Describiendo una función por el triple de valores \((f(p),f(q),f(r))\), los elementos son \((1,0,2)\), \((1,3,2)\), \((4,0,2)\) y \((4,3,2)\). Cada elección de las dos primeras coordenadas, combinada con el único valor de la tercera, da exactamente una función. Las imágenes de las proyecciones son respectivamente \(\{1,4\}\), \(\{0,3\}\) y \(\{2\}\). La unión de factores es \(\{0,1,2,3,4\}\); sus elementos son valores individuales y no registros con tres coordenadas. Ni su tipo de elemento ni su tamaño coincide con el del producto.
Solución 7. El producto sin posiciones contiene la función vacía y tiene tamaño \(1\). La condición de pertenencia no exige ningún valor y hay un único grafo con dominio vacío. El segundo producto es vacío y tiene tamaño \(0\): una función admisible tendría que asignar a \(q\) un valor en \(\varnothing\), imposible. El informe confundió ausencia de posiciones con presencia de una posición sin valores. La convención del producto vacío coincide además con la cuenta finita de elecciones: hay una única asignación sin campos.
Solución 8. Definimos \(f(n)=2n+3\) para todo \(n\in\mathbb N\), y \(g(4)=8\), \(g(n)=2n+3\) si \(n\ne4\). Ambas reglas son funciones en todo el dominio. En cada posición, \(f\) toma el segundo valor del factor; \(g\) toma el primero en posición \(4\) y el segundo en las restantes. Así ambos pertenecen al producto. No son iguales, pues \(f(4)=11\) y \(g(4)=8\). Cambiar una coordenada no exige volver a elegir todas las demás: se usa la selección \(f\) ya construida.
Solución 9. Los tres bloques son no vacíos, disjuntos dos a dos y cubren \(X\), por lo que forman una partición. Compartir bloque define una equivalencia por §11.6. El cociente es \(\{\{a,d\},\{b,e,f\},\{c\}\}\) y tiene tamaño \(3\). Se cumple \([a]=[d]\), \([b]=[e]=[f]\) y \([c]=\{c\}\). La lista de seis nombres repite clases; contar nombres de representantes no cuenta elementos distintos del cociente. La proyección envía cada elemento a su bloque y no es inyectiva, por ejemplo porque \(a\ne d\) pero \([a]=[d]\).
Solución 10. Igualdad de los valores \(2a+5b\) es reflexiva, simétrica y transitiva, así que la relación es una equivalencia. La función \(h\) es constante exactamente en esas clases; por §11.7 desciende a \(\overline h([(a,b)])=2a+5b\). Si dos clases tienen la misma imagen, sus representantes satisfacen la relación y las clases son iguales; esto prueba inyectividad. Para \(t\in\mathbb Z\), el par \((-2t,t)\) tiene valor \(2(-2t)+5t=t\). Su clase es una preimagen de \(t\), lo que prueba sobreyectividad. La inversa es \(t\mapsto[(-2t,t)]\): cualquier representante con valor \(t\) pertenece a esa clase, de modo que la fórmula devuelve la entrada correspondiente.
Solución 11. La primera propuesta falla: \((0,0)\) y \((5,-2)\) tienen ambos valor ponderado \(0\), pero sus sumas son respectivamente \(0\) y \(3\). Son representantes de la misma clase que producirían respuestas distintas; \(F\) no define función. Para \(G\), equivalencia de representantes da igualdad de sus valores ponderados y por ello de \(3(2a+5b)-4\). Sí define una función. Su imagen es \(\{3t-4:t\in\mathbb Z\}\), porque \(\overline h\) alcanza todo entero. No es todo \(\mathbb Z\): por ejemplo \(0\) exigiría \(t=4/3\), que no es entero. La comprobación de buena definición no prueba sobreyectividad; son obligaciones distintas.
Solución 12. La inyección \(A\to I_7\) identifica \(A\) con su imagen, un subconjunto de un conjunto finito. Por §11.8, \(A\) es finito; sea \(|A|=k\). Transportando las inyecciones mediante una biyección \(I_k\to A\), obtenemos una inyección \(I_5\to I_k\) y otra \(I_k\to I_7\). El principio finito da \(5\le k\le7\). Los tamaños posibles son \(5,6,7\). Para cada uno, tome \(A=I_k\): la inclusión de \(I_5\) en \(I_k\) y la inclusión de \(I_k\) en \(I_7\) cumplen los datos. Esto muestra que ninguna de las cotas se puede mejorar sin información adicional.
Solución 13. La función \(v:\mathbb N\to S\), \(v(n)=4n+3\), está bien definida y es sobreyectiva por la descripción de \(S\). Si \(v(n)=v(m)\), cancelar \(4\) en los enteros da \(n=m\), luego es inyectiva. Su inversa es \(s\mapsto(s-3)/4\), que es natural precisamente por pertenecer \(s\) a \(S\). Así \(S\) es numerablemente infinito. La regla propuesta \(u\) da \(u(0)=-1\notin S\) y ni siquiera define una función con el codominio declarado. Reparación de fórmula: usar \(v\). Reparación de dominio: restringir \(u\) a \(\mathbb N\setminus\{0\}\); si \(n\ge1\), \(4n-1=4(n-1)+3\), y cada elemento de \(S\) se obtiene una única vez con \(n=k+1\). Ese dominio también es numerablemente infinito por §11.8.
Solución 14. Sea \(j=e^{-1}:\mathbb Z\to\mathbb N\), cuya fórmula se verificó en §11.9. Definimos \(c:Q\to\mathbb N\) por \(c=j\circ\overline h\); es una biyección por composición. Ahora sea \(H:Q\times\{p,q\}\to\mathbb N\) dada por \(H(C,p)=2c(C)\) y \(H(C,q)=2c(C)+1\). Cada natural es de forma única \(2n\) o \(2n+1\), con \(n\in\mathbb N\). En el primer caso su preimagen es \((c^{-1}(n),p)\); en el segundo, \((c^{-1}(n),q)\). La unicidad de la paridad y de \(c^{-1}(n)\) prueba simultáneamente inyectividad y sobreyectividad. La función auxiliar \(c\) usa clases, no representantes elegidos libremente, por lo que la fórmula queda bien definida.
Solución 15. Para la lista propuesta definimos \(g(k)=2k+3\) si \(f_k(k)=2k\), y \(g(k)=2k\) si \(f_k(k)=2k+3\). Las dos alternativas son exhaustivas y excluyentes porque \(f_k\) pertenece al producto y los valores del factor son distintos. La regla define una función en todo \(\mathbb N\) y siempre toma un valor del factor de índice \(k\), así que \(g\in P\). En esa coordenada difiere de \(f_k\); por tanto \(g\ne f_k\) para cada \(k\) y la lista no cubre \(P\). El producto es no vacío por la fórmula del ejercicio 8, pero esa existencia no proporciona una enumeración. Si \(P\) fuera finito no vacío o numerablemente infinito, habría una lista natural sobreyectiva, que el argumento excluye. Por §11.9, \(P\) no es a lo sumo numerable. La finitud de cada factor no limita el conjunto de selecciones completas al tamaño de un único factor.
Cierre del lenguaje estructural
Las construcciones de este capítulo permiten organizar objetos sin perder de vista sus condiciones de uso. Antes de operar con una familia hay que identificar sus índices; antes de tomar un complemento, el ambiente; antes de usar un producto, las coordenadas admisibles; antes de calcular en clases, la independencia del representante; antes de comparar tamaños, la función y las propiedades que justifican la comparación.
El libro ha construido un lenguaje para afirmar, definir, demostrar, explorar, refutar y presentar razonamientos. Los cursos de álgebra, cálculo, análisis y matemática discreta podrán usarlo en contextos propios. La obligación permanece: fijar el dominio, hacer visibles las hipótesis y justificar exactamente la conclusión que se afirma.