wu :: forums - Print Page


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

        riddles >> putnam exam (pure math) >> Chain of subsets
        
(Message started by: tim on Oct 1^st, 2002, 1:13am)

Title: Chain of subsets
Post by tim on Oct 1^st, 2002, 1:13am

At first, I thought that of course it must be countable: after all, each link in the chain must add at least one element, and there are only a countable number to add.

Then I started to have second thoughts. For example, if the chain counts up through all the even numbers, then all remaining multiples of three, etc. That would break the simple mapping I had in mind.

Solution:

Finally, I found a counterexample. It was ridiculously contorted at first, being a mapping from [0,1) into sequences of binary digits, which in turn can be broken down into a recursive function of unions of powers of primes. Then I hit a really simple one:

Every real number has a Dedekind cut, the set of all rationals less than it. These sets of rationals form a chain. Rationals can be bijectively mapped with the positive integers. Therefore an uncountable chain of sets of positive integers exists.

Title: Re: Chain of subsets
Post by Pietro K.C. on Oct 1^st, 2002, 9:33am

Hats off to Tim! :)

Really beautiful solution.