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