Results 1 to 5 of 5

Math Help - Putnam question

  1. #1
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    Putnam question

    Hello everyone. I would greatly appreciate if someone could validate whether or not the following solution is correct.

    Problem: Is it possible for a countably infinte set to have an uncountable collection of subsets such that the intersection of any two is finite?

    Answer: Yes it is.

    Proof:

    Define \left\{\alpha_n\right\}_{n=1}^{\infty} to be a rational sequence converging to \alpha and \mathcal{U}_{\alpha}=\left\{\alpha_n:n\in\mathbb{N  }\right\} and let \mathcal{J}=\bigcup_{\alpha\in\mathbb{R}}\mathcal{  U}_{\alpha}. It is clear that if \alpha\ne\beta that \mathcal{U}_{\alpha}\cap\mathcal{U}_{\beta} is finite, otherwise both sequences would converge to the same value. Particularly this implies that \alpha\ne\beta\implies\mathcal{U}_{\alpha}\ne\math  cal{U}_{\beta} thus \text{card }\mathcal{J}\ge\text{card }\mathbb{R}. Lastly noting that \mathcal{U}_{\alpha}\subset\mathbb{Q}\quad\forall\  mathcal{U}_{\alpha}\in\mathcal{J} we may conclude that \mathcal{J} is an uncountable collection of subsets of a countable set such that the intersection of any two is finite. \blacksquare


    What do you think?
    Last edited by Drexel28; November 9th 2009 at 09:28 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    100% correct!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by Opalg View Post
    100% correct!
    Almost. I made a typo. Here was my final solution, with all the accrutements.

    Problem: Does there exist an uncountable collection of subsets of a countably infinite set such that the intersection of any two is finite?

    Claim: Yes there does.

    Proof:

    Lemma: Let \alpha,\beta be distinct real numbers. Furthermore let \left\{\alpha_n\right\}_{n=1}^{\infty},\left\{\bet  a_n\right\}_{n=1}^{\infty} be rational sequences converging to \alpha,\beta respectively. Next define \mathcal{U}_{\alpha}=\left\{\alpha_n:n\in\mathbb{N  }\right\}. Then \mathcal{U}_{\alpha}\cap\mathcal{U}_{\beta} is finite.

    Proof: WLOG assume that \alpha<\beta. Then since \lim_{n\to\infty}\alpha_n=\alpha and \lim_{n\to\infty}\beta_n=\beta it can be seen that \lim_{n\to\infty}\left\{\beta_n-\alpha_n\right\}=\beta-\alpha. This implies that \forall\varepsilon>0\text{ }\exists N\in\mathbb{N} such that N\le n\implies \left|\beta_n-\alpha_n-\left(\beta-\alpha\right)\right|<\varepsilon. Manipulating this yields \beta-\alpha-\varepsilon<\beta_n-\alpha_n<\beta-\alpha+\epsilon. Taking \varepsilon=\frac{\beta-\alpha}{2}>0 and focusing on the first two terms in teh above inequality tells us \exists N'\in\mathbb{N} such that N'\le n\implies 0<\frac{\beta-\alpha}{2}<\beta_n-\alpha_n\implies \alpha_n\ne\beta_n. And since N' is finite the conclusion follows \blacksquare

    Now because both the rationals are dense in the reals for every real number \alpha there exists some rational sequence \left\{\alpha_n\right\}_{n=1}^{\infty} such that \lim_{n\to\infty}\alpha_n=\alpha. Define \mathcal{U}_{\alpha} as above and let \mathcal{J}=\left\{\mathcal{U}_{\alpha}:\alpha\in\  mathbb{R}\right\}. Since the above in particular implies that \alpha\ne\beta\implies\mathcal{U}_{\alpha}\ne\math  cal{U}_{\beta} we see that the mapping \Phi:\mathbb{R}\mapsto\mathcal{J} given by \alpha\mapsto\mathcal{U}_{\alpha} is injective. Therefore \text{card }\mathbb{R}\le\text{card }\mathcal{J}. Lastly noting that \mathcal{U}_{\alpha}\subset\mathbb{Q}\quad\forall\  mathcal{U}_{\alpha}\in\mathcal{J} we may conclude that \mathcal{J} is an uncountable collection of subsets of a countable set such that the intersection of any two is finite. \blacksquare



    Remark: Although there must exist a rational sequence \left\{\sigma_n\right\}_{n=1}^{\infty} such that \sigma_n\to\sigma finding them is not altogether obvious. A simple example would be to define \sigma_n=\begin{cases} \sum_{\ell=1}^{n}\frac{\sigma}{2^\ell} & \mbox{if }\sigma\in\mathbb{Q}\\ \text{the }n\text{th convergent in the continued fraction expansion of }\sigma & \mbox{if }\sigma\notin\mathbb{Q} \end{cases}
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    I also came up with an alternate solution. Granted, I was given the hint 'lattice points'.

    Problem: Does there exist an uncountable collection of subsets of a countable set such that the intersection of any two is finite?

    Claim: Yes there is.

    Proof: Let \alpha\in\mathbb{R} and let \mathcal{L}_{\alpha}=\left\{z\in\mathbb{Z}^2:d(y,z  )\le1\right\} where y is any point on the line y=\alpha x. Clearly any two lines y=\alpha x,y=\beta x will only intersect at the origin O. Next note that these two lines will eventually (no matter how close |\alpha-\beta| is) move one unit apart. This will occur when |x|>M for some finite constant M\in\mathbb{R}. This implies that \mathcal{L}_{\alpha}\cap\mathcal{L}_{\beta} is finite for any dinstinct \alpha,\beta. Next we can see that \alpha\ne\beta\implies \mathcal{L}_{\alpha}\ne\mathcal{L}_{\beta}, which is clear from the previous observation. Therefore if we define \mathcal{M}=\left\{\mathcal{L}_{\alpha}:\alpha\in\  mathbb{R}\right\} that the mapping \Psi:\mathbb{R}\mapsto\mathcal{M} given by \alpha\mapsto\mathcal{L}_{\alpha} is injective. Thus \text{card }\mathcal{M}\ge\text{card }\mathbb{R}. Lastly, notice that since \mathcal{L}_{\alpha} consists entirely of lattice points that \mathcal{L}_{\alpha}\subset\mathbb{Z}^2\quad\foral  l\mathcal{L}_{\alpha}\in\mathcal{M}. Putting this all together we see that \mathcal{M} is an uncountably infite collection of subsets of a countably infinite set such that the intersection of any two is finite.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2009
    Posts
    10
    Hello. I've got an another idea. How about this:

    Let  p_1 < p_2 < p_3 < \cdots be the prime numbers. For each  b = (b_1, b_2, b_3, \dots) \in \{0, 1\}^{\mathbb N} = B , let  \textstyle P_b = \{ \prod_{i=1}^n {p_i}^{b_i} : n=1, 2, 3, \dots \} \subset \mathbb N . Then the set  \{ P_b \}_{b \in B} satisfies the condition required in the statement. It is easy to see that uniqueness of prime factorization gives us the finiteness of the intersection of any two distinct members of  \{ P_b \}_{b \in B} and that Cantor's diagonal slash gives us uncountability of  B , namely  \{ P_b \}_{b \in B} .

    Thank you.

    Misako Kawasoe
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Putnam Problem
    Posted in the Math Puzzles Forum
    Replies: 5
    Last Post: September 8th 2010, 11:01 AM
  2. Putnam 1990 A1
    Posted in the Discrete Math Forum
    Replies: 6
    Last Post: June 20th 2010, 10:23 AM
  3. Putnam Problem of the Day (3)
    Posted in the Math Challenge Problems Forum
    Replies: 6
    Last Post: June 11th 2010, 01:31 AM
  4. Putnam Problem of the Day (2)
    Posted in the Math Challenge Problems Forum
    Replies: 0
    Last Post: May 24th 2010, 05:21 PM
  5. Putnam proof
    Posted in the Statistics Forum
    Replies: 8
    Last Post: August 31st 2006, 01:46 PM

Search Tags


/mathhelpforum @mathhelpforum