There is a sequence of finite fields $F_q$ with appropriate polynomials $f_q$ such that
i) $qq_{1}< p$ q_{2}$implies$F_q$F_{q_{1}}$ has fewer elements thatn than $F_p$F_{q_{2}}$(Edited notation a bit here) ii) deg$(f_{q}) \leq n\in\mathbb{N}$(uniformly bounded) iii) the number of points missed by$f_q$is uniformly bounded above by$m\in\mathbb{N}$Under these assumptions, construct an infinite field as follows: Let F be the set of usual field axioms (expressed in first order logic). Let$\psi$be the first order statement "there are coefficients$a_{0}$through$a_{n}$and there are other points$y_{1}$through$y_{m}$such that for any$x$we have$a_{n} x^{n} + ... + a_{1}x + a_{0} \neq y_{k}$for any$k$and for all$w$which are not equal to$y_{1}$through$y_{m}$there is a$x$such that$a_{n}x^{n} + ... + a_{0} = w$" More colloquially,$\psi$says "the polynomial$f(x) = a_{n}x^{n} + ... + a_{0}$misses$y_1$through$y_m$but nothing else" (One can, e.g., set$a_{n} = 0$or$y_{1} = y_{2}$if for a given finite field, the degree is smaller or$f_q$misses fewer points) Let$\phi_k$be the first order statement "There are at least$k$elements" (i.e., there exist$x_{1}$through$x_{k}$such that they are pairwise nonequal). Finally, set$T = F \cup {\psi} \cup {\phi_{n}}$. A model of$T$is simply a set with interpretations for everything such that all the statements of$T$are satisfied. In other words, a model is a field (because is satisfies F) which is infinite (because it simultaneously satisfies all of the$\phi_n$) which has a polynomial like you want (because of$\psi$). Godel's completeness theorem says that$T$has a model iff$T$is consistent. The compactness theorem for first order logic says that$T$is consistent iff every finite subset of$T$is consistent. Hence, by applying Godel's completeness theorem again, we need only show that every finite subset of$T$has a model. Choosing a finite$T_{0}\subseteq T$, we may, without loss of generality, enlarge it by including$F$and$\psi$because a model of$T_{0}\cup F\cup \psi$will model$T_{0}$. Now, since$T_{0}$is finite, there is a largest$N$such that$\phi_{N}$is in$T_{0}$. Because of this, a model of$T_{0}$is simply a finite field of at cardinality at least$N$with a choice of function$f$satisfying what you want (with bound on deg(f) and the number of points missed in the image). But the existence of such a field was precisely the assumption made at the top of the post. Now, hopefully someone can shed some light as to whether or not the assumption is true. 1 You mentioned that for finite fields, such f exist. Under the following assumption, I believe there is an infinite field with the same such that an f exists. (My field theory is very weak, so I'm not sure how obviously correct or obviously incorrect these assumptions are): There is a sequence of finite fields$F_q$with appropriate polynomials$f_q$such that i)$q< p$implies$F_q$has fewer elements thatn$F_p$ii) deg$(f_{q}) \leq n\in\mathbb{N}$(uniformly bounded) iii) the number of points missed by$f_q$is uniformly bounded above by$m\in\mathbb{N}$Under these assumptions, construct an infinite field as follows: Let F be the set of usual field axioms (expressed in first order logic). Let$\psi$be the first order statement "there are coefficients$a_{0}$through$a_{n}$and there are other points$y_{1}$through$y_{m}$such that for any$x$we have$a_{n} x^{n} + ... + a_{1}x + a_{0} \neq y_{k}$for any$k$and for all$w$which are not equal to$y_{1}$through$y_{m}$there is a$x$such that$a_{n}x^{n} + ... + a_{0} = w$" More colloquially,$\psi$says "the polynomial$f(x) = a_{n}x^{n} + ... + a_{0}$misses$y_1$through$y_m$but nothing else" (One can, e.g., set$a_{n} = 0$or$y_{1} = y_{2}$if for a given finite field, the degree is smaller or$f_q$misses fewer points) Let$\phi_k$be the first order statement "There are at least$k$elements" (i.e., there exist$x_{1}$through$x_{k}$such that they are pairwise nonequal). Finally, set$T = F \cup {\psi} \cup {\phi_{n}}$. A model of$T$is simply a set with interpretations for everything such that all the statements of$T$are satisfied. In other words, a model is a field (because is satisfies F) which is infinite (because it simultaneously satisfies all of the$\phi_n$) which has a polynomial like you want (because of$\psi$). Godel's completeness theorem says that$T$has a model iff$T$is consistent. The compactness theorem for first order logic says that$T$is consistent iff every finite subset of$T$is consistent. Hence, by applying Godel's completeness theorem again, we need only show that every finite subset of$T$has a model. Choosing a finite$T_{0}\subseteq T$, we may, without loss of generality, enlarge it by including$F$and$\psi$because a model of$T_{0}\cup F\cup \psi$will model$T_{0}$. Now, since$T_{0}$is finite, there is a largest$N$such that$\phi_{N}$is in$T_{0}$. Because of this, a model of$T_{0}$is simply a finite field of at cardinality at least$N$with a choice of function$f\$ satisfying what you want (with bound on deg(f) and the number of points missed in the image). But the existence of such a field was precisely the assumption made at the top of the post.