3
$\begingroup$

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

$\endgroup$
  • 3
    $\begingroup$ There is a bijection between finite sets and cofinite sets given by $S \rightarrow S^c$ $\endgroup$ – Dylan Yott Jan 28 '15 at 1:10
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Wow, this was really intuitive. Thank you so much David. Can I ask what made you come up with the intuition of the way you made that list? Is this method of counting or constructing a set a common tool? Again, thank you! $\endgroup$ – Valentino Jan 28 '15 at 1:48
  • 2
    $\begingroup$ The key thing is the bit about avoiding getting "stuck" in the list. You have probably seen the proof of the enumerability of positive rationals by placing them in an array and going along the diagonals - the point is that if you went along the rows, then you would never finish the first row so you would never list the second and subsequent rows. This problem is similar. There are possible variations: for example, instead of taking the sum of $k$ to be $0,1,2,\ldots$, you could take the maximum to be $0,1,2,\ldots$, giving a different but equally valid list. $\endgroup$ – David Jan 28 '15 at 2:30
0
$\begingroup$

if $s_0, s_1, \dots$ is an enumeration of $S$ then if $C(S)$ denotes the set of cofinite subsets of $S$ construct the function $\beta:C(S) \to \mathbb{N}$: $$ \beta(T) = \sum_{s_j \not \in T} 2^j $$ by the definition of a co-finite set this sum is always well-defined and finite, and $\beta$ is easily shown to be injective

$\endgroup$

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.