conjuntos finitos archivos

Introducción

En esta entrada daremos continuación al tema de conjuntos finitos. Probaremos más resultados que se satisfacen para los conjuntos finitos y veremos cuál es la cardinalidad del conjunto potencia de un conjunto finito dado.

Conjuntos finitos y contención

Teorema. Sean $A$ y $B$ conjuntos tales que $B$ es finito. Si $A \subseteq B$ , entonces $A$ es finito. Más aún, $| A | \leq | B |$ .

Demostración. (Por inducción sobre $| B |$ ).

Base de inducción. Supongamos que $| B | = 0$ . Entonces $B = \emptyset$ , por lo que $A = \emptyset$ y así, $A$ es finito y $0 = | A | \leq | B | = 0$ .

Hipótesis de inducción. Supongamos que para $| X | = n$ se cumple que si $Y \subseteq X$ , entonces $Y$ es finito y $| Y | \leq | X |$ .

Paso inductivo. Sea $B$ un conjunto finito tal que $| B | = n + 1$ . Veamos que si $A \subseteq B$ , entonces $A$ es finito y $| A | \leq | B |$ .

Si $A = B$ , entonces $A$ es finito y $| A | = | B | \leq | B |$ .

Si $A \neq B$ , existe $x \in B ∖ A$ . Luego, $A \subseteq B ∖ {x}$ y como $| B ∖ {x} | = n$ , tenemos por hipótesis de inducción que $A$ es finito y $| A | \leq | B ∖ {x} | = n \leq n + 1 = | B |$ . En cualquier caso, $A$ es finito y $| A | \leq | B |$ .

Cardinalidad del conjunto potencia

Como parte de los ejercicios de la unidad de números naturales, definimos la operación binaria potencia en $N$ , que intuitivamente se realiza como sigue $m^{n} = \underset{n - v e c e s}{\underset{⏟}{m \cdot m \dots m}}$ .

Teorema. Si $X$ es finito, entonces $P (X)$ es finito y $| P (X) | = 2^{| X |}$ .

Demostración. (Por inducción sobre $| X |$ ).

Base de inducción. Si $| X | = 0$ , entonces $X = \emptyset$ y así, $P (X) = {\emptyset}$ , por lo que $P (X)$ es finito y $| P (X) | = 1 = 2^{0} = 2^{| X |}$ .

Hipótesis de inducción. Supongamos que si $A$ es finito tal que $| A | = n$ , entonces $P (A)$ es finito y $| P (A) | = 2^{| A |}$ .

