Author 
Topic: Uncountable "chain" of subsets? (Read 4041 times) 

Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Uncountable "chain" of subsets?
« on: Mar 29^{th}, 2008, 10:50pm » 
Quote Modify

Let X be a countable set. Let F be a family of distinct subsets of X such that for any A, B in F, either A is subset of B or B is a subset of A. Prove/Disprove: We can find such an X and an F having the above property such that F is uncountable.


IP Logged 



Grimbal
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 7527


Re: Uncountable "chain" of subsets?
« Reply #1 on: Mar 30^{th}, 2008, 2:06pm » 
Quote Modify

This reminds me of the relation between Q and R.


IP Logged 



Obob
Senior Riddler
Gender:
Posts: 489


Re: Uncountable "chain" of subsets?
« Reply #2 on: Mar 30^{th}, 2008, 4:10pm » 
Quote Modify

Very nice, Grimbal! I spent a while last night trying to show F was countable. Its a good thing I didn't succeed!


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Uncountable "chain" of subsets?
« Reply #3 on: Mar 31^{st}, 2008, 11:30am » 
Quote Modify

Yup! We can find F such that it is uncountable.


IP Logged 



Obob
Senior Riddler
Gender:
Posts: 489


Re: Uncountable "chain" of subsets?
« Reply #4 on: Mar 31^{st}, 2008, 12:42pm » 
Quote Modify

And its nice that F isn't pathological either; it is in fact the fundamental construction for all of analysis. For anybody who doesn't know what we're talking about, the idea is to let X be the rational numbers, and let F be the set of all "Dedekind cuts": we let the subset A be in F if (1) A has no greatest element and (2) If y is in A and x < y, then x is in A. Then F can be naturally identified with the set of real numbers (or, depending on your definition of the real numbers, it is the real numbers). So F is uncountable.

« Last Edit: Mar 31^{st}, 2008, 12:42pm by Obob » 
IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Uncountable "chain" of subsets?
« Reply #5 on: Mar 31^{st}, 2008, 1:59pm » 
Quote Modify

So, one way of looking at is as an uncountable chain of subsets of . But another way of looking at is as an uncountable antichain of subsets of , such that any two subsets have finite intersection. How?


IP Logged 



Obob
Senior Riddler
Gender:
Posts: 489


Re: Uncountable "chain" of subsets?
« Reply #6 on: Mar 31^{st}, 2008, 2:14pm » 
Quote Modify

By decimal approximation.


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Uncountable "chain" of subsets?
« Reply #7 on: Mar 31^{st}, 2008, 3:20pm » 
Quote Modify

on Mar 31^{st}, 2008, 1:59pm, Eigenray wrote:So, one way of looking at is as an uncountable chain of subsets of . But another way of looking at is as an uncountable antichain of subsets of , such that any two subsets have finite intersection. How? 
 For each real s, consider a sequence of rationals which converges to it. Call it Q_{s}. Q_{s} intersection Q_{t} is finite for any distinct reals s and t. I believe there is a thread on this which I started. Probably by the name "Almost Disjoint Sets". This problem appears in the book "A problem Seminar" by D.J. Newman.

« Last Edit: Mar 31^{st}, 2008, 3:25pm by Aryabhatta » 
IP Logged 



Eigenray
wu::riddles Moderator Uberpuzzler
Gender:
Posts: 1948


Re: Uncountable "chain" of subsets?
« Reply #8 on: Mar 31^{st}, 2008, 9:01pm » 
Quote Modify

Acutally, both problems have been here before.


IP Logged 



Aryabhatta
Uberpuzzler
Gender:
Posts: 1321


Re: Uncountable "chain" of subsets?
« Reply #9 on: Apr 1^{st}, 2008, 1:23am » 
Quote Modify

That is funny. Perhaps there is a disorder called "Selective Amnesia".


IP Logged 



