Problemas sobre Countability relacionados con la función espacios

Question

Supongamos que tenemos los siguientes conjuntos, y determinar si son countably infinito o incontable .

1. El conjunto de todas las funciones de$\mathbb{N}$$\mathbb{N}$.

2. El conjunto de todas las funciones crecientes de $\mathbb{N}$ a $\mathbb{N}$.

3. El conjunto de todos los no-la disminución de las funciones de $\mathbb{N}$ a $\mathbb{N}$.

4. El conjunto de todas las funciones inyectiva de a $\mathbb{N}$ a $\mathbb{N}$.

5. El conjunto de todos los surjective funciones de de $\mathbb{N}$ a $\mathbb{N}$.

6. El conjunto de todos los bijection funciones de de $\mathbb{N}$ a $\mathbb{N}$.

---

Mis pensamientos sobre esto:

1. El primer conjunto es incontable mediante diagonalización argumento.

2. He leído algo acerca de él que dicen que esto es contable, ya que podemos ver esto como un conjunto de secuencias finitas de números naturales. Pero tengo dificultades para seguir el argumento.

3. El artículo que leí dice que esto es incontable, pero yo no podía seguir el argumento.

4. Para (4),(5) y (6), ni siquiera estoy seguro de cómo abordar los problemas como estos.

Podría alguien por favor explique cómo abordar este tipo de problemas en general?

Y qué importa cuando me cambio todas las $\mathbb{N}$$\mathbb{R}$?

Answer 1

Otro enfoque para la 6ª parte.

Deje que nos denota el conjunto de todos los bijections de$\mathbb N$$\mathbb N$$\operatorname{Bij}(\mathbb N,\mathbb N)$.

Claramente $$|\operatorname{Bij}(\mathbb N,\mathbb N)| \le \aleph_0^{\aleph_0} = 2^{\aleph_0} = \mathfrak c.$$

Vamos a tratar de demostrar lo contrario la desigualdad.

Para la función arbitraria $f\in\operatorname{Bij}(\mathbb N,\mathbb N)$ definimos $$\operatorname{Fix}(f)=\{n\in\mathbb N; f(n)=n\}.$$ (That is, $\operatorname{Fix}(f)$ is the set of all fixed points of the map $f$.) Tratemos de responder a la pregunta, si por cualquier $A\subseteq\mathbb N$ es posible encontrar un bijection ${f_A}:{\mathbb N}\to {\mathbb N}$ tales $\operatorname{Fix}(f_A)=A$. Vamos a considerar dos casos.

