15
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Not sure about $\mathfrak c$-many, but $\omega_1$-many -- yes, I think. $\endgroup$ – tomasz Jun 24 '12 at 13:47
  • 2
    $\begingroup$ @tomasz: continuum many is perfectly doable. $\endgroup$ – Asaf Karagila Jun 24 '12 at 14:21
  • 3
    $\begingroup$ Such system of sets is called almost disjoint family. See e.g. here. $\endgroup$ – Martin Sleziak Jun 24 '12 at 17:07
  • $\begingroup$ This is problem 13, page 27, of Kaplansky's "Set theory and metric spaces". $\endgroup$ – Santropedro Apr 19 '17 at 3:32
  • $\begingroup$ Since this is the canonical duplicate I've decided to edit its title to make it easier to find. I invite people to help improve this question in other ways as well. $\endgroup$ – Asaf Karagila Apr 12 at 16:52
39
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @pritam: By Cantor's theorem it is not countable. $\endgroup$ – Asaf Karagila Jun 24 '12 at 13:06
  • $\begingroup$ @pritam he's considering subsets of $\mathbb{Q}$, which is countable. So it meets your conditions exactly. $\endgroup$ – Dustan Levenstein Jun 24 '12 at 13:07
  • $\begingroup$ @pritam: And $\mathbb Q$ is not a countable set? $\endgroup$ – Asaf Karagila Jun 24 '12 at 13:09
  • 1
    $\begingroup$ @dorsh605: Yes, your previous comment used $X_\alpha$ to denote the sequence converging to $\alpha$. Sorry for not predicting the future change to $S_\alpha$, my crystal ball is not with me right now. ;-) $\endgroup$ – Asaf Karagila Sep 2 '15 at 9:52
  • 1
    $\begingroup$ @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. $\endgroup$ – Asaf Karagila Sep 26 '15 at 13:37
6
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ The definition of $B_A$ is really unclear. $\endgroup$ – Asaf Karagila Mar 14 '14 at 16:46
  • 1
    $\begingroup$ $B_A$ = {${p_0,p_0*p_1,p_0*p_1*p_2,...}$} $\endgroup$ – Amitayu Banerjee Mar 14 '14 at 16:53
  • 1
    $\begingroup$ I asked for a clarification, and you just rewrote the same thing that was unclear. $\endgroup$ – Asaf Karagila Mar 14 '14 at 17:02
  • 1
    $\begingroup$ I still don't understand how do you define $B_A$?? $\endgroup$ – Asaf Karagila Mar 14 '14 at 18:17
  • 1
    $\begingroup$ 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 ? $\endgroup$ – Amitayu Banerjee Mar 14 '14 at 18:35
4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

For each $t\in(\frac1{10},1),$ take its decimal expansion (or one of its decimal expansions in case of non-uniqueness), and let $A_t$ be the set of all finite truncations of that decimal expansion, considered as positive integers. For example, $$A_{\frac13}=\{3,\ 33,\ 333,\ 3333,\ 33333,\dots\},$$ $$A_{\pi-3}=\{1,\ 14,\ 141,\ 1415,\ 14159,\dots\}.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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