- Show the set $A=\{(m,n)\in N\times N : m\leq n\}$ is countably infinite. 
*

*Show the set $A=\{(m,n)\in N\times N : m\leq n\}$ is countably infinite.


If $A$ is countable then we need to show that there is a bijection between $A$ and $\mathbb{N}$, but how can I show $A$ is countably infinite? 
Thanks...
 A: Note that $A$ can be written as 
$$
A = \bigsqcup_{n \in \mathbb{N}}\{(m,n) : m \leq n\}.
$$
That is, $A$ is the disjoint countable union of sets $F_n = \{(m,n) : m \leq n\}$. These are finite: for a fixed $n$, the set $F_n$ has $n$ elements, namely $(1,n) , (2,n) \dots, (n,n)$. Thus $A$ is a countable union of countable sets, which says that $A$ itself is countable. 
To see that is is infinite, observe that the mapping $d : n \in \mathbb{N} \mapsto (n,n) \in A$ is injective, and so $A$ cannot have a finite amount of elements.
A: I'll throw in a couple of approaches:
Quick Approach
If anything goes in terms of premises then we know a couple of things:


*

*Subsets of countable sets are countable

*$\mathbb{N}\times\mathbb{N}$ is countable

*$A$ is a subset of $\mathbb{N}\times\mathbb{N}$

*$A$ is infinite, see Guido's answer.


Bijective Approach
While this isn't necessary to show that $A$ is countably infinite, but there is a mapping between $N$ and $A$. Namely for some $(m,n) \in A, x\in\mathbb{N}$ then $(m,n) = (\lceil\frac{\sqrt{8 x+1}-1}{2}\rceil-x+1,\lceil\frac{\sqrt{8 x+1}-1}{2}\rceil+1)$ and of course the other way is $x=\frac{n(n-1)}{2}+m$
