Cardinality of the gaussian integers

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
BlackSails
Posts: 5315
Joined: Thu Dec 20, 2007 5:48 am UTC

Cardinality of the gaussian integers

Postby BlackSails » Fri Jan 22, 2010 12:28 am UTC

I was thinking a bit about this today, but cant really get anywhere. Im pretty sure that the cardinality is greater than the regular integers (since the integers can be put into correspondance with themselves, and you still have quite alot of integers left over), but I cant figure out if its the same cardinality as the reals or something else.

A quick google search found nothing, but ill admit I didnt look very hard.

User avatar
isomorpher
Posts: 12
Joined: Sat Jan 02, 2010 7:53 am UTC

Re: Cardinality of the gaussian integers

Postby isomorpher » Fri Jan 22, 2010 12:48 am UTC

Nope, their cardinality is aleph-null, exactly the same as the integers. You can think of a single gaussian integer as an ordered pair of integers, and all sets of n-tuples of integers for n < [imath]\omega[/imath] have cardinality aleph null.

One way to order them is a + bi < c + di if a < b or (a=b and c < d). It is easy to see this is a strict well-ordering and isomorphic to [imath]\left \langle \omega,< \right \rangle[/imath].

That's one thing about cardinality of infinite sets. You can have [imath]A \subset B[/imath] and |A| = |B|.

User avatar
Cleverbeans
Posts: 1378
Joined: Wed Mar 26, 2008 1:16 pm UTC

Re: Cardinality of the gaussian integers

Postby Cleverbeans » Fri Jan 22, 2010 1:30 am UTC

Geometrically you need a path that starts at an origin and traverses every lattice point on the complex plane. I'd say start to the left and spiral up and around, and you've got a mapping onto and into the naturals.
"Labor is prior to, and independent of, capital. Capital is only the fruit of labor, and could never have existed if labor had not first existed. Labor is the superior of capital, and deserves much the higher consideration." - Abraham Lincoln

DavCrav
Posts: 251
Joined: Tue Aug 12, 2008 3:04 pm UTC
Location: Oxford, UK

Re: Cardinality of the gaussian integers

Postby DavCrav » Fri Jan 22, 2010 2:10 am UTC

Alternatively, embed the Gaussian integers into the rationals by sending a+bi to p/q, where p is the a-th power of 2 and b is the bth power of 3. By swapping 2 for 5 and 3 for 7, you can deal with minus signs for either a or b, and maybe (a+1)-th power and (b+1)-th power to deal with a+0i and 0+bi. That should do it.

User avatar
Talith
Proved the Goldbach Conjecture
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

Re: Cardinality of the gaussian integers

Postby Talith » Fri Jan 22, 2010 3:39 am UTC

I would go with Dav, bijection from Gaussian integers to the rationals then use your favourite bijection from the rationals to the naturals.

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

Re: Cardinality of the gaussian integers

Postby skeptical scientist » Fri Jan 22, 2010 4:00 am UTC

isomorpher wrote:One way to order them is a + bi < c + di if a < b or (a=b and c < d). It is easy to see this is a strict well-ordering and isomorphic to [imath]\left \langle \omega,< \right \rangle[/imath].

Okay, first of all you mean a<c or a=c and b<d, not what you wrote. But this is still false, since you have essentially described the dictionary order on ZxZ. This is not isomorphic to [imath]\left \langle \omega,< \right \rangle[/imath], and is not a well-ordering.

DavCrav wrote:Alternatively, embed the Gaussian integers into the rationals by sending a+bi to p/q, where p is the a-th power of 2 and b is the bth power of 3. By swapping 2 for 5 and 3 for 7, you can deal with minus signs for either a or b, and maybe (a+1)-th power and (b+1)-th power to deal with a+0i and 0+bi. That should do it.

You can just send a+bi to 2a/3b (or 2a3b for that matter) and be done with it, since this is an injection, and minus signs or zeros are fine.
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

