TIFR CSE 2017 | Part A | Question: 11

Question

Let $f \: \circ \: g$ denote function composition such that $(f \circ g)(x) = f(g(x))$. Let $f: A \rightarrow B$ such that for all $g \: : \: B \rightarrow A$ and $h \: : \: B \rightarrow A$ we have $f \: \circ \: g = f \: \circ \: h \: \Rightarrow g = h$. Which of the following must be true?

• A. $f$ is onto (surjective)
• B. $f$ is one-to-one (injective)
• C. $f$ is both one-to-one and onto (bijective)
• D. the range of $f$ is finite
• E. the domain of $f$ is finite

Comments

Final official ans - Option B.

http://univ.tifr.res.in/gs2017/Files/GS2017_QP_CSS.pdf

---

above question actually is the definition of one to one function

---

link not working

Answer 1

$f:A\rightarrow B$ is injective if and only if, given any functions $g,h:B\rightarrow A$ whenever $f\circ g=f\circ h,$ $f\circ g=f\circ h,then\ g=h$.

Refer to properties of Injective functions: https://en.wikipedia.org/wiki/Injective_function

Let us prove $(\forall g,h:f(g(x))=f(h(x))\rightarrow g(x)=h(x))\rightarrow f\ is\ one-to-one$ is true.

This is equivalent to, $f\ is\ not\ one-to-one\rightarrow (\exists g,h:f(g(x))=f(h(x))\wedge g(x)\neq h(x))$

Let us assume LHS is true, i.e. $f\ is\ not\ one-to-one$.

Then there exists some $c,d\in A$ such that,

                                     $f(c)=f(d)=a,$ where $a$ is an arbitrary element which belongs to B

Let g and h be some functions out of all possible functions from B to A such that $g\neq h$,

                                     i.e. $g(x)=c\ and\ h(x)=d\ \exists c,d\in A\ and\ \exists x\in B$

$\therefore f(g(x))=f(c)=a\ and\ f(h(x))=f(d)=a$ and $g(x)\neq h(x)$, i.e. RHS is also true.

Thus, whenever $\forall g,h\ f\circ g=f\circ h\rightarrow g=h$ is true, $f \ is\ one-to-one$.


Domain of $f$ need not be finite. Let $f:A\rightarrow B$ be identity function and A and B be infinite sets. Assume that $f\circ g=f\circ h$ is true,

then $f(g(x))=f(h(x))\rightarrow g(x)=h(x))$ will be true $\forall g,h$ since $f$ is an identity function. So, even if domain of f is not finite, the condition holds true.

Correct Answer: $B$

Comments

how to approach this kind of question ?? by taking example ??

---

Well...this question is based on the definition of one-to-one function i.e. f(a)=f(b) only when a=b...

Answer 2

i think domain of F must be finite.
morover i think domain of F i.e, A shud be singleton set.
bcoz it is given that for all g and h possible between B and A, f∘g=f∘h⇒g=h..
if domain of F contains more than 1 element in domain,  f∘g=f∘h is possible but, g will not be equal to h
example:
suppose
A,B are set of all integers
g(x)= {x| for all integers x}
h(x)= {1 | for any integer x}
f(x) = {2| for any integer x}
if we see here,
f∘g=f∘h
f∘g = {(x,2)| for all integers x belongs to B}
f∘h = {(x,2) | for all integers x belongs to B}
but actually g and h are not equal.
so domain of f cant contain more than 1 element to ensure "if  f∘g=f∘h then g=h."
if A contains only one element, there is no other way for g and h except to map to that one element.
i mean number of functions possible from B-->A will be only one function if A is singleton set so, g and h will be equal obviously if f∘g=f∘h.
so i think E is the answer

Comments

if you take domain of f as not finite, there will be a possibility that, fog=foh and g!=h..like i quoted in the example.
A,B are set of all integers
g(x)= {x| for all integers x}
h(x)= {1 | for any integer x}
f(x) = {2| for any integer x}
if we see here,
f∘g=f∘h
f∘g = {(x,2)| for all integers x belongs to B}
f∘h = {(x,2) | for all integers x belongs to B}
but actually g and h are not equal.

this is the problem when domain of f is not singleton set.
you should prove that for all possible functions g and h, with domain of f being NOT finite, the given condition gets satisfied. my counter example to your statement is above example.
there exists a function whose domain is not finite and given condition is not satisfied.

if you want to counter example mine, you should prove that there exists two functions g and h, such that fog=gof and g!=h with domain of 'f' being singleton set.

---

Consider the line in question - Which of the following must be true?

I want to say that Domain of f is finite, need not be the case always. There may exist another case too when domain of f is not finite. Hence, Domain of f must be finite always is not true.

Moreover, if I suppose that domain of f is finite, range must also be finite, and if I also suppose that A is singleton f must be one-one also. But only a single option is correct.

It may be the case that I am mistaken somewhere, you can take a look how I think by my answer below. And we can wait for official answer key by TIFR since they release it along with the question paper.

Thank you for your time and energy...

---

final thing i want to say is,
if you say that there exists one g and h such that , given condition is satisfied with f being not finite,it is not sufficient. you should prove that the condition is satisfied for all possible g and h, from B-->A with A being not finite,  is needed.!
if there are 3 functions possible from from B-->A, for all 3 functions, this condition must be satisfied. but you are showing only one such function from B-->A. take all the possibilites and check if every function is satisfying it or not bcoz of the word "FOR ALL".
and yes lets wait for official key :)

Answer 3

We can tackle this question by elimination. 

| Domain | >= | Range |

So, if domain is finite, then range must be finite. both d and e must be true. So, domain is not finite since the question has a single option correct. 

Moreover, we can take an example to counter the statement that domain or range is finite. Example is -> 

Example 1-

if A = B = Set of all real no.s, and if g(x) = x-1, h(x) = x+1, f(x) = x (domain, range of all three functions not finite)

then the condition that f o g = f o h => g=h will also be satisfied. How?

The condition can be written as if g not equal h, then f o g not eq f o h.

In this case, let's assume f o g = f o h are equal even if g is not equal to h.

=>   x + 1 = x -1

=> 1 = -1 ( which is false always)

Hence, our assumption was wrong. Therefore, in this example the condition f o g = f o h => g=h is satisfied.

The options that remain are a,b,c.

Example 2-  

if A = Singleton Set, B = any set may or may not be singleton. From B -> A, only one function is possible because all the elements of the domain (B ) must be mapped to that single element in A only. Then, g = h is always true in this case. So, f o g = f o h => g=h will always be true. 

But, f from A -> B has a single element in the domain, so will be mapped to single element in B. Hence, for f is not onto. So, f is not a bijection also. Hence, option a and c are wrong. d and e were prooved wrong by the previous example.

So, the correct option is b. f must be one-one.

Comments

Thank you. Got it.

---

you could have gone through the explanation provided already and answer has been selected as well:)

---

Hi

I have edited my answer, taking reference to the example you mentioned in the comments above.

Answer 4

definition of one to one function --->

f(x1)=f(x2)===>x1=x2

fog(x)=f(g(x))

foh(x)=f(h(x))

now it is given that fog=foh==>g(x)=h(x)

then it prove from above definition is that it is a one -to-one functionhttps://en.wikipedia.org/wiki/Injective_function

check in definition part

Comments

why it is not onto?

---

Since the cardinality of A and B can be different, so it can’t be onto.