4

Let $T=\{(a,b)\mid a,b\in\mathbb Z_+, b\leq a\}.$ Find a bijective function $f: T \to \mathbb{Z}_+$

I have tried to find a function but I can't, how does such function look like?

Austin Mohr
  • 25,662
Matt
  • 41

2 Answers2

1

(1): $(1,1)$

(2):$(2,1)\ \ \ (2,2)$

(3):$(3,1)\ \ \ (3,2) \ \ \ (3,3) $

$\ldots$

($k$):$(k,0)\ \ \ (k,1) \ \ \ (k,2)\ \ \ \ldots \ \ (k,d)\ \ \ldots (k,k)$

$\ldots$

define $f$ by $f(1,1)=0$ , $f(2,1)=1$ , $f(2,2)=2$ , $f(3,1)=3$ $\ldots$ that is

Take $f(k,d)=1+\ldots+(k-1)+(d)-1=k(k-1)/2+d-1$

Hamou
  • 6,745
0

My bijection won't be explicit, but I typically try to place some kind of order on the sets and place them "side by side".

The set $\mathbb{Z}_+$ already has a natural order on it.

We can order $T$ as follows. For each $n \geq 2$, let $T_n$ contains all ordered pairs from $T$ whose coordinates sum to $n$. Order each $T_n$ lexicographically, and then order $T$ by concatenating all these orders.

With these orders in mind, my bijection would therefore be to map $n$ to the $n^\text{th}$ element of $T$. The first few such mappings are

\begin{align*} 1 &\mapsto (1,1)\\ 2 &\mapsto (2,1)\\ 3 &\mapsto (2,2)\\ 4 &\mapsto (3,1)\\ 5 &\mapsto (3,2)\\ 6 &\mapsto (4,1) \end{align*}

When choosing the order on $T$, it is important to ensure that any element is reached in a finite amount of time. For example, the order $(1,1) < (2,1) < (3,1) < (4, 1) < \cdots$ is not viable since it takes an infinite amount of time to reach $(2,2)$.

Austin Mohr
  • 25,662
  • The elements (1,2) and (1,3) doesnt even exist in $T$. – Matt Oct 12 '14 at 19:59
  • Its ok. You have missed a 2 in the way you defined the function and also the arrow should be the other way, its a function from $T$ to $\mathbb{Z}_+$. THanks for your help – Matt Oct 12 '14 at 20:04
  • @Matt I see the typo involving 2. Thank you. As for the direction of the arrow, it makes no difference since we are proposing a bijection. I specifically reversed it since it is more natural to say "the first element of $T$, the second element of $T$, ...". – Austin Mohr Oct 12 '14 at 20:08