El subconjunto de un conjunto finito es finito

Question

Definimos $A$ es un conjunto finito si existe una biyección entre $A$ y un conjunto de la forma $\{0,\ldots,n-1\}$ para algunos $n\in\mathbb N$ .

¿Cómo podemos demostrar que un subconjunto de un conjunto finito es finito? Por supuesto, basta con demostrar que para un subconjunto de $\{0,\ldots,n-1\}$ . ¿Pero cómo lo hago?

Answer 1

La prueba es esencialmente el principio de encasillamiento, y se demuestra por inducción.

Denotemos $[n]=\{0,\ldots,n-1\}$ . Lo que queremos demostrar es en dos partes:

1. Si $A\subseteq[n]$ entonces $A=[n]$ o existe una biyección entre $A$ y $[m]$ para algunos $m<n$ .

2. Si $m<n$ entonces no existe una biyección desde $[n]$ en $[m]$ . Equivalentemente queremos demostrar que si $f\colon[n]\to[n]$ es inyectiva entonces es suryectiva. También podemos querer demostrar que si $f\colon[n]\to[m]$ entonces $f$ no es inyectiva, o $f\colon[m]\to[n]$ entonces $f$ no es sobreyectiva.

La primera parte no es muy difícil, definimos por inducción $f(0)=\min A$ y $f(k+1)=\min A\setminus\{f(0),\ldots,f(k)\}$ . O bien $f$ es una biyección entre $A$ y $[n]$ o la inducción tuvo que parar antes y $f$ es una biyección entre $[m]$ y $A$ para algunos $m<n$ . Obsérvese que esto no es una pregunta, ya que $A$ es un conjunto de números naturales, y es un subconjunto de $[n]$ por lo que no puede contener más elementos que $[n]$ (más en el sentido real, no en el sentido de cardinalidad).

La segunda parte es complicada porque parece muy obvia. Aquí es donde se demuestra realmente el principio de encasillamiento.

Demostramos esta parte por inducción. Para $n=0$ esto es obvio porque $[0]=\varnothing$ .

Supongamos que para $[n]$ es cierto que si $f\colon[n]\to[n]$ es inyectiva, entonces es sobreyectiva. Queremos demostrar que esto también es cierto para $[n+1]$ .

Dejemos que $f\colon[n+1]\to[n+1]$ sea una función inyectiva. Hay dos casos:

1. Si $f(k)\neq n$ para todos $k<n$ entonces restringiendo $f$ a $[n]$ es una función inyectiva de $[n]$ en $[n]$ . Por la hipótesis de inducción tenemos que la restricción de $f$ a $[n]$ es suryente, por lo tanto $f(n)\notin[n]$ (por lo demás $f$ no es inyectiva) y por tanto $f(n)=n$ y así $f$ también es sobreyectiva.

2. Si $f(k)=n$ para algunos $k<n$ por inyectabilidad esta $k$ es único. Definimos $g$ de la siguiente manera: $$g(x)\begin{cases} f(n) & x=k\\ n & x=n\\ f(x) & x\neq k,n\end{cases}$$ De ello se desprende que $g$ también es inyectiva, y para todo $k< n$ tenemos que tener $g(k)\neq n$ (porque $g(n)=n$ y $g$ es inyectiva). Por tanto, por el caso anterior sabemos que $g$ es suryente. De ello se desprende que $f$ también es suryectiva, como se quería.

---

Unas palabras sobre el axioma de elección y la finitud . La prueba anterior demuestra que finito Los conjuntos son Dedekind-finito . Hay otras formas de definir la finitud, todas ellas verdaderas para conjuntos finitos, pero que también pueden ser verdaderas para conjuntos infinitos. Por ejemplo, "toda suryección es una biyección" puede fallar para conjuntos infinitos Dedekind-finitos; o "toda partición linealmente ordenada es finita"; etc.

Sin embargo, basta con asumir el axioma de elección, o en realidad el axioma de elección contable, para concluir que todos los conjuntos definidos por Dedekind son finitos. Por lo tanto, las formas de finitud anteriores son equivalentes una vez más. (La implicación inversa es falsa, por cierto, es consistente que el axioma de elección contable falle, pero todo conjunto Dedekind-finito es finito).

Answer 2

He aquí una prueba ligeramente diferente del principio de encasillamiento:

Supongamos que $f:[n]\to[n]$ es una inyección que no es sobreyectiva para $n>0$ . Podemos suponer sin pérdida de generalidad que $n$ no está en el rango de $f$ . Porque si lo es, mapeamos el elemento que se mapea a $n$ a algún elemento que no esté en el rango en su lugar y obtener una nueva inyección que no sea sobreyectiva con $n$ no en el rango. Ahora demostramos que $f|[n-1]$ es inyectiva, pero no suryente. Trivialmente, la restricción de una inyección es una inyección. Pero $f(n)\in[n-1]$ no está en el rango de $f|[n-1]$ .

