Matemáticas universitarias — Grado 1 · Bachelor Year 1

1Lógica, conjuntos y aplicaciones

Hasta ahora, las demostraciones se han llevado a cabo con una idea informal pero honesta de lo que significa «demostrar». Este primer capítulo de matemáticas universitarias explicita las reglas del juego: qué es un enunciado matemático, cómo los conectivos y los cuantificadores combinan enunciados, qué pasos son lícitos en una demostración — y construye después, sobre esa base, los dos lenguajes universales de las matemáticas: los conjuntos y las aplicaciones.

1.1 Enunciados y conectivos

Definición 1.1 (Enunciado, conectivos)

Un enunciado (o proposición) es una frase que es verdadera (V) o falsa (F) — exactamente una de las dos. A partir de dos enunciados $P$ y $Q$ se forman:

la negación $\lnot P$ («no $P$ »), verdadera exactamente cuando $P$ es falsa;
la conjunción $P \land Q$ (« $P$ y $Q$ »), verdadera exactamente cuando ambas lo son;
la disyunción $P \lor Q$ (« $P$ o $Q$ »), verdadera exactamente cuando al menos una lo es (este «o» es inclusivo);
la implicación $P \implies Q$ , falsa exactamente cuando $P$ es verdadera y $Q$ falsa;
la equivalencia $P \iff Q$ , verdadera exactamente cuando $P$ y $Q$ tienen el mismo valor de verdad.

Observación 1.2

La tabla de verdad de $P \implies Q$ merece una pausa: cuando $P$ es falsa, $P \implies Q$ es verdadera, sea cual sea $Q$ . «Si $2 < 1$ , entonces $0 = 5$ » es una implicación verdadera. Una implicación no afirma nada sobre lo que ocurre cuando su hipótesis falla.

Proposición 1.3 (Reglas de cálculo con enunciados)

Para todos los enunciados $P$ , $Q$ , $R$ :

$\lnot(\lnot P) \iff P$ ;
leyes de De Morgan: $\lnot(P \land Q) \iff (\lnot P) \lor (\lnot Q)$ y $\lnot(P \lor Q) \iff (\lnot P) \land (\lnot Q)$ ;
$(P \implies Q) \iff \bigl((\lnot P) \lor Q\bigr)$ , de donde $\lnot(P \implies Q) \iff P \land (\lnot Q)$ ;
contraposición: $(P \implies Q) \iff \bigl((\lnot Q) \implies (\lnot P)\bigr)$ ;
$(P \iff Q) \iff \bigl((P \implies Q) \land (Q \implies P)\bigr)$ ;
distributividad: $P \land (Q \lor R) \iff (P \land Q) \lor (P \land R)$ and $P \lor (Q \land R) \iff (P \lor Q) \land (P \lor R)$ .

Demostración. Cada equivalencia se comprueba comparando tablas de verdad: dos enunciados compuestos construidos a partir de $P$ , $Q$ , $R$ son equivalentes exactamente cuando toman el mismo valor de verdad en cada uno de los (cuatro u ocho) casos. Escribamos una tabla completa, la de la primera ley de De Morgan:

$P$	$Q$	$P \land Q$	$\lnot(P \land Q)$	$\lnot P$	$\lnot Q$	$(\lnot P) \lor (\lnot Q)$
V	V	V	F	F	F	F
V	F	F	V	F	V	V
F	V	F	V	V	F	V
F	F	F	V	V	V	V

Las columnas $4$ y $7$ coinciden, lo que demuestra la ley. Para la contraposición resulta más rápido un atajo verbal: $P \implies Q$ es falsa exactamente en el caso ( $P$ verdadera, $Q$ falsa), y $(\lnot Q) \implies (\lnot P)$ es falsa exactamente en el caso ( $\lnot Q$ verdadera, $\lnot P$ falsa), es decir ( $Q$ falsa, $P$ verdadera) — el mismo y único caso, de modo que las dos implicaciones tienen tablas idénticas. Las demás reglas se comprueban igual; obsérvese que (3) reduce toda implicación a una disyunción, con lo que (2) produce mecánicamente la regla de negación $\lnot(P \implies Q) \iff P \land (\lnot Q)$ : para contradecir una implicación hay que exhibir un caso en el que la hipótesis se cumpla y la conclusión falle. ∎

1.2 Cuantificadores

Definición 1.4 (Cuantificadores)

Sea $P(x)$ una propiedad de un elemento $x$ de un conjunto $E$ .

$\forall x \in E,\ P(x)$ («para todo $x$ de $E$ , $P(x)$ ») es verdadera cuando todo elemento de $E$ satisface $P$ ;
$\exists x \in E,\ P(x)$ («existe $x$ en $E$ tal que $P(x)$ ») es verdadera cuando al menos un elemento de $E$ satisface $P$ .

Se escribe $\exists!$ para «existe un único».

Proposición 1.5 (Negación de los cuantificadores)

\lnot\bigl(\forall x \in E,\ P(x)\bigr) \iff \exists x \in E,\ \lnot P(x), \qquad \lnot\bigl(\exists x \in E,\ P(x)\bigr) \iff \forall x \in E,\ \lnot P(x).

Demostración. Razonemos la primera equivalencia en los dos sentidos; la segunda es simétrica. Si $\forall x \in E,\ P(x)$ es falsa, no todo elemento satisface $P$ : el conjunto $A = \{x \in E : \lnot P(x)\}$ no puede ser vacío, y cualquiera de sus elementos atestigua $\exists x \in E,\ \lnot P(x)$ . Recíprocamente, si algún $x_0 \in E$ cumple $\lnot P(x_0)$ , entonces $x_0$ es un contraejemplo y el enunciado universal falla. Para la segunda regla: «ningún $x$ satisface $P$ » significa que el conjunto $\{x : P(x)\}$ es vacío, es decir, que todo $x$ está en su complementario $A$ . Aplicadas en cascada a un prefijo de cuantificadores anidados, las dos reglas dan el procedimiento mecánico del Ejemplo 1.8: la negación recorre la fórmula de izquierda a derecha, cambiando cada $\forall$ por $\exists$ y cada $\exists$ por $\forall$ , y niega finalmente el predicado más interno. ∎

Ejemplo 1.6 (Negar frases matemáticas de todos los días)

Sea $f \colon \R \to \R$ . La frase « $f$ es creciente» se escribe

\forall x \in \R,\ \forall y \in \R,\quad x \leq y \implies f(x) \leq f(y) ,

y su negación, por la Proposición 1.5 junto con la regla $\lnot(P \implies Q) \iff P \land \lnot Q$ :

\exists x \in \R,\ \exists y \in \R,\quad x \leq y \ \text{ y }\ f(x) > f(y) :

basta con un par que lo atestigüe. Del mismo modo, « $f$ está acotada» es $\exists M \in \R,\ \forall x \in \R,\ \abs{f(x)} \leq M$ , con negación

\forall M \in \R,\ \exists x \in \R,\quad \abs{f(x)} > M :

sea cual sea la cota propuesta, algún punto la supera. La idea clave: una negación correcta nunca contiene un «no» aplicado a un bloque cuantificado — es un nuevo enunciado positivo en el que los papeles se intercambian: ahora uno produce los testigos que antes recibía.

Ejemplo 1.7 (Orden de los cuantificadores)

El orden de dos cuantificadores distintos importa:

\forall x \in \R,\ \exists y \in \R,\ y > x \quad\text{es verdadera (tómese } y = x+1\text{),}

\exists y \in \R,\ \forall x \in \R,\ y > x \quad\text{es falsa (ningún real supera a todos los reales).}

En el primer enunciado, $y$ puede depender de $x$ ; en el segundo, un único $y$ debe servir para todo $x$ . Dos cuantificadores iguales, en cambio, siempre conmutan.

Ejemplo 1.8 (Leer una definición con tres cuantificadores)

La frase «la sucesión $(u_n)$ converge a $\ell$ » se escribirá en el Capítulo 11 como

\forall \varepsilon > 0,\ \exists N \in \N,\ \forall n \geq N,\quad \abs{u_n - \ell} \leq \varepsilon .

Su negación, aplicando tres veces la Proposición 1.5, es

\exists \varepsilon > 0,\ \forall N \in \N,\ \exists n \geq N,\quad \abs{u_n - \ell} > \varepsilon .

Saber negar mecánicamente frases de este tipo, sin pensar en lo que significan, es una destreza real: separa el trabajo lógico del trabajo matemático.

1.3 Técnicas de demostración

Método 1.9 (Los esquemas de demostración habituales)

Para demostrar…

una implicación $P \implies Q$ directamente: se supone $P$ y se deduce $Q$ ;
por contraposición: se supone $\lnot Q$ y se deduce $\lnot P$ — válido por la Proposición 1.3 (4);
por reducción al absurdo: se supone que el enunciado es falso y se deriva una contradicción;
una equivalencia: se demuestran las dos implicaciones por separado (o se encadenan equivalencias conocidas);
un enunciado «para todo»: se toma un $x$ arbitrario de $E$ («sea $x \in E$ ») y se demuestra $P(x)$ ;
un enunciado «existe»: se exhibe un testigo, o se demuestra la existencia de forma indirecta;
por inducción: véase el Teorema 1.12.

Al demostrar un enunciado sobre un elemento bien elegido pero arbitrario, nunca hay que atribuirle propiedades adicionales: «sea $x \in \R$ » seguido de «como $x > 0$ …» no demuestra nada sobre los $x$ negativos.

Observación 1.10 (Errores frecuentes en las demostraciones)

Cuatro trampas clásicas, que conviene nombrar de una vez.

El recíproco en lugar del contrarrecíproco. $Q \implies P$ no equivale a $P \implies Q$ ; solo lo hace $\lnot Q \implies \lnot P$ . De «si llueve, la calle se moja» no se puede concluir que haya llovido porque la calle esté mojada.
Demostrar una equivalencia con una sola implicación. Una afirmación «si y solo si» son dos teoremas; hay que anunciar qué sentido se demuestra y demostrar los dos. Una cadena de $\iff$ solo es lícita si todos sus eslabones son realmente reversibles — elevar al cuadrado una ecuación, por ejemplo, no lo es.
Demostraciones hacia atrás. Partir de la conclusión deseada y deducir un enunciado verdadero no demuestra nada (de $-1 = 1$ se deduce, elevando al cuadrado, el verdadero $1 = 1$ ). Un cálculo puede descubrirse hacia atrás, pero debe escribirse hacia adelante, o con equivalencias explícitas.
Testigo fijo frente a elemento arbitrario. Para demostrar $\exists x,\ P(x)$ basta exhibir un $x$ hábilmente elegido; para demostrar $\forall x,\ P(x)$ , el $x$ elegido debe seguir siendo arbitrario. Confundir ambas cosas — comprobar una afirmación universal en un ejemplo — es el error más frecuente entre quienes empiezan.

