Latest LQ Deal: Linux Power User Bundle
Go Back > Forums > Non-*NIX Forums > General
User Name
General This forum is for non-technical general discussion which can include both Linux and non-Linux topics. Have fun!


  Search this Thread
Old 02-02-2004, 03:42 PM   #1
Registered: Oct 2003
Distribution: fedora cor 5 x86_64
Posts: 639

Rep: Reputation: 30
diagonalization proof...

i have a question for a cs class that is impossible... the technique to solve it is called diagonalization. i have to prove that all positive rational numbers are denumerable (meaning have a 1 to 1 correspondence with all positive integers). here is how your supposed to do it...

... ... ... ... ...
3/0 3/1 3/2 3/3 3/4 ...
2/0 2/1 2/2 2/3 2/4 ...
1/0 1/1 1/2 1/3 1/4 ...
0/0 0/1 0/2 0/3 0/4 ...

then to show the correspondence you say that

f(0/0) = 0
f(1/0) = 1
f(0/1) = 2
f(2/0) = 3
f(1/1) = 4
f(0/2) = 5

and so on... where the term diagonalization comes from... if you cant see it, you start at 0/0 then move one up and go down the diaginal, and so on... well, i thought that that is enough to prove that there is a 1-1 correspondence, but i have to find a function that will show that f(x) = y ... the only function that i have came up with was this

f(x/y) = (x+y)(x+y+1)/2 + x

does anyone know if there is a function with just 1 variable?? thank
Old 02-02-2004, 10:26 PM   #2
Senior Member
Registered: Oct 2003
Location: hopefully not here
Distribution: Gentoo
Posts: 2,038

Rep: Reputation: 51
i dono if i read whatever equation u sadi right, but i got that whatever you used is impossible, i x=0 y=0 and ur euation says the answer is 0.5 when it should be 0 right?,

neways thats a nice little trick, it moves out in 3 directions, across y,x and between x and y, only there looks as its a small inconsitiency at the start when it sets up, making it look like a L a bit, as there are 2 distint lines that show b4 3 and then start a solid pattern up
Old 02-02-2004, 11:44 PM   #3
Registered: Oct 2003
Distribution: fedora cor 5 x86_64
Posts: 639

Original Poster
Rep: Reputation: 30
((0 + 0)(0 + 0 + 1)/2) + 0 = 0

i made the same mistake you did, you have to realize that your multiplying the numerator by 0
Old 02-03-2004, 09:59 AM   #4
Registered: Mar 2003
Location: PA
Distribution: Ubuntu (x2)
Posts: 158

Rep: Reputation: 30
Ah. Cantor's diagonalization theroem.

To prove the cardinality of the naturals and rational is equal you need to find a bijection between the two.
Set up a cartesian plain.
now assume the x coordinate is the denominator, and the y the numerator (or vice versa)
imagine a diagonization snaking thorugh all the numbers.

you appear to have control of the part above, i was just clarifing,
the numbering i was taught was not as formulaic as you seem to require but its a valid function.

f(x) = the xth unique rational on the diagonalization (discarding 0 denominators and unsimplfied fractions)

Google it for better results or possibility a more acceptable expression of the function, my math is rusty.


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off

Similar Threads
Thread Thread Starter Forum Replies Last Post
Disaster-Proof server? Transition Slackware 7 09-19-2005 08:02 PM
How do I enable burn-proof in K3b? deviant03 Linux - Software 4 01-30-2005 02:20 PM
LDAP + Proof Of Concept damicatz Linux - Networking 5 11-27-2004 04:50 PM
Hacker proof Joey.Dale Linux - General 2 08-11-2003 08:19 PM
Proof that LQ is just the Best Jadasin Member Success Stories 10 04-30-2003 05:54 PM > Forums > Non-*NIX Forums > General

All times are GMT -5. The time now is 05:45 PM.

Main Menu
Write for LQ is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration