My Math Forum  

Go Back   My Math Forum > College Math Forum > Applied Math

Applied Math Applied Math Forum


Reply
 
LinkBack Thread Tools Display Modes
March 6th, 2010, 02: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]
vaevictis59 is offline  
 
March 6th, 2010, 02: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.
pseudonym is offline  
March 6th, 2010, 02: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 .
vaevictis59 is offline  
March 6th, 2010, 04: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.
pseudonym is offline  
March 10th, 2010, 10: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.
cknapp is offline  
March 11th, 2010, 01:08 AM   #6
Senior Member
 
Joined: Nov 2008

Posts: 199
Thanks: 0

Re: Surjection, Uncountable Set

Quote:
Originally Posted by cknapp
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.

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.
pseudonym is offline  
March 11th, 2010, 02: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.
cmusick is offline  
March 11th, 2010, 02:23 AM   #8
Senior Member
 
Joined: Nov 2008

Posts: 199
Thanks: 0

Re: Surjection, Uncountable Set

Quote:
Originally Posted by cmusick
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.
You need cardinal comparability for this (equivalent to AC).
pseudonym is offline  
March 11th, 2010, 02:51 AM   #9
Senior Member
 
Joined: Jan 2009
From: Japan

Posts: 192
Thanks: 0

Re: Surjection, Uncountable Set

Quote:
Originally Posted by pseudonym
You need cardinal comparability for this (equivalent to AC).
You need AC for trichotomy, but not for anti-symmetry. Take a look at http://en.wikipedia.org/wiki/Cantor%E2% ... er_theorem for a sketch of the proof of anti-symmetry without AC.
cmusick is offline  
March 11th, 2010, 03: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.
pseudonym is offline  
Reply

  My Math Forum > College Math Forum > Applied Math

Tags
set, surjection, uncountable



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Surjection question zelmac Real Analysis 3 October 26th, 2013 11:33 PM
Transitive Surjection proof jstarks4444 Applied Math 2 January 12th, 2012 12:45 PM
Uncountable whatlifeforme Number Theory 1 October 30th, 2011 04: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





Copyright © 2018 My Math Forum. All rights reserved.