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

  • Thread starter bloynoys
  • Start date
  • Tags
    Theory
In summary, the conversation discusses whether or not two functions, f and g, must be equal if their composition with a one-to-one function, h, is equal. It is proven that for finite sets, f and g must be equal, but for infinite sets, there exists a counterexample where they are not equal. The example uses the function h(x)=2x on the set of integers to show that h is one-to-one but not onto, resulting in f and g not being equal.
  • #1
bloynoys
25
0

Homework Statement



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?



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!
 
Physics news on Phys.org
  • #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.
 
  • #3
bloynoys said:

Homework Statement



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?

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.
 
  • #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!
 
  • #5
bloynoys said:
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.
 

1. What is combinatorial theory?

Combinatorial theory is a branch of mathematics that deals with the study of finite or discrete structures. It involves counting, arranging, and selecting elements from a finite set, and has applications in various fields such as computer science, statistics, and physics.

2. What does the equation (f*h=g*h) g=f mean in combinatorial theory?

This equation is known as the cancellation law and it states that if two functions, f and g, have the same composition with a third function h, then f and g must be equal. This is a fundamental concept in combinatorial theory and is used to prove various theorems and identities.

3. How is combinatorial theory used in computer science?

Combinatorial theory has many applications in computer science, particularly in the fields of algorithms, coding theory, and graph theory. It is used to analyze the complexity and efficiency of algorithms, design error-correcting codes, and study the properties of graphs and networks.

4. What are some real-world examples of combinatorial problems?

Combinatorial problems can be found in various real-world scenarios, such as arranging objects on a shelf, scheduling tasks, and optimizing resources. For example, a company may need to schedule employees for different shifts while minimizing conflicts and maximizing productivity, which can be modeled as a combinatorial problem.

5. How can combinatorial theory help in decision-making and problem-solving?

Combinatorial theory provides a systematic and mathematical approach to solving problems and making decisions. It allows for the analysis and optimization of different scenarios, taking into account various constraints and objectives. This can be useful in many fields, including business, engineering, and social sciences.

Similar threads

  • Calculus and Beyond Homework Help
Replies
8
Views
301
  • Calculus and Beyond Homework Help
Replies
1
Views
439
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
996
  • Calculus and Beyond Homework Help
Replies
2
Views
608
  • Calculus and Beyond Homework Help
Replies
6
Views
503
  • Calculus and Beyond Homework Help
Replies
3
Views
128
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
706
  • Calculus and Beyond Homework Help
Replies
2
Views
941
Back
Top