Is an arbitrary union of a chain of countable sets countable?

Clash Royale CLAN TAG#URR8PPP

up vote
2
down vote

favorite

Let $C$ be a chain of countable sets, i.e. $forall S, T in C: S subseteq T lor T subseteq S$, and that every $S in C$ is countable.

Then, is $bigcup C := t mid exists S in C: t in S$ countable?

The answer is no, and a counter-example is $C = omega_1$, the first uncountable cardinal/ordinal.

Is there a more elementary example that doesn't involve, say, cardinals and ordinals?

set-theory

share|cite|improve this question

edited Jul 31 at 7:00

Asaf Karagila

291k31401731

asked Jul 31 at 6:20

Kenny Lau

17.7k2156

add a comment | 

up vote
2
down vote

favorite

Let $C$ be a chain of countable sets, i.e. $forall S, T in C: S subseteq T lor T subseteq S$, and that every $S in C$ is countable.

Then, is $bigcup C := t mid exists S in C: t in S$ countable?

The answer is no, and a counter-example is $C = omega_1$, the first uncountable cardinal/ordinal.

Is there a more elementary example that doesn't involve, say, cardinals and ordinals?

set-theory

share|cite|improve this question

edited Jul 31 at 7:00

Asaf Karagila

291k31401731

asked Jul 31 at 6:20

Kenny Lau

17.7k2156

add a comment | 

up vote
2
down vote

favorite

up vote
2
down vote

favorite

Let $C$ be a chain of countable sets, i.e. $forall S, T in C: S subseteq T lor T subseteq S$, and that every $S in C$ is countable.

Then, is $bigcup C := t mid exists S in C: t in S$ countable?

The answer is no, and a counter-example is $C = omega_1$, the first uncountable cardinal/ordinal.

Is there a more elementary example that doesn't involve, say, cardinals and ordinals?

set-theory

share|cite|improve this question

edited Jul 31 at 7:00

Asaf Karagila

291k31401731

asked Jul 31 at 6:20

Kenny Lau

17.7k2156

Let $C$ be a chain of countable sets, i.e. $forall S, T in C: S subseteq T lor T subseteq S$, and that every $S in C$ is countable.

Then, is $bigcup C := t mid exists S in C: t in S$ countable?

The answer is no, and a counter-example is $C = omega_1$, the first uncountable cardinal/ordinal.

Is there a more elementary example that doesn't involve, say, cardinals and ordinals?

set-theory

share|cite|improve this question

edited Jul 31 at 7:00

Asaf Karagila

291k31401731

asked Jul 31 at 6:20

Kenny Lau

17.7k2156

share|cite|improve this question

share|cite|improve this question

edited Jul 31 at 7:00

Asaf Karagila

291k31401731

edited Jul 31 at 7:00

Asaf Karagila

291k31401731

edited Jul 31 at 7:00

Asaf Karagila

291k31401731

291k31401731

asked Jul 31 at 6:20

Kenny Lau

17.7k2156

asked Jul 31 at 6:20

Kenny Lau

17.7k2156

asked Jul 31 at 6:20

Kenny Lau

17.7k2156

17.7k2156

add a comment | 

add a comment | 

1 Answer
1

active

oldest

votes

up vote
4
down vote



accepted

If you wish to assume choice, then you have no way around $omega_1$. The reason being that any chain has a well-ordered cofinal subset, and thus if all the members of the chain are countable that subset has to be countable or of type $omega_1$. In the former case the union of the chain is countable, and in the latter it will be of size $aleph_1$.

But what happens without assuming the axiom of choice? Well. It is consistent that $Bbb R$ is a countable union of countable sets, or that you have a Russell set, that is a countable union of pairwise disjoint pairs that admit no choice function.

In any such case, you have $A_nmid n<omega$ as a countable family of countable sets (in the Russell set case, finite), then defining $B_n=bigcup_k<nA_n$ gives you that $B_nmid n<omega$ is a countable chain of countable sets whose union is uncountable.

share|cite|improve this answer

edited Jul 31 at 7:09

answered Jul 31 at 6:40

Asaf Karagila

