The complete statement is: Let $(A,≤)$ be a well-ordered nonempty set and let $f$ be the function of $P(A)-${$Ø$} in $A$ defined for: $f(S) =$ first element of $S$.

(a) Prove that $f$ is surjective.

(b) Prove that if $| A | > 1$ then $f$ is not injective.

Clarification: Let $A$ be a set, $P(A)$ denotes the set of parts of $A$. The elements of $P (A)$ are the subsets of $A$:

$P(A)=$ {$x:x$ is a subset of $A$}

To understand the problem,I have create a small example that is the following:

$A=${$1,2,3$} then $P(A)=${$Ø$,{$1$},{$2$},{$3$},{$1,2$},{$1,3$},{$2,3$},{$1,2,3$},}

Then, $f$({$1$})$=$$f$({$1,2$})$=$$f$({$1,3$})$=$$f$({$1,2,3$})$=1$



So for this small example it is verified that every element of $A$ is an image of some element of $P(a)$ then, $f$ is surjective

But I don't know how to demonstrate the exercise in a general way so that's my question.

  • 1
    $\begingroup$ For your first question, your example should help you understand how to find an antecedent of any element $a\in A$. The simplest subset containing $a$ as its first element is..? For the second question, consider two distinct elements $a$ and $a'$, and assume that $a<a'$. Can you build two distinct subsets, using $a$ and $a'$, which have the same image by $P$? $\endgroup$ – Suzet Jun 21 '18 at 3:52
  • 1
    $\begingroup$ The simplest subset that contains containing $a$ as its first element is is the subset that contains only that element, {$a$} $\endgroup$ – Ayesca Jun 21 '18 at 4:04

For $x\in A$, we have $f(\{x\})=x$.

It follows that $f$ is surjective.

Next, suppose $|A| > 1$.

Let $x,y\in A$, with $x\ne y$.

Without loss of generality, assume $x < y$.

Then $f(\{x,y\}) = x$, and $f(\{x\}) = x$, so $f$ is not injective.

| cite | improve this answer | |

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.