# How to prove a group has a basis with exactly one element?

I am struggling with the following question.

Suppose I have a group $H$ which is a subgroup of $\mathbb{Z}\oplus\mathbb{Z}$, such that any element $\begin{bmatrix} a \\[0.3em] b \end{bmatrix}$ is defined as: if $b=0$, then $a=0$. How can I prove that $H$ has a basis with exactly one element?

-
A clearer way to state this problem would be to say that $H$ is a subgroup of ${\mathbb Z} \oplus {\mathbb Z}$ having zero intersection with the first direct factor. –  Derek Holt May 1 '12 at 12:23
What is exactly the meaning of a one element basis? I am under the impression that it is a set with only one element in it; like (x). But the answers here suggest that one element basis is of the type (x,y). I am a bit confused with this. –  CasterT May 9 '12 at 15:23
This is because elements of $\mathbb{Z}\oplus \mathbb{Z}$ are pairs $(x,y)$ with $x,y\in \mathbb{Z}$. –  Tara B May 9 '12 at 16:03
@CasterT: The comment above is addressed to you. –  Tara B May 9 '12 at 22:09

I understand what you mean. Here's my suggestion: take the element of the subgroup whose first coordinate has the smallest positive value: $(a,b)\in H$ such that $a>0$ and $a \leq a'$ for all $(a',b')\in H$ such that $a' > 0$. This exists because $\mathbb{Z}_+$ is well ordered.

Claim: $(a,b)$ is your generator.

You have to show that, for all $(a',b')\in H$, there exists $n\in \mathbb{Z}$ such that $(a',b') = n(a,b)$. Proceed by contradiction. Your assumption on $H$ and the choice of $a$ imply that $b\neq 0$ too. (It could be negative.) A little arithmetic should yield the contradiction.

Note: I haven't written out the argument, but this is how all such problems proceed.

-

I think Tara somewhat gave the answer. If I understand you correctly you have some given subgroup $H$ with the property that if $(a,0)\in H$ then $a=0$. This is slightly different from what you wrote.

You use closure under addition and Bézout's identity for your proof. Assume we have two generators $(a,b)$ and $(c,d)$. Then $d(a,b)-b(c,d)$ must be in $H$ (the product is here understood as the d-fold resp. b-fold sum). But this is just $(da-bc,0)$, thus $da=bc$. Now you have Bézout's identity, i.e. there exist $x,y$ such that $xb+yd=gcd(b,d)=:g$. Write $b=gb'$ and $d=gd'$, then we have $b'(xa+yc,g)=(a,b)$ and $d'(xa+yc,g)=(c,d)$ by the equality $d'a=b'c$. Hence $H$ is generated by one element.

-

This is more or less just another version of the answers already given, but I don't use Bézout's identity or contradiction.

Let $H$ be a subgroup of $\mathbb{Z}\oplus \mathbb{Z}$ such that for any $(a,b)\in H$, if $b=0$ then $a=0$. Another way of saying this is that $(a,0)\in H$ implies $a=0$. So what we are really saying is that the intersection of $H$ with the first direct factor is trivial, as Derek said.

Now suppose $(a_1,b), (a_2,b)\in H$. Since $H$ is a group under addition, $(a_1,b) - (a_2,b) = (a_1 - a_2, 0)\in H$ and hence $a_1 = a_2$. So for each $b\in \mathbb{Z}$, there is at most one $a\in \mathbb{Z}$ such that $(a,b)\in H$.