291k31401731

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Doesn't my counter-example hold in ZF?
  – Kenny Lau
  Jul 31 at 6:41
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  It doesn't have to be a countable chain.
  – Lord Shark the Unknown
  Jul 31 at 6:50
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @LordSharktheUnknown: Early morning... :P
  – Asaf Karagila
  Jul 31 at 7:00
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Kenny: Yes, you're right. I've edited to reflect that.
  – Asaf Karagila
  Jul 31 at 7:03
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Why is $omega_1$ a union of a countable chain?
  – Kenny Lau
  Jul 31 at 7:04
  

  
  
  
  

 | 
show 5 more comments

Your Answer

StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
);
);
, "mathjax-editing");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: true,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2867719%2fis-an-arbitrary-union-of-a-chain-of-countable-sets-countable%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
4
down vote



accepted

If you wish to assume choice, then you have no way around $omega_1$. The reason being that any chain has a well-ordered cofinal subset, and thus if all the members of the chain are countable that subset has to be countable or of type $omega_1$. In the former case the union of the chain is countable, and in the latter it will be of size $aleph_1$.

But what happens without assuming the axiom of choice? Well. It is consistent that $Bbb R$ is a countable union of countable sets, or that you have a Russell set, that is a countable union of pairwise disjoint pairs that admit no choice function.

In any such case, you have $A_nmid n<omega$ as a countable family of countable sets (in the Russell set case, finite), then defining $B_n=bigcup_k<nA_n$ gives you that $B_nmid n<omega$ is a countable chain of countable sets whose union is uncountable.

share|cite|improve this answer

edited Jul 31 at 7:09

answered Jul 31 at 6:40

Asaf Karagila

291k31401731

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Doesn't my counter-example hold in ZF?
  – Kenny Lau
  Jul 31 at 6:41
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  It doesn't have to be a countable chain.
  – Lord Shark the Unknown
  Jul 31 at 6:50
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @LordSharktheUnknown: Early morning... :P
  – Asaf Karagila
  Jul 31 at 7:00
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Kenny: Yes, you're right. I've edited to reflect that.
  – Asaf Karagila
  Jul 31 at 7:03
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Why is $omega_1$ a union of a countable chain?
  – Kenny Lau
  Jul 31 at 7:04
  

  
  
  
  

 | 
show 5 more comments

up vote
4
down vote



accepted

If you wish to assume choice, then you have no way around $omega_1$. The reason being that any chain has a well-ordered cofinal subset, and thus if all the members of the chain are countable that subset has to be countable or of type $omega_1$. In the former case the union of the chain is countable, and in the latter it will be of size $aleph_1$.

But what happens without assuming the axiom of choice? Well. It is consistent that $Bbb R$ is a countable union of countable sets, or that you have a Russell set, that is a countable union of pairwise disjoint pairs that admit no choice function.

In any such case, you have $A_nmid n<omega$ as a countable family of countable sets (in the Russell set case, finite), then defining $B_n=bigcup_k<nA_n$ gives you that $B_nmid n<omega$ is a countable chain of countable sets whose union is uncountable.

share|cite|improve this answer

edited Jul 31 at 7:09

answered Jul 31 at 6:40

Asaf Karagila

291k31401731

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Doesn't my counter-example hold in ZF?
  – Kenny Lau
  Jul 31 at 6:41
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  It doesn't have to be a countable chain.
  – Lord Shark the Unknown
  Jul 31 at 6:50
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @LordSharktheUnknown: Early morning... :P
  – Asaf Karagila
  Jul 31 at 7:00
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Kenny: Yes, you're right. I've edited to reflect that.
  – Asaf Karagila
  Jul 31 at 7:03
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Why is $omega_1$ a union of a countable chain?
  – Kenny Lau
  Jul 31 at 7:04
  

  
  
  
  

 | 
show 5 more comments

up vote
4
down vote



accepted

up vote
4
down vote



accepted

If you wish to assume choice, then you have no way around $omega_1$. The reason being that any chain has a well-ordered cofinal subset, and thus if all the members of the chain are countable that subset has to be countable or of type $omega_1$. In the former case the union of the chain is countable, and in the latter it will be of size $aleph_1$.

But what happens without assuming the axiom of choice? Well. It is consistent that $Bbb R$ is a countable union of countable sets, or that you have a Russell set, that is a countable union of pairwise disjoint pairs that admit no choice function.

