Cantor Diagonalization Formula
Moderators: gmalivuk, Moderators General, Prelates
Cantor Diagonalization Formula
My math professor mentioned that there is a formula for finding a specific element on a Cantor Diagonalization e.g. for NxN maping onto the Naturals
1 2 3 4...
1 1 2 6 10 ....
2 3 5 9....
3 4 8...
4 7...
5 .
6 .
. .
There is also another way of mapping the NxN onto the Naturals, but not with a continuous line so (2,1)=2 , (1,2)=3, (3.1)=4, which is the more normal method.
I've searched on the internet and I haven't found it. I've mostly been looking under cantor diagonalization method, but I find the proof for why the reals are uncountabl. Can anyone point me in the right direction?
1 2 3 4...
1 1 2 6 10 ....
2 3 5 9....
3 4 8...
4 7...
5 .
6 .
. .
There is also another way of mapping the NxN onto the Naturals, but not with a continuous line so (2,1)=2 , (1,2)=3, (3.1)=4, which is the more normal method.
I've searched on the internet and I haven't found it. I've mostly been looking under cantor diagonalization method, but I find the proof for why the reals are uncountabl. Can anyone point me in the right direction?
 gmalivuk
 GNU Terry Pratchett
 Posts: 26725
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Cantor Diagonalization Formula
Well, there are uncountably many ways to order NxN, so I'm not sure which one in particular you're looking for...
 ImTestingSleeping
 Posts: 88
 Joined: Mon Dec 06, 2010 3:46 am UTC
Re: Cantor Diagonalization Formula
Cantor's diagonalization doesn't rely at all on the order of the members of the set. It simply shows that no matter how you order the members, there is always an element which can be created out of the diagonals which won't be included in the list.
I suppose you could create some construction which ordered them in a particular way which allowed you to generalize what a specific element would look like, but that would only work for that ordering. As gmalivuk said, there are uncountably many ways to arrange them.
I suppose you could create some construction which ordered them in a particular way which allowed you to generalize what a specific element would look like, but that would only work for that ordering. As gmalivuk said, there are uncountably many ways to arrange them.

 Posts: 10
 Joined: Mon Nov 22, 2010 10:40 am UTC
Re: Cantor Diagonalization Formula
You'll want to check me on this, but I believe the map [imath]f: N\times N \rightarrow N[/imath] given by
[math]f(m,n) = \frac{1}{2} (m^2 + n^2 + m(2n3)  n + 2)[/math]
is a bijection.
On a side note, have you looked at the CalkinWilf Tree? That gives a very interesting bijection with connections to number theory.
[math]f(m,n) = \frac{1}{2} (m^2 + n^2 + m(2n3)  n + 2)[/math]
is a bijection.
On a side note, have you looked at the CalkinWilf Tree? That gives a very interesting bijection with connections to number theory.
Re: Cantor Diagonalization Formula
The expression "Cantor's diagonalization" almost always refers to the proof that the real numbers are uncountably infinite, a.k.a. nondenumerably infinite.
There's a different argument belonging to the same general topic that's superficially similar because it also involves "diagonals" of an infinite table. Namely, the standard argument that the set of ordered pairs of natural numbers is countably or denumerably infinite (i.e. can be put into bijective correspondence with the set of natural numbers, or listed in an "infinite list"). I don't know offhand whether this argument is due to Cantor, and it's true that the picture involves diagonal lines, but referring to it as "Cantor's diagonalization" is likely to confuse people.
As I remember it, in this proof that N x N is denumerable, we typically say essentially "if we follow the diagonals in this way, every ordered pair of real numbers appears in our list", but we don't explicitly give a formula for "what's the nth ordered pair in our list?" That's still enough to prove denumerability, as long as you're unambiguously describing an algorithm that you can show will list every pair of natural numbers. However, as mentioned earlier, it's also possible to come up with more explicit bijections between N x N and N, and some find this more elegant.
There's a different argument belonging to the same general topic that's superficially similar because it also involves "diagonals" of an infinite table. Namely, the standard argument that the set of ordered pairs of natural numbers is countably or denumerably infinite (i.e. can be put into bijective correspondence with the set of natural numbers, or listed in an "infinite list"). I don't know offhand whether this argument is due to Cantor, and it's true that the picture involves diagonal lines, but referring to it as "Cantor's diagonalization" is likely to confuse people.
As I remember it, in this proof that N x N is denumerable, we typically say essentially "if we follow the diagonals in this way, every ordered pair of real numbers appears in our list", but we don't explicitly give a formula for "what's the nth ordered pair in our list?" That's still enough to prove denumerability, as long as you're unambiguously describing an algorithm that you can show will list every pair of natural numbers. However, as mentioned earlier, it's also possible to come up with more explicit bijections between N x N and N, and some find this more elegant.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Cantor Diagonalization Formula
As mentioned by skullturf, Cantor's diagonalization argument refers to something else. What you are looking for is the Cantor pairing function. According to the Wikipedia article, this function is basically the same as the function that forgetful functor gave. (The difference is that his function is a bijection between {1,2,3,...}^{2} and {1,2,3,...}, whereas the function in the Wikipedia article is a bijection between {0,1,2,...}^{2} and {0,1,2,...}.)
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Re: Cantor Diagonalization Formula
One "standard" ordering of NxN is the lexicographic ordering. (a,b)<(c,d) if a<c or (a=c and b<d).
 gmalivuk
 GNU Terry Pratchett
 Posts: 26725
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Cantor Diagonalization Formula
And that's a fine ordering as far as it goes, but doesn't help you match it up with N.
 imatrendytotebag
 Posts: 152
 Joined: Thu Nov 29, 2007 1:16 am UTC
