# Thread: If [TEX]f:A\to B[/TEX] is onto [TEX]B[/TEX], then [TEX]P(B)\leq P(A)[/TEX]

1. ## If [TEX]f:A\to B[/TEX] is onto [TEX]B[/TEX], then [TEX]P(B)\leq P(A)[/TEX]

Set theory question.

I need to prove 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!

2. ## Re: If [TEX]f:A\to B[/TEX] is onto [TEX]B[/TEX], then [TEX]P(B)\leq P(A)[/TEX]

You mean |P(B)| <= |P(A)| ?

3. ## Re: If [TEX]f:A\to B[/TEX] is onto [TEX]B[/TEX], then [TEX]P(B)\leq P(A)[/TEX]

Originally Posted by Also sprach Zarathustra
Set theory question.
I need to prove that if $f:A\to B$ is onto $B$, then $|P(B)|\leq |P(A)|$. And $|B|\leq |A|$ under axiom of choice.

The way one proves this depends on the way $\le$ is defined.

This might help. There must be an injection $g:B\to A.$

4. ## Re: If [TEX]f:A\to B[/TEX] is onto [TEX]B[/TEX], then [TEX]P(B)\leq P(A)[/TEX]

We have a surjection f from A to B. We need an injection g from P(b) to P(A).

Let b in P(B), we define g like this : g(b)=f^-1(b). g is an injection, proof by contradiction :
let b1 and b2 two subsets of B such that b1=/=b2 and g(b1)=g(b2)=S (S is some subset of A).
Let c in b1\b2 (c is in b1 and not in b2) let x=f^-1(c). x exists because f is surjective. we know that x is in S and f(x)=c.
But c=f(x) belongs to b2 also (because the image of an element of S is in b1 and in b2). This is a contradiction because c is in b1/b2.

so we have an injection from P(b) to P(A) this means by definition |P(b)<=|P(A)|

5. ## Re: If [TEX]f:A\to B[/TEX] is onto [TEX]B[/TEX], then [TEX]P(B)\leq P(A)[/TEX]

Originally Posted by Also sprach Zarathustra
Set theory question.
I need to prove that if $f:A\to B$ is onto $B$, then $|B|\leq |A|$ under axiom of choice.

$f$ is an surjection from $A\to B.$

Let $\mathcal{C}=\left\{f^{-1}(\{b\}):b\in B\right\}$. Now $\mathcal{C}$ is a partition of the set $A$.

There is a choice function, (why?) on $\mathcal{C}$ so that $a_b\in f^{-1}(\{b\})$.

Define $g:B\to A$ by $b\mapsto a_b$.

Show that $g$ is an injection.