Matemáticas universitarias — Grado 1 · Bachelor Year 1

1Lógica, conjuntos y aplicaciones

Hasta ahora las pruebas se han realizado con una idea informal pero honesta. de lo que significa "probar". Este primer capítulo de pregrado. Las matemáticas hacen explícitas las reglas del juego: ¡qué matemática! enunciado es, cómo se combinan los conectivos y cuantificadores enunciados, qué movimientos son legales en una prueba — y luego construye, sobre esta base, los dos lenguajes universales de las matemáticas: conjuntos y aplicaciones.

1.1 Enunciados y conectivos

Definición 1.1 (Enunciado, conectivos)

Un enunciado (o proposición) es un oración que es verdadera (V) o falsa (F) — exactamente una de las dos. De las enunciados $P$ y $Q$ se forma:

o negación $\lnot P$ ("no $P$ "), verdadero exactamente cuando $P$ es falso;
o conjunción $P \land Q$ (“ $P$ y $Q$ ”), verdadero exactamente cuando ambas son ciertas;
o disyunción $P \lor Q$ (“ $P$ o $Q$ ”), verdadero exactamente cuando al menos uno es verdadero (este "o" es inclusivo);
el implicación $P \implies Q$ , falso exactamente cuando $P$ es verdadero y $Q$ es falso;
el equivalencia $P \iff Q$ , verdadero 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 verdadero, sea lo que sea $Q$ . “Si $2 < 1$ entonces $0 = 5$ ” es una implicación verdadera. Una implicación no afirma nada sobre ¿Qué sucede cuando su hipótesis falla?

Proposición 1.3 (Reglas de cómputo de 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)$ , por lo tanto $\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)$ y $P \lor (Q \land R) \iff (P \lor Q) \land (P \lor R)$ .

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

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

Las columnas $4$ y $7$ coinciden, lo que confirma la ley. Para contraposición un atajo verbal es más rápido: $P \implies Q$ es falso exactamente en el caso ( $P$ verdadero, $Q$ falso) y $(\lnot Q) \implies (\lnot P)$ es falso exactamente en el caso ( $\lnot Q$ verdadero, $\lnot P$ falso), es decir ( $Q$ falso, $P$ verdadero) — el mismo caso único, por lo que las dos implicaciones tienen tablas idénticas. Las reglas restantes se verifican de la misma manera; nota que (3) reduce cada implicación a una disyunción, de modo que (2) produce mecánicamente la regla de negación $\lnot(P \implies Q) \iff P \land (\lnot Q)$ : para contradecir una implicación se debe exhibir un caso donde la hipótesis se cumple y la conclusión falla. ∎

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 todos $x$ en $E$ , $P(x)$ ") es verdadero cuando cada 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 decir "existe un único".

