Proof of Cyclic Subgroups and the Order of an Element

Routine facts about powers, inclusions and restrictions of binary operations are used without comment (Toolkit for AL1).

We begin with (i) and (ii). The identity $e=g^{0}$ lies in $\langle g\rangle$ by Integer Powers in a Group (i). For $i,j\in\mathbb{Z}$,

$$g^{i}g^{j}=g^{i+j}\qquad\text{and}\qquad(g^{i})^{-1}=g^{-i}$$

by Exponent Laws for Integer Powers in a Group (iii) and Exponent Laws for Integer Powers in a Group (v), so $\langle g\rangle$ is closed under products and inverses, and it is a subgroup by Subgroups (i). Now let $H$ be a subgroup of $G$ with $g\in H$. Then $g^{0}=e\in H$, and $g^{k}\in H$ for every $k\in\mathbb{N}_{0}$ by induction (Induction on ℕ₀ from 0 for a Condition Expressed by a Predicative Formula (ii)): indeed $g^{k+1}=g^{k}g$ by Exponent Laws for Integer Powers in a Group (iii) and Exponent Laws for Integer Powers in a Group (i), and $H$ is closed under products (Subgroups (i)). Moreover $g^{-k}=(g^{k})^{-1}$ by Exponent Laws for Integer Powers in a Group (v), which lies in $H$ because $H$ is closed under inverses (Subgroups (i)). As every integer is $k$ or $-k$ for some $k\in\mathbb{N}_{0}$ (The Integers Form an Ordered Ring Containing the Natural Numbers as Its Positive Elements (vi)), every element of $\langle g\rangle$ lies in $H$.

For (iii), let $m\in\mathbb{Z}$ and write $m=qn+r$ with $q\in\mathbb{Z}$, $r\in\mathbb{N}_{0}$ and $r<n$, by Division with Remainder (i). By Exponent Laws for Integer Powers in a Group (iii), Exponent Laws for Integer Powers in a Group (iv) and Exponent Laws for Integer Powers in a Group (ii),

$$g^{m}=(g^{n})^{q}g^{r}=e^{q}g^{r}=g^{r}.$$

If $g^{m}=e$, then $g^{r}=e$, and $r\ge1$ would contradict the minimality of $n$ (The Order of an Element of a Group (i)); so $r=0$, $m=qn$, and $n\mid m$ by Divisibility of Integers (i). Conversely, if $m=kn$ with $k\in\mathbb{Z}$, then $g^{m}=(g^{n})^{k}=e^{k}=e$ by Exponent Laws for Integer Powers in a Group (iv) and Exponent Laws for Integer Powers in a Group (ii).

For (iv), suppose that $g^{i}=g^{j}$ with $0\le i<j<n$. Then $g^{j-i}=e$ by Exponent Laws for Integer Powers in a Group (iii) and Exponent Laws for Integer Powers in a Group (v), while $0<j-i<n$, which contradicts the minimality of $n$. So the powers $g^{k}$ with $0\le k<n$ are pairwise distinct. Every element $g^{m}$ of $\langle g\rangle$ equals $g^{r}$ with $r$ the remainder of $m$ found in the proof of (iii), which gives the displayed description of $\langle g\rangle$.

For (v), $\langle g\rangle$ is a group with the restricted operation by (i) and Subgroup Criterion and Basic Examples (ii). The function $k\mapsto g^{k}$ from $\{0,\dots,n-1\}$ to $\langle g\rangle$ is onto and injective by (iv), and $\#\{0,\dots,n-1\}=n$ by Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (i). Hence $\langle g\rangle$ is finite by Finite Sets: the Pigeonhole Principle, Uniqueness of the Length, Subsets, Unions, Products, Images, Bounded Sets of Natural Numbers, Extreme Elements, Sets of Maps, Finite Unions and Finite Choice (vi) and has $n$ elements by Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (iii); that is, $|\langle g\rangle|=n$ by The Order of a Finite Group (i).

For (vi), suppose that $g^{m}=g^{m'}$ with $m\neq m'$; exchanging $m$ and $m'$ if necessary, $m<m'$. By Exponent Laws for Integer Powers in a Group (iii) and Exponent Laws for Integer Powers in a Group (v),

$$g^{m'-m}=g^{m'}g^{-m}=g^{m}(g^{m})^{-1}=e,$$

and $m'-m\in\mathbb{N}$ since $0<m'-m$ (The Integers Form an Ordered Ring Containing the Natural Numbers as Its Positive Elements (vii)), so $g$ has finite order by The Order of an Element of a Group (i), a contradiction.

For (vii), let $G$ be finite, let $h\in G$, and put $N=|G|$. If $h$ had infinite order, then the function $k\mapsto h^{k}$ from $\{0,\dots,N\}$ to $G$ would be injective by (vi) applied to $h$; its image, a subset of $G$, would have $N+1$ elements, so that $N+1\le N$ by Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (i), Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (iii) and Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (iv), which is absurd. So $h$ has finite order $n$, and $\langle h\rangle$ is a subgroup of $G$ with $|\langle h\rangle|=n$ by (i) and (v). Hence $n\mid N$ by Lagrange's Theorem (ii), and then $h^{N}=e$ by (iii).

For (viii), let $|G|=p$ be prime and let $h\in G$ with $h\neq e$. By (vii), $\operatorname{ord}(h)\in\mathbb{N}$ divides $p$, so $\operatorname{ord}(h)\in\{1,p\}$ by Prime Numbers (i); and $\operatorname{ord}(h)=1$ would give $h=h^{1}=e$ by Exponent Laws for Integer Powers in a Group (i). Thus $\operatorname{ord}(h)=p$, and $|\langle h\rangle|=p=|G|$ by (v). Since $\langle h\rangle\subseteq G$, it follows that $\langle h\rangle=G$ by Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (iv), so $h$ is a generator of $G$ (The Set Generated by an Element, and Cyclic Groups (ii)). Such an $h$ exists, because $p\ge2$ by Prime Numbers (i), while $\#\{e\}=1$ (Counting: Intervals, Empty Sets and Singletons, Injective Images, Subsets, Unions and Products (ii)), so $G\neq\{e\}$; hence $G$ is cyclic.