2
$\begingroup$

I'm new to this community and I was wondering if this is a valid way to solve the following problem:

I have to prove that the set of all pairs of integers in a cartesian plane are countable. So would it be valid to prove this in the following manner:

  1. Prove that $\mathbb N$ and $\mathbb Z$ are countable (this should be easily mapped)
  2. Prove that the Cartesian Product of two countable sets are countable
  3. Then prove that the countable union of sets are countable

so... ex: In the cartesian plane, all the positive pairs would be $\mathbb N \times\mathbb N$

Also, I was referred to the Cantor pairing function. I read up on the Wikipedia article but I wasn't exactly sure how they applied to my case.

  • 0
    This has been covered on the site more than several times before.2012-09-04

1 Answers 1

1

As noted in the comments, you don't need $3$, and you can prove $2$ by showing that $\mathbb N \sim \mathbb N \times \mathbb N$.

To show $1$, consider the function:

$f(n) = \begin{cases} k &: n = 2k \\ -k &: n = 2k-1 \end{cases}$

If $f(n) = f(m)$, then $n$ and $m$ must be both even or both odd. Thus, $m=n$ follows almost immediately.

To show $2$, you only need to show an injection $\mathbb N \times \mathbb N \to \mathbb N$; the bijection will then follow from the Schroeder-Bernstein theorem.

The Cantor pairing function provides precisely the injection desired.

$g(m,n) = (m+n)^2 + n$

If $g(m,n) = g(p,q)$, notice that:

$(m+n+1)^2 - (m+n)^2 = 2(m+n) + 1 > n,q$

So $p+q < m+n+1$ and similarly, $m+n < p+q+1$. So $m+n = p+q$. Substituting and cancelling, $n=q$ and $m=p$. Injectivity is proved, as desired.