# Putnam question

Printable View

• Nov 9th 2009, 08: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?

Answer: Yes it is.

Proof:

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

What do you think?
• Nov 10th 2009, 12:32 AM
Opalg
100% correct! (Clapping)
• Nov 10th 2009, 06: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 $\displaystyle \alpha,\beta$ be distinct real numbers. Furthermore let $\displaystyle \left\{\alpha_n\right\}_{n=1}^{\infty},\left\{\bet a_n\right\}_{n=1}^{\infty}$ be rational sequences converging to $\displaystyle \alpha,\beta$ respectively. Next define $\displaystyle \mathcal{U}_{\alpha}=\left\{\alpha_n:n\in\mathbb{N }\right\}$. Then $\displaystyle \mathcal{U}_{\alpha}\cap\mathcal{U}_{\beta}$ is finite.

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

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

Remark: Although there must exist a rational sequence $\displaystyle \left\{\sigma_n\right\}_{n=1}^{\infty}$ such that $\displaystyle \sigma_n\to\sigma$ finding them is not altogether obvious. A simple example would be to define $\displaystyle \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, 02: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 $\displaystyle \alpha\in\mathbb{R}$ and let $\displaystyle \mathcal{L}_{\alpha}=\left\{z\in\mathbb{Z}^2:d(y,z )\le1\right\}$ where $\displaystyle y$ is any point on the line $\displaystyle y=\alpha x$. Clearly any two lines $\displaystyle y=\alpha x,y=\beta x$ will only intersect at the origin $\displaystyle O$. Next note that these two lines will eventually (no matter how close $\displaystyle |\alpha-\beta|$ is) move one unit apart. This will occur when $\displaystyle |x|>M$ for some finite constant $\displaystyle M\in\mathbb{R}$. This implies that $\displaystyle \mathcal{L}_{\alpha}\cap\mathcal{L}_{\beta}$ is finite for any dinstinct $\displaystyle \alpha,\beta$. Next we can see that $\displaystyle \alpha\ne\beta\implies \mathcal{L}_{\alpha}\ne\mathcal{L}_{\beta}$, which is clear from the previous observation. Therefore if we define $\displaystyle \mathcal{M}=\left\{\mathcal{L}_{\alpha}:\alpha\in\ mathbb{R}\right\}$ that the mapping $\displaystyle \Psi:\mathbb{R}\mapsto\mathcal{M}$ given by $\displaystyle \alpha\mapsto\mathcal{L}_{\alpha}$ is injective. Thus $\displaystyle \text{card }\mathcal{M}\ge\text{card }\mathbb{R}$. Lastly, notice that since $\displaystyle \mathcal{L}_{\alpha}$ consists entirely of lattice points that $\displaystyle \mathcal{L}_{\alpha}\subset\mathbb{Z}^2\quad\foral l\mathcal{L}_{\alpha}\in\mathcal{M}$. Putting this all together we see that $\displaystyle \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, 05:31 PM
k-misako
Hello. I've got an another idea. How about this:

Let $\displaystyle p_1 < p_2 < p_3 < \cdots$ be the prime numbers. For each $\displaystyle b = (b_1, b_2, b_3, \dots) \in \{0, 1\}^{\mathbb N} = B$, let $\displaystyle \textstyle P_b = \{ \prod_{i=1}^n {p_i}^{b_i} : n=1, 2, 3, \dots \} \subset \mathbb N$. Then the set $\displaystyle \{ 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 $\displaystyle \{ P_b \}_{b \in B}$ and that Cantor's diagonal slash gives us uncountability of $\displaystyle B$, namely $\displaystyle \{ P_b \}_{b \in B}$.

Thank you.

Misako Kawasoe