15
$\begingroup$

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

  • 1
    Not sure about $\mathfrak c$-many, but $\omega_1$-many -- yes, I think.2012-06-24
  • 2
    @tomasz: continuum many is perfectly doable.2012-06-24
  • 3
    Such system of sets is called [almost disjoint family](http://en.wikipedia.org/wiki/Almost_disjoint_sets). See e.g. [here](http://at.yorku.ca/cgi-bin/bbqa?forum=ask_a_topologist_2002;task=show_msg;msg=0239.0001).2012-06-24
  • 0
    This is problem 13, page 27, of Kaplansky's "Set theory and metric spaces".2017-04-19

6 Answers 6

39

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.

  • 0
    @pritam: By Cantor's theorem it is not countable.2012-06-24
  • 0
    @pritam he's considering subsets of $\mathbb{Q}$, which is countable. So it meets your conditions exactly.2012-06-24
  • 0
    @pritam: And $\mathbb Q$ is not a countable set?2012-06-24
  • 0
    @Mark: Good idea. Thanks!2012-06-24
  • 0
    One can remark that this is essentially why the real numbers are uncountable in particular when constructed with Dedekind cuts, perhaps.2014-03-14
  • 0
    @AsafKaragila If I want to prove it for a general countable set, $X$ , would it be correct to say that there is a bijection, $f$, from $\mathbb{Q}$ to $X$ and for every $\alpha \in \mathbb{R}$ define the set $X_ \alpha$ as the set of all elements of the sequence that converges to $\alpha$ (the same sequence in your solution) after applying $f$ on them and then the function $g: ({X_\alpha })_{\alpha \in \mathbb{R}} \longrightarrow \mathbb{R}$ , $g(X_\alpha)=\alpha$ is a bijection?2015-09-02
  • 0
    @dorsh605: Yes, and perhaps a simpler way of doing that would be to define $F(\alpha)=\{f(q)\mid q\in X_\alpha\}$, where $f\colon\Bbb Q\to X$ is a bijection. Then $F$ is an injective function from $\Bbb R$ into $\mathcal P(X)$ such that any two distinct sets in its image have finite intersection.2015-09-02
  • 0
    @AsafKaragila did you mean $F(\alpha)=\{f(q){ }|{ }q\in \underline{S_\alpha}\}$ where $S_\alpha$ is the set of all elements in the sequence that converges to $\alpha$?2015-09-02
  • 1
    @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. ;-)2015-09-02
  • 0
    @AsafKaragila I only changed it because in my previous comment I defined the set $X_\alpha$ to be the set of elements of $S_\alpha$ after applying f on them i.e $X_\alpha = \{f(q) | q\in S_\alpha \}$2015-09-02
  • 0
    @dorsh605: Oh. I see now. Sorry, yes. $S_\alpha$.2015-09-02
  • 0
    @AsafKaragila thanks for the answer :)2015-09-02
  • 0
    Why does such a sequence exist?2015-09-26
  • 0
    @Sahiba Arora: What sequence?2015-09-26
  • 0
    A sequence which converges monotonically to r.2015-09-26
  • 1
    @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.2015-09-26
  • 0
    @AsafKaragila So you know, if you care so, your solution coincides with the "hint" given by the problem statement of Kaplansky's "Set theory and metric spaces" problem 13, page 27.2017-04-19
  • 0
    @Santropedro: I have never opened that book. It's a standard solution to this problem, and I learned it when I was an undergrad, from one of my friends.2017-04-19
  • 0
    @AsafKaragila Interesting thanks for letting me know that! I hope you didn't get offended (In case it happened, I don't have idea if it did).2017-04-19
6

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

4

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.

  • 2
    The definition of $B_A$ is really unclear.2014-03-14
  • 1
    $B_A$ = {${p_0,p_0*p_1,p_0*p_1*p_2,...}$}2014-03-14
  • 1
    I asked for a clarification, and you just rewrote the same thing that was unclear.2014-03-14
  • 0
    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 !2014-03-14
  • 1
    I still don't understand **how do you define $B_A$**??2014-03-14
  • 1
    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 ?2014-03-14
4

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.

3

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

2

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