GATE CSE
First time here? Checkout the FAQ!
x
+14 votes
838 views

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?

  1. \(g(h(D)) \subseteq D\)
  2. \(g(h(D)) \supseteq D\)
  3. \(g(h(D)) \cap D = \phi\)
  4. \(g(h(D)) \cap (B - D) \ne \phi\)
asked in Set Theory & Algebra by Veteran (66.1k points) 1148 2196 2522 | 838 views
We can not say h is inverse of g but yes it has some inverse behavior.

2 Answers

+19 votes
Best answer

$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 lest 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) , then we would have got  $g(h(D)) = D$.

 

 

answered by Active (2.3k points) 2 19 33
selected by
If h({c})={}h({c})={} , then h is not a function as per its definition.

Therefore f must be bijective.

Well explained Thanks :-)

+2 votes

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 =2B = {{},{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

 

 

answered by Boss (8.8k points) 3 8 12

@Warrior how are you saying that

g({})={}

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

can you explain ... ?

Have the same doubt.

As it is given g(C)={f(x)∣xC}, 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?

Answer:

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
Top Users Oct 2017
  1. Arjun

    23210 Points

  2. Bikram

    17018 Points

  3. Habibkhan

    6652 Points

  4. srestha

    5864 Points

  5. Debashish Deka

    5430 Points

  6. jothee

    4908 Points

  7. Sachin Mittal 1

    4762 Points

  8. joshi_nitish

    4274 Points

  9. sushmita

    3954 Points

  10. Silpa

    3698 Points


Recent Badges

Regular Juhi Sehgal
Popular Question vineet.ildm
Nice Comment Arjun
100 Club vipul verma
Notable Question jothee
Popular Question jothee
Nice Question shivangi5
Regular rinks5
Notable Question shipra tressa
Regular sasi
27,247 questions
35,056 answers
83,703 comments
33,183 users