Proposición 1.5 (Negación de 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. Argumentemos la primera equivalencia en ambas direcciones; el segundo es simétrico. Si $\forall x \in E,\ P(x)$ es falso, entonces no todos elemento satisface $P$ : el conjunto $A = \{x \in E : \lnot P(x)\}$ no puede estar vacío y cualquiera de sus elementos es testigo de $\exists x \in E,\ \lnot P(x)$ . Por el contrario, si algún $x_0 \in E$ satisface $\lnot P(x_0)$ , entonces $x_0$ es un contraejemplo y el universal enunciado falla. Para la segunda regla: “no $x$ satisface $P$ ” significa conjunto $\{x : P(x)\}$ está vacío, es decir, cada $x$ se encuentra en su complemento $A$ . Aplicados en cascada a un prefijo anidado de cuantificadores, los dos Las reglas dan el procedimiento mecánico de Ejemplo 1.8: la negación camina de izquierda a derecha, volteando cada $\forall$ en $\exists$ y cada $\exists$ en $\forall$ , y finalmente niega el predicado más interno. ∎

Ejemplo 1.6 (Negando oraciones matemáticas cotidianas)

Sea $f \colon \R \to \R$ . La frase “ $f$ está aumentando” dice

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

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

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

una sola pareja de testigos es suficiente. Del mismo modo, “ $f$ está acotado” 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 :

Se propone el límite lo que, algún punto lo supera. el Idea: una negación correcta nunca contiene "no" aplicado a un bloque cuantificado — es un nuevo positivo enunciado, en el cual el Se intercambian roles: ahora uno presenta a los testigos que antes recibido.

Ejemplo 1.7 (Orden de cuantificadores)

El orden de diferentes cuantificadores importa:

\forall x \in \R,\ \exists y \in \R,\ y > x \quad\text{is true (take } y = x+1\text{),}

\exists y \in \R,\ \forall x \in \R,\ y > x \quad\text{is false (no real number exceeds all reals).}

En el primero enunciado $y$ puede depender de $x$ ; en el segundo, uno solo $y$ debe funcionar para todos los $x$ . Dos cuantificadores idénticos, por otro lado mano, siempre conmutar.

Ejemplo 1.8 (Lectura de una definición con tres cuantificadores)

La frase “la secuencia $(u_n)$ converge a $\ell$ ” será escrito en 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, por Proposición 1.5 aplicada tres veces, es

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

Ser capaz de negar tales oraciones mecánicamente, sin pensar. sobre lo que quieren decir, es una habilidad genuina: separa el trabajo lógico del trabajo matemático.

1.3 Técnicas de prueba

Método 1.9 (Los patrones de prueba estándar)

Para probar…

an implication $P \implies Q$ directly: asume $P$ , deducir $Q$ ;
por contraposición: asume $\lnot Q$ , deduce $\lnot P$ — válido por Proposición 1.3 (4);
por contradicción: asume que enunciado es falso, deriva una contradicción;
una equivalencia: prove both implications separately (or cadena de equivalencias conocidas);
a “for all” enunciado: elige un arbitrario $x$ en $E$ ("let $x \in E$ ") y probar $P(x)$ ;
a “there exists” enunciado: presentar un testigo, o probar la existencia indirectamente;
por inducción: ver Teorema 1.12.

Al probar un enunciado sobre un elemento bien elegido pero arbitrario, never give the element extra properties: “let $x \in \R$ ” followed by “desde $x > 0$ …” no prueba nada sobre $x$ negativo.

Observación 1.10 (Errores comunes en las pruebas.)

Cuatro trampas clásicas, todas dignas de mencionar una vez.

Inverso en lugar de contrapositivo. $Q \implies P$ es no equivalente a $P \implies Q$ ; sólo $\lnot Q \implies \lnot P$ lo es. “Si llueve, la calle está mojada” no da derecho a concluir que llueve en una calle mojada.
Demostrar una equivalencia por una implicación. Un La afirmación “iff” son dos teoremas; anunciar en qué dirección está siendo probado, y probar ambos. Las cadenas de $\iff$ son legales. sólo si el enlace cada es realmente reversible — elevar al cuadrado una ecuación, por ejemplo, no lo es.
Pruebas al revés. Comenzando desde el deseado Concluir y deducir un verdadero enunciado no prueba nada. (de $-1 = 1$ se deriva el verdadero $1 = 1$ elevando al cuadrado). Un cálculo puede ser descubierto al revés, pero debe ser escrito hacia adelante, o con explícito equivalencias.
Testigo fijo versus elemento arbitrario. Para demostrar $\exists x,\ P(x)$ , uno puede exhibir uno ingeniosamente elegido $x$ ; para probar $\forall x,\ P(x)$ , el elegido $x$ debe seguir siendo arbitrario. Mezclando los dos — comprobando un afirmación universal sobre un ejemplo — es la más común error en las copias para principiantes.

Ejemplo 1.11 (Contraposición y contradicción en el trabajo.)

For $n \in \N$ : if $n^2$ is even then $n$ is even. Por contraposición: si $n$ es impar, $n = 2k+1$ , entonces $n^2 = 4k^2 + 4k + 1$ es extraño.

$\sqrt 2$ is irrational. Por contradicción: supongamos $\sqrt 2 = p/q$ con $p, q \in \N^*$ y la fracción en términos más bajos. Entonces $p^2 = 2q^2$ es par, entonces $p$ es par (punto anterior), $p = 2r$ ; entonces $q^2 = 2r^2$ es par, por lo que $q$ es par — contradice el más bajo términos.

Teorema 1.12 (induccion)

Sea $P(n)$ una propiedad del número entero $n$ . si

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

entonces $P(n)$ es cierto para todos los $n \in \N$ .

Fuerte inducción: conclusión sin cambios si (2) se reemplaza por: para todos $n$ , $\bigl(P(0) \land \dots \land P(n)\bigr) \implies P(n+1)$ .

Demostración. Esta es una propiedad del propio $\N$ , equivalente a: every nonempty subset of $\N$ has a least element (que tomamos como conocida). De hecho, supongamos que (1) y (2) mantienen y dejan $A = \{n \in \N : P(n) \text{ false}\}$ . Si $A \neq \emptyset$ , tiene un elemento mínimo $m$ ; $m \neq 0$ por (1); luego $m - 1 \notin A$ , por lo que se cumple $P(m-1)$ , y (2) da $P(m)$ — contradicción. Entonces $A = \emptyset$ . Para fuerte inducción, aplique el mismo argumento: $P(0), \dots, P(m-1)$ todos se mantienen ya que $m$ es menor en $A$ . ∎

Ejemplo 1.13 (Probando existencia única)

A enunciado $\exists!\,x,\ P(x)$ es dos enunciados, probado por separado: existencia (exhibir o construir algún $x_0$ con $P(x_0)$ ) y unicidad (supongamos $P(x)$ y $P(x')$ , deduzca $x = x'$ ). Muestra: hay un $x$ real único con $x^3 + x = 2$ . Existencia: $x_0 = 1$ funciona, desde $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 (es igual a $\bigl(x + \tfrac{x'}2\bigr)^2 + \tfrac34 x'^2 + 1 \geq 1$ ), por lo que $x = x'$ . Tenga en cuenta la división del trabajo: la existencia utilizó una suposición afortunada, álgebra utilizada de unicidad válida para soluciones arbitrario — Ninguno de los argumentos hace el trabajo del otro, y olvidar el segundo La mitad es una tentación permanente una vez que se ha encontrado una solución.

Ejemplo 1.14

Para todos los $n \in \N^*$ : $\;\sum_{k=1}^n k = \frac{n(n+1)}{2}$ . Caso base $n = 1$ : ambos lados son iguales a $1$ . Paso: asumiendo 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 (Fuerte inducción en el trabajo.)

Every integer $n \geq 2$ is a product of prime numbers (un primo siendo un número entero $\geq 2$ cuyos únicos divisores $\geq 1$ son $1$ y mismo; los primos se estudian por sí mismos en Capítulo 6). La inducción ordinaria es inútil aquí: sabiendo que $95 = 5 \times 19$ factores no dice nada sobre $96$ . La inducción fuerte encaja exactamente. bases caso: $2$ es primo, por lo tanto, un producto (de un factor) de primos. Paso: dejar $n \geq 2$ y supongamos que cada número entero $m$ con $2 \leq m \leq n$ es un producto de números primos. Si $n + 1$ es primo, listo. De lo contrario $n + 1 = ab$ con $2 \leq a, b \leq n$ ; por la hipótesis fuerte tanto $a$ como $b$ son productos de números primos, por lo tanto, $n + 1$ también lo es. La idea: fuerte La inducción es la herramienta adecuada siempre que viva la "razón" de $P(n+1)$ . en algún rango anterior impredecible, no en el rango $n$ .

1.4 Conjuntos

Definición 1.16 (Establecer operaciones)

Tomamos la noción de conjunto y la relación de membresía. $x \in E$ como primitivo. Para conjuntos $A, B$ dentro de un conjunto ambiental $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\}$ , complementar $\overline{A} = E \setminus A$ ;
o conjunto vacío $\emptyset$ , contenidos en cada conjunto;
el conjunto de potencia $\mathcal{P}(E)$ : el conjunto de todos los subconjuntos de $E$ ;
o producto $E \times F$ : el conjunto de pares ordenados $(x, y)$ con $x \in E$ , $y \in F$ .

Ejemplo 1.17 (Acostumbrándose al conjunto de potencia)

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

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

cuatro elementos — y tenga en cuenta la disciplina de tipo: $a \in E$ pero $\{a\} \in \mathcal P(E)$ ; el enunciados $a \in \mathcal P(E)$ y $\{a\} \subseteq \mathcal P(E)$ son ambos falsos tal como están escritos (el segundo requeriría que $a$ sea 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 — conjuntos de conjuntos son conjuntos ordinario y Capítulo 2 confirmarán la duplicación. patrón: $\abs{\mathcal P(E)} = 2^{\abs E}$ . manteniendo los niveles ( $x$ , $\{x\}$ , $\{\{x\}\}$ ) en fila es la mitad de la batalla en ejercicios como Ejercicios 1.11 y 1.12.

Proposición 1.18 (Álgebra de conjuntos)

Para los 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 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 de distributividad en su totalidad:

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 Proposición 1.3 (6), y la El último enunciado lee $x \in (A \cap B) \cup (A \cap C)$ . Cada conjunto La identidad de este tipo se puede demostrar mediante este mecanismo traducción — razón por la cual ninguno de ellos necesita ser memorizado. ∎

Método 1.19 (Demostración de igualdades de conjuntos)

Para probar $A = B$ , pruebe las dos inclusiones: let $x \in A$ , show $x \in B$ ; luego deje que $x \in B$ muestre $x \in A$ . Alternativamente, cadena equivalencias $x \in A \iff \dots \iff x \in B$ cuando cada paso es realmente una equivalencia.

Leyes de De Morgan en imágenes: la región sombreada de la izquierda es A ∪ B = A ∩ B(todo fuera de ambos discos); a la derecha, A ∩ B = A ∪ B(todo excepto la superposición en forma de lente). un El diagrama no es una prueba, pero hace que la búsqueda de elementos sea una prueba de imposible de recordar mal. — 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 fuera de ambos discos); a la derecha, $\overline{A \cap B} = \overline A \cup \overline B$ (todo excepto la superposición en forma de lente). un El diagrama no es una prueba, pero hace que la búsqueda de elementos sea una prueba de Proposición 1.18 imposible de recordar mal.

1.5 Aplicaciones

Definición 1.20 (Aplicación, imagen, imagen inversa)

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 el imagen directa de $A$ y el preimagen de $B$ . El 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 una aplicación inversa: $f^{-1}(B)$ se define para cada $f$ . Imágenes inversas se porta mejor que imágenes: $f^{-1}$ conserva uniones, intersecciones y complementos, mientras que $f(A \cap A') \subseteq f(A) \cap f(A')$ puede ser estricto (Ejercicio 1.8).

Ejemplo 1.22 (Computación de imágenes y preimágenes)

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 el primero: cada $x \in \intcc{-1}2$ tiene $x^2 \in \intcc04$ , y cada $y \in \intcc04$ se obtiene como $y = (\sqrt y)^2$ con $\sqrt y \in \intcc02 \subseteq \intcc{-1}2$ — tenga en cuenta que la imagen es no $\intcc14 = \{(-1)^2, 2^2\}$ : las imágenes de intervalos no son calculado únicamente a partir de puntos finales. Para el segundo: $1 \leq x^2 \leq 4 \iff 1 \leq \abs x \leq 2$ , que se parte en dos pedazos. el tercero ilustra que un imagen inversa puede estar vacío — $f^{-1}(B)$ siempre hace sentido, por pequeña que sea la intersección de $B$ con la imagen. Finalmente observe en este ejemplo el fenómeno de rigor de la observación anterior: con $A = \intcc{-1}0$ y $A' = \intcc01$ , uno tiene $f(A \cap A') = f(\{0\}) = \{0\}$ , mientras que $f(A) \cap f(A') = \intcc01$ .

Definición 1.23 (Inyectivo, sobreyectivo, biyectivo)

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

inyectivo cuando distintos elementos tienen imágenes distintas: $\forall x, x' \in E,\ f(x) = f(x') \implies x = x'$ ;
sobreyectivo cuando cada elemento de $F$ se alcanza: $\forall y \in F,\ \exists x \in E,\ f(x) = y$ ;
biyectivo cuando es ambos, es decir cada $y \in F$ tiene exactamente un imagen inversa.

Teorema 1.24 (Aplicación inversa)

Una aplicación $f \colon E \to F$ es biyectivo si y sólo si hay una aplicación $g \colon F \to E$ con $g \circ f = \mathrm{id}_E$ y $f \circ g = \mathrm{id}_F$ . En ese caso $g$ es único; está escrito $f^{-1}$ y llamado inverso de $f$ , y $f^{-1}$ es en sí mismo biyectivo con $(f^{-1})^{-1} = f$ .

Demostración. ( $\Rightarrow$ ) Si $f$ es biyectivo, cada $y \in F$ tiene un imagen inversa; defina $g(y)$ como imagen inversa. Entonces $f(g(y)) = y$ por construcción, y $g(f(x)) = x$ porque $x$ es el imagen inversa de $f(x)$ .

( $\Leftarrow$ ) Supongamos que existe tal $g$ . Si $f(x) = f(x')$ , aplicando $g$ da $x = x'$ : $f$ es inyectivo. Para $y \in F$ , $x = g(y)$ satisface $f(x) = y$ : $f$ es sobreyectivo.

Unicidad: si $g$ y $h$ funcionan, entonces $g = g \circ \mathrm{id}_F = g \circ (f \circ h) = (g \circ f) \circ h = h$ . Finalmente la pareja de Las identidades son simétricas en $f$ y $g$ , por lo que $g = f^{-1}$ es biyectivo. con inverso $f$ . ∎

Ejemplo 1.25 (Calcular una inversa en la práctica)

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

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

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

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

Una comprobación rápida de ambas composiciones ( $f^{-1}(f(x)) = \frac{(2x+1) - 1}2 = x$ y $f(f^{-1}(y)) = \eu^{\ln y} = y$ ) confirma Criterio de Teorema 1.24. La idea: "resolver $x$ y observar las equivalencias” es simultáneamente la existencia prueba, la prueba de unicidad y la fórmula — pero solo funciona si el codominio se anunció correctamente ( $f$ es no sobreyectivo sobre $\R$ ).

Proposición 1.26 (Composición y tres propiedades)

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

Si $f$ y $g$ son inyectivo (resp. sobreyectivo, biyectivo), entonces es $g \circ f$ ; y luego $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ en el caso biyectivo.
Si $g \circ f$ es inyectivo, entonces $f$ es inyectivo. si $g \circ f$ es sobreyectivo, luego $g$ es sobreyectivo.

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

(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$ , sobreyectividad de $g \circ f$ da $x$ con $g(f(x)) = z$ : luego $y = f(x)$ satisface $g(y) = z$ . ∎

Ejemplo 1.27 (El punto (2) es nítido)

En Proposición 1.26 (2), no se puede actualizar el conclusiones: $g \circ f$ biyectivo ¿no fuerza a $f$ ? sobreyectivo o $g$ inyectivo. Tome $E = G = \{1\}$ , $F = \{1, 2\}$ , con $f(1) = 1$ y $g(1) = g(2) = 1$ : entonces $g \circ f = \mathrm{id}_E$ es biyectivo, pero $f$ omite el elemento $2$ y $g$ colapsa ambos elementos. La moraleja es una contabilidad precisa. regla: la información de composición fluye al interno aplicación para inyectividad y al exterior aplicación para sobreyectividad, nunca al revés. (Ejercicio 1.9 construye el mismo fenómeno con infinito conjuntos, donde está el motor detrás unilateral inversas.)

Ejemplo 1.28

$f \colon \R \to \R$ , $x \mapsto x^2$ no es inyectivo ( $f(-1) = f(1)$ ) ni sobreyectivo ( $-1$ no tiene imagen inversa). Restringir el dominio y el codominio, $f \colon \R_+ \to \R_+$ , $x \mapsto x^2$ es biyectivo, con inverso $y \mapsto \sqrt y$ . Inyectividad o sobreyectividad de A aplicación Depende del dominio y codominio anunciado, no sólo de la fórmula.

1.6 Relaciones

Definición 1.29 (Relación de equivalencia)

Un relación binaria $\mathcal{R}$ en un conjunto $E$ es un relación de equivalencia cuando es: reflexivo ( $x \mathbin{\mathcal{R}} x$ para todos los $x$ ), simétrico ( $x \mathbin{\mathcal{R}} y \implies y \mathbin{\mathcal{R}} x$ ) y transitivo ( $x \mathbin{\mathcal{R}} y$ y $y \mathbin{\mathcal{R}} z$ implican $x \mathbin{\mathcal{R}} z$ ). El clase de equivalencia de $x$ es $\mathrm{cl}(x) = \{y \in E : x \mathbin{\mathcal{R}} y\}$ .

Ejemplo 1.30 (Comprobando los tres axiomas)

En $\R$ , declare $x \mathbin{\mathcal{R}} y$ cuando $x - y \in \Z$ . Reflexivo: $x - x = 0 \in \Z$ . Simétrico: si $x - y \in \Z$ entonces $y - x = -(x - y) \in \Z$ . Transitivo: si $x - y \in \Z$ y $y - z \in \Z$ , entonces $x - z = (x - y) + (y - z) \in \Z$ (una suma de números enteros). Entonces $\mathcal R$ es equivalencia relación y $\mathrm{cl}(x) = x + \Z = \{x + k : k \in \Z\}$ : cada clase contiene exactamente un representante en $\intco01$ , su parte fraccionaria. Por el contrario, la relación “ $\abs{x - y} \leq 1$ ” en $\R$ es reflexiva y simétrica, pero no transitivo ( $0 \mathbin{\mathcal R} 1$ y $1 \mathbin{\mathcal R} 2$ , aún $\abs{0 - 2} > 1$ ): la cercanía no se propaga y no dividir en clases existe — un contraejemplo útil para mantener tener en cuenta al verificar los axiomas parece una rutina.

Teorema 1.31 (Las clases forman una partición.)

Sea $\mathcal{R}$ un relación de equivalencia en $E$ . Entonces el las clases de equivalencia no están vacías, son disjuntas por pares o iguales, y sus unión es $E$ : forman un dividir de $E$ . Por el contrario, cada dividir de $E$ surge de esta manera exactamente de un relación de equivalencia (“estar en la misma pieza”).

Demostración. $x \in \mathrm{cl}(x)$ por reflexividad, por lo que las clases no están vacías con unión $E$ . Supongamos $\mathrm{cl}(x) \cap \mathrm{cl}(y) \neq \emptyset$ , digamos $z$ se encuentra en ambos. Luego $x \mathbin{\mathcal{R}} z$ y $y \mathbin{\mathcal{R}} z$ , por simetría y transitividad $x \mathbin{\mathcal{R}} y$ . Ahora para cualquier $t \in \mathrm{cl}(y)$ , transitividad da $t \in \mathrm{cl}(x)$ , y simétricamente: los dos las clases son iguales. Por el contrario, sea $(E_i)_{i \in I}$ un dividir de $E$ y define $x \mathbin{\mathcal S} y$ como significado “alguna pieza contiene $x$ y $y$ ”. Reflexivo: $x$ se encuentra en alguna pieza, que luego contiene $x$ dos veces. Simétrico: la condición definitoria es simétrica en $x$ y $y$ . Transitivo: si $x, y \in E_i$ y $y, z \in E_j$ , entonces $y \in E_i \cap E_j$ , por lo que $E_i = E_j$ (las piezas distintas son disjunto) y $x, z$ comparten una pieza. La clase $\mathcal S$ de $x$ es exactamente la pieza que contiene $x$ , por lo que las clases son las dadas piezas. Finalmente la relación está determinada por sus clases: dos relaciones de equivalencia con las mismas clases relacionan los mismos pares, ya que cada uno relaciona $x$ y $y$ exactamente cuando $y$ pertenece al clase de $x$ — de ahí la afirmación de unicidad. ∎

Ejemplo 1.32

En $\Z$ , módulo de congruencia $n$ ( $x \equiv y \pmod n$ cuando $n$ divide $x - y$ ) es un relación de equivalencia; sus clases son las $n$ conjuntos de números enteros con un resto dado al dividir por $n$ . este ejemplo se convierte en el anillo $\Z/n\Z$ en Capítulo 7.

Definición 1.33 (Relación de pedido)

Una relación $\preceq$ en $E$ es una orden cuando es reflexivo, antisimétrico ( $x \preceq y$ y $y \preceq x$ implican $x = y$ ) y transitivo. El pedido es total cuando dos elementos cualesquiera sean comparables, parcial en caso contrario. un el elemento $M \in A \subseteq E$ es un mayor elemento de $A$ cuando $a \preceq M$ para todos los $a \in A$ ; los elementos mayores (y menores) son únicos cuando existen.

Ejemplo 1.34

$(\R, \leq)$ está totalmente ordenado. $(\mathcal{P}(E), \subseteq)$ es pedido parcialmente tan pronto como $E$ tenga dos elementos: $\{a\}$ y $\{b\}$ no son comparables. El subconjunto $A = \{\{a\}, \{b\}\}$ de $\mathcal{P}(\{a,b\})$ no tiene elemento mayor, pero tiene un límite superior $\{a, b\}$ : la distinción entre elementos mayores y límites superiores devuelve, para $\R$ , en Capítulo 10.

Ejemplo 1.35 (Dos órdenes en la parrilla $\N^2$ )

En pares de naturales, compare por componentes: $(a, b) \preceq (a', b')$ cuando $a \leq a'$ y $b \leq b'$ (el product orden). Este es un orden — cada axioma es una coordenada heredada por coordenada — pero parcial: $(1, 3)$ y $(2, 0)$ son incomparable. Ahora compare como un diccionario: $(a, b) \preceq_{\mathrm{lex}} (a', b')$ cuando $a < a'$ , o $a = a'$ y $b \leq b'$ (el lexicographic orden). La transitividad requiere una verificación de dos casos pero se cumple, y dos pares cualesquiera ahora son comparables: el orden es total. Los dos pedidos clasifican al mismo conjunto de manera diferente — $(0, 100) \preceq_{\mathrm{lex}} (1, 0)$ a través del producto orden no dice nada — un recordatorio de que orden es una estructura uno elige, no es propiedad de conjunto. Lexicográfico La comparación es también el truco estándar para convertir varios sistemas de clasificación. criterios en uno solo.

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

Un tema tranquilo de este capítulo merece atención: las biyecciones son la noción matemática de "mismo tamaño". Para conjuntos finito esto se convierte en el cálculo de conteo de Capítulo 2, donde toda fórmula es secretamente una biyección; para infinito conjuntos se convierte en el problema del fin de semana a continuación, donde $\N$ , $\Q$ y $\R$ se vuelven resulta que tienen tamaños realmente diferentes. el mismo diccionario reaparece dos veces más en este volumen en formas refinadas: secuencias (Capítulo 11) no son más que aplicaciones $\N \to \R$ , entonces enunciados las secuencias de aproximadamente son enunciados de conjunto de aplicaciones; y lineal El álgebra medirá espacios vectoriales no por biyecciones sino por lineal biyecciones, cuya existencia se rige por una única número, la dimensión (Capítulo 19). Cada vez que un nuevo Aparece "igualdad" — equipotencia, isomorfismo de grupos (Capítulo 7), isomorfismo lineal — el patrón de Teorema 1.24 repite: la igualdad es invertible, aplicación que respeta la estructura.

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

En todas partes, pero unos pocos lugares merecen ser señalados. El tres cuantificador gimnasia de Ejemplo 1.8 es el pan de cada día de Capítulos 11 y 13: cada prueba de límite es un juego contra un $\varepsilon$ arbitrario. Las clases de equivalencia reaparecen como clases de congruencia de $\Z/n\Z$ en Capítulo 7, donde el dividir de Teorema 1.31 adquiere un valor algebraico estructura propia. Relaciones de orden, límites superiores y mínimo superior Los límites se convierten en el corazón axiomático de $\R$ en Capítulo 10. Las inyecciones, sobreyecciones y biyecciones regresan como el aplicaciones lineal de Capítulo 20, donde se puede probar la inyectividad en un solo vector (el núcleo); y el problema del fin de semana a continuación deja al desnudo noción de biyección en una teoría del sizes of infinite conjuntos, cuyas conclusiones (contabilidad de $\Q$ , incontabilidad de $\R$ ) resurgen en Capítulos 10 y 12.

1.7 Ceremonias

Ejercicio 1.1 ★

Escribe la negación de cada enunciado, sin utilizar la palabra “not”:

$\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 un fijo aplicación $f \colon \R \to \R$ ).

Luego decida si enunciados (1) y (2) son verdaderos.

Solución

Solución de Ejercicio 1.1.

Negaciones, empujando a $\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{ and } \abs{f(x)} > \varepsilon$ .

Enunciado (1) es verdadero: dado $x$ , tome $y = -x + 1$ ; luego $x + y = 1 > 0$ . Enunciado (2) es verdadero: $x = 0$ satisface $xy = 0$ para todos los $y$ .

Ejercicio 1.2 ★

Sea $P, Q$ enunciados. Usando tablas de verdad, demuestre que $\lnot(P \implies Q) \iff P \land (\lnot Q)$ , y deducir 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$
T	T	T	F	F	F
T	F	F	T	T	T
F	T	T	F	F	F
F	F	T	F	T	F

Las columnas $4$ y $6$ coinciden, demostrando la equivalencia. La negación de "Si una función es derivable entonces es continua" es por lo tanto: "Existe una función que es diferenciable y no continua". (un enunciado falso, da la casualidad: la implicación original es verdadera, ver Capítulo 14).

Ejercicio 1.3 ★

Demostrar por contraposición: para $x \in \R$ , si $x^3 + x \geq 2$ entonces $x \geq 1$ . Luego demuestre por contradicción: no existe un mínimo estrictamente número real positivo.

Solución

Solución de Ejercicio 1.3.

Contraposición. Supongamos $x < 1$ . Entonces $x^3 < 1$ (el cubo la función está aumentando) y $x < 1$ , por lo que $x^3 + x < 2$ . Esto prueba la contrapositivo, de ahí el enunciado.

Contradicción. Supongamos que $a > 0$ es el valor estrictamente positivo más pequeño. real. Entonces $a/2$ es estrictamente positivo y $a/2 < a$ (desde $a > 0$ ), minimalismo contradictorio. Por lo tanto, no existe tal $a$ .

Ejercicio 1.4 ★

Demuestre 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: asumir el 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 ★

Encuentre el defecto en la siguiente "prueba" de que todos los lápices tienen iguales color. Let $P(n)$ : “in every conjunto of $n$ pencils, all pencils have the same color”. $P(1)$ is clear. Assume $P(n)$ and take $n+1$ pencils; removing the last one, the first $n$ share their color; removing the first one, the last $n$ share their color; hence all $n+1$ share their color.

Solución

Solución de Ejercicio 1.5.

El paso inductivo supone silenciosamente que los dos grupos (“el primero $n$ ” y “el último $n$ ”) se superponen, de modo que los lápices compartidos llevan 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. Entonces $P(1) \implies P(2)$ nunca fue probado, y la inducción colapsa — aunque $P(n) \implies P(n+1)$ es válido para cada $n \geq 2$ .

Ejercicio 1.6 ★

Sean $A, B, C$ subconjuntos de $E$ . Demostrar:

$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 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$ (ambos piezas se encuentran en $B$ ) y $B \subseteq A \cup B$ siempre, por lo que $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$ , entonces $A \cap B = A$ . Supongamos $A \cap B = A$ : luego $A = A \cap B \subseteq B$ . Las tres condiciones son por lo tanto equivalente (probamos un ciclo de implicaciones).

Ejercicio 1.7 ★★

Para cada aplicación, decida (con prueba) si es inyectivo, sobreyectivo, biyectivo:

$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$ , ajuste el codominio para que sea biyectivo y calcule el inversa.

Solución

Solución de Ejercicio 1.7.

$f$ es inyectivo ( $n + 1 = m + 1 \implies n = m$ ) pero no sobreyectivo: $0$ no tiene imagen inversa en $\N$ .
$g$ es biyectivo: $n \mapsto n - 1$ es una inversa de dos caras en $\Z$ .
$h$ es inyectivo: $\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$ , entonces $2x' = 2x$ . No es sobreyectivo en $\R$ : resolver $y = \frac{x+1}{x-1}$ da $x(y - 1) = y + 1$ , que no tiene solución cuando $y = 1$ (la ecuación dice $0 = 2$ ). Con el codominio $\R \setminus \{1\}$ , el mismo cálculo da el único imagen inversa $x = \frac{y+1}{y-1}$ , por lo que $h \colon \R \setminus \{1\} \to \R \setminus \{1\}$ es biyectivo y $h^{-1}(y) = \frac{y+1}{y-1} = h(y)$ : $h$ es su propia inversa.

Ejercicio 1.8 ★★

Dejemos $f \colon E \to F$ , dejemos $A, A' \subseteq E$ y $B, B' \subseteq F$ .

Demuestre $f^{-1}(B \cap B') = f^{-1}(B) \cap f^{-1}(B')$ y $f(A \cup A') = f(A) \cup f(A')$ .
Demuestre $f(A \cap A') \subseteq f(A) \cap f(A')$ y dé una Ejemplo donde la inclusión es estricta.
Demuestre: $f$ es inyectivo si y sólo si $f(A \cap A') = f(A) \cap f(A')$ para todos los $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 imágenes: $y \in f(A \cup A')$ y si $y = f(x)$ para algunas $x$ en $A$ o en $A'$ , si es $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'$ , entonces $y \in f(A)$ y $y \in f(A')$ . Rigor: tomar $f \colon \R \to \R$ , $x \mapsto x^2$ , $A = \{-1\}$ , $A' = \{1\}$ : luego $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$ , contradiciendo lo supuesto igualdad; entonces $f$ es inyectivo. ( $\Rightarrow$ ) Sea $f$ inyectivo y $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'$ , por lo que $y \in f(A \cap A')$ . Con (2), se cumple la igualdad.

Ejercicio 1.9 ★★

Sea $f \colon E \to F$ y $g \colon F \to E$ satisfagan a $g \circ f = \mathrm{id}_E$ . Demuestre que $f$ es inyectivo y $g$ es sobreyectivo. Dé un ejemplo en el que ni $f$ ni $g$ sean biyectivo.

Solución

Solución de Ejercicio 1.9.

$g \circ f = \mathrm{id}_E$ es inyectivo y sobreyectivo, por lo que por Proposición 1.26 (2), $f$ es inyectivo y $g$ es sobreyectivo. 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 todos los $n \in \N$ , pero $f$ no lo es. sobreyectivo y $g$ no es inyectivo.

Ejercicio 1.10 ★★

En $\R$ , defina $x \mathbin{\mathcal{R}} y \iff x^2 - y^2 = x - y$ . Demuestre que $\mathcal{R}$ es un relación de equivalencia y describa el clase de equivalencia de cada $x$ real. ¿Qué clases tienen exactamente una? 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$ . Reflexivo: $y = x$ funciona. Simétrico: la condición “ $y = x$ o $y = 1 - x$ ” es simétrico en $x$ y $y$ (si $y = 1 - x$ entonces $x = 1 - y$ ). Transitivo: supongamos $x \mathbin{\mathcal{R}} y$ y $y \mathbin{\mathcal{R}} z$ ; pasando por los cuatro casos, $z$ es igual a $x$ o $1 - x$ cada vez (por ejemplo, $y = 1 - x$ y $z = 1 - y$ dan $z = x$ ). Entonces $\mathcal{R}$ es relación de equivalencia y $\mathrm{cl}(x) = \{x,\, 1 - x\}$ . Esta clase tiene un elemento exactamente cuando $x = 1 - x$ , es decir, para $x = \frac12$ .

Ejercicio 1.11 ★★★

(Cantor) Sea $E$ un conjunto. Demostrar que no existe sobreyección de $E$ hacia $\mathcal{P}(E)$ . Hint: given $f \colon E \to \mathcal{P}(E)$ , consider $D = \{x \in E : x \notin f(x)\}$ .

Solución

Solución de Ejercicio 1.11.

Sea $f \colon E \to \mathcal{P}(E)$ cualquier aplicación y establezca $D = \{x \in E : x \notin f(x)\} \in \mathcal{P}(E)$ . Supongamos $D = f(a)$ para algunos $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)$ , por definición de $D$ , $a \in D$ : contradicción. Por lo tanto $D$ es no en la imagen de $f$ y $f$ no es sobreyectivo. (En particular no conjunto está en biyección con su conjunto de potencia: hay "más" subconjuntos de $\N$ que los números enteros.)

Ejercicio 1.12 ★★★

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

Demuestre que $f$ es sobreyectivo si y sólo si $\Phi$ es inyectivo.
Demuestre que $f$ es inyectivo si y sólo si $\Phi$ es sobreyectivo.

Solución

Solución de Ejercicio 1.12.

( $\Rightarrow$ ) Sea $f$ sobreyectivo y $\Phi(B) = \Phi(B')$ . Para $y \in B$ , elija $x$ con $f(x) = y$ ; luego $x \in f^{-1}(B) = f^{-1}(B')$ , entonces $y = f(x) \in B'$ . Por lo tanto $B \subseteq B'$ , y simétricamente $B' \subseteq B$ : $\Phi$ es inyectivo. ( $\Leftarrow$ ) Si $f$ no es sobreyectivo, seleccione $y_0 \in F$ fuera de la imagen; entonces $f^{-1}(\{y_0\}) = \emptyset = f^{-1}(\emptyset)$ con $\{y_0\} \neq \emptyset$ , por lo que $\Phi$ es no inyectivo.
( $\Rightarrow$ ) Sea $f$ inyectivo y $A \subseteq E$ . conjunto $B = f(A)$ ; luego $f^{-1}(B) = \{x : f(x) \in f(A)\}$ , y la inyectividad da $f(x) \in f(A) \iff x \in A$ , por lo que $\Phi(B) = A$ : $\Phi$ es sobreyectivo. ( $\Leftarrow$ ) Si $f$ no es inyectivo, tome $x \neq x'$ con $f(x) = f(x')$ . cada imagen inversa conjunto $f^{-1}(B)$ contiene $x$ si y sólo si contiene $x'$ ; por lo tanto $\{x\}$ no tiene la forma $\Phi(B)$ , y $\Phi$ no es sobreyectivo.

1.8 Problema: comparar infinitos

Problema 1.1

¿Cuándo dos conjuntos tienen "el mismo número de elementos"? Cantor respuesta — cuando hay una biyección entre ellos — resulta ser utilizable incluso para infinito conjuntos, y divide el infinito en genuinamente diferentes tamaños. Este problema construye toda la caja de herramientas desde cero. definiciones de este capítulo: el teorema de Cantor–Schröder–Bernstein (dos inyecciones producen una biyección), la contabilización de $\Q$ , la incontabilidad de $\R$ por el argumento diagonal, y la de Cantor sorprendente conclusión de 1874: números trascendentales exist, and massively so, sin exhibir ni uno solo. En todo momento, para conjuntos $E$ y $F$ , escriba $E \preceq F$ cuando haya existe una inyección de $E$ en $F$ y $E \approx F$ (“ $E$ y $F$ son equipotente”) cuando existe una biyección de $E$ hacia $F$ .

Parte I — The vocabulary of comparison.

Demuestre que $\approx$ se comporta como un relación de equivalencia: $E \approx E$ ; si $E \approx F$ entonces $F \approx E$ ; si $E \approx F$ y $F \approx G$ y luego $E \approx G$ . (Cita precisamente Teorema 1.24 y Proposición 1.26.)
Demuestre que $\preceq$ es transitivo y que una inyección $f \colon E \to F$ siempre induce a $E \approx f(E)$ .
Vamos $E \neq \emptyset$ . Demuestre que $E \preceq F$ si y sólo si existe una sobreyección de $F$ a $E$ .
Verifique que $n \mapsto n + 1$ sea una biyección de $\N$ a $\N^* = \N \setminus \{0\}$ , y que

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

es una biyección de $\N$ a $\Z$ . Por lo tanto, eliminando un punto, o duplicar a negativos, no cambia el tamaño de $\N$ .

Parte II — The Cantor–Schröder–Bernstein theorem. Sean $f \colon E \to F$ y $g \colon F \to E$ dos inyecciones. Definir

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 dejar que $h \colon E \to F$ envíe $x \in C$ a $f(x)$ y $x \notin C$ al único $y \in F$ con $g(y) = x$ .

Comprobar que $h$ esté bien definido: si $x \notin C$ entonces $x \in g(F)$ , y el elemento $y$ con $g(y) = x$ es único.
Demuestra que $g\bigl(f(C)\bigr) = \bigcup_{n \geq 1} C_n \subseteq C$ . (Las imágenes directas conmutan con los sindicatos: Ejercicio 1.8.)
Demuestre que $h$ es inyectivo. (Tres casos; en el caso mixto $x \in C$ , $x' \notin C$ , muestran que $h(x) = h(x')$ fuerza $x' \in g(f(C)) \subseteq C$ .)
Demuestre que $h$ es sobreyectivo: dado $y \in F$ , distinga los casos $g(y) \notin C$ y $g(y) \in C_n$ para algunos $n \geq 1$ (¿por qué es imposible $g(y) \in C_0$ ?), y exhiben un imagen inversa de $y$ en cada caso.
Concluye con Cantor–Schröder–Bernstein theorem: si $E \preceq F$ y $F \preceq E$ , entonces $E \approx F$ . Comenta en una frase lo que hace que esto enunciado no trivial.
Dos aplicaciones. (a) Mostrar $\intcc01 \approx \intoo01$ . (b) Demuestre que $\varphi(p, q) = 2^p(2q + 1) - 1$ define un biyección de $\N \times \N$ a $\N$ — inyectividad por un argumento de paridad, sobreyectividad por inducción fuerte (Teorema 1.12). Por lo tanto $\N \times \N \approx \N$ : el plano de puntos enteros no es mayor que el línea.

Parte III — Conjuntos contables. Llamar a conjunto $E$ como máximo contable cuando $E \preceq \N$ y contable cuando $E \approx \N$ .

Demuestre que todo subconjunto infinito $A \subseteq \N$ es contable. (Defina $\varphi(n)$ recursivamente como el mínimo elemento de $A \setminus \{\varphi(0), \dots, \varphi(n-1)\}$ ; mostrar $\varphi$ es estrictamente creciente, satisface $\varphi(n) \geq n$ y alcanza todos los elementos de $A$ .)
Deduzca que un conjunto es como máximo contable si y sólo si es finito o contable, y observe que la pregunta 9 da la atajo: si $E \preceq \N$ y $\N \preceq E$ , entonces $E$ es contable.
Demuestre que si $E$ y $F$ son como máximo contables, también lo es $E \times F$ . Deduzca que $\Z \times \N^*$ es contable.
Demuestre que $\Q$ es contable. (Inyecte $\Q$ en $\Z \times \N^*$ escribiendo cada racional en sus términos más bajos con positivo denominador — la unicidad de esa representación es probado en Capítulo 6; luego aplique la pregunta 12.)
Demuestre que una unión contable de como máximo conjuntos contables está en más contable: si cada $E_n$ ( $n \in \N$ ) es como máximo contable, también lo es $\bigcup_{n \in \N} E_n$ . (Envíe $x$ al par $(n, f_n(x))$ donde $n$ es el índice el menos con $x \in E_n$ .)
Demuestre que el conjunto de los subconjuntos finito de $\N$ es contable. (Asigne un subconjunto finito $F$ a $\sum_{i \in F} 2^i$ ; probar la inyectividad comparando el elemento más grande donde dos finito conjuntos difieren, usando $\sum_{k=0}^{m-1} 2^k = 2^m - 1$ de Ejercicio 1.4.)

Parte IV — Diagonalization. Deja $\{0,1\}^{\N}$ denota el conjunto de todos los aplicaciones $u \colon \N \to \{0, 1\}$ , es decir, el conjunto de secuencias binarias.

Construya una biyección entre $\mathcal{P}(\N)$ y $\{0,1\}^{\N}$ (funciones del indicador).
(El argumento diagonal) Sea $\Phi \colon \N \to \{0,1\}^{\N}$ cualquier aplicación. Considere la secuencia $d$ definida por $d(n) = 1 - \Phi(n)(n)$ . Mostrar que $d$ no está en el imagen de $\Phi$ y concluir que $\{0,1\}^{\N}$ es no como máximo contable. Explica en una frase por qué, hasta la pregunta 17, este es exactamente el teorema de Cantor (Ejercicio 1.11) para $E = \N$ .
Admitir — como familiar de la escuela y establecido rigurosamente en Capítulo 10 — que cada $x \in \intco01$ tiene una expansión decimal adecuado única $x = 0.d_1 d_2 d_3\dots$ (una que no termina en una cadena infinita de $9$ s). Dada cualquier secuencia $(x_n)_{n \geq 1}$ de elementos de $\intco01$ , construya $x \in \intco01$ con $x \neq x_n$ para todos $n$ : elija su dígito $n$ para que sea $5$ si el $n$ -ésimo El dígito de $x_n$ difiere de $5$ y de $6$ en caso contrario. justificar cuidadosamente que $x$ sea adecuado y evite cada $x_n$ , y concluir que $\intco01$ no es, como mucho, contable.
Deduzca que $\R$ es incontable y que el conjunto $\R \setminus \Q$ de números irracionales también es incontable. ¿En qué sentido preciso son irracionales "la mayoría" de los números reales?

Part V — Cantor’s 1874 theorem: trascendental numeros exist. Un número real $x$ es algebraico cuando $P(x) = 0$ para algún polinomio distinto de cero $P$ con coeficientes enteros y trascendental en caso contrario. Admítelo para esta parte — se demuestra en Capítulo 8 — que un polinomio distinto de cero de El grado $n$ tiene como máximo $n$ raíces reales.

Demuestre que todo número racional es algebraico y encuentre polinomios explícitos con coeficientes enteros aniquiladores $\sqrt 2$ y $\sqrt 2 + \sqrt 3$ .
Para $n \in \N$ fijo, demuestre que el conjunto de polinomios de El grado como máximo $n$ con coeficientes enteros es contable. (Inyéctelo en $\Z^{n+1}$ e induzca en $n$ con pregunta 13.)
Deduce que el conjunto de todo polinomios con número entero los coeficientes son contables.
Prueba Cantor’s theorem on números algebraicos: el conjunto $\mathcal{A}$ de números reales algebraicos es contable.
Concluye: los números reales trascendentales existen, y el conjunto de números trascendentales es incontable. Luego haga un balance de Todo el problema en unas pocas frases: la cadena $\N \approx \Z \approx \Q \approx \mathcal{A}$ , el salto estricto a $\R \approx$ (esencialmente) $\mathcal{P}(\N)$ , donde cada herramienta (Cantor–Schröder–Bernstein, uniones contables, el diagonal) fue decisivo — y el golpe filosófico de demostrando que existen incontables números trascendentales sin nombrar ni uno solo. (Acreditando un número específico como $\pi$ trascendental es mucho más difícil y más allá de esto volumen.)

Solución

Solución de Problema 1.1.

1. Reflexivo: $\mathrm{id}_E$ es una biyección de $E$ sobre sí mismo. Simétrico: si $f \colon E \to F$ es biyectivo, Teorema 1.24 proporciona $f^{-1} \colon F \to E$ , en sí biyectivo. Transitivo: si $f \colon E \to F$ y $g \colon F \to G$ son biyección, Proposición 1.26 (1) dice $g \circ f \colon E \to G$ es una biyección. (Esto es sólo “como” un equivalencia relación: la colección de todos los conjuntos no es en sí misma un conjunto, según paradojas que insinúa Ejercicio 1.11; las tres propiedades son lo que importa.)

2. Si $f \colon E \to F$ y $g \colon F \to G$ son inyectivo, $g \circ f$ es inyectivo por Proposición 1.26 (1): $E \preceq G$ . Para el segundo punto, restrinja $f$ a su imagen: el aplicación $\tilde f \colon E \to f(E)$ , $x \mapsto f(x)$ , es sobreyectivo por construcción de $f(E)$ y inyectivo porque $f$ es, por lo tanto, biyectivo: $E \approx f(E)$ .

3. ( $\Rightarrow$ ) Sea $f \colon E \to F$ inyectivo y arreglar $a \in E$ ( $E \neq \emptyset$ ). Defina $s \colon F \to E$ por: $s(y)$ es el único $x$ con $f(x) = y$ cuando $y \in f(E)$ (singularidad por inyectividad), y $s(y) = a$ en caso contrario. Por cada $x \in E$ , $s(f(x)) = x$ , por lo que se alcanza cada $x$ : $s$ es sobreyectivo. ( $\Leftarrow$ ) Sea $s \colon F \to E$ sobreyectivo. Para cada $x \in E$ , elija un $y_x \in F$ con $s(y_x) = x$ y configure $u(x) = y_x$ . si $u(x) = u(x')$ luego $x = s(u(x)) = s(u(x')) = x'$ : $u \colon E \to F$ es inyectivo.

4. $n \mapsto n + 1$ aplicaciones $\N$ en $\N^*$ , es inyectivo ( $n + 1 = m + 1 \implies n = m$ ) y sobreyectivo (cada $m \geq 1$ es $(m - 1) + 1$ con $m - 1 \in \N$ ). Para $\sigma$ : aplicaciones incluso números $0, 2, 4, \dots$ a $0, 1, 2, \dots$ y números impares $1, 3, 5, \dots$ a $-1, -2, -3, \dots$ Inyectividad: las entradas pares aterrizan en $\N$ ( $\sigma(n) = n/2 \geq 0$ ) y las entradas impares aterrizan en el enteros estrictamente negativos ( $\sigma(n) = -(n+1)/2 \leq -1$ ), por lo que un La colisión debe ocurrir dentro de una clase de paridad, donde $\sigma$ es estrictamente monótono ( $n/2 = m/2$ o $(n+1)/2 = (m+1)/2$ fuerza a $n = m$ ). Sobreyectividad: $k \geq 0$ es $\sigma(2k)$ ; $k \leq -1$ es $\sigma(-2k - 1)$ con $-2k - 1 \geq 1$ impar. Entonces $\N \approx \N^*$ y $\N \approx \Z$ .

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

6. Imágenes directas conmutan con sindicatos (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. Sea $x \neq x'$ en $E$ . Si ambos se encuentran en $C$ , entonces $h(x) = f(x) \neq f(x') = h(x')$ por inyectividad de $f$ . Si ninguno de los dos se encuentra en $C$ , luego $g(h(x)) = x \neq x' = g(h(x'))$ , entonces $h(x) \neq h(x')$ . si $x \in C$ y $x' \notin C$ (el caso mixto, hasta intercambiar 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. Entonces $h(x) \neq h(x')$ en todos los casos: $h$ es inyectivo.

8. Vamos $y \in F$ . Case 1: $g(y) \notin C$ . Entonces $h(g(y)) = g^{-1}(g(y)) = y$ : el elemento $g(y)$ es un imagen inversa. Case 2: $g(y) \in C$ , digamos $g(y) \in C_n$ . Desde $g(y) \in g(F)$ , tenemos $g(y) \notin C_0 = E \setminus g(F)$ , entonces $n \geq 1$ y $g(y) \in C_n = g(f(C_{n-1}))$ : hay $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$ , por lo que $h(x) = f(x) = y$ . En ambos casos $y$ es obtenido: $h$ es sobreyectivo, por lo tanto biyectivo.

9. Si $E \preceq F$ y $F \preceq E$ , elija las inyecciones $f \colon E \to F$ y $g \colon F \to E$ ; preguntas 5–8 construir un biyección $h \colon E \to F$ , entonces $E \approx F$ . El enunciado es no trivial porque las dos inyecciones administradas no están relacionadas — ninguna necesita ser sobreyectivo, y ninguna fórmula que combine $f$ y $g$ define ingenuamente a aplicación: todo el contenido es el dividir de $E$ en la región $C$ (donde se copia $f$ ) y su complemento (donde se ejecuta $g$ hacia atrás).

10. (a) La inclusión $\intoo01 \to \intcc01$ es inyectivo; y $x \mapsto \frac{x + 1}3$ aplicaciones $\intcc01$ inyectivamente en $\intcc{\frac13}{\frac23} \subseteq \intoo01$ (es afín con pendiente distinta de cero). Por pregunta 9, $\intcc01 \approx \intoo01$ — a biyección que es bastante desagradable de escribir explícitamente. (b) Inyectividad. Supongamos que $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 lado derecho es par y el lado izquierdo impar — imposible; entonces $p = p'$ , luego $2q + 1 = 2q' + 1$ y $q = q'$ . Surjetividad. Demostramos por inducción fuerte que todo número entero $m \geq 1$ tiene la forma $2^p(2q + 1)$ . Para $m = 1$ : $p = q = 0$ . Sea $m \geq 1$ y asuma el reclamo para todos los números 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)$ , entonces $m + 1 = 2^{p+1}(2q + 1)$ . Por lo tanto $\varphi(p, q) = 2^p(2q + 1) - 1$ llega a cada $n \in \N$ , y $\varphi$ es una biyección $\N \times \N \to \N$ .

11. Dado que $A$ es infinito, $A \setminus \{\varphi(0), \dots, \varphi(n - 1)\}$ nunca está vacío y la propiedad de elemento mínimo de $\N$ (usado para probar Teorema 1.12) hace el Definición recursiva legítima. 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)$ ; entonces $\varphi(n + 1) \geq \varphi(n)$ , y se excluye la igualdad, 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$ . Inyectividad se deriva de una estricta monotonicidad. Sobreyectividad sobre $A$ : supongamos que algo de $a \in A$ nunca lo es alcanzado. Desde $\varphi(a + 1) \geq a + 1 > a$ , el conjunto de $n$ con $\varphi(n) > a$ no está vacío; sea $n$ su elemento mínimo. por cada $k < n$ , $\varphi(k) \leq a$ , por lo tanto $\varphi(k) < a$ ( $a$ no es alcanzado). Entonces $a$ se encuentra en $A \setminus \{\varphi(0), \dots, \varphi(n - 1)\}$ y $a < \varphi(n)$ , contradiciendo la minimalidad definiendo $\varphi(n)$ . Entonces $\varphi$ es una biyección $\N \to A$ , y $A$ es contable.

12. Dejar $E \preceq \N$ mediante una inyección $f$ ; luego $E \approx f(E)$ (pregunta 2). Si $f(E)$ es finito, $E$ es finito; si $f(E)$ es infinita, la pregunta 11 da $f(E) \approx \N$ , entonces $E \approx \N$ por transitividad (pregunta 1). Por el contrario finitos conjuntos y conjuntos contables obviamente inyectar en $\N$ . El atajo: $E \preceq \N$ y $\N \preceq E$ dan $E \approx \N$ directamente por Cantor–Schröder–Bernstein — no se necesita 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 un inyección $E \times F \to \N$ : si las imágenes coinciden, inyectividad de $\varphi$ (pregunta 10) da $f(x) = f(x')$ y $g(y) = g(y')$ , luego $x = x'$ , $y = y'$ . Para $\Z \times \N^*$ : ambos factores son contable (pregunta 4), entonces $\Z \times \N^* \preceq \N$ ; es infinito (contiene $\{0\} \times \N^*$ ), por lo tanto contable por pregunta 12.

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

15. Para cada $n$ fijar una inyección $f_n \colon E_n \to \N$ . Para $x \in \bigcup_n E_n$ , sea $n(x)$ el el menos $n$ con $x \in E_n$ y establezca $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')$ , por lo tanto $x = x'$ por inyectividad de $f_n$ . Entonces la unión se inyecta en $\N$ : es, como mucho, contable.

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 elemento más grande en el que difieren, digamos $m \in F \setminus F'$ (intercambie nombres si es necesario). Los elementos $> m$ pertenecen a ambos o ninguno de los dos, por lo que contribuyen igualmente a ambas sumas; comparando el Aportes de 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 ,

utilizando la suma geométrica de Ejercicio 1.4. Por lo tanto $\Psi(F) \neq \Psi(F')$ : $\Psi$ es inyectivo y conjunto de subconjuntos finitos. de $\N$ es como máximo contable; es infinito (contiene todo singletons), por lo tanto contables.

17. Enviar $A \subseteq \N$ a su indicador $\mathbf 1_A \colon \N \to \{0,1\}$ , $\mathbf 1_A(n) = 1$ si $n \in A$ y $0$ de lo contrario; envíe $u \in \{0,1\}^{\N}$ a $A_u = \{n \in \N : u(n) = 1\}$ . Los dos aplicaciones son mutuamente inversos: $A_{\mathbf 1_A} = A$ y $\mathbf 1_{A_u} = u$ (verificar el valor en cada $n$ ). Por Teorema 1.24, cada uno es una biyección: $\mathcal{P}(\N) \approx \{0,1\}^{\N}$ .

18. Por cada $n$ , $d(n) = 1 - \Phi(n)(n) \neq \Phi(n)(n)$ , por lo que las secuencias $d$ y $\Phi(n)$ difieren en el índice $n$ : $d \neq \Phi(n)$ . Por lo tanto ningún $\Phi$ es sobreyectivo, y según la pregunta 3 hay tampoco hay inyección $\{0,1\}^{\N} \to \N$ : $\{0,1\}^{\N}$ no está en más contable. 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)\}$ (efectivamente $d(n) = 1 \iff \Phi(n)(n) = 0 \iff n \notin f(n)$ ): el argumento diagonal is Prueba de Cantor Ejercicio 1.11 para $E = \N$ .

