0
$\begingroup$

Iam supposed to prove that the set $\mathbb{Z}_+ \times \mathbb{Z}_+$ is countable by first constructing a bijective function $f: \mathbb{Z}_+ \times \mathbb{Z}_+ \to A$ where $A$ is the subset of $\mathbb{Z}_+ \times \mathbb{Z}_+$ consisting of pairs $(x,y)$ with $y \leq x$, and then constructing a bijective function $g: A \to \mathbb{Z}_+$

I have tried several functions for $f$ but cant find one, any hints?

$\endgroup$
2
  • 1
    $\begingroup$ HINT: Search the website. $\endgroup$
    – Asaf Karagila
    Commented Oct 12, 2014 at 1:16
  • $\begingroup$ @AsafKaragila didnt find for this question, can you link? $\endgroup$
    – user117449
    Commented Oct 12, 2014 at 1:21

3 Answers 3

0
$\begingroup$

try

$f:\mathbb{Z}_+\times \mathbb{Z}_+ \rightarrow A$

$ (x,y)\rightarrow (x+y,x)$

$\endgroup$
0
$\begingroup$

I'll make it a hint, as you asked for one but it's pretty straightforward:

What does $f$ have to do to $x$ if it doesn't change $y$?

$\endgroup$
0
$\begingroup$

Hopefully this helps:

The set $A=\{(n,m):0\le m \le n\}$ is countable.

Define the sequence $a_0=0$, $a_{n+1}=a_n+n+1$. Using induction you can verify that $a_n$ is increasing. Now define $f:A\to N$ as follows $f(n,m)=a_n+m$ (you need to check that this $f$ is injective).

So there is a bijection from $A$ to $f(A)$. But the latter is a subset of $\mathbb{N}$, this means that is countable or finite (why?). But $A$ is clearly not finite. Hence is countable.

Corollary: the set $\mathbb{N}\times \mathbb{N}$ is countable. Since $A$ is countable so $B=\{(n,m): 0\le n\le m\}$ is (let $g$ the map which switches $n$ and $m$, and shows that is a bijection).

Thus $\mathbb{N}^2$ is countable since is the union of $A$ and $B$.

$\endgroup$

You must log in to answer this question.