Si el complemento del conjunto a $A$ es infinito, es decir, $\mathbb N\setminus A=\{b_n; n\in\mathbb N\}$ (y podemos suponer que los elementos de la $\mathbb N\setminus A$ están escritos en el orden creciente, es decir,$b_1<b_2<\dots<b_n<b_{n+1}<\dots$ ), entonces podemos definir una función de $f_A$ como sigue: $$f_A(x)= \begin{cases} x, & \text{if }x\in A, \\ b_{2k+1}, &\text{ak %#%#% for some %#%#%},\\ b_{2k}, &\text{ak %#%#% for some %#%#%}. \end{casos} $$ En otras palabras, no se mueven los elementos de $x=b_{2k}$ y los elementos del complemento se emparejaron y hemos intercambiado es par. Dicho mapa es un bijection de $k\in\mathbb N$ $x=b_{2k+1}$tal que $k\in\mathbb N$.

Luego consideraremos el caso de que $A$ es finito.

Si $\mathbb N$, $\mathbb N$ es una función de cumplimiento $\operatorname{Fix}(f_A)=A$.

Si el conjunto de $\mathbb N\setminus A$ es un singleton $\mathbb N\setminus A=\emptyset$, entonces es que es imposible encontrar un bijection $f=id_{\mathbb N}$ tal que $\operatorname{Fix}(f_A)=\mathbb N=A$. Ningún elemento de $\mathbb N\setminus A$ pueden ser mapeados en $\{a\}$ (ya que todos estos elementos son fijos). Pero $f$ no puede ser asignada en $\operatorname{Fix}(f)=A=\mathbb N\setminus\{a\}$ ya que esto significaría que $\mathbb N\setminus A$ es un punto fijo.

Pero si el conjunto de $a$ tiene al menos dos elementos, entonces es posible construir un mapa. De nuevo hemos de asumir que los elementos $a$ están escritos en el orden creciente, es decir,$a$$a$. Ponemos a $\mathbb N\setminus A$ $b_k$, $\mathbb N\setminus A=\{b_0,\dots, b_n\}$ para$b_0<b_1<\dots<b_n$$f_A(x)=x$. (I. e. hemos hecho un ciclo que consta de elementos de $x\in A$.)

Esto define un bijection $f_A(b_k)=b_{k+1}$ tal que $0\le k<n$.

La asignación de $f_A(b_n)=b_0$ que hemos descrito anteriormente, es un mapa del conjunto de $\mathbb N\setminus A$ que consta de todos los subconjuntos de a ${f_A}:{\mathbb N}\to{\mathbb N}$, cuyo complemento no es un singleton, para el conjunto de $\operatorname{Fix}(f_A)=A$. Este mapa es inyectiva; ya que de $A\mapsto f_A$ obtenemos $\mathcal P({\mathbb N})\setminus\{\mathbb N\setminus\{a\}\in\mathbb N\}$.

Desde el set $\mathbb N$ con la cardinalidad $\operatorname{Bij}(\mathbb N,\mathbb N)$ hemos omitido una contables set $f_A=f_B$. Por lo tanto la cardinalidad de esta diferencia $A=\operatorname{Fix}(f_A)=\operatorname{Fix}(f_B)=B$ es de nuevo $\mathcal P({\mathbb N})$.

Así nos encontramos con una inyección de un conjunto de cardinalidad $\mathfrak c$ para el conjunto de $\{\mathbb N\setminus\{a\}\in\mathbb N\}$. Esto produce que el opuesto de la desigualdad $\mathcal P({\mathbb N})\setminus\{\mathbb N\setminus\{a\}\in\mathbb N\}$$ y por Cantor-Bernstein teorema obtenemos $\mathfrak c$.

Answer 2

Voy a aprovechar esta oportunidad para mencionar aquí un muy bonito (al menos en mi opinión) la prueba de que la cardinalidad de todos los bijections $\mathbb N\to\mathbb N$$\mathfrak c=2^{\aleph_0}$, que es básicamente la parte 6. Yo lo que es un wiki de la comunidad, ya que la idea no es mía. Creo que he visto este en el sci. las matemáticas, pero no estoy seguro acerca de esto y no puedo encontrar el enlace ahora. (Siéntase libre de añadir algunos consejos y enlaces, si usted sabe algunos.)

SUGERENCIA: Si alguien quiere probar a desarrollar la idea por sí mismo, la idea básica es la de Riemann, de reordenación del teorema.

---

Deje que nos denota el conjunto de todos los bijections de$\mathbb N$$\mathbb N$$\operatorname{Bij}(\mathbb N,\mathbb N)$.

Claramente $$|\operatorname{Bij}(\mathbb N,\mathbb N)| \le \aleph_0^{\aleph_0} = 2^{\aleph_0} = \mathfrak c.$$

Ahora vamos a demostrar lo contrario la desigualdad. Escojamos una serie de $\sum_{n=0}^\infty x_n$, la cual es convergente pero no absolutamente convergente (por ejemplo,$\sum_{n=0}^\infty x_n = \sum_{n=0}^\infty (-1)^n\frac1{n+1}$). Por Riemann del teorema, para cualquier número real $r$ existe una permutación $\pi\in \operatorname{Bij}(\mathbb N,\mathbb N)$ tal que $\sum_{n=0}^\infty x_{\pi(n)}=r$. Si elegimos para cada una de las $r$ uno de esos permutación, se obtiene una inyectiva mapa de$\mathbb R$$\operatorname{Bij}(\mathbb N,\mathbb N)$. Así $|\operatorname{Bij}(\mathbb N,\mathbb N)| \ge |\mathbb R| = \mathfrak c = 2^{\aleph_0}$.

Answer 3

Vamos $$ \eqalign{ A_1&=\text{el conjunto de todas las funciones de }\Bbb N\text{ a }\Bbb N. \cr A_2&=\text{el conjunto de todos los no-aumento de }\Bbb N\text{ a }\Bbb N. \cr A_3&=\text{el conjunto de todos los no-decreciente }\Bbb N\text{ a }\Bbb N. \cr A_4&=\text{el conjunto de todos 1-1 funciones de}\Bbb N\text{ a }\Bbb N. \cr A_5&=\text{el conjunto de todos en funciones de }\Bbb N\text{ a }\Bbb N. \cr A_6&=\text{el conjunto de todos los bijections de }\Bbb N\text{ a }\Bbb N. \cr } $$

Considere la posibilidad de $A_6$:

$A_6$ puede considerarse como el conjunto de $\bigl\{\,\pi :\pi \text{ is a permutation of } (1,2,3,\ldots)\,\bigr\}$.

Para cualquier permutación $\pi$, podemos asociada a una secuencia binaria $(x_n)$ mediante el establecimiento de $$x_n=\cases{ 0,& \text{if } \pi_n=n\cr 1,& \text{otherwise} }.$$ Esto induce una en el mapa de $A_6$ para el conjunto de las infinitas secuencias binarias (Edit: no del todo, como Martin Sleziak señala en su respuesta, las secuencias binarias que tienen "sólo " 1", no tienen ningún elemento en $A_6$ asignado a ellos. Pero, como el conjunto de procesos contables, el resto del argumento se va a ir a través de. Martin también describe muy bien cómo obtener este mapa.). Desde el último conjunto es incontable, por lo que es el antiguo.

Por eso, $A_6$ es incontable.

De esto se sigue que $A_5$, $A_4$, y $A_1$ son innumerables.

Ahora, considere la posibilidad de $A_2$:

Si $f$ no es una función creciente, a continuación, $f$ debe ser eventualmente constante. Por lo tanto, la cardinalidad $A_2$ sería en la mayoría de la cardinalidad del conjunto $$ \bigcup_{j,m} \bigl\{\,(a_i)_{i=1}^\infty : a_i=m, i\ge j\,\bigr \}. $$ Pero esto último es una contables de la unión de conjuntos contables y, por lo tanto, contables.

Por eso, $A_2$ es contable.

Ahora, considere la posibilidad de $A_3$:

La cardinalidad del conjunto de la no disminución de las funciones es, al menos, la cardinalidad del conjunto $$ \{\, Un\subconjunto\Bbb N : \text{ es un subconjunto infinito de } \Bbb N\, \}. $$

Desde este último conjunto incontable, $A_3$ es incontable.

Answer 4

Esto no es una respuesta completa. [Estoy tomando $\mathbb N$ para incluir a $0$.] Voy a darte una prueba de que hay una cantidad no numerable de bijections de $\mathbb N$ a sí mismo. Esto, obviamente, subsume las preguntas (4)-(6).

Considerar las funciones de $f : \mathbb N \to \mathbb N$ de la siguiente forma especial: Por cada $k$, el par de elementos de a $\{ 2k, 2k+1 \}$ se asigna a sí mismo. Sin embargo, tenemos dos maneras de hacer esto:

• o bien: mapa de $2k$ a sí mismo, y de manera similar para $2k+1$.

• o: mapa de $2k$ $2k+1$ a cada uno de los otros.

El punto clave es que para cada una de las $k$, se puede elegir una de las dos posibilidades de forma independiente. Desde allí se $2$ opciones para cada una de las $k$, usted tiene $2^{\mathbb N}$ opciones; es decir, hay una cantidad no numerable de tales funciones, para satisfacer esta restricción. Y cada función es un bijection de $\mathbb N$ a sí mismo.

El de arriba necesita un poco de trabajo para hacer totalmente riguroso. En particular, tratar de formalizar lo que quiero decir por "$2^\mathbb N$ de posibilidades".

---

Para (3), la idea es similar. Para cada una de las $k$, trate de asignar $k$ a $2k$ o $2k+1$. Los detalles se dejan como ejercicio.

---

Para (2), hace la siguiente sugerencia de ayuda? Todos los no-aumento de la función $f : \mathbb N \to \mathbb N$ finalmente es constante. Así que la función es únicamente especifica si describimos lo finito inicial "porción" de la función.

Otro enfoque (debido a la tuberculosis) para (2): Si traza la gráfica de una no-aumenta la función, se parece a una escalera que desciende a medida que nos movemos de izquierda a derecha-de una escalera con un número finito de pasos, ya que la función puede bajar sólo un número finito de veces. También se puede reconstruir la función si queremos grabar la parte superior derecha de las esquinas de cada uno de esos pasos. Desde la última corresponde a un subconjunto finito de $\mathbb N \times \mathbb N$ (contables), se sigue que nuestro conjunto de no aumentar las funciones contables como bien.