Ejemplo 1.11 (Contraposición y absurdo en acción)

Para $n \in \N$ : si $n^2$ es par, entonces $n$ es par. Por contraposición: si $n$ es impar, $n = 2k+1$ , entonces $n^2 = 4k^2 + 4k + 1$ es impar.

$\sqrt 2$ es irracional. Por reducción al absurdo: supongamos que $\sqrt 2 = p/q$ con $p, q \in \N^*$ y la fracción irreducible. Entonces $p^2 = 2q^2$ es par, luego $p$ es par (punto anterior), $p = 2r$ ; entonces $q^2 = 2r^2$ es par, luego $q$ es par — lo que contradice la irreducibilidad.

Teorema 1.12 (Inducción)

Sea $P(n)$ una propiedad del entero $n$ . Si

$P(0)$ es verdadera, y
para todo $n \in \N$ , $P(n) \implies P(n+1)$ ,

entonces $P(n)$ es verdadera para todo $n \in \N$ .

Inducción fuerte: la conclusión no cambia si se sustituye (2) por: para todo $n$ , $\bigl(P(0) \land \dots \land P(n)\bigr) \implies P(n+1)$ .

Demostración. Se trata de una propiedad del propio $\N$ , equivalente a esta: todo subconjunto no vacío de $\N$ tiene un elemento mínimo (que damos por conocida). En efecto, supongamos (1) y (2) y sea $A = \{n \in \N : P(n) \text{ falsa}\}$ . Si $A \neq \emptyset$ , tiene un elemento mínimo $m$ ; $m \neq 0$ por (1); entonces $m - 1 \notin A$ , luego $P(m-1)$ se cumple, y (2) da $P(m)$ — contradicción. Por tanto $A = \emptyset$ . Para la inducción fuerte se aplica el mismo razonamiento: $P(0), \dots, P(m-1)$ se cumplen todas, pues $m$ es el mínimo de $A$ . ∎

Ejemplo 1.13 (Demostrar existencia y unicidad)

