Power sets and cardinalities (proof)

  • #1
TheFacemore
2
0

Homework Statement



Let A be a set. Show that there is no surjective function phi: A --> P(A), where P(A) is the power set of A. What does this say about the cardinalities of A and P(A)?

Homework Equations


Assume that phi is a surjection of A onto P(A) and consider the set U= {a in A : a not in phi(a)} of A. Since phi is a surjection there must be a u in A satisfying phi(u)=U.


The Attempt at a Solution

 
Physics news on Phys.org
  • #2
Okay, so how does "phi(u)= U" lead to a contradiction?
 
  • #3
TheFacemore said:
Assume that phi is a surjection of A onto P(A) and consider the set U= {a in A : a not in phi(a)} of A. Since phi is a surjection there must be a u in A satisfying phi(u)=U.

That's not an effort, that is the hint that was given.
Anyway, think about whether u is an element of U.
 
  • #4
From those 2 replies i feel as if I am trying to overthink this problem. Is it that u does not need to be an element of U but it has to be an element of A? or something to that extent?
 

Similar threads

Back
Top