1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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:

    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
    n = \left(\sum^{x+y-2}_{k=1} k \right) + x

    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