My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Thanks Tree3Thanks
  • 1 Post By Maschke
  • 1 Post By Maschke
  • 1 Post By Maschke
Reply
 
LinkBack Thread Tools Display Modes
April 12th, 2017, 06:15 PM   #1
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 308
Thanks: 21

Countable Union of Countable Sets Question

I am hoping for a better understanding of what a countable union of countable sets means.

I have noted that Feferman and Levy famously showed that the reals can be a countable union of countable sets long ago. We can also have an uncountable set that is the countable union of sets of size two (e.g., Russell cardinals). I understand that the axiom of choice plays into this (it fails in Feferman and Levy's model noted above) and in ZFC the well ordering theorem is implied which in turn requires that each cardinal have an initial ordinal.

I get that choice may be needed to have an enumeration of each countable set in a countable union. To clarify, if an enumeration is given for each countable set, then an enumeration of their union can be constructed. Alternatively, if no such enumeration is given for each countable set, then choice can be used to select an enumeration instead.

What I don't understand is that, where the reals are not countable and neither is $w_1$, how can the reals be a countable union of countable sets?

A layman's explanation is the best I'll be able to understand... I'm no math whiz.

Thank you!
AplanisTophet is offline  
 
April 12th, 2017, 07:42 PM   #2
Senior Member
 
Joined: Aug 2012

Posts: 1,571
Thanks: 379

Quote:
Originally Posted by AplanisTophet View Post
I am hoping for a better understanding of what a countable union of countable sets means.

I have noted that Feferman and Levy famously showed that the reals can be a countable union of countable sets long ago. We can also have an uncountable set that is the countable union of sets of size two (e.g., Russell cardinals). I understand that the axiom of choice plays into this (it fails in Feferman and Levy's model noted above) and in ZFC the well ordering theorem is implied which in turn requires that each cardinal have an initial ordinal.

I get that choice may be needed to have an enumeration of each countable set in a countable union. To clarify, if an enumeration is given for each countable set, then an enumeration of their union can be constructed. Alternatively, if no such enumeration is given for each countable set, then choice can be used to select an enumeration instead.

What I don't understand is that, where the reals are not countable and neither is $w_1$, how can the reals be a countable union of countable sets?

A layman's explanation is the best I'll be able to understand... I'm no math whiz.

Thank you!
Let me give you a short slightly meta answer.

I Googled Feferman-Levy and found this Stackexchange thread. This is advanced set theory. Unless you happen to be knowledgeable in the modern set-theoretic technique of forcing, you can't even begin to understand the statement of the theorem. I have just barely enough knowledge to know exactly what I'd need to do in order to grok that Stackexchange thread: Spend a year reading Kunen and Jech, and working at it. In another universe some version of me is doing exactly that. I take comfort in that thought.

But what this is all about is basically alternate models of the real numbers. Just as Euclidean and non-Eucidean geometry are each models of Euclid's axioms minus the parallel postulate; in the same way, there can be many different models of set theory and the real numbers.

You may recall that Gödel showed that the axiom of choice and the Continuum hypothesis were consistent with the rest of set theory back in 1934 or so.

Then in 1964 Paul Cohen showed that their negations were consistent as well. In so doing, he cooked up a model of the axioms in which they were false.

But that wasn't the most important thing he did. His real achievement was to show how to "cook up" wild models of set theory in order to study independence results. He invented the technique of forcing.

Today, forcing is highly abstract and set theorists casually talk about this type of forcing and that type of forcing.

This is some of the background material to read that Stackexchange thread.

Now the point - and I did promise this would be short -- is that they cooked up a crazy model of set theory in which the real numbers, defined in the usual way but with respect to crazy set theory and not usual set theory, happen to be a countable union of countable sets.

The purpose of cooking up a model like this is to show that even though the axiom of choice is considered weird and troublesome, without it things are weird and troublesome too. That's why people study this stuff.

I hope this is helpful. Tell me if this is the kind of answer you had in mind. Just think non-Euclidean geometry, it's the same thing but for set theory.

On the other hand if I got this wrong and you're an expert on this stuff and asking a highly technical question, my apologies, but in that case you should try this out on Stackexchange. They have professional set theorists there, it's incredible what they know.
Thanks from AplanisTophet

Last edited by Maschke; April 12th, 2017 at 07:57 PM.
Maschke is online now  
April 12th, 2017, 08:04 PM   #3
Senior Member
 
Joined: Aug 2012

Posts: 1,571
Thanks: 379

ps -- I put this in a separate post because it's a different answer, shorter and more to the point.

Nobody said the reals are countable in this model. In fact the reals are always uncountable, that's a theorem of ZF. It's Cantor's theorem. No Choice needed.

The theorem that fails is that a countable union of countable sets is countable. That actually requires Choice. That's not commonly realized.

In the usual "snaking diagonals" proof of the countability of the rationals, we don't need choice. That's because we can define an explicit order on the rationals.

But in general, here is the problem. Suppose I have a countable collection of countable sets. Since each set is countable, there is a nonempty set of bijections between that set and the positive integers. We know there's at least one, but in fact there may be many.

So now ... to get the snaking idea to work, we have to choose a bijection from each of infinitely many nonempty sets! Bam, we just used at least countable choice. That's weaker than full Choice but stronger than ZF.

elementary set theory - Prove that the union of countably many countable sets is countable. - Mathematics Stack Exchange

So in the absence of Choice, we should expect that there's a countable union of countable sets that's not countable. Because we can see that we made essential use of countable Choice to prove that a countable union is countable.

So in this funny model of set theory, the reals are uncountable AND they are a countable union of countable sets.

I hope this answer helps too!
Thanks from AplanisTophet

Last edited by Maschke; April 12th, 2017 at 08:07 PM.
Maschke is online now  
April 13th, 2017, 05:50 PM   #4
Senior Member
 
Joined: Jun 2014
From: USA

Posts: 308
Thanks: 21

Quote:
Originally Posted by Maschke View Post
Let me give you a short slightly meta answer.

I Googled Feferman-Levy and found this Stackexchange thread. This is advanced set theory. ... Spend a year reading Kunen and Jech, and working at it. In another universe some version of me is doing exactly that. I take comfort in that thought.
Yes, those papers are beyond me, ... well, in this universe anyways. Point well taken though.

Quote:
Originally Posted by Maschke View Post
You may recall that Gödel showed that the axiom of choice and the Continuum hypothesis were consistent with the rest of set theory back in 1934 or so.

Then in 1964 Paul Cohen showed that their negations were consistent as well. In so doing, he cooked up a model of the axioms in which they were false.

But that wasn't the most important thing he did. His real achievement was to show how to "cook up" wild models of set theory in order to study independence results.

...

The purpose of cooking up a model like this is to show that even though the axiom of choice is considered weird and troublesome, without it things are weird and troublesome too. That's why people study this stuff.

I hope this is helpful.

That helps to put it into perspective, yes. I find it fascinating that something as simple as the axiom of choice can be so powerful.


Quote:
Originally Posted by Maschke View Post
Nobody said the reals are countable in this model. In fact the reals are always uncountable, that's a theorem of ZF. It's Cantor's theorem. No Choice needed.

The theorem that fails is that a countable union of countable sets is countable. That actually requires Choice. That's not commonly realized.
So if choice is included, then the model in which the reals are a countable union of countable sets falls apart. If it is not, then the reals may be a countable union of countable sets but there is no way to enumerate them nevertheless.


Quote:
Originally Posted by Maschke View Post
elementary set theory - Prove that the union of countably many countable sets is countable. - Mathematics Stack Exchange

So in the absence of Choice, we should expect that there's a countable union of countable sets that's not countable. Because we can see that we made essential use of countable Choice to prove that a countable union is countable.

So in this funny model of set theory, the reals are uncountable AND they are a countable union of countable sets.

I hope this answer helps too!
Yes, that is a nice link and explanation of why at least some choice is needed.

I think the necessary 'piece' for my understanding is that the reals cannot be expressed as a countable union of countable sets in any model where choice holds true, which I assume to be the obvious case because, if they could be expressed as such in a model where choice holds up, then they would have to be enumerable. Sound correct?
AplanisTophet is offline  
April 13th, 2017, 06:11 PM   #5
Senior Member
 
Joined: Aug 2012

Posts: 1,571
Thanks: 379

Quote:
Originally Posted by AplanisTophet View Post
I think the necessary 'piece' for my understanding is that the reals cannot be expressed as a countable union of countable sets in any model where choice holds true, which I assume to be the obvious case because, if they could be expressed as such in a model where choice holds up, then they would have to be enumerable. Sound correct?
Yes exactly. Glad my posts were helpful. The reals are uncountable in any model. That's because we can prove Cantor's theorem in ZF (a set has strictly smaller cardinality than its powerset); and likewise we can prove in ZF that the reals are equinumerous with the powerset of the naturals (via binary sequences for example).

On the other hand, the theorem that a countable union of countable sets is countable depends in a subtle way (usually not mentioned) on countable choice.

So in this funny model (funny odd not funny haha), the reals are still uncountable, but they're a countable union of countable sets.

It's often claimed that because the axiom of choice leads to weird results, we should reject it. It's not commonly realized that its absence leads to equally weird results.
Thanks from AplanisTophet

Last edited by Maschke; April 13th, 2017 at 06:16 PM.
Maschke is online now  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
countable, question, sets, union



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Countable and uncountable sets Loren Number Theory 32 September 12th, 2016 10:09 AM
Countable Union proof jstarks4444 Applied Math 1 May 13th, 2011 08:15 AM
Sets, Countable and Uncountable Bernie Applied Math 3 September 9th, 2009 01:28 AM
I have another one, Countable sets. Fra Algebra 5 February 14th, 2008 04:04 PM
Countable Union proof jstarks4444 Number Theory 1 December 31st, 1969 04:00 PM





Copyright © 2017 My Math Forum. All rights reserved.