
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?


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}$

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.

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