9.2: Conjuntos finitos

En la sección anterior, se utilizó la frase “conjunto finito” sin definirlo formalmente. Seamos un poco más precisos. La siguiente taquigrafía es útil.

Definición 9.17. Para cada uno\(n\in \mathbb{N}\), defina\([n]:= \{1,2,\ldots,n\}\).

Por ejemplo,\([5]=\{1,2,3,4,5\}\). Observe que nuestra notación se parece a la notación que usamos para las clases de equivalencia. Sin embargo, a pesar de la notación similar, estos conceptos no están relacionados. Tendremos que confiar en el contexto para mantenerlos rectos.

La siguiente definición debe coincidir con tu intuición sobre lo que significa que un conjunto sea finito.

Definición 9.18. Un conjunto\(A\) es finito si\(A=\emptyset\) o\(card(A)=card([n])\) para algunos\(n\in\mathbb{N}\). Si\(A=\emptyset\), entonces decimos que\(A\) tiene cardinalidad 0 y si\(card(A)=card([n])\), entonces decimos que\(A\) tiene cardinalidad\(n\).

Demostremos algunos resultados sobre conjuntos finitos. Al probar los siguientes teoremas, no olvides considerar el conjunto vacío.

Teorema 9.19. Si\(A\) es finito y\(card(A)=card(B)\), entonces\(B\) es finito.

Teorema 9.20. Si\(A\) tiene cardinalidad\(n\in\mathbb{N}\cup\{0\}\) y\(x\notin A\), entonces\(A\cup\{x\}\) es finito y tiene cardinalidad\(n+1\).

Considera usar inducción al probar el siguiente teorema.

Teorema 9.21. Por cada\(n\in\mathbb{N}\), cada subconjunto de\([n]\) es finito.

El teorema 9.20 muestra que agregar un solo elemento a un conjunto finito aumenta la cardinalidad en 1. Como era de esperar, eliminar un elemento de un conjunto finito disminuye la cardinalidad en 1.

Teorema 9.22. Si\(A\) tiene cardinalidad\(n\in\mathbb{N}\), entonces para todos\(x\in A\),\(A\setminus \{x\}\) es finito y tiene cardinalidad\(n-1\).

El siguiente resultado nos dice que la cardinalidad de un subconjunto propio de un conjunto finito nunca es la misma que la cardinalidad del conjunto original. Resulta que este teorema no se sostiene para conjuntos infinitos.

Teorema 9.23. Cada subconjunto de un conjunto finito es finito. En particular, si\(A\) es un conjunto finito, entonces\(card(B)<card(A)\) para todos los subconjuntos adecuados\(B\) de\(A\).

La inducción es un enfoque sensato para probar los dos siguientes teoremas.

Teorema 9.24. Si\(A_1,A_2,\ldots, A_k\) es una colección finita de conjuntos finitos, entonces\(\displaystyle \bigcup_{i=1}^k A_i\) es finita.

El siguiente teorema, llamado el Principio Pigeonhole, es sorprendentemente útil. Pone restricciones sobre cuándo podemos tener una función de inyección. El nombre del teorema se inspira en la siguiente idea: Si\(n\) las palomas desean posarse en una casa con\(k\) casilleros y\(n>k\), entonces debe darse el caso de que al menos un hoyo contenga más de una paloma. Tenga en cuenta que 2 es el valor más pequeño de lo\(n\) que tiene sentido en la hipótesis a continuación.

Teorema 9.25. Si\(n,k\in\mathbb{N}\) y\(f:[n]\to [k]\) con\(n>k\), entonces no\(f\) es inyectivo.