Power sets and cardinalities (proof)

  • Thread starter Thread starter TheFacemore
  • Start date Start date
  • Tags Tags
    Power Proof Sets
AI Thread Summary
The discussion centers on proving that there is no surjective function from a set A to its power set P(A). It begins by defining a set U that contains elements of A not mapped to by the function phi. The contradiction arises when considering whether the element u, which maps to U, is itself in U. This leads to the conclusion that the cardinality of A is less than that of P(A), highlighting the fundamental difference in their sizes. The conversation reflects on the implications of this proof and the nature of set functions.
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?
 

Thread 'Greatest possible value of a constant in polynomial'

Since ##px^9+q## is the factor, then ##x^9=\frac{-q}{p}## will be one of the roots. Let ##f(x)=27x^{18}+bx^9+70##, then: $$27\left(\frac{-q}{p}\right)^2+b\left(\frac{-q}{p}\right)+70=0$$ $$b=27 \frac{q}{p}+70 \frac{p}{q}$$ $$b=\frac{27q^2+70p^2}{pq}$$ From this expression, it looks like there is no greatest value of ##b## because increasing the value of ##p## and ##q## will also increase the value of ##b##. How to find the greatest value of ##b##? Thanks
View full post »

Similar threads

I Question about "A Group Epimorphism is Surjective"
Replies
13
Views
696
Proof about two disjoint non-empty sets ## S ## and ## T ##
Replies
11
Views
2K
MHB Is Φ a Bijective Map from Power Set to Characteristic Functions?
Replies
7
Views
2K
Various Intuitions and Conceptualizations of Measurable Cardinals.
Replies
0
Views
3K
Alternator torque when connected to a phase-shifted AC source
Replies
3
Views
2K
Deriving the Matrix for a 3 dimensional rotation
Replies
9
Views
3K
I Homemorphism in quotient topology
Replies
5
Views
659
What Is the Cardinality of Nested Power Sets?
Replies
5
Views
6K
Transform General EQ Acos(wt)+Bsin(wt)
Replies
3
Views
18K
Ellipse chord subtending a right angle
Replies
3
Views
2K

Hot Threads

Recent Insights

Back
Top