wu :: forums
wu :: forums - Uncountable "chain" of subsets?

Welcome, Guest. Please Login or Register.
May 25th, 2024, 1:14pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: SMQ, Eigenray, Icarus, Grimbal, william wu, towr)
   Uncountable "chain" of subsets?
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Uncountable "chain" of subsets?  (Read 4041 times)
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Uncountable "chain" of subsets?  
« on: Mar 29th, 2008, 10:50pm »
Quote Quote Modify 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: male
Posts: 7527
Re: Uncountable "chain" of subsets?  
« Reply #1 on: Mar 30th, 2008, 2:06pm »
Quote Quote Modify Modify

This reminds me of the relation between Q and R.
IP Logged
Obob
Senior Riddler
****





   


Gender: male
Posts: 489
Re: Uncountable "chain" of subsets?  
« Reply #2 on: Mar 30th, 2008, 4:10pm »
Quote Quote Modify 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: male
Posts: 1321
Re: Uncountable "chain" of subsets?  
« Reply #3 on: Mar 31st, 2008, 11:30am »
Quote Quote Modify Modify

Yup! We can find F such that it is uncountable.  
 
IP Logged
Obob
Senior Riddler
****





   


Gender: male
Posts: 489
Re: Uncountable "chain" of subsets?  
« Reply #4 on: Mar 31st, 2008, 12:42pm »
Quote Quote Modify 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 31st, 2008, 12:42pm by Obob » IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Uncountable "chain" of subsets?  
« Reply #5 on: Mar 31st, 2008, 1:59pm »
Quote Quote Modify 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 anti-chain of subsets of , such that any two subsets have finite intersection.  How?
IP Logged
Obob
Senior Riddler
****





   


Gender: male
Posts: 489
Re: Uncountable "chain" of subsets?  
« Reply #6 on: Mar 31st, 2008, 2:14pm »
Quote Quote Modify Modify

By decimal approximation.
IP Logged
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Uncountable "chain" of subsets?  
« Reply #7 on: Mar 31st, 2008, 3:20pm »
Quote Quote Modify Modify

on Mar 31st, 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 anti-chain 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 Qs. Qs intersection Qt 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 31st, 2008, 3:25pm by Aryabhatta » IP Logged
Eigenray
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 1948
Re: Uncountable "chain" of subsets?  
« Reply #8 on: Mar 31st, 2008, 9:01pm »
Quote Quote Modify Modify

Acutally, both problems have been here before.
IP Logged
Aryabhatta
Uberpuzzler
*****






   


Gender: male
Posts: 1321
Re: Uncountable "chain" of subsets?  
« Reply #9 on: Apr 1st, 2008, 1:23am »
Quote Quote Modify Modify

That is funny. Perhaps there is a disorder called "Selective Amnesia".
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board