Familia de funciones sin límites de$\mathbb{N}$ a$\mathbb{N}$

Question

Definiciones:

1. Para las funciones$f,g:\mathbb{N}\to \mathbb{N}$, decimos$f\leq ^{*} g$ si existe$n\in\mathbb{N}$ de manera tal que para$n\leq m$ tenemos$f(m)\leq g(m)$

2. La familia$F$ de funciones desde$\mathbb{N}$ a$\mathbb{N}$ no tiene límites si para cada función$g:\mathbb{N}\to \mathbb{N}$, existe$f\in F$, por lo que$f\leq ^{*} g$ no se mantiene.

Pregunta:

Demuestre que una familia sin límites$F$ de funciones de$\mathbb{N}$ a$\mathbb{N}$ es incontable.

¡Gracias por cualquier ayuda!

Answer 1

En lugar de mostrar que cada ilimitado de la familia es incontable, vamos a probar la (equivalente) contraposición: Mostrar que cada contables de la familia no puede ser ilimitado. Deje $F$ ser una contables de la familia de funciones de $\mathbb N\to \mathbb N$. Es decir, existe un bijection $\mathbb N\to F$, o en pocas palabras, podemos enumerar los elementos de $F$ como este: $$\tag1F=\{f_n\mid n\in\mathbb N\}.$$ Esta $F$ sería infinito si para cada $g\colon\mathbb N\to \mathbb N$ existe un $f\in F$ tal que $f\le^* g$ es falso. Por lo tanto tenemos que demostrar que existe $g\colon\mathbb N\to \mathbb N$ tal que para todos los $f\in F$ la declaración de $f\le^* g$ es cierto.

Simplemente definir $$\tag2g(n)=\max\{f_k(n)\mid k\le n\}.$$ Ahora vamos a $f$ ser un elemento arbitrario de $F$. Tenemos que mostrar $f\le^* g$. Por $(1)$, tenemos $f=f_n$ para algunos $n$. A continuación, el uso de $(2)$ $$\tag3g(m)=\max\{f_k(m)\mid k\le m\}\ge f(m)\quad \text{for }m\ge n$$ debido a $f$ se produce entre el $f_k$ con $k\le m$. Pero $(3)$ es sólo la definición de $f\le^* g$. $_\square$