Results 1 to 5 of 5
Like Tree2Thanks
  • 1 Post By MacstersUndead
  • 1 Post By zhandele

Thread: g eventually dominates f ?

  1. #1
    Member
    Joined
    Nov 2012
    From
    Normal, IL USA
    Posts
    194
    Thanks
    29

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Jan 2009
    Posts
    415
    Thanks
    79

    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.)
    Last edited by MacstersUndead; Apr 26th 2019 at 06:39 AM.
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2012
    From
    Normal, IL USA
    Posts
    194
    Thanks
    29

    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
    go, no "eventual" about it.

    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?
    Thanks from MacstersUndead
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Jan 2009
    Posts
    415
    Thanks
    79

    Re: g eventually dominates f ?

    Your friend's answer seems good for natural numbers.

    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Nov 2012
    From
    Normal, IL USA
    Posts
    194
    Thanks
    29

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. astrobiologists do eventually
    Posted in the Statistics Forum
    Replies: 0
    Last Post: Jan 9th 2016, 11:48 AM
  2. Eventually self-outgrowing = eventually monotonic?
    Posted in the Advanced Math Topics Forum
    Replies: 4
    Last Post: May 31st 2012, 04:58 PM
  3. Eventually bounded rational functions
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: Apr 11th 2010, 11:26 AM
  4. Not eventually constant!
    Posted in the Math Challenge Problems Forum
    Replies: 3
    Last Post: Oct 24th 2009, 07:08 AM
  5. sequences of eventually monotone functions
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: Sep 28th 2009, 09:59 PM

/mathhelpforum @mathhelpforum