Now let $b$ be the minimum positive integer such that $(a,b)\in H$ for some $a\in \mathbb{Z}$. Suppose $(a',b')\in H$, and write $b' = bq + r$ with $q\in \mathbb{Z}$, $0\leq r<b$. Then $(a',b') - q(a,b) = (a'-qa, r)\in H$, so $r=0$ by the minimality of $b$. But then since $q(a,b) = (qa,b')\in H$, we must have $a' = qa$ by the uniqueness of $a'$. Hence $(a',b') = q(a,b)$, so every element of $H$ is a multiple of $(a,b)$ and hence $(a,b)$ generates $H$.

-

If you mean that $H$ is a subgroup of $\mathbb{Z}\oplus\mathbb{Z}$ where each $h=\left[\matrix{a\\b}\right]\in H$ satisfies the condition $b=0\implies a=0$, then you have a tractable problem.

In this case, a hint is to consider the smallest positive value that $a$ can have over all such $h$ above.

You could define $\alpha=\inf_{h\in H}|\pi_1(h)|$ where $\pi_1:H\to\mathbb{Z}$ is the "projection" homomorphism $h\mapsto a$ taking each $h$ to its first ordinate. Or, if this seems to abstract, start by observing that the set $A=\{a~|~h\in H\}$ is itself a subgroup of $\mathbb{Z}$, then let $A^+=\{a\in A~|~a > 0\}$ and $\alpha=\inf A^+$.

Then, let $g=\left[\matrix{\alpha\\\beta}\right]$ be a (the) element of $H$ having this minimal positive first ordinate. You will be able to show that $g$ is in fact unique and that it generates $H$, i.e. each $h=ng$ for some $n\in\mathbb{Z}$.

Intuitively, you can visualize this as a (parallelogramic) lattice in $\mathbb{Z}^2$, or as an additive subgroup (in fact, an ideal) $I=\left<\alpha+i\beta\right>$ in the ring of Gaussian integers.

To make the formal proof, you could use Bézout's identity as Simon Markett does. Or, you can notice that the minimality condition defining $\alpha$ is in fact an equivalent way of defining the greatest common divisor. Then, notice that $\pm\alpha$ are the unique generators of $H_1=\pi_1(\mathbb{Z})$ which is a cyclic subgroup of the first $\mathbb{Z}$ in $\mathbb{Z}\oplus\mathbb{Z}$, for if some $h$ had $a\not\equiv0\pmod\alpha$, then replacing $a$ with its remainder $r$ would produce an element of $H$ with smaller first ordinate, condtradicting the minimality of $\alpha$.

Lastly, we need to show that $\beta$ as defined above (which may be negative) generates $H_2=\pi_2(H)$, i.e. has minimal absolute value over all second ordinates $b$ of $h\in H$. However we already know that $H_2$ is a cyclic subgroup of $\mathbb{Z}$, and if its generator $\beta'$ were smaller in absolute value than $\beta$, then we would have $\beta'|\beta\implies\beta=n\beta'$ and hence $g=ng'$ for some $g'=\left[\matrix{\alpha'\\\beta'}\right]\in H$ with second ordinate $\beta'$ and some $n\ne0,~\pm1$. But then we would have $\alpha=n\alpha'=|n\alpha'|>|\alpha'|$, contradicting the minimality of $\alpha$.

The key insight in this last step is that the minimality (in absolute value) of $\alpha$ and $\beta$ are linked, or coupled. Thus, we could started by defining $\beta$ as well from a minimality condition, analogously to $\alpha$, and then proving that one of $\left[\matrix{\alpha\\\pm\beta}\right]$ generates $H$.

-
you beat me to the punch! –  Jerry Gagelman May 1 '12 at 12:28
@JerryGagelman: actually, I think yours is correct and mine not. I was too hasty! –  bgins May 1 '12 at 12:31
I have one more question from Tara B. In your answer you have mentioned "Since H is a group under addition, $(a_1,b)−(a_2,b)=(a_1−a_2,0) \in H$". Isn't it for a group under subtraction we can write the above? I am still in the process of learning these, so I have a lot of questions.
No. Subtraction is not associative, so you can't have a 'group under subtraction'. If $G$ is a group under addition, then for any $x,y\in G$, we have $-y\in G$, since $-y$ is the inverse of $y$, and so $x + (-y)\in G$. We can write $x-y$ as shorthand for $x + (-y)$. –  Tara B May 10 '12 at 19:04