increasing sequence of functions modulo fixed finite error Here we consider only functions from $\mathbb N$ to itself.  Say $f <_n g$ if $\{ i : f(i) \geq g(i) \}$ has size at most $n$.
Is it possible to have a fixed integer $k$, a $<_k$-increasing (linearly ordered) sequence $\{ f_n : n \in \mathbb N \}$ and a function $g$ such that $g >_k f_n$ for all $n$?
 A: Finally, here is a proof that there is no such thing for any $k$ (after first only showing it for $k=1$) if you want the $f_n$ to be linearly ordered by $<_k$.
Assume such $(f_n)_{n\in\mathbb N}$ and $g$ exist for some $k$. For any $n$ fix some exception set $e_n\in[\mathbb N]^k$ that witnesses $f_n<_k g$, that is for all $m\in\mathbb N\setminus e_n$ we have $f_n(m)<g(m)$.

Claim 1 There is no $e\in[\mathbb N]^k$ with $e=e_n$ infinitly often.

Proof: If there is, we can assume wlog that $e_n=\{0,\dots, k-1\}$ for all $n$. But then $f_n(k)<g(k),\dots, f_n(2k+1)<g(2k+1)$ holds for all $n$. Thus there are $n_0<n_1$ with $f_{n_0}(k)=f_{n_1}(k),\dots, f_{n_0}(2k+1)=f_{n_1}(2k+1)$,  contradicting $f_{n_0}<_k f_{n_1}$. $\square$

Claim 2 There is no $1\leq i\leq k$ and $e\in[\mathbb N]^{i}$ with $e\subseteq e_n$ infintely often.

Proof: We proof this by induction on $i$. The base case $i=k$ is already done. Lets assume that the claim fails for $1\leq i<k$, but holds for $i+1$. We assume wlog that $\{0,\dots i-1\}\subseteq e_n$ for all $n$. Since the claim holds for $i+1$, there is some $N$ so that for all $n\geq N$ we have $f_n(k)<g(k),\dots, f_n(2k+1)<g(2k+1)$. We can now find $N\leq n_0<n_1$ with $f_{n_0}\not<_kf_{n_1}$ as above, contradiction. $\square$
By Claim 2 for $i=1$, there is some $N$ so that for all $n\geq N$ we have $f_n(0)<g(0),\dots, f_n(k+1)<g(k+1)$. But once again this allows us to find $N\leq n_0<n_1$ so that $f_{n_0}\not<_kf_{n_1}$, contradiction.
Earlier I posted an answer where I wrongly assumed you only want $f_n<_1 f_{n+1}$ for all $n$. In that case, this is indeed possible. Here is my original answer:
For the purpose of this answer I do not consider $0$ as a natural number.

Lemma There is a sequence $(f_n)_{n\in\mathbb N}$ and a function $g$ so that $f_n<_1 f_{n+1}$ and $f_n<_0 g$ for all $n$.

Proof:
Let $a=(a_n)_{n\in\mathbb N}$ be a sequence with the following properties:


*

*for any $n\in\mathbb N$ there is $i_n\leq 2^n$ so that $a_{i_n}=n$

*if $a_m=n$ then then $a_{m+2^n}=n$
It is not hard to construct such a sequence. Let every odd entry be $1$. Say you have specified the indices where $a_l$ equals $m$ for all $m<n$. Then let $i_n$ be the least integer $\leq 2^n$ which is not any of these indices (this $i_n$ exists inductively). Then let $a_{i_n}=n$ and produce all other such indices using rule 2, i.e $a_k=n$ iff $k=i_n\ mod\ 2^n$.
Now we are up to constructing a sequence $(f_n)_{n\in\mathbb N}$ and a $g$ with the requested property. 
Let $f_0$ be zero everywhere. If $f_n$ is constructed, define $f_{n+1}$ as follows: If $k\neq a_{n+1}$ then let $f_{n+1}(k)=f_n(k)+1$. Let $f_{n+1}(a_{n+1})=0$. Clearly $f_n<_1 f_{n+1}$ for all $n$. The sequence $a$ basically specifies at which places we drop back to zero. Using the porperties of $a$, we can see easily that $f_n(k)<2^k$ for any $n$ and thus the function $g(k)=2^k$ dominates every $f_n$ everywhere. $\square$
