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.

  • 4
    Does "numerous" mean "countable"?2012-01-05
  • 0
    Does "acts of" mean "operations on"?2012-01-05
  • 0
    @Srivatsan: I think "numerous" does mean "countable" because the result is true if it does and false if it means "uncountable"!2012-01-05
  • 1
    @Srivatsan OP probably intended "denumerable", which is sometimes used to mean "countably infinite".2012-01-05
  • 0
    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.2012-01-05
  • 0
    @Austin Ah, yes. I'm not very used to the word, so it did not occur to me unfortunately. That would fit, except that the intersection of two countably infinite sets need not be countably infinite. Let's hope the OP clarifies. :)2012-01-05
  • 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
    "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}"?2012-01-05
  • 0
    @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?2012-01-05
  • 0
    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.2012-01-05
  • 0
    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].2012-01-05
  • 0
    @Adam: To make { appear you need to write \{. For example, $\{ n \, :\, f(n) \in \mathbb{Z} \}$. And for the arrow you can write \rightarrow which gives $\rightarrow$ rather than $->$. The [Wikipedia page](http://en.wikipedia.org/wiki/Wikipedia:MATH) on $\LaTeX$ is useful.2012-01-05
  • 0
    @Adam: Put a backslash before `{` and `}` to have them show up. E.g., `$\{x\}$` gives you $\{x\}$. As Clive pointed out, there had been an error, but it was corrected well before you posted your answer. I will edit out that comment.2012-01-05
  • 0
    As mentioned, it takes a little time to type out a response - when I began to type it was there. It perhaps looks better now, it is quite a poor design that \ is required when typing { - common symbol, though I think I'll survive.2012-01-05
  • 2
    @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!2012-01-05
  • 0
    @CliveNewstead: incidentally, `\to` is a much shorter way of writing $\to$.2012-06-04
  • 0
    @benmachine: Odd, I always use \to (even in my answer above). I wonder why I didn't suggest it.2012-06-04