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

4 Answers

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

answered by Active (2.1k points)
edited by
0
If h({c})={}h({c})={} , then h is not a function as per its definition.

Therefore f must be bijective.
0

Well explained Thanks :-)

+4 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 Loyal (6.8k points)
0

@Warrior how are you saying that

g({})={}

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

can you explain ... ?

0

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?

0
how to show D as false?
0 votes
0 votes
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=ϕ
answered by Active (1.8k points)
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

40,871 questions
47,531 answers
146,040 comments
62,298 users