Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
You mean (2)...cartesian product of two countable sets is countable , and also (3)..the countable union of countable sets is countable. And then yes: that would do the trick. –  DonAntonio Aug 30 '12 at 3:48
2  
$\Bbb N$ is countable pretty much by definition. You really need only to show that $\Bbb Z$ is countable, which is, as you say, pretty easy, and that the Cartesian product of two countable sets is countable; then it follows immediately that $\Bbb Z\times\Bbb Z$ is countable. You don’t need (3) at all. –  Brian M. Scott Aug 30 '12 at 3:50
    
Yes, that is what I mean. Thanks! –  Kevin Aug 30 '12 at 3:51
    
For $(2)$, the Cantor pairing function, or some other similar tool, is useful. –  André Nicolas Aug 30 '12 at 4:02
    
I have the feeling that your problem is the same as (2), or even easier. Anyway, just think about how you would count grid points in the plane from the origin, expanding out as slowly as possible. –  Tunococ Aug 30 '12 at 6:00

1 Answer 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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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