Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I need some hints for proving that if $f:A\to B$ is onto $B$, then $P(B)\leq P(A)$. And $|B|\leq |A|$ under axiom of choice.

Thank you!

share|improve this question
    
How constructing one-to-one function $F$, where $F:P(B)\to P(A)$? –  17SI.34SA Dec 6 '12 at 3:48

2 Answers 2

up vote 3 down vote accepted

Define $\hat f\colon P(B)\to P(A)$ by setting $\hat f(X)=\{a\in A\mid f(a)\in X\}$. You can show this is an injection.

If the axiom of choice holds simply choose from $\hat f(\{b\})$ to construct the injection from $B$ to $A$.

share|improve this answer

First, try relating the cardinality of $A$ and $B$ by using the information you have. Then, use that to generalize up to the cardinality of the power sets.

share|improve this answer
    
If A and B are finite sets, I can say that |B|<|A|. But what in the case they aren't? –  17SI.34SA Dec 6 '12 at 3:16
    
Jebruho, relating the cardinalities requires choice. –  Asaf Karagila Dec 6 '12 at 8:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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