1
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ Have you looked at a basic example, like $A = \{1,2\}$? $\endgroup$ – pjs36 Apr 11 '15 at 21:28
  • $\begingroup$ 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 $\endgroup$ – RandomMath Apr 11 '15 at 21:30
  • 3
    $\begingroup$ Then you need to read more about what a "power set" is, and probably what it takes for a function to be "onto"/surjective. $\endgroup$ – pjs36 Apr 11 '15 at 21:32
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Just to clarify, where did you get the range of f from? $\endgroup$ – RandomMath Apr 11 '15 at 21:34
  • 2
    $\begingroup$ 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)$ $\endgroup$ – Elaqqad Apr 11 '15 at 21:35
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ for any type of powerset question similar to above, would this hold? $\endgroup$ – RandomMath Apr 11 '15 at 21:31
  • $\begingroup$ If there was an X for which F(x) = EmptySet, this would make it surjective right? $\endgroup$ – RandomMath Apr 11 '15 at 21:31
  • 1
    $\begingroup$ $\emptyset$ is in any powerset. $\endgroup$ – ogogmad Apr 11 '15 at 21:32
  • 2
    $\begingroup$ 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. $\endgroup$ – ogogmad Apr 11 '15 at 21:33
2
$\begingroup$

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? $$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.