Re: Cantor Diagonalization Formula
There's also a cool bijection from N to the positive rationals where you take a natural number N and consider it's prime factorization. If p1^a1*p2^a2...*pn^an are all the primes raised to even powers, the numerator of the fraction is p1^a1/2*p2^a2/2*...*pn^an/2. If q1^b1*...*qm^bm are all the primes raised to odd powers, the denominator is q1^(b1+1)/2*q2^(b2+1)/2*...*qm^(bm+1)/2. (If there are no such primes in the relevant category, the numerator/denominator equals 1).
Hey baby, I'm proving love at nth sight by induction and you're my base case.
Re: Cantor Diagonalization Formula
If you're willing to invoke SchroederBernstein, it's enough to show a bijection between N and part of NxN, and another bijection between NxN and part of N.
The first is trivial. For the second, say each of your pairs of natural numbers is written with a comma separating the two numbers. Interpret that as base 11 notation, where the comma is one of the digits!
The first is trivial. For the second, say each of your pairs of natural numbers is written with a comma separating the two numbers. Interpret that as base 11 notation, where the comma is one of the digits!
Re: Cantor Diagonalization Formula
Hmm. Yes, the lexicographic ordering is useless here.
The way I've always seen this particular trick done is to step through NxN by first running through pairs (x,y) with x+y=2, then through pairs with x+y=3, and so on. It's usually drawn like a snake, going backwards and forwards up the diagonals, but to work out the formula it would be easier to always go in order of increasing x, say.
Now you should easily be able to work out which number maps to (x,y), because you can count the pairs (x',y') with x'+y'<x+y .
The way I've always seen this particular trick done is to step through NxN by first running through pairs (x,y) with x+y=2, then through pairs with x+y=3, and so on. It's usually drawn like a snake, going backwards and forwards up the diagonals, but to work out the formula it would be easier to always go in order of increasing x, say.
Now you should easily be able to work out which number maps to (x,y), because you can count the pairs (x',y') with x'+y'<x+y .
Re: Cantor Diagonalization Formula
You can go zigzag from a corner.
As in http://ariaturns.files.wordpress.com/2009/11/cantorzigzag.png
As in http://ariaturns.files.wordpress.com/2009/11/cantorzigzag.png
Who is online
Users browsing this forum: No registered users and 11 guests