The Gateway to Computer Science Excellence

+43 votes

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

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

0

Is there any other method we can use instead of some counter example to find correct answer, as one may take wrong counter example.

Please suggest

0

@!KARAN-Kenneth Rosen has lot of exercises based on this.Only 5 hours maximum it would take for anyone who has not even touched functions.Once you do it, taking counter-examples would be very intuitive for you.And such question are asked in GATE many times.

+63 votes

Best answer

D is answer.

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$ ,

**LHS != RHS.**

B)

LHS: $f ( A \cap B ) = f (\{\}) = \{\}$.

RHS: $f(A) \cap f(B) = \{ 1\} \cap \{ 1\} = \{ 1\}$

**LHS!=RHS.**

C)

LHS: $|f ( A \cap B )| = |f (\{\})| = |\{ \}| = 0$

RHS: $\min\{|f(A)|,|f(B)|\} = \min(1,1) = 1$

**LHS!=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.

0

Can you please elaborate a little on d)...This is true that in a function a value can be mapped only to one value but how is d) true..?

+30

(S ∩ T) contains common elements of S and T and f^{-1} of that will give the elements of X mapping to those common elements.

Now, f^{-1} (S) will give the elements of X mapping to the elements in S, and f^{-1} (T) will give the same for elements in T. Now, we take intersection and get elements of X which have a mapping to both S and T, or we only get elements of X for which a mapping exist to both S and T. As we know an element cannot have more than 1 mapping in a function. So, this would mean the mapped element must be present in both S and T.

+3

aren't you assuming that function is bijective for the inverse(otherwise inverse doesn't exist) and so if we take bijective assumption for the option B then it is also true.

+1

@srinath sri

i think in part A) |f({a,b,c})| would be 1 as f({a,b,c}) = {1} and this is same for |f(A)| and |f(B)|.

i think in part A) |f({a,b,c})| would be 1 as f({a,b,c}) = {1} and this is same for |f(A)| and |f(B)|.

+1

@srinath,

in option b , you have taken {1,1} and {1} as different sets, and concluded L.H.S != R.H.S , but in sets we dont allow same values again, then L.H.S will be equal to R.H.S.

in option b , you have taken {1,1} and {1} as different sets, and concluded L.H.S != R.H.S , but in sets we dont allow same values again, then L.H.S will be equal to R.H.S.

0

if f(a)=1,f(b)=2,f(c)=1 and

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

A)

what would have been the value of |f(A∪B)|??

what is this | f(x) | in case of set ?

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

A)

what would have been the value of |f(A∪B)|??

what is this | f(x) | in case of set ?

0

@Arjun sir.. For option D , we must assume that function is bijective. And if function is bijective then option B should also be true. ?

Please explain.

Please explain.

0

When I solve this question with the example in d pic I Iet the answer as option B.

Plz correct me if I am wrong anywhere

+1

Here you have made a mistake .. according to your diagram .. f inv (s) = 1,3,4 .. and f inv (t)= 3,2 .. hence their intersection will be 3 .. which is equal to LHS .

Therefore option d is correct.

Therefore option d is correct.

0

Isnt all wrong?

Let

- $X=\{1,2,3,4\}$ and $Y=\{a,b,c\}$
- $A=\{1,2\}$,
- $B=\{3,4\}$,
- $S=\{a,b\}$,
- $T=\{b,c\}$,
- $f(1)=a$,
- $f(2)=f(3)=b$,
- $f(4)=c$
- Digramatically

$f(A\cup B)=|f(\{1,2,3,4\})|=|\{a,b,c\}|=3$

$|f(A)|+|f(B)|=|{a,b}|+|{b,c}|=2+2=4\neq f(A\cup B)\rightarrow $ option (a) is false

$f(A\cap B)=f(\phi)=\phi$

$f(A)\cap f(B)=\{1,2\}\cap \{2,3\}=\{2\}\neq \phi \rightarrow $ option (b) is false

$|f(A\cap B)|=|f(\phi)|=|\phi|=0$

$min(|f(A)|,|f(B)|)=min(2,2)=2\neq 0\rightarrow $ option (c) is false

$f^{-1}(S\cap T)=f^{-1}(\{b\})=\{2,3\}$

$f^{-1}(S)\cap f^{-1}(T)=\{1,2\}\cap \{3,4\}=\phi\neq \{2,3\}\rightarrow $ option (d) is false

In mathematics, a function is a relation between a set of inputs and a set of permissible outputs with the property that each input is related to exactly one output.

+14

Inverse is possible only when the function is Bijective(One to One + Onto). The example used here bu you is onto but not one-to-one.

0

For option d, one way to look is that , Inverse function is given so f must be bijective

i.e for every element of both the sets(x & y) there is a connection, & this connection is like a straight forward bridge of two edges of a river( imagine like that).

then just remove the $f^{-1}$ & see $(S \cap T) = (S) \cap (T)$

It's become trivial.

i.e for every element of both the sets(x & y) there is a connection, & this connection is like a straight forward bridge of two edges of a river( imagine like that).

then just remove the $f^{-1}$ & see $(S \cap T) = (S) \cap (T)$

It's become trivial.

+9 votes

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

0 votes

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

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

52,215 questions

59,981 answers

201,180 comments

94,637 users