DavCrav
Posts: 251
Joined: Tue Aug 12, 2008 3:04 pm UTC
Location: Oxford, UK

Re: Cardinality of the gaussian integers

Postby DavCrav » Fri Jan 22, 2010 10:31 am UTC

skeptical scientist wrote:
isomorpher wrote:One way to order them is a + bi < c + di if a < b or (a=b and c < d). It is easy to see this is a strict well-ordering and isomorphic to [imath]\left \langle \omega,< \right \rangle[/imath].

Okay, first of all you mean a<c or a=c and b<d, not what you wrote. But this is still false, since you have essentially described the dictionary order on ZxZ. This is not isomorphic to [imath]\left \langle \omega,< \right \rangle[/imath], and is not a well-ordering.

DavCrav wrote:Alternatively, embed the Gaussian integers into the rationals by sending a+bi to p/q, where p is the a-th power of 2 and b is the bth power of 3. By swapping 2 for 5 and 3 for 7, you can deal with minus signs for either a or b, and maybe (a+1)-th power and (b+1)-th power to deal with a+0i and 0+bi. That should do it.

You can just send a+bi to 2a/3b (or 2a3b for that matter) and be done with it, since this is an injection, and minus signs or zeros are fine.


Sure. I don't know why I said that. It was 2am, so maybe that is the reason...

User avatar
t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

Re: Cardinality of the gaussian integers

Postby t0rajir0u » Fri Jan 22, 2010 1:50 pm UTC

If you want to prove that things have the same cardinality using no effort whatsoever, you should use Cantor-Bernstein-Schroeder. The injection from the integers to the Gaussian integers is obvious and as has been mentioned, prime factorization gives you an injection in the other direction. (In fact, prime factorization implies that the integers have the same size as the set of finite subsets of the integers!)

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

Re: Cardinality of the gaussian integers

Postby skeptical scientist » Fri Jan 22, 2010 2:03 pm UTC

t0rajir0u wrote:If you want to prove that things have the same cardinality using no effort whatsoever, you should use Cantor-Bernstein-Schroeder. The injection from the integers to the Gaussian integers is obvious and as has been mentioned, prime factorization gives you an injection in the other direction. (In fact, prime factorization implies that the integers have the same size as the set of finite subsets of the integers!)

Of course there are many other proofs. For the Gaussian integers, I'd just use the spiral proof mentioned above, since that gives you a nice straightforward list. For finite subsets of the integers, I'd just list all finite sets bounded by ±1 (including the empty set), then all finite sets bounded by ±2 but not by ±1, then all finite sets bounded by ±3 but not by ±2, and so on. No doubt Cantor–Schroeder–Bernstein is nice, but sometimes a direct construction is nicer.
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

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Cardinality of the gaussian integers

Postby Xanthir » Fri Jan 22, 2010 2:59 pm UTC

Bah. The best mapping between guassian integers and integers is the same as the best mapping between rationals and integers - interpret the gaussian integer as a higher-base number with the various symbols (minimally the comma, the i, and the minus sign on the imaginary part, for a base 13 number) as digits above 9. Every guassian integer will map to a unique integer.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

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

Re: Cardinality of the gaussian integers

Postby skeptical scientist » Fri Jan 22, 2010 3:52 pm UTC

Meh, that's an injection, not a bijection, and not really all that nice (it takes a lot longer to describe than the injection into the rationals).
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

User avatar
isomorpher
Posts: 12
Joined: Sat Jan 02, 2010 7:53 am UTC

Re: Cardinality of the gaussian integers

Postby isomorpher » Fri Jan 22, 2010 4:17 pm UTC

skeptical scientist wrote:
isomorpher wrote:One way to order them is a + bi < c + di if a < b or (a=b and c < d). It is easy to see this is a strict well-ordering and isomorphic to [imath]\left \langle \omega,< \right \rangle[/imath].

