I've been having some trouble with this question. In fact, I spend a long time on a solution which I came to realize the next day it was entirely wrong. I feel completely stumped, and I could really use a hint or some help. My class has only covered enumerability and some basic set theory, and I've actually had fun and answered almost all similar problems I've been faced with in class except this one. I would be honored if someone out there could shoot me a hint or give me a nudge in the right direction.
Let $S$ be an enumerable set. A subset $A\subseteq B$ is cofinite iff $S-B$ is finite. Then it can be said that the set of all cofinite subsets of $S$ is enumerable.
Okay, after I realized I completely butchered my original solution I went back to think about what it was that I found difficult about this problem. I know that $|S-B|=n$, that the function $f:S\rightarrow \mathbb{N}$ is bijective (by definition of enumerability), and we want to prove that that the set $X$ of all cofinite subsets forms a one-to-one correspondence with the natural numbers. However, I'm having a difficult time discovering gap between how $|S-B|=n$ helps me construct new set $X$, let alone show that it is countable.
Thank You
Best Answer
Informally, a set is enumerable if and only if you can list its elements. You can list all finite subsets of $$S=\{a_1,a_2,a_3,\ldots\}$$ by writing down all the sets containing elements $a_k$ with the $k$s adding up to $0$, then all those with the $k$ adding up to $1$, then $2$, then $3$ and so on. As there are only finitely many sets in each category, the list never gets "stuck". So we would begin with $$\varnothing\ ,\quad \{a_1\}\ ,\quad \{a_2\}\ ,\quad \{a_1,a_2\}\ ,\quad \{a_3\}\ ,\quad \{a_1,a_3\}\ ,\quad \{a_4\}$$ and so on. Then the cofinite sets are just the complements of these: $$\varnothing^c\ ,\quad \{a_1\}^c\ ,\quad \{a_2\}^c\ ,\quad \{a_1,a_2\}^c\ ,\quad \{a_3\}^c\ ,\quad \{a_1,a_3\}^c\ ,\quad \{a_4\}^c\ ,\ldots\ .$$ Since we have listed all the elements of the set of cofinite subsets of $S$, this set is enumerable.