19. Escriba $x_n = 0.d_1(n)\,d_2(n)\,d_3(n)\dots$ en forma adecuada. forme y defina $\delta_n = 5$ si $d_n(n) \neq 5$ , $\delta_n = 6$ si $d_n(n) = 5$ , entonces $x = 0.\delta_1\delta_2\delta_3\dots$ Este La expansión utiliza sólo los dígitos $5$ y $6$ , por lo que no termina en todos los $9$ : es la expansión adecuada de un $x \in \intco01$ real. Para cada $n$ , los dígitos $n$ de $x$ y $x_n$ difieren ( $\delta_n \neq d_n(n)$ por construcción); desde expansiones adecuadas son únicos, $x \neq x_n$ . Por lo tanto ninguna secuencia agota $\intco01$ : por Pregunta 3 nuevamente, $\intco01$ no es contable como máximo.

20. $\intco01 \subseteq \R$ , entonces una inyección $\R \to \N$ se limitaría a uno en $\intco01$ , contradiciendo la pregunta 19: $\R$ es incontable. Si $\R \setminus \Q$ fueran como máximo contables, entonces $\R = \Q \cup (\R \setminus \Q)$ sería una unión de dos en la mayoría conjuntos contables, por lo tanto, como máximo contable según la pregunta 15 (tome $E_0 = \Q$ , $E_n = \R \setminus \Q$ para $n \geq 1$ ) — contradicción. Entonces los irracionales son incontables. Precisamente: dentro de $\R$ , los racionales forman un conjunto contable mientras que sus el complemento es incontable; ninguna biyección puede coincidir jamás con $\R \setminus \Q$ con $\Q$ — hay estrictamente "más" irracionales que los racionales, aunque ambos son infinitos y densos.

