Demostrar que si A es contable, entonces también lo es $cl_f(A)$ .

Question

Sea B un conjunto y $f:B^m \rightarrow B$ . Por definición, dado un subconjunto $A \subseteq B$ el cierre de $A$ en $f$ denotado por $cl_{f}(A)$ es el subconjunto más pequeño de $B$ que contiene $A$ y se cierra bajo $f$ .

Demostrar que si A es contable, entonces también lo es $cl_f(A)$ .

Mi pregunta es, ¿cómo puedo definir una función tal que $cl_f(A) \mapsto A$ .

Answer 1

No podrás encontrar una función así (supongo que quieres una inyectiva, ya que si no, no sacas nada). Para verlo, supongamos $B=\mathbb{N}, m=1, f(x)=x+1,$ y $A=\{1\}$ . Entonces $cl_f(A)=\mathbb{N}$ mientras que $A$ es, por supuesto, finito.

El argumento de que $cl_f(A)$ es contable si $A$ tendrá que ser más abstracto. Para simplificar, supongamos que $m=1$ - así que $f:B\rightarrow B$ . El cierre $cl_f(A)$ puede desglosarse del siguiente modo:

• Sea $A_0=A$ .

• Una vez definido $A_n$ , dejemos que $A_{n+1}=\{f(x): x\in A_n\}$ .

Ahora podemos demostrar ( ejercicio ) que $cl_f(A)=\bigcup_{n\in\mathbb{N}} A_n$ .

Ahora utilizamos el importante hecho ( ejercicio ) que la unión de un número contable de conjuntos contables es contable. Junto con el punto anterior, esto nos dice que bastará con demostrar que cada $A_n$ es contable.

Así que ahora la pregunta es, ¿cómo hacemos que ? La respuesta es la inducción: queremos demostrar, por inducción sobre $n$ que $A_n$ es contable. Para $n=0$ es cierto por suposición (recuerde $A_0=A$ ).

Supongamos $A_n$ es contable; ¿cómo sabemos que $A_{n+1}$ ¿también es contable? Esto se deduce del siguiente hecho más general ( ejercicio ): que si $X\subseteq B$ es contable, entonces $\{f(x): x\in X\}$ es contable. Esto es algo así como la versión de "un paso" de lo que en realidad estás tratando de demostrar; ten en cuenta que en general $\{f(x): x\in X\}$ est mucho más pequeño que $cl_f(X)$ .

Así será la prueba:

• Demuestra cómo podemos descomponer $cl_f(A)$ en un número contable de piezas.

• Demostrar que el "cierre de un paso" de un conjunto contable es contable.

• Utilízalo para demostrar por inducción que cada pieza de $cl_f(A)$ es contable, si $A$ lo es.

• Termina utilizando el hecho de que una unión contable de conjuntos contables es contable.

---

Tenga en cuenta que los ejercicios anteriores son en realidad de dos tipos distintos. El segundo y el tercero tratan directamente de la manipulación de conjuntos contables, mientras que el primero trata realmente de finito conjuntos (o mejor dicho, secuencias finitas).

Obsérvese también que los ejercicios primero y tercero se complican cuando pasamos de $m=1$ al caso general. En particular, la versión general del tercer ejercicio es una aplicación de una versión más fuerte del segundo ejercicio: que si tomo el producto cartesiano finito de conjuntos contables, el resultado sigue siendo contable. (Es un buen ejercicio demostrar que la palabra "finito" es necesaria allí: demuestre que el producto cartesiano de $\mathbb{N}$ -muchos ejemplares de $\{1, 2\}$ es incontable).