Let $\mathcal{F}$ be a finite set of functions from the natural numbers to the natural numbers. Consider the set $S_{\mathcal{F}}=\{g:\mathbb{N}\to\mathbb{N}\mid f\in O(g)\text{ for every } f\in\mathcal{F}\} $. I want to decide whether $S$ has a minimal element with respect to big Oh, i.e. can I show (or disprove) that there exists a $g\in S$ such that for every other $h\in S$, we have $g\in O(h)$? I think if I just choose $g$ to be the sum of all the functions in $\mathcal{F}$ then this does the trick.
Now, does the result also hold if $\mathcal{F}$ is replaced with any countable set of functions? I feel like this result should be true and that I should be able to apply some sort of well ordering principle or Zorn's lemma type argument to solve this, but I'm not really sure how to proceed. Any help is appreciated!
Consider $\mathcal{F} = \{n \mapsto n^\alpha \,\mid\, 0<\alpha < 1\}$.
Assume that your conclusion holds, i.e. there is $g \in S = S_{\mathcal{F}}$ such that for every $h \in S$, we have $g \in O(h)$.
Consider $h_n := g_n / \ln n$ (here, I ignore the requirement $h_n \in \Bbb{N}$, this can be fixed by rounding, I omit the details).
Let $\alpha \in (0,1)$ be arbitrary. Choose $\beta \in (\alpha,1)$. Then $n^\beta \in O(g)$, i.e. $n^\beta / g_n \leq C$ for all $n$. But this implies $$ n^\alpha / h_n = n^\alpha \cdot \ln (n) / g_n \leq C' \cdot n^\beta / g_n \leq C \cdot C', $$ since the logarithm grows slower than any positive power of $n$.
By what we just showed, $h \in S$. By choice of $g$, this implies $h \cdot \ln n = g \in O(h)$, which is obviously false.
Hence, the claim fails in general for infinite sets $\mathcal{F}$. Note that we can even choose $\mathcal{F}$ to be countable by considering only $\alpha \in (0,1) \cap \Bbb{Q}$.