## Cardinality of the gaussian integers

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

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

### Cardinality of the gaussian integers

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.

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

### Re: Cardinality of the gaussian integers

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

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

### Re: Cardinality of the gaussian integers

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

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.

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

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

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

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

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

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

### Re: Cardinality of the gaussian integers

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!)

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

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

Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Cardinality of the gaussian integers

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

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

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

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

### Re: Cardinality of the gaussian integers

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.

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

### Re: Cardinality of the gaussian integers

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

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

### Re: Cardinality of the gaussian integers

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

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.

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

### Re: Cardinality of the gaussian integers

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.

Xanthir
My HERO!!!
Posts: 5413
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

### Re: Cardinality of the gaussian integers

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