GATE CSE 2003 | Question: 37

Question

Let \(f : A \to B\) be an injective (one-to-one) function. Define \(g : 2^A \to 2^B\) as:
\(g(C) = \left \{f(x) \mid x \in C\right\} \), for all subsets $C$ of $A$.
Define \(h : 2^B \to 2^A\) as: \(h(D) = \{x \mid x \in A, f(x) \in D\}\), for all subsets $D$ of $B$. Which of the following statements is always true?

• A. \(g(h(D)) \subseteq D\)
• B. \(g(h(D)) \supseteq D\)
• C. \(g(h(D)) \cap D = \phi\)
• D. \(g(h(D)) \cap (B - D) \ne \phi\)

Comments

f(f^−1(D)) ⊆ D This happens because of codomain can have elements that are not mapped by any element from domain so while doing this we get a subset of codomain subset that are mapped by domain. so in the question h(D) is acting like a inverse function of f. we can also use , f(h(D)) subset of D right? that also true? because  f(subset of domain) = set of images for domain subset , right? @legend_of_cse

Note: if f is surjective then f(f^-1(D)) = D

correct me if i am wrong.

---

One Variation: when f is not one - one ( f: A -> B)

f^−1(f(C)) ⊇ C for any proper subset of domain A

if C = A (special case) then

f^-1(f(C)) = C

if f is one to one then,

f^-1(f(C)) = C for any subset of domain A

 

---

