Welcome to the most active Linux Forum on the web.
 Home Forums HCL Reviews Tutorials Articles Register Search Today's Posts Mark Forums Read
 LinuxQuestions.org diagonalization proof...
 General This forum is for non-technical general discussion which can include both Linux and non-Linux topics. Have fun!

Notices

 02-02-2004, 03:42 PM #1 true_atlantis Member   Registered: Oct 2003 Distribution: fedora cor 5 x86_64 Posts: 639 Rep: 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
 02-02-2004, 10:26 PM #2 SciYro Senior Member   Registered: Oct 2003 Location: hopefully not here Distribution: Gentoo Posts: 2,038 Rep: 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
 02-02-2004, 11:44 PM #3 true_atlantis Member   Registered: Oct 2003 Distribution: fedora cor 5 x86_64 Posts: 639 Original Poster Rep: ((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
 02-03-2004, 09:59 AM #4 fatman Member   Registered: Mar 2003 Location: PA Distribution: Ubuntu (x2) Posts: 158 Rep: 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.

 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 Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post Transition Slackware 7 09-19-2005 08:02 PM deviant03 Linux - Software 4 01-30-2005 02:20 PM damicatz Linux - Networking 5 11-27-2004 04:50 PM Joey.Dale Linux - General 2 08-11-2003 08:19 PM Jadasin LinuxQuestions.org Member Success Stories 10 04-30-2003 05:54 PM

LinuxQuestions.org

All times are GMT -5. The time now is 09:36 AM.

 Contact Us - Advertising Info - Rules - LQ Merchandise - Donations - Contributing Member - LQ Sitemap -