5
$\begingroup$

Possible Duplicate:
Countable set having uncountably many infinite subsets

Question:

Is it possible to find uncountably many infinite sets of natural numbers that any two of these sets have only finitely many common elements

$\endgroup$

marked as duplicate by Asaf Karagila, Henning Makholm, Chris Eagle, Did, David Mitra Jan 14 '13 at 21:09

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

15
$\begingroup$

You can even get $2^\omega=\mathfrak c$ of them. Such families of sets are called almost disjoint families.

One way to get an uncountable almost disjoint family of subsets of $\Bbb N$ is as follows. For each irrational number $x$ let $\langle q_x(k):k\in\Bbb N\rangle$ be a sequence of rational numbers converging monotonically to $x$. It’s easy to see that if $x$ and $y$ are distinct irrationals, the sequences $\langle q_x(k):k\in\Bbb N\rangle$ and $\langle q_y(k):k\in\Bbb N\rangle$ can have only finitely many terms in common. Now let $\varphi:\Bbb Q\to\Bbb N$ be any bijection, for each irrational $x$ let $D(x)=\{\varphi(q_x(k)):k\in\Bbb N\}$, and let $\mathscr{D}=\{D(x):x\in\Bbb R\setminus\Bbb Q\}$; $\mathscr{D}$ is an uncountable family of almost disjoint subsets of $\Bbb N$.

Added: Here’s another cute way. Imagine that you have an infinite plastic strip one unit wide. You pin some point on its midline to the origin, so that the strip can rotate about the origin. In each orientation it covers an infinite number of points of the integer lattice $\Bbb Z\times\Bbb Z$. For $\alpha\in[0,\pi)$ let $S_\alpha$ be the set of points in $\Bbb Z\times\Bbb Z$ covered by the strip when its midline coincides with the line $y=\alpha x$; it’s easy to see that $S\alpha\cap S_\beta$ is finite when $\alpha\ne\beta$. Now let $\varphi:\Bbb Z\times\Bbb Z\to\Bbb N$ be any injection, and for $\alpha\in[0,\pi)$ let $T_\alpha=\varphi[S_\alpha]$; the family $\{T_\alpha:\alpha\in[0,\pi)\}$ is then almost disjoint.

$\endgroup$
  • 2
    $\begingroup$ You can even say "real number" instead of "irrational". $\endgroup$ – Henning Makholm Jan 14 '13 at 21:02
  • $\begingroup$ Indeed, using $\mathbb R\setminus\mathbb Q$ distracts the reader. $\endgroup$ – Did Jan 14 '13 at 21:05
  • $\begingroup$ @did: Depends on the reader: I’ve had students get confused by the use of rationals as both indices and elements of the sets. $\endgroup$ – Brian M. Scott Jan 14 '13 at 21:10
  • 1
    $\begingroup$ The second one is nice. $\endgroup$ – Did Jan 14 '13 at 21:14
  • $\begingroup$ I like the second example. In fact, we can construct the real numbers as equivalence classes of functions $\mathbb{Z} \to \mathbb{Z}$ that fit inside some such plastic strip of finite width through the origin. $\endgroup$ – 6005 Sep 16 '16 at 19:48

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