wu :: forums « wu :: forums - Chain of subsets » Welcome, Guest. Please Login or Register. Aug 8th, 2022, 3:58pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    putnam exam (pure math) (Moderators: towr, Grimbal, william wu, SMQ, Eigenray, Icarus)    Chain of subsets « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: Chain of subsets  (Read 1225 times)
tim
Junior Member

Posts: 81
 Chain of subsets   « on: Oct 1st, 2002, 1:13am » Quote Modify

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.

 IP Logged
Pietro K.C.
Full Member

Gender:
Posts: 213
 Re: Chain of subsets   « Reply #1 on: Oct 1st, 2002, 9:33am » Quote Modify

Hats off to Tim!

Really beautiful solution.
 « Last Edit: Oct 1st, 2002, 9:34am by Pietro K.C. » IP Logged

"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was --- the meaning of life. It was not what I expected." (Dogbert)
 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 »