Teoría de conjuntos: cardinalidad de un subconjunto de un conjunto finito.

Question

Supongamos que $A$ es un conjunto finito de cardinalidad $n$ . Y que $B$ sea un subconjunto de $A$ y la cardinalidad de $B$ es igual a $n$ . Entonces $B=A$ .

Muchos textos utilizan este hecho con mucha frecuencia, pero parece que lo dan por sentado. ¿Cómo puedo demostrarlo con rigor? Se agradecerá cualquier ayuda.

Answer 1

Desde $B \subseteq A$ podemos dividir $A = B \cup (A \setminus B)$ . Estos conjuntos son disjuntos. Tomando las cardinalidades, vemos $n = n + \left|A \setminus B\right|$ , lo que implica $|A \setminus B| = 0$ Por lo tanto $A \setminus B = \emptyset$ Así que $A = B$ .

Answer 2

Has dado con un punto muy sutil, que mucha gente puede pasar por alto cuando se encuentra por primera vez con este tema. Sí, tenemos que demostrar estas cosas.

Esto es una consecuencia del principio de encasillamiento. Si $B\subseteq A$ y $A$ es finito, entonces $A=B$ o bien no hay funciones inyectivas de $A$ en $B$ pero si $|A|=|B|$ entonces por definición existe una biyección desde $A$ en $B$ .

Así que esto, a su vez, se convierte en una cuestión de cómo demostrar el principio de encasillamiento. La respuesta es por inducción sobre el número de elementos, y se puede encontrar una prueba completa aquí .

Answer 3

Vamos a probar el contrapositivo declaración. Supongamos que $A$ tiene un subconjunto con la misma cardinalidad como $A$ (en otras palabras, $A$ es Dedekind infinito.) Vamos a mostrar que el $A$ es infinito.

Tomar un subconjunto $B$ $A$ con la misma cardinalidad como $A$. Luego hay un bijection $f : A \to B$ y un elemento $a \in A \setminus B$. De forma recursiva definir una función $h : \mathbb{N} \to A$ por

• $h(0) = a$
• $h(i+1) = f(h(i))$.

Utilizando el hecho de que la función de $f$ es inyectiva y su rango no contiene $a$, uno puede demostrar por inducción sobre $j \in \mathbb{N}$ que los elementos $h(0),\ldots,h(j)$ son distintos, por lo $h$ es una inyección de$\mathbb{N}$$A$. La existencia de una inyección significa que $\left|A\right| \ge \aleph_0$, lo $A$ es infinito.

(Hay un detalle escondido aquí, es decir, el hecho de que no puede ser una inyección de $\mathbb{N}$ a un conjunto finito. Esto puede ser demostrado por inducción sobre la cardinalidad del conjunto finito por un argumento similar a la que Asaf menciona.)