21. $p/q$ (con $q \neq 0$ ) es una raíz de $qX - p$ , una polinomio distinto de cero con coeficientes enteros. $\sqrt 2$ es una raíz de $X^2 - 2$ . Para $x = \sqrt 2 + \sqrt 3$ : $x^2 = 5 + 2\sqrt 6$ , entonces $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 una raíz de $X^4 - 10X^2 + 1$ .

22. Aplicación $P = a_0 + a_1X + \dots + a_nX^n$ (grado $\leq n$ , coeficientes enteros) a $(a_0, \dots, a_n) \in \Z^{n+1}$ : esto es inyectivo, ya que un polinomio está determinado por sus coeficientes. Por inducción en $n$ : $\Z^1 = \Z$ es contable (pregunta 4), y $\Z^{n+2} \approx \Z^{n+1} \times \Z$ es contable como máximo por pregunta 13. Entonces, cada conjunto de polinomios enteros de grado acotado es como máximo contable; es infinito (contiene las constantes), por lo tanto contable por la pregunta 12.

23. El conjunto de todos los polinomios enteros es

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

unión contable de conjuntos contables: a lo sumo contable por la pregunta 15, e infinito, luego contable.

24. Para cada polinomio entero distinto de cero $P$ , la raíz conjunto $R_P = \{x \in \R : P(x) = 0\}$ es finito (como máximo $\deg P$ elementos, admitidos). Por la pregunta 23 los polinomios enteros distintos de cero se puede enumerar $P_0, P_1, P_2, \dots$ ; entonces $\mathcal{A} = \bigcup_{n \in \N} R_{P_n}$ es una unión contable de finitos (por lo tanto como máximo contable) conjuntos: como máximo contable según la pregunta 15. contiene $\Q$ (pregunta 21), por lo que es infinito: $\mathcal{A}$ es contable.

