Onto Mappings from a Set to Its Power Set

Click For Summary
SUMMARY

This discussion centers on proving that there are no onto mappings from a set S to its power set S*. The proof employs a contradiction approach, utilizing Cantor's diagonal argument. By defining a subset B of S that contradicts the mapping f, it is established that for any element x in S, the mapping cannot be onto, as it leads to a logical contradiction. Thus, the conclusion is that such a mapping f cannot exist.

PREREQUISITES
  • Understanding of set theory and power sets
  • Familiarity with proof by contradiction
  • Knowledge of Cantor's diagonal argument
  • Basic concepts of functions and mappings in mathematics
NEXT STEPS
  • Study the implications of Cantor's theorem on set sizes
  • Explore other proofs of non-existence of onto mappings in set theory
  • Learn about different types of functions, specifically injective and surjective mappings
  • Investigate advanced topics in set theory, such as cardinality and ordinal numbers
USEFUL FOR

Mathematicians, students studying set theory, and anyone interested in understanding the foundations of mathematical logic and functions.

e(ho0n3
Messages
1,349
Reaction score
0
Homework Statement
Prove that there are no mappings from a set S onto S*, where S* is the power set of S.

The attempt at a solution
This begs proof by contradiction: Let f be a mapping from S onto S*. Then for every A in S*, there is an a in S with f(a) = A. I don't know how to proceed from here. Any tips?
 
Physics news on Phys.org
Can you construct a subset of S (call it B) that is different from all of the other subsets f(a)? Hint: a is either in f(a) or not in f(a). Whichever it is, make B the opposite. Think 'Cantor diagonal'.
 
Hmm...let B = {a in S : a not in f(a)}. B belongs to S* and since f is onto there must be an x in S for which f(x) = B.

I guess I should now ask if x is in B? Suppose it is. Then x is not in f(x) = B. Contradiction. If x is not in B, then x is in f(x) = B. Contradiction. Hence, f can't be onto.

Thanks a lot!
 

Similar threads

Prove every subset of countable set is either finite or else countable
  • · Replies 1 ·
Replies
1
Views
2K
Prove Set of all onto mappings from A->A is closed
  • · Replies 6 ·
Replies
6
Views
2K
Show that a set has no "unique nearest point" property
  • · Replies 14 ·
Replies
14
Views
2K
|Orbit(s)| = |G| when action is fixed-point free
  • · Replies 1 ·
Replies
1
Views
2K
Universal Mapping Property of Free Groups: Definition and Proof
  • · Replies 4 ·
Replies
4
Views
2K
Set of least upper bounds multiplied by a constant
  • · Replies 1 ·
Replies
1
Views
1K
Null space of dual map of T = annihilator of range T
  • · Replies 1 ·
Replies
1
Views
3K
Topology by Simmons Problem 1.3.3
  • · Replies 3 ·
Replies
3
Views
1K
A Set in the plane is never isometric to a proper subset
  • · Replies 11 ·
Replies
11
Views
2K
Show that if U and T are onto, then UT is also onto
  • · Replies 5 ·
Replies
5
Views
2K