Cantor Diagonalization Formula

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

geoth
Posts: 10
Joined: Sat Dec 11, 2010 7:30 pm UTC

Cantor Diagonalization Formula

Postby geoth » Sat Dec 11, 2010 7:44 pm UTC

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?

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26725
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Cantor Diagonalization Formula

Postby gmalivuk » Sat Dec 11, 2010 9:28 pm UTC

Well, there are uncountably many ways to order NxN, so I'm not sure which one in particular you're looking for...
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
ImTestingSleeping
Posts: 88
Joined: Mon Dec 06, 2010 3:46 am UTC

Re: Cantor Diagonalization Formula

Postby ImTestingSleeping » Sat Dec 11, 2010 9:38 pm UTC

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.

forgetful functor
Posts: 10
Joined: Mon Nov 22, 2010 10:40 am UTC

Re: Cantor Diagonalization Formula

Postby forgetful functor » Sat Dec 11, 2010 9:39 pm UTC

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(2n-3) - n + 2)[/math]
is a bijection.

On a side note, have you looked at the Calkin-Wilf Tree? That gives a very interesting bijection with connections to number theory.

skullturf
Posts: 556
Joined: Thu Dec 07, 2006 8:37 pm UTC
Location: Chicago
Contact:

Re: Cantor Diagonalization Formula

Postby skullturf » Sun Dec 12, 2010 12:17 am UTC

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.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Cantor Diagonalization Formula

Postby skeptical scientist » Sun Dec 12, 2010 2:08 am UTC

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

bobdylan
Posts: 31
Joined: Tue Dec 14, 2010 5:30 pm UTC

Re: Cantor Diagonalization Formula

Postby bobdylan » Tue Dec 14, 2010 6:24 pm UTC

One "standard" ordering of NxN is the lexicographic ordering. (a,b)<(c,d) if a<c or (a=c and b<d).

User avatar
gmalivuk
GNU Terry Pratchett
Posts: 26725
Joined: Wed Feb 28, 2007 6:02 pm UTC
Location: Here and There
Contact:

Re: Cantor Diagonalization Formula

Postby gmalivuk » Tue Dec 14, 2010 8:59 pm UTC

And that's a fine ordering as far as it goes, but doesn't help you match it up with N.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
imatrendytotebag
Posts: 152
Joined: Thu Nov 29, 2007 1:16 am UTC

Re: Cantor Diagonalization Formula

Postby imatrendytotebag » Tue Dec 14, 2010 10:54 pm UTC

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.

skullturf
Posts: 556
Joined: Thu Dec 07, 2006 8:37 pm UTC
Location: Chicago
Contact:

Re: Cantor Diagonalization Formula

Postby skullturf » Wed Dec 15, 2010 1:29 am UTC

If you're willing to invoke Schroeder-Bernstein, 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!

bobdylan
Posts: 31
Joined: Tue Dec 14, 2010 5:30 pm UTC

Re: Cantor Diagonalization Formula

Postby bobdylan » Wed Dec 15, 2010 10:15 am UTC

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 .

alphachap
Posts: 4
Joined: Tue Dec 21, 2010 9:17 pm UTC

Re: Cantor Diagonalization Formula

Postby alphachap » Tue Dec 21, 2010 10:14 pm UTC

You can go zig-zag from a corner.
As in http://ariaturns.files.wordpress.com/2009/11/cantorzigzag.png


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 11 guests