Can someone verify this. I am confused because I am not sure if I am being asked to strictly construct a bijection or not, although that is probably the case. The thing that confuses me is that I am not sure what "countable" means-- even on StackExchange people will say different things. Is countable a bijection from a set to the natural numbers? Is it an injection from the natural numbers to a set?

Am I supposed to talk about cardinality? Functions? What about the theorem that subsets of a countable set are countable?

Let us assume $A$ is countable and $B$ is a finite subset of $A$.

$A$ is countable which means it is either finite, or countably infinite.

If $A$ is finite, then $(A-B)$ is clearly finite (and countable) since the difference of two finite sets is finite.

If $B = \emptyset$, then $(A-B) = A$, which is countable so $(A-B)$ is countable.

Let us consider the case where $A$ is countably infinite.

Consider an arbitrary element $x \in (A-B).$

$\implies x \in A \land x \notin B$.

So $x\in A$.

It follows that $\forall x \in (A-B), x \in A \implies (A-B) \subseteq A$.

We can assume $(A-B) \neq A$ because $A$ is countably infinite and $(A-B)$ is finite, so $(A-B) \subset A$.

Suppose we define an injection $f$ as $f:A \rightarrow \mathbb{N}$.

Since $(A-B) \subset A$ we can from that derive an injective function $g: (A-B) \rightarrow A$.

We can compose these two injective functions as $g \circ f: (A-B) \rightarrow \mathbb{N}$.

  • $\begingroup$ Note that $|A-B|\le |A|,$ and hence $ \le \omega$, i.e., it is countable. $\endgroup$ – Paul May 20 '16 at 3:32

Conceptually, I think you have the idea. Just note "$A$ is countable" does not mean $\# A = \# \mathbb{N}$, but that $A$ admits a bijection to a subset of $\mathbb{N}$, so $\# A \leq \# \mathbb{N}$. Now to actually prove the claim, simply take your bijection and construct new one out of it by removing the elements of $B$.

  • $\begingroup$ I thought that $\#A \leq \#B$ for two sets $A$ and $B$ meant that there was an injection from $A \rightarrow B$? (which may or may not be a bijection). $\endgroup$ – J00S May 20 '16 at 4:26
  • $\begingroup$ I also thought that $\#A < \#B$ meant there was strictly an injection (not a bijection). $\endgroup$ – J00S May 20 '16 at 4:27
  • 1
    $\begingroup$ you are correct. But the two definitions are equivalent. An injection from $A$ to $B$ means one can construct to a bijection from $A$ to a subset of $B$ (this subset is just the image). $\endgroup$ – GiantTortoise1729 May 20 '16 at 15:44
  • $\begingroup$ How about this? $g$ as $g: (A-B) \rightarrow (\mathbb{N}-\{f(b):$ for some $b \in B\})$ $\endgroup$ – J00S May 21 '16 at 21:49
  • $\begingroup$ exactly. just make sure you're rigorous about defining everything. $\endgroup$ – GiantTortoise1729 May 21 '16 at 22:47

If $f:A \to \mathbb{N}$ is injective, $f:S\to \mathbb{N}$ is injective where $S \subset A$. Can you see why?

  • $\begingroup$ Well, $B$ being a finite subset of another set $A$ means there is an injection from $B$ to that set $A$, right? $\endgroup$ – J00S May 20 '16 at 4:28
  • $\begingroup$ Is there something like a set $A \approx \mathbb{N}$, $(A-B) = A - \{b \in B\}$, $(A-B) \approx (\mathbb{N} - \{n \in \mathbb{N}\}$, $\mathbb{N} \approx (\mathbb{N} - \{n \in \mathbb{N}\})$ $\implies (A-B) \approx \mathbb{N}$ $\endgroup$ – J00S May 20 '16 at 4:32
  • $\begingroup$ Is this because there is an injection from $S$ to $A$, and you can compose the two functions to create an injection from $S$ to $\mathbb{N}$? The thing that confuses me here is that there are conflicting definitions of "countable" I am getting. Some say it is a bijection to the natural numbers others tell me it is the other way around, or that it is an injection to the natural numbers...? $\endgroup$ – J00S May 21 '16 at 20:29

Hint: Since $A$ is countable, there is a bijection from $A$ to $\mathbb N$.

Using this, show that there is a way to enumerate $A$ as $(a_n)_{n < \omega}$ such that $B = (a_n)_{n < m}$ for some finite $m$.

This then gives a fairly natural bijection of $A \setminus B$ to $\mathbb N$.


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.