Author |
Topic: Almost disjoint family (Read 1181 times) |
|
Aryabhatta
Uberpuzzler
Gender: 
Posts: 1321
|
 |
Almost disjoint family
« on: Jul 26th, 2004, 12:43am » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Almost disjoint family
« Reply #1 on: Jul 26th, 2004, 2:26am » |
Quote Modify
|
::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..::
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Almost disjoint family
« Reply #2 on: Jul 26th, 2004, 7:22am » |
Quote Modify
|
on Jul 26th, 2004, 2:26am, 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: The obvious solution has cardinality equal to N. What is a popular set that is larger?
Hint2: How is it defined?
Hint3: Cauchy sequences of rationals
Solution:
Let f : N -> Q be a bijection.
For each real x, let {ri} be a Cauchy sequence of rationals converging to x. Let Sx = { f-1(ri) }.
|
| « Last Edit: Jul 26th, 2004, 7:25am by Eigenray » |
IP Logged |
|
|
|
beibeibee
Newbie
 
Gender:
Posts: 5
|
|
Re: Almost disjoint family
« Reply #3 on: Oct 6th, 2004, 10:51am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Almost disjoint family
« Reply #4 on: Oct 6th, 2004, 11:45am » |
Quote Modify
|
on Oct 6th, 2004, 10:51am, 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.
|
|
IP Logged |
|
|
|
beibeibee
Newbie
Gender:
Posts: 5
|
|
Re: Almost disjoint family
« Reply #5 on: Oct 12th, 2004, 4:07am » |
Quote Modify
|
on Oct 6th, 2004, 11:45am, Aryabhatta wrote:
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.
|
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print