6.2: Conjuntos Infinitos

Los sets infinitos son misteriosos. Muchas paradojas clásicas abordan confusiones históricas sobre la idea del infinito. Al mismo tiempo, a matemáticos de los antiguos griegos les ha resultado imposible desarrollar el pensamiento matemático sin el uso del infinito. ¿Por qué es así? Desde un punto de vista metafísico, la idea del infinito probablemente no sea necesaria. Desde un punto de vista físico, no hay evidencia de infinito. Es decir, el universo, tal y como lo entendemos, es finito. Incluso desde un punto de vista teológico, el infinito es en cierta medida el complemento de lo finito -y, en consecuencia, da origen a sus propias paradojas.

El infinito ha preocupado a algunos matemáticos y filósofos, y algunos han tratado de prescindir de él. No hay muchos adeptos a esta escuela. La idea del infinito es tan útil que el estudiante de matemáticas tendrá que desarrollar cierta comodidad con la idea -y sus consecuencias lógicas. En cualquier caso, el infinito existe claramente en el universo matemático, exista o no en el mundo natural, y usar el infinito ha sido crucial para desarrollar una comprensión matemática del mundo natural. En esta sección iniciamos una investigación de conjuntos infinitos.

Utilizaremos inyecciones y suryecciones para construir alguna maquinaria analítica para comparar conjuntos.

NOTACIÓN. \(\preceq\)Dejar\(X\) y\(Y\) ser conjuntos. Escribimos\(X \preceq Y\) si hay una inyección\[f: X \rightarrow Y \text {. }\] Esta notación sugiere que, bajo las condiciones de la definición, pensamos\(X\) que es “no mayor que” que\(Y\). Esto tiene sentido, ya que somos capaces de asociarnos a cualquier elemento de\(X\) un elemento distinto de\(Y\). Si\(f\) en la definición hay una sobreyección, entonces también\(f\) es una biyección y\(|X|=|Y|\). De lo contrario,\(f\) es una función que se asocia con cada elemento del rango de\(f\) (que es un subconjunto apropiado de\(Y\)) un elemento único de\(X\), y\(Y\) todavía tiene algunos elementos no contabilizados por \(f\). Entonces\(Y\) podría ser “más grande” que\(X\), pero ciertamente no será “más pequeño”. Es posible que desee considerar esta definición en el caso especial de conjuntos finitos\(X\) y\(Y\). Observarás que\[X \preceq Y \Longleftrightarrow|X| \leq|Y| .\] En el Ejercicio 6.3 se te pide que demuestres que\(\preceq\) es transitivo y reflexivo.

OBSERVACIÓN. ¿Hay dos conjuntos comparables con respecto a\(\preceq\)? Sorprendentemente, requiere de una suposición más avanzada, llamada Axioma de Elección (ver Apéndice B), para garantizar la comparabilidad de todos los pares de conjuntos. Prácticamente todos los matemáticos aceptan el Axioma de Elección. Asumiremos el Axioma de Elección en este texto.

Si\(X \preceq Y\) y\(Y \preceq X\), esperaríamos que\(X\) y\(Y\) sean del mismo tamaño. Esto es cierto, aunque la prueba es un poco complicada. El resultado es muy útil, ya que muchas veces es mucho más fácil anotar dos inyecciones que una biyección. TEOREMA 6.4. Teorema de Schröder-Bernstein Let\(X\) and\(Y\) be sets. Si\(X \preceq Y\) y\(Y \preceq X\), entonces\(|X|=|Y|\).

