Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 12 down vote accepted

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

share|cite|improve this answer
So this is the even and odd numbers? Aren't they countable? – PEV Nov 28 '10 at 16:27
never mind, $C$ is the power set. – PEV Nov 28 '10 at 16:30

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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