El conjunto de funciones que son cero casi por todas partes es enumerable

Question

Me he vuelto un poco abrumado con un problema en el que estoy trabajando yo tenía un amigo que me diga que mi prueba fue mal. Agradecería si alguien podría explicar por qué estoy equivocado, y, posiblemente, ofrecer una solución alternativa.

Problema: Una función de $f\colon \mathbb{N} \to \mathbb{N}$ es cero en casi todas partes iff $f(n)=0$ para todos excepto un número finito de parámetros. Se puede demostrar que el conjunto de funciones que son cero en casi todas partes es enumerable.

Intento: Vamos A $E=\{f\colon \mathbb{N} \to \mathbb{N}\mid f \text{ is zero almost everywhere}\}$. Deje $Q\colon \mathbb{N}\to E$ tal que $Q(n)=f_n$ donde definimos $f_n(x)=0$ para todos, pero $n\in\mathbb{N}$ valores.

Fix $f\in E$, entonces debemos demostrar que existe un número entero $n\in N $ tal que $f=f_n$, pero por defnition $f$ es cero en casi todas partes, por lo $f(x)=0$ para todos, pero de un número finito de $r\in\mathbb{N}$ valores. Elija $n=r$.

Me doy cuenta de que esta es una incorrecta prueba, pero no estoy muy seguro de dónde. También he utilizado nunca una sugerencia que me dieron que dice usar el hecho de que una contables de la unión de conjuntos contables es contable.

Gracias.

Answer 1

Vamos a encontrar una biyección explícita de $E$ $\mathbb{N}\setminus\{0\}$. Entonces es fácil obtener un bijection explícita de $E$ $\mathbb{N}$ (o en la otra dirección).

Sea $p_0,p_1,p_2,\dots$ los primos en su orden natural. Si $f$ es una función que es $0$ casi en todas partes, mapa $f$ $$p_0^{f(0)}p_1^{f(1)}p_2^{f(2)}p_3^{f(3)}\cdots.\tag{1}$ $ el producto (1) es un producto finito. Por el teorema Fundamental de la aritmética, la asignación que sólo hemos definido es una biyección de $E$ $\mathbb{N}\setminus\{0\}$.

Answer 2

$Q$ no se define correctamente. Dices que $Q(n)$ es una función que no es cero para exactamente los valores de $n$, pero hay (infinitamente) muchas funciones que satisfacen esta propiedad.

Si especificar cuál es esa función (o usar el axioma de elección), entonces $Q$ será ciertamente no sobreyectiva.

¿Qué le parece lo siguiente? Definir $E_k$ como el conjunto de funciones que son $0$ $n>k$ ($n\le k$ puede ser cero o no). Entonces $E_k$ es finito. Ahora use la sugerencia que usted ha mencionado.

Answer 3

Sugerencia: Cuente sus funciones como sigue. Que $A_N$ ser el conjunto de todas las funciones que son distinto de cero sólo para $n \leq N$ y todo distinto a cero los valores de la función están menor o igual a $N$. Evidentemente el juego es $\cup_N A_N$. Pero cada $A_N$ es finito, por lo que si sabes que una Unión contable de conjuntos finitos es a lo más contable, entonces se realiza.

Answer 4

Una forma común para demostrar que un conjunto es enumerable es utilizar el siguiente hecho (también la sugerencia de siempre):

Una unión que en la mayoría de los countably muchos conjuntos enumerables es enumerable.

La prueba de esta afirmación se aplica exactamente igual a la de la prueba usual de que los racionales son enumerables.

Con esto, se puede descomponer el conjunto de $E$ en una unión contables muchos conjuntos enumerables?

(Sugerencia: ¿cuántos elementos de $E$ tienen exactamente $1$ elemento distinto de cero? Cuántos exactamente $2$? Cuántos...)

Answer 5

Cada una de las $\Bbb N\to\Bbb N$ función es una secuencia natural. Vamos a definir un "retrato" de una casi-cero en todas partes de la función como una secuencia finita de todos los argumentos, para que la función tiene un valor diferente de cero, intercaladas con esos valores. Por ejemplo, $f=(0, 0, 15, 0, 27, 0,...)$ tiene un retrato de $P(f)=(3, 15, 5, 27)$. Por supuesto, el retrato es única: cada función tiene su propia vertical. También vamos a definir un natural "tamaño" de una función de $f$ como una suma de retrato términos de $S(f)=\sum_{n\in\Bbb N}P(f)_n$. La función de ejemplo de arriba tiene el tamaño de $3+15+5+27=50$.

Todas las funciones pueden ser ordenados por un aumento de tamaño. Por supuesto, hay muchos, pero siempre finitely muchas de las funciones del mismo tamaño. Todas las funciones del mismo tamaño pueden ser ordenados lexicográficamente por su retrato.
De esta manera podemos definir una secuencia de casi todas-en todas partes de cero secuencias naturales, que estabilishes sus enumerability.