Discusión. La idea detrás de esta prueba es la siguiente. Lo demostramos\(|X|=|Y|\) construyendo una biyección\(F: X \nrightarrow Y\). Nos dan inyecciones\(f: X \rightarrow Y\) y\(g: Y \rightarrow X\). Construimos\(F\) usando las inyecciones\(f\) y\(g\) como guías. Es decir, queremos definir de\(F\) manera que para cada uno\(x \in X\), ya sea\(F(x)=f(x)\) o\(F(x)=g^{-1}(x)\). Es obvio que esto no se puede lograr ciegamente. Por ejemplo, si\(x \in X \backslash g[Y]\), nuestra mano es forzada, y\(F(x)=f(x)\). De igual manera\(y \in Y \backslash f[X]\), si, nuestra única oportunidad de lograr nuestro objetivo es para\(F(g(y))=y\). Si tomamos la decisión equivocada para\(F(x)\), perderemos el uso de\(f\) y\(g\) como guías. Podríamos considerar\(F\) indecisos sobre\(x\) desde entonces\(f\) y\(g^{-1}\) no estamos de acuerdo. La solución es usar\(f\) y movernos de un lado\(g\) a otro entre\(X\) y\(Y\) hasta que encontremos que nuestra mano está forzada.

Prueba. Dejar\[f: X \rightarrow Y\] y\[g: Y \rightarrow X\] ser inyecciones. Podemos suponer eso\(X\) y\(Y\) somos disjuntas.

Discusión. Si\(X\) y no\(Y\) son disjuntos, podemos reemplazar\(X\) con\(X \times\{0\}\) y\(Y\) con\(Y \times\{1\}\). La existencia de una biyección implica\[g: X \times\{0\} \mapsto Y \times\{1\}\] claramente la existencia de una biyección de\(X\) a\(Y\).

Si\(x \in X\) decimos\(y \in Y\) es el predecesor de\(x\) si\(g(y)=x\). Análogamente, si\(y \in Y\) decimos que\(x \in X\) es el antecesor de\(y\) if\(f(x)=y\). Es posible que un elemento no tenga predecesor. Por ejemplo, si\(x \in X \backslash g[Y]\), entonces no\(x\) tiene predecesor. Sin embargo, si un elemento sí tiene un predecesor, ese predecesor es único (ya que\(f\) y\(g\) son ambas inyecciones). Dado un elemento\(w\), deja\(m(w)\) ser 0 si\(w\) no tiene predecesor. De lo contrario, deje\(m(w)\) ser el número máximo\(N \geq 1\) tal que haya una secuencia finita\(\left\langle z_{n} \mid 0 \leq n \leq N\right\rangle\) para algunos\(N \geq 1\) satisfactorios

(1)\(w=z_{N}\)

(2) Porque\(n<N, z_{n}\) es el predecesor de\(z_{n+1}\), si existe el máximo. Si el máximo no existe (es decir, si se pueden hacer cadenas arbitrariamente largas de predecesores), vamos\(m(w)=\infty\).

Ahora define\[\begin{aligned} X_{e} &=\{x \in X \mid m(x) \text { is even }\} \\ X_{o} &=\{x \in X \mid m(x) \text { is odd }\} \\ X_{i} &=\{x \in X \mid m(x)=\infty\} \\ Y_{e} &=\{y \in Y \mid m(y) \text { is even }\} \\ Y_{o} &=\{y \in Y \mid m(y) \text { is odd }\} \\ Y_{i} &=\{y \in Y \mid m(y)=\infty\} \end{aligned}\] La colección\[\left\{X_{e}, X_{o}, X_{i}\right\}\] es obviamente una partición de\(X\). Del mismo modo,\[\left\{Y_{o}, Y_{e}, Y_{i}\right\}\] es una partición de\(Y\).

