¿Es el conjunto de la disminución de las funciones de $\Bbb N$ $\Bbb N$ contable?

Question

Quiero probar el sistema de disminución de las funciones de $\Bbb N$ $\Bbb N$ es contable.

Yo una función decreciente, $f$, con un elemento menos, $n$, y que $x$ ser el número más pequeño tal que $f(x)=n$.

¿Es aceptable que desde $f$ es decreciente para todos los $y>x$, $f(y)=f(x)=n$ %?

Al hacerlo, $i$ continuación, puede mostrar aumento de no funciones pueden ser definidas por el conjunto de $\{f(1),\dotsc,f(x)\}$ y creo que puedo hacer el resto.

Answer 1

Definir $$S_N:=\{f:\mathbb{N}\to\mathbb{N}\;|\; f \text{ is non-increasing and } f(1)\leq N\}$$ A continuación, el conjunto es $$S=\bigcup_{N=1}^\infty S_N$$ Desde una unión de conjuntos contables es contable, es suficiente para mostrar que cada una de las $S_N$ es contable. Ahora, afirman que la inducción en $N$.

AÑADIDO (la inducción de argumento): $S_1$ es contable, ya que su único elemento es la función de $f(n)=1,\forall n\in\mathbb{N}$. Ahora supongamos $S_N$ es contable. Una función en $S_{N+1}$ es la función constante $f(n)=N+1,\forall n\in\mathbb{N}$, o se alcanza un número $m=f(n_0)\leq N$ en algún punto de $n_0\in\mathbb{N}$. Ahora, después de esta $n_0$, la función puede ser considerada como una función de la $S_N$. Por lo tanto, para dar una función en $S_{N+1}$ es para dar un entero $n_0$ y una función en $S_{N}$. Es decir, $S_{N+1}$ es en bijection con $\mathbb{N}\times S_{N}$, que es contable desde $S_N$ es contable (por la hipótesis de inducción). Por lo tanto, $S_{N+1}$ es contable.

Answer 2

Sugerencia: Cada secuencia [estrictamente] decreciente de números naturales es finito. Observar que una función decreciente es completamente determinada por un conjunto finito de números naturales y concluir la countability.

Answer 3

Sugerencia $\ $ por la codificación de una disminución de la secuencia por una secuencia finita de productos naturales (por ejemplo, lista el número finito de lugares donde cambia el valor) el conjunto es un subconjunto de $\,\bigcup_{\,k=1}^{\,\infty}\! \Bbb N^k,$ una Unión contable de countables.

Answer 4

Sí; el número de no-disminución de las funciones de $f: \mathbb N \rightarrow \mathbb N$ contables: 0)sabemos que estas funciones deben ser eventualmente constante, ya que f(1) es un valor finito, y hay un número infinito de valores {$f(2),f(3),....$}. Dicen las funciones es constante después de $f(k)$.

1)Activar una función en un decimal cadena, por {$f(1),f(2),..,f(k),f(k),..$} $\rightarrow 0.f(1)f(2)....f(k)f(k)....$

2)Dividir el número decimal de la imagen en la suma: $$0.f(1)f(2)...f(k-1)0000...0 +0.0000f(k)f(k)...f(k)...$$

3)Cada uno de los términos de la suma es un número Racional, por lo que la cadena representa un número Racional.

4)La colección a continuación, se inyecta en los Racionales. Pero sabemos que el conjunto de constantes de las funciones de $f(n)=k; k=1,2,3,...$ también es no decreciente. Por lo que la colección es countably-infinito.

---

Explicación Extendida: El conjunto de la no disminución de las funciones contables debido a que cada cadena de $f(1),f(2),...,f(n)$ , cuando es visto como una expansión decimal $0.f(1)f(2)....$, es un número Racional. Esto es debido a que la secuencia {$f(1),f(2),...$} debe ser, finalmente,-constante, es decir, existe un número entero $k$ después de que $f(k)=f(k+1)=....=f(k+n)=.....$.

Así que tenemos la tarea: $$ f(1),f(2),...,f(n),... \rightarrow 0.f(1)f(2)....f(n).. ..$$

Y el argumento es que la expresión de la derecha, visto como un número Real, es Racional.

La prueba de la demanda es que , desde que la cadena es el tiempo constante, dicen que después de la $k$-ésimo lugar, usted puede escribir la cadena como:

$\frac {.f(1).....f(k-1)}{10^{k-1}} + 0.00000000.f(k)f(k)....f(k)....=$ (donde el primer $f(k)$ se inicia en el $k-$th spot), que es una suma de Racionales, y por tanto, es un Racional. Por lo que el (la imagen) de la secuencia de la no disminución de los mapas es un subconjunto de los Racionales. EDIT: Lo que hacemos es, si $f(k)$ $n$ dígitos, giramos a cada dígito en un plazo en la expansión decimal, por ejemplo, si $f(x)=753$, $753 \rightarrow 0.00000753753...753....$

Tenga en cuenta que las colecciones es infinito, ya que la constante de secuencia $f(n)=k; k=1,2,3,...$ hace el trabajo, es decir, es no decreciente.

Answer 5

Nota para los nerds: los siguientes evita el axioma de elección, pero no es intuitionistically válido.

Deje $f\colon \Bbb N \to \Bbb N$ ser una función decreciente, donde $\Bbb N = \{0,1,\dotsc\}$ (estoy incluyendo $0$).

Deje $n-1$ ser el número más pequeño en el que $f$ toma en su valor más pequeño. Entonces podemos representar a $f$ como finita de la secuencia, una $n$-tupla, $f(0),f(1),\dotsc,f(n-1)$. El conjunto de todas las representaciones, entonces es un subconjunto del conjunto $\Bbb N^{<\omega}$ de tuplas de números naturales.

Queremos mostrar, entonces, que el $T:=\Bbb N^{<\omega}$ es contable. Puesto que un subconjunto de un contable conjunto es contable, esto va a demostrar el teorema.

Nota para los nerds: lo que queda es totalmente constructivo, por lo que puedo ver.

Hay muchos clásicos bijections de$\Bbb N\times \Bbb N$$\Bbb N$. Elige tu favorito y llamar a $p_2$. Para cada una de las $n\ge 2$, vamos a $p_{n+1}\colon \Bbb N^n\to n$ ser definido por $p_{n+1}(x_0,x_1,\dots,x_n)=p_2(x_0,p_n(x_1,\dots,x_n))$. La integridad, la deje $p_1$ ser la identidad de la función en $\Bbb N$. Por inducción, usted puede ver fácilmente que $p_n$ es un bijection de $\Bbb N^n$ $\Bbb N$por cada $n$.

Ahora que tenemos todos estos $p_n$s, vamos a ponerlos juntos. Para cada tupla $(x_0,\dots,x_{n-1})$, vamos a $q(x_0,\dots,x_{n-1})=p_2(n,p_n(x_0,\dots,x_{n-1}))$. Es decir, estamos usando $p_2$ a incluir la longitud de la tupla con el resultado de la aplicación de $p_n$ a que tupla. Pero, a continuación, $q$ es exactamente lo que estamos buscando: un bijection de$\Bbb N^{<\omega}$$\Bbb N$.