wu :: forums « wu :: forums - Uncountable "chain" of subsets? » Welcome, Guest. Please Login or Register. May 25th, 2024, 1:14pm RIDDLES SITE WRITE MATH! Home Help Search Members Login 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 Notify of replies Send Topic Print
 Author Topic: Uncountable "chain" of subsets?  (Read 4041 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
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »