edited by
13,899 views
63 votes
63 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, |f(A \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)$
edited by

5 Answers

Best answer
80 votes
80 votes

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

edited by
25 votes
25 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
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).
Answer:

Related questions

41 votes
41 votes
2 answers
3
go_editor asked Sep 28, 2014
8,431 views
Let $G$ be a group with $15$ elements. Let $L$ be a subgroup of $G$. It is known that $L \neq\ G$ and that the size of $L$ is at least $4$. The size of $L$ is __________....
45 votes
45 votes
7 answers
4