D = {a, c}
h(D) = {1}
g(h(D) = g({1}) = {a}.
And g(h(D)) ⊆ D, everything in g(h(D)) is inside D. So it can't have anything in B − D.

Answer 1

$f:A\rightarrow B$ is a one to one function. Every element in A will have a corresponding element in B. Therefore, the size of range for this is n(A) and n(B) $\geq$ n(A).

$g:2^{A}\rightarrow 2^{B}, g(C)=\left \{f(x) \mid x\in C \right \}$ , since $f$ is one to one, for every subset of A there will be corresponding subset of B. Therefore, this is also a one to one function and size of range for this is $n(2^{A}).$

$h:2^{B}\rightarrow 2^{A}, h(D)=\left \{ x \mid x\in A, f(x)\in D \right \}$ this function is not a one to one function. Every subset of B will be mapped to subset of $A$ for which it has all the images of subset of $A$. Size  of range for this function will be $n(2^{A}).$

That said, now $g\left ( h\left ( D \right ) \right )$ will also have the range of size $n(2^{A}).$ Since $n(A)\leq n(B), n(2^{A})$ must be less than or equal to $n(2^{B}).$ The answer is $g\left ( h\left ( D \right ) \right )\subseteq D$.

For example let $A = \left\{1, 2 \right\}$ and $B = \left\{a, b, c\right\}$. Let $f(1) = a, f(2) = b$. Now,

• $g\left( \left\{ \right\} \right) = \left\{\right\} $
• $g\left( \left\{1\right\} \right) = \left\{a\right\} $
• $g\left( \left\{2\right\} \right) = \left\{b\right\} $
• $g\left( \left\{1,2\right\} \right) = \left\{a,b\right\} $
• $h\left( \left\{\right\} \right) = \left\{\right\} $
• $h\left( \left\{a\right\} \right) = \left\{1\right\} $
• $h\left( \left\{b\right\} \right) = \left\{2\right\} $
• $h\left( \left\{c\right\} \right) = \left\{\right\} $
• $h\left( \left\{a, b\right\} \right) = \left\{1, 2\right\} $
• $h\left( \left\{a, c\right\} \right) = \left\{1\right\} $
• $h\left( \left\{b, c\right\} \right) = \left\{2\right\} $
• $h\left( \left\{a, b, c\right\} \right) = \left\{1, 2\right\} $

Now, we can see that for any $D \subseteq B, g(h(D)) \subseteq D$. Had the function $f$ been bijective (one-one and onto or one-one and co-domain = range), we would have got  $g(h(D)) = D$.

Correct Answer: $A$

Comments

pls tell me how the subset of A i.e. {1,2} maps to {a,b}. I mean Is this a union operation i.e g{1}Ug{2} just like kind of a homomorphism??/

---

@ankitrazzagmail.com

$h(\{c\}) = \phi$ means it is empty and NOT that $\phi$ is an element of A. To represent that, we have to write $h(\{c\}) = \{\phi\}$ which is not the case here.

---

in this the last option would be wrong if A and B are of equal size ?

Answer 2

For this problem, we just take an example which satisfies all the conditions which are given in the Qs.

For example let A={1,2} and B={ a,b,c}. Let f(1) =a, f(2)=b. Now, 

g({})={}

g({1})={a}

g({2})={b}

g({1,2})={a,b}

h({})={}

h({a})={1}

h({b})={2}

h({c})={}

h({a,b})={1,2}

h({a,c})={1}

h({b,c})={2}

h({a,b,c})={1,2}

we can see that h is not One-to-One.

Now, we find out g(h(D)).

D =2^B = {{},{a},{b},{c} ,{a,b} ,{a,c},{b,c},{a,b,c} }

h(D)= { {},{1},{2},{1,2} }

g({})={}

g({1})={a}

g({2})={b}

g({1,2})={a,b}

g(h(D)) = {{},{a},{b},{a,b}}

Now we can see that for any D⊆B,g(h(D)) ⊆ D. Had the function f been bijective (one-one and onto or one-one and co-domain = range) , then we would have got  g(h(D))=D.

The correct answer is,(A) g(h(D))⊆D

Comments

@Warrior how are you saying that

g({})={}

h({})={} ... ?

can you explain ... ?

---

Have the same doubt.

As it is given g(C)={f(x)∣x∈C}, for all subsets C of A.

∴g({ })=f(x) | x∈C.

For what value of x can you get f(x)={ } ? There is no such element as { } in f's co-domain. How should we proceed?

---

how to show D as false?

Answer 3

The function  $f:A\rightarrow B$ is a one-one function so, $n(B)\geq n(A)$. 

Let $n(B)$ = 5 and $n(A)$ = 4.

 

Let $D$ be a subset of $B$ of 4 elements. 

 $h : 2^B \to 2^A$         $h(D) = C$.  Thus it is clear $h$ is not a one-one function.

$g : 2^A \to 2^B$          $g(h(D))=g(C) = E$.  (g is a one-one function).   And $E\subseteq D$.

Hence, $g(h(D))\subseteq D$. 

Correct Option: A.

Comments

Nice Explanation!!

---

Best way

Answer 4

http://www.cse.iitd.ernet.in/~mittal/gate/gate_math_2003.html

Answer 5

Let's go through this problem step by step, breaking down the given definitions and analyzing the options logically.

Step 1: Understanding the Definitions

We are given:

- A function f: A → B which is injective (i.e., one-to-one).

Now, two set functions are defined:

Function g : $2^A$ → $2^B$ 

Defined as: g(C) = { f(x) | x ∈ C }

This means:  

Given a subset C ⊆ A, apply the function f to every element of C, and collect the results in a set.  

So g maps subsets of A to subsets of B via f.

Function h :$ 2^B$ → $2^A$  

Defined as: h(D) = { x ∈ A | f(x) ∈ D }

This is the pre-image under f:  

Given a subset D ⊆ B, find all x ∈ A such that f(x) ∈ D.  

So h maps subsets of B back to subsets of A, using f⁻¹ (where defined).

Step 2: Composition g(h(D))

We want to understand what happens when we do: g(h(D))

Let’s break it down:

- h(D) gives you all x ∈ A such that f(x) ∈ D

- Then, g(h(D)) = { f(x) | x ∈ h(D) }

But from the definition of h(D), we already know f(x) ∈ D.  

So this means: g(h(D)) = { f(x) | f(x) ∈ D } ⊆ D

That is: g(h(D)) ⊆ D

✅ So, Option A is correct

Now check each option logically:

Option B: g(h(D)) ⊇ D ❌  

False. If D contains elements not in the image of f, those cannot appear in g(h(D)).

Option C: g(h(D)) ∩ D = ∅ ❌  

False. In fact, g(h(D)) ⊆ D, so the intersection is generally non-empty.

Option D: g(h(D)) ∩ (B − D) ≠ ∅ ❌  

False. Since g(h(D)) ⊆ D, it has no element in B − D.

✅ Final Answer:  A is correct .
 

Answer 6

There can be three cases with respect to D

Case i> All the elements of D are from range set of function f

               In that case  g(h(D))=D

Case ii> All the elements of D are from  (B- (range of f) ) set

              in that case h(D)=ϕ,  so, g(h(D))=ϕ

Case iii> Few elements of D are form range of f and few other elements of D are from (B- (range of f))

            in that case g(h(D))=elements of D which are from range of f, hence in this case g(h(D)) is a subset of D

A. In whichever above category D  falls g(h(D))⊆D is true, Hence Answer

B. g(h(D))⊇D false, as we can see in all the three cases g(h(D)) is either equal to D or it is proper subset of D

C. g(h(D))∩D=ϕ false,  as we can see from case i and iii, it can be non empty

D. g(h(D))∩(B−D)≠ϕ false, as we can see from case ii, g(h(D)) can be ϕ, and ϕ ∩ any set=ϕ