Aumentar la biyección $f\colon \mathbb{N} \to \mathbb{Q}$

Question

Sabemos que existe un bijection $f\colon \mathbb{N} \to \mathbb{Q}$ desde el conjunto de los números naturales al conjunto de los números racionales. Hay un aumento de la bijection? Dado $m, n \in \mathbb{N}$ tales como que $m < n$,$f(m) < f(n)$.

He tratado de argumentar de la siguiente manera: para cada bijection $f$ o $f$ es el aumento o hay un menor número natural $M_f$ tales como que $f$ es el aumento natural de todos los números menos de $M_f$. Vamos a ordenar la bijections como sigue: $f' \leq f$ si $M_{f'} \leq M_f$ y si la restricción de $f$ a todos los números enteros de menos de $M_{f'}$ es igual a $f'$.

Ahora, dado un no-creciente bijection $f$, que se puede construir otro bijection $f'$$M_f < M_{f'}$, simplemente cambiando $f(M_f)$ otro $f(y)$ al $y > M_f$. También, dada una cadena de bijections $f_i$ o de la $M_{f_i}$'s son limitados o no están. Si son limitados, tome su máximo y construir un límite superior por el método anterior. Si no lo son, para cada $n \in \mathbb{N}$, $f_i(n)$ debe ser constante para suficientemente grande $i$. Definir $f'(n) = f_i(n)$, y tendremos $f' \geq f_i$ todos los $i$. Por el Lema de Zorn, debe existir una máxima bijection, que debe ser creciente. Es esto correcto?

EDIT: acabo de pensar, no hay ningún número puede ser $f(1)$, debido a que para cada número racional no es uno estrictamente menor. Pero ahora, ¿dónde está el error en el argumento anterior?

Answer 1

Creo que tu error está en creer que sólo porque usted puede construir una secuencia infinita de bijections que están aumentando más y más, no es un final, "límite" bijection, como si la secuencia es de alguna manera convergente. La secuencia no es convergente, y no hay límite. O, hay un límite, pero no es un bijection más. Cualquiera que sea la interpretación que le gusta.

Pensar en tratar de hacer un bijection con la propiedad de que $f(n) = n$ para todos los números naturales. Es fácil hacer una secuencia $f_N$ de bijections para que la propiedad se mantiene para todos los $n<N$. En la final, pero el límite está claro que no es un bijection más.

La mayoría de la "obra" de un bijection como esto se hace en el extremo de la cola de $\Bbb N$, y dejando la cola libre en cada término de la secuencia significa que usted tiene suficiente espacio para hacer en bijections. En el límite, el extremo de la cola no es libre, y por lo tanto tiene un tiempo más difícil de ser un bijection.

De hecho, es fácil dar otros ejemplos de secuencias de bijections que convergen a algo que no es un bijection. Por ejemplo, las funciones de $f_n:\Bbb R\to \Bbb R$ (o $\Bbb Q\to \Bbb Q$ si te gusta) dado por $f_n(x) = \frac xn$ convergen pointwise a $f(x) = 0$.

Answer 2

De hecho, hay una manera fácil de mostrar que no hay ninguna tal bijection: hay un racional $q$ entre $f(0)$$f(1)$! Pero no podemos $f(n)=q$ cualquier $n>1$, ya que el $f$ tiene que ir en aumento.

---

Muy bien, así que ahora vamos a mirar a su argumento.

Primero de todo, creo que te has misdefined $M_f$: creo que quiere que el mayor número tal que $f$ es creciente por debajo de $M_f$ (de lo contrario siempre vamos a tener $M_f=0$).

Pero el verdadero error es cuando se intenta aplicar el lema de Zorn. De hecho, su poset ¿ no , tienen la propiedad de que cada cadena tiene una cota superior! Específicamente, la función intenta definir como el límite superior de una arbitraria de la cadena, no puede ser un bijection (de hecho, usted puede configurarlo para que esta función es lo que el aumento de la inyección de $\mathbb{N}$ $\mathbb{Q}$que desea que sea).

Este es un error común: tiene un poset $P_1$ que desea aplicar Zorn, y se encuentra dentro de otro natural poset $P_2$. En este caso, $P_1$ es el poset ha definido, y $P_2$ es el poset de todas las inyecciones de$\mathbb{N}$$\mathbb{Q}$, ordenado en forma análoga ($g\le h$ si $M_h\ge M_g$$h(n)=g(n)$$n\le M_g$). El problema es que, mientras que cualquier cadena en $P_2$ tiene un límite superior en $P_2$, una cadena en la $P_1$ va a estar garantizada sólo a tiene una cota superior en $P_2$.

(Y sólo para aclarar, he aquí un explícito elemento maximal de a $P_2$: el mapa de identidad $f: n\mapsto n$. ¿Por qué es esta máxima? Bueno, para cualquier $g$$\ge f$, tendríamos que contar con que $g$ está de acuerdo con $f$ mientras $f$ es cada vez mayor. Más simbólicamente, el problema es que $M_f=\infty$. Pero $f$ es siempre creciente, por lo que tendríamos que tener $g=f$. En general, las máximas de los elementos de $P_2$ son exactamente el aumento de las inyecciones de$\mathbb{N}$$\mathbb{Q}$.)

Answer 3

No demostrar que su función $f'$ es una biyección, y en general no es. Será sólo por una inyección cada vez mayor. Por ejemplo, dada una cadena $f_1,f_2,\dots$ de bijections donde cada $f_k$ satisface $f_k(i)=i$ % todo $i\le k$, entonces el $f'(i)=i$ % todo $i$, $f'$ no es sobreyectiva.

$f_1 = 1,\frac12,\frac{47}{55},\dots$

$f_2 = 1,2,-\frac35\dots$

$f_3 = 1,2,3,\frac{99}{77}\dots$

$\vdots$

$f'=1,2,3,4,5,\dots$ no es un bijection.