GATE CSE
First time here? Checkout the FAQ!
x
+11 votes
1.3k views

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)$
asked in Set Theory & Algebra by Veteran (87.2k points)   | 1.3k views

2 Answers

+23 votes
Best answer
D)

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

B)
     $f ( A  \cap B ) = f (\{\}) = \{\}$.
$f(A) \cap f(B) = \{ 1\} \cap \{ 1\} = \{ 1\}$
LHS!=RHS
C)
     $|f ( A  \cap B )| = |f (\{\})| = |\{ \}| = 0$
$\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.
answered by Loyal (3.7k points)  
edited by
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 ?
@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.
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).
answered by (269 points)  
Answer:

Related questions



Top Users Sep 2017
  1. Habibkhan

    6836 Points

  2. Arjun

    2310 Points

  3. Warrior

    2306 Points

  4. rishu_darkshadow

    2092 Points

  5. A_i_$_h

    2004 Points

  6. nikunj

    1980 Points

  7. manu00x

    1750 Points

  8. Bikram

    1744 Points

  9. SiddharthMahapatra

    1718 Points

  10. makhdoom ghaya

    1690 Points


26,038 questions
33,650 answers
79,695 comments
31,069 users