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:
\( 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.\( \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 \).
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?
- 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.
- 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.
- Ejercicio 6.7 Si \( A,B \) son finitos, mostrar que el conjunto de todas las funciones \( f:A\to B \) es finito.
>> Clic aquí para Opiniones, preguntas y otros comentarios del curso: Teoría de Conjuntos 2011