6
$\begingroup$

Let C be a collection of subsets of $\mathbb{N}$ such that $A,B\in C \Rightarrow A \not\subseteq B$. Can C be uncountable?

2 Answers 2

12

Yes. Consider the collections of subsets which contain exactly one of $2i$ and $2i+1$, for all $i$.

  • 0
    So this is the even and odd numbers? Aren't they countable?2010-11-28
  • 0
    never mind, $C$ is the power set.2010-11-28
6

Here is another one, perhaps due to Donald J Newman.

For each real number $x$ consider an (infinite) sequence of rationals $R_x = \{r_{x1}, r_{x2}, \cdots \}$ which converges to $x$.

For $x \neq y$, $R_x$ and $R_y$ have at most finite intersection.

Thus the set $S = \{R_x : x \in \mathbb{R}\}$ is an uncountable collection of infinite subsets of a countable set, none of which is a subset of other. In fact, any two members of the collection have only a finite intersection.