GATE CSE 2014 | Set 3 | Question: 2

Question

Let $X$ and $Y$ be finite sets and $f:X \to Y$ be a function. Which one of the following statements is TRUE?

• A. For any subsets $A$ and $B$ of $X, |f(A \cup B)| = |f(A)| + |f(B)|$
• B. For any subsets $A$ and $B$ of $X, f(A \cap B) = f(A) \cap f(B)$
• C. For any subsets $A$ and $B$ of $X, |f(A \cap B)| = \min \{|f(A)|, |f(B)|\}$
• D. For any subsets $S$ and $T$ of $Y, f^{-1}(S \cap T) = f^{-1}(S) \cap f^{-1}(T)$

Comments

And for other option take examples .here A and B  are subset.

Take examples A = { 1,2,3} , B ={3,4,5} now f(1) =a, f(2)=b , f(3)=c ,f(4)=a, f(5)=e

---

I wanted to clear one thing $$f^{-1}$$ here is not the inverse function. It is the notation of the inverse image . These are two differenet thing used in two different concept even though the notation is same. 
plese open link provided by the legend_of_cse and read about the inverse image in it . It contains all the properties also which will be useful as GATE ask such questions.



This image is from the book "Discreat mathematics and its application kenneth rosen eight edition" page number 163
here before asking that same question they have defined here what is inverse image and then a beware that its not the inverse function 
So here the gate should also have define what they mean by f^-1 

So the option D is true regardless of whether f inverse exist or not.

---

\(f^{-1}(S \cap T)\)  contains every \(x \in X\) such that f(x) is in S and T both.

 \(f^{-1}(S)\) contains every \(x \in X\) such that f(x) is in S.
 \(f^{-1}(T)\) contains every \(x \in X\) such that f(x) is in T.

\(f^{-1}(S) \cap f^{-1}(T)\) contains every \(x \in X\) such that f(x) is in S and T both.

Hence, Option (D) is correct!

Answer 1

3 out of 4 options can be eliminated with the help of a counter example.

Let $X = \{ a , b , c \}$ and $Y = \{ 1 , 2 \}$
A Function $f$ maps each element of $X$ to exactly one element in $Y$.
Let $f(a)=1 , f(b)=1 , f(c) =1$ and $A = \{ a  \}, B = \{ b , c \}$

A)

• LHS: $|f ( A \cup B )| = |f (\{a,b,c\})| = |\{1\}| = 1$
• RHS: $|f(A)|+|f(B)| = 1 + 1 = 2$ ,
• $\textbf{LHS} \neq \textbf{RHS}$

B)

• LHS: $f ( A  \cap B ) = f (\{\}) = \{\}$.
• RHS: $f(A) \cap f(B) = \{ 1\} \cap \{ 1\} = \{ 1\}$
• $\textbf{LHS} \neq \textbf{RHS}$

C)

• LHS: $|f ( A  \cap B )| = |f (\{\})| = |\{ \}| = 0$
• RHS: $\min\{|f(A)|,|f(B)|\} = \min(1,1) = 1$
• $\textbf{LHS} \neq \textbf{RHS}$

D)

Its easy to see that this is true because in a function a value can be mapped only to one value. The option assumes inverse of function $f$ exists.

 

Answer is $D$.

Comments

@Dknights bcz bijections is same as inverse only this is two way statement . 

source: kennath rosen 

---

@Dknights Inverse of a function exisit only if the function f is bijection 

---

for Option D 

Answer 2

f is a function from $X \rightarrow Y$

Let's consider options one by one and also consider whether we can have a failure case for each of the options

(A)

For any subsets A and B of X,$|f(A∪B)|=|f(A)|+|f(B)|$

This case can fail if A and B have atleast one common element, in that case AUB will count only total number of distinct elements in A and B and then it will find image of all such elements and give the count

But the RHS expression will separately give count for the number of images of A+Number of images of B.

Assume A={A,B} and B={B,C}. $|f(A)|=2$ and $|f(B)=2|$ and $|f(A \cup B)|=3$

So this option is clearly wrong.

(B) 

For any subsets A and B of X,$f(A∩B)=f(A)∩f(B)$

This can fail in case of Many to one function where A and B are completely disjoint but the image set of A and B overlap.

Take A={A,B} and B={C,D} LHS will come to be empty but RHS will have 2.

So this option also ruled out.

And through this reasoning also I rule out option (C)

(D) 

For any subsets S and T of Y, $f^{−1}(S∩T)=f^{−1}(S)∩f^{−1}(T)$

If they have defined inverse of the function f , this means f is invertible and hence one-to-one and onto.

Since f is bijective, whenever any subsets of Y, S and T overlap, their corresponding images in $f^{-1}$ would also overlap.

And if they don't overlap, then their images also won't.

ANS-D

Comments

Ayush Upadhyaya

If inverse exist, then can we say that the function is bijective ??

If so, then why not option B is true.

---

@mrinmoyh, Simply because there is no inverse defined in option B.

---

Alapan Chatterjee awesome observation

---

@Ayush Upadhyaya

How you came to the conclusion that  they have defined inverse of the function f , in D.

Answer 3

Option D is true...all 3 are false

Answer 4

ANS-D

Answer 5

What question wants to ask is for One-One Functions option B) always holds.

B) For One to One functions, whatever is common in A and B will also give the same image in Y else it will give different images. Eg F(a)=1, F(b)=2, and F(c)=3

A={a,b} and B={b,c}

In A /\ B = {b} then images of A and B will also give common element which is the image of b= 2. This is in agreement with One-One property if F(a)= F(b) then a=b only.

In D) option they have given a Bijective Function, which is One-One from both sides. So This property will hold in D)

A) and C) are easy to prove by taking counter examples. However, i can see that A) is definitely true if Function is One-One and A and B are disjoint sets(A /\ B = Null).

In C) This will be valid always only if either A is a subset of B or vice-versa((A /\ B) =A or B).

Comments

where hav they mentioned bijective function ???

---

If inverse exists for a function then it must be bijective.

---

Jst see Arjun sir's commet in the best answer ....

Answer 6

I do see rigorous examples supporting Option(D) but not a rigorous proof. Although not mentioned in the question we must assume that the function has an inverse over the subsets $S,T$.

CLAIM:- Let $f:X \to Y$ be a function from $X$ to $Y$. Let $S,T$ be subsets of $Y$ such that $f$ has an inverse over these subsets. Then,

\[f^{-1}(S \cap T)=f^{-1}(S) \cap f^{-1}(T)\]

 

PROOF:-

Let $q\in f^{-1}( S\cap T)$. Then, 

\[f(q)\in S\cap T\] $\implies$

\[f(q)\in S  \wedge  f(q)\in T\]

So,

\[q\in f^{-1}(S) \wedge  q\in f^{-1}(T)\]

Finally,

\[q\in f^{-1}(S) \cap f^{-1}(T)\].

This is one side of the proof. The other side follows similarly by beginning with $q \in f^{-1}(S) \cap f^{-}(T)$ and proving that $q\in f^{-1}(S\cap T)$.