Answer 3

Dejemos que $I_n = \{0, 1, ... n-1\}$ y $B\subset A$ . Entonces existe una inyección de $B\to I_n$ ya que hay una biyección desde $A\to I_n$ . Dado que existe tal $n$ existe(*) un mínimo $j$ de manera que haya una inyección de $B\to I_j$ y si eso no fuera una suryección allí podríamos construir una inyección de $B\to I_{j-1}$ (a menos que $j=0$ pero luego $I_j=\emptyset$ y la función es trivialmente una suryección).

---

Si en lugar de ello se utiliza Dedekind-finito como definición de finito. Es decir, que toda función inyectiva sobre $A$ es sobreyectiva, entonces resulta bastante obvio.

Si $B\subseteq A$ no fuera finito habría un mapeo inyectivo desde $B$ a $C\subsetneq B$ y podríamos ampliarlo a $A$ tomando el mapa de identidad fuera de $B$ entonces tendríamos un mapeo inyectivo desde $A$ a un subconjunto adecuado de $A$ lo que significa que $A$ es infinito, lo que contradice la suposición.

---

(*) Esto se basa en que todo conjunto no vacío $X$ (de $j$ de manera que haya una inyección $B\to I_j$ ) de los números naturales tiene un elemento mínimo que se puede demostrar por inducción.

Answer 4

Para cualquier $k \in \Bbb N$ dejar $[k]$ representan el conjunto $\{0,\ldots,k-1\}$ .

Lema 1: Si $A$ es un conjunto finito, entonces también lo es $A \cup \{b\}$ .
Prueba
Dejemos que $\sigma: A \xrightarrow{\sim} [n]$ sea una correspondencia biyectiva.
Si $b \in A$ no hay nada que hacer.
En caso contrario, defina $\tau: A \cup \{b\} \to [n+1]$ de la siguiente manera:

$\tau(x) = \left\{\begin{array}{lr} \;\;\;\sigma(x)\, \;\;\text{ |} & \text{for } x \in A\\ \;\;\;n \;\;\;\;\;\;\;\text{ |} & \text{for } x = b \end{array}\right\}$

Es elemental comprobar que $\tau$ es una biyección. $\quad \blacksquare$

Proposición 2: Si $A \subset [n]$ entonces $A$ es un conjunto finito.
Prueba
Podemos suponer que $A \ne \emptyset$ .
Para $0 \le m \le n$ definir $A_m = A \cap [m]$ para que $A = A_n$ .
Cada $A_m$ con $m \lt n$ es igual a $A_{m+1}$ o es igual a $A_{m+1} \setminus \{m\}$ .
Para obtener una contradicción, suponga que $A$ es infinito.
Por el lema 1 y la inducción decreciente finita paso a paso, si $A_n$ es infinito entonces todos los conjuntos $A_m$ con $0 \le m \le n$ también debe ser infinito. Pero

$\quad A_0 = A \cap [0] = A \cap \emptyset = \emptyset$

y hemos llegado a una contradicción. $\quad \blacksquare$

---

Observación: También podemos utilizar el lema 1 para proporcionar una prueba directa que utilice la inducción directa; para $n \in \Bbb N$ , defina el enunciado

$P(n):$ Si un conjunto $A$ puede ponerse en correspondencia biyectiva con $[n]$ y $B \subset A$ entonces existe $m \in \Bbb N$ tal que $B$ puede ponerse en correspondencia biyectiva con $[m]$ .

Answer 5

Para cualquier $k \in \Bbb N$ dejar $[k]$ representan el conjunto $\{0,\ldots,k-1\}$ .

Proposición 1: Si $A$ es finito y $B \subset A$ entonces $B$ es finito.
Prueba
Para obtener una contradicción, tome el mínimo $n$ para los que existen conjuntos $A$ y $B$ y una función $\sigma: [n] \to A$ tal que $B \subset A$ y $B$ no es finito.
Debe ser cierto que $B \subsetneq A$ y así dejar que $a \in A$ con $a \notin B$ .
Dejemos que $j_a = \sigma^{-1}(a)$ y definir

$\tau(x) = \left\{\begin{array}{lr} \;\sigma(x)\, \;\;\;\;\;\;\text{ |} & \text{for } x \lt j_a \\ \;\sigma(x+1) \; \text{ |} & \text{for } x \ge j_a \end{array}\right\}$

La función $\tau$ es una correspondencia biyectiva entre $[n-1]$ y $A \setminus \{a\}$ ; también, $B \subset A \setminus \{a\}$ .
Pero entonces $n$ no es el número entero mínimo y hemos llegado a una contradicción. $\quad \blacksquare$