25. Si $\R \setminus \mathcal{A}$ fueran como máximo contables, $\R = \mathcal{A} \cup (\R \setminus \mathcal{A})$ sería como máximo contable (pregunta 15), contradiciendo la pregunta 20. Por lo tanto números trascendentales existen e incluso forman un conjunto incontable, mientras que el números algebraicos — que incluye todos los números construidos de números enteros por radicales — forman un mero esqueleto contable dentro de $\R$ . Resumen de la arquitectura: preguntas 1–3 conjunto hasta el lenguaje de comparación; Cantor–Schröder–Bernstein (preguntas 5–9) probemos la equipotencia mediante dos inyecciones fáciles en lugar de una biyección inteligente, y se usó para $\intcc01 \approx \intoo01$ , para $\Q$ y en toda la Parte V; la biyección de emparejamiento (pregunta 10) productos motorizados y uniones contables (preguntas 13, 15), que a su vez impulsó $\Q$ , los polinomios enteros y $\mathcal{A}$ ; el argumento diagonal (preguntas 18–19) proporcionado la única desigualdad estricta $\N \prec \R$ que constituye toda la historia no trivial. La conclusión de Cantor es filosóficamente sorprendente: la La prueba no muestra ningún numero trascendental en absoluto, pero muestra que en el sentido de equipotencia casi todos número real es trascendental. Nombrar un trascendental específico — $\pi$ o $\eu$ — requirió matemáticas completamente diferentes y décadas más trabajo.