Elementos mínimos con respecto a Oh grandes

Question

Deje $\mathcal{F}$ ser un conjunto finito de funciones de los números naturales a los números naturales. Consideremos el conjunto a $S_{\mathcal{F}}=\{g:\mathbb{N}\to\mathbb{N}\mid f\in O(g)\text{ for every } f\in\mathcal{F}\} $. Quiero decidir si $S$ tiene un mínimo elemento con respecto a las grandes Oh, es decir, puedo demostrar (o refutar) que existe una $g\in S$ tal que para cada a$h\in S$,$g\in O(h)$? Yo creo que si me acaba de elegir a $g$ a ser la suma de todas las funciones en $\mathcal{F}$, entonces esto hace el truco.

Ahora bien, el resultado también si $\mathcal{F}$ se reemplaza con cualquier contables conjunto de funciones? Me siento como este resultado debe ser cierto, y que yo debería ser capaz de aplicar algún tipo de principio de orden o el lema de Zorn tipo de argumento para resolver esto, pero no estoy muy seguro de cómo proceder. Cualquier ayuda es muy apreciada.

Answer 1

Considere la posibilidad de $\mathcal{F} = \{n \mapsto n^\alpha \,\mid\, 0<\alpha < 1\}$.

Suponga que su conclusión se mantiene, es decir, $g \in S = S_{\mathcal{F}}$ tal que para cada a$h \in S$,$g \in O(h)$.

Considere la posibilidad de $h_n := g_n / \ln n$ (aquí, hago caso omiso al requerimiento de $h_n \in \Bbb{N}$, esto puede ser solucionado por redondeo, omito los detalles).

Deje $\alpha \in (0,1)$ ser arbitraria. Elija $\beta \in (\alpha,1)$. A continuación,$n^\beta \in O(g)$, es decir, $n^\beta / g_n \leq C$ todos los $n$. Pero esto implica $$ n^\alpha / h_n = n^\alpha \cdot \ln (n) / g_n \leq C' \cdot n^\beta / g_n \leq C \cdot C', $$ desde el logaritmo crece más lento que cualquier potencia positiva de $n$.

Por lo que acabo de mostrar, $h \in S$. Por elección de $g$, esto implica $h \cdot \ln n = g \in O(h)$, lo cual es obviamente falso.

Por lo tanto, la reivindicación de la falla, en general, para conjuntos infinitos $\mathcal{F}$. Tenga en cuenta que incluso, podemos optar $\mathcal{F}$ a ser contables teniendo en cuenta solamente a $\alpha \in (0,1) \cap \Bbb{Q}$.