wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> Uncountable "chain" of subsets?
        
(Message started by: Aryabhatta on Mar 29^th, 2008, 10:50pm)

Title: Uncountable "chain" of subsets?
Post by Aryabhatta on Mar 29^th, 2008, 10:50pm

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.

Title: Re: Uncountable "chain" of subsets?
Post by Grimbal on Mar 30^th, 2008, 2:06pm

This reminds me of the relation between Q and R.

Title: Re: Uncountable "chain" of subsets?
Post by Obob on Mar 30^th, 2008, 4:10pm

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

Title: Re: Uncountable "chain" of subsets?
Post by Aryabhatta on Mar 31^st, 2008, 11:30am

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

Title: Re: Uncountable "chain" of subsets?
Post by Obob on Mar 31^st, 2008, 12:42pm

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.

Title: Re: Uncountable "chain" of subsets?
Post by Eigenray on Mar 31^st, 2008, 1:59pm

So, one way of looking at http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbr.gif is as an uncountable chain of subsets of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbq.gif.

But another way of looking at http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbr.gif is as an uncountable anti-chain of subsets of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/bbq.gif, such that any two subsets have finite intersection. How?

Title: Re: Uncountable "chain" of subsets?
Post by Obob on Mar 31^st, 2008, 2:14pm

By [hide]decimal approximation.[/hide]

Title: Re: Uncountable "chain" of subsets?
Post by Aryabhatta on Mar 31^st, 2008, 3:20pm

on 03/31/08 at 13:59:47, Eigenray wrote:

[hide] 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.[/hide]

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.

Title: Re: Uncountable "chain" of subsets?
Post by Eigenray on Mar 31^st, 2008, 9:01pm

Acutally, [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1033460011]both[/link] [link=http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1090827814]problems[/link] have been here before.

Title: Re: Uncountable "chain" of subsets?
Post by Aryabhatta on Apr 1^st, 2008, 1:23am

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