Proving f is Not Surjective: A Finite Set Mapping to its Power Set

[nicksauce]

Homework Statement

Suppose that f is a mapping from a finite set X to P(X) (the power set of X). Prove that f is not surjective.

Homework Equations

The Attempt at a Solution

My proof strategy is
1) Show that P(X) always has more elements than X
2) Show that a mapping from X->Y cannot be surjective if Y has more elements than X.
(Unless someone can suggest a better strategy ;)

1)We'll prove this by induction. Let |X| represent the number of elements in a finite set X. For the base case, X={a} and P(x)={ {a}, {a,0} }, so it holds (0 means the null set here). For the inductive step suppose X={a1,...,an} and |P(x)| > |X|. Let Y = {a1,...an,a_n+1}, where we have added a new element a_n+1. Then |Y|=|X|+1. But P(Y)=P(X) (union) {a_n+1} (union) {a_n+1,0} (union) Possibly some other sets including a_n+1. Thus
|P(Y)| >= |P(X)| + 2 > |P(X)| + 1 > |X| + 1 = |Y|.

2)Suppose X={x1,...,xn} and Y={y1,...,ym} where m>n. Let f:X->Y. Then the image of f has at most n distinct elements, so there are at the fewest m-n elements of Y that aren't in the image of f. Since m-n > 0, this means that f is not surjective, as there m-n elements of Y that cannot be written as f(x) for some x in X.

Just a rough outline of the proof, but does that seem okay?

 

[tiny-tim]

Suppose that f is a mapping from a finite set X to P(X) (the power set of X). Prove that f is not surjective.
…
(Unless someone can suggest a better strategy ;)

Hi nicksauce!

The object is to construct an A in P(X) such that A is not an f(x) …

Do you know the proof that the real numbers are not countable?

You can adapt it to this.

(if you don't know it, come back for a specific hint )

 

[nicksauce]

I don't know that proof, so that specific hint might be helpful. Thanks.

 

[tiny-tim]

ok…

For a given f, you need to construct a subset of X which is not an f(x).

Hint: for a given f, for each x, either x ε f(x), or x ε X - f(x).