Let $X$ be a countable set. Let $A \subset X$.

How can I prove that if $A$ is finite then $X \setminus A$ is countable?

I started off by supposing that $X \setminus A$ is finite and then need to show that this leads to a contradition.

The result that $X \setminus A$ is countable will then follow because all subsets of $X$ are countable or finite

  • $\begingroup$ Every subset of a countable set is countable, so I suspect that by countable you really mean countably infinite. HINT: What do you know about the union of two finite sets? $\endgroup$ – Brian M. Scott Dec 2 '14 at 22:19

Suppose for the sake of contradiction that $X- A$ is finite. What does that imply about $(X-A) \cup A$?

  • $\begingroup$ I believe that this implies #(X−A)∪A = #A + #(X-A) but I'm not sure what this means in the context of finding a contradiction that X-A is not finite $\endgroup$ – user131215 Dec 2 '14 at 22:26
  • $\begingroup$ Let's pretend these sets are numbers. What is $(x-y)+y$? $\endgroup$ – graydad Dec 2 '14 at 22:27
  • $\begingroup$ $(x-y)+y=x$. Similarly, $(X-A)\cup A = X$. So we have expressed $X$ as the union of two finite sets. Is that kosher? $\endgroup$ – graydad Dec 2 '14 at 22:40
  • $\begingroup$ I'm still not sure where the contradiction comes in? $\endgroup$ – user131215 Dec 3 '14 at 17:45
  • $\begingroup$ $X$ is infinite. Yet we've expressed $X$ as the union of two finite sets. The union of two finite sets is finite. So $X$ must be finite. $\endgroup$ – graydad Dec 3 '14 at 18:52

Let $X$ be a countable set.

Therefore, there exists an injective function $f:X\to \mathbb{N}$

By definition of injective, we have $\forall a,b\in X:[f(a)=f(b)\implies a=b] $

Let $A \subset X$.

Let $g$ be a function $g:X \setminus A \to \mathbb{N}$ such that $\forall a\in X\setminus A: g(a)=f(a)$

  1. Suppose $x,y\in X\setminus A$

  2. By definition of $\setminus$, we have $x,y \in X$

  3. Suppose $g(x)=g(y)$

  4. By definition of $g$ ,we have $g(x)=f(x)$

  5. By definition of $g$ ,we have $g(y)=f(y)$

  6. $f(x)=f(y)$ (substituting 4 and 5 into 3)

  7. $x=y$ (from 2 and since $f$ is injective)

  8. $g(x)=g(y)\implies x=y$ (conclusion from 3 and 7)

  9. $\forall a,b \in X\setminus A: [g(a)=g(b) \implies a=b]$ (conclusion from 1 and 8)

  10. $g$ is an injective function $g:X\setminus A\to \mathbb{N}$ (from 9 and definition of $g$)

  11. By definition, $X\setminus A$ is countable (regardless of whether $A$ is finite)

  • 1
    $\begingroup$ Please read the OP and my comment again. It seems that OP is using the word "countable" to mean "countably infinite." And yes, there are references that use the word "countable" to mean "countably infinite" rather than "countably infinite or finite." $\endgroup$ – Braindead Dec 11 '14 at 15:32
  • 1
    $\begingroup$ You are not understanding my comments. Try replacing the word "countable" in OP with "countably infinite." Also look at the comment by Brian M. Scott. $\endgroup$ – Braindead Dec 11 '14 at 16:06
  • 1
    $\begingroup$ That is exactly what I have been saying this entire time. If you read the entire post (and not just the first two lines), it's pretty apparent that when OP says "countable" he really means "countably infinite." $\endgroup$ – Braindead Dec 11 '14 at 16:58
  • 1
    $\begingroup$ And here, I repeat myself: There are references that use the word "countable" to mean "countably infinite" rather than "countably infinite or finite." $\endgroup$ – Braindead Dec 11 '14 at 17:00
  • 1
    $\begingroup$ See wikipedia's entry on "Countable set." $\endgroup$ – Braindead Dec 11 '14 at 17:08

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.