Paso inductivo. Sea $X$ un conjunto finito tal que $| X | = n + 1$ . Supongamos que $X = {X_{1}, X_{2}, \dots, X_{n}, X_{n + 1}}$ . Luego, consideremos $X^{'} = X ∖ {X_{1}}$ , entonces $| X^{'} | = n$ y así, $| P (X^{'}) | = 2^{| X^{'} |}$ . Veamos que $P (X)$ es finito y $| P (X) | = 2^{| X |}$ . Para ello veamos primero que $P (X) = P (X^{'}) \cup {Z \in P (X) : X_{1} \in Z}$ .

Procederemos por doble contención.

$\subseteq$ ) Sea $Y \in P (X)$ , entonces $Y \subseteq X$ . Si $X_{1} \in Y$ , entonces $Y \in {Z \in P (X) : X_{1} \in Z}$ y por lo tanto, $Y \in P (X^{'}) \cup {Z \in P (X) : X_{1} \in Z}$ .

Si $X_{1} \notin Y$ , entonces $Y \subseteq X ∖ {X_{1}} = X^{'}$ , por lo que $Y \in P (X^{'})$ y por lo tanto, $Y \in P (X^{'}) \cup {Z \in P (X) : X_{1} \in Z}$ .

Concluimos que $P (X) \subseteq P (X^{'}) \cup {Z \in P (X) : X_{1} \in Z}$ .

$\supseteq$ ) Sea $Y \in P (X^{'}) \cup {Z \in P (X) : X_{1} \in Z}$ .

Caso 1: Si $Y \in P (X^{'})$ , entonces $Y \subseteq X^{'}$ y como $X^{'} \subseteq X$ , entonces $Y \subseteq X$ y así, $Y \in P (X)$ .

Caso 2: Si $Y \in {Z \in P (X) : X_{1} \in Z}$ , entonces $Y \in P (X)$ .

Por lo tanto, $P (X^{'}) \cup {Z \in P (X) : X_{1} \in Z} \subseteq P (X)$ .

Así, $P (X) = P (X^{'}) \cup {Z \in P (X) : X_{1} \in Z}$ .

Luego, por hipótesis de inducción tenemos que $P (X^{'})$ es finito y $| P (X^{'}) | = 2^{n}$ .

Resulta que ${Z \in P (X)}$ es finito; más aún, afirmamos que $| {Z \in P (X) : X_{1} \in Z} | = | P (X^{'}) |$ . Para probar este último hecho estableceremos una biyección entre $P (X^{'})$ y ${Z \in P (X) : X_{1} \in Z}$ .

Consideremos $f : P (X^{'}) \to {Z \in P (X) : X_{1} \in Z}$ dada por $f (Y) = Y \cup {X_{1}}$ . Veamos que $f$ es biyectiva.

Inyectividad. Sean $A, B \in P (X^{'})$ tales que $f (A) = f (B)$ , esto es $A \cup {X_{1}} = B \cup {X_{1}}$ . Luego, $A$ y ${X_{1}}$ son ajenos pues $A \subseteq X^{'} = X ∖ {X_{1}}$ ; asimismo, $B$ y ${X_{1}}$ son ajenos pues $B \subseteq X^{'} = X ∖ {X_{1}}$ . De este modo, debe ocurrir que $A = B$ . Por lo tanto, $f$ es inyectiva.

Suprayectividad. Sea $Y \in {Z \in P (X) : X_{1} \in Z}$ . Entonces $Y \subseteq X$ y $X_{1} \in Y$ .

Veamos que existe $W \subseteq X ∖ {X_{1}}$ tal que $f (W) = Y$ . Consideremos $W = Y ∖ {X_{1}}$ . Tenemos que $f (W) = (Y ∖ {X_{1}}) \cup {X_{1}} = Y$ . Por lo tanto, $f$ es suprayectiva.

Así, $f$ es biyectiva y $| {Z \in P (X) : X_{1} \in Z} | = 2^{n}$ .

Por lo tanto, usando regla de la suma, tenemos que $| P (X) | = | P (X^{'}) \cup {Z \in P (X)} | = 2^{n} + 2^{n} = 2 (2^{n}) = 2^{n + 1}$ . Esto concluye nuestra prueba.

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta entrada.

Demuestra que si $A$ es un conjunto finito, entonces $A$ no es equipotente a ninguno de sus subconjuntos propios.
Demuestra que si $A \subseteq B$ y $B$ es finito, entonces $| B | = | B ∖ A | + | A |$ .
Sean $A$ y $B$ conjuntos finitos. Sea $F$ el conjunto de todas las posibles funciones de $A$ en $B$ . Muestra que $F$ es finito. ¿Cuál es su cardinalidad en términos de las de $A$ y $B$ ?
Sean $A$ y $B$ conjuntos finitos. Muestra que $A \times B$ es finito. ¿Cuál es su cardinalidad en términos de las de $A$ y $B$ ?
Demuestra que para cualquier número natural $n$ se tiene que $n < 2^{n}$ .

Más adelante…

En la siguiente entrada abordaremos a los conjuntos infinitos. Esto nos acercará a una discusión importante sobre qué son en realidad los cardinales en teoría de los conuntos.

Entradas relacionadas

Ir a Teoría de los Conjuntos I
Entrada anterior: Teoría de los Conjuntos I: Conjuntos finitos
Siguiente entrada: Teoría de los Conjuntos I: Conjuntos infinitos

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»

Introducción

Ahora que sabemos el concepto de equipotencia, en esta entrada definiremos qué son los conjuntos finitos y hablaremos de ellos. A grandes rasgos, serán aquellos que tengan tantos elementos como alguno de los números naturales que ya definimos. Además, veremos resultados acerca de la cardinalidad de la unión de dos conjuntos.

Conjuntos finitos

Definición. Sea $X$ un conjunto. Decimos que $X$ es un conjunto finito si y sólo si existe $n \in N$ tal que $X \sim n$ .

Ejemplo.

El conjunto $\emptyset$ es finito, pues existe una biyección entre el conjunto $\emptyset$ y $0$ ; a saber, la función vacía.

Ejemplo.

El conjunto $A = {2, 4, 6, 8, 10}$ es finito pues $f : A \to 5 = {0, 1, 2, 3, 4}$ definida por medio de $f = {(2, 0), (4, 1), (6, 2), (8, 3), (10, 4)}$ es una función biyectiva.

Principio de las casillas y unicidad de natural equipotente

La definición dice que $X$ es finito cuando hay un natural al que es equipotente pero, ¿este natural es único? La respuesta es que sí. Demostraremos esto a través de algunos resultados auxiliares, que a la vez nos permitirán enunciar y demostrar un par de versiones del principio de las casillas.

Lema (principio de las casillas). No existe ninguna función inyectiva $f : n + 1 \to n$ .

Demostración. Probaremos el resultado por inducción. Para $n = 0$ el resultado es cierto pues no existe ninguna función (inyectiva o no) $f : 1 \to 0$ , pues $0 = \emptyset$ y $1 \neq \emptyset$ .

Supongamos que el resultado es cierto para el natural $n$ , es decir, que no existe ninguna función inyectiva $f : n + 1 \to n$ . Veremos que no existe ninguna función inyectiva $g : n + 2 \to n + 1$ . En busca de una contradicción, supongamos que sí existe tal $g$ .

Si $I m (g) \subseteq n$ , entonces la restricción de $g$ a $n + 1$ es una función inyectiva de $n + 1$ en $n$ , lo que contradice la hipótesis inductiva. Así, existe un natural $k \leq n + 2$ tal que $g (k) = n + 1$ . Si $k = n + 2$ , entonces $g ∖ {(n + 2, n + 1)}$ es una función inyectiva de $n + 1$ en $n$ , que contradice la hipótesis inductiva. Así, $k \leq n + 1$ . Como $g$ es inyectiva, $g (n + 2) = l \neq k$ . Pero entonces, $(g ∖ {(n + 2, l), (k, n + 1)}) \cup {(k, l)}$ es una función inyectiva de $n + 1$ en $n$ , dando una contradicción final a la hipótesis inductiva.

Usualmente el principio de las casillas se piensa así: si $f : n + 1 \to n$ es una función, entonces deben existir $x, y \in n + 1$ tales que $f (x) = f (y)$ . En términos intuitivos, «si colocamos $n + 1$ pelotas en $n$ casillas, entonces por lo menos en alguna casilla quedaron por lo menos dos pelotas». Si son todavía más pelotas, el resultado es cierto, como lo indica el siguiente corolario de manera formal.

Corolario. Sean $m, n$ naturales con $n < m$ . Entonces no existen funciones inyectivas $f : m \to n$ .

Demostración. Recordemos que si $n < m$ , entonces $n \subset m$ y de hecho $n + 1 \subseteq m$ . Si existiera una función inyectiva $f : m \to n$ , entonces su restricción a $n + 1$ sería una función inyectiva de $n + 1$ en $n$ , contradiciendo el principio de las casillas.

En particular, si $X$ es un conjunto finito, entonces debe haber un único natural $n$ al cual es equipotente. Si hubiera dos distintos $m$ y $n$ , sin pérdida de generalidad $n < m$ . Tendríamos entonces que $m \sim X$ y $X \sim n$ , pero entonces $m \sim n$ y existiría una función biyectiva de $m$ a $n$ . En particular, sería una función inyectiva, lo cual contradice el corolario anterior.

Con esto en mente, es conveniente añadir la siguiente notación para conjuntos finitos.

Definición. Sea $X$ un conjunto finito y $n \in N$ el natural tal que $X \sim n$ . Definimos el cardinal de $X$ como $n$ y lo denotaremos por $| X | = n$ .

La regla de la suma

La regla de la suma es un resultado muy versátil que nos permite entender exactamente la cardinalidad de la unión de dos conjuntos finitos disjuntos. Además, este resultado motivará posteriormente la definición de suma de cardinales infinitos, cuando hablemos de ellos.

Teorema (regla de la suma). Si $X$ y $Y$ son conjuntos finitos y disjuntos, con $| X | = m$ y $| Y | = n$ , entonces $X \cup Y$ es finito y $| X \cup Y | = m + n$ .

Demostración. Sean $f : X \to m$ y $g : Y \to n$ biyecciones. Definimos la función $h : X \cup Y \to m + n$ como sigue: $h (x) = {\begin{cases} f (x) & si x \in X \\ m + g (x) & si x \in Y . \end{cases}$

Como $X$ y $Y$ son disjuntos, $h$ es una función de dominio $X \cup Y$ . Como $f (x) \leq m - 1 \leq m + n - 1$ y $m + g (x) \leq m + n - 1$ , entonces la imagen de $h$ está contenida en $m + n$ . Afirmamos que $h$ es una biyección de $X \cup Y$ en $m + n$ .

Veamos que $h$ es inyectiva. Supongamos que $x, y$ en $X \cup Y$ son tales que $h (x) = h (y)$ . Es imposible que $x \in X$ y $y \in Y$ pues en ese caso $h (x) = f (x) \leq m - 1$ y $h (y) = m + g (y) \geq m$ . Análogamente, $x \in Y$ y $y \in X$ es imposible. Así, o bien ambos $x$ y $y$ están en $X$ , o bien ambos están en $Y$ . Si están en $X$ , tenemos $f (x) = h (x) = h (y) = f (y)$ y como $f$ es inyectiva, obtenemos $x = y$ . Si están en $Y$ , tenemos $m + g (x) = h (x) = h (y) = m + g (y)$ . Por ley de cancelación de la suma, se tiene $g (x) = g (y)$ . Y por inyectividad de $g$ se tendría $x = y$ .

Ahora, veamos que $h$ es suprayectiva. Tomemos $k \in m + n$ . Si $k \leq m - 1$ , entonces como $f$ es suprayectiva, existe $x \in X$ tal que $f (x) = k$ y entonces $h (x) = f (x) = k$ . Si $k \geq m$ , entonces existe $l$ tal que $m + l = k$ . Dicha $l$ debe cumplir $l \leq n - 1$ , pues en otro caso $m + n - 1 \geq k = m + l \geq m + n$ , lo cual sería una contradicción. Como $g$ es biyectiva, existe $r$ tal que $g (r) = l$ . Y entonces $h (r) = m + g (r) = m + l = k$ .

Como $h$ es inyectiva y suprayectiva, obtenemos que es biyectiva, como queríamos.

La regla de la suma tiene varios corolarios como consecuencia.

Corolario. Si $X$ es finito y $y \notin X$ , entonces $X \cup {y}$ es finito y $| X \cup {y} | = | X | + 1$ .

Demostración. Aplicamos la regla de la suma y $| {y} | = 1$ .

Corolario (principio de inclusión-exclusión). Sean $X$ y $Y$ conjuntos finitos. Entonces $X \cup Y$ es finito. Más aún, $| X \cup Y | + | X \cap Y | = | X | + | Y |$ .

Demostración. Se tiene que $X = (X \cap Y) \cup (X ∖ Y)$ y que $(X \cap Y) \cap (X ∖ Y) = \emptyset$ (verifica ambas cosas). Así, por regla de la suma se tiene que $| X | = | X \cap Y | + | X ∖ Y | .$

De manera similar, se tiene que $X \cup Y = Y \cup (X ∖ Y)$ con $Y \cap (X ∖ Y) = \emptyset$ (verifíca ambas cosas). Así, por la regla de la suma se tiene que $| Y | + | X ∖ Y | = | X \cup Y | .$

Sumando las dos igualdades que obtuvimos, tenemos que $| X | + | Y | + | X ∖ Y | = | X \cap Y | + | X \cup Y | + | X ∖ Y | .$

Aplicando la ley de cancelación para eliminar $| X ∖ Y |$ , obtenemos el resultado deseado.

Corolario. Sean $X$ y $Y$ conjuntos finitos, entonces $X \cup Y$ es finito. Más aún, $| X \cup Y | \leq | X | + | Y |$ .

Demostración. Por el principio de inclusión-exclusión, $| X \cup Y | \leq | X \cup Y | + | X \cap Y | = | X | + | Y | .$

La regla de la suma por sí misma es muy versátil y tiene una versión más general.

Teorema (regla de la suma generalizada). Sea $n$ un natural y sean $A_{1}, \dots, A_{n}$ conjuntos finitos y tales que $A_{j} \cap A_{i} = \emptyset$ para cualesquiera $i, j$ en ${1, \dots, n}$ . Entonces $A := ⋃ {A_{i} : i \in {1, \dots, n}}$ es finito.

En los ejercicios tendrás que probar esta versión.

Un último resultado que demostraremos es el siguiente.

Teorema. Si $F$ es finito y para cualquier $X \in F$ pasa que $X$ es finito, entonces $⋃ F$ es finito.

Demostración. (Por inducción sobre la cardinalidad de $F$ ).

Base de inducción. Si $| F | = 0$ , entonces $F = \emptyset$ . Así, se cumple por vacuidad, que si cualquier $X \in F$ es finito, entonces $⋃ F$ es finito. Más aún, $⋃ F = \emptyset$ y $| ⋃ F | = 0$ .

Hipótesis de inducción. Supongamos que si $| G | = n$ y para cualquier $X \in G$ , $X$ es finito, se cumple que $⋃ G$ es finito.

Paso inductivo. Veamos que si $| F | = n + 1$ y para cualquier $X \in F$ , $X$ es finito, entonces $⋃ F$ es finito.

Como $| F |$ es distinto de $0$ , tomeos $X \in F$ y definamos $F^{'} := F ∖ {X}$ . Tenemos que cualquier elemento de $F^{'}$ es finito y que $| F^{'} | = n$ , por lo que por hipótesis de inducción se cumple que $⋃ F^{'}$ es finito.

Ahora, por el corolario del principio de inclusión-exclusión, tenemos que $⋃ F^{'} \cup X$ es finito.

Afirmación. $⋃ F = ⋃ F^{'} \cup X$ .

Demostración de la afirmación.

Sea $x \in ⋃ F$ , entonces existe $Y \in F$ tal que $x \in Y$ .

Caso 1: Si $Y = X$ , entonces $x \in X$ y por lo tanto, $x \in ⋃ F^{'} \cup X$ .

Caso 2: Si $Y \neq X$ , entonces $Y \in F^{'}$ y así, $x \in ⋃ F^{'}$ .

Los casos anteriores muestran que $⋃ F \subseteq ⋃ F^{'} \cup X$ .

Ahora, como $F^{'} \subseteq F$ y $X \in F$ , entonces $⋃ F^{'} \cup X \subseteq ⋃ F$ .

Así, $⋃ F = ⋃ F^{'} \cup X$ . Por lo tanto, $⋃ F$ es finito. Lo que concluye nuestra prueba.

Tarea moral

La siguiente lista de ejercicios te permitirá reforzar el contenido visto en esta sección.

Sea $X$ un conjunto finito y $x \in X$ . Si $| X | = n + 1$ , demuestra que $X ∖ {x}$ es finito y que $| X ∖ {x} | = n$ .
Sea $X$ es un conjunto finito. Prueba que si $A \subseteq X$ , entonces, $A$ es un conjunto finito.
Demuestra por inducción la regla de la suma generalizada. Como sugerencia, uno de los pasos intermedios es que enuncies formalmente y demustres que para todo natural $n$ se cumple que $(A_{1} \cup \dots \cup A_{n}) \cap B = (A_{1} \cap B) \cup \dots \cup (A_{n} \cap B)$ .

Más adelante…

En la siguiente entrada continuaremos con el contenido de esta sección, probaremos más propiedades sobre los conjuntos finitos y a su vez hablaremos acerca de la cardinalidad del conjunto potencia.

Entradas relacionadas

Ir a Teoría de los Conjuntos I
Entrada anterior: Teoría de los Conjuntos I: Teorema de Cantor-Schröder-Bernstein
Siguiente entrada: Teoría de los Conjuntos I: Conjuntos finitos (parte II)

Agradecimientos

Trabajo realizado con el apoyo del Programa UNAM-DGAPA-PAPIME PE109323 «Hacia una modalidad a distancia de la Licenciatura en Matemáticas de la FC-UNAM – Etapa 3»

El blog de Leo

Aprendiendo, creando y compartiendo matemáticas

Archivo de la etiqueta: conjuntos finitos

Teoría de los Conjuntos I: Conjuntos finitos (parte II)

Introducción

Conjuntos finitos y contención

Cardinalidad del conjunto potencia

Tarea moral

Más adelante…

Entradas relacionadas

Agradecimientos

Teoría de los Conjuntos I: Conjuntos finitos

Introducción

Conjuntos finitos

Principio de las casillas y unicidad de natural equipotente

La regla de la suma

Tarea moral

Más adelante…

Entradas relacionadas

Agradecimientos