The Gateway to Computer Science Excellence
+11 votes

For a set $A$ define $P(A)$ to be the set of all subsets of $A$. For example, if $A = \{1, 2\}$ then $P(A) = \{ \emptyset, \{1, 2\}, \{1\}, \{ 2 \} \}$. Let $A \rightarrow P(A)$ be a function and $A$ is not empty. Which of the following must be TRUE?

  1. $f$ cannot be one-to-one (injective)
  2. $f$ cannot be onto (surjective)
  3. $f$ is both one-to-one and onto (bijective)
  4. there is no such $f$ possible
  5. if such a function $f$ exists, then $A$ is infinite
in Set Theory & Algebra by Veteran (106k points)
edited by | 584 views

2 Answers

+21 votes
Best answer

Even if it can be one-to-one in the following way,

But, It cannot be onto,because, the number of elements in domain $(A)$  $<$ the number of elements in co-domain ($P(A)$) . For a function to be onto, the domain should be able to cover all elements of co-domain with each element of the domain having exactly one image in co-domain.
So, option$(B)$

by Boss (12k points)
edited by

Nice solution.Thanks :)

a function output for a single value is a single value only not a set of values So I think it is wrong

rio What about this function : F(x) = (x x+1)

onto does not mean it has to be one-one. So how B is the ans?


ye you are right  ...a function to be onto need not to be one -one...

but option B is correct this way...

wrong option A:- no. of element in A is less than no.of element in B for always...therefor it can be one-one no problem (evry single element form A could map to unique element in B) 

correct optionB:- a function to be onto ...necessory condition that all the element in B should map to A...but here no. of element in A is less that no. of element in B ..therefor it is not possible could not be onto......i hope now u got it....

niceexplanation @anusha

@Anusha Motamarri

How you mapped 1 -> {1, 2} and 2 -> {1}. Is it random only like any element can be mapped to anyone else or something different?


I didn't understand the question properly

A is a set and P(A) is also a set. The function f: A ->P(A) means the domain and codomain should be set. Then why we are mapping elements of the sets. 

Please help

@Anusha Motamarri.


I've been thinking on the same lines too. :) @vizzard110

I think for a given A there is only one possible P(A).

2 different A's cannot map to a single P(A) so it is one-to one.

And for a given set of A's we have a finite set of P(A)'s, so if we "assume" co-domain (they haven't defined what needs to be taken as co-domainπŸ˜₯) to be the set of all P(A)'s then we have co-domain = range, and hence it is onto.

So I got the answer as option 3) f is both one-to-one and onto.


@rohith1001 I understood the question incorrectly. Question is saying that there is a mapping between elements of set A to the elements of the set of P(A) i.e. all the subsets.

Now if we try to map between these two sets we can map all the elements of A to all elements of P(A) in whatever manner we want. So this function can be one-one.

This function cannot be onto because we cannot map all elements of P(A) to A because |P(A)|>|A|.

Right, so this is the only point in this question.

Thanks @vizzard110

I got it now. :)

So we just have a function that has domain as the elements of A and co-domain as the subsets of A. (Mapping can be anything)

Since |P(A)|>|A| we cannot make the function onto.


@rohith1001 you can take any possible mapping of your own choice but you can always see that onto is not possible.

+1 vote

If the number of elements in Co-domain is greater than number of elements of domain, then the function cannot be onto...

If the number of elements in domain is greater than codomain,then the function cannot be one-to-one.

Here number of elements in co-domain is greater than domain,so obviously there will be atleast one element in co-domain which will not have a preimage in the domain. But it can be one-to-one... 

So Option B)

by Loyal (8k points)

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
50,737 questions
57,392 answers
105,444 users