problemas demostrando cada subconjunto de un conjunto finito es finito con ingenua teoría de conjuntos

Question

En un primer curso de licenciatura en análisis, han establecido un modelo de los números naturales (sin el cero), una prueba por inducción, definición recursiva, inyectividad, surjectivity, bijectivity de mapas de primaria y de las propiedades y las siguientes definiciones y hechos:

• para cada $m \in \mathbb{N}$ el conjunto $A_m := \{k \in \mathbb{N};\ 1 \leq k \leq m\}$,
• dos conjuntos de $M$ $N$ son equipotente si hay un bijection $f \colon M \to N$, escrito $M \sim N$,
• un conjunto $M$ es finito si está vacía o equipotente a $A_m$ algunos $m \in \mathbb{N}$,
• $\forall m, n \in \mathbb{N}\colon A_m \sim A_n \Leftrightarrow m = n$,
• la cardinalidad de un finito no vacío set $M$ $\#M = m$ donde $M \sim A_m$, y
• cada subconjunto no vacío de números naturales tiene un mínimo elemento.

Ahora tienen que demostrar que un subconjunto de un conjunto finito no vacío es de nuevo finito.

Tengo que presentar una solución para ellos. Es claro que uno puede restringir este problema:

Para $m \in \mathbb{N}$ si $T \subseteq A_m$, entonces no es un $n \in \mathbb{N},\ n \leq m: T \sim A_n$.

Traté de definir $T_1 = T$ y para $k \in \mathbb{N}$ $T_{k+1} := T_k \setminus \{\min T_k\}$ si $T_k \neq \emptyset$ $T_{k+1} := \emptyset$ si $T_k = \emptyset$. Ahora quiero demostrar que hay un $n \in \mathbb{N} \colon T_{n+1} = \emptyset$. Esto haría $A_n \to T, k \mapsto \min T_k$ un bijection.

¿Cómo puedo proceder? Pensé que tal vez se puede utilizar la inducción de la cardinalidad de la $T_k$, pero yo no lo veo de inmediato y tengo poco tiempo. Uno puede tratar de demostrar que para cualquier $k \in \mathbb{N}$ el conjunto $T_k$ es finito y si $T_k \neq \emptyset$,$\# T_{k+1} + 1 = \#T_k$, pero luego ¿qué?

Answer 1

Para mostrar que hay un $n$ tal que $T_{n+1} = \emptyset$, sólo tenga en cuenta que el $\min ( T_k ) \geq k$ ( $T_k \cap A_{k-1} = \emptyset$ ; una fácil prueba por inducción), y por lo $T_{m+1}$ debe estar vacío (si $T \subseteq A_m$).

---

Yo personalmente proceder de una manera diferente, y no se molestan mucho en tratar de demostrar un bijection. En su lugar, por inducción de mostrar que para cada una de las $m$ cada vacía $T \subseteq A_m$ es finito. El caso base $m = 1$ es trivial. Supongo que es conocida por $m$, y deje $T \subseteq A_{m+1}$ ser no vacío. Hay tres casos:

1. Si $T = A_{m+1}$, entonces estamos hecho.
2. Si $m+1 \notin T$, entonces en realidad $T \subseteq A_m$, y está hecho por hipótesis.
3. Si $T \neq A_{m+1}$$m+1 \in T$, podemos intercambiar $m+1 \in T$ algo no $T$ a un subconjunto $S \subseteq A_m$ equipotente con $T$. (Y por lo $T$ es equipotente con un conjunto finito.)

Answer 2

Deje $f : k \mapsto \min T_k$.

Utilice el hecho de que $b \notin A \setminus \{b\}$ y la inducción para demostrar que $\min T_i = \min T_j \implies \min T_j \in T_i \implies i = j$ (asumiendo $i \geq j$) y, por tanto, $f$ es una inyección.

Utilice el hecho de que $(A \setminus \{b\}) \cup \{b\} = A$ (asumiendo $b \in A$) para demostrar que $\bigcup \{\min T_i \} = T$ e lo $f$ es un surjection.