# Putnam question

• Nov 9th 2009, 09:40 PM
Drexel28
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?

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?
• Nov 10th 2009, 01:32 AM
Opalg
100% correct! (Clapping)
• Nov 10th 2009, 07:44 AM
Drexel28
Quote:

Originally Posted by Opalg
100% correct! (Clapping)

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}$
• Nov 10th 2009, 03:49 PM
Drexel28
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.
• Dec 11th 2009, 06:31 PM
k-misako
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}$.