El conjunto de todas las secuencias finitas de miembros de un conjunto contable es también contable

Question

Mientras leía "A mathematical introduction to Logic" de Enderton, me encontré con la prueba de la siguiente frase: "El conjunto de todas las secuencias finitas de miembros del conjunto contable A es también contable".

Prueba: El conjunto S de todas estas secuencias finitas puede caracterizarse por la ecuación $$S=\bigcup_{n \in N} A^{n+1}$$ Como A es contable, tenemos una función f que mapea A uno a uno en N. La idea básica es mapear S uno a uno en N asignando a $(a_0,a_1,...,a_m)$ el número $2^{f(a_0)+1}3^{f(a_1)+1}\cdot ... \cdot p_m^{f(a_m)+1}$ , donde $p_m$ es el $(m+1)$ primera. Esto adolece del defecto de que esta asignación podría no estar bien definida. Porque es posible que haya $(a_0,a_1,...,a_m)=(b_0,b_1,...,b_n)$ con $a_i$ y $b_j$ en A pero con $m\neq n$ . Pero esto no es grave; basta con asignar a cada miembro de S el menor número que se pueda obtener de la forma anterior. Esto nos da un mapa bien definido; es fácil ver que es uno a uno.

Nota: P es una secuencia finita de miembros de A si para algún entero positivo $n$ tenemos $P=(x_1,...,x_n)$ donde cada $x_i \in A$ .

En primer lugar, no puedo entender por qué la primera asignación podría no estar bien definida y la segunda sí. En segundo lugar, no puedo entender qué quiere decir Enderton con "simplemente asignar a cada miembro de S el número más pequeño que se pueda obtener de la forma anterior". Por cierto, ¿es $(a,b,c,d) = ((a,b),(c,d))$ ¿Es cierto? Además, ¿en qué casos puedo omitir/añadir paréntesis en una tupla para tener una tupla igual?

Answer 1

Así que tal vez sea una buena idea trasladar parte de los comentarios aquí, ya que son relevantes para responder a la pregunta:

En primer lugar, no existe una definición única de $(a,b,c,d)$ pero el estándar es $(a,(b,(c,d)))$ . Mi opinión es que dependiendo de la definición puede ser imposible que surja un problema, pero utilizando la definición que he proporcionado es posible tener un conflicto.

El problema surge en el caso de que alguna tupla de elementos de $A$ también está en $A$ . Supongamos, por ejemplo, que $a,b\in A$ pero al mismo tiempo $(a,b)\in A$ . Además, supongamos que $f(a)=1,f(b)=2,f((a,b))=3$ . Entonces el triple $(a,a,b)$ según la definición estándar es $(a,(a,b))$ . Entonces no está claro si hay que enviar $(a,(a,b))$ a $2^2\cdot3^4$ o a $2^2\cdot 3^2\cdot 5^3$ .

Lo que sugiere Enderton es elegir el menos $n$ tal que la secuencia $P$ se encuentra en $A^n$ . Por lo tanto, en nuestro ejemplo anterior debemos optar por denotar $(a,(a,b))$ con $2^2\cdot 3^4$ ya que este elemento está en $A^2$ y en $A^3$ pero $2<3$ .

Answer 2

Ya he dado esta respuesta en otro lugar. Permítanme repetirla aquí.

Para demostrar la contabilidad de $\bigcup _{n=1}^\infty A^n$ basta con dar una función inyectiva $\phi$ de esta unión a $A$ . Sin pérdida de generalidad, tome $A$ para ser el conjunto de enteros positivos y para el bien de esta prueba considerarlos como escritos en base 10, que hace uso de los símbolos $0, 1,2$ hasta $9$ . Ahora introduzcamos 3 símbolos más, a saber, la coma, el paréntesis abierto y el cerrado, que deben interpretarse como los símbolos (adicionales) de los números diez, once y doce, respectivamente, en base tres.

Ahora la inyección $\phi$ toma un elemento típico como $(3,8,17)$ y los interpreta como una expresión base trece: $(3,8,17)_{\rm thirteen}$ que expresado en base diez es $(11\times 13^7) + (3\times 13^6) + (10\times 13^5) + (8\times 13^4) +(10\times 13^3) + (1\times 13^2) + (7\times 13^1) + (12\times 1).$

Answer 3

No se define lo que $f$ es, pero mientras sea inyectiva y positiva no veo cómo se produce un conflicto. En particular, si $n \gt m$ uno de los números será divisible por $p_{m+1}$ y otro no. Me parece más sencillo tomar $(a_0,a_1,\ldots,a_m)$ a $2^{a_0}3^{a_1}\ldots p_m^{a_m}$ . La factorización única muestra que cada tupla va a una imagen distinta.

Para su último no hemos definido tuplas de tuplas, que es lo que $((a,b),(c,d))$ es. Si lo mapeamos recursivamente usando mi función $(a,b)\to 2^a3^b$ Así que $(a,b,c,d) \to 2^a3^b5^c7^d$ mientras que $((a,b),(c,d)) \to 2^{2^a3^b}3^{2^c3^d}$ que no son iguales.

Answer 4

Acabo de empezar ese libro y me gustaría añadir un poco a la respuesta de @Apostolos (que de hecho me ayudó a entender el tema).

La cuestión de cómo el hecho de que dos tuplas sean iguales corresponde a la igualdad de sus números de elementos, y los elementos en sí mismos se da en el libro justo antes del Teorema en cuestión (Lemma 0A) (el tratamiento de Enderton de las n-tuplas es similar al de @Apostolos con la única diferencia en la asociatividad, Enderton utiliza la definición recursiva "izquierda-asociativa" de las n-tuplas).

Creo que la fuente de la confusión aquí es que Enderton no ha centrado del todo la atención del lector (en mi opinión) en la cuestión a la que nos enfrentamos: saber cómo hacer una elección de (una del número finito de formas posibles) cómo un elemento de $S$ podría construirse como una secuencia de los elementos de $A$ .

La cuestión es que sólo nos interesan los elementos de $S$ . Así que no nos interesa enumerar todas las formas de cómo un $s \in S$ puede construirse como una secuencia de los elementos de $A$ .

En cambio, partimos de un $s \in S$ y luego mostrar cómo podemos recoger una sola cadena de $A^n$ por lo que un solo número de $\mathbb{N}$ .