1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Combinatorial Theory (f*h=g*h) g=f?

  1. Oct 12, 2011 #1
    1. The problem statement, all variables and given/known data

    If f :X -> X and g:X -> X are functions, and h:X -> X is a one-to-one function such that
    f * h = g * h need it be the case that f = g? Prove it or give a counterexample. What if, in addition, X is finite?

    3. The attempt at a solution

    I know that f does not equal g for an infinite set but is for a finite set. I know to prove that it isn't when it is infinite set it is the difference between the onto function. I am not sure how to relate that to the problem and build a proof out of it.

  2. jcsd
  3. Oct 12, 2011 #2
    Yes, g must equal f in your example, i do not have time to answer your question fully, but I would first say you have not correctly defined a one-to-one function appropriately. Look into defining similarity of classes of a one to one relation.
  4. Oct 12, 2011 #3


    User Avatar
    Science Advisor
    Homework Helper

    I think you've got the right idea. If X is finite and h is one-to-one, then h is also onto. So f=g. So if you want to construct a counterexample (and you DO), pick X to be an infinite set and h one-to-one but not onto. Try it.
  5. Oct 12, 2011 #4
    I am not sure where to go from here. I understand all the basics of onto and one to one functions but am struggling to apply them here.

    What I have:

    X is an infinite set, h is a one to one function, but not an onto function. Thus when using the function h, the two infinite X sets do not have matching ranges. Thus, there could be two different h values and so f does not have to equal g for infinite sets.

    When X is a finite set, and h is one to one, then it has to be onto, thus stating that through the function h, the number is equal to it's output and thus h=h and so f has to equal g.

    Is that right? I feel like I am missing something. Thanks again for all your help!
  6. Oct 13, 2011 #5


    User Avatar
    Science Advisor
    Homework Helper

    Try an example. Pick X=Z, the integers. Define h:Z->Z, by h(x)=2x. Is h one-to-one? Is it onto? Use that to make your counterexample.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook