Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|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
Such system of sets is called almost disjoint family. See e.g. here. – Martin Sleziak Jun 24 '12 at 17:07
up vote 35 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|cite|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
@Sahiba Arora: For various reasons. Mainly because every convergent sequence in $\Bbb R$ has a monotonous subsequence. You can also enumerate the rational numbers, and proceed by induction to define a sequence which converges monotonically to $r$ from above or from below. – Asaf Karagila Sep 26 '15 at 13:37

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|cite|improve this answer

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|cite|improve this answer

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_1x$ 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|cite|improve this answer

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|cite|improve this answer
The definition of $B_A$ is really unclear. – Asaf Karagila Mar 14 '14 at 16:46
$B_A$ = {${p_0,p_0*p_1,p_0*p_1*p_2,...}$} – Amitayu Banerjee Mar 14 '14 at 16:53
I asked for a clarification, and you just rewrote the same thing that was unclear. – Asaf Karagila Mar 14 '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 '14 at 17:14
Given an infinite subset of primes, A = {$p_0,p_1,...$}, I am forming a set $B_A$, the element $p_i$ in A is mapped to ($p_0*p_1*...*p_i$) in B. Can you please elaborate the problem ? – Amitayu Banerjee Mar 14 '14 at 18:35

Your Answer


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.