8

I know that $\mathbb Z$ and $\mathbb{Z}\times\mathbb{Z}$ have the same cardinality because you can create a bijection between the two. The example I was taught is Cantor's pairing function, which maps $\mathbb{N}^2\to\mathbb{N}$ like so: $\displaystyle C(x,y)=y+\frac{(x+y)(x+y+1)}{2}$, and has an inverse $C^{-1}:\mathbb{N}\to\mathbb{N}^2$ which is explained nicely on Wikipedia.

Given that $+$ is defined on $\mathbb{Z}^2$ such that $(x_1,y_1)+(x_2,y_2)=(x_1+x_2,y_1+y_2)$ (i.e. simple vector addition), I was trying to draw some sort of a relation between the sums of integers and the sums of the pairs they map to using the pairing function. I honestly can't see much of a pattern, but I'm willing to conjecture that:

$C^{-1}(a + b) = C^{-1}(a) + C^{-1}(b)$ is true if and only if a or b is $0$

I'm not sure how to prove that, but I have a hunch that it somehow relates to the answer of my actual question:

Is there a function $f:\mathbb{Z}\to\mathbb{Z}\times\mathbb{Z}$ such that:

  1. $f^{-1}:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$ exists
  2. $\forall a,b \in \mathbb{Z}, f(a+b) = f(a)+f(b)$
  3. $\forall a,b \in \mathbb{Z}\times\mathbb{Z}, f(a+b) = f(a)+f(b)$

Can I have a bijective group homomorphism from the integers to pairs of integers?

jen-rose
  • 351
  • 1
    Generalization: https://math.stackexchange.com/questions/2865241, https://math.stackexchange.com/questions/142128 – Watson Nov 30 '18 at 07:46

3 Answers3

24

No: unlike $\Bbb Z$, $\Bbb Z\times\Bbb Z$ is not cyclic. It’s easy to show that no $\langle m,n\rangle\in\Bbb Z\times\Bbb Z$ generates $\Bbb Z\times\Bbb Z$. In case you’d like to try, I’ve spoiler-protected the argument; mouse-over to see it.

Suppose that $\langle m,n\rangle$ generates $\Bbb Z\times\Bbb Z$; then $$\Bbb Z\times\Bbb Z=\{\langle km,kn\rangle:k\in\Bbb Z\}\;.$$ Clearly we must have $m=\pm 1$, as otherwise $\{km:k\in\Bbb Z\}\ne\Bbb Z$. Similarly, $n=\pm 1$. But then $\langle m,n\rangle$ generates either $\{\langle k,k\rangle:k\in\Bbb Z\}$ or $\{\langle k,-k\rangle:k\in\Bbb Z\}$, neither of which is $\Bbb Z\times\Bbb Z$.

Brian M. Scott
  • 616,228
  • 7
    Fancy mouse-thing :) – abcdef Apr 01 '15 at 10:47
  • Interesting way to think about it. So, in general, can you never have an isomorphism from a cyclic group to a non-cyclic group of the same order? – jen-rose Apr 01 '15 at 20:42
  • @kebertx: That’s right. If $G$ is cyclic and generated by $g$, and $h:G\to H$ is an isomorphism, then $h(g)$ generates $H$, which is therefore cyclic. – Brian M. Scott Apr 01 '15 at 20:52
  • 1
    @ Brian M Scott. Thanks for a great post. Would it be more clear (especially to beginning students like myself) if instead of <m,n> to write <(m,n)>. The elements of Z X Z are ordered pairs. More importantly, do you agree that <(1,1)> = <(1,-1)> = <(-1,1)> = <(-1,-1)> ? – Geoffrey Critzer May 22 '15 at 12:05
  • @Geoffrey: $\langle m,n\rangle$ is a standard notation for ordered pairs, though one that's probably most common in set theory. I use it out of long habit, since parentheses are so heavily overloaded. As the $\in$ makes clear, it is a single element of $\Bbb Z\times\Bbb Z$; if the angle brackets denoted subgroup generated by, as you seem to be reading it, I'd have had to use $\subseteq$ or $\le$. – Brian M. Scott May 22 '15 at 12:55
7

Suppose that you had a surjective group homomorphism $f:\mathbb Z \to \mathbb Z \times \mathbb Z$. Then you could find $a, b \in \mathbb Z$ such that $f(a)=(1,0)$ and $f(b)=(0,1)$. We can now compute $f(ab)$ in two ways. $f(ab)=af(b)=a(0,1)=(0,a)$ and $f(ab)=bf(a)=(b,0)$. Since $(0,a)\neq (b,0)$ unless $a=b=0$, we cannot have such a surjective function.

Aaron
  • 24,207
  • I do not understand why f(ab) = af(b) ? When you write f(ab) do you mean the function f evaluated at the product (usual multiplication) of a and b. ? – Geoffrey Critzer May 22 '15 at 12:51
  • Yes. Use induction on the value of $a$ and the fact that multiplication is just repeated addition plus the definition. That a group Bono orphism between abelian groups commutes with addition. – Aaron May 22 '15 at 18:02
  • I hate my phone's autocorrect. Hopefully you can figure out what I meant to write there. – Aaron May 22 '15 at 18:03
  • yes thank you, now I understand. – Geoffrey Critzer May 23 '15 at 13:16
1

Notation: $C$'s inverse is $D$. An admittedly dull computation follows. Let's suppose $D(a+b)=D(a)+D(b)$. With the notations $D(a)=A$ and $D(b)=B$, it is equivalent to $D(C(A)+C(B)) = A + B$, and hence C is bijective, further to $C(A)+C(B)=C(A+B)$. In the terms of the coordinates, $A=(A1,A2)$ and $B=(B1,B2)$ it is equivalent to $C(A1,A2)+C(B1,B2)=C(A1+B1,A2+B2)$, further to $$A2 + \frac{(A1+A2)\cdot(A1+A2+1)}{2} + B2 + (B1+B2)\cdot\frac{(B1+B2+1)}{2} = A2 + B2 + (A1+B1+A2+B2)\cdot\frac{(A1+B1+A2+B2+1)}{2}$$ That is, $$(A1+A2)\cdot(A1+A2+1) + (B1+B2)\cdot(B1+B2+1) = (A1+B1+A2+B2)\cdot(A1+B1+A2+B2+1)$$ With the notation: $A1+A2=x$, $B1+B2=y$, it is $$x(x+1)+y(y+1)=(x+y)(x+y+1)$$ That is, $2\cdot x\cdot y=0$

ijbalazs
  • 11