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


by bloynoys
Tags: combinatorial, fhgh, theory
bloynoys
bloynoys is offline
#1
Oct12-11, 08:32 PM
P: 24
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!
Phys.Org News Partner Science news on Phys.org
Review: With Galaxy S5, Samsung proves less can be more
Making graphene in your kitchen
Study casts doubt on climate benefit of biofuels from corn residue
CLSabey
CLSabey is offline
#2
Oct12-11, 08:55 PM
P: 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.
Dick
Dick is offline
#3
Oct12-11, 09:29 PM
Sci Advisor
HW Helper
Thanks
P: 25,171
Quote Quote by bloynoys View Post
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!
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.

bloynoys
bloynoys is offline
#4
Oct12-11, 11:29 PM
P: 24

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


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!
Dick
Dick is offline
#5
Oct13-11, 09:48 AM
Sci Advisor
HW Helper
Thanks
P: 25,171
Quote Quote by bloynoys View Post
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!
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.


Register to reply

Related Discussions
A few basic questions about combinatorial game theory General Math 2
A town has 6 parks. One day, 6 friends, who are unaware of each Set Theory, Logic, Probability, Statistics 5
Plz help with this combinatorial identity Precalculus Mathematics Homework 2
Combinatorial group and representation theory? Linear & Abstract Algebra 3
Textbooks in combinatorial theory Set Theory, Logic, Probability, Statistics 0