Power set / surjection

  • Thread starter nicksauce
  • Start date
  • #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?
 

Answers and Replies

  • #2
tiny-tim
Science Advisor
Homework Helper
25,832
251
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! :smile:

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. :smile:

(if you don't know it, come back for a specific hint :wink:)
 
  • #3
nicksauce
Science Advisor
Homework Helper
1,272
5
I don't know that proof, so that specific hint might be helpful. Thanks.
 
  • #4
tiny-tim
Science Advisor
Homework Helper
25,832
251
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). :smile:
 

Related Threads on Power set / surjection

  • Last Post
Replies
1
Views
932
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
2
Views
826
  • Last Post
Replies
4
Views
396
  • Last Post
Replies
1
Views
734
  • Last Post
Replies
1
Views
3K
Replies
1
Views
1K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
3
Views
488
Top