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

Encodings help

  1. Jan 12, 2008 #1
    I know this would probably be in a different category but I wasn't sure.

    Find an encoding for Q x Q.

    I have no idea what to do for this question was we werent even taught encodings.

    any help is appreciated
    thanks
     
  2. jcsd
  3. Jan 12, 2008 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Well, the first thing you need to do is find a definition for "encoding"- especially an encoding for a set of numbers. I suspect that such an encoding would be just a listing of the the rational numbers: 1- r1, 2- r2, etc. Have you seen the proof that the set of rational numbers is countable?
     
    Last edited: Jan 12, 2008
  4. Jan 12, 2008 #3
    Yeah, according to my notes an encoding is "a total injective function C: A->N into the natural numbers. For a in A, the number c(a) is called the code of A"

    I think I've seen the proof you're talking about, its the one done by Cantor's diagonalization right ?
     
  5. Jan 12, 2008 #4

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    No, "Cantor's Diagonalization" is a proof that the set of all real numbers is not countable. I was thinking of the proof where we right the positive integers along the top of a chart, another copy of the integers vertically along the left and, where n along the top meets m along the left, write the fraction m/n. Now "zigzag" throught that chart. To extend it to QxQ, write the positive integers along the top, the positive integers along the left and, where column m and row n intersect, write (rm, rn[/b]) where rn is the rational number "encoded" by m and rn is the rational number "encoded" by n. Now zigzag through that.
     
  6. Jan 13, 2008 #5


    Apparently thats Cantor's zig-zag (which is the one I meant to say in the previous post)
    Anyway, I found this on the internet
    http://www.homeschoolmath.net/teaching/rational-numbers-countable.php

    Do you mean that for instance (r4, r4) or 5,6,7 whatever number it is, is the encoding i've been looking for ?
     
  7. Jan 14, 2008 #6

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    First, I don't know what you mean by "(r4, r4)". Is there any significance that the both rs have subscript 4? Second, you were the one who told me "Yeah, according to my notes an encoding is "a total injective function C: A->N into the natural numbers. For a in A, the number c(a) is called the code of A". If I understand what you are saying correctly, yes, that is the "encoding".
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Encodings help
  1. Help ! (Replies: 6)

  2. Efficient encoding (Replies: 3)

  3. Proof help? (Replies: 4)

Loading...