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.

Possible Duplicate:
Countable set having uncountably many infinite subsets


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

share|improve this question

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.

I don't understand why you changed the title of the question... –  Asaf Karagila Jan 14 '13 at 21:57

1 Answer 1

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.

share|improve this answer
You can even say "real number" instead of "irrational". –  Henning Makholm Jan 14 '13 at 21:02
Indeed, using $\mathbb R\setminus\mathbb Q$ distracts the reader. –  Did Jan 14 '13 at 21:05
@did: Depends on the reader: I’ve had students get confused by the use of rationals as both indices and elements of the sets. –  Brian M. Scott Jan 14 '13 at 21:10
The second one is nice. –  Did Jan 14 '13 at 21:14

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