Un enunciado $\exists!\,x,\ P(x)$ son dos enunciados, que se demuestran por separado: la existencia (exhibir o construir algún $x_0$ con $P(x_0)$ ) y la unicidad (suponer $P(x)$ y $P(x')$ y deducir $x = x'$ ). Muestra: existe un único real $x$ tal que $x^3 + x = 2$ . Existencia: $x_0 = 1$ sirve, pues $1 + 1 = 2$ . Unicidad: si $x^3 + x = x'^3 + x'$ , entonces

0 = (x^3 - x'^3) + (x - x') = (x - x')\,\bigl(x^2 + xx' + x'^2 + 1\bigr),

y el segundo factor es positivo (vale $\bigl(x + \tfrac{x'}2\bigr)^2 + \tfrac34 x'^2 + 1 \geq 1$ ), luego $x = x'$ . Obsérvese el reparto del trabajo: la existencia se apoyó en una conjetura afortunada; la unicidad, en un cálculo algebraico válido para soluciones arbitrarias — ninguno de los dos argumentos hace el trabajo del otro, y olvidar la segunda mitad es una tentación constante en cuanto se ha encontrado una solución.

Ejemplo 1.14

Para todo $n \in \N^*$ : $\;\sum_{k=1}^n k = \frac{n(n+1)}{2}$ . Caso base $n = 1$ : los dos miembros valen $1$ . Paso: suponiendo la fórmula para $n$ ,

\sum_{k=1}^{n+1} k = \frac{n(n+1)}{2} + (n+1) = (n+1)\Bigl(\frac n2 + 1\Bigr) = \frac{(n+1)(n+2)}{2}. \qedhere

Ejemplo 1.15 (La inducción fuerte en acción)

Todo entero $n \geq 2$ es un producto de números primos (siendo un primo un entero $\geq 2$ cuyos únicos divisores $\geq 1$ son $1$ y él mismo; los primos se estudian por sí mismos en el Capítulo 6). La inducción ordinaria es impotente aquí: saber que $95 = 5 \times 19$ se factoriza no dice nada sobre $96$ . La inducción fuerte encaja exactamente. Caso base: $2$ es primo, luego es un producto (de un solo factor) de primos. Paso: sea $n \geq 2$ y supongamos que todo entero $m$ con $2 \leq m \leq n$ es un producto de primos. Si $n + 1$ es primo, ya está. En caso contrario $n + 1 = ab$ con $2 \leq a, b \leq n$ ; por la hipótesis fuerte, $a$ y $b$ son productos de primos, y por tanto también lo es $n + 1$ . La idea clave: la inducción fuerte es la herramienta adecuada siempre que la «razón» de $P(n+1)$ resida en un rango anterior imprevisible, y no en el rango $n$ .

1.4 Conjuntos

Definición 1.16 (Operaciones con conjuntos)

Tomamos como primitivas la noción de conjunto y la relación de pertenencia $x \in E$ . Para conjuntos $A, B$ contenidos en un conjunto ambiente $E$ :

inclusión: $A \subseteq B$ cuando $\forall x,\ x \in A \implies x \in B$ ; igualdad $A = B$ cuando $A \subseteq B$ y $B \subseteq A$ ;
unión $A \cup B$ , intersección $A \cap B$ , diferencia $A \setminus B = \{x \in A : x \notin B\}$ , complementario $\overline{A} = E \setminus A$ ;
el conjunto vacío $\emptyset$ , contenido en todo conjunto;
el conjunto de las partes $\mathcal{P}(E)$ : el conjunto de todos los subconjuntos de $E$ ;
el producto $E \times F$ : el conjunto de los pares ordenados $(x, y)$ con $x \in E$ , $y \in F$ .

Ejemplo 1.17 (Familiarizarse con el conjunto de las partes)

Para $E = \{a, b\}$ :

\mathcal P(E) = \bigl\{\, \emptyset,\ \{a\},\ \{b\},\ \{a, b\} \,\bigr\},

cuatro elementos — y obsérvese la disciplina de tipos: $a \in E$ , pero $\{a\} \in \mathcal P(E)$ ; los enunciados $a \in \mathcal P(E)$ y $\{a\} \subseteq \mathcal P(E)$ son ambos falsos tal como están escritos (el segundo exigiría que $a$ fuese un subconjunto de $E$ ). Iterando desde la nada: $\mathcal P(\emptyset) = \{\emptyset\}$ tiene un elemento, $\mathcal P(\mathcal P(\emptyset)) = \{\emptyset, \{\emptyset\}\}$ tiene dos, el siguiente tiene cuatro — los conjuntos de conjuntos son conjuntos ordinarios, y el Capítulo 2 confirmará la duplicación: $\abs{\mathcal P(E)} = 2^{\abs E}$ . Mantener claros los niveles ( $x$ , $\{x\}$ , $\{\{x\}\}$ ) es la mitad del trabajo en ejercicios como los Ejercicios 1.11 y 1.12.

Proposición 1.18 (Álgebra de conjuntos)

Para subconjuntos $A, B, C$ de $E$ :

$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ y $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ ;
De Morgan: $\overline{A \cup B} = \overline{A} \cap \overline{B}$ y $\overline{A \cap B} = \overline{A} \cup \overline{B}$ ;
$A \subseteq B \iff \overline{B} \subseteq \overline{A}$ .

Demostración. Cada identidad traduce una regla de la Proposición 1.3 mediante el diccionario ( $\in A$ o no) $\leftrightarrow$ (enunciado verdadero o falso): por ejemplo, $x \in \overline{A \cup B} \iff \lnot(x \in A \lor x \in B) \iff (x \notin A) \land (x \notin B) \iff x \in \overline{A} \cap \overline{B}$ . El punto (3) es la contraposición. Como segunda muestra, la primera ley distributiva completa:

x \in A \cap (B \cup C) \iff (x \in A) \land \bigl(x \in B \lor x \in C\bigr) \iff \bigl(x \in A \land x \in B\bigr) \lor \bigl(x \in A \land x \in C\bigr),

por la distributividad de la Proposición 1.3 (6), y el último enunciado se lee $x \in (A \cap B) \cup (A \cap C)$ . Toda identidad conjuntista de este tipo se demuestra con esta única traducción mecánica — razón por la cual ninguna de ellas hay que memorizarla. ∎

Método 1.19 (Demostrar igualdades de conjuntos)

Para demostrar $A = B$ se prueban las dos inclusiones: sea $x \in A$ , se comprueba que $x \in B$ ; después, sea $x \in B$ , se comprueba que $x \in A$ . Otra vía es encadenar equivalencias $x \in A \iff \dots \iff x \in B$ , cuando cada paso sea realmente una equivalencia.

Las leyes de De Morgan en imágenes: la región sombreada de la izquierda es A ∪ B = A ∩ B (todo lo que queda fuera de los dos discos); a la derecha, A ∩ B = A ∪ B (todo salvo la lente central). Un dibujo no es una demostración, pero hace imposible recordar mal la demostración por elementos de la . — Las leyes de De Morgan en imágenes: la región sombreada de la izquierda es $\overline{A \cup B} = \overline A \cap \overline B$ (todo lo que queda fuera de los dos discos); a la derecha, $\overline{A \cap B} = \overline A \cup \overline B$ (todo salvo la lente central). Un dibujo no es una demostración, pero hace imposible recordar mal la demostración por elementos de la Proposición 1.18.

1.5 Aplicaciones

Definición 1.20 (Aplicación, imagen, imagen recíproca)

Una aplicación (o función) $f \colon E \to F$ asigna a cada elemento $x$ del conjunto $E$ (el dominio) exactamente un elemento $f(x)$ del conjunto $F$ (el codominio). Para $A \subseteq E$ y $B \subseteq F$ :

f(A) = \{f(x) : x \in A\} \subseteq F, \qquad f^{-1}(B) = \{x \in E : f(x) \in B\} \subseteq E

son la imagen directa de $A$ y la imagen recíproca de $B$ . La composición de $f \colon E \to F$ y $g \colon F \to G$ es $g \circ f \colon E \to G$ , $x \mapsto g(f(x))$ .

Observación 1.21

La notación $f^{-1}(B)$ no presupone que exista una aplicación inversa: $f^{-1}(B)$ está definida para toda $f$ . Las imágenes recíprocas se comportan mejor que las directas: $f^{-1}$ conserva uniones, intersecciones y complementarios, mientras que $f(A \cap A') \subseteq f(A) \cap f(A')$ puede ser estricta (Ejercicio 1.8).

Ejemplo 1.22 (Cálculo de imágenes e imágenes recíprocas)

Sea $f \colon \R \to \R$ , $x \mapsto x^2$ . Entonces:

f\bigl(\intcc{-1}{2}\bigr) = \intcc04, \qquad f^{-1}\bigl(\intcc14\bigr) = \intcc{-2}{-1} \cup \intcc12, \qquad f^{-1}(\{-1\}) = \emptyset .

Para la primera: todo $x \in \intcc{-1}2$ cumple $x^2 \in \intcc04$ , y todo $y \in \intcc04$ se alcanza como $y = (\sqrt y)^2$ con $\sqrt y \in \intcc02 \subseteq \intcc{-1}2$ — obsérvese que la imagen no es $\intcc14 = \{(-1)^2, 2^2\}$ : las imágenes de intervalos no se calculan solo con los extremos. Para la segunda: $1 \leq x^2 \leq 4 \iff 1 \leq \abs x \leq 2$ , que se parte en dos trozos. La tercera ilustra que una imagen recíproca puede ser vacía — $f^{-1}(B)$ siempre tiene sentido, por pequeña que sea la intersección de $B$ con la imagen. Por último, obsérvese en este ejemplo el fenómeno de inclusión estricta de la observación anterior: con $A = \intcc{-1}0$ y $A' = \intcc01$ se tiene $f(A \cap A') = f(\{0\}) = \{0\}$ , mientras que $f(A) \cap f(A') = \intcc01$ .

Definición 1.23 (Inyectiva, sobreyectiva, biyectiva)

Una aplicación $f \colon E \to F$ es:

inyectiva cuando elementos distintos tienen imágenes distintas: $\forall x, x' \in E,\ f(x) = f(x') \implies x = x'$ ;
sobreyectiva cuando todo elemento de $F$ se alcanza: $\forall y \in F,\ \exists x \in E,\ f(x) = y$ ;
biyectiva cuando es ambas cosas, es decir, cuando todo $y \in F$ tiene exactamente una imagen recíproca.

Teorema 1.24 (Aplicación inversa)

Una aplicación $f \colon E \to F$ es biyectiva si y solo si existe una aplicación $g \colon F \to E$ tal que $g \circ f = \mathrm{id}_E$ y $f \circ g = \mathrm{id}_F$ . En tal caso $g$ es única; se escribe $f^{-1}$ y se llama inversa de $f$ , y $f^{-1}$ es a su vez biyectiva, con $(f^{-1})^{-1} = f$ .

Demostración. ( $\Rightarrow$ ) Si $f$ es biyectiva, todo $y \in F$ tiene una única imagen recíproca; se define $g(y)$ como esa imagen recíproca. Entonces $f(g(y)) = y$ por construcción, y $g(f(x)) = x$ porque $x$ es la imagen recíproca de $f(x)$ .

( $\Leftarrow$ ) Supongamos que existe tal $g$ . Si $f(x) = f(x')$ , aplicando $g$ se obtiene $x = x'$ : $f$ es inyectiva. Para $y \in F$ , $x = g(y)$ cumple $f(x) = y$ : $f$ es sobreyectiva.

Unicidad: si $g$ y $h$ sirven las dos, entonces $g = g \circ \mathrm{id}_F = g \circ (f \circ h) = (g \circ f) \circ h = h$ . Por último, el par de identidades es simétrico en $f$ y $g$ , luego $g = f^{-1}$ es biyectiva con inversa $f$ . ∎

Ejemplo 1.25 (Cálculo de una inversa en la práctica)

Sea $f \colon \R \to \intoo0{+\infty}$ , $f(x) = \eu^{2x+1}$ . Para invertirla se resuelve $y = f(x)$ para un $y > 0$ dado:

y = \eu^{2x+1} \iff \ln y = 2x + 1 \iff x = \frac{\ln y - 1}2 ,

siendo cada paso reversible en los dominios anunciados. El cálculo lo entrega todo a la vez: para cada $y$ del codominio hay exactamente una solución $x$ , luego $f$ es biyectiva, y

f^{-1} \colon \intoo0{+\infty} \to \R, \qquad f^{-1}(y) = \frac{\ln y - 1}2 .

Una comprobación rápida de las dos composiciones ( $f^{-1}(f(x)) = \frac{(2x+1) - 1}2 = x$ y $f(f^{-1}(y)) = \eu^{\ln y} = y$ ) confirma el criterio del Teorema 1.24. La idea clave: «despejar $x$ y vigilar las equivalencias» es a la vez la demostración de existencia, la de unicidad y la fórmula — pero solo funciona si el codominio se anunció correctamente ( $f$ no es sobreyectiva sobre $\R$ ).

Proposición 1.26 (La composición y las tres propiedades)

Sean $f \colon E \to F$ y $g \colon F \to G$ .

Si $f$ y $g$ son inyectivas (resp. sobreyectivas, biyectivas), también lo es $g \circ f$ ; y entonces $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ en el caso biyectivo.
Si $g \circ f$ es inyectiva, entonces $f$ es inyectiva. Si $g \circ f$ es sobreyectiva, entonces $g$ es sobreyectiva.

Demostración. (1) Si $g(f(x)) = g(f(x'))$ , la inyectividad de $g$ da $f(x) = f(x')$ , y la de $f$ da entonces $x = x'$ . Si $z \in G$ , la sobreyectividad de $g$ da un $y$ con $g(y) = z$ , y la de $f$ da un $x$ con $f(x) = y$ , de modo que $g(f(x)) = z$ . En el caso biyectivo se comprueba directamente que $f^{-1} \circ g^{-1}$ es una inversa por los dos lados de $g \circ f$ , y la unicidad del Teorema 1.24 concluye.

(2) Si $f(x) = f(x')$ , entonces $g(f(x)) = g(f(x'))$ , y la inyectividad de $g \circ f$ da $x = x'$ . Si $z \in G$ , la sobreyectividad de $g \circ f$ da un $x$ con $g(f(x)) = z$ : entonces $y = f(x)$ cumple $g(y) = z$ . ∎

Ejemplo 1.27 (El punto (2) no se puede mejorar)

En la Proposición 1.26 (2) no se pueden reforzar las conclusiones: que $g \circ f$ sea biyectiva no obliga a que $f$ sea sobreyectiva ni a que $g$ sea inyectiva. Tómese $E = G = \{1\}$ , $F = \{1, 2\}$ , con $f(1) = 1$ y $g(1) = g(2) = 1$ : entonces $g \circ f = \mathrm{id}_E$ es biyectiva, pero $f$ no alcanza el elemento $2$ y $g$ colapsa los dos elementos. La moraleja es una regla de contabilidad precisa: la información sobre la composición pasa a la aplicación interior para la inyectividad y a la exterior para la sobreyectividad, nunca al revés. (El Ejercicio 1.9 construye el mismo fenómeno con conjuntos infinitos, donde es el motor de las inversas laterales.)

Ejemplo 1.28

$f \colon \R \to \R$ , $x \mapsto x^2$ no es inyectiva ( $f(-1) = f(1)$ ) ni sobreyectiva ( $-1$ no tiene imagen recíproca). Restringiendo el dominio y el codominio, $f \colon \R_+ \to \R_+$ , $x \mapsto x^2$ sí es biyectiva, con inversa $y \mapsto \sqrt y$ . Que una aplicación sea inyectiva o sobreyectiva depende del dominio y del codominio anunciados, no solo de la fórmula.

1.6 Relaciones

Definición 1.29 (Relación de equivalencia)

Una relación binaria $\mathcal{R}$ en un conjunto $E$ es una relación de equivalencia cuando es reflexiva ( $x \mathbin{\mathcal{R}} x$ para todo $x$ ), simétrica ( $x \mathbin{\mathcal{R}} y \implies y \mathbin{\mathcal{R}} x$ ) y transitiva ( $x \mathbin{\mathcal{R}} y$ e $y \mathbin{\mathcal{R}} z$ implican $x \mathbin{\mathcal{R}} z$ ). La clase de equivalencia de $x$ es $\mathrm{cl}(x) = \{y \in E : x \mathbin{\mathcal{R}} y\}$ .

Ejemplo 1.30 (Comprobar los tres axiomas)

En $\R$ , se declara $x \mathbin{\mathcal{R}} y$ cuando $x - y \in \Z$ . Reflexiva: $x - x = 0 \in \Z$ . Simétrica: si $x - y \in \Z$ , entonces $y - x = -(x - y) \in \Z$ . Transitiva: si $x - y \in \Z$ e $y - z \in \Z$ , entonces $x - z = (x - y) + (y - z) \in \Z$ (suma de enteros). Así pues, $\mathcal R$ es una relación de equivalencia, y $\mathrm{cl}(x) = x + \Z = \{x + k : k \in \Z\}$ : cada clase contiene exactamente un representante en $\intco01$ , su parte fraccionaria. En cambio, la relación « $\abs{x - y} \leq 1$ » en $\R$ es reflexiva y simétrica, pero no transitiva ( $0 \mathbin{\mathcal R} 1$ y $1 \mathbin{\mathcal R} 2$ , y sin embargo $\abs{0 - 2} > 1$ ): la proximidad no se propaga, y no existe ninguna partición en clases — un contraejemplo útil cuando comprobar los axiomas empieza a parecer rutinario.

Teorema 1.31 (Las clases forman una partición)

Sea $\mathcal{R}$ una relación de equivalencia en $E$ . Entonces las clases de equivalencia son no vacías, dos a dos disjuntas o iguales, y su unión es $E$ : forman una partición de $E$ . Recíprocamente, toda partición de $E$ proviene de este modo de exactamente una relación de equivalencia («estar en el mismo trozo»).

Demostración. $x \in \mathrm{cl}(x)$ por reflexividad, luego las clases son no vacías y su unión es $E$ . Supongamos que $\mathrm{cl}(x) \cap \mathrm{cl}(y) \neq \emptyset$ , digamos que $z$ está en las dos. Entonces $x \mathbin{\mathcal{R}} z$ e $y \mathbin{\mathcal{R}} z$ , luego, por simetría y transitividad, $x \mathbin{\mathcal{R}} y$ . Ahora bien, para cualquier $t \in \mathrm{cl}(y)$ , la transitividad da $t \in \mathrm{cl}(x)$ , y simétricamente: las dos clases son iguales. Para el recíproco, sea $(E_i)_{i \in I}$ una partición de $E$ y definamos $x \mathbin{\mathcal S} y$ como «algún trozo contiene a la vez a $x$ y a $y$ ». Reflexiva: $x$ está en algún trozo, que contiene entonces a $x$ dos veces. Simétrica: la condición que la define es simétrica en $x$ e $y$ . Transitiva: si $x, y \in E_i$ e $y, z \in E_j$ , entonces $y \in E_i \cap E_j$ , luego $E_i = E_j$ (dos trozos distintos son disjuntos) y $x, z$ comparten trozo. La clase de $x$ para $\mathcal S$ es exactamente el trozo que contiene a $x$ , de modo que las clases son los trozos dados. Por último, la relación queda determinada por sus clases: dos relaciones de equivalencia con las mismas clases relacionan los mismos pares, ya que cada una relaciona $x$ e $y$ exactamente cuando $y$ pertenece a la clase de $x$ — de donde la unicidad afirmada. ∎

Ejemplo 1.32

En $\Z$ , la congruencia módulo $n$ ( $x \equiv y \pmod n$ cuando $n$ divide a $x - y$ ) es una relación de equivalencia; sus clases son los $n$ conjuntos de enteros con un resto dado en la división por $n$ . Este ejemplo se convierte en el anillo $\Z/n\Z$ en el Capítulo 7.

Definición 1.33 (Relación de orden)

Una relación $\preceq$ en $E$ es un orden cuando es reflexiva, antisimétrica ( $x \preceq y$ e $y \preceq x$ implican $x = y$ ) y transitiva. El orden es total cuando dos elementos cualesquiera son comparables, y parcial en caso contrario. Un elemento $M \in A \subseteq E$ es un máximo de $A$ cuando $a \preceq M$ para todo $a \in A$ ; el máximo (y el mínimo) es único cuando existe.

Ejemplo 1.34

$(\R, \leq)$ está totalmente ordenado. $(\mathcal{P}(E), \subseteq)$ está parcialmente ordenado en cuanto $E$ tiene dos elementos: $\{a\}$ y $\{b\}$ no son comparables. El subconjunto $A = \{\{a\}, \{b\}\}$ de $\mathcal{P}(\{a,b\})$ no tiene máximo, y sin embargo tiene una cota superior, $\{a, b\}$ : la distinción entre máximos y cotas superiores reaparece, para $\R$ , en el Capítulo 10.

Ejemplo 1.35 (Dos órdenes en la cuadrícula $\N^2$ )

En los pares de naturales, se comparan componente a componente: $(a, b) \preceq (a', b')$ cuando $a \leq a'$ y $b \leq b'$ (el orden producto). Es un orden — cada axioma se hereda coordenada a coordenada — pero parcial: $(1, 3)$ y $(2, 0)$ son incomparables. Comparémoslos ahora como en un diccionario: $(a, b) \preceq_{\mathrm{lex}} (a', b')$ cuando $a < a'$ , o bien $a = a'$ y $b \leq b'$ (el orden lexicográfico). La transitividad exige distinguir dos casos, pero se cumple, y ahora dos pares cualesquiera son comparables: el orden es total. Los dos órdenes ordenan el mismo conjunto de manera distinta — $(0, 100) \preceq_{\mathrm{lex}} (1, 0)$ aunque el orden producto no diga nada — lo que recuerda que un orden es una estructura que se elige, no una propiedad del conjunto. La comparación lexicográfica es además el truco habitual para reducir varios criterios de ordenación a uno solo.

Observación 1.36 (Interludio: el tamaño como biyección)

Un tema callado de este capítulo merece un foco: las biyecciones son la noción matemática de «mismo tamaño». Para los conjuntos finitos se convierte en el cálculo combinatorio del Capítulo 2, donde toda fórmula es en secreto una biyección; para los conjuntos infinitos, en el problema del fin de semana que cierra el capítulo, donde $\N$ , $\Q$ y $\R$ resultan tener tamaños genuinamente distintos. El mismo diccionario reaparece dos veces más en este volumen, en formas refinadas: las sucesiones (Capítulo 11) no son otra cosa que aplicaciones $\N \to \R$ , de modo que los enunciados sobre sucesiones son enunciados sobre un conjunto de aplicaciones; y el álgebra lineal medirá los espacios vectoriales no con biyecciones, sino con biyecciones lineales, cuya existencia está gobernada por un único número, la dimensión (Capítulo 19). Siempre que aparece una nueva «igualdad» — equipotencia, isomorfismo de grupos (Capítulo 7), isomorfismo lineal — se repite el patrón del Teorema 1.24: la igualdad es una aplicación invertible que respeta la estructura.

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

En todas partes — pero algunos lugares merecen señalarse. La gimnasia de tres cuantificadores del Ejemplo 1.8 es el pan de cada día de los Capítulos 11 y 13: toda demostración de un límite es una partida jugada contra un $\varepsilon$ arbitrario. Las clases de equivalencia reaparecen como las clases de congruencia de $\Z/n\Z$ en el Capítulo 7, donde la partición del Teorema 1.31 adquiere una estructura algebraica propia. Las relaciones de orden, las cotas superiores y los extremos superiores se convierten en el corazón axiomático de $\R$ en el Capítulo 10. Las inyecciones, sobreyecciones y biyecciones vuelven como las aplicaciones lineales del Capítulo 20, donde la inyectividad se puede comprobar sobre un solo vector (el núcleo); y el problema del fin de semana convierte la noción desnuda de biyección en una teoría de los tamaños de los conjuntos infinitos, cuyas conclusiones (numerabilidad de $\Q$ , no numerabilidad de $\R$ ) reaparecen en los Capítulos 10 y 12.

1.7 Ejercicios

Ejercicio 1.1 ★

Escríbase la negación de cada enunciado sin emplear la palabra «no»:

$\forall x \in \R,\ \exists y \in \R,\ x + y > 0$ ;
$\exists x \in \R,\ \forall y \in \R,\ xy = 0$ ;
$\forall \varepsilon > 0,\ \exists \delta > 0,\ \forall x \in \R,\ \abs{x} \leq \delta \implies \abs{f(x)} \leq \varepsilon$ (para una aplicación fija $f \colon \R \to \R$ ).

Decídase después si los enunciados (1) y (2) son verdaderos.

Solución

Solución de Ejercicio 1.1.

Negaciones, haciendo pasar $\lnot$ a través de cada cuantificador (Proposición 1.5) y usando $\lnot(P \implies Q) \iff P \land \lnot Q$ :

$\exists x \in \R,\ \forall y \in \R,\ x + y \leq 0$ ;
$\forall x \in \R,\ \exists y \in \R,\ xy \neq 0$ ;
$\exists \varepsilon > 0,\ \forall \delta > 0,\ \exists x \in \R,\ \abs{x} \leq \delta \text{ y } \abs{f(x)} > \varepsilon$ .

El enunciado (1) es verdadero: dado $x$ , tómese $y = -x + 1$ ; entonces $x + y = 1 > 0$ . El enunciado (2) es verdadero: $x = 0$ cumple $xy = 0$ para todo $y$ .

Ejercicio 1.2 ★

Sean $P, Q$ dos enunciados. Demuéstrese con tablas de verdad que $\lnot(P \implies Q) \iff P \land (\lnot Q)$ , y dedúzcase la negación de: «si una función es derivable, entonces es continua».

Solución

Solución de Ejercicio 1.2.

Tabla de verdad, escribiendo V/F para los cuatro casos $(P, Q)$ :

$P$	$Q$	$P \implies Q$	$\lnot(P \implies Q)$	$\lnot Q$	$P \land \lnot Q$
V	V	V	F	F	F
V	F	F	V	V	V
F	V	V	F	F	F
F	F	V	F	V	F

Las columnas $4$ y $6$ coinciden, lo que demuestra la equivalencia. Por tanto, la negación de «si una función es derivable, entonces es continua» es: «existe una función derivable y no continua» (un enunciado falso, dicho sea de paso: la implicación de partida es verdadera, véase el Capítulo 14).

Ejercicio 1.3 ★

Demuéstrese por contraposición: para $x \in \R$ , si $x^3 + x \geq 2$ , entonces $x \geq 1$ . Demuéstrese después por reducción al absurdo que no existe el menor número real estrictamente positivo.

Solución

Solución de Ejercicio 1.3.

Contraposición. Supongamos $x < 1$ . Entonces $x^3 < 1$ (la función cubo es creciente) y $x < 1$ , luego $x^3 + x < 2$ . Esto demuestra el contrarrecíproco y, por tanto, el enunciado.

Reducción al absurdo. Supongamos que $a > 0$ es el menor real estrictamente positivo. Entonces $a/2$ es estrictamente positivo y $a/2 < a$ (pues $a > 0$ ), lo que contradice la minimalidad. Luego no existe tal $a$ .

Ejercicio 1.4 ★

Demuéstrese por inducción que, para todo $n \in \N$ :

$\sum_{k=0}^{n} 2^k = 2^{n+1} - 1$ ;
$4^n + 5$ es divisible por $3$ .

Solución

Solución de Ejercicio 1.4.

Caso base $n = 0$ : $2^0 = 1 = 2^1 - 1$ . Paso: suponiendo la identidad para $n$ ,

$\sum_{k=0}^{n+1} 2^k = (2^{n+1} - 1) + 2^{n+1} = 2 \cdot 2^{n+1} - 1 = 2^{n+2} - 1 .$
Caso base $n = 0$ : $4^0 + 5 = 6 = 3 \times 2$ . Paso: si $4^n + 5 = 3m$ , entonces

$4^{n+1} + 5 = 4(4^n + 5) - 15 = 3(4m - 5),$

divisible por $3$ .

Ejercicio 1.5 ★

Encuéntrese el fallo de la siguiente «demostración» de que todos los lápices tienen el mismo color. Sea $P(n)$ : «en todo conjunto de $n$ lápices, todos los lápices tienen el mismo color». $P(1)$ es evidente. Supongamos $P(n)$ y tomemos $n+1$ lápices; quitando el último, los $n$ primeros comparten color; quitando el primero, los $n$ últimos comparten color; luego los $n+1$ comparten color.

Solución

Solución de Ejercicio 1.5.

El paso de inducción supone en silencio que los dos grupos («los $n$ primeros» y «los $n$ últimos») se solapan, de modo que los lápices comunes transportan el color de un grupo al otro. Para $n + 1 = 2$ los dos grupos son $\{$ primer lápiz $\}$ y $\{$ segundo lápiz $\}$ : son disjuntos y el argumento se rompe. Así pues, $P(1) \implies P(2)$ nunca quedó demostrado y la inducción se desmorona — aunque $P(n) \implies P(n+1)$ sí sea válido para todo $n \geq 2$ .

Ejercicio 1.6 ★

Sean $A, B, C$ subconjuntos de $E$ . Demuéstrese:

$A \setminus B = A \cap \overline{B}$ ;
$(A \cup B) \setminus C = (A \setminus C) \cup (B \setminus C)$ ;
$A \subseteq B \iff A \cup B = B \iff A \cap B = A$ .

Solución

Solución de Ejercicio 1.6.

$x \in A \setminus B \iff x \in A \land x \notin B \iff x \in A \land x \in \overline{B} \iff x \in A \cap \overline{B}$ .
Usando (1) y la distributividad (Proposición 1.18): $(A \cup B) \cap \overline{C} = (A \cap \overline{C}) \cup (B \cap \overline{C})$ .
Supongamos $A \subseteq B$ . Entonces $A \cup B \subseteq B$ (las dos partes están en $B$ ) y $B \subseteq A \cup B$ siempre, luego $A \cup B = B$ . Supongamos $A \cup B = B$ : entonces $A \cap B \subseteq A$ siempre, y $A \subseteq A \cup B = B$ da $A \subseteq A \cap B$ , luego $A \cap B = A$ . Supongamos $A \cap B = A$ : entonces $A = A \cap B \subseteq B$ . Las tres condiciones son, pues, equivalentes (hemos demostrado un ciclo de implicaciones).

Ejercicio 1.7 ★★

Decídase, con demostración, si cada aplicación es inyectiva, sobreyectiva o biyectiva:

$f \colon \N \to \N$ , $n \mapsto n + 1$ ;
$g \colon \Z \to \Z$ , $n \mapsto n + 1$ ;
$h \colon \R \setminus \{1\} \to \R$ , $x \mapsto \frac{x+1}{x-1}$ .

Para $h$ , ajústese el codominio para hacerla biyectiva y calcúlese la inversa.

Solución

Solución de Ejercicio 1.7.

$f$ es inyectiva ( $n + 1 = m + 1 \implies n = m$ ) pero no sobreyectiva: $0$ no tiene imagen recíproca en $\N$ .
$g$ es biyectiva: $n \mapsto n - 1$ es una inversa por los dos lados en $\Z$ .
$h$ es inyectiva: $\frac{x+1}{x-1} = \frac{x'+1}{x'-1}$ da $(x+1)(x'-1) = (x'+1)(x-1)$ , es decir, $xx' - x + x' - 1 = xx' - x' + x - 1$ , luego $2x' = 2x$ . No es sobreyectiva sobre $\R$ : al resolver $y = \frac{x+1}{x-1}$ se obtiene $x(y - 1) = y + 1$ , que no tiene solución cuando $y = 1$ (la ecuación queda $0 = 2$ ). Con codominio $\R \setminus \{1\}$ , el mismo cálculo da la única imagen recíproca $x = \frac{y+1}{y-1}$ , de modo que $h \colon \R \setminus \{1\} \to \R \setminus \{1\}$ es biyectiva y $h^{-1}(y) = \frac{y+1}{y-1} = h(y)$ : $h$ es su propia inversa.

Ejercicio 1.8 ★★

Sea $f \colon E \to F$ , y sean $A, A' \subseteq E$ y $B, B' \subseteq F$ .

Demuéstrese que $f^{-1}(B \cap B') = f^{-1}(B) \cap f^{-1}(B')$ y que $f(A \cup A') = f(A) \cup f(A')$ .
Demuéstrese que $f(A \cap A') \subseteq f(A) \cap f(A')$ y dese un ejemplo en el que la inclusión sea estricta.
Demuéstrese que $f$ es inyectiva si y solo si $f(A \cap A') = f(A) \cap f(A')$ para todos $A, A'$ .

Solución

Solución de Ejercicio 1.8.

$x \in f^{-1}(B \cap B') \iff f(x) \in B \cap B' \iff f(x) \in B \land f(x) \in B' \iff x \in f^{-1}(B) \cap f^{-1}(B')$ . Para las imágenes: $y \in f(A \cup A')$ si y solo si $y = f(x)$ para algún $x$ de $A$ o de $A'$ , si y solo si $y \in f(A)$ o $y \in f(A')$ .
Si $y \in f(A \cap A')$ , entonces $y = f(x)$ con $x \in A$ y $x \in A'$ , luego $y \in f(A)$ e $y \in f(A')$ . Estrictitud: tómese $f \colon \R \to \R$ , $x \mapsto x^2$ , $A = \{-1\}$ , $A' = \{1\}$ : entonces $f(A \cap A') = f(\emptyset) = \emptyset$ , pero $f(A) \cap f(A') = \{1\}$ .
( $\Leftarrow$ ) Con $A = \{x\}$ , $A' = \{x'\}$ para $x \neq x'$ : si $f(x) = f(x')$ , entonces $f(A) \cap f(A') = \{f(x)\}$ mientras que $f(A \cap A') = \emptyset$ , lo que contradice la igualdad supuesta; luego $f$ es inyectiva. ( $\Rightarrow$ ) Sea $f$ inyectiva e $y \in f(A) \cap f(A')$ : $y = f(x) = f(x')$ con $x \in A$ , $x' \in A'$ ; la inyectividad da $x = x' \in A \cap A'$ , luego $y \in f(A \cap A')$ . Con (2), se tiene la igualdad.

Ejercicio 1.9 ★★

Sean $f \colon E \to F$ y $g \colon F \to E$ tales que $g \circ f = \mathrm{id}_E$ . Demuéstrese que $f$ es inyectiva y $g$ es sobreyectiva. Dese un ejemplo en el que ni $f$ ni $g$ sea biyectiva.

Solución

Solución de Ejercicio 1.9.

$g \circ f = \mathrm{id}_E$ es inyectiva y sobreyectiva, luego, por la Proposición 1.26 (2), $f$ es inyectiva y $g$ es sobreyectiva. Ejemplo: $E = \N$ , $F = \Z$ , $f$ la inclusión $n \mapsto n$ , y $g \colon \Z \to \N$ , $g(n) = n$ para $n \geq 0$ y $g(n) = 0$ para $n < 0$ . Entonces $g(f(n)) = n$ para todo $n \in \N$ , pero $f$ no es sobreyectiva y $g$ no es inyectiva.

Ejercicio 1.10 ★★

En $\R$ se define $x \mathbin{\mathcal{R}} y \iff x^2 - y^2 = x - y$ . Demuéstrese que $\mathcal{R}$ es una relación de equivalencia y descríbase la clase de equivalencia de cada real $x$ . ¿Qué clases tienen exactamente un elemento?

Solución

Solución de Ejercicio 1.10.

$x^2 - y^2 = x - y \iff (x - y)(x + y) = x - y \iff (x - y)(x + y - 1) = 0 \iff y = x$ o $y = 1 - x$ . Reflexiva: $y = x$ sirve. Simétrica: la condición « $y = x$ o $y = 1 - x$ » es simétrica en $x$ e $y$ (si $y = 1 - x$ , entonces $x = 1 - y$ ). Transitiva: supongamos $x \mathbin{\mathcal{R}} y$ e $y \mathbin{\mathcal{R}} z$ ; recorriendo los cuatro casos, $z$ vale cada vez $x$ o $1 - x$ (por ejemplo, $y = 1 - x$ y $z = 1 - y$ dan $z = x$ ). Así pues, $\mathcal{R}$ es una relación de equivalencia y $\mathrm{cl}(x) = \{x,\, 1 - x\}$ . Esta clase tiene un solo elemento exactamente cuando $x = 1 - x$ , es decir, para $x = \frac12$ .

Ejercicio 1.11 ★★★

(Cantor) Sea $E$ un conjunto. Demuéstrese que no hay ninguna sobreyección de $E$ sobre $\mathcal{P}(E)$ . Indicación: dada $f \colon E \to \mathcal{P}(E)$ , considérese $D = \{x \in E : x \notin f(x)\}$ .

Solución

Solución de Ejercicio 1.11.

Sea $f \colon E \to \mathcal{P}(E)$ una aplicación cualquiera y póngase $D = \{x \in E : x \notin f(x)\} \in \mathcal{P}(E)$ . Supongamos que $D = f(a)$ para algún $a \in E$ . Si $a \in D$ , entonces, por definición de $D$ , $a \notin f(a) = D$ : contradicción. Si $a \notin D$ , entonces $a \notin f(a)$ , luego, por definición de $D$ , $a \in D$ : contradicción. Así pues, $D$ no está en la imagen de $f$ , y $f$ no es sobreyectiva. (En particular, ningún conjunto está en biyección con su conjunto de las partes: hay «más» subconjuntos de $\N$ que enteros.)

Ejercicio 1.12 ★★★

Sea $f \colon E \to F$ una aplicación. Defínase $\Phi \colon \mathcal{P}(F) \to \mathcal{P}(E)$ por $\Phi(B) = f^{-1}(B)$ .

Demuéstrese que $f$ es sobreyectiva si y solo si $\Phi$ es inyectiva.
Demuéstrese que $f$ es inyectiva si y solo si $\Phi$ es sobreyectiva.

Solución

Solución de Ejercicio 1.12.

( $\Rightarrow$ ) Sea $f$ sobreyectiva y $\Phi(B) = \Phi(B')$ . Para $y \in B$ , tómese $x$ con $f(x) = y$ ; entonces $x \in f^{-1}(B) = f^{-1}(B')$ , luego $y = f(x) \in B'$ . Por tanto $B \subseteq B'$ , y simétricamente $B' \subseteq B$ : $\Phi$ es inyectiva. ( $\Leftarrow$ ) Si $f$ no es sobreyectiva, tómese $y_0 \in F$ fuera de la imagen; entonces $f^{-1}(\{y_0\}) = \emptyset = f^{-1}(\emptyset)$ con $\{y_0\} \neq \emptyset$ , luego $\Phi$ no es inyectiva.
( $\Rightarrow$ ) Sea $f$ inyectiva y $A \subseteq E$ . Póngase $B = f(A)$ ; entonces $f^{-1}(B) = \{x : f(x) \in f(A)\}$ , y la inyectividad da $f(x) \in f(A) \iff x \in A$ , luego $\Phi(B) = A$ : $\Phi$ es sobreyectiva. ( $\Leftarrow$ ) Si $f$ no es inyectiva, tómense $x \neq x'$ con $f(x) = f(x')$ . Todo conjunto imagen recíproca $f^{-1}(B)$ contiene a $x$ si y solo si contiene a $x'$ ; por tanto $\{x\}$ no es de la forma $\Phi(B)$ , y $\Phi$ no es sobreyectiva.

1.8 Problema: comparar infinitos

Problema 1.1

¿Cuándo tienen dos conjuntos «el mismo número de elementos»? La respuesta de Cantor — cuando existe una biyección entre ellos — resulta ser utilizable incluso para conjuntos infinitos, y parte el infinito en tamaños genuinamente distintos. Este problema construye toda la caja de herramientas a partir de las definiciones desnudas del capítulo: el teorema de Cantor–Schröder–Bernstein (dos inyecciones fabrican una biyección), la numerabilidad de $\Q$ , la no numerabilidad de $\R$ por el argumento diagonal y la asombrosa conclusión de Cantor en 1874: existen números trascendentes, y en cantidad masiva, sin exhibir ni uno solo. En todo el problema, para conjuntos $E$ y $F$ , se escribe $E \preceq F$ cuando existe una inyección de $E$ en $F$ , y $E \approx F$ (« $E$ y $F$ son equipotentes») cuando existe una biyección de $E$ sobre $F$ .

Parte I — El vocabulario de la comparación.

Pruébese que $\approx$ se comporta como una relación de equivalencia: $E \approx E$ ; si $E \approx F$ , entonces $F \approx E$ ; si $E \approx F$ y $F \approx G$ , entonces $E \approx G$ . (Cítense con precisión el Teorema 1.24 y la Proposición 1.26.)
Pruébese que $\preceq$ es transitiva y que una inyección $f \colon E \to F$ induce siempre $E \approx f(E)$ .
Sea $E \neq \emptyset$ . Pruébese que $E \preceq F$ si y solo si existe una sobreyección de $F$ sobre $E$ .
Compruébese que $n \mapsto n + 1$ es una biyección de $\N$ sobre $\N^* = \N \setminus \{0\}$ , y que

$\sigma(n) = \frac n2 \ \ (n \text{ par}), \qquad \sigma(n) = -\frac{n+1}2 \ \ (n \text{ impar})$

es una biyección de $\N$ sobre $\Z$ . Así pues, quitar un punto, o duplicar hacia los negativos, no cambia el tamaño de $\N$ .

Parte II — El teorema de Cantor–Schröder–Bernstein. Sean $f \colon E \to F$ y $g \colon F \to E$ dos inyecciones. Defínanse

C_0 = E \setminus g(F), \qquad C_{n+1} = g\bigl(f(C_n)\bigr) \ \ (n \in \N), \qquad C = \bigcup_{n \in \N} C_n,

y sea $h \colon E \to F$ la aplicación que envía $x \in C$ a $f(x)$ , y $x \notin C$ al único $y \in F$ tal que $g(y) = x$ .

Compruébese que $h$ está bien definida: si $x \notin C$ , entonces $x \in g(F)$ , y el elemento $y$ con $g(y) = x$ es único.
Pruébese que $g\bigl(f(C)\bigr) = \bigcup_{n \geq 1} C_n \subseteq C$ . (Las imágenes directas conmutan con las uniones: Ejercicio 1.8.)
Pruébese que $h$ es inyectiva. (Tres casos; en el caso mixto $x \in C$ , $x' \notin C$ , véase que $h(x) = h(x')$ obligaría a que $x' \in g(f(C)) \subseteq C$ .)
Pruébese que $h$ es sobreyectiva: dado $y \in F$ , distínganse los casos $g(y) \notin C$ y $g(y) \in C_n$ para algún $n \geq 1$ (¿por qué es imposible $g(y) \in C_0$ ?), y exhíbase una imagen recíproca de $y$ en cada caso.
Conclúyase el teorema de Cantor–Schröder–Bernstein: si $E \preceq F$ y $F \preceq E$ , entonces $E \approx F$ . Coméntese en una frase qué hace que este enunciado no sea trivial.
Dos aplicaciones. (a) Pruébese que $\intcc01 \approx \intoo01$ . (b) Pruébese que $\varphi(p, q) = 2^p(2q + 1) - 1$ define una biyección de $\N \times \N$ sobre $\N$ — la inyectividad por un argumento de paridad, la sobreyectividad por inducción fuerte (Teorema 1.12). Así pues, $\N \times \N \approx \N$ : el plano de los puntos enteros no es mayor que la recta.

Parte III — Conjuntos numerables. Un conjunto $E$ se llama a lo sumo numerable cuando $E \preceq \N$ , y numerable cuando $E \approx \N$ .

Pruébese que todo subconjunto infinito $A \subseteq \N$ es numerable. (Defínase $\varphi(n)$ por recurrencia como el mínimo de $A \setminus \{\varphi(0), \dots, \varphi(n-1)\}$ ; véase que $\varphi$ es estrictamente creciente, que cumple $\varphi(n) \geq n$ y que alcanza todos los elementos de $A$ .)
Dedúzcase que un conjunto es a lo sumo numerable si y solo si es finito o numerable, y obsérvese que la pregunta 9 da el atajo: si $E \preceq \N$ y $\N \preceq E$ , entonces $E$ es numerable.
Pruébese que si $E$ y $F$ son a lo sumo numerables, también lo es $E \times F$ . Dedúzcase que $\Z \times \N^*$ es numerable.
Pruébese que $\Q$ es numerable. (Inyéctese $\Q$ en $\Z \times \N^*$ escribiendo cada racional como fracción irreducible de denominador positivo — la unicidad de esa representación se demuestra en el Capítulo 6; aplíquese después la pregunta 12.)
Pruébese que una unión numerable de conjuntos numerables es a lo sumo numerable: si cada $E_n$ ( $n \in \N$ ) es a lo sumo numerable, también lo es $\bigcup_{n \in \N} E_n$ . (Envíese $x$ al par $(n, f_n(x))$ , donde $n$ es el índice mínimo con $x \in E_n$ .)
Pruébese que el conjunto de los subconjuntos finitos de $\N$ es numerable. (Envíese un subconjunto finito $F$ a $\sum_{i \in F} 2^i$ ; demuéstrese la inyectividad comparando el mayor elemento en el que difieren dos conjuntos finitos, con ayuda de $\sum_{k=0}^{m-1} 2^k = 2^m - 1$ del Ejercicio 1.4.)

Parte IV — Diagonalización. Denótese por $\{0,1\}^{\N}$ el conjunto de todas las aplicaciones $u \colon \N \to \{0, 1\}$ , es decir, el conjunto de las sucesiones binarias.

Constrúyase una biyección entre $\mathcal{P}(\N)$ y $\{0,1\}^{\N}$ (funciones indicadoras).
(El argumento diagonal) Sea $\Phi \colon \N \to \{0,1\}^{\N}$ una aplicación cualquiera. Considérese la sucesión $d$ definida por $d(n) = 1 - \Phi(n)(n)$ . Pruébese que $d$ no está en la imagen de $\Phi$ , y conclúyase que $\{0,1\}^{\N}$ no es a lo sumo numerable. Explíquese en una frase por qué, a través de la pregunta 17, esto es exactamente el teorema de Cantor (Ejercicio 1.11) para $E = \N$ .
Admítase — como es familiar desde la secundaria y se establece con rigor en el Capítulo 10 — que todo $x \in \intco01$ tiene un único desarrollo decimal propio $x = 0.d_1 d_2 d_3\dots$ (uno que no termine en una sucesión infinita de cifras $9$ ). Dada una sucesión cualquiera $(x_n)_{n \geq 1}$ de elementos de $\intco01$ , constrúyase $x \in \intco01$ con $x \neq x_n$ para todo $n$ : tómese como $n$ -ésima cifra un $5$ si la $n$ -ésima cifra de $x_n$ es distinta de $5$ , y un $6$ en caso contrario. Justifíquese con cuidado que $x$ es propio y que evita todos los $x_n$ , y conclúyase que $\intco01$ no es a lo sumo numerable.
Dedúzcase que $\R$ no es numerable, y que el conjunto $\R \setminus \Q$ de los números irracionales tampoco lo es. ¿En qué sentido preciso «casi todos» los números reales son irracionales?

Parte V — El teorema de Cantor de 1874: existen números trascendentes. Un número real $x$ es algebraico cuando $P(x) = 0$ para algún polinomio no nulo $P$ con coeficientes enteros, y trascendente en caso contrario. Admítase en esta parte — se demuestra en el Capítulo 8 — que un polinomio no nulo de grado $n$ tiene a lo sumo $n$ raíces reales.

Pruébese que todo número racional es algebraico, y hállense polinomios explícitos con coeficientes enteros que anulen a $\sqrt 2$ y a $\sqrt 2 + \sqrt 3$ .
Para $n \in \N$ fijo, pruébese que el conjunto de los polinomios de grado a lo sumo $n$ con coeficientes enteros es numerable. (Inyéctese en $\Z^{n+1}$ y aplíquese inducción sobre $n$ con la pregunta 13.)
Dedúzcase que el conjunto de todos los polinomios con coeficientes enteros es numerable.
Demuéstrese el teorema de Cantor sobre los números algebraicos: el conjunto $\mathcal{A}$ de los números reales algebraicos es numerable.
Conclúyase: existen números reales trascendentes, y el conjunto de los números trascendentes no es numerable. Hágase después balance de todo el problema en unas pocas frases: la cadena $\N \approx \Z \approx \Q \approx \mathcal{A}$ , el salto estricto hasta $\R \approx$ (esencialmente) $\mathcal{P}(\N)$ , dónde fue decisiva cada herramienta (Cantor–Schröder–Bernstein, uniones numerables, la diagonal) — y la fuerza filosófica de demostrar que existen incontables números trascendentes sin nombrar ni uno. (Demostrar que un número concreto como $\pi$ es trascendente es mucho más difícil y queda fuera de este volumen.)

Solución

Solución de Problema 1.1.

1. Reflexiva: $\mathrm{id}_E$ es una biyección de $E$ sobre sí mismo. Simétrica: si $f \colon E \to F$ es biyectiva, el Teorema 1.24 proporciona $f^{-1} \colon F \to E$ , también biyectiva. Transitiva: si $f \colon E \to F$ y $g \colon F \to G$ son biyecciones, la Proposición 1.26 (1) dice que $g \circ f \colon E \to G$ es una biyección. (Esto solo se parece a una relación de equivalencia: la colección de todos los conjuntos no es a su vez un conjunto, por las paradojas que apunta el Ejercicio 1.11; lo que importa son las tres propiedades.)

2. Si $f \colon E \to F$ y $g \colon F \to G$ son inyectivas, $g \circ f$ es inyectiva por la Proposición 1.26 (1): $E \preceq G$ . Para el segundo punto, correstrínjase $f$ a su imagen: la aplicación $\tilde f \colon E \to f(E)$ , $x \mapsto f(x)$ , es sobreyectiva por construcción de $f(E)$ e inyectiva porque lo es $f$ , luego biyectiva: $E \approx f(E)$ .

3. ( $\Rightarrow$ ) Sea $f \colon E \to F$ inyectiva y fíjese $a \in E$ ( $E \neq \emptyset$ ). Defínase $s \colon F \to E$ así: $s(y)$ es el único $x$ con $f(x) = y$ cuando $y \in f(E)$ (unicidad por inyectividad), y $s(y) = a$ en caso contrario. Para todo $x \in E$ se tiene $s(f(x)) = x$ , luego todo $x$ se alcanza: $s$ es sobreyectiva. ( $\Leftarrow$ ) Sea $s \colon F \to E$ sobreyectiva. Para cada $x \in E$ elíjase un $y_x \in F$ con $s(y_x) = x$ , y póngase $u(x) = y_x$ . Si $u(x) = u(x')$ , entonces $x = s(u(x)) = s(u(x')) = x'$ : $u \colon E \to F$ es inyectiva.

4. $n \mapsto n + 1$ envía $\N$ dentro de $\N^*$ , es inyectiva ( $n + 1 = m + 1 \implies n = m$ ) y sobreyectiva (todo $m \geq 1$ es $(m - 1) + 1$ con $m - 1 \in \N$ ). Para $\sigma$ : envía los números pares $0, 2, 4, \dots$ a $0, 1, 2, \dots$ y los impares $1, 3, 5, \dots$ a $-1, -2, -3, \dots$ Inyectividad: las entradas pares caen en $\N$ ( $\sigma(n) = n/2 \geq 0$ ) y las impares, en los enteros estrictamente negativos ( $\sigma(n) = -(n+1)/2 \leq -1$ ), de modo que una colisión tendría que producirse dentro de una misma clase de paridad, donde $\sigma$ es estrictamente monótona ( $n/2 = m/2$ o $(n+1)/2 = (m+1)/2$ obligan a $n = m$ ). Sobreyectividad: $k \geq 0$ es $\sigma(2k)$ ; $k \leq -1$ es $\sigma(-2k - 1)$ con $-2k - 1 \geq 1$ impar. Así pues, $\N \approx \N^*$ y $\N \approx \Z$ .

5. $C_0 = E \setminus g(F) \subseteq C$ , luego $x \notin C$ implica $x \notin C_0$ , es decir, $x \in g(F)$ : algún $y \in F$ cumple $g(y) = x$ . Si además $g(y') = x$ , la inyectividad de $g$ da $y' = y$ . Por tanto, la segunda cláusula de la definición de $h$ selecciona un único elemento bien definido $g^{-1}(x)$ .

6. Las imágenes directas conmutan con las uniones (Ejercicio 1.8 (1), aplicado a $f$ y luego a $g$ ):

g\bigl(f(C)\bigr) = g\Bigl(f\Bigl(\bigcup_{n \in \N} C_n\Bigr)\Bigr) = \bigcup_{n \in \N} g\bigl(f(C_n)\bigr) = \bigcup_{n \in \N} C_{n+1} = \bigcup_{n \geq 1} C_n \subseteq C .

7. Sean $x \neq x'$ en $E$ . Si los dos están en $C$ , entonces $h(x) = f(x) \neq f(x') = h(x')$ por inyectividad de $f$ . Si ninguno está en $C$ , entonces $g(h(x)) = x \neq x' = g(h(x'))$ , luego $h(x) \neq h(x')$ . Si $x \in C$ y $x' \notin C$ (el caso mixto, salvo intercambio de nombres): supongamos $h(x) = h(x')$ , es decir, $f(x) = g^{-1}(x')$ . Aplicando $g$ : $x' = g(f(x)) \in g(f(C))$ , y la pregunta 6 da $x' \in C$ — contradicción. Luego $h(x) \neq h(x')$ en todos los casos: $h$ es inyectiva.

8. Sea $y \in F$ . Caso 1: $g(y) \notin C$ . Entonces $h(g(y)) = g^{-1}(g(y)) = y$ : el elemento $g(y)$ es una imagen recíproca. Caso 2: $g(y) \in C$ , digamos $g(y) \in C_n$ . Como $g(y) \in g(F)$ , se tiene $g(y) \notin C_0 = E \setminus g(F)$ , luego $n \geq 1$ y $g(y) \in C_n = g(f(C_{n-1}))$ : existe $x \in C_{n-1}$ con $g(y) = g(f(x))$ . La inyectividad de $g$ da $y = f(x)$ , y $x \in C_{n-1} \subseteq C$ , luego $h(x) = f(x) = y$ . En ambos casos $y$ se alcanza: $h$ es sobreyectiva y, por tanto, biyectiva.

9. Si $E \preceq F$ y $F \preceq E$ , tómense inyecciones $f \colon E \to F$ y $g \colon F \to E$ ; las preguntas 5–8 construyen una biyección $h \colon E \to F$ , luego $E \approx F$ . El enunciado no es trivial porque las dos inyecciones dadas no guardan relación alguna — ninguna tiene por qué ser sobreyectiva, y ninguna fórmula que mezcle ingenuamente $f$ y $g$ define una aplicación: todo el contenido está en la partición de $E$ en la región $C$ (donde se copia $f$ ) y su complementario (donde se recorre $g$ hacia atrás).

10. (a) La inclusión $\intoo01 \to \intcc01$ es inyectiva; y $x \mapsto \frac{x + 1}3$ envía $\intcc01$ de forma inyectiva dentro de $\intcc{\frac13}{\frac23} \subseteq \intoo01$ (es afín con pendiente no nula). Por la pregunta 9, $\intcc01 \approx \intoo01$ — una biyección bastante desagradable de escribir explícitamente. (b) Inyectividad. Supongamos $2^p(2q + 1) = 2^{p'}(2q' + 1)$ con, digamos, $p \leq p'$ . Dividiendo por $2^p$ : $2q + 1 = 2^{p' - p}(2q' + 1)$ . Si $p' > p$ , el miembro derecho es par y el izquierdo impar — imposible; luego $p = p'$ , y entonces $2q + 1 = 2q' + 1$ y $q = q'$ . Sobreyectividad. Veamos por inducción fuerte que todo entero $m \geq 1$ es de la forma $2^p(2q + 1)$ . Para $m = 1$ : $p = q = 0$ . Sea $m \geq 1$ y supóngase la afirmación para todos los enteros de $\intint1m$ . Si $m + 1$ es impar, $m + 1 = 2q + 1$ con $p = 0$ . Si $m + 1$ es par, $m + 1 = 2m'$ con $1 \leq m' \leq m$ ; por hipótesis $m' = 2^p(2q + 1)$ , luego $m + 1 = 2^{p+1}(2q + 1)$ . Así pues, $\varphi(p, q) = 2^p(2q + 1) - 1$ alcanza todo $n \in \N$ , y $\varphi$ es una biyección $\N \times \N \to \N$ .

11. Como $A$ es infinito, $A \setminus \{\varphi(0), \dots, \varphi(n - 1)\}$ nunca es vacío, y la propiedad del elemento mínimo de $\N$ (usada para demostrar el Teorema 1.12) legitima la definición por recurrencia. Estrictamente creciente: $\varphi(n + 1)$ pertenece a $A \setminus \{\varphi(0), \dots, \varphi(n)\} \subseteq A \setminus \{\varphi(0), \dots, \varphi(n - 1)\}$ , cuyo mínimo es $\varphi(n)$ ; luego $\varphi(n + 1) \geq \varphi(n)$ , y la igualdad queda excluida, de donde $\varphi(n+1) > \varphi(n)$ . $\varphi(n) \geq n$ : por inducción, $\varphi(0) \geq 0$ y $\varphi(n + 1) \geq \varphi(n) + 1 \geq n + 1$ . La inyectividad se sigue de la monotonía estricta. Sobreyectividad sobre $A$ : supongamos que algún $a \in A$ no se alcanza nunca. Como $\varphi(a + 1) \geq a + 1 > a$ , el conjunto de los $n$ con $\varphi(n) > a$ no es vacío; sea $n$ su mínimo. Para todo $k < n$ se tiene $\varphi(k) \leq a$ , luego $\varphi(k) < a$ ( $a$ no se alcanza). Entonces $a$ está en $A \setminus \{\varphi(0), \dots, \varphi(n - 1)\}$ y $a < \varphi(n)$ , lo que contradice la minimalidad que define $\varphi(n)$ . Así pues, $\varphi$ es una biyección $\N \to A$ , y $A$ es numerable.

12. Sea $E \preceq \N$ mediante una inyección $f$ ; entonces $E \approx f(E)$ (pregunta 2). Si $f(E)$ es finito, $E$ es finito; si $f(E)$ es infinito, la pregunta 11 da $f(E) \approx \N$ , luego $E \approx \N$ por transitividad (pregunta 1). Recíprocamente, los conjuntos finitos y los conjuntos numerables se inyectan obviamente en $\N$ . El atajo: $E \preceq \N$ y $\N \preceq E$ dan $E \approx \N$ directamente por Cantor–Schröder–Bernstein — sin necesidad de ningún argumento de enumeración.

13. Sean $f \colon E \to \N$ y $g \colon F \to \N$ inyecciones. Entonces $(x, y) \mapsto \varphi\bigl(f(x), g(y)\bigr)$ es una inyección $E \times F \to \N$ : si las imágenes coinciden, la inyectividad de $\varphi$ (pregunta 10) da $f(x) = f(x')$ y $g(y) = g(y')$ , y luego $x = x'$ , $y = y'$ . Para $\Z \times \N^*$ : los dos factores son numerables (pregunta 4), luego $\Z \times \N^* \preceq \N$ ; es infinito (contiene $\{0\} \times \N^*$ ) y, por tanto, numerable por la pregunta 12.

14. Todo racional $r$ tiene una única representación $r = p/q$ con $p \in \Z$ , $q \in \N^*$ y la fracción irreducible (la unicidad se demuestra en el Capítulo 6; para $r = 0$ tómese $0/1$ ). La aplicación $r \mapsto (p, q)$ es entonces inyectiva: el par determina $r = p/q$ . Por tanto $\Q \preceq \Z \times \N^* \preceq \N$ por la pregunta 13. Como $\N \subseteq \Q$ da $\N \preceq \Q$ , la pregunta 12 (o directamente Cantor–Schröder–Bernstein) muestra que $\Q \approx \N$ : los racionales son numerables.

15. Para cada $n$ , fíjese una inyección $f_n \colon E_n \to \N$ . Para $x \in \bigcup_n E_n$ , sea $n(x)$ el menor $n$ con $x \in E_n$ , y póngase $u(x) = \varphi\bigl(n(x), f_{n(x)}(x)\bigr) \in \N$ . Si $u(x) = u(x')$ , la inyectividad de $\varphi$ da $n(x) = n(x') = n$ y $f_n(x) = f_n(x')$ , luego $x = x'$ por inyectividad de $f_n$ . Así, la unión se inyecta en $\N$ : es a lo sumo numerable.

16. Sea $\Psi(F) = \sum_{i \in F} 2^i$ para $F \subseteq \N$ finito ( $\Psi(\emptyset) = 0$ ). Supongamos $F \neq F'$ y sea $m$ el mayor elemento en el que difieren, digamos $m \in F \setminus F'$ (intercámbiense los nombres si hace falta). Los elementos $> m$ pertenecen a los dos o a ninguno, luego contribuyen igual a las dos sumas; comparando las contribuciones de los elementos $\leq m$ :

\sum_{i \in F,\, i \leq m} 2^i \geq 2^m > 2^m - 1 = \sum_{k=0}^{m-1} 2^k \geq \sum_{i \in F',\, i \leq m} 2^i ,

usando la suma geométrica del Ejercicio 1.4. Por tanto $\Psi(F) \neq \Psi(F')$ : $\Psi$ es inyectiva y el conjunto de los subconjuntos finitos de $\N$ es a lo sumo numerable; es infinito (contiene todos los conjuntos unitarios) y, por tanto, numerable.

17. Envíese $A \subseteq \N$ a su indicadora $\mathbf 1_A \colon \N \to \{0,1\}$ , $\mathbf 1_A(n) = 1$ si $n \in A$ y $0$ en caso contrario; envíese $u \in \{0,1\}^{\N}$ a $A_u = \{n \in \N : u(n) = 1\}$ . Las dos aplicaciones son mutuamente inversas: $A_{\mathbf 1_A} = A$ y $\mathbf 1_{A_u} = u$ (compruébese el valor en cada $n$ ). Por el Teorema 1.24, cada una es una biyección: $\mathcal{P}(\N) \approx \{0,1\}^{\N}$ .

18. Para todo $n$ , $d(n) = 1 - \Phi(n)(n) \neq \Phi(n)(n)$ , de modo que las sucesiones $d$ y $\Phi(n)$ difieren en el índice $n$ : $d \neq \Phi(n)$ . Por tanto ningún $\Phi$ es sobreyectiva, y por la pregunta 3 tampoco hay ninguna inyección $\{0,1\}^{\N} \to \N$ : $\{0,1\}^{\N}$ no es a lo sumo numerable. A través del diccionario de la pregunta 17, una aplicación $\Phi \colon \N \to \{0,1\}^{\N}$ es una aplicación $f \colon \N \to \mathcal{P}(\N)$ , y $d$ corresponde al conjunto $D = \{n : n \notin f(n)\}$ (en efecto, $d(n) = 1 \iff \Phi(n)(n) = 0 \iff n \notin f(n)$ ): el argumento diagonal es la demostración de Cantor del Ejercicio 1.11 para $E = \N$ .

19. Escríbase $x_n = 0.d_1(n)\,d_2(n)\,d_3(n)\dots$ en forma propia y defínase $\delta_n = 5$ si $d_n(n) \neq 5$ , y $\delta_n = 6$ si $d_n(n) = 5$ ; póngase $x = 0.\delta_1\delta_2\delta_3\dots$ Este desarrollo solo usa las cifras $5$ y $6$ , luego no termina en una sucesión de $9$ : es el desarrollo propio de un real $x \in \intco01$ . Para cada $n$ , las cifras $n$ -ésimas de $x$ y de $x_n$ difieren ( $\delta_n \neq d_n(n)$ por construcción); como los desarrollos propios son únicos, $x \neq x_n$ . Así pues, ninguna sucesión agota $\intco01$ : de nuevo por la pregunta 3, $\intco01$ no es a lo sumo numerable.

20. $\intco01 \subseteq \R$ , luego una inyección $\R \to \N$ se restringiría a una de $\intco01$ , en contra de la pregunta 19: $\R$ no es numerable. Si $\R \setminus \Q$ fuese a lo sumo numerable, entonces $\R = \Q \cup (\R \setminus \Q)$ sería una unión de dos conjuntos numerables a lo sumo y, por tanto, a lo sumo numerable por la pregunta 15 (tómese $E_0 = \Q$ , $E_n = \R \setminus \Q$ para $n \geq 1$ ) — contradicción. Luego los irracionales no son numerables. Con precisión: dentro de $\R$ , los racionales forman un conjunto numerable mientras que su complementario no lo es; ninguna biyección podrá jamás emparejar $\R \setminus \Q$ con $\Q$ — hay estrictamente «más» irracionales que racionales, aunque los dos conjuntos sean infinitos y los dos sean densos.

21. $p/q$ (con $q \neq 0$ ) es raíz de $qX - p$ , un polinomio no nulo con coeficientes enteros. $\sqrt 2$ es raíz de $X^2 - 2$ . Para $x = \sqrt 2 + \sqrt 3$ : $x^2 = 5 + 2\sqrt 6$ , luego $x^2 - 5 = 2\sqrt 6$ y $(x^2 - 5)^2 = 24$ , es decir,

x^4 - 10x^2 + 1 = 0 :

$\sqrt 2 + \sqrt 3$ es raíz de $X^4 - 10X^2 + 1$ .

22. Envíese $P = a_0 + a_1X + \dots + a_nX^n$ (de grado $\leq n$ y coeficientes enteros) a $(a_0, \dots, a_n) \in \Z^{n+1}$ : es inyectiva, pues un polinomio queda determinado por sus coeficientes. Por inducción sobre $n$ : $\Z^1 = \Z$ es numerable (pregunta 4), y $\Z^{n+2} \approx \Z^{n+1} \times \Z$ es a lo sumo numerable por la pregunta 13. Así pues, cada conjunto de polinomios enteros de grado acotado es a lo sumo numerable; es infinito (contiene las constantes) y, por tanto, numerable por la pregunta 12.

23. El conjunto de todos los polinomios enteros es

\bigcup_{n \in \N} \{P : \deg P \leq n,\ P \text{ con coeficientes enteros}\},

una unión numerable de conjuntos numerables: a lo sumo numerable por la pregunta 15, e infinito, luego numerable.

24. Para cada polinomio entero no nulo $P$ , el conjunto de raíces $R_P = \{x \in \R : P(x) = 0\}$ es finito (a lo sumo $\deg P$ elementos, admitido). Por la pregunta 23, los polinomios enteros no nulos se pueden enumerar $P_0, P_1, P_2, \dots$ ; entonces $\mathcal{A} = \bigcup_{n \in \N} R_{P_n}$ es una unión numerable de conjuntos finitos (y por tanto a lo sumo numerables): a lo sumo numerable por la pregunta 15. Contiene a $\Q$ (pregunta 21), luego es infinito: $\mathcal{A}$ es numerable.

25. Si $\R \setminus \mathcal{A}$ fuese a lo sumo numerable, $\R = \mathcal{A} \cup (\R \setminus \mathcal{A})$ sería a lo sumo numerable (pregunta 15), en contra de la pregunta 20. Por tanto existen números trascendentes y forman incluso un conjunto no numerable, mientras que los números algebraicos — entre los que está todo número construido a partir de enteros mediante radicales — forman un mero esqueleto numerable dentro de $\R$ . Resumen de la arquitectura: las preguntas 1–3 montan el lenguaje de la comparación; Cantor–Schröder–Bernstein (preguntas 5–9) permite demostrar la equipotencia con dos inyecciones fáciles en lugar de una biyección ingeniosa, y se usó para $\intcc01 \approx \intoo01$ , para $\Q$ y a lo largo de toda la parte V; la biyección de emparejamiento (pregunta 10) puso en marcha los productos y las uniones numerables (preguntas 13 y 15), que a su vez pusieron en marcha $\Q$ , los polinomios enteros y $\mathcal{A}$ ; el argumento diagonal (preguntas 18–19) proporcionó la única desigualdad estricta $\N \prec \R$ que hace no trivial toda la historia. La conclusión de Cantor es filosóficamente llamativa: la demostración no exhibe ni un solo número trascendente y, sin embargo, prueba que, en el sentido de la equipotencia, casi todo número real es trascendente. Nombrar un trascendente concreto — $\pi$ o $\eu$ — exigió matemáticas completamente distintas y décadas más de trabajo.

Términos definidos en este capítulo

Ver los 395 términos del glosario