Ahora estamos en condiciones de definir una bijección entre\(X\) y\(Y\). Vamos\[F(x)=\left\{\begin{array}{ccc} f(x) & \text { if } & x \in X_{i} \\ f(x) & \text { if } & x \in X_{e} \\ g^{-1}(x) & \text { if } & x \in X_{o} . \end{array}\right.\] Discusión. Nos queda algo de trabajo en esta prueba. Tenemos que verificar que\(F\) es una bijección de\(X\) a\(Y\). La idea detrás de la definición de\(F\) puede no ser obvia, así que investiguemos la motivación para la definición. Supongamos\(g\) que\(f\) y no sean sobreyecciones (si alguna de las funciones es una suryección no habría nada que probar, ya que también sería una biyección). Dejar\(x \in X \backslash g[Y]\) y\(y \in Y \backslash f[X]\). Ya que\(x \notin g[Y]\), la única opción posible para\(F(x)\) es\(f(x)\). De igual manera\(y \notin f[X]\),, y el único valor posible de\(F^{-1}(y)\) es\(g(y)\). Pero esto no resuelve todos nuestros problemas. El conjunto\(X \backslash g[Y]\) está conformado por aquellos integrantes de los\(X\) que no tienen antecesores, y\(Y \backslash f[X]\) está integrado por los integrantes de\(Y\) sin antecesores. Si vamos a definir\(F\) juntando\(f\) y\(g\), encontramos que nuestras manos se vieron forzadas con estos conjuntos. Ahora supongamos que eso\(x \in X\) tiene exactamente un antecedente. Entonces no\(g^{-1}(x)\) tiene predecesor. Como observamos anteriormente, necesitamos satisfacer\[F^{-1}\left(g^{-1}(x)\right)=g\left(g^{-1}(x)\right)=x\] y por lo tanto debemos satisfacer\[F(x)=g^{-1}(x) .\] De igual manera, si\(y \in Y\) tiene exactamente un antecedente, debemos satisfacer\[F^{-1}(y)=f^{-1}(y) .\] Si un elemento\(w\) de\(X \cup Y\) tiene finitamente muchos antecedentes,\(\left.F\right|_{A(w)}\) estarán determinados por la restricción impuesta por el antecedente sin antecedente.

Afirmamos que\[F: X \mapsto Y .\] Se ve fácilmente que\(F\) está bien definido. Ya que\(X_{o} \subseteq g[Y]\) y\(g\) es una inyección,\(\left.F\right|_{X_{o}}=\left.g^{-1}\right|_{X_{o}}\) está bien definida. Eso\(F\) está bien definido\(X_{e}\) y\(X_{i}\) es obvio. Además\[\begin{gathered} F\left[X_{e}\right]=f\left[X_{e}\right]=Y_{o} \\ F\left[X_{o}\right]=g^{-1}\left[X_{o}\right]=Y_{e} \end{gathered}\] y\[F\left[X_{i}\right]=f\left[X_{i}\right]=Y_{i} .\] Discusión. Aunque no tuvimos otra opción en la definición de\(F\) on\(X_{e}\) y\(X_{o}\), podríamos haber definido\(F\) así que\(\left.F\right|_{X_{i}}=\left.g^{-1}\right|_{X_{i}}\).

Por lo tanto,

\(F[X]=F\left[X_{e} \cup X_{o} \cup X_{i}\right]=f\left[X_{e}\right] \cup g^{-1}\left[X_{o}\right] \cup f\left[X_{i}\right]=Y_{o} \cup Y_{e} \cup Y_{i}=Y .\)Así\(F\) es una sobrejección. Demostramos que\(F\) es una inyección. Vamos\(x, z \in X\), y supongamos\(F(x)=F(z)\). Si\(x \in X_{e}\), entonces\(F(x) \in Y_{o}\) y\(z \in X_{e}\). De ahí\[F(x)=f(x)=f(z)=F(z) .\] que Since\(f\) sea una inyección, así es\(\left.f\right|_{X_{e}}\). Por lo tanto\(x=z\).

Si\(x \in X_{o}\), entonces\(F(x) \in Y_{e}\) y\(z \in X_{o}\). Entonces\[F(x)=g^{-1}(x)=g^{-1}(z)=F(z) .\] La función\(g\) es una inyección, por lo tanto\(\left.g^{-1}\right|_{X_{o}}\) es una inyección y así\(x=z\).

Por último, si\(x \in X_{i}\), entonces\(F(x) \in X_{i}\) y\(z \in X_{i}\). Así\[F(x)=f(x)=f(z)=F(z) .\] que ya\(f\) es una inyección,\(x=z\).

Por lo tanto\(F\) es una inyección. De ahí,\[F: X \mapsto Y\] y\[|X|=|Y| .\] TEOROMA 6.5. \(\mathbb{N}\)es un conjunto infinito.

Discusión. Mostramos que cualquier función con dominio\(\ulcorner n\urcorner\), pues\(n \in\)\(\mathbb{N}\), no logra ser una suryección. Por lo tanto, no\(\mathbb{N}\) es finito.

Prueba. Asumir\(n \in \mathbb{N}\), y\[f:\ulcorner n\urcorner \longrightarrow \mathbb{N} .\] Let\[a=1+\sum_{i=0}^{n-1} f(i) \in \mathbb{N} .\] Claramente\(a \notin f[\ulcorner n\urcorner]\), así no\(f\) es una sobrejección. En consecuencia, no hay ninguna\(n \in \mathbb{N}\) que pueda ser mapeada de manera surjectiva\(\mathbb{N}\). Por lo tanto, no\(\mathbb{N}\) es finito. No sólo es\(\mathbb{N}\) un conjunto infinito, es en cierto sentido el conjunto infinito “más pequeño”.

TEOREMA 6.6. Si\(X\) es infinito, entonces\(\mathbb{N} \preceq X\).

Discusión. Definiremos una inyección\(f: \mathbb{N} \rightarrow X\) inductivamente, construyéndola paso a paso.

Prueba. Como\(X\) es infinito, no está vacío, por lo que debe contener algún elemento\(x_{0}\). Definir\(f(0)=x_{0}\).

Ahora, supongamos que todos\(x_{0}=f(0), x_{1}=f(1), \ldots, x_{n}=f(n)\) han sido elegidos, así que eso\[\left.f\right|_{\{0,1, \ldots, n\}}=\left.f\right|_{n+1\urcorner}: k \mapsto x_{k}\] es inyectivo. Como\(X\) es infinita, la función\(\left.f\right|_{\left.{ }_{n+1}\right\urcorner}\) que hemos definido no puede ser suryectiva. Entonces existe algunos\(x_{n+1}\) en\(X \backslash\left\{x_{0}, \ldots, x_{n}\right\}\). Definir\(f(n+1)=x_{n+1}\). Continuando de esta manera, alcanzamos una inyección\(f\) definida en todos\(\mathbb{N}\).

OBSERVACIÓN. El lector astuto pudo haber notado que en la prueba anterior, terminamos haciendo un número infinito de elecciones de elementos de\(X\).

DEFINICIÓN. Cardinalidad,\(\aleph_{0}\) Utilizamos la expresión\(\aleph_{0}\) (léase “aleph nought” 1) para el tamaño de\(\mathbb{N}\). Es decir\[\aleph_{0}:=|\mathbb{N}| \text {. }\] El tamaño de un conjunto se llama la cardinalidad del conjunto. Cualquier conjunto que sea biyective con\(\mathbb{N}\) tiene cardinalidad\(\aleph_{0}\). Un conjunto finito tiene cardinalidad igual al número natural único con el que es biyectiva.

DEFINICIÓN. Contable Un conjunto que es finito o tiene cardinalidad\(\aleph_{0}\) se denomina conjunto contable.

No estamos desarrollando formalmente la idea de cardinalidad. Esto requeriría trabajar con los ordinales, lo que nos distraería de intereses matemáticos más inmediatos. Sin embargo, usaremos el lenguaje

\({ }^{1} \aleph\)es la primera letra del alfabeto hebreo. y convenciones de cardenales donde es intuitiva y no interfiere con nuestro programa.