# If a function maps $A$ to its PowerSet, is it Surjective?

Given an arbitrary set $$A$$, let $$F : A \rightarrow 2^A$$ be the function defined for all $$a \in A$$ by

$$f(a) = \{a\}$$

If $$A$$ maps to its power set, does this make $$F$$ surjective?

If somebody could help to prove this that would be very helpful

• Have you looked at a basic example, like $A = \{1,2\}$? – pjs36 Apr 11 '15 at 21:28
• I read somewhere that, No matter what A is, the EmptySet is an element of the PowerSet, so it cannot be onto, but I dont understand why – RandomMath Apr 11 '15 at 21:30
• Then you need to read more about what a "power set" is, and probably what it takes for a function to be "onto"/surjective. – pjs36 Apr 11 '15 at 21:32

No it's not surjective because $\emptyset$ is not in the range of $f$

• Just to clarify, where did you get the range of f from? – RandomMath Apr 11 '15 at 21:34
• the range of $f$ is the set of all elements $y$ such that $y=f(x)$ for some $x$, we define it as follow $$Range(f)=f(A)=\{f(x)/x\in A\}$$ and $f$ is surjective if and only if every element is in $f(A)$ – Elaqqad Apr 11 '15 at 21:35

There is no surjective map from $A \to 2^A$ as Cantor has taught us with his diagonal argument.

Let's assume $A$ itself is non-empty so the proposed mapping $f$ has non-empty image. Elements of the power set of $A$ are subsets of $A$. The power set therefore comprises the empty set, "singleton" sets containing exactly one element, sets containing two elements, or three, etc.; if $A$ itself contains infinitely many elements, then $A$ also has subsets containing infinitely many elements, and each is an element of the power set.

In order for a function with codomain $2^{A}$ to be surjective, every subset of $A$ must be in the image.

The image of the mapping $f(a) = \{a\}$ consists of the singleton subsets of $A$. Not every subset of $A$ is a singleton, so $f$ is not surjective.

Perhaps you're conflating the image of $f$ with the union $$\bigcup_{a \in A} f(a) = \bigcup_{a \in A} \{a\} = A?$$

No. There is no $x$ for which $f(x)=\emptyset$. Surjective means it hits everything in $2^A$ which it doesn't because $\emptyset \in 2^A$.

$f$ is injective though.

• for any type of powerset question similar to above, would this hold? – RandomMath Apr 11 '15 at 21:31
• If there was an X for which F(x) = EmptySet, this would make it surjective right? – RandomMath Apr 11 '15 at 21:31
• $\emptyset$ is in any powerset. – ogogmad Apr 11 '15 at 21:32
• You have to hit everything. If there is a surjection between $A$ and $2^A$ then $|A| \geq |2^A|$, which can never be true. For finite sets, it's true because $2^n > n$, and for infinite sets it follows by Cantor's theorem. There is no such surjection. – ogogmad Apr 11 '15 at 21:33