General This forum is for nontechnical general discussion which can include both Linux and nonLinux topics. Have fun! 
Notices 
Welcome to LinuxQuestions.org, a friendly and active Linux Community.
You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!
Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.
Are you new to LinuxQuestions.org? Visit the following links:
Site Howto 
Site FAQ 
Sitemap 
Register Now
If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.
Having a problem logging in? Please visit this page to clear all LQrelated cookies.

Introduction to Linux  A Hands on Guide
This guide was created as an overview of the Linux Operating System, geared toward new users as an exploration tour and getting started guide, with exercises at the end of each chapter.
For more advanced trainees it can be a desktop reference, and a collection of the base knowledge needed to proceed with system and network administration. This book contains many real life examples derived from the author's experience as a Linux system and network administrator, trainer and consultant. They hope these examples will help you to get a better understanding of the Linux system and that you feel encouraged to try out things on your own.
Click Here to receive this Complete Guide absolutely free. 


02022004, 03:42 PM

#1

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 11 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



02022004, 10:26 PM

#2

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



02022004, 11:44 PM

#3

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



02032004, 09:59 AM

#4

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.



Thread Tools 
Search this Thread 


Posting Rules

You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off



All times are GMT 5. The time now is 10:55 AM.

LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.

Latest Threads
LQ News

