0
$\begingroup$

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.

  • 0
    The part about union of two sets is basically the same as [Sum of two countably infinite sets](http://math.stackexchange.com/questions/85612/sum-of-two-countably-infinite-sets)2012-01-07

2 Answers 2

5

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.

1

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?

  • 0
    @benmachine: Odd, I always use$\to$(even in my answer above). I wonder why I didn't suggest it.2012-06-04