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
    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.2012-08-30
  • 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.2012-08-30
  • 0
    Yes, that is what I mean. Thanks!2012-08-30
  • 0
    For $(2)$, the Cantor pairing function, or some other similar tool, is useful.2012-08-30
  • 0
    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.2012-08-30
  • 0
    This has been covered on the site more than several times before.2012-09-04

1 Answers 1