# Encodings help

1. Jan 12, 2008

### toxi

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. Jan 12, 2008

### HallsofIvy

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 by a moderator: Jan 12, 2008
3. Jan 12, 2008

### toxi

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 ?

4. Jan 12, 2008

### HallsofIvy

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.

5. Jan 13, 2008

### toxi

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 ?

6. Jan 14, 2008

### HallsofIvy

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".

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook