---
title: "Lógica, conjuntos y aplicaciones"
book: "Matemáticas universitarias — Grado 1"
subject: math
language: es
chapter: 1
exercises: 12
source: https://one-course.com/books/math/3/es/chapter/1-logica-conjuntos-y-aplicaciones
---

# Capítulo 1 — Ló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](#def-b1-logic-statement) matemático, cómo los conectivos y los cuantificadores combinan [enunciados](#def-b1-logic-statement), 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](#def-b1-logic-sets) 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](#def-b1-logic-statement) $P$, $Q$, $R$:

1. $\lnot(\lnot P) \iff P$ ;
2. 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)$ ;
3. $(P \implies Q) \iff \bigl((\lnot P) \lor Q\bigr)$ , de donde $\lnot(P \implies Q) \iff P \land (\lnot Q)$ ;
4. contraposición: $(P \implies Q) \iff \bigl((\lnot Q) \implies (\lnot P)\bigr)$ ;
5. $(P \iff Q) \iff \bigl((P \implies Q) \land (Q \implies  P)\bigr)$ ;
6. 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](#def-b1-logic-statement) 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](#def-b1-logic-sets) $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](#def-b1-logic-sets) $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](#def-b1-logic-statement) universal falla. Para la segunda regla: «ningún $x$ satisface $P$» significa que el [conjunto](#def-b1-logic-sets) $\{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](#ex-b1-logic-limit): 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](#prop-b1-logic-negquant) 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](#def-b1-logic-statement) 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](#def-b1-logic-order) 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](#def-b1-logic-statement), $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](https://one-course.com/books/math/3/es/chapter/11-sucesiones#ch-b1-seq) 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](#prop-b1-logic-negquant), 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…

1. *una implicación $P \implies Q$ directamente* : se supone $P$ y se deduce $Q$ ;
2. *por contraposición* : se supone $\lnot Q$ y se deduce $\lnot P$ — válido por la [Proposición 1.3](#prop-b1-logic-rules) (4);
3. *por reducción al absurdo* : se supone que el [enunciado](#def-b1-logic-statement) es falso y se deriva una contradicción;
4. *una equivalencia* : se demuestran las dos implicaciones por separado (o se encadenan equivalencias conocidas);
5. *un [enunciado](#def-b1-logic-statement) «para todo»* : se toma un $x$ *arbitrario* de $E$ («sea $x \in E$ ») y se demuestra $P(x)$ ;
6. *un [enunciado](#def-b1-logic-statement) «existe»* : se exhibe un testigo, o se demuestra la existencia de forma indirecta;
7. *por inducción* : véase el [Teorema 1.12](#thm-b1-logic-induction) .

Al demostrar un [enunciado](#def-b1-logic-statement) 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.

1. *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.
2. *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.
3. *Demostraciones hacia atrás.* Partir de la conclusión deseada y deducir un [enunciado](#def-b1-logic-statement) 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.
4. *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

1. $P(0)$ es verdadera, y
2. 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](#def-b1-logic-statement) $\exists!\,x,\ P(x)$ son *dos* [enunciados](#def-b1-logic-statement), 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](https://one-course.com/books/math/3/es/chapter/6-aritmetica-de-los-enteros#ch-b1-arith)). 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](#def-b1-logic-statement) $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](#def-b1-logic-sets) de [conjuntos](#def-b1-logic-sets) son [conjuntos](#def-b1-logic-sets) ordinarios, y el [Capítulo 2](https://one-course.com/books/math/3/es/chapter/2-combinatoria#ch-b1-counting) 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](#exo-b1-logic-11) y [1.12](#exo-b1-logic-12).

**Proposición 1.18 (Álgebra de conjuntos).**

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

1. $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)$ ;
2. De Morgan: $\overline{A \cup B} = \overline{A} \cap  \overline{B}$ y $\overline{A \cap B} = \overline{A} \cup  \overline{B}$ ;
3. $A \subseteq B \iff \overline{B} \subseteq \overline{A}$ .

**Demostración.** Cada identidad traduce una regla de la [Proposición 1.3](#prop-b1-logic-rules) mediante el diccionario ($\in A$ o no) $\leftrightarrow$ ([enunciado](#def-b1-logic-statement) 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](#prop-b1-logic-rules) (6), y el último [enunciado](#def-b1-logic-statement) 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 .](https://one-course.com/images/onecourse/chapters/math-3/b1-logic/fig-5465323f1d10.svg)

*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](#prop-b1-logic-setalgebra).*

## 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](#def-b1-logic-sets) $E$ (el *dominio*) exactamente un elemento $f(x)$ del [conjunto](#def-b1-logic-sets) $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](#def-b1-logic-map) 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](#exo-b1-logic-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](#def-b1-logic-map) 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](#def-b1-logic-map) $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](#def-b1-logic-map) .

**Teorema 1.24 (Aplicación inversa).**

Una [aplicación](#def-b1-logic-map) $f \colon E \to F$ es [biyectiva](#def-b1-logic-inj) si y solo si existe una [aplicación](#def-b1-logic-map) $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](#def-b1-logic-inj), con $(f^{-1})^{-1} = f$.

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

($\Leftarrow$) Supongamos que existe tal $g$. Si $f(x) = f(x')$, aplicando $g$ se obtiene $x = x'$: $f$ es [inyectiva](#def-b1-logic-inj). Para $y \in F$, $x = g(y)$ cumple $f(x) = y$: $f$ es [sobreyectiva](#def-b1-logic-inj).

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](#def-b1-logic-inj) 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](#def-b1-logic-inj), 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](#thm-b1-logic-inverse). 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](#def-b1-logic-inj) 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$.

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

**Demostración.** (1) Si $g(f(x)) = g(f(x'))$, la [inyectividad](#def-b1-logic-inj) de $g$ da $f(x) = f(x')$, y la de $f$ da entonces $x = x'$. Si $z \in G$, la [sobreyectividad](#def-b1-logic-inj) 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](#def-b1-logic-inj) 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](#thm-b1-logic-inverse) concluye.

(2) Si $f(x) = f(x')$, entonces $g(f(x)) = g(f(x'))$, y la [inyectividad](#def-b1-logic-inj) de $g \circ f$ da $x = x'$. Si $z \in G$, la [sobreyectividad](#def-b1-logic-inj) 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](#prop-b1-logic-comp) (2) no se pueden reforzar las conclusiones: que $g \circ f$ sea [biyectiva](#def-b1-logic-inj) *no* obliga a que $f$ sea [sobreyectiva](#def-b1-logic-inj) ni a que $g$ sea [inyectiva](#def-b1-logic-inj). 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](#def-b1-logic-inj), 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](#def-b1-logic-map) *interior* para la [inyectividad](#def-b1-logic-inj) y a la *exterior* para la [sobreyectividad](#def-b1-logic-inj), nunca al revés. (El [Ejercicio 1.9](#exo-b1-logic-9) construye el mismo fenómeno con [conjuntos](#def-b1-logic-sets) infinitos, donde es el motor de las inversas laterales.)

**Ejemplo 1.28.**

$f \colon \R \to \R$, $x \mapsto x^2$ no es [inyectiva](#def-b1-logic-inj) ($f(-1) =
f(1)$) ni [sobreyectiva](#def-b1-logic-inj) ($-1$ no tiene [imagen recíproca](#def-b1-logic-map)). Restringiendo el dominio y el codominio, $f \colon \R_+ \to \R_+$, $x \mapsto x^2$ sí es [biyectiva](#def-b1-logic-inj), con inversa $y \mapsto \sqrt y$. Que una [aplicación](#def-b1-logic-map) sea [inyectiva](#def-b1-logic-inj) o [sobreyectiva](#def-b1-logic-inj) 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](#def-b1-logic-sets) $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](#def-b1-logic-equiv), 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](#thm-b1-logic-partition) 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](#def-b1-logic-equiv) en $E$. Entonces las [clases de equivalencia](#def-b1-logic-equiv) 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](#thm-b1-logic-partition) de $E$ proviene de este modo de exactamente una [relación de equivalencia](#def-b1-logic-equiv) («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](#thm-b1-logic-partition) 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](#def-b1-logic-equiv) 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](#def-b1-logic-equiv); sus clases son los $n$ [conjuntos](#def-b1-logic-sets) 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](https://one-course.com/books/math/3/es/chapter/7-estructuras-algebraicas#ch-b1-structures).

**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](https://one-course.com/books/math/3/es/chapter/10-numeros-reales#ch-b1-reals).

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

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](#def-b1-logic-order) producto*). Es un [orden](#def-b1-logic-order) — 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](#def-b1-logic-order) lexicográfico*). La transitividad exige distinguir dos casos, pero se cumple, y ahora dos pares cualesquiera son comparables: el [orden](#def-b1-logic-order) es total. Los dos órdenes ordenan el mismo [conjunto](#def-b1-logic-sets) de manera distinta — $(0, 100) \preceq_{\mathrm{lex}} (1, 0)$ aunque el [orden](#def-b1-logic-order) producto no diga nada — lo que recuerda que un [orden](#def-b1-logic-order) es una estructura que se *elige*, no una propiedad del [conjunto](#def-b1-logic-sets). 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](#def-b1-logic-sets) finitos se convierte en el cálculo combinatorio del [Capítulo 2](https://one-course.com/books/math/3/es/chapter/2-combinatoria#ch-b1-counting), donde toda fórmula es en secreto una [biyección](#def-b1-logic-inj); para los [conjuntos](#def-b1-logic-sets) 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](https://one-course.com/books/math/3/es/chapter/11-sucesiones#ch-b1-seq)) no son otra cosa que aplicaciones $\N \to \R$, de modo que los [enunciados](#def-b1-logic-statement) sobre sucesiones son [enunciados](#def-b1-logic-statement) sobre un [conjunto](#def-b1-logic-sets) 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](https://one-course.com/books/math/3/es/chapter/19-dimension-finita#ch-b1-findim)). Siempre que aparece una nueva «igualdad» — equipotencia, isomorfismo de grupos ([Capítulo 7](https://one-course.com/books/math/3/es/chapter/7-estructuras-algebraicas#ch-b1-structures)), isomorfismo lineal — se repite el patrón del [Teorema 1.24](#thm-b1-logic-inverse): la igualdad es una [aplicación](#def-b1-logic-map) 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](#ex-b1-logic-limit) es el pan de cada día de los Capítulos [11](https://one-course.com/books/math/3/es/chapter/11-sucesiones#ch-b1-seq) y [13](https://one-course.com/books/math/3/es/chapter/13-limites-y-continuidad#ch-b1-continuity): toda demostración de un límite es una partida jugada contra un $\varepsilon$ arbitrario. Las [clases de equivalencia](#def-b1-logic-equiv) reaparecen como las clases de congruencia de $\Z/n\Z$ en el [Capítulo 7](https://one-course.com/books/math/3/es/chapter/7-estructuras-algebraicas#ch-b1-structures), donde la [partición](#thm-b1-logic-partition) del [Teorema 1.31](#thm-b1-logic-partition) adquiere una estructura algebraica propia. Las relaciones de [orden](#def-b1-logic-order), las cotas superiores y los extremos superiores se convierten en el corazón axiomático de $\R$ en el [Capítulo 10](https://one-course.com/books/math/3/es/chapter/10-numeros-reales#ch-b1-reals). Las inyecciones, sobreyecciones y biyecciones vuelven como las aplicaciones lineales del [Capítulo 20](https://one-course.com/books/math/3/es/chapter/20-aplicaciones-lineales#ch-b1-linmaps), donde la [inyectividad](#def-b1-logic-inj) 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](#def-b1-logic-inj) en una teoría de los *tamaños de los [conjuntos](#def-b1-logic-sets) infinitos*, cuyas conclusiones (numerabilidad de $\Q$, no numerabilidad de $\R$) reaparecen en los Capítulos [10](https://one-course.com/books/math/3/es/chapter/10-numeros-reales#ch-b1-reals) y [12](https://one-course.com/books/math/3/es/chapter/12-topologia-de-la-recta-real#ch-b1-topology).

## 1.7 Ejercicios

**Ejercicio 1.1 ★.**

Escríbase la negación de cada [enunciado](#def-b1-logic-statement) sin emplear la palabra «no»:

1. $\forall x \in \R,\ \exists y \in \R,\ x + y > 0$ ;
2. $\exists x \in \R,\ \forall y \in \R,\ xy = 0$ ;
3. $\forall \varepsilon > 0,\ \exists \delta > 0,\ \forall x \in  \R,\ \abs{x} \leq \delta \implies \abs{f(x)} \leq \varepsilon$ (para una [aplicación](#def-b1-logic-map) fija $f \colon \R \to \R$ ).

Decídase después si los [enunciados](#def-b1-logic-statement) (1) y (2) son verdaderos.

**Solución de Ejercicio 1.1.**

Negaciones, haciendo pasar $\lnot$ a través de cada cuantificador ([Proposición 1.5](#prop-b1-logic-negquant)) y usando $\lnot(P \implies Q) \iff
P \land \lnot Q$:

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

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

**Ejercicio 1.2 ★.**

Sean $P, Q$ dos [enunciados](#def-b1-logic-statement). 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 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](#def-b1-logic-statement) falso, dicho sea de paso: la implicación de partida es verdadera, véase el [Capítulo 14](https://one-course.com/books/math/3/es/chapter/14-derivacion#ch-b1-derivative)).

**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 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](#def-b1-logic-statement).

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

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

**Solución de Ejercicio 1.4.**

1. 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 .$$
2. 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](#def-b1-logic-sets) 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 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:

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

**Solución de Ejercicio 1.6.**

1. $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}$ .
2. Usando (1) y la distributividad ( [Proposición 1.18](#prop-b1-logic-setalgebra) ): $(A \cup B) \cap \overline{C} = (A \cap \overline{C}) \cup  (B \cap \overline{C})$ .
3. 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](#def-b1-logic-map) es [inyectiva](#def-b1-logic-inj), [sobreyectiva](#def-b1-logic-inj) o [biyectiva](#def-b1-logic-inj):

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

Para $h$, ajústese el codominio para hacerla [biyectiva](#def-b1-logic-inj) y calcúlese la inversa.

**Solución de Ejercicio 1.7.**

1. $f$ es [inyectiva](#def-b1-logic-inj) ( $n + 1 = m + 1 \implies n = m$ ) pero no [sobreyectiva](#def-b1-logic-inj) : $0$ no tiene [imagen recíproca](#def-b1-logic-map) en $\N$ .
2. $g$ es [biyectiva](#def-b1-logic-inj) : $n \mapsto n - 1$ es una inversa por los dos lados en $\Z$ .
3. $h$ es [inyectiva](#def-b1-logic-inj) : $\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](#def-b1-logic-inj) 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](#def-b1-logic-map) $x = \frac{y+1}{y-1}$ , de modo que $h \colon \R \setminus \{1\} \to \R \setminus \{1\}$ es [biyectiva](#def-b1-logic-inj) 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$.

1. 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')$ .
2. 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.
3. Demuéstrese que $f$ es [inyectiva](#def-b1-logic-inj) si y solo si $f(A \cap A') =  f(A) \cap f(A')$ para todos $A, A'$ .

**Solución de Ejercicio 1.8.**

1. $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')$ .
2. 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\}$ .
3. ( $\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](#def-b1-logic-inj) . ( $\Rightarrow$ ) Sea $f$ [inyectiva](#def-b1-logic-inj) e $y \in f(A) \cap f(A')$ : $y = f(x) = f(x')$ con $x \in A$ , $x' \in A'$ ; la [inyectividad](#def-b1-logic-inj) 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](#def-b1-logic-inj) y $g$ es [sobreyectiva](#def-b1-logic-inj). Dese un ejemplo en el que ni $f$ ni $g$ sea [biyectiva](#def-b1-logic-inj).

**Solución de Ejercicio 1.9.**

$g \circ f = \mathrm{id}_E$ es [inyectiva](#def-b1-logic-inj) y [sobreyectiva](#def-b1-logic-inj), luego, por la [Proposición 1.26](#prop-b1-logic-comp) (2), $f$ es [inyectiva](#def-b1-logic-inj) y $g$ es [sobreyectiva](#def-b1-logic-inj). 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](#def-b1-logic-inj) y $g$ no es [inyectiva](#def-b1-logic-inj).

**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](#def-b1-logic-equiv) y descríbase la [clase de equivalencia](#def-b1-logic-equiv) de cada real $x$. ¿Qué clases tienen exactamente un elemento?

**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](#def-b1-logic-equiv) 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](#def-b1-logic-sets). Demuéstrese que no hay ninguna [sobreyección](#def-b1-logic-inj) 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 de Ejercicio 1.11.**

Sea $f \colon E \to \mathcal{P}(E)$ una [aplicación](#def-b1-logic-map) 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](#def-b1-logic-inj). (En particular, ningún [conjunto](#def-b1-logic-sets) está en [biyección](#def-b1-logic-inj) con su [conjunto de las partes](#def-b1-logic-sets): hay «más» subconjuntos de $\N$ que enteros.)

**Ejercicio 1.12 ★★★.**

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

1. Demuéstrese que $f$ es [sobreyectiva](#def-b1-logic-inj) si y solo si $\Phi$ es [inyectiva](#def-b1-logic-inj) .
2. Demuéstrese que $f$ es [inyectiva](#def-b1-logic-inj) si y solo si $\Phi$ es [sobreyectiva](#def-b1-logic-inj) .

**Solución de Ejercicio 1.12.**

1. ( $\Rightarrow$ ) Sea $f$ [sobreyectiva](#def-b1-logic-inj) 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](#def-b1-logic-inj) . ( $\Leftarrow$ ) Si $f$ no es [sobreyectiva](#def-b1-logic-inj) , 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](#def-b1-logic-inj) .
2. ( $\Rightarrow$ ) Sea $f$ [inyectiva](#def-b1-logic-inj) y $A \subseteq E$ . Póngase $B = f(A)$ ; entonces $f^{-1}(B) = \{x : f(x) \in f(A)\}$ , y la [inyectividad](#def-b1-logic-inj) da $f(x) \in f(A) \iff x \in A$ , luego $\Phi(B) =  A$ : $\Phi$ es [sobreyectiva](#def-b1-logic-inj) . ( $\Leftarrow$ ) Si $f$ no es [inyectiva](#def-b1-logic-inj) , tómense $x \neq x'$ con $f(x) = f(x')$ . Todo [conjunto](#def-b1-logic-sets) [imagen recíproca](#def-b1-logic-map) $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](#def-b1-logic-inj) .

## 1.8 Problema: comparar infinitos

**Problema 1.1.**

¿Cuándo tienen dos [conjuntos](#def-b1-logic-sets) «el mismo número de elementos»? La respuesta de Cantor — cuando existe una [biyección](#def-b1-logic-inj) entre ellos — resulta ser utilizable incluso para [conjuntos](#def-b1-logic-sets) 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](#def-b1-logic-inj)), 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](#pb-b1-logic-1), y en cantidad masiva*, sin exhibir ni uno solo. En todo el problema, para [conjuntos](#def-b1-logic-sets) $E$ y $F$, se escribe $E \preceq F$ cuando existe una [inyección](#def-b1-logic-inj) de $E$ en $F$, y $E \approx F$ («$E$ y $F$ son *equipotentes*») cuando existe una [biyección](#def-b1-logic-inj) de $E$ sobre $F$.

**Parte I — El vocabulario de la comparación.**

1. Pruébese que $\approx$ se comporta como una [relación de equivalencia](#def-b1-logic-equiv) : $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](#thm-b1-logic-inverse) y la [Proposición 1.26](#prop-b1-logic-comp) .)
2. Pruébese que $\preceq$ es transitiva y que una [inyección](#def-b1-logic-inj) $f \colon E \to F$ induce siempre $E \approx f(E)$ .
3. Sea $E \neq \emptyset$ . Pruébese que $E \preceq F$ si y solo si existe una [sobreyección](#def-b1-logic-inj) de $F$ sobre $E$ .
4. Compruébese que $n \mapsto n + 1$ es una [biyección](#def-b1-logic-inj) 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](#def-b1-logic-inj) 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](#def-b1-logic-map) que envía $x \in C$ a $f(x)$, y $x \notin C$ al único $y \in F$ tal que $g(y) = x$.

5. 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.
6. 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](#exo-b1-logic-8) .)
7. Pruébese que $h$ es [inyectiva](#def-b1-logic-inj) . (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$ .)
8. Pruébese que $h$ es [sobreyectiva](#def-b1-logic-inj) : 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](#def-b1-logic-map) de $y$ en cada caso.
9. 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](#def-b1-logic-statement) no sea trivial.
10. 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](#def-b1-logic-inj) de $\N \times \N$ sobre $\N$ — la [inyectividad](#def-b1-logic-inj) por un argumento de paridad, la [sobreyectividad](#def-b1-logic-inj) por inducción fuerte ( [Teorema 1.12](#thm-b1-logic-induction) ). Así pues, $\N \times \N \approx  \N$ : el plano de los puntos enteros no es mayor que la recta.

**Parte III — [Conjuntos numerables](#pb-b1-logic-1).** Un [conjunto](#def-b1-logic-sets) $E$ se llama *a lo sumo numerable* cuando $E \preceq \N$, y *numerable* cuando $E \approx \N$.

11. 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$ .)
12. Dedúzcase que un [conjunto](#def-b1-logic-sets) 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.
13. 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.
14. 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](https://one-course.com/books/math/3/es/chapter/6-aritmetica-de-los-enteros#ch-b1-arith) ; aplíquese después la pregunta 12.)
15. Pruébese que una unión numerable de [conjuntos numerables](#pb-b1-logic-1) 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$ .)
16. Pruébese que el [conjunto](#def-b1-logic-sets) 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](#def-b1-logic-inj) comparando el mayor elemento en el que difieren dos [conjuntos](#def-b1-logic-sets) finitos, con ayuda de $\sum_{k=0}^{m-1} 2^k = 2^m - 1$ del [Ejercicio 1.4](#exo-b1-logic-4) .)

**Parte IV — Diagonalización.** Denótese por $\{0,1\}^{\N}$ el [conjunto](#def-b1-logic-sets) de todas las aplicaciones $u \colon \N \to \{0, 1\}$, es decir, el [conjunto](#def-b1-logic-sets) de las sucesiones binarias.

17. Constrúyase una [biyección](#def-b1-logic-inj) entre $\mathcal{P}(\N)$ y $\{0,1\}^{\N}$ (funciones indicadoras).
18. (El argumento diagonal) Sea $\Phi \colon \N \to  \{0,1\}^{\N}$ una [aplicación](#def-b1-logic-map) 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](#exo-b1-logic-11) ) para $E = \N$ .
19. Admítase — como es familiar desde la secundaria y se establece con rigor en el [Capítulo 10](https://one-course.com/books/math/3/es/chapter/10-numeros-reales#ch-b1-reals) — 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.
20. Dedúzcase que $\R$ no es numerable, y que el [conjunto](#def-b1-logic-sets) $\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](#pb-b1-logic-1).** 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](https://one-course.com/books/math/3/es/chapter/8-polinomios#ch-b1-poly) — que un polinomio no nulo de grado $n$ tiene a lo sumo $n$ raíces reales.

21. 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$ .
22. Para $n \in \N$ fijo, pruébese que el [conjunto](#def-b1-logic-sets) 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.)
23. Dedúzcase que el [conjunto](#def-b1-logic-sets) de *todos* los polinomios con coeficientes enteros es numerable.
24. Demuéstrese el *teorema de Cantor sobre los [números algebraicos](#pb-b1-logic-1)* : el [conjunto](#def-b1-logic-sets) $\mathcal{A}$ de los números reales algebraicos es numerable.
25. Conclúyase: existen números reales trascendentes, y el [conjunto](#def-b1-logic-sets) de los [números trascendentes](#pb-b1-logic-1) 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](#pb-b1-logic-1) 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 de Problema 1.1.**

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

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

**3.** ($\Rightarrow$) Sea $f \colon E \to F$ [inyectiva](#def-b1-logic-inj) 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](#def-b1-logic-inj)), 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](#def-b1-logic-inj). ($\Leftarrow$) Sea $s \colon F \to E$ [sobreyectiva](#def-b1-logic-inj). 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](#def-b1-logic-inj).

**4.** $n \mapsto n + 1$ envía $\N$ dentro de $\N^*$, es [inyectiva](#def-b1-logic-inj) ($n + 1 = m + 1 \implies n = m$) y [sobreyectiva](#def-b1-logic-inj) (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](#def-b1-logic-inj): 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](#def-b1-logic-inj): $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](#def-b1-logic-inj) 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](#exo-b1-logic-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](#def-b1-logic-inj) 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](#def-b1-logic-inj).

**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](#def-b1-logic-map). *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](#def-b1-logic-inj) 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](#def-b1-logic-inj) y, por tanto, [biyectiva](#def-b1-logic-inj).

**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](#def-b1-logic-inj) $h \colon E \to F$, luego $E \approx F$. El [enunciado](#def-b1-logic-statement) no es trivial porque las dos inyecciones dadas no guardan relación alguna — ninguna tiene por qué ser [sobreyectiva](#def-b1-logic-inj), y ninguna fórmula que mezcle ingenuamente $f$ y $g$ define una [aplicación](#def-b1-logic-map): todo el contenido está en la [partición](#thm-b1-logic-partition) 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](#def-b1-logic-inj); y $x \mapsto \frac{x + 1}3$ envía $\intcc01$ de forma [inyectiva](#def-b1-logic-inj) dentro de $\intcc{\frac13}{\frac23} \subseteq \intoo01$ (es afín con pendiente no nula). Por la pregunta 9, $\intcc01 \approx \intoo01$ — una [biyección](#def-b1-logic-inj) bastante desagradable de escribir explícitamente. (b) *[Inyectividad](#def-b1-logic-inj).* 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](#def-b1-logic-inj).* 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](#def-b1-logic-inj) $\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](#thm-b1-logic-induction)) 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](#def-b1-logic-inj)* se sigue de la monotonía estricta. *[Sobreyectividad](#def-b1-logic-inj) sobre $A$:* supongamos que algún $a \in A$ no se alcanza nunca. Como $\varphi(a + 1) \geq a + 1 > a$, el [conjunto](#def-b1-logic-sets) 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](#def-b1-logic-inj) $\N \to A$, y $A$ es numerable.

**12.** Sea $E \preceq \N$ mediante una [inyección](#def-b1-logic-inj) $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](#def-b1-logic-sets) finitos y los [conjuntos numerables](#pb-b1-logic-1) 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](#def-b1-logic-inj) $E \times F \to \N$: si las imágenes coinciden, la [inyectividad](#def-b1-logic-inj) 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](https://one-course.com/books/math/3/es/chapter/6-aritmetica-de-los-enteros#ch-b1-arith); para $r = 0$ tómese $0/1$). La [aplicación](#def-b1-logic-map) $r \mapsto (p, q)$ es entonces [inyectiva](#def-b1-logic-inj): 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](#def-b1-logic-inj) $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](#def-b1-logic-inj) de $\varphi$ da $n(x) =
n(x') = n$ y $f_n(x) = f_n(x')$, luego $x = x'$ por [inyectividad](#def-b1-logic-inj) 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](#exo-b1-logic-4). Por tanto $\Psi(F) \neq \Psi(F')$: $\Psi$ es [inyectiva](#def-b1-logic-inj) y el [conjunto](#def-b1-logic-sets) de los subconjuntos finitos de $\N$ es a lo sumo numerable; es infinito (contiene todos los [conjuntos](#def-b1-logic-sets) 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](#thm-b1-logic-inverse), cada una es una [biyección](#def-b1-logic-inj): $\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](#def-b1-logic-inj), y por la pregunta 3 tampoco hay ninguna [inyección](#def-b1-logic-inj) $\{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](#def-b1-logic-map) $\Phi \colon \N \to \{0,1\}^{\N}$ es una [aplicación](#def-b1-logic-map) $f \colon \N \to \mathcal{P}(\N)$, y $d$ corresponde al [conjunto](#def-b1-logic-sets) $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](#exo-b1-logic-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](#def-b1-logic-inj) $\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](#pb-b1-logic-1) 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](#pb-b1-logic-1) mientras que su complementario no lo es; ninguna [biyección](#def-b1-logic-inj) podrá jamás emparejar $\R \setminus \Q$ con $\Q$ — hay estrictamente «más» irracionales que racionales, aunque los dos [conjuntos](#def-b1-logic-sets) 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](#def-b1-logic-inj), 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](#def-b1-logic-sets) 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](#def-b1-logic-sets) 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](#pb-b1-logic-1): a lo sumo numerable por la pregunta 15, e infinito, luego numerable.

**24.** Para cada polinomio entero no nulo $P$, el [conjunto](#def-b1-logic-sets) 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](#def-b1-logic-sets) 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](#pb-b1-logic-1) y forman incluso un [conjunto](#def-b1-logic-sets) no numerable, mientras que los [números algebraicos](#pb-b1-logic-1) — 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](#def-b1-logic-inj) ingeniosa, y se usó para $\intcc01 \approx \intoo01$, para $\Q$ y a lo largo de toda la parte V; la [biyección](#def-b1-logic-inj) 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](#pb-b1-logic-1) 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.