Possible Duplicate:
Countable Sets and the Cartesian Product of them
Sum of two countably infinite sets

I want to solve a problem, this problem is the following:

Prove that if the sets $A$ and $B$ are countable then these sets are also countable:

  1. $Α \cap B$
  2. $A \cup B$
  3. $A \times B$ (Cartesian product of $A$ and $B$)

Thank you very much.


marked as duplicate by Asaf Karagila, t.b., Austin Mohr, Martin Sleziak, Zhen Lin Jan 7 '12 at 8:54

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 4
    $\begingroup$ Does "numerous" mean "countable"? $\endgroup$ – Srivatsan Jan 5 '12 at 0:47
  • $\begingroup$ Does "acts of" mean "operations on"? $\endgroup$ – joriki Jan 5 '12 at 1:39
  • $\begingroup$ @Srivatsan: I think "numerous" does mean "countable" because the result is true if it does and false if it means "uncountable"! $\endgroup$ – Clive Newstead Jan 5 '12 at 2:11
  • 1
    $\begingroup$ @Srivatsan OP probably intended "denumerable", which is sometimes used to mean "countably infinite". $\endgroup$ – Austin Mohr Jan 5 '12 at 4:15
  • $\begingroup$ I also believe that should be an uncountable collection of answers on this site in which those questions were answered. I know that the search function sucks, but even "countable product" should give you your desired thread. $\endgroup$ – Asaf Karagila Jan 5 '12 at 7:47

Suppose $A$ and $B$ are countable.

Let $f:A \to \mathbb{N}$ and $g:B \to \mathbb{N}$ be injective maps, which exist by countability. To show that each of your sets is countable, it suffices to find an injection from the sets into the natural numbers.

$A \cap B \subseteq A$, so $f|_{A \cap B} : A \cap B \to \mathbb{N}$ is injective.

$A \cup B = (A \smallsetminus B) \cup B$, so we can define $h : A \cup B \to \mathbb{N}$ by defining $h(x)$ to be either $2f(x)$ or $2g(x)+1$, depending on whether it lies in $A \smallsetminus B$ or $B$. I leave the detail of proving that this is a well-defined injective function to you.

We can define $h : A \times B \to \mathbb{N}$ by $h(x,y) = 2^{f(x)}3^{g(x)}$. I again leave you to check that this is a well-defined injective map. Note that it makes use of the fundamental theorem of arithmetic.


Clive has taken a standard approach. It's standard to show you have an injection from the set mapping to the natural numbers - that then means you can make a bijection. Here's a constructive approach;

$A\setminus B \cup B = A \cup B$ but the LHS is made up of disjoint sets. Taking your (known?) bijection from the integers and the natural numbers, could you find a bijection between A\B U B and $\mathbb N$ ?

Now, we can prove every subset of a countable set is countable - how? Let Z be a subset of the countable set Y, where $f: \mathbb N \rightarrow Y$ is a bijection. Then Z is finite or infinite - we can assume it's infinite (why)?

Consider $ \{ n | f(n) \in Z \}$ - is that an empty subset of the natural numbers? What is it's least element? Call it x (that is x is the least element).

Now, look at $ \{ n | f(n) \in Z \}$ \ $ \{x \}$ - what is this set's least element? Why can't it be x also? Do you think you could find a bijection?

Does that mean A n B will be countable?

To construct a bijection between $ \mathbb N x \mathbb N $ and $\mathbb N$ is non-trivial (why do we need only find a bijection for $ \mathbb N x \mathbb N $ and not AxB?) in the sense it relies on a little trick. Draw a plane and start ticking off lattice points (points where oordinates are integers). Put your pen on the origin and draw a line to (1,1) - now down to (1,0) then (1,-1), (0,-1), (-1,-1), (-1,0), (-1,1) finally (0,1) - where should we go next? Is there a 'formula' for such a route?

  • $\begingroup$ "unfortunately has a couple of errors": Could you please be more specific? I don't understand what the second sentence means, particularly how it finishes with "to let you have some countable set". When you wrote "{ n | f(n) is in Z}", did you mean $\{n:f^{-1}(n)\in Z\}$, a.k.a. $f(Z)$? Is there something missing between "{ n | f(n) is in Z}" and "{x}"? $\endgroup$ – Jonas Meyer Jan 5 '12 at 2:41
  • $\begingroup$ @Jonas: FWIW, the error in my answer was corrected. But still, I've voted +1 because I like Adam's way of explaining the thought processes behind finding the maps into $\mathbb{N}$. Adam, you might want to use $\LaTeX$ to make the notation a bit clearer? $\endgroup$ – Clive Newstead Jan 5 '12 at 2:41
  • $\begingroup$ Yes, I want to but { always goes invisible if you use dollar signs [I will go back and mathbb sets). No, Jonas I mean if Z is a subset of Y look at {n | f(n( is an element of Z} - unfortunately I wrote the bijection from Y to Z where it should (obviosuly) be N to Z. $\endgroup$ – Adam Jan 5 '12 at 2:58
  • $\begingroup$ I also regret using Y and Z (I did that to avoid recycling A and B, though on second thought I perhaps should not have done this - I hope you realise this is a forum, and swiftness / explanations / accuracy / layout are on a trade-off) [this isn't a attack on anyone, simply a general comment that it takes longer to correctly type out an argument than say a stream of words]. $\endgroup$ – Adam Jan 5 '12 at 3:04
  • 2
    $\begingroup$ @Adam: Unfortunately (, [ and < are just about as common as { in mathematics, but without some way of enclosing data in brackets, a scripting language such as $\LaTeX$ isn't much use! $\endgroup$ – Clive Newstead Jan 5 '12 at 3:18

Not the answer you're looking for? Browse other questions tagged or ask your own question.