What is an encoding for Q x Q and how is it related to Cantor's zig-zag method?

[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 weren't even taught encodings.

any help is appreciated
thanks

 

[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- r₁, 2- r₂, etc. Have you seen the proof that the set of rational numbers is countable?

 

[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 ?

 

[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 (r_m, r_{n[/b]) where rn is the rational number "encoded" by m and rn is the rational number "encoded" by n. Now zigzag through that.}

 

[toxi]

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 (r_m, r_{n[/b]) where rn is the rational number "encoded" by m and rn is the rational number "encoded" by n. Now zigzag through that.}

<sub>Apparently that's 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 ?</sub>

 

[HallsofIvy]

Apparently that's 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 (r₄, r₄) or 5,6,7 whatever number it is, is the encoding I've been looking for ?

First, I don't know what you mean by "(r₄, r₄)". 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".