creciente secuencia de funciones modulo fijo error finito

Question

Aquí vamos a considerar sólo las funciones de $\mathbb N$ a sí mismo. Decir $f <_n g$ si $\{ i : f(i) \geq g(i) \}$ tiene de tamaño en la mayoría de las $n$.

Es posible tener un sistema fijo entero $k$, $<_k$-aumento (linealmente ordenado) secuencia $\{ f_n : n \in \mathbb N \}$ y una función de $g$ tal que $g >_k f_n$ para todos los $n$?

Answer 1

Por último, aquí es una prueba de que no hay tal cosa para cualquier $k$ (después de la primera sólo se muestra para $k=1$) si desea que el $f_n$ a es linealmente ordenado por $<_k$.

Asumir dichas $(f_n)_{n\in\mathbb N}$ e $g$ existen para algunos $k$. Para cualquier $n$ corregir algunos excepción conjunto $e_n\in[\mathbb N]^k$ que los testigos $f_n<_k g$, que es para todos los $m\in\mathbb N\setminus e_n$ tenemos $f_n(m)<g(m)$.

Reivindicación 1 no es $e\in[\mathbb N]^k$ con $e=e_n$ infinitly a menudo.

Prueba: Si hay, podemos asumir wlog que $e_n=\{0,\dots, k-1\}$ para todos los $n$. Pero, a continuación, $f_n(k)<g(k),\dots, f_n(2k+1)<g(2k+1)$ tiene para todos los $n$. Por lo tanto, hay $n_0<n_1$ con $f_{n_0}(k)=f_{n_1}(k),\dots, f_{n_0}(2k+1)=f_{n_1}(2k+1)$, contradiciendo $f_{n_0}<_k f_{n_1}$. $\square$

La reivindicación 2 no es $1\leq i\leq k$ e $e\in[\mathbb N]^{i}$ con $e\subseteq e_n$ infintely a menudo.

La prueba: Le esta prueba por inducción sobre $i$. El caso base $i=k$ ya está hecho. Supongamos que la afirmación de falla por $1\leq i<k$, pero se mantiene para $i+1$. Asumimos wlog que $\{0,\dots i-1\}\subseteq e_n$ para todos los $n$. Dado que la demanda tiene por $i+1$, hay algunos $N$ así que para todos los $n\geq N$ tenemos $f_n(k)<g(k),\dots, f_n(2k+1)<g(2k+1)$. Ahora podemos encontrar $N\leq n_0<n_1$ con $f_{n_0}\not<_kf_{n_1}$ como en el anterior, la contradicción. $\square$

Por la Reivindicación 2 por $i=1$, hay algunos $N$ así que para todos los $n\geq N$ tenemos $f_n(0)<g(0),\dots, f_n(k+1)<g(k+1)$. Pero una vez más esto nos permite encontrar el $N\leq n_0<n_1$ , de modo que $f_{n_0}\not<_kf_{n_1}$, contradicción.

Anteriormente he publicado una respuesta donde me asumido erróneamente que sólo desea $f_n<_1 f_{n+1}$ para todos los $n$. En ese caso, este hecho es posible. Aquí está mi respuesta original:

Para el propósito de esta respuesta no considero a $0$ como un número natural.

Lema Hay una secuencia $(f_n)_{n\in\mathbb N}$ y una función de $g$ , de modo que $f_n<_1 f_{n+1}$ e $f_n<_0 g$ para todos los $n$.

Prueba:

Deje $a=(a_n)_{n\in\mathbb N}$ ser una secuencia con las siguientes propiedades:

1. para cualquier $n\in\mathbb N$ hay $i_n\leq 2^n$ , de modo que $a_{i_n}=n$
2. si $a_m=n$ entonces $a_{m+2^n}=n$

No es difícil construir una secuencia. Cada impar entrada se $1$. Digamos que usted ha especificado los índices de donde $a_l$ es igual a $m$ para todos los $m<n$. A continuación, vamos a $i_n$ ser el menor entero $\leq 2^n$ que no es ninguno de estos índices (esta $i_n$ existe inductivamente). A continuación, vamos a $a_{i_n}=n$ y producir todos los otros índices a partir de la regla 2, yo.e $a_k=n$ fib $k=i_n\ mod\ 2^n$.

Ahora estamos a la construcción de una secuencia $(f_n)_{n\in\mathbb N}$ e una $g$ con la propiedad solicitada. Deje $f_0$ cero en todas partes. Si $f_n$ está construido, definir $f_{n+1}$ como sigue: Si $k\neq a_{n+1}$ a continuación, vamos a $f_{n+1}(k)=f_n(k)+1$. Deje $f_{n+1}(a_{n+1})=0$. Claramente $f_n<_1 f_{n+1}$ para todos los $n$. La secuencia de $a$ básicamente especifica a qué lugares tenemos la posibilidad de volver a cero. El uso de los bienes de $a$, podemos ver fácilmente que $f_n(k)<2^k$ cualquier $n$ y por lo tanto la función $g(k)=2^k$ domina cada $f_n$ todas partes. $\square$