# Thread: g eventually dominates f ?

1. ## g eventually dominates f ?

I found this exercise in a publication from leanprover. The publication was about equinumerosity (two sets might be called equinumerous if they have the same cardinality). I hope someone can point me in the right direction.

Exercise

If f and g are functions from N to N, we say "g eventually dominates f" if there is some n such that, for every $\displaystyle m \ge n$, we have $\displaystyle g\left( m \right) > f\left( m \right)$. Informally we say "from some point on, g is always greater than f."

Let $\displaystyle {f_0},\,{f_1},\,{f_2},\, \ldots$ be a sequence of functions from N to N indexed by the natural numbers. Show that there exists a function g that eventually dominates each f.

My thoughts

If I'm allowed to use a different function g for each f, then this seems very simple. I could write $\displaystyle {g_i}\left( n \right) = {f_i}(n) + i - n + 2$. I put in the 2 so that there would always be some values for which g does not dominate f, even when i is small.

Is that what I'm supposed to do? I'm not sure where this exercise is supposed to lead me.

I suspect they want a single function $\displaystyle {g}$ that will dominate every $\displaystyle {f_i}$. How do I do that? I'm familiar with the Cantor Pairing Function. I'm sure that a bijection exists between $\displaystyle \left\langle {i,j} \right\rangle \in N \times N$ and $\displaystyle {f_i}(n)$. But then the sequence isn't right. The n that would get me to $\displaystyle {f_i}(n)$ isn't the same n as you see in the $\displaystyle {f_i}$ function. If I increment n, I'll wind up with something like $\displaystyle {f_{i+1}}(n-1)$, moving up a diagonal.

Any ideas?

2. ## Re: g eventually dominates f ?

The first observation would be that a function g diverging to positive infinity will always dominate functions f that have some upper bound M, so you just need to consider other functions f that diverge to positive infinity also as n goes to infinity.
The second observation would be that the function g doesn't necessarily need to dominate each $\displaystyle f_i$ at the same n such that g dominates f.

I have two ideas to prove.

The first idea is to prove by construction, and define your function g inductively such that g eventually dominates each $\displaystyle f_i$.
First, take out all functions with upper bound M.
Second, compare the first two functions of the remaining set and check if they intersect or don't intersect. If they don't intersect, one function always dominates the other. If there are finite intersections, one function dominates the other at the last point of intersection. If there are infinite intersections (ex. n sin(n) and (n+1) sin(n+1), I'm stuck on generally constructing a function p(x) that would dominate both functions being compared. Perhaps with a derivative-like approach, so that the rate of p(x) is eventually faster.
After comparing, let g be the function that eventually dominated the other function, and compare it with the next function of the sequence and repeat.

The second idea would be to prove by contradiction. ie. Suppose that there exists some $\displaystyle f_j$ in the set that cannot be eventually dominated, and show this leads to a contradiction. ie. Suppose for all n, there exists $\displaystyle f_j$ such that $\displaystyle f_j(n) > g(n)$ for all functions g from N to N. This might be hard to prove, but intuition leads me to believe the contradiction rests on that such $\displaystyle f_j$ must immediately diverge to positive infinity. (ie. vertical asymptote everywhere.)

3. ## Re: g eventually dominates f ?

I'm surprised this question has drawn so little interest.

You should know that the leanprover page from which I got this problem isn't a difficult read. It mentions Cantor-Schroeder-Bernstein, but omits to prove it because "the proof is tricky." Some of the other exercises include "Show that equinumerosity is an equivalence relation" and "Show that the Cantor Pairing Function is a bijection." Surely this question can't be as hard as all that. Here's a link to that in case anyone wants to look at it:

https://leanprover.github.io/logic_a..._infinite.html

A friend of mine did suggest a possible answer. I think it meets the terms of the problem, but I doubt it's the answer that the leanprover author (not named) had in mind. Here it is:

$\displaystyle g\left( n \right) = \sum\limits_{i = 1}^n {{f_i}\left( n \right) + 1}$
And here are a few examples:

$\displaystyle \begin{array}{l} g\left( 1 \right) = {f_1}\left( 1 \right) + 1\\ g\left( 2 \right) = {f_1}\left( 2 \right) + {f_2}\left( 2 \right) + 1\\ g\left( 3 \right) = {f_1}\left( 3 \right) + {f_2}\left( 3 \right) + {f_3}\left( 3 \right) + 1\\ g\left( 4 \right) = {f_1}\left( 4 \right) + {f_2}\left( 4 \right) + {f_3}\left( 4 \right) + {f_4}\left( 4 \right) + 1 \end{array}$

There are two things about this that I don't like. The first is that it doesn't generalize, even to negative integers. The second is that it seems to dominate every $\displaystyle {f_i}$ right from the get

I'm still hoping for more ideas.

BTW ... I know what you mean about "vertical asymptotes everywhere," but do we use the term asymptotes with discrete functions?

4. ## Re: g eventually dominates f ?

For integers, only need to modify the construction slightly, to avoid adding negative values, when g(n) should be monotonic increasing.
ex.
$\displaystyle g(n) = max(f_i(n)) + 1$
or
$\displaystyle g\left( n \right) = \sum\limits_{i = 1}^n {\mid{f_i}\left( n \right)\mid + 1}$

Your friend's construction doesn't necessarily dominate each $\displaystyle f_i$ immediately. Consider two functions $\displaystyle f_1(n)=1$ and $\displaystyle f_2(n)=3$
In this case,
$\displaystyle \begin{array}{l} g\left( 1 \right) = {f_1}\left( 1 \right) + 1 = 2\\ g\left( 2 \right) = {f_1}\left( 2 \right) + {f_2}\left( 2 \right) + 1 = 5\end{array}$

g(n) eventually dominates $\displaystyle f_1$ at $\displaystyle i=1$
g(n) eventually dominates $\displaystyle f_2$ at $\displaystyle i=2$

I was speaking off the cuff talking about vertical asymptotes, but they make sense to me irrespective of the domain. In retrospect, I should have said something along the lines of: "Such a function that couldn't be eventually dominated would have to have a rate of increase greater than all other rates of increases, which is a contradiction involving infinity."

In retrospect, I think I overthought this because I was thinking how to generalize in terms of real numbers, but real numbers are uncountable, unlike natural numbers, so a construction like your friend's wouldn't be feasible in real numbers, but I do think it's sufficient for this question.

5. ## Re: g eventually dominates f ?

Thanks for pointing those things out. My reservations were unfounded.

One consequence of this little theorem is that the set of functions from $\displaystyle N \to N \times N$ is uncountable, which is highly intuitive in any case. Could that be the point of the exercise? But if I were asked to prove that, I wouldn't do it that way. I'd use
$\displaystyle g\left( n \right) = {f_n}\left( n \right) + 1$ which might not dominate any $\displaystyle {f_i}$ but would not appear on any list of functions.