- #1

nicksauce

Science Advisor

Homework Helper

- 1,272

- 5

## 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?