My Math Forum Surjection, Uncountable Set

 Applied Math Applied Math Forum

 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 $\mathcal{P}(\mathbb{N})$ onto $\omega_1$. Notation: $\omega_1$ 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, 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.
 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 $\omega_1$ into $\mathcal{P}(\mathbb{N})$.
 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.
 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 $\omega_1$, 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, 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 $\omega_1$, 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.

 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 $|\mathcal{P}(\mathbb{N})| > |\mathbb{N}|$ (because it's a power set, nothing special about the natural numbers). Now suppose that $|\mathcal{P}(\mathbb{N})| < |\omega_1|$. From our prior observation we know that $\mathcal{P}(\mathbb{N})$ is uncountable, and by assumption $\omega_1$ is a set of smallest uncountable cardinality; we have a contradiction here and may conclude $|\mathcal{P}(\mathbb{N})| \geq |\omega_1|$. It follows immediately that there is a surjection.
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 $|\mathcal{P}(\mathbb{N})| > |\mathbb{N}|$ (because it's a power set, nothing special about the natural numbers). Now suppose that $|\mathcal{P}(\mathbb{N})| < |\omega_1|$. From our prior observation we know that $\mathcal{P}(\mathbb{N})$ is uncountable, and by assumption $\omega_1$ is a set of smallest uncountable cardinality; we have a contradiction here and may conclude $|\mathcal{P}(\mathbb{N})| \geq |\omega_1|$. It follows immediately that there is a surjection.
You need cardinal comparability for this (equivalent to AC).

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.

 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 $\mathscr{P}(\mathbb{N})\not < \omega_1$ to $\mathscr{P}(\mathbb{N})\geq \omega_1$ 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 $\omega_1$ to $\mathscr{P}(\mathbb{N})$ to imply a surjection $\mathscr{P}(\mathbb{N})$ to $\omega_1$. 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 Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post zelmac Real Analysis 3 October 26th, 2013 11:33 PM jstarks4444 Applied Math 2 January 12th, 2012 12:45 PM whatlifeforme Number Theory 1 October 30th, 2011 04:53 AM jstarks4444 Number Theory 0 December 31st, 1969 04:00 PM jstarks4444 Number Theory 0 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top