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?

  1. For any subsets $A$ and $B$ of $X, |fA \cup B| = |f(A)| + |f(B)|$
  2. For any subsets $A$ and $B$ of $X, f(A \cap B) = f(A) \cap f(B)$
  3. For any subsets $A$ and $B$ of $X, |f(A \cap B)| = \min \{|f(A)|, |f(B)|\}$
  4. For any subsets $S$ and $T$ of $Y, f^{-1}(S \cap T) = f^{-1}(S) \cap f^{-1}(T)$
in Set Theory & Algebra by Veteran
edited by | 4.9k views
Inclusion–exclusion principle.

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

@Shaik Masthan @Mk Utkarsh @Ayush Upadhyaya @srestha


@!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.


@Ayush Upadhyaya

Could you please tell me which part of Kenneth Rosen has these questions related to counters.

4 Answers

+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 \}$
LHS: $|f ( A \cup B )| = |f (\{a,b,c\})| = |\{1\}| = 1$

RHS: $|f(A)|+|f(B)| = 1 + 1 = 2$ ,

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

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

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

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.

by Active
edited by
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..?

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


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.

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

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.
yes. Those were wrong. Corrected the example now..
if  f(a)=1,f(b)=2,f(c)=1 and
  what would have been the value of    |f(A∪B)|??

what is this | f(x) |  in case of set ?
@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.
In option D, the inverse is used -- so it is safe to assume that it exists.

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

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.

Isnt all wrong?


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

Option (a)

$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

Option (b)

$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

Option (c)

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

Option (d)

$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

Definition of function from wikipedia:

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.



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. 

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


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.


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)


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.


by Boss

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

If so, then why not option B is true.

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).
by Junior
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 ....
0 votes

Option D is true...all 3 are false

by Junior

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,215 questions
59,981 answers
94,637 users