Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can a countable set contain uncountably many infinite subsets such that the intersection of any two such distinct subsets is finite ?

share|improve this question
    
Not sure about $\mathfrak c$-many, but $\omega_1$-many -- yes, I think. –  tomasz Jun 24 '12 at 13:47
    
@tomasz: continuum many is perfectly doable. –  Asaf Karagila Jun 24 '12 at 14:21
1  
Such system of sets is called almost disjoint family. See e.g. here. –  Martin Sleziak Jun 24 '12 at 17:07
add comment

5 Answers 5

up vote 26 down vote accepted

Yes. For every $r\in\mathbb R$ choose a sequence of rational numbers $\{r_n\in\mathbb Q\mid n\in\mathbb N\}$ which converges monotonically to $r$, this sequence is of course a subset of $\mathbb Q$ - a countable set.

If $r\neq s$ are two real numbers then the sequence we chose for them must intersect at a finite subset, otherwise we had a subsequence of the two which would converge to two different limit points.

Since $\mathbb R$ is uncountable (and in fact has cardinality as $\mathcal P(\mathbb Q)$) we have indeed uncountably many subsets of $\mathbb Q$ with the wanted property.

share|improve this answer
    
@pritam: By Cantor's theorem it is not countable. –  Asaf Karagila Jun 24 '12 at 13:06
    
@pritam he's considering subsets of $\mathbb{Q}$, which is countable. So it meets your conditions exactly. –  Dustan Levenstein Jun 24 '12 at 13:07
    
@pritam: And $\mathbb Q$ is not a countable set? –  Asaf Karagila Jun 24 '12 at 13:09
    
@Mark: Good idea. Thanks! –  Asaf Karagila Jun 24 '12 at 17:13
    
One can remark that this is essentially why the real numbers are uncountable in particular when constructed with Dedekind cuts, perhaps. –  Pedro Tamaroff Mar 14 at 19:21
add comment

Yes. We know $\mathbb{N}$ and $\mathbb{Q}$ are equipotent so we choose a bijection $f:\mathbb{N} \to \mathbb{Q}$. We also know that $\mathbb{R}$ is equipotent to the set of equivalence classes of Cauchy sequences in $\mathbb{Q}$. For every $r \in \mathbb{R}$ choose $(q_{r,n})_n$ a representative from the equivalence class corresponding to $r$. Note that if $r_1\neq r_2 \in \mathbb{R}$ then $q_{r_1,n} = q_{r_2,n}$ for at most finitely many $n$. Since $f$ is a bijection we have that the sequences $(m_{r,n})_n := (f^{-1}(q_{r,n}))_n \subseteq \mathbb{N}$ share the same property. Since $\mathbb{R}$ is uncountable this concludes the proof; just choose the subset $N_\alpha$ to be the range of $m_\alpha$.

share|improve this answer
add comment

Pick $S = \cup_{n \in \mathbb N} \{0;1\}^{\{1;2;\ldots;n\}}$, the set of functions from a finite set to $\{0;1\}$. For any function $f : \mathbb N \to \{0;1\}$, let $g(f) = \{ f|_{\{1;2;\ldots;n\}}, n \in \mathbb N\}$ : $g(f)$ is the subset of $S$ containing all the restrictions of $f$.

Then the set $\{g(f), f : \mathbb N \to \{0;1\}\}$ is an uncountable subset of $\mathcal P(S)$ (because $g$ is injective and there are uncountably many functions $f$) where any two distinct subsets have finite intersection (if $f_1$ and $f_2$ are distinct, they disagree at some integer $n$, from which all their restrictions are different).

Also, this is almost the same as picking $S$ as the set of finite subsets of $\mathbb{N}$, and $g : \mathcal P(\mathbb N) \to \mathcal P( S)$ the injection given by $g(X) = \{X \cap \{1 ; 2 ; \ldots n \}, n \in \mathbb N\}$.

share|improve this answer
add comment

Let P be the set of all prime numbers, which is countable. Consider an infinite subset A = {$p_0,p_1,p_2...$} of primes from P arranged in an increasing order. We form $B_A$ = {$p_0,p_0p_1,p_0p_1p_2,...$} corresponding to A.

Now, the prime factorization is unique for integers. Thus, if we choose another infinite subset $A_1$ of P different from A then the corresponding $B_{A_1}$ and $B_A$ has only finitely many elements in common. Since P is countably infinite, the number of different infinite subsets of P is continuum. Hence we are done.

share|improve this answer
2  
The definition of $B_A$ is really unclear. –  Asaf Karagila Mar 14 at 16:46
    
$B_A$ = {${p_0,p_0*p_1,p_0*p_1*p_2,...}$} –  Amitayu Banerjee Mar 14 at 16:53
    
I asked for a clarification, and you just rewrote the same thing that was unclear. –  Asaf Karagila Mar 14 at 17:02
    
There is a one to one correspondence between A and $B_A$ . So, Now for different infinite subset $A_1$ and $A_2$ we get corresponding $B_{A_1}$ and $B_{A_2}$. Then we arise in 2 possible cases, 1. First finite terms in $B_{A_1}$ and $B_{A_2}$ are same. 2. Otherwise, both the sets would have been same,leading to $A_1$ = $A_2$ and that's a contradiction ! –  Amitayu Banerjee Mar 14 at 17:14
    
I still don't understand how do you define $B_A$?? –  Asaf Karagila Mar 14 at 18:17
show 1 more comment

Another Solution: Since $\mathbb{N}$ and $\mathbb{N}\times\mathbb{N}$ are equivalent, and cardinality of $\mathbb{N}$ is $\omega$, we can work on $\mathbb{N}\times\mathbb{N}$. Fix a m $\in$ $\mathbb{R}$, let $A_m$ be the set of points (x,y) $\in$ $\mathbb{N}\times\mathbb{N}$, that are of distance $\leq$ 1 from the line y = mx. $A_m$ is infinite as it has a point on every vertical line x=k (k=0,1,2,...) and for any 2 lines y = mx and y= $m_1$x for m $\neq$$m_1$ , there are only finite number of points lying of distance $\leq$ 1 from both, so, $\ A_m\cap \ A_{m_1}$ is finite. These sets $\ A_m$ are the required subsets which are continuum many.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.