March 6th, 2010, 03:00 PM  #1 
Newbie Joined: Mar 2009 Posts: 7 Thanks: 0  Surjection, Uncountable Set
Prove that there exists a surjection from onto . Notation: denotes the first uncountable ordinal. The solution may have some aspects in common with the proof of Hartog’s theroem. [we may not use the Axiom of Choice] 
March 6th, 2010, 03:47 PM  #2 
Senior Member Joined: Nov 2008 Posts: 199 Thanks: 0  Re: Surjection, Uncountable Set
This is not true in general for arbitrary uncountable sets.

March 6th, 2010, 03:50 PM  #3 
Newbie Joined: Mar 2009 Posts: 7 Thanks: 0  Re: Surjection, Uncountable Set
Why is that? This I know there is no bijection, but there should be a surjection. I know it takes some form of the Axiom of Choice to prove that there exists an injection from into .

March 6th, 2010, 05:38 PM  #4 
Senior Member Joined: Nov 2008 Posts: 199 Thanks: 0  Re: Surjection, Uncountable Set
Did you edit your original post to change 'uncountable set' to 'first uncountable ordinal' or did I just misread it the first time? In any case, with this interpretation of w_1 the theorem sounds true after all. As it stands I can't see a way to do it without AC but I'll let you know if I think of anything.

March 10th, 2010, 11:27 PM  #5 
Senior Member Joined: Oct 2007 From: Chicago Posts: 1,701 Thanks: 3  Re: Surjection, Uncountable Set
The first thought off the top of my head is to find a bijection from some subset of P(N) to , and send everything else to 0... Of course, while this seems like it should be easy, I'm not quite seeing how to do it.

March 11th, 2010, 02:08 AM  #6  
Senior Member Joined: Nov 2008 Posts: 199 Thanks: 0  Re: Surjection, Uncountable Set Quote:
If there's a bijection from some subset S of P(N) with cardinality of S strictly less than that of P(N) you'll disprove the continuum hypothesis. If the S is equal in cardinality with P(N) you'll have proved the continuum hypothesis. Both of these are impossible in ZFC so the only option would be a bijection between a subset of P(N) the question of whose cardinality is not fully resolvable in ZFC. This sounds to me like quite a difficult thing to construct and makes me think this method may not be the way to go.  
March 11th, 2010, 03:17 AM  #7 
Senior Member Joined: Jan 2009 From: Japan Posts: 192 Thanks: 0  Re: Surjection, Uncountable Set
Start with the observation that (because it's a power set, nothing special about the natural numbers). Now suppose that . From our prior observation we know that is uncountable, and by assumption is a set of smallest uncountable cardinality; we have a contradiction here and may conclude . It follows immediately that there is a surjection. 
March 11th, 2010, 03:23 AM  #8  
Senior Member Joined: Nov 2008 Posts: 199 Thanks: 0  Re: Surjection, Uncountable Set Quote:
 
March 11th, 2010, 03:51 AM  #9  
Senior Member Joined: Jan 2009 From: Japan Posts: 192 Thanks: 0  Re: Surjection, Uncountable Set Quote:
 
March 11th, 2010, 04:16 AM  #10 
Senior Member Joined: Nov 2008 Posts: 199 Thanks: 0  Re: Surjection, Uncountable Set
I may well be missing something but I don't see how you can use antisymmetry to get from to without appealing to CC. With CC it is of course obvious but without it there is no reason for the lack of an injection from to to imply a surjection to . Without CC we can't assume the existence of any surjections or injections at all between general uncountable sets, only between ordinals. Without CC the smallest uncountable ordinal is not the smallest uncountable set.


Tags 
set, surjection, uncountable 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Surjection question  zelmac  Real Analysis  3  October 27th, 2013 12:33 AM 
Transitive Surjection proof  jstarks4444  Applied Math  2  January 12th, 2012 01:45 PM 
Uncountable  whatlifeforme  Number Theory  1  October 30th, 2011 05:53 AM 
Injection implied by Surjection  jstarks4444  Number Theory  0  December 31st, 1969 04:00 PM 
Transitive Surjection proof  jstarks4444  Number Theory  0  December 31st, 1969 04:00 PM 