Author |
Topic: Uncountable "chain" of subsets? (Read 4070 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Uncountable "chain" of subsets?
« on: Mar 29th, 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 30th, 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 30th, 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 31st, 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 31st, 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 31st, 2008, 12:42pm by Obob » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Uncountable "chain" of subsets?
« Reply #5 on: Mar 31st, 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 anti-chain 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 31st, 2008, 2:14pm » |
Quote Modify
|
By decimal approximation.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Uncountable "chain" of subsets?
« Reply #7 on: Mar 31st, 2008, 3:20pm » |
Quote 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:
Posts: 1948
|
|
Re: Uncountable "chain" of subsets?
« Reply #8 on: Mar 31st, 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 1st, 2008, 1:23am » |
Quote Modify
|
That is funny. Perhaps there is a disorder called "Selective Amnesia".
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print