Prove relation between the group of integers and a subgroup

[PhysicsRock]

Homework Statement

Let $X \subseteq \mathbb{Z}$ be a subgroup of $(\mathbb{Z},0,+)$. Show that an $l \in \mathbb{N}_0$ exists such that $X = l \cdot \mathbb{Z}$.

Relevant Equations

There are no other equations, so I'm just gonna state the hint that comes with the problem here. It is: In case $\{ 0 \} \subsetneq X$ choose $l = \min(X \cap \mathbb{N})$.

So, a friend of mine has attempted a solution. Unfortunately, he's having numbers spawn out of nowhere and a lot of stuff is going on there which I can't make sense of. I'm going to write down the entire attempt.

$$
0 \in X \; \text{otherwise no subgroup since neutral element isn't included} \notag
$$

For each additional element $x$, $-x$ has to be an element as well, to satisfy the condition of an inverse. Now let $H_+$ be the set of all elements of $X$ that are greater or equal to $0$ and likewise for $H_-$ containing all negative integers. Then $X = H_+ \cup H_-$. Following the hint, let $l$ be the smallest number contained in $X$. For $H_+,H_-$, $l \cdot h = \underbrace{h + h + h + ... + h}_{l-times}$ has to be an element of the respective group too, because of closedness.

Now let $h \in H_+$. Then $h = l \cdot z + r$ with $r < l$ (don't know where the $r$ is coming from and why it has to be less than $l$). Since $l$ is the smallest positive number and $r < l$, it follows that $r = 0$ and this $x = l \cdot z \, \forall \, x \in X$. The process is analogous for $H_-$.

Does this make sense and if not, what went wrong? Thanks everyone!

 

[fresh_42]

Homework Statement:: Let $X \subseteq \mathbb{Z}$ be a subgroup of $(\mathbb{Z},0,+)$. Show that an $l \in \mathbb{N}_0$ exists such that $X = l \cdot \mathbb{Z}$.
Relevant Equations:: There are no other equations, so I'm just going to state the hint that comes with the problem here. It is: In case $\{ 0 \} \subsetneq X$ choose $l = \min(X \cap \mathbb{N})$.

So, a friend of mine has attempted a solution. Unfortunately, he's having numbers spawn out of nowhere and a lot of stuff is going on there which I can't make sense of. I'm going to write down the entire attempt.

$$
0 \in X \; \text{otherwise no subgroup since neutral element isn't included} \notag
$$

For each additional element $x$, $-x$ has to be an element as well, to satisfy the condition of an inverse. Now let $H_+$ be the set of all elements of $X$ that are greater or equal to $0$ and likewise for $H_-$ containing all negative integers. Then $X = H_+ \cup H_-$. Following the hint, let $l$ be the smallest number contained in $X$. For $H_+,H_-$, $l \cdot h = \underbrace{h + h + h + ... + h}_{l-times}$ has to be an element of the respective group too, because of closedness.

Now let $h \in H_+$. Then $h = l \cdot z + r$ with $r < l$ (don't know where the $r$ is coming from and why it has to be less than $l$). Since $l$ is the smallest positive number and $r < l$, it follows that $r = 0$ and this $x = l \cdot z \, \forall \, x \in X$. The process is analogous for $H_-$.

Does this make sense and if not, what went wrong? Thanks everyone!

It is correct. Written in a bit confusing way that suggests you didn't understand all steps, but all in all correct.

$X\subseteq \mathbb{Z}$ is a subgroup. So $0\in X$ and $X\neq \emptyset.$

If $X=\{0\}$ then $X=0\cdot \mathbb{Z}$ and we are done.

Next, we assume that $\{0\}\subsetneq X$ is a proper subgroup, i.e. $X$ contains at least one element $x\neq 0.$ With $x\in X$ we also have $-x\in X$ and either $x$ or $-x$ is positive. This means that $X$ contains a number $x>0.$ Since the natural numbers (positive integers) are bounded from below, we can choose the smallest positive $X\ni l>0.$

We now apply the Euclidean algorithm, i.e. the ordinary division, and divide any number $x\in X$ by $l.$ Unfortunately, we are not allowed to divide $x$ by $l$ since $\mathbb{Z}$ doesn't contain all quotients. What we can do is to subtract $l$ from $x$ as long as the result is greater or equal $l.$ This is basically the long division: $x=q\cdot l +r.$ Subtract $l$ as long from $x$ as $r\geq l,$ here $q$ times, until $r<l.$ We can always perform this step such that $0\leq r,$ because we can select $q<0$ if necessary.

We now rearrange the equation: $r=x-q\cdot l=\underbrace{x}_{\in X} - \underbrace{(\underbrace{l+l+\ldots +l}_{q\text{ times}}}_{\in X} \in X.$

However, $X\ni r\geq 0$ can only be the case if $r=0$ by the choice of $l$ as the minimal element among those in $X$. Thus any arbitrary element $x\in X$ is of the form $x=q\cdot l+0,$ i.e. $X=\mathbb{Z}\cdot l.$

The distinction between $H_+$ and $H_-$ isn't necessary. The Euclidean algorithm works for all integers in a way such that the remainder of consecutive subtractions are always positive. If necessary, i.e. if $x<0,$ then we perform consecutive additions instead.

 

[PhysicsRock]

It is correct. Written in a bit confusing way that suggests you didn't understand all steps, but all in all correct.

$X\subseteq \mathbb{Z}$ is a subgroup. So $0\in X$ and $X\neq \emptyset.$

If $X=\{0\}$ then $X=0\cdot \mathbb{Z}$ and we are done.

Next, we assume that $\{0\}\subsetneq X$ is a proper subgroup, i.e. $X$ contains at least one element $x\neq 0.$ With $x\in X$ we also have $-x\in X$ and either $x$ or $-x$ is positive. This means that $X$ contains a number $x>0.$ Since the natural numbers (positive integers) are bounded from below, we can choose the smallest positive $X\ni l>0.$

We now apply the Euclidean algorithm, i.e. the ordinary division, and divide any number $x\in X$ by $l.$ Unfortunately, we are not allowed to divide $x$ by $l$ since $\mathbb{Z}$ doesn't contain all quotients. What we can do is to subtract $l$ from $x$ as long as the result is greater or equal $l.$ This is basically the long division: $x=q\cdot l +r.$ Subtract $l$ as long from $x$ as $r\geq l,$ here $q$ times, until $r<l.$ We can always perform this step such that $0\leq r,$ because we can select $q<0$ if necessary.

We now rearrange the equation: $r=x-q\cdot l=\underbrace{x}_{\in X} - \underbrace{(\underbrace{l+l+\ldots +l}_{q\text{ times}}}_{\in X} \in X.$

However, $X\ni r\geq 0$ can only be the case if $r=0$ by the choice of $l$ as the minimal element among those in $X$. Thus any arbitrary element $x\in X$ is of the form $x=q\cdot l+0,$ i.e. $X=\mathbb{Z}\cdot l.$

The distinction between $H_+$ and $H_-$ isn't necessary. The Euclidean algorithm works for all integers in a way such that the remainder of consecutive subtractions are always positive. If necessary, i.e. if $x<0,$ then we perform consecutive additions instead.

Thank you so much. Actually getting it explained is always super helpful. All I got were the equations. My friend didn't explain his steps and his handwriting was hard to read anyway, so I had a very hard time figuring out what each step meant. But this really does explain everything nicely. Thank you again :)

 

[PeroK]

Why not simply:

Let $l$ be the least positive element in $X$. By induction $l\mathbb Z \subseteq X$.

If there exists positive $k \in X$ but $k \notin l\mathbb Z$ then $nl < k < (n+1)l$ for some $n$. Hence $k -nl \in X$ with $0< k -nl < l$. Contradiction.

 

[fresh_42]

Why not simply:

Let $l$ be the least positive element in $X$. By induction $l\mathbb Z \subseteq X$.

If there exists positive $k \in X$ but $k \notin l\mathbb Z$ then $nl < k < (n+1)l$ for some $n$. Hence $k -nl \in X$ with $0< k -nl < l$. Contradiction.

This is the identical proof just without all the technical details and references to the group axioms and the fact that Euclidean rings are principal ideal domains. Whether you write $k=nl+r$ or $x=ql+r$ isn't really a difference.

 

[PeroK]

This is the identical proof just without all the technical details and references to the group axioms and the fact that Euclidean rings are principal ideal domains. Whether you write $k=nl+r$ or $x=ql+r$ isn't really a difference.

It seems to me that the OP may be too focused on the details and not yet able to see the outline of a proof for himself. The details rarely sort themselves out without my knowing what I'm trying to do.

I think it's important for the OP to recognise the common proof ideas here, as well as follow a complete step by step solution.

 

[fresh_42]

Choosing a minimal element ($l$) from a subset of $\mathbb{N}$ and using the Euclidean division to find a smaller element ($r$) which leads to either a contradiction or to $r=0$ is a standard technique.

Locking $k$ up between $nl$ and $(n+1)l$ not so much.