Combinatorial Theory (f*h=g*h) g=f?

1. bloynoys

25
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.

Thanks!

2. CLSabey

7
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.

3. Dick

25,738
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.

4. bloynoys

25
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!

5. Dick

25,738
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.