Sección 6. Conjuntos Finitos.
Hay al menos un par de alternativas a la hora de definir las nociones de conjunto finito e infinito.
Sin entrar en demasiada polémica, vamos a usar de aquí en adelante las definiciones tal como aparecen en el texto de Munkres, y quizá en algún momento discutamos alguna alternativa.
\( \bullet \) Definición. Sección inicial de enteros positivos. Se denomina sección o sección inicial de enteros positivos a todo conjunto de enteros positivos \( S_n \), para algún \( n \) entero positivo, donde:
\( \bullet \) Un conjunto \( A \) se dice finito si, o bien es vacío, o bien existe una función biyectiva \( f:A\to\{1,\cdots,n\} \) para algún entero positivo \( n \). En el primer caso, se dice que \( A \) tiene cardinal \( 0 \), y en el último caso se dice que \( A \) tiene cardinal \( n \).
En particular, el conjunto \( \{1,\cdots,n\} \) es un ejemplo trivial de cardinalidad \( n \), por ser biyectivo consigo mismo, que es la sección \( S_n \).
Por ser demasiado obvio a nuestra experiencia cotidiana, se nos ha pasado por alto quizá un tecnicismo matemático importante.
Hemos dado por obvio que dos conjuntos finitos que tienen cardinales distintos, tienen en verdad distinta "cantidad" de elementos, sin precisar demasiado bien lo que esto significa.
Y también hemos dejado entrever que si dos conjuntos finitos no son biyectivos entre sí, entonces sus cardinales son distintos.
¿Pero es esto cierto?
Digamos que dos conjuntos finitos tienen el mismo cardinal si son biyectivos entre sí, o sea, si hay una biyección entre ambos. Esta misma definición se usa también para el caso de conjuntos que no son finitos, pero lo veremos más adelante.
Munkres no define este término de equicardinalidad en esta sección, pero me parece apropiado hacerlo.
Aquellas cuestiones que nos parecen obvias sobre los números y los cardinales finitos, son susceptibles de ser demostradas matemáticamente, y en tal caso la prueba debe darse y estudiarse con seriedad.
Las pruebas en sí mismas ilustran sutilezas del trabajo matemático mismo, y es esa su importancia.
\( \bullet \) Lema 1. Sea \( n \) un entero positivo. Sea \( A \) un conjunto; sea \( a_0\in A \). Entonces existe una biyección \( f \) de \( A \) con \( \{1,\cdots,n+1\} \) si, y sólo si, hay una biyección \( g \) del conjunto \( A-\{a_0\} \) con \( \{1,\cdots,n\} \).
La demostración queda como ejercicio, como es costumbre en estas proposiciones de fácil deducción.
Aunque no duden en preguntar si no sale, o no se entiende.
Tan sólo recordar que como es una demostración con "si, y sólo si", requiere de dos partes, una "de ida" y otra "de vuelta".
Primero se supone que efectivamente existe la biyección \( g \) y se procura construir la biyección \( f \).
Y luego se parte de suponer la existencia de \( f \) y se construye \( g \), reordenando los elementos si hiciera falta, o sea, "rebuscándosela" para que la construcción funcione.
\( \bullet \) Teorema 2. Sea \( A \) un conjunto; suponer que existe una biyección \( f:A\to\{1,\cdots,n\} \) para algún \( n\in \mathbb Z_+ \). Sea \( B \subsetneqq A \). Entonces no existe biyección alguna \( g:B\to\{1,\cdots,n\} \); pero si \( B\neq\emptyset \), existe una biyección \( h:B\to\{1,\cdots,m\} \) para algún \( m<n \).
De nuevo, la demostración queda como ejercicio. Demos, sin embargo, algunas indicaciones de cómo proceder con la prueba. Se comienza estudiando el caso en que B es un conjunto vacío. Este caso es trivial, y es bueno descartarlo de entrada por ser diferente a los otros.
Luego se realiza una prueba por inducción en el número \( n \) del enunciado del Teorema (que corresponde al cardinal del conjunto de "llegada" de la biyección \( f \)).
Se forma la colección \( C \) de enteros positivos para los cuales el Teorema es cierto, y luego se procura demostrar que \( C \) es un conjunto inductivo. Es decir, que primero se debe demostrar que el Teorema es cierto cuando \( n=1 \). A continuación se supone que el Teorema es válido para un valor \( n \) genérico, y se procura demostrar que bajo ese supuesto, aún es cierto el Teorema para el valor \( n+1 \). En este paso inductivo se debe usar el Lema 1.
Se requiere un poco de reflexión y trabajo hasta que la prueba sale bien, pero tras unos minutos de atención, las cuentas salen sin dificultad.
En el texto de Munkres está completa, y si no, como siempre, pueden consultar si no sale o no se entiende.
Les recomiendo que presten mucha atención a los hechos que el Teorema exige demostrar, y que lo hagan con el detalle pertinente. Nada de dejar cabos sueltos. Es un ejercicio de exactitud, antes que todo, y por ello se requiere paciencia.
\( \bullet \) Corolario 3. Si \( A \) es finito, no existe una biyección de \( A \) con un subconjunto propio de sí mismo.
La demostración es un sencillo ejercicio, que consiste en hacer una prueba por reducción al absurdo, y aplicando el Teorema 2. Es, de nuevo, más tecnicismo.
La moraleja de este último resultado es que todo conjunto que es biyectivo con una parte propia de sí mismo, no puede ser finito.
Por esta razón, Dedekind tomó el camino de usar estas propiedades como base para definir las nociones de conjunto finito e infinito.
Decimos que un conjunto \( A \) es Dedekind-finito si es vacío o no existe biyección con una parte propia de sí mismo.
El Corolario anterior nos estaría diciendo ahora que un conjunto es finito si, y sólo si, es Dedekind-finito.
O sea, ambas definiciones resultan lógicamente equivalentes.
¿Y entonces para qué preocuparse? ¿Por qué no dejar la definición más clara de finitud, que habla de tener un cardinal \( n \), y punto?
Bueno, la ventaja de la definición de Dedekind es que el concepto de finitud no está atado a la existencia de un sistema como el de los enteros positivos.
\( \bullet \) Corolario 4. \( \mathbb{Z}_+ \) no es finito.
Esto se deduce del simple hecho de que existe una biyección de \( \mathbb{Z}_+ \) con un subconjunto propio, digamos \( \mathbb{Z}_+-\{1\} \). ¿Cuál sería?
\( \bullet \) Corolario 5. La cardinalidad de un conjunto finito \( A \) está unívocamente determinada por \( A \).
Esa manera tan pintoresca de enunciar un Corolario tan sólo significa que si \( A \) tiene asociado dos cardinales \( m,n, \) entonces en realidad son necesariamente el mismo, vale decir, \( m=n \).
La prueba se deja como ejercicio, y basta considerar por ejemplo el caso en que \( m<n \) y jugar con biyecciones, hasta obtener una contradicción con el Corolario 4.
\( \bullet \) Corolario 6. Si \( A \) es un conjunto finito, y si \( B\subset A \), entonces \( B \) es finito. Si \( B \subsetneqq A \), entonces la cardinalidad de \( B \) es menor que la cardinalidad de \( A \).
\( \bullet \) Corolario 7. Sea \( B \) un conjunto no vacío. Entonces las siguientes aserciones son equivalentes:
Cuando hay varias equivalencias, es práctico probarlas equivalencias "en círculo" para ahorrar trabajo.
Demostraremos que \( (1)\Rightarrow(2)\Rightarrow(3)\Rightarrow(1) \).
\( (1)\Rightarrow(2): \) Por definición de conjunto finito, como \( B\neq\emptyset \), existe una biyección \( f:\{1,\cdots,n\}\to B \) para algún entero positivo \( n \). Esta biyección sirve como suryección, y la prueba termina aquí.
\( (2)\Rightarrow(3): \) Si \( f:\{1,\cdots,n\}\to B \) es suryectiva, definir \( g:B\to\{1,\cdots,n\} \) por medio de la ecuación:
Como \( f \) es suryectiva, el conjunto \( f^{-1}(\{b\}) \) es no vacío; entonces la propiedad de buena-ordenación de \( \mathbb{Z}_+ \) implica que \( g(b) \) está bien definida y en forma unívoca.
Probemos que \( g \) es inyectiva. Si \( b\neq b' \), entonces los conjuntos \( f^{-1}(\{b\}) \) y \( f^{-1}(\{b'\}) \) son disjuntos, luego sus elementos mínimos han de ser necesariamente diferentes entre sí.
\( (3)\Rightarrow(1): \) Si \( g:B\to\{1,\cdots,n\} \) es inyectiva, entonces cambiando el rango de \( g \) se obtiene una biyección de \( B \) con un subconjunto de \( \{1,\cdots,n\} \). Se sigue del Corolario 6 que \( B \) es finito.
La prueba del Lema anterior es un calco de la dada en Munkres, y no ví razón para cambiarla.
Sin embargo, es posible apuntar aquí una sutil observación en lo que respecta a la prueba de que \( (2)\Rightarrow(3) \).
Notemos cómo es que allí se pudo obtener una inyección a partir de una suryección, con una aplicación de la propiedad de buena ordenación de \( \mathbb{Z}_+ \).
¿Hubiera sido posible dar una demostración similar sin recurrir a una propiedad como esa?
¿Qué es lo que esto significa?
En subsecuentes secciones veremos que la buena ordenación es equivalente al axioma de elección, un principio matemático muy controvertido.
Pareciera que un Corolario tan sencillo como el que estamos analizando aquí no puede "cerrarse" sin apelar a hechos "fuertes" como la buena ordenación.
Y después de todo, ¿qué es lo que hace que la buena ordenación haga el trabajo aquí?
Lo que realmente hace falta en la prueba es una regla que permita definir la función \( g \), de forma concreta. Algún "algoritmo" o "ley" que determine, a fin de cuentas, una "función" \( g \) bien construida, y que unívocamente determine un "valor" \( g(x) \) para cada \( x \) del dominio.
Al trabajar con funciones "suryectivas" surge el inconveniente de que las preimágenes no son necesariamente "únicas". Así que, ¿con qué criterio elegir una preimagen concreta para formar una nueva función? Si uno tiene una forma de hacerlo, bienvenido sea. Pero no siempre será así, y en el contexto general de la teoría de conjuntos sólo se puede echar mano de principios generales, como la propiedad de buena ordenación y sus equivalentes.
\( \bullet \) Corolario 8. Uniones finitas y productos cartesianos finitos de conjuntos finitos, son de nuevo finitos.
Dejamos los detalles como ejercicio, pero demos el esquema de la prueba.
Primero se debe probar que, si \( A,B \), son dos conjuntos finitos, su unión \( A\cup B \) es finita.
El caso en que se tienen conjuntos vacíos es trivial, y pasamos rápidamente a suponer que ambos \( A,B \), son no vacíos.
Se obtienen biyecciones \( f:\{1,\cdots,n\}\to A \) y \( g:\{1,\cdots,m\}\to B \), para ciertos \( n,m\in\mathbb{Z}_+ \), y luego se aprovechan para construir una suryección \( h:\{1,\cdots,m+n\}\to A\cup B \). Se aplica el Corolario 7 para decir que \( A\cup B \) es finito.
Nótese que es muy natural obtener ahí una suryección antes que una biyección. ¿Por qué?
Ahora, para una unión \( A_1\cup A_2\cup\cdots \cup A_k \) se procede por inducción en el índice \( k \).
Si \( A,B \), son finitos, se analiza lo que ocurre con \( A\times B \). Para ello es posible aprovechar lo hecho para las uniones.
Tomamos primero un elemento individual \( a\in A \), y observamos que el producto \( \{a\}\times B \) es obviamente finito. ¿Por qué?.
Si ahora hacemos \( A\times B=\bigcup_{a\in A}\{a\}\times B \), hemos logrado escribir el producto \( A\times B \) como una unión finita de conjuntos finitos.
Por el párrafo precedente, esto es un conjunto finito.
Finalmente, para un producto finito \( A_1\times A_2\times\cdots\times A_k \) de conjuntos finitos, se procede por inducción en el índice \( k \).
>> Clic aquí para Opiniones, preguntas y otros comentarios del curso: Topología (Munkres)
Sección 7. Conjuntos Numerables y No Numerables.
\( \bullet \) Definición. Un conjunto \( A \) se dice infinito si no es finito. Se dice que es infinito enumerable si hay una función biyectiva \( f:A\to\mathbb{Z}_+ \).
\( \bullet \) Ejemplo 1. El conjunto \( \mathbb{Z} \) de los enteros es infinito enumerable. ¿Qué biyección serviría para demostrarlo?
\( \bullet \) Ejemplo 2. El conjunto \( \mathbb{Z}_+\times\mathbb{Z}_+ \) es infinito enumerable. Para probarlo, sea \( A=\{(x,y)\in\mathbb{Z}_+\times\mathbb{Z}_+|x \leq y\} \), y defínanse las funciones \( f:\mathbb{Z}_+\times\mathbb{Z}_+\to A \), \( f(x,y)=(x+y-1,y) \), y \( g:A\to\mathbb{Z}_+ \), \( g(x,y)=\frac12(x-1)x+y \). Esas dos funciones son biyectivas (probarlo), y su composición es la biyección buscada.
\( \bullet \) Un conjunto se dice contable o numerable o enumerable si es finito o bien infinito enumerable. Si un conjunto no es numerable, se dice no-numerable.
Munkres enuncia y demuestra aquí un Teorema que, a fin de cuentas, necesita de una propiedad de los números enteros positivos denominada Principio de Definición Recursiva.
Lo que haremos nosotros es enunciarlo antes del Teorema, para que la estructura de la Sección sea más idónea.
Dicho Principio se da sin demostración, pero puede probarse. La prueba se da en la Sección 8.
La manera en que se enuncia este Principio a continuación es algo informal.
\( \bullet \) Principio de Definición Recursiva. Sea \( A \) un conjunto. Dada una fórmula que define \( h(1) \) como un elemento único de \( A \), y para \( i>1 \) define \( h(i) \) unívocamente como un elemento de \( A \) en términos de los valores de \( h \) para enteros positivos menores que \( i \), resulta que esta fórmula determina una única función \( h:\mathbb{Z}_+\to A \).
Este Principio permite utilizar ciertas fórmulas de recurrencia para definir algunas funciones cuyo dominio es \( \mathbb{Z}_+ \).
Cuando esto se lleva a cabo, suele decirse que se hace una definición por inducción o por recurrencia.
Sin un Principio de Definición por Recurrencia, las definiciones recursivas no podrían aceptarse.
\( \bullet \) Teorema 1. Sea \( B\neq\emptyset \). Las siguientes afirmaciones son equivalentes:
La demostración requiere seguir pasos similares al Corolario 7 de la Sección 6.
Sin embargo, en algunos casos conviene separar el análisis según que el conjunto \( B \) sea finito o no.
\( (1)\Rightarrow(2): \) El caso infinito es sencillo, y en el caso finito basta tomar una biyección entre alguna sección \( \{1,\cdots,n\} \) y \( B \) y "rellenarla" poniendo algún elemento arbitrario de \( B \) como valor de \( f(k) \) si \( k > n \).
\( (2)\Rightarrow(3): \) Se repite lo hecho en la Sección 6.
\( (3)\Rightarrow(1): \) Dada la inyección \( g \), se puede reducir su codominio para obtener una biyección entre \( B \) y un subconjunto \( C \) de \( \mathbb{Z}_+ \).
Como todo subconjunto de \( \mathbb{Z}_+ \) es numerable (este hecho lo probaremos en el Lema 2), resulta que \( C \) es numerable.
Esto implica que \( B \) es numerable.
\( \bullet \) Lema 2. Si \( C \) es un subconjunto infinito de \( \mathbb{Z}_+ \), entonces \( C \) es infinito enumerable.
Se debe definir una biyección \( h:\mathbb{Z}_+\to C \). El procedimiento es bastante típico, y se hace recursivamente.
Se pone \( h(1)=\textsf{minimo}(C) \), y asumiendo que los valores \( h(1),\cdots,h(n) \) han sido definidos, se estipula que \( h(n+1)=\textsf{minimo}(C-\{h(1),\cdots,h(n)\}) \).
Para que esta definición funcione, se requiere comprobar que es correcta, o sea, bien definida. Vale decir: el conjunto sobre el cual se está tomando el mínimo en cada paso debe ser no vacío.
Luego se debe comprobar que \( h \) es biyectiva, lo cual se hace chequeando por separado que es inyectiva y suryectiva.
Dejamos los detalles como ejercicio.
\( \bullet \) Corolario 3. Un subconjunto de un conjunto enumerable es enumerable.
La demostración queda como ejercicio.
\( \bullet \) Corolario 4. El conjunto \( \mathbb{Z}_+\times\mathbb{Z}_+ \) es infinito numerable.
Debido al Teorema 1, es suficiente construir una función inyectiva \( f:\mathbb{Z}_+\times\mathbb{Z}_+\to\mathbb{Z}_+ \). Definimos \( f \) como \( f(n,m)=2^n3^m \).
Es fácil verificar que \( f \) es inyectiva, y se deja como ejercicio (usar la paridad de las potencias de 2 y de 3).
\( \bullet \) Ejemplo. El conjunto \( \mathbb{Q}_+ \) de números racionales positivos es infinito enumerable. Se deja como ejercicio. Digamos al menos que se puede aprovechar la función suryectiva \( g:\mathbb{Z}_+\times\mathbb{Z}_+\to\mathbb{Q}_+ \) dada por \( g(n,m)=m/n \).
\( \bullet \) Teorema 5. Una unión numerable de conjuntos numerables es numerable.
Sea \( \{A_n\}_{n\in J} \) una familia de conjuntos numerables, donde el conjunto de índices \( J \) es \( \{1,\cdots,N\} \) o bien \( \mathbb{Z}_+ \).
Asumir que cada conjunto \( A_n\neq\emptyset \) (si se tuvieran en cuenta los conjuntos vacíos, no se agregaría elemento alguno a la unión total).
Como cada \( A_n \) es numerable, podemos elegir para cada \( n \) una función suryectiva \( f_n:\mathbb{Z}_+\to A_n \). Similarmente, podemos elegir una función suryectiva \( g:\mathbb{Z}_+\to J \).
Ahora definimos
La función \( h \) es suryectiva (verificarlo).
Como hay una biyección entre \( \mathbb{Z}_+\times\mathbb{Z}_+ \) y \( \mathbb{Z}_+ \), la numerabilidad de la unión se sigue del Teorema 1.
En esta demostración se utiliza una "elección" bastante arriegada.
Es cierto que para cada \( n \) existe una suryección \( f_n:\mathbb{Z}_+\to A_n \), pero no sabemos cuántas hay, o claramente cuáles son todas, y así, "elegir" una de ellas sin una "regla concreta" es algo que no podría hacerse, eventualmente.
Para poder hacerlo se ha de recurrir al Axioma de Elección.
Por un lado, este axioma es controvertido, pero por otro lado, se usa muy comunmente en matemática, y más aún en topología. Así que nosotros lo utilizaremos sin mayores pruritos.
Sin embargo, tengo una objeción de usar el Axioma de Elección en este punto. ¿Por qué? Bueno, por la sencilla razón de que el texto de Munkres introduce y estudia el Axioma de Elección en secciones posteriores.
¿Sería posible evitar el uso del Axioma de Elección, al menos en este punto?
Mi opinión es que esto no se puede conseguir.
Sin embargo, planteo una prueba alternativa, que busca aislar mejor dónde está el inconveniente, o sea, el punto crucial donde el Axioma de Elección se hace claramente inevitable.
Eso es lo que haré en los párrafos que siguen en color azul.
Segunda demostración del mismo Teorema.
Ciertamente, si definimos \( B_n=\bigcup_{m \leq n} A_n \), es posible demostrar por inducción que cada conjunto \( B_n \) es numerable. Más aún, forman una familia creciente de conjuntos: \( B_1\subset B_2\subset \cdots \).
Puede que se tenga una lista finita de estos conjuntos \( B_1,\cdots, B_N \), o bien que a partir de cierto índice \( N \) todos los conjuntos sean iguales: \( B_N=B_{N+1}=\cdots \)
En cualquier caso, la unión de la familia \( \{A_n\}_{n\in J} \) es igual a \( B_N \), que resulta pues numerable.
Supongamos el caso restante, a saber, que \( B_n \subsetneqq B_{n+1} \), todo \( n\in\mathbb{Z}_+ \).
Denotemos \( V=\bigcup_{n\in \mathbb{Z}_+} B_n \).
Ciertamente \( V \) debe ser un conjunto infinito (por qué).
Esto implica que existe algún \( n\in\mathbb{Z}_+ \) tal que \( B_{n} \) es infinito (¿por qué?).
Por buena ordenación de \( \mathbb{Z}_+ \), hay un mínimo \( n_0\in\mathbb{Z}_+ \) con esta propiedad.
Vamos a suponer, para simplificar la exposición, que \( B_1 \) es ya infinito, o sea, \( n_0=1 \), ya que la unión total \( V \) tendrá, después de todo, a todos los elementos que estamos considerando, pues la unión es "creciente".
/color]
Ahora definimos una función \( \beta:V\to\mathbb{Z}_+ \) que indica el mínimo índice \( n \) al que pertenece cada \( x\in V \), así:
Como cada \( B_n \) ahora es infinito numerable, para cada \( n \) existen funciones biyectivas de \( B_n \) en \( \mathbb{Z}_+ \) .
Denotemos \( \mathcal{F}_n \) a la familia de todas las funciones biyectivas \( f:B_n\to\mathbb{Z}_+ \).
Consideremos ahora una sucesión de funciones \( \sigma=\{f_n\}_{n\in\mathbb{Z}_+} \) tal que \( f_n\in \mathcal{F}_n \).
Hemos "elegido" un elemento \( f_n \) para cada \( n \) del conjunto infinito \( \mathbb{Z}_+ \).
O sea, hemos hecho uso del Axioma de Elección, aunque notemos que la colección \( \{\mathcal{F}_n|n\in\mathbb{Z}_+\} \) es sólo infinita numerable, por lo tanto es suficiente una versión numerable del Axioma de Elección.
Vamos a construir una función \( g_\sigma:V\to\mathbb{Z}_+ \) de la siguiente manera:
Para cada \( x\in V \), hacemos
Esta definición tiene pleno sentido, porque todo \( x\in V \) está presente en \( B_{\beta}(x) \), en cuyo caso \( x \) está en el dominio de \( f_{\beta(x)} \).
Ahora construyamos otra función \( h_\sigma:V\to\mathbb{Z}_+ \) de la siguiente manera:
Probemos que cualquiera de estas funciones es inyectiva. Sean pues \( x,y\in V \), y supongamos que \( h_\sigma(x)=h_\sigma(y) \).
Obtenemos que \( 2^{\beta(x)}3^{g_\sigma(x)}=2^{\beta(y)}3^{g_\sigma(y)} \).
Como los números 2 y 3 son coprimos entre sí, resulta que \( 2^{\beta(x)}=2^{\beta(y)} \), y \( 3^{g_\sigma(x)}=3^{g_\sigma(y)} \).
De la igualdad \( 2^{\beta(x)}=2^{\beta(y)} \), inferimos que \( \beta(x)=\beta(y) \).
Esto significa que el mínimo índice \( n \) tal que \( x\in B_n \) es el mismo para el que \( y\in B_n \).
O sea, existe un \( n_0 \) tal que \( x,y\in B_{n_0} \), y además \( n<n_0 \) implica que \( x,y\not\in B_n \).
En particular, las funciones \( f_{\beta(x)} \) y \( f_{\beta(y)} \) son iguales, o sea, "son" la función \( f_{n_0} \), siendo iguales sus dominios al conjunto \( B_{n_0} \).
Ahora, de la igualdad \( 3^{g_\sigma(x)}=3^{g_\sigma(y)} \), inferimos que \( {g_\sigma(x)}={g_\sigma(y)} \).
Pero esto quiere decir, por definición de \( g_\sigma \), que \( f_{\beta(x)}(x)=f_{\beta(y)}(y) \).
Mas, dado que \( f_{\beta(x)}=f_{n_0}=f_{\beta(y)} \), tenemos que \( f_{n_0}(x)=f_{n_0}(y) \).
Como \( f_{n_0} \) es una función biyectiva, esto demuestra que \( x=y \).
Ahora bien. Hemos probado que existe una función inyectiva \( h_\sigma \) de \( V \) en \( \mathbb{Z}_+ \).
Esto implica por el Teorema 1 que \( V \) es un conjunto numerable.
\( \bullet \) Teorema 6. El producto finito de conjuntos numerables es numerable.
¿Es cierto que el producto cartesiano numerable de conjuntos numerables es también numerable? Respuesta: NO.
\( \bullet \) Teorema 7. Sea \( X=\{0,1\} \). Entonces \( X^\omega \) es un conjunto no-numerable.
\( \bullet \) Ejercicio. Demostrar que si \( B\neq\emptyset \), y \( f:B\to C \) es inyectiva, entonces existe una función sobreyectiva \( g:C\to B \). ¿Cómo se construye \( g \)?
El siguiente Teorema da otro ejemplo de conjunto no-numerable, con \( A=\mathbb{Z}_+ \), por ejemplo.
\( \bullet \) Teorema 8. Sea \( A \) un conjunto. No existe aplicación inyectiva \( f:\mathcal{P}(A)\to A \), y tampoco existe aplicación sobreyectiva \( g:A\to \mathcal{P}(A) \).
En virtud del Ejercicio precedente, basta probar que una aplicación \( g:A\to\mathcal{P}(A) \) no puede ser sobreyectiva.
Así que supongamos por el absurdo que sí existe una tal \( g \) sobreyectiva.
Notemos que las imágenes de la función \( g \) son subconjuntos de \( A \).
Si \( a\in A \), se tiene que, o bien \( a\in g(a) \), o bien \( a\not\in g(a) \).
Sea
Se deja como ejercicio demostrar que \( B \) no está en la imagen de \( g \), o sea, no existe \( a_0\in A \) tal que \( f(a_0) \) es igual a \( B \).
(Si no sale, avisen, y completo con más detalles...)
En un capítulo posterior se demostrará que \( \mathbb{R} \) es un conjunto no-numerable.
No se hace aquí, porque sólo hemos dado los axiomas de los números reales, y faltaría agregar una larga serie de construcciones para tener más claro cómo proceder.
>> Clic aquí para Opiniones, preguntas y otros comentarios del curso: Topología (Munkres)
Sección 8. El Principio de Definición Recursiva.
Esta sección es interesante, pero tiene resultados muy estandarizados de la teoría de conjuntos.
No quisiera perder tiempo con ellos, aún cuando a mí mismo me gustan muchísimo estos temas de las definiciones por recurrencia y cuestiones relacionadas.
No obstante, si cualquiera de ustedes desea más detalles, explicaciones, o quiere profundizar en todo esto, basta conque lo diga y nos sumergimos en el tema.
Sea \( C\subset \mathbb{Z}_+ \) un conjunto infinito.
Nos preguntamos si es posible definir una función \( h:\mathbb{Z}_+\to C \) que satisfaga:
\( (*)\qquad h(1)=\min(C),\qquad h(i)=\min(C-h(\{1,\cdots,i-1\})),\qquad i> 1. \)
Primero se estudian funciones definidas por secciones \( \{1,\cdots,n\} \), y luego se pasa al caso de todo \( \mathbb{Z}_+ \).
\( \bullet \) Lema 1. Dado \( n\in\mathbb{Z}_+ \), existe una función
que satisface \( (*) \) para todo \( i=1,\cdots,n \).
Se deja como ejercicio.
Basta proceder por inducción en el número \( n \) de elementos del dominio de \( f \), y prestando atención a la forma de \( h \) en \( (*) \).
\( \bullet \) Lema 2. Si \( f:\{1,\cdots,n\}\to C \) y \( g:\{1,\cdots,m\}\to C \) son funciones que verifican \( (*) \) en sus respectivos dominios, entonces \( f(i)=g(i) \), para todo \( i \) que esté en ambos dominios al mismo tiempo.
Se deja como ejercicio.
Se puede proceder por reducción al absurdo, e invocando el hecho de que todo conjunto de enteros positivos tiene un mínimo.
\( \bullet \) Teorema 3. Existe una única función \( h:\mathbb{Z}_+\to C \) que verifica \( (*) \) para todo \( i\in\mathbb{Z}_+ \).
Se dejan los detalles como ejercicio.
Basta notar que, por los Lemas 1 y 2, para cada \( n \) existe una única función \( f_n:\{1,\cdots,n\}\to C \) que verifica \( (*) \).
Recordar que una función es un conjunto formado por pares ordenados.
Así que tiene sentido definir el conjunto de pares ordenados \( f=\bigcup_{n\in\mathbb{Z}_+} f_n \).
Se debe demostar que \( f \) es una función con dominio \( \mathbb{Z}_+ \).
O sea, hay que constatar que se cumple la regla de unicidad de la imagen.
También hay que chequear (fácil) que se cumple \( (*) \) para todo \( i\in\mathbb{Z}_+ \).
Finalmente, hay que explicar que \( h \) es única. (Aprovechar el Lema 2 para obtener unicidad).
\( \bullet \) Teorema 4 (Principio de definición recursiva). Sean \( A \) un conjunto y \( a_0\in A \). Supongamos que \( \rho \) es una función que asigna un elemento de \( A \) a cada función \( f \), con dominio una sección no vacía de enteros positivos e imagen en \( A \). Entonces existe una única función
tal que
\( (*)\qquad h(1)=a_0,\qquad h(i)=\rho (h|\{1,\cdots,i-1\}),\qquad i> 1. \)
Demostración: Sigue ideas muy similares a los resultados previos. Salvo que ahora la función \( h \) no cumple \( (*) \) sino una regla general.
_____________
\( \bullet \) La fórmula \( (*) \) se llama fórmula recursiva para \( h \).
La idea general es que uno está "autorizado" a definir una función mediante una fórmula de recurrencia.
Vale decir, si uno especifica una fórmula de recurrencia, ésta nos define correctamente una función, y sin ambigüedad, ya que el Teorema anterior nos garantiza que existe al menos una función que satisface la recurrencia (la recurrencia es algo con "sentido"), y además dicha función es única (la recurrencia es "inambigua").
Notemos algunos detalles técnicos. El dominio de la función \( \rho \) del Teorema 4 es un conjunto muy complicado.
Sea \( \mathcal{F}_n \) la familia de todas las funciones \( f:\{1,\cdots,n\}\to A \).
Entonces el dominio de \( \rho \) es la unión \( \bigcup_{n\in\mathbb{Z}_+} \mathcal{F}_n \).
La imagen de \( \rho \) es un subconjunto de \( A \).
Así que podemos anotar:
Ahora bien, la función \( h \) del "discurso" del Teorema 4 tiene como dominio todo el conjunto \( \mathbb{Z}_+ \), y no meras secciones.
Sin embargo, se pueden considerar las restricciones de \( h \) a secciones \( \{1,\cdots,i-1\} \).
Estas funciones "restricción" se indican, como es costumbre, con el símbolo \( | \), así: \( h|\{1,\cdots,i-1\} \), y así se obiene un "objeto" de \( \mathcal{F}_{i-1} \), al cual es válido aplicarle la función \( \rho \).
\( \bullet \) Ejemplo 1. Comprobar que el Teorema 3 es un caso particular del Teorema 4. Basta definir:
\( \bullet \) Ejemplo 2. Definir rigurosamente las potencias \( a^n \), con \( a\in\mathbb{R} \) y \( n\in\mathbb{Z}_+ \), mediante la fórmula de recurrencia:
Sugerencia: Utilizar \( \rho (f)=f(m)\cdot a \), si el dominio de \( f \) es \( \{1,\cdots,m\} \).
>> Clic aquí para Opiniones, preguntas y otros comentarios del curso: Topología (Munkres)
Hay al menos un par de alternativas a la hora de definir las nociones de conjunto finito e infinito.
Sin entrar en demasiada polémica, vamos a usar de aquí en adelante las definiciones tal como aparecen en el texto de Munkres, y quizá en algún momento discutamos alguna alternativa.
\( \bullet \) Definición. Sección inicial de enteros positivos. Se denomina sección o sección inicial de enteros positivos a todo conjunto de enteros positivos \( S_n \), para algún \( n \) entero positivo, donde:
\( S_n=\{1,2,\cdots,n\}. \)
\( \bullet \) Un conjunto \( A \) se dice finito si, o bien es vacío, o bien existe una función biyectiva \( f:A\to\{1,\cdots,n\} \) para algún entero positivo \( n \). En el primer caso, se dice que \( A \) tiene cardinal \( 0 \), y en el último caso se dice que \( A \) tiene cardinal \( n \).
En particular, el conjunto \( \{1,\cdots,n\} \) es un ejemplo trivial de cardinalidad \( n \), por ser biyectivo consigo mismo, que es la sección \( S_n \).
Por ser demasiado obvio a nuestra experiencia cotidiana, se nos ha pasado por alto quizá un tecnicismo matemático importante.
Hemos dado por obvio que dos conjuntos finitos que tienen cardinales distintos, tienen en verdad distinta "cantidad" de elementos, sin precisar demasiado bien lo que esto significa.
Y también hemos dejado entrever que si dos conjuntos finitos no son biyectivos entre sí, entonces sus cardinales son distintos.
¿Pero es esto cierto?
Digamos que dos conjuntos finitos tienen el mismo cardinal si son biyectivos entre sí, o sea, si hay una biyección entre ambos. Esta misma definición se usa también para el caso de conjuntos que no son finitos, pero lo veremos más adelante.
Munkres no define este término de equicardinalidad en esta sección, pero me parece apropiado hacerlo.
Aquellas cuestiones que nos parecen obvias sobre los números y los cardinales finitos, son susceptibles de ser demostradas matemáticamente, y en tal caso la prueba debe darse y estudiarse con seriedad.
Las pruebas en sí mismas ilustran sutilezas del trabajo matemático mismo, y es esa su importancia.
\( \bullet \) Lema 1. Sea \( n \) un entero positivo. Sea \( A \) un conjunto; sea \( a_0\in A \). Entonces existe una biyección \( f \) de \( A \) con \( \{1,\cdots,n+1\} \) si, y sólo si, hay una biyección \( g \) del conjunto \( A-\{a_0\} \) con \( \{1,\cdots,n\} \).
La demostración queda como ejercicio, como es costumbre en estas proposiciones de fácil deducción.
Aunque no duden en preguntar si no sale, o no se entiende.
Tan sólo recordar que como es una demostración con "si, y sólo si", requiere de dos partes, una "de ida" y otra "de vuelta".
Primero se supone que efectivamente existe la biyección \( g \) y se procura construir la biyección \( f \).
Y luego se parte de suponer la existencia de \( f \) y se construye \( g \), reordenando los elementos si hiciera falta, o sea, "rebuscándosela" para que la construcción funcione.
\( \bullet \) Teorema 2. Sea \( A \) un conjunto; suponer que existe una biyección \( f:A\to\{1,\cdots,n\} \) para algún \( n\in \mathbb Z_+ \). Sea \( B \subsetneqq A \). Entonces no existe biyección alguna \( g:B\to\{1,\cdots,n\} \); pero si \( B\neq\emptyset \), existe una biyección \( h:B\to\{1,\cdots,m\} \) para algún \( m<n \).
De nuevo, la demostración queda como ejercicio. Demos, sin embargo, algunas indicaciones de cómo proceder con la prueba. Se comienza estudiando el caso en que B es un conjunto vacío. Este caso es trivial, y es bueno descartarlo de entrada por ser diferente a los otros.
Luego se realiza una prueba por inducción en el número \( n \) del enunciado del Teorema (que corresponde al cardinal del conjunto de "llegada" de la biyección \( f \)).
Se forma la colección \( C \) de enteros positivos para los cuales el Teorema es cierto, y luego se procura demostrar que \( C \) es un conjunto inductivo. Es decir, que primero se debe demostrar que el Teorema es cierto cuando \( n=1 \). A continuación se supone que el Teorema es válido para un valor \( n \) genérico, y se procura demostrar que bajo ese supuesto, aún es cierto el Teorema para el valor \( n+1 \). En este paso inductivo se debe usar el Lema 1.
Se requiere un poco de reflexión y trabajo hasta que la prueba sale bien, pero tras unos minutos de atención, las cuentas salen sin dificultad.
En el texto de Munkres está completa, y si no, como siempre, pueden consultar si no sale o no se entiende.
Les recomiendo que presten mucha atención a los hechos que el Teorema exige demostrar, y que lo hagan con el detalle pertinente. Nada de dejar cabos sueltos. Es un ejercicio de exactitud, antes que todo, y por ello se requiere paciencia.
\( \bullet \) Corolario 3. Si \( A \) es finito, no existe una biyección de \( A \) con un subconjunto propio de sí mismo.
La demostración es un sencillo ejercicio, que consiste en hacer una prueba por reducción al absurdo, y aplicando el Teorema 2. Es, de nuevo, más tecnicismo.
La moraleja de este último resultado es que todo conjunto que es biyectivo con una parte propia de sí mismo, no puede ser finito.
Por esta razón, Dedekind tomó el camino de usar estas propiedades como base para definir las nociones de conjunto finito e infinito.
Decimos que un conjunto \( A \) es Dedekind-finito si es vacío o no existe biyección con una parte propia de sí mismo.
El Corolario anterior nos estaría diciendo ahora que un conjunto es finito si, y sólo si, es Dedekind-finito.
O sea, ambas definiciones resultan lógicamente equivalentes.
¿Y entonces para qué preocuparse? ¿Por qué no dejar la definición más clara de finitud, que habla de tener un cardinal \( n \), y punto?
Bueno, la ventaja de la definición de Dedekind es que el concepto de finitud no está atado a la existencia de un sistema como el de los enteros positivos.
\( \bullet \) Corolario 4. \( \mathbb{Z}_+ \) no es finito.
Esto se deduce del simple hecho de que existe una biyección de \( \mathbb{Z}_+ \) con un subconjunto propio, digamos \( \mathbb{Z}_+-\{1\} \). ¿Cuál sería?
\( \bullet \) Corolario 5. La cardinalidad de un conjunto finito \( A \) está unívocamente determinada por \( A \).
Esa manera tan pintoresca de enunciar un Corolario tan sólo significa que si \( A \) tiene asociado dos cardinales \( m,n, \) entonces en realidad son necesariamente el mismo, vale decir, \( m=n \).
La prueba se deja como ejercicio, y basta considerar por ejemplo el caso en que \( m<n \) y jugar con biyecciones, hasta obtener una contradicción con el Corolario 4.
\( \bullet \) Corolario 6. Si \( A \) es un conjunto finito, y si \( B\subset A \), entonces \( B \) es finito. Si \( B \subsetneqq A \), entonces la cardinalidad de \( B \) es menor que la cardinalidad de \( A \).
\( \bullet \) Corolario 7. Sea \( B \) un conjunto no vacío. Entonces las siguientes aserciones son equivalentes:
- (1) \( B \) es finito.
- (2) Hay una función suryectiva de una sección de los enteros positivos sobre \( B \).
- (3) Hay una función inyectiva de \( B \) en una sección de los enteros positivos.
Demostración
Cuando hay varias equivalencias, es práctico probarlas equivalencias "en círculo" para ahorrar trabajo.
Demostraremos que \( (1)\Rightarrow(2)\Rightarrow(3)\Rightarrow(1) \).
\( (1)\Rightarrow(2): \) Por definición de conjunto finito, como \( B\neq\emptyset \), existe una biyección \( f:\{1,\cdots,n\}\to B \) para algún entero positivo \( n \). Esta biyección sirve como suryección, y la prueba termina aquí.
\( (2)\Rightarrow(3): \) Si \( f:\{1,\cdots,n\}\to B \) es suryectiva, definir \( g:B\to\{1,\cdots,n\} \) por medio de la ecuación:
\( g(b)=\textsf{el elemento mínimo de\ } f^{-1}(\{b\}). \)
Como \( f \) es suryectiva, el conjunto \( f^{-1}(\{b\}) \) es no vacío; entonces la propiedad de buena-ordenación de \( \mathbb{Z}_+ \) implica que \( g(b) \) está bien definida y en forma unívoca.
Probemos que \( g \) es inyectiva. Si \( b\neq b' \), entonces los conjuntos \( f^{-1}(\{b\}) \) y \( f^{-1}(\{b'\}) \) son disjuntos, luego sus elementos mínimos han de ser necesariamente diferentes entre sí.
\( (3)\Rightarrow(1): \) Si \( g:B\to\{1,\cdots,n\} \) es inyectiva, entonces cambiando el rango de \( g \) se obtiene una biyección de \( B \) con un subconjunto de \( \{1,\cdots,n\} \). Se sigue del Corolario 6 que \( B \) es finito.
La prueba del Lema anterior es un calco de la dada en Munkres, y no ví razón para cambiarla.
Sin embargo, es posible apuntar aquí una sutil observación en lo que respecta a la prueba de que \( (2)\Rightarrow(3) \).
Notemos cómo es que allí se pudo obtener una inyección a partir de una suryección, con una aplicación de la propiedad de buena ordenación de \( \mathbb{Z}_+ \).
¿Hubiera sido posible dar una demostración similar sin recurrir a una propiedad como esa?
¿Qué es lo que esto significa?
En subsecuentes secciones veremos que la buena ordenación es equivalente al axioma de elección, un principio matemático muy controvertido.
Pareciera que un Corolario tan sencillo como el que estamos analizando aquí no puede "cerrarse" sin apelar a hechos "fuertes" como la buena ordenación.
Y después de todo, ¿qué es lo que hace que la buena ordenación haga el trabajo aquí?
Lo que realmente hace falta en la prueba es una regla que permita definir la función \( g \), de forma concreta. Algún "algoritmo" o "ley" que determine, a fin de cuentas, una "función" \( g \) bien construida, y que unívocamente determine un "valor" \( g(x) \) para cada \( x \) del dominio.
Al trabajar con funciones "suryectivas" surge el inconveniente de que las preimágenes no son necesariamente "únicas". Así que, ¿con qué criterio elegir una preimagen concreta para formar una nueva función? Si uno tiene una forma de hacerlo, bienvenido sea. Pero no siempre será así, y en el contexto general de la teoría de conjuntos sólo se puede echar mano de principios generales, como la propiedad de buena ordenación y sus equivalentes.
[cerrar]
\( \bullet \) Corolario 8. Uniones finitas y productos cartesianos finitos de conjuntos finitos, son de nuevo finitos.
Demostración
Dejamos los detalles como ejercicio, pero demos el esquema de la prueba.
Primero se debe probar que, si \( A,B \), son dos conjuntos finitos, su unión \( A\cup B \) es finita.
El caso en que se tienen conjuntos vacíos es trivial, y pasamos rápidamente a suponer que ambos \( A,B \), son no vacíos.
Se obtienen biyecciones \( f:\{1,\cdots,n\}\to A \) y \( g:\{1,\cdots,m\}\to B \), para ciertos \( n,m\in\mathbb{Z}_+ \), y luego se aprovechan para construir una suryección \( h:\{1,\cdots,m+n\}\to A\cup B \). Se aplica el Corolario 7 para decir que \( A\cup B \) es finito.
Nótese que es muy natural obtener ahí una suryección antes que una biyección. ¿Por qué?
Ahora, para una unión \( A_1\cup A_2\cup\cdots \cup A_k \) se procede por inducción en el índice \( k \).
Si \( A,B \), son finitos, se analiza lo que ocurre con \( A\times B \). Para ello es posible aprovechar lo hecho para las uniones.
Tomamos primero un elemento individual \( a\in A \), y observamos que el producto \( \{a\}\times B \) es obviamente finito. ¿Por qué?.
Si ahora hacemos \( A\times B=\bigcup_{a\in A}\{a\}\times B \), hemos logrado escribir el producto \( A\times B \) como una unión finita de conjuntos finitos.
Por el párrafo precedente, esto es un conjunto finito.
Finalmente, para un producto finito \( A_1\times A_2\times\cdots\times A_k \) de conjuntos finitos, se procede por inducción en el índice \( k \).
[cerrar]
Ejercicios Sección 6
- Ejercicio 6.1
- (a) Hacer una lista de todas las funciones inyectivas \( f:\{1,2,3\}\to\{1,2,3,4\} \).
Muestre que ninguna es biyectiva. - (b) ¿Cuántas funciones inyectivas \( f:\{1,\cdots,8\}\to\{1,\cdots,10\} \) hay?
- (a) Hacer una lista de todas las funciones inyectivas \( f:\{1,2,3\}\to\{1,2,3,4\} \).
- Ejercicio 6.2 Muestre que si \( B \) no es finito y \( B\subset A \), entonces \( A \) no es finito.
- Ejercicio 6.3 Sea \( X=\{0,1\} \). Halle una biyección entre \( X^\omega \) y un subconjunto propio de sí mismo.
- Ejercicio 6.4 Sea \( A \) un conjunto finito no vacío simplemente ordenado (estrictamente).
- (a) Muestre que \( A \) tiene un elemento máximo. (Ayuda: proceda por inducción en el cardinal de \( A \)).
- (b) Muestre que \( A \) tiene el tipo de orden de una sección de los enteros positivos.
- (a) Muestre que \( A \) tiene un elemento máximo. (Ayuda: proceda por inducción en el cardinal de \( A \)).
- Ejercicio 6.5 Si \( A\times B \) es finito, ¿se deduce que \( A \) y \( B \) son también finitos?
- Ejercicio 6.6
- (a) Sea \( A=\{1,\cdots,n\} \). Mostrar que hay una biyección de \( \mathcal{P}(A) \) con el producto cartesiano \( X^n \), donde \( X \) es el conjunto \( X=\{0,1\} \).
- (b) Muestre que si \( A \) es finito, entonces \( \mathcal{P}(A) \) es finito.
- (a) Sea \( A=\{1,\cdots,n\} \). Mostrar que hay una biyección de \( \mathcal{P}(A) \) con el producto cartesiano \( X^n \), donde \( X \) es el conjunto \( X=\{0,1\} \).
- Ejercicio 6.7 Si \( A,B \) son finitos, mostrar que el conjunto de todas las funciones \( f:A\to B \) es finito.
[cerrar]
>> Clic aquí para Opiniones, preguntas y otros comentarios del curso: Topología (Munkres)
Sección 7. Conjuntos Numerables y No Numerables.
\( \bullet \) Definición. Un conjunto \( A \) se dice infinito si no es finito. Se dice que es infinito enumerable si hay una función biyectiva \( f:A\to\mathbb{Z}_+ \).
\( \bullet \) Ejemplo 1. El conjunto \( \mathbb{Z} \) de los enteros es infinito enumerable. ¿Qué biyección serviría para demostrarlo?
\( \bullet \) Ejemplo 2. El conjunto \( \mathbb{Z}_+\times\mathbb{Z}_+ \) es infinito enumerable. Para probarlo, sea \( A=\{(x,y)\in\mathbb{Z}_+\times\mathbb{Z}_+|x \leq y\} \), y defínanse las funciones \( f:\mathbb{Z}_+\times\mathbb{Z}_+\to A \), \( f(x,y)=(x+y-1,y) \), y \( g:A\to\mathbb{Z}_+ \), \( g(x,y)=\frac12(x-1)x+y \). Esas dos funciones son biyectivas (probarlo), y su composición es la biyección buscada.
\( \bullet \) Un conjunto se dice contable o numerable o enumerable si es finito o bien infinito enumerable. Si un conjunto no es numerable, se dice no-numerable.
Munkres enuncia y demuestra aquí un Teorema que, a fin de cuentas, necesita de una propiedad de los números enteros positivos denominada Principio de Definición Recursiva.
Lo que haremos nosotros es enunciarlo antes del Teorema, para que la estructura de la Sección sea más idónea.
Dicho Principio se da sin demostración, pero puede probarse. La prueba se da en la Sección 8.
La manera en que se enuncia este Principio a continuación es algo informal.
\( \bullet \) Principio de Definición Recursiva. Sea \( A \) un conjunto. Dada una fórmula que define \( h(1) \) como un elemento único de \( A \), y para \( i>1 \) define \( h(i) \) unívocamente como un elemento de \( A \) en términos de los valores de \( h \) para enteros positivos menores que \( i \), resulta que esta fórmula determina una única función \( h:\mathbb{Z}_+\to A \).
Este Principio permite utilizar ciertas fórmulas de recurrencia para definir algunas funciones cuyo dominio es \( \mathbb{Z}_+ \).
Cuando esto se lleva a cabo, suele decirse que se hace una definición por inducción o por recurrencia.
Sin un Principio de Definición por Recurrencia, las definiciones recursivas no podrían aceptarse.
\( \bullet \) Teorema 1. Sea \( B\neq\emptyset \). Las siguientes afirmaciones son equivalentes:
- (1) \( B \) es enumerable.
- (2) Hay una función suryectiva \( f:\mathbb{Z}_+\to B \).
- (3) Hay una función inyectiva \( g:B\to\mathbb{Z}_+ \).
Demostración
La demostración requiere seguir pasos similares al Corolario 7 de la Sección 6.
Sin embargo, en algunos casos conviene separar el análisis según que el conjunto \( B \) sea finito o no.
\( (1)\Rightarrow(2): \) El caso infinito es sencillo, y en el caso finito basta tomar una biyección entre alguna sección \( \{1,\cdots,n\} \) y \( B \) y "rellenarla" poniendo algún elemento arbitrario de \( B \) como valor de \( f(k) \) si \( k > n \).
\( (2)\Rightarrow(3): \) Se repite lo hecho en la Sección 6.
\( (3)\Rightarrow(1): \) Dada la inyección \( g \), se puede reducir su codominio para obtener una biyección entre \( B \) y un subconjunto \( C \) de \( \mathbb{Z}_+ \).
Como todo subconjunto de \( \mathbb{Z}_+ \) es numerable (este hecho lo probaremos en el Lema 2), resulta que \( C \) es numerable.
Esto implica que \( B \) es numerable.
[cerrar]
\( \bullet \) Lema 2. Si \( C \) es un subconjunto infinito de \( \mathbb{Z}_+ \), entonces \( C \) es infinito enumerable.
Demostración
Se debe definir una biyección \( h:\mathbb{Z}_+\to C \). El procedimiento es bastante típico, y se hace recursivamente.
Se pone \( h(1)=\textsf{minimo}(C) \), y asumiendo que los valores \( h(1),\cdots,h(n) \) han sido definidos, se estipula que \( h(n+1)=\textsf{minimo}(C-\{h(1),\cdots,h(n)\}) \).
Para que esta definición funcione, se requiere comprobar que es correcta, o sea, bien definida. Vale decir: el conjunto sobre el cual se está tomando el mínimo en cada paso debe ser no vacío.
Luego se debe comprobar que \( h \) es biyectiva, lo cual se hace chequeando por separado que es inyectiva y suryectiva.
Dejamos los detalles como ejercicio.
[cerrar]
\( \bullet \) Corolario 3. Un subconjunto de un conjunto enumerable es enumerable.
La demostración queda como ejercicio.
\( \bullet \) Corolario 4. El conjunto \( \mathbb{Z}_+\times\mathbb{Z}_+ \) es infinito numerable.
Demostración
Debido al Teorema 1, es suficiente construir una función inyectiva \( f:\mathbb{Z}_+\times\mathbb{Z}_+\to\mathbb{Z}_+ \). Definimos \( f \) como \( f(n,m)=2^n3^m \).
Es fácil verificar que \( f \) es inyectiva, y se deja como ejercicio (usar la paridad de las potencias de 2 y de 3).
[cerrar]
\( \bullet \) Ejemplo. El conjunto \( \mathbb{Q}_+ \) de números racionales positivos es infinito enumerable. Se deja como ejercicio. Digamos al menos que se puede aprovechar la función suryectiva \( g:\mathbb{Z}_+\times\mathbb{Z}_+\to\mathbb{Q}_+ \) dada por \( g(n,m)=m/n \).
\( \bullet \) Teorema 5. Una unión numerable de conjuntos numerables es numerable.
Demostración (se dan dos pruebas alternativas, y se discute el uso del Axioma de Elección)
Sea \( \{A_n\}_{n\in J} \) una familia de conjuntos numerables, donde el conjunto de índices \( J \) es \( \{1,\cdots,N\} \) o bien \( \mathbb{Z}_+ \).
Asumir que cada conjunto \( A_n\neq\emptyset \) (si se tuvieran en cuenta los conjuntos vacíos, no se agregaría elemento alguno a la unión total).
Como cada \( A_n \) es numerable, podemos elegir para cada \( n \) una función suryectiva \( f_n:\mathbb{Z}_+\to A_n \). Similarmente, podemos elegir una función suryectiva \( g:\mathbb{Z}_+\to J \).
Ahora definimos
\( \displaystyle h:\mathbb{Z}_+\times\mathbb{Z}_+\to\bigcup_{n\in J}A_n;\qquad\qquad h(k,m)=f_{g(k)}(m). \)
La función \( h \) es suryectiva (verificarlo).
Como hay una biyección entre \( \mathbb{Z}_+\times\mathbb{Z}_+ \) y \( \mathbb{Z}_+ \), la numerabilidad de la unión se sigue del Teorema 1.
En esta demostración se utiliza una "elección" bastante arriegada.
Es cierto que para cada \( n \) existe una suryección \( f_n:\mathbb{Z}_+\to A_n \), pero no sabemos cuántas hay, o claramente cuáles son todas, y así, "elegir" una de ellas sin una "regla concreta" es algo que no podría hacerse, eventualmente.
Para poder hacerlo se ha de recurrir al Axioma de Elección.
Por un lado, este axioma es controvertido, pero por otro lado, se usa muy comunmente en matemática, y más aún en topología. Así que nosotros lo utilizaremos sin mayores pruritos.
Sin embargo, tengo una objeción de usar el Axioma de Elección en este punto. ¿Por qué? Bueno, por la sencilla razón de que el texto de Munkres introduce y estudia el Axioma de Elección en secciones posteriores.
¿Sería posible evitar el uso del Axioma de Elección, al menos en este punto?
Mi opinión es que esto no se puede conseguir.
Sin embargo, planteo una prueba alternativa, que busca aislar mejor dónde está el inconveniente, o sea, el punto crucial donde el Axioma de Elección se hace claramente inevitable.
Eso es lo que haré en los párrafos que siguen en color azul.
Segunda demostración del mismo Teorema.
Ciertamente, si definimos \( B_n=\bigcup_{m \leq n} A_n \), es posible demostrar por inducción que cada conjunto \( B_n \) es numerable. Más aún, forman una familia creciente de conjuntos: \( B_1\subset B_2\subset \cdots \).
Puede que se tenga una lista finita de estos conjuntos \( B_1,\cdots, B_N \), o bien que a partir de cierto índice \( N \) todos los conjuntos sean iguales: \( B_N=B_{N+1}=\cdots \)
En cualquier caso, la unión de la familia \( \{A_n\}_{n\in J} \) es igual a \( B_N \), que resulta pues numerable.
Supongamos el caso restante, a saber, que \( B_n \subsetneqq B_{n+1} \), todo \( n\in\mathbb{Z}_+ \).
Denotemos \( V=\bigcup_{n\in \mathbb{Z}_+} B_n \).
Ciertamente \( V \) debe ser un conjunto infinito (por qué).
Esto implica que existe algún \( n\in\mathbb{Z}_+ \) tal que \( B_{n} \) es infinito (¿por qué?).
Por buena ordenación de \( \mathbb{Z}_+ \), hay un mínimo \( n_0\in\mathbb{Z}_+ \) con esta propiedad.
Vamos a suponer, para simplificar la exposición, que \( B_1 \) es ya infinito, o sea, \( n_0=1 \), ya que la unión total \( V \) tendrá, después de todo, a todos los elementos que estamos considerando, pues la unión es "creciente".
/color]
Ahora definimos una función \( \beta:V\to\mathbb{Z}_+ \) que indica el mínimo índice \( n \) al que pertenece cada \( x\in V \), así:
\( \beta:V\to\mathbb{Z},\qquad\beta(x)=\min\{n|x\in B_n\}. \)
Como cada \( B_n \) ahora es infinito numerable, para cada \( n \) existen funciones biyectivas de \( B_n \) en \( \mathbb{Z}_+ \) .
Denotemos \( \mathcal{F}_n \) a la familia de todas las funciones biyectivas \( f:B_n\to\mathbb{Z}_+ \).
Consideremos ahora una sucesión de funciones \( \sigma=\{f_n\}_{n\in\mathbb{Z}_+} \) tal que \( f_n\in \mathcal{F}_n \).
Hemos "elegido" un elemento \( f_n \) para cada \( n \) del conjunto infinito \( \mathbb{Z}_+ \).
O sea, hemos hecho uso del Axioma de Elección, aunque notemos que la colección \( \{\mathcal{F}_n|n\in\mathbb{Z}_+\} \) es sólo infinita numerable, por lo tanto es suficiente una versión numerable del Axioma de Elección.
Vamos a construir una función \( g_\sigma:V\to\mathbb{Z}_+ \) de la siguiente manera:
Para cada \( x\in V \), hacemos
\( g_\sigma(x)=f_{\beta(x)}(x). \)
Esta definición tiene pleno sentido, porque todo \( x\in V \) está presente en \( B_{\beta}(x) \), en cuyo caso \( x \) está en el dominio de \( f_{\beta(x)} \).
Ahora construyamos otra función \( h_\sigma:V\to\mathbb{Z}_+ \) de la siguiente manera:
\( h_\sigma(x)=2^{\beta(x)}3^{g_\sigma(x)}. \)
Probemos que cualquiera de estas funciones es inyectiva. Sean pues \( x,y\in V \), y supongamos que \( h_\sigma(x)=h_\sigma(y) \).
Obtenemos que \( 2^{\beta(x)}3^{g_\sigma(x)}=2^{\beta(y)}3^{g_\sigma(y)} \).
Como los números 2 y 3 son coprimos entre sí, resulta que \( 2^{\beta(x)}=2^{\beta(y)} \), y \( 3^{g_\sigma(x)}=3^{g_\sigma(y)} \).
De la igualdad \( 2^{\beta(x)}=2^{\beta(y)} \), inferimos que \( \beta(x)=\beta(y) \).
Esto significa que el mínimo índice \( n \) tal que \( x\in B_n \) es el mismo para el que \( y\in B_n \).
O sea, existe un \( n_0 \) tal que \( x,y\in B_{n_0} \), y además \( n<n_0 \) implica que \( x,y\not\in B_n \).
En particular, las funciones \( f_{\beta(x)} \) y \( f_{\beta(y)} \) son iguales, o sea, "son" la función \( f_{n_0} \), siendo iguales sus dominios al conjunto \( B_{n_0} \).
Ahora, de la igualdad \( 3^{g_\sigma(x)}=3^{g_\sigma(y)} \), inferimos que \( {g_\sigma(x)}={g_\sigma(y)} \).
Pero esto quiere decir, por definición de \( g_\sigma \), que \( f_{\beta(x)}(x)=f_{\beta(y)}(y) \).
Mas, dado que \( f_{\beta(x)}=f_{n_0}=f_{\beta(y)} \), tenemos que \( f_{n_0}(x)=f_{n_0}(y) \).
Como \( f_{n_0} \) es una función biyectiva, esto demuestra que \( x=y \).
Ahora bien. Hemos probado que existe una función inyectiva \( h_\sigma \) de \( V \) en \( \mathbb{Z}_+ \).
Esto implica por el Teorema 1 que \( V \) es un conjunto numerable.
[cerrar]
\( \bullet \) Teorema 6. El producto finito de conjuntos numerables es numerable.
Demostración
Primero se prueba que el producto de dos conjuntos numerables \( A,B \) es numerable, y luego se procede por inducción en el número de factores.
Si alguno de los conjuntos \( A,B \) es vacío, todo es trivial, así que supongamos que son no vacíos.
Existen funciones suryectivas \( f:\mathbb{Z}_+\to A, g:\mathbb{Z}_+\to B \). Entonces la función \( h:\mathbb{Z}_+\times \mathbb{Z}_+\to A\times B \), dada por \( h(n,m)=(f(n),g(m)) \) es suryectiva, y así \( A\times B \) es numerable.
El caso general de \( n \) factores \( A_1\times \cdots\times A_n \) se demuestra por inducción en \( n \), y se deja como ejercicio.
Si alguno de los conjuntos \( A,B \) es vacío, todo es trivial, así que supongamos que son no vacíos.
Existen funciones suryectivas \( f:\mathbb{Z}_+\to A, g:\mathbb{Z}_+\to B \). Entonces la función \( h:\mathbb{Z}_+\times \mathbb{Z}_+\to A\times B \), dada por \( h(n,m)=(f(n),g(m)) \) es suryectiva, y así \( A\times B \) es numerable.
El caso general de \( n \) factores \( A_1\times \cdots\times A_n \) se demuestra por inducción en \( n \), y se deja como ejercicio.
[cerrar]
¿Es cierto que el producto cartesiano numerable de conjuntos numerables es también numerable? Respuesta: NO.
\( \bullet \) Teorema 7. Sea \( X=\{0,1\} \). Entonces \( X^\omega \) es un conjunto no-numerable.
Demostración
La prueba puede hacerse con el típico procedimiento diagonal de Cantor.
También puede usarse el hecho de que \( X^\omega \) es biyectivo con \( \mathcal{P}(\mathbb{Z}_+) \), y aprovechar el conocido hecho de la teoría de conjuntos, que afirma que toda función de un conjunto \( Z \) en su conjunto de partes \( \mathcal{P}(Z) \) no puede ser jamás sobreyectiva.
En virtud del Teorema 1, parte (2), basta demostrar que toda función \( g:\mathbb{Z}_+\to X^\omega \) no puede ser sobreyectiva.
Vamos a construir un elemento \( \mathbf{y}=(y_1,y_2,\cdots)\in X^\omega \) que no pertenece a la imagen de \( g \).
Para cada \( n \), el valor de \( g(n) \) es una sucesión \( \mathbf{x}^n\in X^\omega \), y podemos denotar a sus elementos como \( \mathbf{x}^n=(x^n_{1},x^n_2,\cdots) \).
Definimos finalmente \( y_n=1-x_^n_n \).
Dejamos como ejercicio comprobar que \( \mathbf{y}=(y_1,y_2,\cdots) \) no puede ser igual a \( g(n) \), cualquiera sea \( n\in\mathbb{Z}_+ \).
También puede usarse el hecho de que \( X^\omega \) es biyectivo con \( \mathcal{P}(\mathbb{Z}_+) \), y aprovechar el conocido hecho de la teoría de conjuntos, que afirma que toda función de un conjunto \( Z \) en su conjunto de partes \( \mathcal{P}(Z) \) no puede ser jamás sobreyectiva.
En virtud del Teorema 1, parte (2), basta demostrar que toda función \( g:\mathbb{Z}_+\to X^\omega \) no puede ser sobreyectiva.
Vamos a construir un elemento \( \mathbf{y}=(y_1,y_2,\cdots)\in X^\omega \) que no pertenece a la imagen de \( g \).
Para cada \( n \), el valor de \( g(n) \) es una sucesión \( \mathbf{x}^n\in X^\omega \), y podemos denotar a sus elementos como \( \mathbf{x}^n=(x^n_{1},x^n_2,\cdots) \).
Definimos finalmente \( y_n=1-x_^n_n \).
Dejamos como ejercicio comprobar que \( \mathbf{y}=(y_1,y_2,\cdots) \) no puede ser igual a \( g(n) \), cualquiera sea \( n\in\mathbb{Z}_+ \).
[cerrar]
\( \bullet \) Ejercicio. Demostrar que si \( B\neq\emptyset \), y \( f:B\to C \) es inyectiva, entonces existe una función sobreyectiva \( g:C\to B \). ¿Cómo se construye \( g \)?
El siguiente Teorema da otro ejemplo de conjunto no-numerable, con \( A=\mathbb{Z}_+ \), por ejemplo.
\( \bullet \) Teorema 8. Sea \( A \) un conjunto. No existe aplicación inyectiva \( f:\mathcal{P}(A)\to A \), y tampoco existe aplicación sobreyectiva \( g:A\to \mathcal{P}(A) \).
Demostración
En virtud del Ejercicio precedente, basta probar que una aplicación \( g:A\to\mathcal{P}(A) \) no puede ser sobreyectiva.
Así que supongamos por el absurdo que sí existe una tal \( g \) sobreyectiva.
Notemos que las imágenes de la función \( g \) son subconjuntos de \( A \).
Si \( a\in A \), se tiene que, o bien \( a\in g(a) \), o bien \( a\not\in g(a) \).
Sea
\( B=\{a|a\in A-g(a)\}. \)
Se deja como ejercicio demostrar que \( B \) no está en la imagen de \( g \), o sea, no existe \( a_0\in A \) tal que \( f(a_0) \) es igual a \( B \).
(Si no sale, avisen, y completo con más detalles...)
[cerrar]
En un capítulo posterior se demostrará que \( \mathbb{R} \) es un conjunto no-numerable.
No se hace aquí, porque sólo hemos dado los axiomas de los números reales, y faltaría agregar una larga serie de construcciones para tener más claro cómo proceder.
Ejercicios Sección 7
- Ejercicio 7.1 Demostrar que \( \mathbb{Q} \) es infinto numerable.
- Ejercicio 7.2 Muestre que las funciones \( f,g \) de los Ejemplos 1 y 2 son biyecciones.
- Ejercicio 7.3 Sea \( X=\{0,1\} \). Muestre que existe una biyección entre el conjunto \( \mathcal{P}(\mathbb{Z}_+) \) y el producto cartesiano \( X^\omega \).
- Ejercicio 7.4
- (a) Un número real \( x \) se dice algebraico (sobre los racionales) si satisface alguna ecuación polinomial de grado positivo.\( x^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0=0 \)
con coeficientes racionales \( a_i \).
Asumiendo que cada ecuación polinomial tiene sólo un número finito de raíces, mostrar que el conjunto de números algebraicos es numerable. - (b) Un número real se dice trascendente si no es algebraico.
Asumiendo que los números reales son no-numerables, mostrar que los números trascendentes son no-numerables.
- (a) Un número real \( x \) se dice algebraico (sobre los racionales) si satisface alguna ecuación polinomial de grado positivo.
- Ejercicio 7.5 Determine, para cada uno de los siguientes conjuntos, si son o no numerables. Justifique sus respuestas:
- (a) El conjunto \( A \) de todas las funciones \( f:\{0,1\}\to \mathbb{Z}_+ \).
- (b) El conjunto \( B_n \) de todas las funciones \( f:\{1,\cdots,n\}\to\mathbb{Z}_+ \).
- (c) El conjunto \( C=\bigcup_{n\in\mathbb{Z}_+}B_n \).
- (d) El conjunto \( D \) de todas las funciones \( f:\mathbb{Z}_+\to\mathbb{Z}_+ \).
- (e) El conjunto \( E \) de todas las funciones \( f:\mathbb{Z}_+\to\{0,1\} \).
- (f) El conjunto \( F \) de todas las funciones \( f:\mathbb{Z}_+\to \{0,1\} \) que son eventualmente cero (esto significa que existe un entero positivo \( N \) tal que \( f(n)=0 \) para todo \( n \geq N \)).
- (g) El conjunto \( G \) de todas las funciones \( f:\mathbb{Z}_+\to\mathbb{Z}_+ \) que son eventualmente \( 1 \).
- (h) El conjunto \( H \) de todas las funciones \( f:\mathbb{Z}_+\to\mathbb{Z}_+ \) que son eventualmente constantes.
- (i) El conjunto \( I \) de todos los subconjuntos de 2 elementos de \( \mathbb{Z}_+ \).
- (j) El conjunto \( J \) de todos los subconjuntos finitos de \( \mathbb{Z}_+ \).
- Ejercicio 7.6 Decimos que dos conjuntos \( A,B \) tienen la misma cardinalidad si hay una biyección de \( A \) con \( B \).
- (a) Muestre que si \( B\subset A \) y si hay una inyección \( f:A\to B \), entonces \( A \) y \( B \) tienen la misma cardinalidad.
Ayuda: Utilice una definición recursiva para construir conjuntos \( A_1=A,B_1=B \) y para \( n>1 \), \( A_n=f(A_{n-1}),B_n=f(B_{n-1}) \).
Luego observe que \( A_1\supset B_1\supset A_2\supset B_2\supset A_3\supset\cdots \).
Finalmente defina la biyección \( h:A\to B \) mediante:\( h(x)=\begin{cases}f(x),&x\in \bigcup_n (A_n-B_n),\\ x,&\textsf{en otro caso.}\end{cases} \) - (b) Teorema (de Schroeder-Bernstein). Si hay inyecciones \( f:A\to C \) y \( g:C\to A \), entonces \( A \) y \( C \) tienen la misma cardinalidad.
- (a) Muestre que si \( B\subset A \) y si hay una inyección \( f:A\to B \), entonces \( A \) y \( B \) tienen la misma cardinalidad.
- Ejercicio 7.7 Muestre que los conjuntos \( D,E \) del Ejercicio 5 tienen la misma cardinalidad.
- Ejercicio 7.8 Denotemos \( X=\{0,1\} \); sea \( \mathcal{B} \) el conjunto de todos los subconjuntos numerables de \( X^\omega \). Muestre que \( X^\omega \) y \( \mathcal{B} \) tienen la misma cardinalidad.
- Ejercicio 7.9
- (a) La fórmula\( (*)\qquad h(1)=1,\qquad h(2)=2,\qquad h(n)=[h(n+1)]^2-[h(n-1)]^2,\quad n\geq2 \)
no es una a la cual se aplica el principio de definición recursiva.
Muestre que no existe una función \( h:\mathbb{Z}_+\to\mathbb{R} \) que satisface esta fórmula.
Ayuda: Reformule \( (*) \) tal que el principio pueda aplicarse y requiera que \( h \) sea positiva. - (b) Muestre que la fórmula \( (*) \) de la parte (a) no determina \( h \) unívocamente.
Ayuda: Si \( h \) es una función positivia que satisface \( (*) \), hacer \( f(i)=h(i) \) para \( i\neq3 \), y \( f(3)=-3 \). - Muestre que no hay una función \( h:\mathbb{Z}_+\to\mathbb{R} \) que satisface la fórmula\( h(1)=1,\qquad h(2)=2,\qquad h(n)=[h(n+1)]^2-[h(n-1)]^2,\quad n \geq2. \)
- (a) La fórmula
[cerrar]
>> Clic aquí para Opiniones, preguntas y otros comentarios del curso: Topología (Munkres)
Sección 8. El Principio de Definición Recursiva.
Esta sección es interesante, pero tiene resultados muy estandarizados de la teoría de conjuntos.
No quisiera perder tiempo con ellos, aún cuando a mí mismo me gustan muchísimo estos temas de las definiciones por recurrencia y cuestiones relacionadas.
No obstante, si cualquiera de ustedes desea más detalles, explicaciones, o quiere profundizar en todo esto, basta conque lo diga y nos sumergimos en el tema.
Sea \( C\subset \mathbb{Z}_+ \) un conjunto infinito.
Nos preguntamos si es posible definir una función \( h:\mathbb{Z}_+\to C \) que satisfaga:
\( (*)\qquad h(1)=\min(C),\qquad h(i)=\min(C-h(\{1,\cdots,i-1\})),\qquad i> 1. \)
Primero se estudian funciones definidas por secciones \( \{1,\cdots,n\} \), y luego se pasa al caso de todo \( \mathbb{Z}_+ \).
\( \bullet \) Lema 1. Dado \( n\in\mathbb{Z}_+ \), existe una función
\( f:\{1,\cdots,n\}\to C \)
que satisface \( (*) \) para todo \( i=1,\cdots,n \).
Demostración
Se deja como ejercicio.
Basta proceder por inducción en el número \( n \) de elementos del dominio de \( f \), y prestando atención a la forma de \( h \) en \( (*) \).
[cerrar]
\( \bullet \) Lema 2. Si \( f:\{1,\cdots,n\}\to C \) y \( g:\{1,\cdots,m\}\to C \) son funciones que verifican \( (*) \) en sus respectivos dominios, entonces \( f(i)=g(i) \), para todo \( i \) que esté en ambos dominios al mismo tiempo.
Demostración
Se deja como ejercicio.
Se puede proceder por reducción al absurdo, e invocando el hecho de que todo conjunto de enteros positivos tiene un mínimo.
[cerrar]
\( \bullet \) Teorema 3. Existe una única función \( h:\mathbb{Z}_+\to C \) que verifica \( (*) \) para todo \( i\in\mathbb{Z}_+ \).
Demostración
Se dejan los detalles como ejercicio.
Basta notar que, por los Lemas 1 y 2, para cada \( n \) existe una única función \( f_n:\{1,\cdots,n\}\to C \) que verifica \( (*) \).
Recordar que una función es un conjunto formado por pares ordenados.
Así que tiene sentido definir el conjunto de pares ordenados \( f=\bigcup_{n\in\mathbb{Z}_+} f_n \).
Se debe demostar que \( f \) es una función con dominio \( \mathbb{Z}_+ \).
O sea, hay que constatar que se cumple la regla de unicidad de la imagen.
También hay que chequear (fácil) que se cumple \( (*) \) para todo \( i\in\mathbb{Z}_+ \).
Finalmente, hay que explicar que \( h \) es única. (Aprovechar el Lema 2 para obtener unicidad).
[cerrar]
\( \bullet \) Teorema 4 (Principio de definición recursiva). Sean \( A \) un conjunto y \( a_0\in A \). Supongamos que \( \rho \) es una función que asigna un elemento de \( A \) a cada función \( f \), con dominio una sección no vacía de enteros positivos e imagen en \( A \). Entonces existe una única función
\( h:\mathbb{Z}_+\to A \)
tal que
\( (*)\qquad h(1)=a_0,\qquad h(i)=\rho (h|\{1,\cdots,i-1\}),\qquad i> 1. \)
Demostración: Sigue ideas muy similares a los resultados previos. Salvo que ahora la función \( h \) no cumple \( (*) \) sino una regla general.
_____________
\( \bullet \) La fórmula \( (*) \) se llama fórmula recursiva para \( h \).
La idea general es que uno está "autorizado" a definir una función mediante una fórmula de recurrencia.
Vale decir, si uno especifica una fórmula de recurrencia, ésta nos define correctamente una función, y sin ambigüedad, ya que el Teorema anterior nos garantiza que existe al menos una función que satisface la recurrencia (la recurrencia es algo con "sentido"), y además dicha función es única (la recurrencia es "inambigua").
Notemos algunos detalles técnicos. El dominio de la función \( \rho \) del Teorema 4 es un conjunto muy complicado.
Sea \( \mathcal{F}_n \) la familia de todas las funciones \( f:\{1,\cdots,n\}\to A \).
Entonces el dominio de \( \rho \) es la unión \( \bigcup_{n\in\mathbb{Z}_+} \mathcal{F}_n \).
La imagen de \( \rho \) es un subconjunto de \( A \).
Así que podemos anotar:
\( \rho :\left(\bigcup_{n\in\mathbb{Z}_+}\mathcal{F}_n\right)\to A. \)
Ahora bien, la función \( h \) del "discurso" del Teorema 4 tiene como dominio todo el conjunto \( \mathbb{Z}_+ \), y no meras secciones.
Sin embargo, se pueden considerar las restricciones de \( h \) a secciones \( \{1,\cdots,i-1\} \).
Estas funciones "restricción" se indican, como es costumbre, con el símbolo \( | \), así: \( h|\{1,\cdots,i-1\} \), y así se obiene un "objeto" de \( \mathcal{F}_{i-1} \), al cual es válido aplicarle la función \( \rho \).
\( \bullet \) Ejemplo 1. Comprobar que el Teorema 3 es un caso particular del Teorema 4. Basta definir:
\( \rho (f)=\min(C)-\textsf{imagen de}(f) \)
\( \bullet \) Ejemplo 2. Definir rigurosamente las potencias \( a^n \), con \( a\in\mathbb{R} \) y \( n\in\mathbb{Z}_+ \), mediante la fórmula de recurrencia:
\( a^1=a,\qquad a^n=a^{n-1}\cdot a \)
Sugerencia: Utilizar \( \rho (f)=f(m)\cdot a \), si el dominio de \( f \) es \( \{1,\cdots,m\} \).
Ejercicios Sección 8
- Ejercicio 8.1 Sea \( (b_1,b_2,\cdots) \) una sucesión de números reales.
La suma \( \sum_{k=1}^n b_k \) está definida por inducción como sigue:
\( \displaystyle \sum_{k=1}^n b_k,\qquad\qquad \qquad\qquad\qquad n=1. \)
\( \displaystyle \sum_{k=1}^n b_k=\left(\sum_{k=1}^{n-1} b_k\right)+b_n,\qquad\qquad n>1. \)
Sea \( A \) el conjunto de los números reales; elija \( \rho \) tal que sea posible aplicar el Teorema 4 para definir la suma rigurosamente.
En ocasiones, la suma \( \sum_{k=1}^n b_k \) se denotará con el símbolo \( b_1+b_2+\cdots+a_n \).
Notemos cómo es que en este punto Munkres pone atención al uso formalmente correcto de la notación con puntos suspensivos.
Esto es lo que hace la diferencia entre "meras convenciones" no explicadas en los textos corrientes de matemáticas, y el uso consistente e inambiguo de una determinada notación.
En todo caso, lo importante aquí es "rescatar" que finalmente todo enunciado matemático requiere que haya una manera formal y precisa de escribirlo. - Ejercicio 8.2 Sea \( (b_1,b_2,\cdots) \) una sucesión de números reales.
El producto \( \prod_{k=1}^n b_k \) está definido por inducción como sigue:
\( \displaystyle \prod_{k=1}^n b_k,\qquad\qquad\qquad\qquad\qquad n=1. \)
\( \displaystyle \prod_{k=1}^n b_k=\left(\prod_{k=1}^{n-1} b_k\right)\cdot b_n,\qquad\qquad n>1. \)
Usar el Teorema 4 para definir el producto rigurosamente.
En ocasiones, el producto \( \prod_{k=1}^n b_k \) se denotará con el símbolo \( b_1\cdot b_2\cdot\; \cdots\;\cdot b_n \). - Ejercicio 8.3 Obtener la definición de \( a^n \) y de \( n! \) para \( n\in\mathbb{Z}_+ \) como un caso especial del Ejercicio 2.
- Ejercicio 8.4 Los números de Fibonacci de la teoría de números se definen recursivamente por la fórmula:\( \lambda_1=\lambda_2=1,\qquad \lambda_n=\lambda_{n-1}+\lambda_{n-2},\quad n>2. \)
Defínalos rigurosamente usando el Teorema 4. - Ejercicio 8.5 Muestre que hay una única función \( h:\mathbb{Z}_+\to\mathbb{R}_+ \) que satisface la fórmula\( h(1)=3,\qquad h(i)=[h(i-1)+1]^{1/2},\quad i>1. \)
- Ejercicio 8.6
- (a) Muestre que no hay una función \( h:\mathbb{Z}_+\to\mathbb{R}_+ \) que satisface la fórmula\( h(1)=3,\qquad h(i)=[h(i-1)-1]^{1/2},\quad i>1. \)
Explique por qué este ejemplo no viola el principio de definición recursiva. - (b) Considere la fórmula de recursión
\( h(1) = 3, \)
y para \( i>1 \):
\( h(i) = \begin{cases}[h(i-1)-1]^{1/2},&\textsf{si\ } h(i-1)>1,\\5,&\textsf{si\ }h(i-1) \leq 1.
\end{cases} \)
Muestre que existe una única función \( h:\mathbb{Z}_+\to\mathbb{R}_+ \) que satisface esta fórmula.
- (a) Muestre que no hay una función \( h:\mathbb{Z}_+\to\mathbb{R}_+ \) que satisface la fórmula
- Ejercicio 8.7 Pruebe el Teorema 4.
- Ejercicio 8.8 Verificar la siguiente versión del principio de definición recursiva:
Sea \( A \) un conjunto.
Sea \( \rho \) una función que asigna un elemento \( \rho(f) \) de \( A \) a cada función \( f:S_n\to A \), donde \( S_n \) es alguna sección de \( \mathbb{Z}_+ \).
Entonces existe una única función \( h:\mathbb{Z}_+\to A \) tal que \( h(n)=\rho(h|S_n) \) para cada \( n\in\mathbb{Z}_+ \).
[cerrar]
>> Clic aquí para Opiniones, preguntas y otros comentarios del curso: Topología (Munkres)
En línea
). 
