# Homework Help: Onto Mappings from a Set to Its Power Set

1. Sep 6, 2008

### e(ho0n3

The problem statement, all variables and given/known data
Prove that there are no mappings from a set S onto S*, where S* is the power set of S.

The attempt at a solution
This begs proof by contradiction: Let f be a mapping from S onto S*. Then for every A in S*, there is an a in S with f(a) = A. I don't know how to proceed from here. Any tips?

2. Sep 6, 2008

### Dick

Can you construct a subset of S (call it B) that is different from all of the other subsets f(a)? Hint: a is either in f(a) or not in f(a). Whichever it is, make B the opposite. Think 'Cantor diagonal'.

3. Sep 6, 2008

### e(ho0n3

Hmm...let B = {a in S : a not in f(a)}. B belongs to S* and since f is onto there must be an x in S for which f(x) = B.

I guess I should now ask if x is in B? Suppose it is. Then x is not in f(x) = B. Contradiction. If x is not in B, then x is in f(x) = B. Contradiction. Hence, f can't be onto.

Thanks a lot!