wu :: forums - Print Page


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

        riddles >> putnam exam (pure math) >> Almost disjoint family
        
(Message started by: Aryabhatta on Jul 26^th, 2004, 12:43am)

Title: Almost disjoint family
Post by Aryabhatta on Jul 26^th, 2004, 12:43am

This is a problem from the book: "A problem Seminar" by Donald J Newman.

Two sets are called almost disjoint if there intersection is finite.

Let F be a family of subsets of natural numbers. What is the largest cardinality that F can have so that any two distinct members of F are almost disjoint?

Title: Re: Almost disjoint family
Post by towr on Jul 26^th, 2004, 2:26am

::[hide]Can't you just take the family { { i | i < n} | n [in] [bbn] }, which has the same cardinality as [bbn] since they are equivalent.
Since any set in the family is finite any intersection between them is finite..

And even the power set of [bbn] has the same cardinality, doesn't it? So you can't get any more..[/hide]::

Title: Re: Almost disjoint family
Post by Eigenray on Jul 26^th, 2004, 7:22am

on 07/26/04 at 02:26:56, towr wrote:

And even the power set of [bbn] has the same cardinality, doesn't it?

Nooo!!!!! No set has the same cardinality as its power set:
Suppose f : S [to] P(S) is a bijection. Consider f^-1({ x | x [notin] f(x) }).

Back to the problem:
Hint1: [hide]The obvious solution has cardinality equal to N. What is a popular set that is larger?[/hide]
Hint2: [hide]How is it defined?[/hide]
Hint3: [hide]Cauchy sequences of rationals[/hide]
Solution:[hide]
Let f : N -> Q be a bijection.
For each real x, let {r_i} be a Cauchy sequence of rationals converging to x. Let S_x = { f^-1(r_i) }.
[/hide]

Title: Re: Almost disjoint family
Post by beibeibee on Oct 6^th, 2004, 10:51am

I think the answer is 2^aleph_0.
Just think about comlete binary tree of omega!!! You will find the family of sets of infinite many natural numbers, each of which is in some a branch of that tree.

Title: Re: Almost disjoint family
Post by Aryabhatta on Oct 6^th, 2004, 11:45am

on 10/06/04 at 10:51:36, beibeibee wrote:

I think the answer is 2^aleph_0.
Just think about comlete binary tree of omega!!! You will find the family of sets of infinite many natural numbers, each of which is in some a branch of that tree.

Yes. your answer is right! and your solution interesting.
It seems that any two paths from root must have a finite intersection, but when it comes to infinity a proof would be more convincing than just intuition. I am sure that your solution is correct (and very elegant i think), it would be more convincing if there was a proof.

Title: Re: Almost disjoint family
Post by beibeibee on Oct 12^th, 2004, 4:07am

on 10/06/04 at 11:45:19, Aryabhatta wrote:

Ok, let us make the intuition into proof.

First, put 0 or 1 on every node in the complete binary tree, just like this:
0
0 1
0 1 0 1
… … …
then clearly each sequence of 0’s and 1’s laying in some a branch encodes exactly a subset of N. We now can conclude that there is 2^aleph_0 branches.

Next, we show that any two different branches are ‘almost disjoint’. Now put the natural numbers on the nodes, like this:

0
1 2
3 4 5 6
… … …
You can see any two different branches, say B_1 and B_2, will meet on some natural number, say n, where each of these branches goes its own way. We then obtain B_1 cap B_2 is of cardinality less than n.