The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+22 votes
1.3k 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 (69k points) | 1.3k views
We can not say h is inverse of g but yes it has some inverse behavior.

2 Answers

+26 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.4k points)
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 :-)

+3 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 Veteran (16.3k points)

@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

33,646 questions
40,193 answers
114,178 comments
38,666 users