12.2: Propiedades de los conjuntos finitos y su cardinalidad
- Page ID
- 118312
Conjuntos finitos versus secuencias finitas
Recordemos que una función\(f: \mathbb{N}_{<n} \rightarrow A\) define una secuencia finita de elementos del conjunto\(A\text{,}\) estableciendo
Si\(A\) es finito, entonces existe tal función\(f\) que es biyectiva, lo que lleva a lo siguiente.
Un conjunto\(A\) es finito si y solo si existe una secuencia finita a partir de\(A\) la cual cada elemento de\(A\) aparece exactamente una vez.
- El hecho anterior hace una importante conexión entre funciones y conteo. Si\(A\) es un conjunto finito,\(f: \mathbb{N}_{<n} \rightarrow A\) es una biyección correspondiente, y creamos secuencia\(\{a_k\}_{k=0}^m\) con\(a_k = f(k)\) como arriba, entonces somos capaces de enumerar los elementos de\(A\) en secuencia:
\ begin {ecuación*} A =\ {a_0, a_1,\ ldots, a_ {n-1}\}\ texto {.} \ end {equation*}
A su vez, escribir los elementos de\(A\) en secuencia es realmente solo una forma de contarlos, de una manera que es aproximadamente equivalente a contar con tus dedos (si tuvieras muchos dedos). De hecho, contar los elementos de ordena\(A\) totalmente los elementos de\(A\) (un concepto que encontraremos en un futuro capítulo). En el Capítulo 13, vamos a adaptar esta conexión entre funciones y conteo para determinar si es posible “contar” conjuntos infinitos.
- Debemos señalar, sin embargo, que el hecho anterior es esencialmente trivial una vez que “desentrañamos” las definiciones de conjunto finito y secuencia finita, ya que ambos implican una función con dominio\(\mathbb{N}_{<m}\) para algunos\(m\) y codominio\(A\text{.}\)
Un conjunto\(A\) es finito si y sólo si existe una secuencia finita a partir de la\(A\) cual contiene cada elemento de al\(A\) menos una vez.
- Idea de prueba
-
Si tenemos una secuencia que contiene cada elemento de al\(A\) menos una vez, podríamos convertirlo en una secuencia que contenga cada elemento de\(A\) exactamente una vez eliminando términos repetidos.
Conjuntos finitos versus bijecciones, subconjuntos y uniones
Las bijecciones se componen para crear bijecciones (ver Ejercicio 10.7.13). Este hecho nos permite relacionar conjuntos finitos entre sí.
Si uno de\(A,B\) es finito y existe una biyección\(f: A\rightarrow B\text{,}\) entonces ambos son finitos y\(\vert A \vert = \vert B \vert\text{.}\)
- Idea de Prueba.
-
Reconsiderar “uno de\(A,B\) finito” como disyunción: “\(A\)es finito o\(B\) es finito”. Después irrumpir en casos.
Supongamos\(A\) que es finito.
Supongamos\(\vert A \vert = n\text{,}\) para que exista una biyección\(g: \mathbb{N}_{<n}\rightarrow A\text{.}\) Entonces también\(f\circ g: \mathbb{N}_{<n} \rightarrow B\) es una biyección, entonces\(\vert B \vert = n\text{.}\)Supongamos\(B\) que es finito.
Supongamos\(\vert B \vert = n\text{.}\) Repetir el argumento del caso anterior, intercambiando roles de\(A\)\(B\) y y usando la biyección\(f^{-1} : B \rightarrow A\) en lugar de\(f\text{.}\)
Supongamos que\(B\) es un conjunto finito.
- Cada subconjunto\(A \subseteq B\) es finito, con\(\vert A \vert \le \vert B \vert\text{.}\)
- Si\(f: C \rightarrow B\) es una inyección, entonces\(C\) es finito con\(\vert C \vert \le \vert B \vert\text{.}\)
- Idea de Prueba.
-
- Esto le queda a usted como Ejercicio 12.6.1.
- Vamos a\(A\) representar la imagen\(f(C)\text{.}\)\(A \subseteq B\text{,}\) Entonces para que podamos aplicar Declaración 1 y Hecho\(\PageIndex{2}\).
También podemos relacionar la cardinalidad de conjuntos finitos con la operación sindical.
Supongamos\(A\) y\(B\) son subconjuntos finitos de un conjunto universal\(U\text{.}\)
Si\(A\) y\(B\) son disjuntos, entonces\(\vert A \sqcup B \vert = \vert A \vert + \vert B \vert\text{.}\)
\(\vert A \cup B \vert = \vert A \vert + \vert B \vert - \vert A \cap B \vert\text{.}\)
- Idea de Prueba.
-
La idea detrás de estas fórmulas debería ser obvia una vez que dibujes diagramas de Venn apropiados, pero las pruebas formales te quedan a ti en el Ejercicio 12.6.2.
Cardinalidad de conjuntos de poder de conjuntos finitos
¿Cuál es la cardinalidad de\(\mathscr{P}(\{1,2,3,\ldots,k\})\text{?}\)
Solución
¡Podemos resolver esto usando recursividad! En el Ejemplo 11.2.4, definimos la siguiente secuencia de subconjuntos de\(\mathbb{N}\text{,}\)
\ begin {reunir*} A_0 =\ varnothing,\ quad A-1 =\ {1\},\ quad A_2 =\ {1,2\},\ quad A_3 =\ {1,2,3\},\\\ ldots,\ quad A_k =\ {1, 2,\ ldots, k\},\ quad\ ldots\ text {,}\ end {recolección*}
recursivamente. También podemos expresar la secuencia\(N_k = \vert \mathscr{P}(A_k) \vert\) recursivamente. Primero,\(N_0 = 1\text{.}\) Entonces, desde
\ begin {ecuación*} A_ {k-1} =\ {1, 2,\ ldots, k-1\}\ subsetneqq\ {1,2,\ ldots, k-1, k\} = A_k,\ end {ecuación*}
podemos considerar\(\mathscr{P}(A_{k-1}) \subseteq \mathscr{P}(A_k)\text{.}\) (Ver Ejercicio 9.9.13.) Al hacerlo, podemos irrumpir\(\mathscr{P}(A_k)\) en la unión disjunta
\ begin {ecuation*}\ mathscr {P} (a_K) =\ mathscr {P} (A_ {k-1})\ sqcup\ mathscr {P} (A_ {k-1}) ^c.\ end {ecuación*}
Observe que los elementos de\(\mathscr{P}(A_{k-1})\) son precisamente aquellos subconjuntos de\(A_k\) que no contienen el elemento\(k\text{,}\) y por lo tanto los elementos de\(\mathscr{P}(A_{k-1})^c\) son precisamente aquellos subconjuntos de\(A_k\) que contienen el elemento\(k\text{.}\) So
\ begin {ecuación*} B\ in\ mathscr {P} (A_ {k-1})\ quad\ Rightarrow\ quad B\ cup\ {k\}\ in\ mathscr {P} (A_ {k-1}) ^c\ text {.} \ end {equation*}
Esta correspondencia en realidad nos da una bijección
\ begin {align*}\ mathscr {P} (A_ {k-1}) &\ a\ mathscr {P} (A_ {k-1}) ^c,\\ B &\ mapsto B\ copa\ {k\}. \ end {align*}
(¡Verifica!)
Ahora tenemos
\ begin {ecuación*} N_ {k-1} =\ vert\ mathscr {P} (A_ {k-1})\ vert =\ vert\ mathscr {P} (A_ {k-1}) ^c\ vert\ text {.} \ end {equation*}
Desde
\ begin {ecuation*}\ mathscr {P} (a_k) =\ mathscr {P} (A_ {k-1})\ sqcup\ mathscr {P} (A_ {k-1}) ^c\ text {,}\ end {ecuación*}
tenemos entonces
\ begin {ecuación*} n_k = N_ {k-1} + N_ {k-1} = 2 N_ {k-1}\ text {,}\ end {ecuación*}
una secuencia definida recursivamente. Resolver esta relación de recurrencia por rendimientos de iteración
\ begin {ecuación*} n_k = 2^k\ texto {.} \ end {ecuación*}
Verificar que el mapa
\ begin {align*}\ mathscr {P} (A_ {k-1}) &\ a\ mathscr {P} (A_ {k-1}) ^c,\\ B &\ mapsto B\ copa\ {k\}. \ end {align*}
en la solución al Ejemplo Trabajado anterior es una bijección.
Podemos usar la idea de Ejemplo Trabajado\(\PageIndex{1}\) para probar un hecho similar pero más general.
Si\(\vert A \vert = n\text{,}\) entonces\(\vert \mathscr{P}(A) \vert = 2^n\text{.}\)
- Idea de Prueba.
-
Dado que\(A\) tiene la misma cardinalidad que el conjunto\(\{1,2,3,\dots,n\}\text{,}\) existe una biyección entre los dos conjuntos. En el Ejercicio 12.6.8, se le pide que demuestre que dos conjuntos de la misma cardinalidad también tienen conjuntos de poder de la misma cardinalidad. Usando este hecho y el resultado del Ejemplo Trabajado\(\PageIndex{1}\), tenemos
\ begin {ecuación*}\ vert\ mathscr {P} (A)\ vert =\ vert\ mathscr {P} (\ {1,2,3,\ dots, n\})\ vert = 2^n\ text {.} \ end {ecuación*}
Conjuntos infinitos
un conjunto que no es finito
el conjunto\(A\) es infinito
el conjunto\(A\) es finito
Para demostrar que un conjunto\(A\) es infinito usando la definición técnica, debemos demostrar que ninguna biyección\(\mathbb{N}_{<m} \to A\) puede existir, por cada valor de cardinalidad\(m\text{.}\) Pero si\(A\) es infinito, habrá muchas funciones inyectoras\(\mathbb{N}_{<m} \hookrightarrow A\) para cada\(m\text{.}\) Por lo tanto, hay que demostrar que no\(\mathbb{N}_{<m} \twoheadrightarrow A\) puede existir ninguna sobrejección, por cada\(m\text{.}\)
Supongamos que tenemos un alfabeto que consiste en una sola letra\(\Sigma = \{\text{x}\}\text{.}\) Luego el conjunto de palabras
\ begin {ecuación*}\ Sigma^ {\ ast} =\ {x,\, xx,\, xxx,\,\,\ ldots\}\ end {ecuación*}
es infinita.
Para verificar esto, vamos a argumentar que ninguna función\(\mathbb{N}_{<m} \to \Sigma^{\ast}\) puede ser suryectiva, no importa el valor de cardinalidad\(m\text{.}\) Así supongamos que\(m \in \mathbb{N}\) es fija pero arbitraria, y\(f: \mathbb{N}_{<m} \rightarrow \Sigma^{\ast}\) es una función arbitraria. Siguiendo la Prueba de Surjectividad (que también describe cómo demostrar que una función no es suryectiva), debemos exhibir un elemento de ejemplo en\(\Sigma^{\ast}\) que no es la imagen bajo\(f\) de ningún elemento de dominio en\(\mathbb{N}_{<m}\text{.}\)
La función\(f\) define una secuencia finita de palabras de\(\Sigma^{\ast}\text{:}\)
\ begin {ecuation*} w_0, w_1, w_2,\ ldots, w_ {m-1},\ end {equation*}
donde cada uno\(w_j\) es la imagen\(f(j)\text{.}\) Tenemos dos casos.
Cada uno\(w_j\) es la palabra vacía.
En este caso, claramente\(f\) no puede ser suryectiva ya que la palabra que consiste en la letra única no\(x\) está en la secuencia de salidas para\(f\text{.}\)
De lo contrario.
En este caso, considere la palabra que obtenemos al concatenar las palabras\(w_0, w_1, \ldots, w_{m-1}\) juntas dos veces sobre:
\ begin {ecuación*} w = w_0 w_1 w_2\ cdots w_ {m-1} w_0 w_1 w_2\ cdots w_ {m-1}\ texto {.} \ end {equation*}
(Tenga en cuenta que esto no es multiplicación, solo estamos escribiendo las palabras una tras otra para crear una palabra grande.) Entonces esta palabra es ciertamente más larga que cualquiera de las palabras individuales\(w_j\text{,}\) y así no puede ser igual a una de esas palabras. (La razón por la que hemos concatenado todos los\(w_j\) dos veces es para que no tengamos que considerar por separado el caso de que todos menos uno de los\(w_j\) estén vacíos, ya que en ese caso concatenar todo el\(w_j\) solo una vez no produciría realmente un resultado que sea más largo que ese no vacío\(w_j\text{.}\)) Dado que esta palabra larga no está en la secuencia de elementos de imagen para\(f\text{,}\) la función\(f\) no puede ser suryectiva.
Si bien no tenemos esperanzas de demostrar que un conjunto\(A\) es infinito demostrando que las funciones\(\mathbb{N}_{<m} \to A\) no pueden ser inyectoras, si lo deseamos podemos argumentar el uso de la inyectividad simplemente dando la vuelta a las cosas. Si una biyección\(\mathbb{N}_{<m} \to A\) fuera posible, su inversa también\(A \to \mathbb{N}_{<m}\) sería una biyección. Entonces otra manera de demostrar que un conjunto\(A\) es infinito es demostrar que ninguna inyección\(A \to \mathbb{N}_{<m}\) es posible, por cada número de cardinalidad\(m\text{.}\)
También podemos demostrar que un conjunto es infinito relacionándolo con conjuntos infinitos conocidos.
Supongamos que\(A\) es un conjunto infinito.
- Cada conjunto\(B\) que contiene\(A\) como subconjunto (i.e.\(B \supseteq A\)) es infinito.
- Si\(f: A\rightarrow B\) es una inyección, entonces también\(B\) es infinita.
- Prueba.
-
- Esto le queda a usted como Ejercicio 12.6.4.
- Esto es solo lo contrapositivo de la Declaración 2 de hecho\(\PageIndex{3}\).
Demostrar que si\(\Sigma \ne \varnothing\text{,}\) entonces\(\vert \Sigma^{\ast} \vert = \infty\text{,}\) independientemente de si\(\vert \Sigma \vert \lt \infty\) o\(\vert \Sigma \vert = \infty\text{.}\)
Solución
Si\(\Sigma \ne \varnothing\text{,}\) entonces existe alguna\(x \in \Sigma\text{.}\) Consideremos el alfabeto restringido\(\Xi = \{x\}\text{.}\) En Ejemplo\(\PageIndex{2}\), demostramos que\(\Xi^{\ast}\) era infinito. Claramente\(\Xi \subseteq \Sigma\) implica\(\Xi^{\ast} \subseteq \Sigma^{\ast}\text{,}\) que aplicando la Declaración 1 de Hecho\(\PageIndex{5}\) podemos concluir que también\(\Sigma^{\ast}\) es infinito.