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.

Let $X= \{ A \subset \mathbb{N} : \mathbb{N} \backslash A \text{ is finite}\}$. What is the cardinality of $X$? Prove it.

For me the cardinality should be the same as the natural numbers. I am trying to show a way of ordering it, the first A is one with the smallest numbers and so on.

share|improve this question
add comment

3 Answers

up vote 4 down vote accepted

Hint: Note that $f(A)=\Bbb N\setminus A$ is a bijection from $X$ to $\text{Fin}(\Bbb N)=\{A\subseteq\Bbb N\mid A\text{ is finite}\}$.

(If you haven't seen that $\text{Fin}(\Bbb N)$ is countably infinite before, you can demonstrate an injection into $\Bbb N$ by mapping $\{a_1,\ldots,a_k\}$ to $p_{a_1}\times\cdots\times p_{a_k}$, where $p_i$ is the $i$-th prime number.)

share|improve this answer
add comment

$X$ can be placed into 1-1 correspondence with the finite subsets of $\mathbb{N}$. This is countable, so $X$ is countable.

share|improve this answer
add comment

Hint:

1) There is one subset of the naturals without the number $\,1\,$ , also one subsets of the naturals without the number $\,2\,$ ...etc.

2) There is one subset without the numbers $\,1,2\,$ ,also one without $\,1,3\,$ ...

...................................

Thus, there are $\,\aleph_0\,$ subsets of the natural without one element since if $\,S^{(1)}\,$ is the subset of $\,\mathcal P(\Bbb N)\,$ containing all these subsets, then if

$$S_k:=N-\{k\}\Longrightarrow S^{(1)}=\bigcup_{k=1}^\infty S_k$$

...and etc.

share|improve this answer
add comment

Your Answer

 
discard

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.