In any such case, you have $A_nmid n<omega$ as a countable family of countable sets (in the Russell set case, finite), then defining $B_n=bigcup_k<nA_n$ gives you that $B_nmid n<omega$ is a countable chain of countable sets whose union is uncountable.

share|cite|improve this answer

edited Jul 31 at 7:09

answered Jul 31 at 6:40

Asaf Karagila

291k31401731

If you wish to assume choice, then you have no way around $omega_1$. The reason being that any chain has a well-ordered cofinal subset, and thus if all the members of the chain are countable that subset has to be countable or of type $omega_1$. In the former case the union of the chain is countable, and in the latter it will be of size $aleph_1$.

But what happens without assuming the axiom of choice? Well. It is consistent that $Bbb R$ is a countable union of countable sets, or that you have a Russell set, that is a countable union of pairwise disjoint pairs that admit no choice function.

In any such case, you have $A_nmid n<omega$ as a countable family of countable sets (in the Russell set case, finite), then defining $B_n=bigcup_k<nA_n$ gives you that $B_nmid n<omega$ is a countable chain of countable sets whose union is uncountable.

share|cite|improve this answer

edited Jul 31 at 7:09

answered Jul 31 at 6:40

Asaf Karagila

291k31401731

share|cite|improve this answer

share|cite|improve this answer

edited Jul 31 at 7:09

edited Jul 31 at 7:09

edited Jul 31 at 7:09

answered Jul 31 at 6:40

Asaf Karagila

291k31401731

answered Jul 31 at 6:40

Asaf Karagila

291k31401731

answered Jul 31 at 6:40

Asaf Karagila

291k31401731

291k31401731

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Doesn't my counter-example hold in ZF?
  – Kenny Lau
  Jul 31 at 6:41
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  It doesn't have to be a countable chain.
  – Lord Shark the Unknown
  Jul 31 at 6:50
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @LordSharktheUnknown: Early morning... :P
  – Asaf Karagila
  Jul 31 at 7:00
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Kenny: Yes, you're right. I've edited to reflect that.
  – Asaf Karagila
  Jul 31 at 7:03
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Why is $omega_1$ a union of a countable chain?
  – Kenny Lau
  Jul 31 at 7:04
  

  
  
  
  

 | 
show 5 more comments

• 
  
  
  

  
  

  
  
  
  
  
  

  
  Doesn't my counter-example hold in ZF?
  – Kenny Lau
  Jul 31 at 6:41
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  It doesn't have to be a countable chain.
  – Lord Shark the Unknown
  Jul 31 at 6:50
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @LordSharktheUnknown: Early morning... :P
  – Asaf Karagila
  Jul 31 at 7:00
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  @Kenny: Yes, you're right. I've edited to reflect that.
  – Asaf Karagila
  Jul 31 at 7:03
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  Why is $omega_1$ a union of a countable chain?
  – Kenny Lau
  Jul 31 at 7:04
  

  
  
  
  

Doesn't my counter-example hold in ZF?
– Kenny Lau
Jul 31 at 6:41

Doesn't my counter-example hold in ZF?
– Kenny Lau
Jul 31 at 6:41

It doesn't have to be a countable chain.
– Lord Shark the Unknown
Jul 31 at 6:50

It doesn't have to be a countable chain.
– Lord Shark the Unknown
Jul 31 at 6:50

@LordSharktheUnknown: Early morning... :P
– Asaf Karagila
Jul 31 at 7:00

@LordSharktheUnknown: Early morning... :P
– Asaf Karagila
Jul 31 at 7:00

@Kenny: Yes, you're right. I've edited to reflect that.
– Asaf Karagila
Jul 31 at 7:03

@Kenny: Yes, you're right. I've edited to reflect that.
– Asaf Karagila
Jul 31 at 7:03

Why is $omega_1$ a union of a countable chain?
– Kenny Lau
Jul 31 at 7:04

Why is $omega_1$ a union of a countable chain?
– Kenny Lau
Jul 31 at 7:04

 | 
show 5 more comments

 

draft saved

draft discarded

 

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2867719%2fis-an-arbitrary-union-of-a-chain-of-countable-sets-countable%23new-answer', 'question_page');

);

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email