Power sets and cardinalities (proof)

  • Thread starter Thread starter TheFacemore
  • Start date Start date
  • Tags Tags
    Power Proof Sets
Click For Summary

Homework Help Overview

The problem involves demonstrating that there cannot be a surjective function from a set A to its power set P(A). The discussion centers around the implications of this assertion on the cardinalities of A and P(A).

Discussion Character

  • Conceptual clarification, Assumption checking

Approaches and Questions Raised

  • Participants explore the implications of the assumption that phi is a surjection and consider the set U defined in relation to phi. Questions arise regarding the relationship between the element u and the set U, particularly whether u belongs to U.

Discussion Status

The discussion is ongoing, with participants questioning the reasoning behind the contradiction that arises from the assumption. There is a focus on clarifying the implications of the definitions and assumptions involved.

Contextual Notes

Participants are navigating the constraints of the problem, particularly regarding the definitions of surjective functions and the properties of power sets. There is an acknowledgment of a hint provided, which some participants are interpreting differently.

TheFacemore
Messages
2
Reaction score
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
Okay, so how does "phi(u)= U" lead to a contradiction?
 
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.
 
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

  • · Replies 13 ·
Replies
13
Views
2K
  • · Replies 11 ·
Replies
11
Views
3K
  • · Replies 7 ·
Replies
7
Views
2K
Replies
0
Views
3K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 9 ·
Replies
9
Views
3K
  • · Replies 5 ·
Replies
5
Views
2K
  • · Replies 5 ·
Replies
5
Views
6K
  • · Replies 3 ·
Replies
3
Views
18K
  • · Replies 3 ·
Replies
3
Views
2K