I know that $\mathbb{N}$ is countably infinite and that countability infinite sets can be split into countably infinite subsets.

$\mathbb{N} \times \mathbb{N}$ = $\{(n,n) |$ $\forall n \in \mathbb{N}\}$

Can I describe this as the union of two pairwise disjoint subsets of the ordered pairs of even numbers and those of odd numbers?


$\{(2,2), (4,4), (6,6), ... (m,m)\}$ $\forall m \in \mathbb{N}_m$ where $\mathbb{N}_m$ is the set of all even natural numbers.

$\{(1,1), (3,3), (5,5), ... (n,n)\}$ $\forall n \in \mathbb{N}_n$ where $\mathbb{N}_n$ is the set of all odd natural numbers.

Surely the union of these two sets is equivalent to $\mathbb{N} \times \mathbb{N}$?

I also have to show that the union of pairwise disjoint countably infinite sets are countably infinite.

  • 7
    $\begingroup$ $\mathbb N \times \mathbb N$ is not $\{ (n, n) : n \in \mathbb N \}$. It is $\{ (n, m) : n, m \in \mathbb N\}$. If your question pertains to $\mathbb N \times \mathbb N$, you could write $\mathbb N \times \mathbb N = \bigcup_{n \in \mathbb N} \{ (n, m) : m \in \mathbb N \}$, which is a countably infinite union of countably infinite sets. $\endgroup$ – Jon Warneke May 22 '16 at 1:18
  • $\begingroup$ You seem to have omitted $(1,4)$ and $(2,3)$. $\endgroup$ – MJD May 22 '16 at 1:30
  • $\begingroup$ How can I show that such a set like that given in your example is countably infinite? More specifically how do I prove surjectivity? I can probably figure out injectivity. $\endgroup$ – J00S May 22 '16 at 3:49
  • 1
    $\begingroup$ You seem to have asked the wrong question. It is obvious that $\mathbb{N}\times\mathbb{N}$ is the union of a countable infinity of countably infinite sets. But your real question seems to be: why is $\mathbb{N}\times\mathbb{N}$ countable? $\endgroup$ – almagest May 22 '16 at 5:40

The claim that the union of $\{(1,1),(3,3),...\}$ and $\{(2,2),(4,4),...\}$ is the same as $\mathbb{N}\times\mathbb{N}$ is false because you are ommiting pairs of the form $(e,o)$ and $(o,e)$, where $e$ is an even number and $o$ is an odd number, which clearly belong to $\mathbb{N}\times\mathbb{N}$.


The set NxN is the disjoint union of four infinite countable sets defined as classes equivalence by the equivalence relation: (n, m) R (n ', m') iff n and n 'have the same parity and m, m' have the same parity. This gives the following classes: cl(0,0) = {(n, m) in NxN such that n and m are even} cl (0.1) = {(n, m) in NxN such that n even and m odd} cl (1.0) and class (1,1).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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