2
$\begingroup$

This is a question from my proofs course review list that I have had trouble understanding.

I understand the concept of disjoint sets. I'm not sure what they mean by countable. How would one prove a set is countable and furthermore, that the union of two countable sets is countable.

Please help me get started with the question by understanding this concept.

$\endgroup$
  • $\begingroup$ Related: math.stackexchange.com/questions/647008/… $\endgroup$ – 6005 May 3 '14 at 20:16
  • $\begingroup$ You should probably be aware of what a countable set is. (Did you forget it ?) A countable set is just a set such that you can count its elements. Obvious for finite sets. For infinite sets, the trick is to establish a bijection between the set and $N$ (naturals). $\endgroup$ – Yves Daoust May 3 '14 at 20:18
  • $\begingroup$ Actually you just need an injective function from the set to $\Bbb N$ $\endgroup$ – Ellya May 3 '14 at 20:23
  • $\begingroup$ Here is the solution I had sent to me by peers: A: f : A->Z (one to one) B: g : B->Z (one to one) f x g = A x B = Z x Z = one to one = countable Can someone decipher this for me? $\endgroup$ – user122661 May 3 '14 at 20:26
7
$\begingroup$

A formal proof would be something like this. If $A$ and $B$ are countable (and disjoint) sets, then there exist injective functions $f$ and $g$ from $A$ and $B$, respectively, to $\mathbb{N}$. Let $C=A\cup B$ and define a function $h:C\rightarrow\mathbb{N}$ as follows:

$$h(z) = \begin{cases}2f(z) & \text{if } z\in A\\ 2g(z)+1 & \text{if } z\in B\end{cases}$$

Then, if $x\neq y$, we clearly have $h(x)\neq h(y)$ since if $x,y\in A$ this follows from the fact that $f$ is injective (analogously for $x,y\in B$) and if $x\in A$ and $y\in B$, we have that $h(x)$ is even while $h(y)$ is odd (analogously for $x\in B$, $y\in A$). Hence $h$ is an injective function from $C$ to $\mathbb{N}$ and thus, by definition, $C$ is countable.

$\endgroup$
2
$\begingroup$

(In the following, countable means what is often referred to as countably infinite, i.e. countable and not finite)

A set $A$ is called countable if there exists a bijection $f$ between $A$ and the set of natural numbers $\mathbb{N}$. In other words, $A$ is countable if there is some mapping $f \,:\, A \to \mathbb{N}$ such that $f$ hits every element of $\mathbb{N}$ exactly once. Note that any such $f$ has a uniquely defined inverse $f^{-1}$.

It follows that there exists a bijection $f_{A,B}$ between any two countable sets $A$ and $B$, because if $f_A$ is a bijection from $A$ to $\mathbb{N}$, and $f_b$ a bijection from $B$ to $\mathbb{N}$, then $x \mapsto f_B^{-1}(f_A(x))$ is a bijection from $A$ to $B$.

Therefore, to show that the union of two arbitrary disjoint countable sets is countable, it suffices to show that the union of two specific disjoint countable sets $A,B$ is countable. This works because if $X,Y$ are disjoint and countable, by the above there are bijections $f_X \,:\, X \to A$, $f_Y \,:\, Y \to B$, and a bijection $g \,:\, A \cup B \to \mathbb{N}$. We can therefore define a biection from $f \,:\, X \cup Y$ to $\mathbb{N}$ by setting $$ f(z) = \begin{cases} g(f_X(z)) &\text{if $z \in X$,} \\ g(f_Y(z)) &\text{if $z \in Y$.} \end{cases} $$ (I leave the proof that this actually is a bijection to you)

Since we can view $\mathbb{Z}$ as the disjoint union of $\mathbb{N} = \{0,1,\ldots\}$ and $\mathbb{Z} \setminus \mathbb{N} = \{\ldots,-2,-1\}$, it therefore suffices to

  1. show that $\mathbb{Z} \setminus \mathbb{N}$ is countable, i.e. to find a bijection between $\{\ldots,-2,-1\}$ and $\{0,1,\ldots\}$, and

  2. show that $\mathbb{Z}$ is countable.

$\endgroup$
  • $\begingroup$ By the way, the standard definition of countable also encompasses finite sets. $\endgroup$ – mathse May 3 '14 at 21:40
  • 2
    $\begingroup$ @mathse I hate the standard definition then ;-) But you're right, I should point out that my use of countable is what is often called "countably infinite". Will fix. $\endgroup$ – fgp May 3 '14 at 21:42
0
$\begingroup$

There are many ways to prove that set is countable. But the basic method is - enumerate it with some formula.

For example, two disjoint sets

$$A = \{2n-1\mid n-natural\}$$ $$B = \{2n\mid n-integer\}$$ enumerate it $$A_i=2i-1, i>0$$ $$B_i=2i$$ $A,B$ is countable. I say "$C = A\cup B$ is countable too". Formula will be not so simple as it was before, but it exist and easy to write.

$$C_i=\begin{cases} {i,i\gt0} \\{2i,i\le0}\end{cases}$$

Prove that every pair of disjoint countable sets gives another countable set in union.

$\endgroup$
  • $\begingroup$ This is a funny answer. How does it answer the question, though? It seems like your answer discusses a specific example (in an "odd" way, though) and then rephrases what the OP asks for. $\endgroup$ – mathse May 3 '14 at 21:47
  • $\begingroup$ @mathse I think specific examples usually helps for "understanding this concept". Anyway - those who read formulas with smile is my friends for life) $\endgroup$ – Ralor May 4 '14 at 4:12
  • $\begingroup$ Yes, your approach is funny and if it were to be a proof of the proposition in question, I would give it zero points. $\endgroup$ – mathse May 4 '14 at 7:54
  • $\begingroup$ @mathse I think you should give me zero points at least twice, because your answer seem to use the same idea. But you gave a solution, and I've tried to explain the concept (I wasn't able to give a solution like yours :D) $\endgroup$ – Ralor May 4 '14 at 8:09
  • 1
    $\begingroup$ @Ralor You only gave a single example. Examples cannot replace proofs. $\endgroup$ – user144248 May 4 '14 at 10: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.