0
$\begingroup$

Can you define a simple bijective function from $\mathbb{N}$ to $\mathbb{N}_k\times \mathbb{N}$ (or from $\mathbb{N}$ to $\mathbb{N}\times\mathbb{N}_k$)?
P.s.: $\mathbb{N}_k=\{1,2,3,\cdots, k\}$

$\endgroup$
10
  • $\begingroup$ FYI, your $\mathbb{N}_k$ is normally written as $[k]$ in combinatorics. $\endgroup$
    – Chappers
    Commented Sep 13, 2015 at 17:20
  • $\begingroup$ uhm - yes. Start, e.g., by mapping $\{1,2,\ldots, k\}$ to $(1,1), (2,1), \ldots (k,1)$ (if you start counting in $\mathbb{N}$ at $1$) $\endgroup$
    – Thomas
    Commented Sep 13, 2015 at 17:23
  • $\begingroup$ @Thomas: Is $f(n)=(n,1), \quad \forall n\in \mathbb{N}$ bijective? $\endgroup$
    – Sisabe
    Commented Sep 13, 2015 at 17:33
  • $\begingroup$ No. The next step would be to map $k+1$ to $(1,2)$, then, $k+2$ to $(2, 2)$ and ($\ldots$) $2k$ to $(k,2)$. Then $ 2k+1$ to $(1,3)$, $2k+2$ to $(2,3)$. Can you recognize the pattern? $\endgroup$
    – Thomas
    Commented Sep 13, 2015 at 17:37
  • $\begingroup$ @Thomas: I'd like to have a formula for $f$. Can you give me one? $\endgroup$
    – Sisabe
    Commented Sep 13, 2015 at 17:42

1 Answer 1

3
$\begingroup$

Hint: modular arithmetic provides an essentially trivial function.

(In particular, the Euclidean division algorithm produces, for each $n \in \{0,1,2,3,\dotsc\}$, a unique $q \in \{0,1,2,3,\dotsc\}$ and $r \in \{ 1,2,3,\dotsc,k-1 \}$ so that $n=qk+r$. You can then fiddle this around to get the particular bijection you want.)

$\endgroup$
3
  • $\begingroup$ This is what I had in mind, too. :-) +$1$ $\endgroup$
    – Clayton
    Commented Sep 13, 2015 at 17:23
  • 1
    $\begingroup$ @Clayton Perhaps we should think outside the box a bit more ... :) $\endgroup$
    – Chappers
    Commented Sep 13, 2015 at 17:25
  • $\begingroup$ Could you please give me an example? $\endgroup$
    – Sisabe
    Commented Sep 13, 2015 at 17:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .