For each of the following sets, determine if it is finite, countably infinite, or uncountable. You need not prove your answer is correct, but you should give a reason for your response.

  1. For some $n\in\mathbb{N}$, $\{(a_1, a_2, \dots, a_n)\in\mathbb{N}^n\ | \ a_1+a_2+\dots+a_n<5000\}$
  2. $\{S\in\mathcal{P}(\mathbb{N})\ | \ \mathbb{N}\backslash S\hbox{ is finite}\}$
  3. $\{x\in \mathbb{R}\ | \ \hbox{there is a decimal expansion of $x$ with only even digits}\}$

For #1, I said that it is finite. Since every $a_i \in \mathbb{N}$, every $a_i \leq 5000$. Combinations of a finite set of numbers must also be finite.

For #2, I said that it is countably infinite. To make $\mathbb{N}\backslash S$ finite, $S$ would have to be an infinite subset of $\mathbb{N}$, of which are infinite. Therefore the initial set is infinite. Since $\mathbb{N}$ is countably infinite, we can reason that the initial set is also countably infinite.

For #3, I said that it is uncountable. An argument can be made with Cantor's diagonalization method to show that a list of real numbers with decimal expansions with only even digits can never be complete and the set is therefore uncountable.

Do my arguments make sense/ are my conclusions correct?


The each claim is correct. I would express the first argument as "since the set's cardinality is at most $5000^n,$ then the set has finite cardinality," or something similar.

Your argument for the second is hard to make sense of, unfortunately. I would say, rather, that $\Bbb N$ has countably-infinitely-many finite subsets (as a countable union of countable sets is countable), so it has countably-infinitely-many subsets with finite complements.

  • $\begingroup$ Let $\mathscr S$ be the set defined in $2$. Then there is a $1-1$ correspondence between finite subsets of $\Bbb N$ and elements of $\mathscr S$. Since there are countably many finite subsets of $\Bbb N$, then there are also countably many elements of $\mathscr S$. This is a slightly more precise way of saying the second paragraph in this answer. $\endgroup$ – Robert Shore Apr 9 at 2:48
  • $\begingroup$ @Robert - True. $\endgroup$ – Cameron Buie Apr 9 at 2:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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