Okay, first of all you mean a<c or a=c and b<d, not what you wrote. But this is still false, since you have essentially described the dictionary order on ZxZ. This is not isomorphic to [imath]\left \langle \omega,< \right \rangle[/imath], and is not a well-ordering.


Yeah, I did mean a<c or a=c and b<d. Also I forgot we were dealing with negatives, hahaha. Of course there are orderings we can create that are order isomorphic to the naturals, similar to the way you would well-order the integers. Even if we couldn't think of one, the well-ordering theorem at least guarantees us that one exists.

User avatar
Cleverbeans
Posts: 1378
Joined: Wed Mar 26, 2008 1:16 pm UTC

Re: Cardinality of the gaussian integers

Postby Cleverbeans » Fri Jan 22, 2010 4:38 pm UTC

I rejected the injection into the rationals because I'm accustomed to seeing the cardinality of the rationals demonstrated by mapping a numerator by denominator lattice into the naturals which is exactly the same problem so it seemed a bit hand-wavy if the OP hadn't already been convinced that the rationals are countable. If they'd already been convinced of that fact however I think it's a superior to use the prime mapping because it is easier to see how it extends to an extended product of countable sets by mapping say, a,b,c,d -> 2a * 3b * 5c * 7d in contrast with a geometric traversal which may be difficult to see in 4+ dimensions.
"Labor is prior to, and independent of, capital. Capital is only the fruit of labor, and could never have existed if labor had not first existed. Labor is the superior of capital, and deserves much the higher consideration." - Abraham Lincoln

User avatar
t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

Re: Cardinality of the gaussian integers

Postby t0rajir0u » Fri Jan 22, 2010 4:40 pm UTC

What's difficult about the geometric argument? Order the lattice points by Manhattan distance from the origin and then lexicographically. This argument has the benefit that not only does it extend to finite subsets of the integers, but it doesn't require that you prove prime factorization: it only requires the two simplest properties of the integers, order and sum.

Anyway, since my favorite bijection between the integers and the rationals hasn't been brought up yet: interpret the base-2 expansion of an integer as a finite continued fraction.

(Seriously, though, I don't see the point of arguing about "best" arguments. It's good to know how to prove a result in many different ways.)

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: Cardinality of the gaussian integers

Postby mike-l » Fri Jan 22, 2010 4:45 pm UTC

t0rajir0u wrote:Anyway, since my favorite bijection between the integers and the rationals hasn't been brought up yet: interpret the base-2 expansion of an integer as a finite continued fraction.


That's.... sexy!
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

User avatar
PM 2Ring
Posts: 3713
Joined: Mon Jan 26, 2009 3:19 pm UTC
Location: Sydney, Australia

Re: Cardinality of the gaussian integers

Postby PM 2Ring » Fri Jan 22, 2010 5:09 pm UTC

What mike-l said. Continued fractions never cease to amaze me.

I like the square spiral mapping, however it's a lot easier mapping from the gaussians to the integers than the other way around, and I agree that it doesn't generalize easily to higher dimensions.

Still, square spirals can be a handy way to display the integers in 2D. Most famously, Ulam found interesting prime patterns using square spirals, and so I've used them in graphical prime generators. I've also used square spirals to create the display in graphical programs that investigate the Collatz conjecture.

User avatar
Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Cardinality of the gaussian integers

Postby Xanthir » Fri Jan 22, 2010 5:45 pm UTC

skeptical scientist wrote:Meh, that's an injection, not a bijection, and not really all that nice (it takes a lot longer to describe than the injection into the rationals).

True, but injection is all you need, since the injection is trivial in the other direction. And it's just plain clever.

The injection into the rationals is non-trivial, actually, because you can produce a zero denominator (you have to be explicit that whichever component you use for the denominator is +1 in the mapping). Easier to map it into 2-tuples of integers, as the second post in this thread states.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 5 guests