Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Find explicit bijection from N to N x N

  1. Apr 27, 2010 #1
    1. The problem statement, all variables and given/known data

    Find a linear ordering of [tex]\mathbb{N} \times \mathbb{N}[/tex] and
    use it to construct an explicit bijection [tex]f : \mathbb{N} \to \mathbb{N} \times \mathbb{N}[/tex].

    2. Relevant equations



    3. The attempt at a solution

    I know how to find a bijection by graphically by drawing the [tex]\mathbb{N} \times \mathbb{N}[/tex] in a matrix and then traverse the elements diagonally. However, I cannot find a formula that maps an [tex]n[/tex] to a [tex](x,y)[/tex] pair.
     
  2. jcsd
  3. Apr 27, 2010 #2
    Your idea about traversing the elements of the N X N matrix diagonally is good.

    Now, we want to write down that idea in a formula form.

    Let's start with the first few n:
    n=1:(1,1)
    n=2:(1,2)
    n=3:(2,1)
    n=4:(1,3)
    n=5:(2,2)
    n=6:(3,1)

    Now let's consider the pairs in the left column of the matrix, where the pair is (x,1). What pattern is there to these x-values: {1,3,6,10,15...}?
    Next consider the pairs that make up a diagonal, for example {(1,3),(2,2),(3,1)}. What pattern is there in these?

    Can you use those two patterns to write down an expression for the ordered pair that corresponds to a particular n value?
     
  4. May 1, 2010 #3
    Thanks for your reply. I found a bijection from [tex]\mathbb{N} \times \mathbb{N}[/tex] to [tex]\mathbb{N}[/tex] by
    [tex]
    \begin{align*}
    n = \left(\sum^{x+y-2}_{k=1} k \right) + x
    \end{align*}
    [/tex]

    However, is this a bijection from [tex]\mathbb{N}[/tex] to [tex]\mathbb{N} \times \mathbb{N}[/tex] asked by the question? Given a [tex]n[/tex] I cannot use this equation to find a [tex](x,y)[/tex] pair.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook