How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

✓ 15 results · all verified · 13 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full and owner-audited; the judge is an additional, independent cross-model AI review of the proofs. The 2 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Binary Operations, Monoids, Groups and Subgroups

1 · Prerequisites

2 · Summary

Objective. This page opens the abstract algebra track. Everything the library has built so far, the naturals, the integers, the rationals and the reals, was built one structure at a time, and each construction re-proved the same handful of facts about its own operation: associativity, an identity, inverses, cancellation. This page isolates that handful into axioms and proves the facts once, for every structure satisfying them at once. The axioms themselves say nothing about numbers, and no result below is about a particular number system. Numbers do enter, in three specific places and as the library's own $N$ and $Z$ : as exponents, as counts, and in the division algorithm that the order of an element turns out to need, which is proved here for want of an earlier home. The number systems reappear as examples of groups only on the companion page linked under Prerequisites above.

One operation, and the two uniqueness results that license the notation. Binary operation on a set; associativity, commutativity, and a subset closed under the operation fixes what an operation is and what it means for a subset to be closed under it; Left identity, right identity, and two-sided identity for a binary operation keeps left, right and two-sided identities apart. The separation matters, because A left identity and a right identity for the same binary operation are equal; hence there is at most one two-sided identity then proves the sharp statement that a left identity and a right identity for the same operation are equal, so a two-sided identity is unique when it exists. That is what makes "the identity" legitimate language in Semigroup and monoid. One level up the same device recurs: Left inverse, right inverse, and invertible element of a monoid separates left, right and two-sided inverses and In a monoid, a left inverse and a right inverse of the same element are equal; hence an invertible element has exactly one inverse, and it is two-sided proves that in a monoid a left inverse and a right inverse of the same element coincide, this time using associativity, which is essential. Only then does Group and abelian group define a group as a monoid in which every element is invertible and write $g^{- 1}$ .

The first consequences. In a group $e^{- 1} = e$ , $(g^{- 1})^{- 1} = g$ and $(g h)^{- 1} = h^{- 1} g^{- 1}$ , the order of the last product being essential gives $e^{- 1} = e$ , $(g^{- 1})^{- 1} = g$ and $(g h)^{- 1} = h^{- 1} g^{- 1}$ , and settles that the reversal in the last is essential by showing $(g h)^{- 1} = g^{- 1} h^{- 1}$ holds exactly when $g$ and $h$ commute. Cancellation in a group: $g x = g y$ or $x g = y g$ forces $x = y$ ; equivalently left and right translation by $g$ are bijections of $G$ , so $g x = h$ and $x g = h$ each have exactly one solution proves cancellation on both sides, in the form that left and right translation by $g$ are bijections of $G$ , so each of $g x = h$ and $x g = h$ has exactly one solution. The invertible elements of a monoid form a group under the restricted operation runs the construction in the other direction: the invertible elements of any monoid form a group, and a monoid is a group exactly when that is all of it.

The symmetric group, homed here rather than later. The symmetric group $Sym (X)$ : the bijections of a set $X$ under composition introduces $Sym (X)$ , the bijections of a set under composition, together with cycle notation, and $Sym (X)$ is a group under composition, and it is non-abelian whenever $X$ has at least three distinct elements proves it is a group and that it fails to be abelian as soon as $X$ has three distinct elements. The non-abelian clause is phrased with three named points and no counting, so it is available for any set whatever. This material is placed here, rather than with the combinatorics of $S_{n}$ , because group actions need $Sym (X)$ earlier than the finite symmetric groups are studied, and because it supplies this page's own non-abelian witnesses.

Long products, and the exponent laws. Associativity is an axiom about three factors; that brackets may be dropped in a product of any length is a theorem. The product $g_{0} g_{1} \dots g_{n - 1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity defines $\prod_{i < n} g_{i}$ by recursion, with the empty product equal to the identity, and Generalised associativity: in a monoid the product of a finite list does not depend on the bracketing, and in a commutative monoid it does not depend on the order of the factors either proves the splitting law, the regrouping law that is the precise form of "the bracketing does not matter", and, in a commutative monoid, invariance under permuting the factors. Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ then defines $g^{n}$ for natural $n$ in a monoid and for integer $n$ in a group, splitting on the sign of the exponent rather than on a representative of it, and Exponent laws in a group: $g^{m + n} = g^{m} g^{n}$ and $(g^{m})^{n} = g^{m n}$ for all $m, n \in Z$ , and $(g h)^{n} = g^{n} h^{n}$ when $g$ and $h$ commute proves the exponent laws. The last of those, $(g h)^{n} = g^{n} h^{n}$ , carries the hypothesis that $g$ and $h$ commute, in its statement and in its title, because it is false without it; the companion page exhibits the failure at $n = 2$ .

Subgroups. Subgroup asks for three closure conditions; One-step subgroup test: a nonempty $H \subseteq G$ is a subgroup iff $g h^{- 1} \in H$ for all $g, h \in H$ ; the identity and the inverses of $H$ are then those of $G$ replaces them by the single test $g h^{- 1} \in H$ on a nonempty subset, and settles the point that a subset which happens to be a group under the restricted operation must carry the identity and the inverses of the ambient group, cancellation being what forces it. The intersection of a nonempty family of subgroups of $G$ is a subgroup of $G$ shows intersections of subgroups are subgroups, which is exactly what makes The subgroup $⟨ S ⟩$ generated by a subset, the cyclic subgroup $⟨ g ⟩$ , and cyclic groups work: $⟨ S ⟩$ is defined from outside, as the intersection of all subgroups containing $S$ , and $⟨ g ⟩ = {g^{n} : n \in Z}$ , and every cyclic group is abelian identifies the single-generator case from inside, $⟨ g ⟩ = {g^{n} : n \in Z}$ , and deduces that every cyclic group is abelian. Unions of subgroups are almost never subgroups, which the companion page records.

Division with remainder, minted here too. Nothing earlier in the library supplies division with remainder in $Z$ , and two results below are unprovable without it, so Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ proves it, for a positive divisor, from the ordered ring structure and the well-ordering principle. No absolute value on $Z$ is needed and none is used. The relation " $b$ divides $a$ " is defined there for use here; the systematic theory of divisibility belongs to a later page, which must record that its general notion restricts to this one rather than introduce a second silently.

Order. The order of an element is definable only once something is known to exist, so the existence comes first: In a finite group, every element $g$ satisfies $g^{n} = e$ for some natural $n \geq 1$ proves that in a finite group some positive power of every element is the identity, using the pigeonhole principle directly on the map $k \mapsto g^{k}$ rather than any statement about subsets of finite sets. The order $∣ G ∣$ of a finite group and the order $ord (g)$ of an element, with $ord (g) = \infty$ when no positive power of $g$ is the identity then defines $∣ G ∣$ , using the fact that a finite set is equinumerous with exactly one natural number, and $ord (g)$ as the least positive $n$ with $g^{n} = e$ , using the well-ordering principle, with $ord (g) = \infty$ when no such $n$ exists. If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ is the payoff: $g^{k} = e$ exactly when $ord (g)$ divides $k$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $∣ ⟨ g ⟩ ∣ = ord (g)$ , so the order of an element is the order of the group it generates.

Homomorphisms, definition only. Monoid homomorphism and group homomorphism defines monoid and group homomorphisms, and A group homomorphism automatically satisfies $f (e) = e^{'}$ and $f (g^{- 1}) = f (g)^{- 1}$ , and $f (g^{n}) = f (g)^{n}$ for every $n \in Z$ ; for monoid homomorphisms preservation of the identity must be assumed explains why the two definitions differ: a group homomorphism automatically preserves the identity, the inverses and all integer powers, whereas for monoids preservation of the identity has to be assumed, as the constant map $0$ on $(Z, \cdot)$ shows. Kernels, images, isomorphisms and the isomorphism theorems belong to a later page and are not used here.

What is deliberately absent. There is no direct product of groups on this page, since the page that develops products already lists it; no greatest common divisor, since nothing here needs one; and no notion of isomorphism, since the homomorphism theory is developed later. Twenty-nine items are proved here, seven of them marked as landmarks in the flowchart above.

3 · Logical flowchart

4 · Definitions, theorems and proofs

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (z-ai/glm-5.2)audited 2026-07-27Open item page →

Binary operation on a set; associativity, commutativity, and a subset closed under the operation

Definition

A binary operation on a set $S$ is a function (A function is a relation $f$ with $(a, b) \in f$ and $(a, c) \in f$ implying $b = c$ ; $f : A \to B$ , the value $f (a)$ , domain and codomain) whose domain is the Cartesian product $S \times S$ (The Cartesian product $A \times B : = {z \in P (P (A \cup B)) : \exists a \in A \exists b \in B z = (a, b)}$ ),

$* : S \times S ⟶ S,$

written in infix form $x * y : = * (x, y)$ . That the value always lies in $S$ is part of the definition, and is referred to as $S$ being closed under $*$ . The pair $(S, *)$ is called a set equipped with a binary operation.

The operation $*$ is

associative when $(x * y) * z = x * (y * z)$ for all $x, y, z \in S$ ;
commutative when $x * y = y * x$ for all $x, y \in S$ .

Two elements $x, y \in S$ commute when $x * y = y * x$ ; so $*$ is commutative exactly when every two elements of $S$ commute.

A subset $T \subseteq S$ is closed under $*$ when $x * y \in T$ for all $x, y \in T$ . In that case the restriction of $*$ to $T \times T$ has all its values in $T$ and is therefore a binary operation on $T$ , called the restricted operation or the operation induced on $T$ ; it is again associative if $*$ is, and again commutative if $*$ is, since both conditions are equations required of elements of $T$ , which are in particular elements of $S$ .

Remarks

Notation. Where no confusion arises the operation is written multiplicatively, $x y$ for $x * y$ , and additively, $x + y$ , when it is commutative and the context is additive. Nothing in this page depends on the choice: every statement is about an abstract operation.
Bracketing. Associativity is stated for three factors only. That it lets brackets be dropped in a product of any finite length is a theorem, not a restatement: it is Generalised associativity: in a monoid the product of a finite list does not depend on the bracketing, and in a commutative monoid it does not depend on the order of the factors either, proved below.
Familiar instances already in the library are addition and multiplication on $N$ (Addition of natural numbers, Multiplication of natural numbers), on $Z$ (Arithmetic on the integers) and on any field (Field).

DefinitionDefinition: Literature-sourcedProof: Not applicablejudge pass (z-ai/glm-5.2)audited 2026-07-27Open item page →

Left identity, right identity, and two-sided identity for a binary operation

Definition

Let $*$ be a binary operation on a set $S$ (Binary operation on a set; associativity, commutativity, and a subset closed under the operation) and let $e \in S$ . Then $e$ is

a left identity for $*$ when $e * x = x$ for every $x \in S$ ;
a right identity for $*$ when $x * e = x$ for every $x \in S$ ;
a two-sided identity, or simply an identity, when it is both.

Remarks

The three notions are genuinely different for a general operation, and the library keeps them apart deliberately: several existing items prove the two sides separately. For addition on $N$ , for instance, $n + 0 = n$ holds by the defining recursion (Addition of natural numbers) while $0 + n = n$ is a theorem proved by induction (Left identity for addition).
A structure can have many left identities and no right identity, so "the identity" is not legitimate language until uniqueness is available. That is A left identity and a right identity for the same binary operation are equal; hence there is at most one two-sided identity, proved next, and it is the item that licenses the definite article everywhere below.

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-27Open item page →

A left identity and a right identity for the same binary operation are equal; hence there is at most one two-sided identity

Statement

Let $*$ be a binary operation on a set $S$ (Binary operation on a set; associativity, commutativity, and a subset closed under the operation). If $e \in S$ is a left identity and $f \in S$ is a right identity for $*$ (Left identity, right identity, and two-sided identity for a binary operation), then $e = f$ . Consequently:

$*$ has at most one two-sided identity;
if $*$ has a two-sided identity $e$ , then $e$ is the only left identity and the only right identity for $*$ .

No associativity is assumed.

Facts & Assumptions

Given: A binary operation $*$ on a set $S$ , an element $e \in S$ with $e * x = x$ for all $x \in S$ , and an element $f \in S$ with $x * f = x$ for all $x \in S$ (Left identity, right identity, and two-sided identity for a binary operation).

[A1]

$e$ is a left identity: $e * x = x$ for every $x \in S$ .

[A2]

$f$ is a right identity: $x * f = x$ for every $x \in S$ .

Proof

technique · direct

1.1

Evaluate $e * f$ using [A1] with $x = f$ : $e * f = f$ .

1.2

Evaluate the same element $e * f$ using [A2] with $x = e$ : $e * f = e$ .

2.1

The two evaluations are of the same element of $S$ , so $e = e * f = f$ .

step 1.1step 1.2

3.1

If $e_{1}$ and $e_{2}$ are two-sided identities, then $e_{1}$ is in particular a left identity and $e_{2}$ a right identity, so $e_{1} = e_{2}$ by step 2.1; this is claim 1.

step 2.1given

3.2

If $e$ is a two-sided identity and $g$ is any left identity, then $g$ is a left identity and $e$ a right identity, so $g = e$ by step 2.1; if $g$ is any right identity, then $e$ is a left identity and $g$ a right identity, so $e = g$ by step 2.1. This is claim 2.

step 2.1given

4.1

Hence a left identity and a right identity always coincide, and a two-sided identity, when it exists, is unique and is the unique one-sided identity on either side.

step 2.1step 3.1step 3.2∎

Remarks

The argument is the whole content of the phrase "the identity": the element $e * f$ is read in two ways, and the two readings are forced to agree. Nothing beyond the two defining equations is used, so the lemma applies to any binary operation whatever, associative or not.
The same two-readings device, one level up, gives uniqueness of inverses (In a monoid, a left inverse and a right inverse of the same element are equal; hence an invertible element has exactly one inverse, and it is two-sided); there associativity is needed, and it is what makes the argument work.

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (z-ai/glm-5.2)audited 2026-07-27Open item page →

Semigroup and monoid

Definition

A semigroup is a pair $(S, *)$ consisting of a set $S$ and an associative binary operation $*$ on $S$ (Binary operation on a set; associativity, commutativity, and a subset closed under the operation).

A monoid is a triple $(M, *, e)$ in which $(M, *)$ is a semigroup and $e \in M$ is a two-sided identity for $*$ (Left identity, right identity, and two-sided identity for a binary operation), that is,

$e * x = x = x * e for every x \in M .$

By A left identity and a right identity for the same binary operation are equal; hence there is at most one two-sided identity a binary operation has at most one two-sided identity, so $e$ is determined by $(M, *)$ and may be called the identity of $M$ ; it is written $e$ , or $e_{M}$ when several monoids are in play, and $1$ or $0$ in multiplicative or additive notation. For that reason a monoid is often written simply as $(M, *)$ , or as $M$ .

A semigroup or monoid is commutative (for monoids also called abelian) when its operation is commutative.

A subset $N \subseteq M$ is a submonoid when $e \in N$ and $N$ is closed under $*$ ; the restricted operation then makes $(N, *, e)$ a monoid, associativity being inherited (Binary operation on a set; associativity, commutativity, and a subset closed under the operation).

Remarks

The definite article is earned, not assumed. Writing "the identity" presupposes uniqueness, and that is exactly what A left identity and a right identity for the same binary operation are equal; hence there is at most one two-sided identity supplies, from the two defining equations alone. This is the first of the two uniqueness obligations on this page; the second is uniqueness of inverses (In a monoid, a left inverse and a right inverse of the same element are equal; hence an invertible element has exactly one inverse, and it is two-sided), which is what will license writing "the inverse".
A monoid is data, not a property. $(M, *, e)$ carries the identity as part of the structure. The uniqueness result says nothing is lost by suppressing it from the notation, and nothing is gained by keeping it.
Every group is a monoid (Group and abelian group), and the invertible elements of a monoid form a group (The invertible elements of a monoid form a group under the restricted operation), so the two notions are tied together in both directions.

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (z-ai/glm-5.2)audited 2026-07-27Open item page →

Left inverse, right inverse, and invertible element of a monoid

Definition

Let $(M, *, e)$ be a monoid (Semigroup and monoid) and let $g \in M$ . An element $h \in M$ is

a left inverse of $g$ when $h * g = e$ ;
a right inverse of $g$ when $g * h = e$ ;
a two-sided inverse, or simply an inverse, of $g$ when it is both, that is when $h * g = e = g * h$ .

The element $g$ is invertible, or a unit of $M$ , when it has a two-sided inverse. The set of units of $M$ is written $M^{\times}$ .

The identity is always invertible, since $e * e = e$ exhibits $e$ as a two-sided inverse of itself.

Remarks

One-sided inverses are not enough on their own. The definition keeps the three notions apart because the sharp uniqueness statement, and hence the right to write $g^{- 1}$ , is about their interaction: in a monoid a left inverse of $g$ and a right inverse of $g$ are automatically equal (In a monoid, a left inverse and a right inverse of the same element are equal; hence an invertible element has exactly one inverse, and it is two-sided). Until that is proved, "the inverse of $g$ " is not legitimate language.
$M^{\times}$ is a group under the restricted operation (The invertible elements of a monoid form a group under the restricted operation), and a monoid is a group exactly when $M^{\times} = M$ (Group and abelian group).

LemmaStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-27Open item page →

In a monoid, a left inverse and a right inverse of the same element are equal; hence an invertible element has exactly one inverse, and it is two-sided

Statement

Let $(M, *, e)$ be a monoid (Semigroup and monoid) and let $g \in M$ . If $h$ is a left inverse of $g$ and $h^{'}$ is a right inverse of $g$ (Left inverse, right inverse, and invertible element of a monoid), then $h = h^{'}$ . Consequently:

an invertible element $g$ has exactly one two-sided inverse, written $g^{- 1}$ ;
for an invertible $g$ , every left inverse of $g$ and every right inverse of $g$ equals $g^{- 1}$ , so a single one-sided equation $h * g = e$ or $g * h = e$ already forces $h = g^{- 1}$ ;
if $g$ has both a left inverse and a right inverse then $g$ is invertible.

Associativity is used, and is essential.

Facts & Assumptions

Given: A monoid $(M, *, e)$ , an element $g \in M$ , an element $h \in M$ with $h * g = e$ , and an element $h^{'} \in M$ with $g * h^{'} = e$ (Left inverse, right inverse, and invertible element of a monoid).

[A1]

$h * g = e$ .

[A2]

$g * h^{'} = e$ .

[L1]

$*$ is associative: $(x * y) * z = x * (y * z)$ for all $x, y, z \in M$ (Semigroup and monoid, Binary operation on a set; associativity, commutativity, and a subset closed under the operation).

[L2]

$e$ is a two-sided identity: $e * x = x = x * e$ for every $x \in M$ (Semigroup and monoid, Left identity, right identity, and two-sided identity for a binary operation).

Proof

technique · direct

1.1

Since $e$ is a right identity and $g * h^{'} = e$ , we may write $h = h * e = h * (g * h^{'})$ .

A2L2

1.2

Since $e$ is a left identity and $h * g = e$ , we may write $h^{'} = e * h^{'} = (h * g) * h^{'}$ .

A1L2

1.3

Associativity identifies the two right-hand sides: $h * (g * h^{'}) = (h * g) * h^{'}$ .

2.1

Combining, $h = h * (g * h^{'}) = (h * g) * h^{'} = h^{'}$ , which is the stated equality of a left inverse and a right inverse.

step 1.1step 1.2step 1.3

3.1

Claim 3: if $h$ is a left inverse and $h^{'}$ a right inverse of $g$ , then $h = h^{'}$ by step 2.1, so this common element satisfies both $h * g = e$ and $g * h = e$ and is a two-sided inverse; hence $g$ is invertible.

step 2.1A1A2

3.2

Claim 1: let $u$ and $v$ be two-sided inverses of $g$ . Then $u$ is a left inverse and $v$ is a right inverse of $g$ , so $u = v$ by step 2.1; the two-sided inverse of an invertible element is therefore unique, and the notation $g^{- 1}$ is legitimate.

step 2.1given

3.3

Claim 2: let $g$ be invertible with two-sided inverse $g^{- 1}$ . If $h * g = e$ then $h$ is a left inverse and $g^{- 1}$ is a right inverse of $g$ , so $h = g^{- 1}$ by step 2.1; if $g * h = e$ then $g^{- 1}$ is a left inverse and $h$ a right inverse, so $g^{- 1} = h$ by step 2.1.

step 2.1given

4.1

A left inverse and a right inverse of the same element coincide, an invertible element has exactly one inverse, and either one-sided equation already identifies it.

step 2.1step 3.1step 3.2step 3.3∎

Remarks

Where associativity enters. Step 1.3 is the only use of it, and it is indispensable: for a non-associative operation with a two-sided identity an element can have several distinct left inverses. This is why the lemma is stated for monoids and not for arbitrary operations with an identity, in contrast with A left identity and a right identity for the same binary operation are equal; hence there is at most one two-sided identity, which needs no associativity at all.
What this licenses. Group and abelian group defines a group as a monoid all of whose elements are invertible, and then writes $g^{- 1}$ and treats it as two-sided. Claim 1 is what makes that notation well defined, and claim 2 is the working form used throughout: to identify an inverse it suffices to verify one of the two equations, provided the element is already known to be invertible.

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (z-ai/glm-5.2)audited 2026-07-27Open item page →

Group and abelian group

Definition

A group is a monoid $(G, *, e)$ (Semigroup and monoid) in which every element is invertible (Left inverse, right inverse, and invertible element of a monoid). Written out, a group is a set $G$ with a binary operation $*$ (Binary operation on a set; associativity, commutativity, and a subset closed under the operation) and an element $e \in G$ such that

(G1) $(x * y) * z = x * (y * z)$ for all $x, y, z \in G$ ;
(G2) $e * x = x = x * e$ for every $x \in G$ ;
(G3) for every $x \in G$ there is $y \in G$ with $y * x = e = x * y$ .

By A left identity and a right identity for the same binary operation are equal; hence there is at most one two-sided identity the element $e$ of (G2) is unique, and by In a monoid, a left inverse and a right inverse of the same element are equal; hence an invertible element has exactly one inverse, and it is two-sided the element $y$ of (G3) is unique for each $x$ and is determined by either one of the two equations alone. So the notations $e$ for the identity and $x^{- 1}$ for the inverse of $x$ are legitimate, and asserting $y * x = e$ alone already says $y = x^{- 1}$ .

A group is abelian, or commutative, when its operation is commutative: $x * y = y * x$ for all $x, y \in G$ .

Notation. The operation is usually written multiplicatively, $x y$ for $x * y$ , with identity $e$ (or $1$ ) and inverse $x^{- 1}$ . For an abelian group it is often written additively, $x + y$ , with identity $0$ and inverse $- x$ ; the two notations describe the same notion and nothing below depends on the choice. We write $G$ for the group when the operation is understood.

Remarks

Why (G3) may be stated one-sidedly in practice. The axiom as written asks for a two-sided inverse. Because In a monoid, a left inverse and a right inverse of the same element are equal; hence an invertible element has exactly one inverse, and it is two-sided is proved before this definition, and is proved in the sharp form "a left inverse and a right inverse of the same element coincide", verifying either equation for a candidate $y$ suffices once the element is known to be invertible. Nothing on this page ever uses a one-sided inverse without that lemma standing behind it.
A group is a monoid, not merely like one. Every statement proved for monoids applies verbatim to groups. In the other direction the invertible elements of a monoid form a group (The invertible elements of a monoid form a group under the restricted operation), so groups arise inside every monoid.
The axioms are not independent of the notation, but the content is. Read additively, (G1)–(G3) are exactly the additive axioms in the definition of a field (Field), whose axiom (A) says in as many words that $(F, +)$ is an abelian group and whose axiom (M) says the same of $(F ∖ {0}, \cdot)$ ; so every field already carries two groups.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-27Open item page →

In a group $e^{- 1} = e$ , $(g^{- 1})^{- 1} = g$ and $(g h)^{- 1} = h^{- 1} g^{- 1}$ , the order of the last product being essential

Statement

Let $G$ be a group (Group and abelian group) with identity $e$ . For all $g, h \in G$ :

$e^{- 1} = e$ ;
$(g^{- 1})^{- 1} = g$ ; in particular inversion $g \mapsto g^{- 1}$ is its own two-sided inverse as a map $G \to G$ , hence a bijection of $G$ ;
$(g h)^{- 1} = h^{- 1} g^{- 1}$ ;
$(g h)^{- 1} = g^{- 1} h^{- 1}$ holds if and only if $g$ and $h$ commute. So the reversal of order in claim 3 cannot be dropped in general, and in an abelian group it may be.

Facts & Assumptions

Given: A group $G$ with identity $e$ , and elements $g, h \in G$ ; $g^{- 1}$ denotes the unique two-sided inverse of $g$ (Group and abelian group, Left inverse, right inverse, and invertible element of a monoid).

[L1]

Uniqueness of inverses in the sharp form: if $x$ is invertible and $y * x = e$ or $x * y = e$ , then $y = x^{- 1}$ ; and an element with a left and a right inverse is invertible with that common element as inverse (In a monoid, a left inverse and a right inverse of the same element are equal; hence an invertible element has exactly one inverse, and it is two-sided).

[L2]

The group axioms: $*$ is associative, $e$ is a two-sided identity, and every element has a two-sided inverse (Group and abelian group, Left identity, right identity, and two-sided identity for a binary operation).

Proof

technique · direct

1.1

$e e = e$ by the identity law, so $e$ is a two-sided inverse of $e$ ; since inverses are unique, $e^{- 1} = e$ , which is claim 1.

L1L2

1.2

The defining equations of $g^{- 1}$ are $g^{- 1} g = e$ and $g g^{- 1} = e$ ; read with $g^{- 1}$ in the role of the element being inverted, they say that $g$ is a two-sided inverse of $g^{- 1}$ . Uniqueness gives $(g^{- 1})^{- 1} = g$ , which is the equation of claim 2.

L1L2

1.3

Compute $(g h) (h^{- 1} g^{- 1}) = g (h h^{- 1}) g^{- 1} = g e g^{- 1} = g g^{- 1} = e$ , using associativity to regroup and the identity law twice.

1.4

Compute likewise $(h^{- 1} g^{- 1}) (g h) = h^{- 1} (g^{- 1} g) h = h^{- 1} e h = h^{- 1} h = e$ .

2.1

By steps 1.3 and 1.4 the element $h^{- 1} g^{- 1}$ is a two-sided inverse of $g h$ , so $g h$ is invertible and $(g h)^{- 1} = h^{- 1} g^{- 1}$ by uniqueness; this is claim 3.

step 1.3step 1.4L1

2.2

Inversion is a map $G \to G$ by claim (G3) and uniqueness, and step 1.2 says it composed with itself is the identity map of $G$ , so it is a bijection of $G$ onto itself; this completes claim 2.

step 1.2L1L2

3.1

Suppose $g h = h g$ . Applying step 2.1 to the pair $(h, g)$ gives $(h g)^{- 1} = g^{- 1} h^{- 1}$ , and $g h = h g$ gives $(g h)^{- 1} = (h g)^{- 1}$ ; hence $(g h)^{- 1} = g^{- 1} h^{- 1}$ .

step 2.1given

3.2

Conversely suppose $(g h)^{- 1} = g^{- 1} h^{- 1}$ . Taking inverses of both sides and using step 2.1 on the right and step 1.2 on the left gives $g h = ((g h)^{- 1})^{- 1} = (g^{- 1} h^{- 1})^{- 1} = (h^{- 1})^{- 1} (g^{- 1})^{- 1} = h g$ .

step 1.2step 2.1

4.1

Steps 3.1 and 3.2 give claim 4: $(g h)^{- 1} = g^{- 1} h^{- 1}$ holds exactly when $g$ and $h$ commute, so the reversal in claim 3 is essential precisely for non-commuting pairs, and is harmless in an abelian group.

step 3.1step 3.2

5.1

Claims 1, 2, 3 and 4 are established in steps 1.1, 2.2, 2.1 and 4.1.

step 1.1step 2.1step 2.2step 4.1∎

Remarks

Claim 4 is what makes the wording of claim 3 more than a stylistic preference: a pair with $(g h)^{- 1} \neq g^{- 1} h^{- 1}$ exists in a group exactly when some two of its elements fail to commute. That non-abelian groups exist is settled below by $Sym (X)$ is a group under composition, and it is non-abelian whenever $X$ has at least three distinct elements, which shows $Sym (X)$ is non-abelian whenever $X$ has three distinct elements.
Claim 2 is used constantly in the form "inversion is a bijection": a statement quantified over all $g$ may be re-read as a statement quantified over all $g^{- 1}$ without loss.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

Cancellation in a group: $g x = g y$ or $x g = y g$ forces $x = y$ ; equivalently left and right translation by $g$ are bijections of $G$ , so $g x = h$ and $x g = h$ each have exactly one solution

Statement

Let $G$ be a group (Group and abelian group) and let $g \in G$ . Define the left translation $λ_{g} : G \to G$ by $λ_{g} (x) = g x$ and the right translation $ρ_{g} : G \to G$ by $ρ_{g} (x) = x g$ . Then:

Cancellation. For all $x, y \in G$ : if $g x = g y$ then $x = y$ , and if $x g = y g$ then $x = y$ .
$λ_{g}$ and $ρ_{g}$ are bijections of $G$ (Injection, surjection, bijection), with inverse maps $λ_{g^{- 1}}$ and $ρ_{g^{- 1}}$ respectively.
For every $h \in G$ the equation $g x = h$ has exactly one solution in $G$ , namely $x = g^{- 1} h$ ; and $x g = h$ has exactly one solution, namely $x = h g^{- 1}$ .

Facts & Assumptions

Given: A group $G$ with identity $e$ , an element $g \in G$ with inverse $g^{- 1}$ , and the maps $λ_{g} (x) = g x$ , $ρ_{g} (x) = x g$ (Group and abelian group).

[L1]

The group axioms: associativity, $e$ a two-sided identity, and $g^{- 1} g = e = g g^{- 1}$ (Group and abelian group, Left identity, right identity, and two-sided identity for a binary operation).

[L3]

A map is bijective exactly when it has a two-sided inverse map; injective means $f (x) = f (y)$ forces $x = y$ (Injection, surjection, bijection).

Proof

technique · direct

1.1

Suppose $g x = g y$ . Multiplying on the left by $g^{- 1}$ and regrouping, $x = e x = (g^{- 1} g) x = g^{- 1} (g x) = g^{- 1} (g y) = (g^{- 1} g) y = e y = y$ .

1.2

Suppose $x g = y g$ . Multiplying on the right by $g^{- 1}$ and regrouping, $x = x e = x (g g^{- 1}) = (x g) g^{- 1} = (y g) g^{- 1} = y (g g^{- 1}) = y e = y$ .

1.3

For every $x \in G$ , $λ_{g^{- 1}} (λ_{g} (x)) = g^{- 1} (g x) = (g^{- 1} g) x = e x = x$ , and $λ_{g} (λ_{g^{- 1}} (x)) = g (g^{- 1} x) = (g g^{- 1}) x = e x = x$ .

1.4

For every $x \in G$ , $ρ_{g^{- 1}} (ρ_{g} (x)) = (x g) g^{- 1} = x (g g^{- 1}) = x$ , and $ρ_{g} (ρ_{g^{- 1}} (x)) = (x g^{- 1}) g = x (g^{- 1} g) = x$ .

1.5

Existence in claim 3: $g (g^{- 1} h) = (g g^{- 1}) h = e h = h$ , so $x = g^{- 1} h$ solves $g x = h$ ; and $(h g^{- 1}) g = h (g^{- 1} g) = h e = h$ , so $x = h g^{- 1}$ solves $x g = h$ .

2.1

Claim 1 is steps 1.1 and 1.2.

step 1.1step 1.2

2.2

By step 1.3 the map $λ_{g^{- 1}}$ is a two-sided inverse of $λ_{g}$ , so $λ_{g}$ is a bijection of $G$ with inverse $λ_{g^{- 1}}$ ; by step 1.4 the same holds for $ρ_{g}$ with inverse $ρ_{g^{- 1}}$ . This is claim 2.

step 1.3step 1.4L3

2.3

Uniqueness in claim 3: if $g x = h = g x^{'}$ then $x = x^{'}$ by step 1.1, and if $x g = h = x^{'} g$ then $x = x^{'}$ by step 1.2.

step 1.1step 1.2

3.1

Cancellation holds on both sides, both translations are bijections, and each of the two equations has exactly one solution.

step 2.1step 2.2step 1.5step 2.3∎

Remarks

Claim 2 is the form used most often: it says every row and every column of the multiplication table of a group is a rearrangement of $G$ , since $λ_{g}$ and $ρ_{g}$ permute $G$ . Inversion pairs $g$ with $g^{- 1}$ (In a group $e^{- 1} = e$ , $(g^{- 1})^{- 1} = g$ and $(g h)^{- 1} = h^{- 1} g^{- 1}$ , the order of the last product being essential), so the two families of translations are indexed by the same elements.
Cancellation is strictly weaker than invertibility. A commutative monoid can satisfy both cancellation laws without being a group; $(N, +)$ is such a monoid, recorded on the companion page.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-27Open item page →

The invertible elements of a monoid form a group under the restricted operation

Statement

Let $(M, *, e)$ be a monoid (Semigroup and monoid) and let $M^{\times}$ be its set of invertible elements (Left inverse, right inverse, and invertible element of a monoid). Then $M^{\times}$ contains $e$ , is closed under $*$ and under inversion, and $(M^{\times}, *, e)$ is a group (Group and abelian group), called the group of units of $M$ .

Moreover $M$ is itself a group exactly when $M^{\times} = M$ .

Facts & Assumptions

Given: A monoid $(M, *, e)$ and its set of units $M^{\times} = {g \in M : g has a two-sided inverse in M}$ (Left inverse, right inverse, and invertible element of a monoid).

[L1]

$*$ is associative and $e$ is a two-sided identity for it (Semigroup and monoid).

[L2]

An invertible $g$ has exactly one two-sided inverse $g^{- 1}$ (In a monoid, a left inverse and a right inverse of the same element are equal; hence an invertible element has exactly one inverse, and it is two-sided).

[L3]

A group is a monoid in which every element is invertible (Group and abelian group).

[L4]

If a subset of $M$ is closed under $*$ , the restriction of $*$ to it is a binary operation on it, and associativity is inherited (Binary operation on a set; associativity, commutativity, and a subset closed under the operation).

Proof

technique · direct

1.1

$e \in M^{\times}$ , since $e * e = e$ exhibits $e$ as a two-sided inverse of itself.

1.2

Let $g, h \in M^{\times}$ with inverses $g^{- 1}, h^{- 1}$ . Then $(g * h) * (h^{- 1} * g^{- 1}) = g * (h * h^{- 1}) * g^{- 1} = g * e * g^{- 1} = g * g^{- 1} = e$ and $(h^{- 1} * g^{- 1}) * (g * h) = h^{- 1} * (g^{- 1} * g) * h = h^{- 1} * e * h = h^{- 1} * h = e$ , the regroupings being licensed by associativity. So $h^{- 1} * g^{- 1}$ is a two-sided inverse of $g * h$ in $M$ , whence $g * h \in M^{\times}$ .

L1L2

1.3

Let $g \in M^{\times}$ . The equations $g^{- 1} * g = e = g * g^{- 1}$ read with $g^{- 1}$ as the element being inverted say that $g$ is a two-sided inverse of $g^{- 1}$ ; hence $g^{- 1} \in M^{\times}$ .

1.4

If $M^{\times} = M$ then $M$ is a monoid in which every element is invertible, that is a group; conversely if $M$ is a group then every element of $M$ is invertible, so $M \subseteq M^{\times}$ , and $M^{\times} \subseteq M$ always, giving $M^{\times} = M$ .

L3given

2.1

By step 1.2 the set $M^{\times}$ is closed under $*$ , so $*$ restricts to a binary operation on $M^{\times}$ , associative because it is associative on $M$ .

step 1.2L1L4

3.1

By step 1.1 the element $e$ lies in $M^{\times}$ , and $e * x = x = x * e$ holds for every $x \in M^{\times}$ because it holds for every $x \in M$ ; so $(M^{\times}, *, e)$ is a monoid.

step 1.1step 2.1L1

4.1

Every $g \in M^{\times}$ is invertible in $M^{\times}$ : its inverse $g^{- 1}$ lies in $M^{\times}$ by step 1.3, and the two equations $g^{- 1} * g = e = g * g^{- 1}$ are equations between elements of $M^{\times}$ . Hence $(M^{\times}, *, e)$ is a group.

step 1.3step 3.1L3

5.1

The units of $M$ form a group under the restricted operation, with the same identity, and this group is all of $M$ exactly when $M$ is a group.

step 3.1step 4.1step 1.4∎

Remarks

The point of step 4.1 is that invertibility is a condition relative to a containing structure: $g$ is a unit of $M^{\times}$ because the witness $g^{- 1}$ was shown to lie in $M^{\times}$ , not merely in $M$ . Skipping step 1.3 would leave a genuine gap.
The lemma is the source of most of the small examples of groups: the units of $(Z, \cdot)$ are ${1, - 1}$ , and the units of a field under multiplication are exactly the nonzero elements.

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (z-ai/glm-5.2)audited 2026-07-27Open item page →

The symmetric group $Sym (X)$ : the bijections of a set $X$ under composition

Definition

Let $X$ be a set. A permutation of $X$ is a bijection $f : X \to X$ (Injection, surjection, bijection). The symmetric group of $X$ is the set of all permutations of $X$ ,

$Sym (X) : = {f : X \to X : f is a bijection},$

equipped with composition as its operation,

$(f \circ g) (x) = f (g (x)) (x \in X),$

and with the identity map ${i d}_{X}$ , given by ${i d}_{X} (x) = x$ , as distinguished element.

Composition of two bijections of $X$ is again a bijection of $X$ (Injection, surjection, bijection), so $Sym (X)$ is closed under $\circ$ and $\circ$ is a binary operation on it (Binary operation on a set; associativity, commutativity, and a subset closed under the operation); and ${i d}_{X}$ is a bijection of $X$ , so it is an element of $Sym (X)$ , and it is a two-sided identity for composition (Left identity, right identity, and two-sided identity for a binary operation) because $f \circ {i d}_{X} = f = {i d}_{X} \circ f$ holds pointwise for every $f$ . That $(Sym (X), \circ, {i d}_{X})$ is a group is $Sym (X)$ is a group under composition, and it is non-abelian whenever $X$ has at least three distinct elements.

Cycle notation for a finite list of distinct points. For distinct elements $x_{0}, x_{1}, \dots, x_{k - 1}$ of $X$ with $k \geq 2$ , the symbol $(x_{0} x_{1} \dots x_{k - 1})$ denotes the permutation sending $x_{i}$ to $x_{i + 1}$ for $i < k - 1$ , sending $x_{k - 1}$ to $x_{0}$ , and fixing every element of $X$ outside ${x_{0}, \dots, x_{k - 1}}$ . It is a bijection, because the map described sends the set ${x_{0}, \dots, x_{k - 1}}$ onto itself by a rule with an evident inverse (send each $x_{i + 1}$ back to $x_{i}$ and $x_{0}$ back to $x_{k - 1}$ ) and fixes the complement pointwise. A transposition is such a symbol with $k = 2$ , that is $(a b)$ with $a \neq b$ : it exchanges $a$ and $b$ and fixes everything else, and it satisfies $(a b) \circ (a b) = {i d}_{X}$ .

A product of cycle symbols means their composite, so $(a b) (c d)$ is $(a b) \circ (c d)$ .

Remarks

Order of composition. With the convention $(f \circ g) (x) = f (g (x))$ the right-hand factor acts first. Both conventions are in use in the literature; this one is the one already fixed for function composition in the library and is the one used in every computation on this page and its companion.
Why this is defined here rather than with the finite symmetric groups. $Sym (X)$ for an arbitrary set $X$ is the ambient object needed as soon as one speaks of a group acting on a set, which is earlier in the reading order than the combinatorial study of $S_{n}$ ; homing it here keeps every citation of it backward-pointing.
The general cycle notation above is used on this page only for transpositions; cycles of length $3$ and $4$ , and products of two disjoint transpositions, appear on the companion examples page. The systematic theory, including the factorisation of an arbitrary permutation of a finite set into disjoint cycles, belongs to a later page.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-27Open item page →

$Sym (X)$ is a group under composition, and it is non-abelian whenever $X$ has at least three distinct elements

Statement

For every set $X$ , the triple $(Sym (X), \circ, {i d}_{X})$ of The symmetric group $Sym (X)$ : the bijections of a set $X$ under composition is a group (Group and abelian group); the inverse of a permutation $f$ is its inverse function $f^{- 1}$ .

If $X$ contains three distinct elements $a$ , $b$ , $c$ , then $Sym (X)$ is not abelian: the transpositions $τ = (a b)$ and $ρ = (b c)$ satisfy $τ \circ ρ \neq ρ \circ τ$ .

Facts & Assumptions

Given: A set $X$ ; $Sym (X)$ the set of bijections $X \to X$ with the operation $f \circ g$ defined by $(f \circ g) (x) = f (g (x))$ and the element ${i d}_{X}$ (The symmetric group $Sym (X)$ : the bijections of a set $X$ under composition); and, for the second claim, three distinct elements $a, b, c \in X$ together with the transpositions $τ = (a b)$ and $ρ = (b c)$ of The symmetric group $Sym (X)$ : the bijections of a set $X$ under composition.

[L1]

A composite of two bijections $X \to X$ is a bijection $X \to X$ , so $\circ$ is a binary operation on $Sym (X)$ ; ${i d}_{X}$ is a bijection; and a bijection $f$ has a two-sided inverse function $f^{- 1}$ , which is itself a bijection (Injection, surjection, bijection, The symmetric group $Sym (X)$ : the bijections of a set $X$ under composition).

[L2]

Two functions $X \to X$ are equal exactly when they agree at every point of $X$ .

[L3]

A group is a monoid in which every element is invertible; a monoid is an associative operation with a two-sided identity (Group and abelian group, Semigroup and monoid, Left inverse, right inverse, and invertible element of a monoid).

Proof

technique · direct

1.1

Composition is associative: for $f, g, h \in Sym (X)$ and $x \in X$ , both $((f \circ g) \circ h) (x)$ and $(f \circ (g \circ h)) (x)$ evaluate to $f (g (h (x)))$ , so the two composites agree at every point and are equal.

L2given

1.2

${i d}_{X}$ is a two-sided identity: for $f \in Sym (X)$ and $x \in X$ , $(f \circ {i d}_{X}) (x) = f (x)$ and $({i d}_{X} \circ f) (x) = f (x)$ , so $f \circ {i d}_{X} = f = {i d}_{X} \circ f$ .

L1L2given

1.3

Every $f \in Sym (X)$ is invertible in $Sym (X)$ : the inverse function $f^{- 1}$ is again a bijection $X \to X$ , hence lies in $Sym (X)$ , and it satisfies $f^{- 1} (f (x)) = x$ and $f (f^{- 1} (x)) = x$ for every $x$ , that is $f^{- 1} \circ f = {i d}_{X} = f \circ f^{- 1}$ .

L1L2

1.4

The transposition $τ = (a b)$ satisfies $τ (a) = b$ , $τ (b) = a$ and $τ (x) = x$ for $x \notin {a, b}$ ; the transposition $ρ = (b c)$ satisfies $ρ (b) = c$ , $ρ (c) = b$ and $ρ (x) = x$ for $x \notin {b, c}$ . Both are bijections of $X$ , being their own inverses.

givenL1

2.1

By steps 1.1 and 1.2 the pair $(Sym (X), \circ)$ with the element ${i d}_{X}$ is a monoid; by step 1.3 every element of it is invertible; hence it is a group, and the inverse of $f$ is the inverse function $f^{- 1}$ .

step 1.1step 1.2step 1.3L3

2.2

Evaluate the two composites at $c$ . Since $c \neq a$ and $c \neq b$ , $τ (c) = c$ , so $(ρ \circ τ) (c) = ρ (τ (c)) = ρ (c) = b$ . And $ρ (c) = b$ , so $(τ \circ ρ) (c) = τ (ρ (c)) = τ (b) = a$ .

step 1.4given

3.1

The two composites take different values at $c$ , because $a \neq b$ ; hence $τ \circ ρ \neq ρ \circ τ$ and $Sym (X)$ is not abelian.

step 2.2L2given

4.1

$Sym (X)$ is a group under composition, and it fails to be abelian as soon as $X$ has three distinct elements.

step 2.1step 3.1∎

Remarks

"Three distinct elements", not a cardinality hypothesis. The second claim is stated and proved with three named, pairwise distinct points of $X$ . No notion of the size of $X$ is used, so the statement is available for any $X$ whatever, finite or not, and needs nothing about counting.
For $X$ with at most two elements $Sym (X)$ is abelian: it has at most two elements itself, and any group with at most two elements is abelian, since one of any two of its elements is then the identity.
The witness pair $τ, ρ$ is reused on the companion page to show that the exponent law $(g h)^{n} = g^{n} h^{n}$ genuinely needs its commuting hypothesis.

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (z-ai/glm-5.2)audited 2026-07-27Open item page →

The product $g_{0} g_{1} \dots g_{n - 1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity

Definition

Let $(M, \cdot, e)$ be a monoid (Semigroup and monoid) and let $g : N \to M$ be a family of elements of $M$ , written $g_{i} : = g (i)$ . There is exactly one function $P_{g} : N \to M$ satisfying

$P_{g} (0) = e, P_{g} (σ (n)) = P_{g} (n) \cdot g_{n} (n \in N),$

and we write

$\prod_{i < n} g_{i} : = P_{g} (n), also written g_{0} g_{1} \dots g_{n - 1} .$

In particular the empty product is $\prod_{i < 0} g_{i} = e$ , and $\prod_{i < 1} g_{i} = e \cdot g_{0} = g_{0}$ .

Why the recursion is legitimate. The clause $P_{g} (σ (n)) = P_{g} (n) \cdot g_{n}$ consults $n$ as well as $P_{g} (n)$ , so The recursion theorem does not apply to it directly. Apply that theorem instead with the set $A = N \times M$ , the element $a = (0, e)$ , and the function $F : A \to A$ given by $F (n, x) = (σ (n), x \cdot g_{n})$ : it yields a unique $H : N \to N \times M$ with $H (0) = (0, e)$ and $H (σ (n)) = F (H (n))$ . Writing $H (n) = (H_{1} (n), H_{2} (n))$ , induction (The principle of mathematical induction) gives $H_{1} (n) = n$ for every $n$ , since $H_{1} (0) = 0$ and $H_{1} (σ (n)) = σ (H_{1} (n))$ . Hence $H (σ (n)) = (σ (n), H_{2} (n) \cdot g_{n})$ , so $P_{g} : = H_{2}$ satisfies the two displayed equations. It is the only such function: if $Q$ satisfies them too, then ${n : P_{g} (n) = Q (n)}$ contains $0$ and is closed under $σ$ , hence is all of $N$ by induction.

The value depends only on $g_{0}, \dots, g_{n - 1}$ . If $g, g^{'} : N \to M$ satisfy $g_{i} = g_{i}^{'}$ for every $i < n$ , then $P_{g} (n) = P_{g^{'}} (n)$ . Indeed the set of $n$ for which this implication holds contains $0$ , both products then being $e$ ; and if it holds at $n$ , and $g, g^{'}$ agree at every $i < σ (n)$ , then they agree at every $i < n$ and also at $n$ itself, because $i < σ (n)$ is equivalent to $i \leq n$ (On $N$ the order is membership: $m < n ⟺ m \in n$ ), so $P_{g} (σ (n)) = P_{g} (n) \cdot g_{n} = P_{g^{'}} (n) \cdot g_{n}^{'} = P_{g^{'}} (σ (n))$ . Induction finishes it. This is what makes the notation $g_{0} g_{1} \dots g_{n - 1}$ unambiguous: it names a value determined by the first $n$ terms alone, and a finite list $u$ of length $n$ , that is a function $u : n \to M$ on the von Neumann natural $n = {0, \dots, n - 1}$ (The natural numbers $N$ (von Neumann)), determines the product $\prod_{i < n} u_{i} : = P_{\tilde{u}} (n)$ computed from any extension $\tilde{u} : N \to M$ of $u$ .

Remarks

The empty product is the identity, and this is not a convention chosen for convenience. It is forced by the recursion, whose base clause is $P_{g} (0) = e$ , and it is what makes the induction in Generalised associativity: in a monoid the product of a finite list does not depend on the bracketing, and in a commutative monoid it does not depend on the order of the factors either start. $N$ contains $0$ (The natural numbers $N$ (von Neumann)), so $n = 0$ is a genuine case of every statement below, never an afterthought.
The factors are multiplied left to right: $P_{g} (σ (n))$ appends $g_{n}$ on the right. Nothing depends on that choice, because Generalised associativity: in a monoid the product of a finite list does not depend on the bracketing, and in a commutative monoid it does not depend on the order of the factors either shows the value is unchanged by any regrouping of consecutive factors; but the choice must be made, since the recursion has to say where the new factor goes.
The existing Finite sums and finite products, by recursion is a different object: it is stated for sequences $N \to R$ in the complete ordered field, and its multiplicative alias already names the product of real numbers. It cannot carry a product in an arbitrary monoid, which is why this item exists.

TheoremStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-27Open item page →

Generalised associativity: in a monoid the product of a finite list does not depend on the bracketing, and in a commutative monoid it does not depend on the order of the factors either

Statement

Let $(M, \cdot, e)$ be a monoid and let $g : N \to M$ , with finite products $\prod_{i < n} g_{i}$ as in The product $g_{0} g_{1} \dots g_{n - 1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity.

Splitting law. For all $m, n \in N$ ,

$\prod_{i < m + n} g_{i} = (\prod_{i < m} g_{i}) \cdot (\prod_{j < n} g_{m + j}) .$
Regrouping law (bracketing does not matter). Let $s : N \to N$ satisfy $s_{0} = 0$ and $s_{j} \leq s_{σ (j)}$ for every $j$ , and for each $j$ let $c_{j}$ be the unique natural number with $s_{j} + c_{j} = s_{σ (j)}$ . Put $B_{j} : = \prod_{l < c_{j}} g_{s_{j} + l}$ , the product of the $j$ -th block of consecutive factors. Then for every $r \in N$ ,

$\prod_{j < r} B_{j} = \prod_{i < s_{r}} g_{i} .$

In words: cut the list $g_{0}, \dots, g_{s_{r} - 1}$ into consecutive blocks in any way whatever, multiply out each block, and multiply the results in order; the answer is the product of the whole list.
Commutative case (order does not matter). Suppose in addition that $M$ is commutative. Let $n \in N$ and let $π \in Sym (n)$ be a permutation of the von Neumann natural $n = {0, \dots, n - 1}$ (The symmetric group $Sym (X)$ : the bijections of a set $X$ under composition). Let $h : N \to M$ be any family with $h_{i} = g_{π (i)}$ for every $i < n$ . Then

$\prod_{i < n} h_{i} = \prod_{i < n} g_{i} .$

Facts & Assumptions

Given: A monoid $(M, \cdot, e)$ , a family $g : N \to M$ , and the products of The product $g_{0} g_{1} \dots g_{n - 1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity, which satisfy $\prod_{i < 0} u_{i} = e$ and $\prod_{i < σ (n)} u_{i} = (\prod_{i < n} u_{i}) \cdot u_{n}$ for every family $u : N \to M$ , and whose value $\prod_{i < n} u_{i}$ depends only on $u_{0}, \dots, u_{n - 1}$ .

[L1]

Induction on $N$ (The principle of mathematical induction).

[L2]

The monoid laws: $\cdot$ is associative and $e$ is a two-sided identity (Semigroup and monoid).

[L3]

Addition on $N$ : $m + 0 = m$ and $m + σ (n) = σ (m + n)$ , so in particular $m + 1 = σ (m)$ (Addition of natural numbers); addition is commutative and associative (Addition is commutative, Addition is associative) and cancellative (Addition is cancellative).

[L4]

Order on $N$ : $m \leq n$ means $m + k = n$ for some $k \in N$ , and $m < n$ means $m \leq n$ with $m \neq n$ (Order on the natural numbers); $m \leq n ⟺ m + k \leq n + k$ and $m < n ⟺ m + k < n + k$ (Order is compatible with addition); exactly one of $m < n$ , $m = n$ , $n < m$ holds (Trichotomy of the order on $N$ ); $m < n ⟺ σ (m) \leq n$ (Discreteness: $σ (n)$ is the immediate successor); and every $n \neq 0$ is a successor (Every nonzero natural number is a successor).

[L5]

On $N$ the order is membership: $m < n ⟺ m \in n$ , so $n = {m : m < n}$ ; and $m < σ (n) ⟺ m \leq n$ ; and $n \notin n$ (On $N$ the order is membership: $m < n ⟺ m \in n$ , The natural numbers $N$ (von Neumann)).

[L6]

A permutation of $n$ is a bijection $n \to n$ ; bijections are injective and surjective, and composites of injections are injective (The symmetric group $Sym (X)$ : the bijections of a set $X$ under composition, Injection, surjection, bijection).

Proof

technique · induction

1.1

Splitting law, base $n = 0$ : the left side is $\prod_{i < m + 0} g_{i} = \prod_{i < m} g_{i}$ , and the right side is $(\prod_{i < m} g_{i}) \cdot \prod_{j < 0} g_{m + j} = (\prod_{i < m} g_{i}) \cdot e = \prod_{i < m} g_{i}$ ; so the two agree, for every $m$ .

basegivenL2L3

1.2

Splitting law, inductive hypothesis: fix $n$ and assume $\prod_{i < m + n} g_{i} = (\prod_{i < m} g_{i}) \cdot (\prod_{j < n} g_{m + j})$ for every $m$ and every family $g$ .

1.3

Write $u_{j} : = g_{m + j}$ , a family $N \to M$ , so that $\prod_{j < n} g_{m + j} = \prod_{j < n} u_{j}$ and $u_{n} = g_{m + n}$ .

given

1.4

In claim 2 the natural $c_{j}$ exists because $s_{j} \leq s_{σ (j)}$ , and it is unique by cancellation, so $B_{j}$ is well defined for every $j$ and $B : N \to M$ is a family.

givenL3L4

1.5

Regrouping law, base $r = 0$ : the left side is $\prod_{j < 0} B_{j} = e$ and the right side is $\prod_{i < s_{0}} g_{i} = \prod_{i < 0} g_{i} = e$ .

basegiven

1.6

Regrouping law, inductive hypothesis: assume $\prod_{j < r} B_{j} = \prod_{i < s_{r}} g_{i}$ for this $r$ .

1.7

Commutative case, base $n = 0$ : both products are empty, hence both equal $e$ .

basegiven

1.8

Commutative case, inductive hypothesis: fix $n$ and assume that for every family $g$ , every $π \in Sym (n)$ and every family $h$ with $h_{i} = g_{π (i)}$ for $i < n$ , one has $\prod_{i < n} h_{i} = \prod_{i < n} g_{i}$ .

1.9

Successor step, the data. Let $π \in Sym (σ (n))$ and let $h$ satisfy $h_{i} = g_{π (i)}$ for every $i < σ (n)$ . Put $k : = π^{- 1} (n)$ , so $k < σ (n)$ , that is $k \leq n$ , and let $r$ be the natural with $k + r = n$ ; then $k + σ (r) = σ (k + r) = σ (n)$ .

givenL3L4L5L6choose

1.10

The skip map. Define $δ : N \to N$ by $δ (i) = i$ when $i < k$ and $δ (i) = σ (i)$ when $k \leq i$ ; the two clauses are exhaustive and mutually exclusive by trichotomy, so $δ$ is a function. It is injective: two arguments below $k$ with equal images are equal; two arguments at least $k$ have equal images only if their successors agree, hence only if they agree; and if $i < k \leq j$ then $δ (i) = i < k \leq j < σ (j) = δ (j)$ .

L4L5construct

2.1

Splitting law, successor step: $m + σ (n) = σ (m + n)$ , so $\prod_{i < m + σ (n)} g_{i} = \prod_{i < σ (m + n)} g_{i} = (\prod_{i < m + n} g_{i}) \cdot g_{m + n}$ ; applying the hypothesis and then associativity, this equals $((\prod_{i < m} g_{i}) \cdot \prod_{j < n} u_{j}) \cdot u_{n} = (\prod_{i < m} g_{i}) \cdot ((\prod_{j < n} u_{j}) \cdot u_{n}) = (\prod_{i < m} g_{i}) \cdot \prod_{j < σ (n)} u_{j}$ , which is the claim at $σ (n)$ .

step 1.2step 1.3givenL2L3

2.2

$δ$ maps $n$ into $σ (n) ∖ {k}$ , and onto it. If $i < k$ then $δ (i) = i \neq k$ and $i < k \leq n < σ (n)$ . If $k \leq i < n$ then $δ (i) = σ (i)$ with $k \leq i < σ (i)$ , so $δ (i) \neq k$ , and $i < n$ gives $σ (i) < σ (n)$ by compatibility of the order with adding $1$ . Conversely let $y < σ (n)$ with $y \neq k$ . If $y < k$ then $y < k \leq n$ , so $y < n$ and $y = δ (y)$ . If $k < y$ then $y \neq 0$ , so $y = σ (x)$ for some $x$ ; from $k < σ (x)$ we get $k \leq x$ , and from $σ (x) < σ (n)$ we get $x < n$ , so $y = σ (x) = δ (x)$ with $x < n$ .

step 1.9step 1.10L4L5

3.1

By induction the splitting law holds for all $m, n \in N$ ; this is claim 1.

step 1.1step 2.1L1

3.2

The reduced permutation. Set $π^{'} : = π \circ δ$ restricted to $n$ . By step 2.2 it maps $n$ into $π [σ (n) ∖ {k}]$ , and since $π$ is a bijection of $σ (n)$ with $π (k) = n$ , that image set is $σ (n) ∖ {n} = n$ ; the same step gives surjectivity onto it, and $π^{'}$ is injective as a composite of injections. So $π^{'} \in Sym (n)$ .

step 1.9step 2.2L5L6

4.1

Regrouping law, successor step: $\prod_{j < σ (r)} B_{j} = (\prod_{j < r} B_{j}) \cdot B_{r} = (\prod_{i < s_{r}} g_{i}) \cdot \prod_{l < c_{r}} g_{s_{r} + l}$ by the hypothesis, and the splitting law with $m = s_{r}$ and $n = c_{r}$ turns the right-hand side into $\prod_{i < s_{r} + c_{r}} g_{i} = \prod_{i < s_{σ (r)}} g_{i}$ . By induction claim 2 holds for every $r$ .

step 3.1step 1.4step 1.5step 1.6givenL1

4.2

Splitting the permuted product. By step 1.9 and the splitting law, $\prod_{i < σ (n)} h_{i} = \prod_{i < k + σ (r)} h_{i} = (\prod_{i < k} h_{i}) \cdot (\prod_{j < σ (r)} h_{k + j})$ ; and since $σ (r) = 1 + r$ , a second application of the splitting law to the family $j \mapsto h_{k + j}$ gives $\prod_{j < σ (r)} h_{k + j} = (\prod_{j < 1} h_{k + j}) \cdot (\prod_{l < r} h_{k + 1 + l}) = h_{k} \cdot \prod_{l < r} h_{k + σ (l)}$ .

step 3.1step 1.9givenL3

4.3

Recognising the shorter permuted product. Let $w_{i} : = h_{δ (i)}$ . For $i < k$ one has $w_{i} = h_{i}$ , and for $l < r$ one has $w_{k + l} = h_{σ (k + l)} = h_{k + σ (l)}$ ; so the splitting law at $m = k$ , $n = r$ gives $\prod_{i < n} w_{i} = (\prod_{i < k} h_{i}) \cdot \prod_{l < r} h_{k + σ (l)}$ . Moreover $w_{i} = h_{δ (i)} = g_{π (δ (i))} = g_{π^{'} (i)}$ for every $i < n$ , by step 2.2 and step 3.2.

step 3.1step 1.9step 1.10step 2.2step 3.2L3

5.1

Moving the removed factor to the end. $h_{k} = g_{π (k)} = g_{n}$ , and $M$ is commutative, so $(\prod_{i < k} h_{i}) \cdot (h_{k} \cdot \prod_{l < r} h_{k + σ (l)}) = ((\prod_{i < k} h_{i}) \cdot \prod_{l < r} h_{k + σ (l)}) \cdot g_{n}$ , using commutativity to exchange $h_{k}$ with the block to its right and associativity to regroup.

step 1.9step 4.2givenL2

6.1

Applying the hypothesis. The family $w$ satisfies $w_{i} = g_{π^{'} (i)}$ for $i < n$ with $π^{'} \in Sym (n)$ , so the inductive hypothesis gives $\prod_{i < n} w_{i} = \prod_{i < n} g_{i}$ ; combining with steps 4.2, 5.1 and 4.3, $\prod_{i < σ (n)} h_{i} = (\prod_{i < n} g_{i}) \cdot g_{n} = \prod_{i < σ (n)} g_{i}$ , which is the claim at $σ (n)$ .

step 1.8step 3.2step 4.2step 5.1step 4.3given

7.1

By induction claim 3 holds for every $n$ ; with claims 1 and 2 already established, the theorem is proved.

step 3.1step 4.1step 1.7step 6.1L1discharge-induction∎

Remarks

What "does not depend on the bracketing" means here, exactly. The library introduces no formal syntax of bracketed expressions, so the claim is made in the equivalent working form of claim 2: any way of cutting the list into consecutive blocks, multiplying each block out, and multiplying the block values in order returns the same element. Every bracketing of $g_{0} g_{1} \dots g_{n - 1}$ is obtained by iterating that cut, so claim 2 is what is used whenever one drops brackets in a long product.
The order of the factors is a separate question from the bracketing. Claim 2 holds in any monoid and never moves a factor past another; claim 3 does move factors, and is false without commutativity. In $Sym ({1, 2, 3})$ the two transpositions $(1 2)$ and $(2 3)$ already give $τ ρ \neq ρ τ$ ( $Sym (X)$ is a group under composition, and it is non-abelian whenever $X$ has at least three distinct elements).
The empty product carries the induction. Both inductions start at $n = 0$ with the value $e$ ; $N$ contains $0$ , so this is a real base case and not a degenerate convention.

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (z-ai/glm-5.2)audited 2026-07-27Open item page →

Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$

Definition

Natural exponents, in a monoid. Let $(M, \cdot, e)$ be a monoid (Semigroup and monoid) and $g \in M$ . By the recursion theorem (The recursion theorem), applied with the set $M$ , the element $e$ and the function $x \mapsto x \cdot g$ from $M$ to $M$ , there is exactly one function $N \to M$ , written $n \mapsto g^{n}$ , with

$g^{0} = e, g^{σ (n)} = g^{n} \cdot g (n \in N) .$

In particular $g^{0} = e$ for every $g$ , including $g = e$ , and $g^{1} = g^{σ (0)} = e \cdot g = g$ . Since $N$ contains $0$ (The natural numbers $N$ (von Neumann)), the exponent $0$ is a genuine value of the definition and not a separate convention.

Integer exponents, in a group. Let $G$ be a group (Group and abelian group) and $g \in G$ . Write $ι : N \to Z$ for the embedding $ι (k) = [(k, 0)]$ of The naturals embed in the integers, which is injective, preserves addition, multiplication and order, and has as image exactly the nonnegative integers. For $x \in Z$ define

$g^{x} : = g^{k}$ , the natural power, when $0 \leq x$ and $x = ι (k)$ ;
$g^{x} : = (g^{k})^{- 1}$ when $x < 0$ and $- x = ι (k)$ .

Why this is well defined. The order on $Z$ is total and antisymmetric (The integers form a totally ordered ring, Order on the integers), so exactly one of $0 \leq x$ and $x < 0$ holds and the two clauses never both apply. In the first clause $x$ is nonnegative, so $x = ι (k)$ for some $k \in N$ , and $k$ is unique because $ι$ is injective. In the second clause $x < 0$ gives $0 = x + (- x) < 0 + (- x) = - x$ by compatibility of the order with addition (The integers form a totally ordered ring, Arithmetic on the integers), so $- x$ is a positive integer and again $- x = ι (k)$ for a unique $k$ . The inverse $(g^{k})^{- 1}$ is a single determined element by In a monoid, a left inverse and a right inverse of the same element are equal; hence an invertible element has exactly one inverse, and it is two-sided and Left inverse, right inverse, and invertible element of a monoid. Finally the two readings of $g^{ι (k)}$ , as a natural power and as an integer power, agree by construction, so no ambiguity is introduced.

Abbreviation. In an exponent we write $k$ for the integer $ι (k)$ when a natural number $k$ is used where an integer is expected; this is unambiguous because $ι$ is injective and preserves the arithmetic and the order, and because the two readings of $g^{k}$ agree as just noted.

Additive notation. When the group is written additively the same object is written $n g$ or $n \cdot g$ rather than $g^{n}$ , with $0 g = 0$ and $σ (n) g = n g + g$ ; the definitions are identical, only the symbols differ.

Remarks

The case split is on the integer, not on a representative. An integer is an equivalence class $[(a, b)]$ of pairs of naturals (The integers as equivalence classes of pairs of naturals), so a definition of $g^{x}$ by a formula in $a$ and $b$ would carry a well-definedness obligation. The definition above avoids that entirely: it splits on the sign of $x$ , which is a property of the integer itself, and then uses the unique natural supplied by The naturals embed in the integers.
Negative exponents need a group, not merely a monoid. The second clause uses an inverse, which a monoid need not have. Natural powers are available in any monoid, and every statement below says which of the two settings it is in.
The exponent is an index, an element of $N$ or of $Z$ , and never an element of the group. No canonical-natural machinery (The canonical natural $ι (n) = n \cdot 1_{F}$ of a field) is involved: that item is about the image of $N$ inside a field, a different map with the same traditional name.
The laws $g^{m + n} = g^{m} g^{n}$ , $(g^{m})^{n} = g^{m n}$ and, when $g$ and $h$ commute, $(g h)^{n} = g^{n} h^{n}$ are proved in Exponent laws in a group: $g^{m + n} = g^{m} g^{n}$ and $(g^{m})^{n} = g^{m n}$ for all $m, n \in Z$ , and $(g h)^{n} = g^{n} h^{n}$ when $g$ and $h$ commute. The last one is false without the commuting hypothesis.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-27Open item page →

Exponent laws in a group: $g^{m + n} = g^{m} g^{n}$ and $(g^{m})^{n} = g^{m n}$ for all $m, n \in Z$ , and $(g h)^{n} = g^{n} h^{n}$ when $g$ and $h$ commute

Statement

Let $G$ be a group (Group and abelian group) with identity $e$ , let $g, h \in G$ , and let powers be as in Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ . For all $m, n \in Z$ :

$g^{m + n} = g^{m} g^{n}$ ;
$g^{- m} = (g^{m})^{- 1}$ ;
$(g^{m})^{n} = g^{m n}$ ;
$g^{m} g^{n} = g^{n} g^{m}$ : any two powers of one element commute;
if $g h = h g$ then $(g h)^{n} = g^{n} h^{n}$ .

Claim 5 is false in general without its hypothesis: in a group in which $g$ and $h$ do not commute the equation can fail already at $n = 2$ , and a witness is recorded on the companion page.

Claims 1 and 3 hold in any monoid (Semigroup and monoid) for exponents in $N$ , and so does claim 5 for exponents in $N$ under the same commuting hypothesis; only the extension to negative exponents needs inverses.

Facts & Assumptions

Given: A group $G$ with identity $e$ and elements $g, h \in G$ ; powers $g^{n}$ for $n \in N$ defined by $g^{0} = e$ and $g^{σ (n)} = g^{n} g$ , and $g^{x}$ for $x \in Z$ defined by $g^{ι (k)} = g^{k}$ and $g^{- ι (k)} = (g^{k})^{- 1}$ for $ι (k) > 0$ (Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ ). Throughout, $ι : N \to Z$ is the embedding of The naturals embed in the integers, and a natural number written where an integer is expected means its image under $ι$ .

[L1]

Induction on $N$ (The principle of mathematical induction).

[L2]

The group laws: associativity, the two-sided identity $e$ , and two-sided inverses (Group and abelian group, Semigroup and monoid).

[L3]

$(u v)^{- 1} = v^{- 1} u^{- 1}$ , $(u^{- 1})^{- 1} = u$ and $e^{- 1} = e$ in a group (In a group $e^{- 1} = e$ , $(g^{- 1})^{- 1} = g$ and $(g h)^{- 1} = h^{- 1} g^{- 1}$ , the order of the last product being essential).

[L4]

$ι$ is injective, preserves addition, multiplication and order, and its image is exactly the set of nonnegative integers; $ι (0) = 0$ and $ι (1) = 1$ (The naturals embed in the integers, Arithmetic on the integers).

[L5]

$Z$ is a commutative ring: addition and multiplication are associative and commutative, $x + 0 = x$ , $x \cdot 1 = x$ , multiplication distributes over addition, and every $x$ has an additive inverse $- x$ (The integers form a commutative ring, Arithmetic on the integers); every integer is $[(a, b)]$ for naturals $a, b$ , and then $[(a, b)] = ι (a) - ι (b)$ (The integers as equivalence classes of pairs of naturals).

[L6]

The order on $Z$ is total and compatible with addition, so exactly one of $0 \leq x$ , $x < 0$ holds, and $x < 0$ implies $0 < - x$ (The integers form a totally ordered ring, Order on the integers).

[L7]

On $N$ : addition satisfies $m + 0 = m$ and $m + σ (n) = σ (m + n)$ , so $σ (n) = n + 1$ (Addition of natural numbers, The natural numbers $N$ (von Neumann)); it is commutative (Addition is commutative); $m \leq n$ means $m + k = n$ for some $k$ (Order on the natural numbers); and exactly one of $a < b$ , $a = b$ , $b < a$ holds (Trichotomy of the order on $N$ ).

Proof

technique · induction

1.1

Natural exponents, base of claim 1: for every $m \in N$ , $g^{m + 0} = g^{m} = g^{m} e = g^{m} g^{0}$ .

basegivenL2L7

1.2

Natural exponents, inductive hypothesis for claim 1: fix $n \in N$ and assume $g^{m + n} = g^{m} g^{n}$ for every $m \in N$ and every $g$ .

1.3

Suppose $g h = h g$ ; base of the commuting sub-claim: $g h^{0} = g e = e g = h^{0} g$ .

basegivenL2

1.4

Inductive hypothesis of the commuting sub-claim: assume $g h^{n} = h^{n} g$ .

1.5

Base of claim 5 for natural exponents: $(g h)^{0} = e = e \cdot e = g^{0} h^{0}$ .

basegivenL2

1.6

Inductive hypothesis of claim 5 for natural exponents: assume $g h = h g$ and $(g h)^{n} = g^{n} h^{n}$ .

1.7

If $u v = v u$ in $G$ then $u v^{- 1} = v^{- 1} u$ : multiplying $u v = v u$ on the left and on the right by $v^{- 1}$ gives $v^{- 1} (u v) v^{- 1} = v^{- 1} (v u) v^{- 1}$ , and regrouping both sides gives $v^{- 1} u = u v^{- 1}$ . Consequently $u^{- 1} v^{- 1} = (v u)^{- 1} = (u v)^{- 1} = v^{- 1} u^{- 1}$ .

L2L3

1.8

Claim 2 for a nonnegative exponent. If $k = 0$ then $- ι (0) = 0$ , so $g^{- ι (0)} = g^{0} = e$ and $(g^{0})^{- 1} = e^{- 1} = e$ . If $k \neq 0$ then $0 < ι (k)$ because $ι$ preserves the order, so $- ι (k) < 0$ and the second clause of the definition gives $g^{- ι (k)} = (g^{k})^{- 1}$ directly.

givenL3L4L6

1.9

Claim 3 for a nonnegative second exponent, base: $(g^{x})^{0} = e = g^{0} = g^{x \cdot 0}$ , since $x \cdot 0 = 0$ in $Z$ .

basegivenL5

1.10

Claim 3 for a nonnegative second exponent, inductive hypothesis: assume $(g^{x})^{ι (n)} = g^{x ι (n)}$ for this $n \in N$ and every $x \in Z$ .

2.1

Successor step for claim 1 with natural exponents: $g^{m + σ (n)} = g^{σ (m + n)} = g^{m + n} g = (g^{m} g^{n}) g = g^{m} (g^{n} g) = g^{m} g^{σ (n)}$ ; by induction, $g^{m + n} = g^{m} g^{n}$ for all $m, n \in N$ , in any monoid.

step 1.2givenL1L2L7

2.2

Successor step for the commuting sub-claim: $g h^{σ (n)} = g (h^{n} h) = (g h^{n}) h = (h^{n} g) h = h^{n} (g h) = h^{n} (h g) = (h^{n} h) g = h^{σ (n)} g$ ; by induction $g h^{n} = h^{n} g$ for every $n \in N$ whenever $g h = h g$ .

step 1.3step 1.4givenL1L2

2.3

Claim 2 in general. If $0 \leq x$ then $x = ι (k)$ and step 1.8 gives $g^{- x} = (g^{k})^{- 1} = (g^{x})^{- 1}$ . If $x < 0$ then $0 < - x$ , so $- x = ι (k)$ and by definition $g^{x} = (g^{k})^{- 1}$ , whence $(g^{x})^{- 1} = g^{k} = g^{- x}$ . This is claim 2.

step 1.8givenL3L4L6

3.1

Successor step for claim 5 with natural exponents: assuming $g h = h g$ , $(g h)^{σ (n)} = (g h)^{n} (g h) = (g^{n} h^{n}) (g h) = g^{n} ((h^{n} g) h) = g^{n} ((g h^{n}) h) = (g^{n} g) (h^{n} h) = g^{σ (n)} h^{σ (n)}$ , the fourth equality being step 2.2 applied to $g$ and $h^{n}$ ; by induction $(g h)^{n} = g^{n} h^{n}$ for every $n \in N$ .

step 1.5step 1.6step 2.2givenL1L2

3.2

Normal form. Let $x \in Z$ and write $x = ι (a) - ι (b)$ with $a, b \in N$ , possible since $x = [(a, b)]$ for some naturals. Then $g^{x} = g^{a} (g^{b})^{- 1}$ . Indeed, by trichotomy either $b \leq a$ , say $a = b + c$ , in which case $x = ι (c)$ and $g^{a} (g^{b})^{- 1} = (g^{b} g^{c}) (g^{b})^{- 1} = (g^{c} g^{b}) (g^{b})^{- 1} = g^{c} = g^{x}$ , using step 2.1 twice together with commutativity of addition on $N$ ; or $a < b$ , say $b = a + c$ with $c \neq 0$ , in which case $x = - ι (c)$ and $g^{a} (g^{b})^{- 1} = g^{a} (g^{a} g^{c})^{- 1} = g^{a} ((g^{c})^{- 1} (g^{a})^{- 1}) = ((g^{c})^{- 1} g^{a}) (g^{a})^{- 1} = (g^{c})^{- 1} = g^{x}$ , the third equality using step 1.7 with $u = g^{a}$ and $v = g^{c}$ , which commute by step 2.1.

step 1.7step 2.1step 1.8givenL2L3L4L5L7

4.1

Claim 1 for integer exponents. Write $x = ι (a) - ι (b)$ and $y = ι (c) - ι (d)$ , so $x + y = ι (a + c) - ι (b + d)$ . By step 3.2 and step 2.1, $g^{x + y} = g^{a + c} (g^{b + d})^{- 1} = (g^{a} g^{c}) (g^{b} g^{d})^{- 1} = (g^{a} g^{c}) ((g^{d})^{- 1} (g^{b})^{- 1})$ . On the other side $g^{x} g^{y} = (g^{a} (g^{b})^{- 1}) (g^{c} (g^{d})^{- 1}) = (g^{a} g^{c}) ((g^{b})^{- 1} (g^{d})^{- 1})$ , moving $(g^{b})^{- 1}$ past $g^{c}$ by step 1.7, since $g^{b}$ and $g^{c}$ commute by step 2.1. Finally $(g^{b})^{- 1} (g^{d})^{- 1} = (g^{d})^{- 1} (g^{b})^{- 1}$ by step 1.7 again, so the two sides agree.

step 1.7step 2.1step 3.2L2L3L4L5

4.2

Claim 5 for a negative exponent: assume $g h = h g$ and let $n < 0$ , so $- n = ι (k)$ with $k \in N$ . Then $(g h)^{n} = ((g h)^{- n})^{- 1} = (g^{k} h^{k})^{- 1} = (h^{k})^{- 1} (g^{k})^{- 1} = h^{n} g^{n}$ by claim 2 and step 3.1; and $g^{k}$ and $h^{k}$ commute, by step 2.2 applied twice, so their inverses commute by step 1.7, giving $h^{n} g^{n} = g^{n} h^{n}$ . With step 3.1 this proves claim 5 for every $n \in Z$ .

step 1.7step 2.2step 3.1step 2.3L3L6

5.1

Claim 4. By claim 1 and commutativity of addition in $Z$ , $g^{x} g^{y} = g^{x + y} = g^{y + x} = g^{y} g^{x}$ .

step 4.1L5

5.2

Claim 3, successor step: $(g^{x})^{σ (n)} = (g^{x})^{n} g^{x} = g^{x ι (n)} g^{x} = g^{x ι (n) + x} = g^{x (ι (n) + 1)} = g^{x ι (σ (n))}$ , using the hypothesis, then claim 1, then distributivity in $Z$ , then $ι (σ (n)) = ι (n + 1) = ι (n) + 1$ . By induction, $(g^{x})^{y} = g^{x y}$ for every $x \in Z$ and every $y \geq 0$ . When $x = ι (m)$ is itself nonnegative the two exponents $x ι (n)$ and $x$ occurring here are nonnegative as well, so the appeal to claim 1 is an appeal to its monoid form, step 2.1, and the computation uses no inverse; that is the natural-exponent case, valid in any monoid.

step 4.1step 2.1step 1.9step 1.10givenL1L4L5L7

6.1

Claim 3 for a negative second exponent: let $y < 0$ , so $0 < - y$ . Applying claim 2 to the element $g^{x}$ gives $(g^{x})^{y} = ((g^{x})^{- y})^{- 1}$ , which by step 5.2 equals $(g^{x (- y)})^{- 1} = (g^{- (x y)})^{- 1} = ((g^{x y})^{- 1})^{- 1} = g^{x y}$ , using claim 2 once more and then $(u^{- 1})^{- 1} = u$ . Together with step 5.2 this is claim 3.

step 2.3step 5.2L3L5L6

7.1

Claims 1 to 5 are established: claim 1 in step 4.1, claim 2 in step 2.3, claim 3 in step 6.1, claim 4 in step 5.1 and claim 5 in steps 3.1 and 4.2; the natural-exponent forms of claims 1, 3 and 5 are steps 2.1, 5.2 and 3.1, and use no inverses.

step 2.1step 3.1step 2.3step 4.1step 5.1step 5.2step 6.1step 4.2discharge-induction∎

Remarks

The commuting hypothesis in claim 5 is not a technicality. Without it the law fails, and the title of this item carries the hypothesis for that reason. The published Laws of integer exponents states the corresponding law without a hypothesis, and is correct because it is about a field, where multiplication is commutative by definition; nothing there transfers to a general group.
Where each law is really used. Claim 1 is what makes $x \mapsto g^{x}$ a homomorphism from $(Z, +)$ and hence what makes cyclic subgroups behave; claim 4 is why every cyclic group is abelian ( $⟨ g ⟩ = {g^{n} : n \in Z}$ , and every cyclic group is abelian); claim 2 is what lets every statement about negative exponents be reduced to a statement about natural ones, which is how the case analysis above is kept finite.
The proof splits an arbitrary integer as $ι (a) - ι (b)$ rather than by cases on its sign wherever possible. That is deliberate: the normal form of step 3.2 is proved once and then every integer identity is a computation with natural powers and inverses.

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (z-ai/glm-5.2)audited 2026-07-27Open item page →

Subgroup

Definition

Let $G$ be a group (Group and abelian group) with identity $e$ . A subset $H \subseteq G$ is a subgroup of $G$ , written $H \leq G$ , when

(S1) $e \in H$ ;
(S2) $H$ is closed under the operation: $x, y \in H$ implies $x y \in H$ (Binary operation on a set; associativity, commutativity, and a subset closed under the operation);
(S3) $H$ is closed under inverses: $x \in H$ implies $x^{- 1} \in H$ .

By (S2) the operation of $G$ restricts to a binary operation on $H$ ; it is associative there because it is associative on $G$ , the element $e$ of (S1) is a two-sided identity for it (Left identity, right identity, and two-sided identity for a binary operation), and (S3) supplies for each $x \in H$ a two-sided inverse lying in $H$ (Left inverse, right inverse, and invertible element of a monoid). So a subgroup, with the restricted operation, is itself a group, and its identity and its inverses are those of $G$ .

Every group $G$ has the two trivial subgroups ${e}$ and $G$ itself; a subgroup $H$ with $H \neq G$ is called proper.

Remarks

The definition is stated so that no comparison of structures is needed. A subgroup is a subset satisfying three closure conditions, and the group structure it carries is inherited rather than chosen. The converse reading, that a subset which happens to be a group under the restricted operation is a subgroup in the above sense, is a small theorem rather than a tautology, because a priori such a subset could carry a different identity; it is part of One-step subgroup test: a nonempty $H \subseteq G$ is a subgroup iff $g h^{- 1} \in H$ for all $g, h \in H$ ; the identity and the inverses of $H$ are then those of $G$ , and cancellation in $G$ is what rules that out.
Conditions (S1)–(S3) are not independent as stated: if $H$ is nonempty and satisfies (S2) and (S3) then it satisfies (S1). The economical single test is One-step subgroup test: a nonempty $H \subseteq G$ is a subgroup iff $g h^{- 1} \in H$ for all $g, h \in H$ ; the identity and the inverses of $H$ are then those of $G$ .
Intersections of subgroups are subgroups (The intersection of a nonempty family of subgroups of $G$ is a subgroup of $G$ ), which is what makes "the smallest subgroup containing a given subset" meaningful (The subgroup $⟨ S ⟩$ generated by a subset, the cyclic subgroup $⟨ g ⟩$ , and cyclic groups). Unions of subgroups are almost never subgroups.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-27Open item page →

One-step subgroup test: a nonempty $H \subseteq G$ is a subgroup iff $g h^{- 1} \in H$ for all $g, h \in H$ ; the identity and the inverses of $H$ are then those of $G$

Statement

Let $G$ be a group (Group and abelian group) with identity $e$ and let $H \subseteq G$ be nonempty. Then $H$ is a subgroup of $G$ (Subgroup) if and only if

$g h^{- 1} \in H for all g, h \in H .$

Moreover, if $H \subseteq G$ is nonempty, closed under the operation of $G$ , and is a group under that restricted operation with some identity element $f$ and some inverse $x^{*}$ for each $x \in H$ , then $f = e$ and $x^{*} = x^{- 1}$ for every $x \in H$ ; so $H$ is a subgroup in the sense of Subgroup, and "subgroup" and "subset that is a group under the restricted operation" agree.

Facts & Assumptions

Given: A group $G$ with identity $e$ , and a nonempty subset $H \subseteq G$ .

[L1]

A subgroup is a subset containing $e$ and closed under the operation and under inverses; it is then a group under the restricted operation, with identity $e$ and with the inverses of $G$ (Subgroup).

[L2]

The group laws in $G$ : associativity, the two-sided identity $e$ , and two-sided inverses (Group and abelian group).

[L3]

$(g^{- 1})^{- 1} = g$ (In a group $e^{- 1} = e$ , $(g^{- 1})^{- 1} = g$ and $(g h)^{- 1} = h^{- 1} g^{- 1}$ , the order of the last product being essential).

[L4]

Cancellation in $G$ : $g x = g y$ implies $x = y$ (Cancellation in a group: $g x = g y$ or $x g = y g$ forces $x = y$ ; equivalently left and right translation by $g$ are bijections of $G$ , so $g x = h$ and $x g = h$ each have exactly one solution).

[L5]

Uniqueness of inverses in a monoid, in the sharp form: if $x$ is invertible and $y x = e$ or $x y = e$ , then $y = x^{- 1}$ (In a monoid, a left inverse and a right inverse of the same element are equal; hence an invertible element has exactly one inverse, and it is two-sided).

Proof

technique · direct

1.1

Necessity. Suppose $H$ is a subgroup and let $g, h \in H$ . Then $h^{- 1} \in H$ by closure under inverses, and $g h^{- 1} \in H$ by closure under the operation.

1.2

Sufficiency, the identity. Suppose $g h^{- 1} \in H$ for all $g, h \in H$ . Since $H$ is nonempty, choose $x \in H$ ; taking $g = h = x$ gives $x x^{- 1} = e \in H$ .

givenL2choose

1.3

The second claim, the identity. Let $H$ be nonempty, closed under the operation, and a group under the restricted operation with identity $f \in H$ . Then $f f = f$ in $H$ , hence in $G$ ; also $f e = f$ in $G$ . Cancelling $f$ on the left in $f f = f e$ gives $f = e$ .

givenL2L4

2.1

Sufficiency, inverses. Let $h \in H$ . Taking $g = e$ , which lies in $H$ by step 1.2, gives $e h^{- 1} = h^{- 1} \in H$ .

step 1.2givenL2

2.2

The second claim, inverses. Let $x \in H$ with inverse $x^{*} \in H$ for the restricted operation, so $x^{*} x = f = e$ by step 1.3. Since $x$ is invertible in $G$ , uniqueness of inverses gives $x^{*} = x^{- 1}$ ; in particular $x^{- 1} \in H$ .

step 1.3L5

3.1

Sufficiency, products. Let $g, h \in H$ . By step 2.1, $h^{- 1} \in H$ , so applying the hypothesis to the pair $g$ and $h^{- 1}$ gives $g (h^{- 1})^{- 1} \in H$ , and $(h^{- 1})^{- 1} = h$ , so $g h \in H$ .

step 2.1givenL3

3.2

Hence such an $H$ contains $e$ by step 1.3, is closed under the operation by assumption, and is closed under inverses by step 2.2: it is a subgroup in the sense of Subgroup.

step 1.3step 2.2L1

4.1

Steps 1.2, 2.1 and 3.1 verify (S1), (S3) and (S2), so $H$ is a subgroup; with step 1.1 this proves the equivalence.

step 1.1step 1.2step 2.1step 3.1L1

5.1

The one-step test characterises subgroups among nonempty subsets, and a nonempty subset that is a group under the restricted operation is a subgroup with the same identity and the same inverses as $G$ .

step 4.1step 3.2∎

Remarks

Why the second claim is needed at all. Nothing in the phrase "is a group under the restricted operation" forces the identity of that group to be the identity of $G$ ; the hypothesis only says some element acts as an identity within $H$ . Cancellation in $G$ is what collapses the two, and it is available because $G$ is a group. In a monoid the corresponding statement is false: a subset closed under the operation can be a monoid whose identity is not the identity of the ambient monoid, as ${0}$ inside $(Z, \cdot, 1)$ shows, where $0$ is an idempotent acting as an identity on that subset.
Nonemptiness cannot be dropped from the one-step test, since the empty set satisfies the condition vacuously and is not a subgroup: it does not contain $e$ .
Closure under the operation alone is not enough, even for a nonempty subset: the nonnegative integers inside $(Z, +)$ are closed under addition and contain $0$ , but are not a subgroup, as recorded on the companion page.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-27Open item page →

The intersection of a nonempty family of subgroups of $G$ is a subgroup of $G$

Statement

Let $G$ be a group (Group and abelian group) and let $H$ be a nonempty set of subgroups of $G$ (Subgroup). Then the intersection

$K = ⋂_{H \in H} H = {x \in G : x \in H for every H \in H}$

is a subgroup of $G$ . In particular the intersection of two subgroups is a subgroup.

Facts & Assumptions

Given: A group $G$ with identity $e$ , a nonempty set $H$ of subgroups of $G$ , and $K$ the intersection of the members of $H$ .

[L1]

Each $H \in H$ contains $e$ , is closed under the operation, and is closed under inverses (Subgroup).

[L2]

One-step test: a nonempty subset $S \subseteq G$ with $g h^{- 1} \in S$ for all $g, h \in S$ is a subgroup (One-step subgroup test: a nonempty $H \subseteq G$ is a subgroup iff $g h^{- 1} \in H$ for all $g, h \in H$ ; the identity and the inverses of $H$ are then those of $G$ ).

Proof

technique · direct

1.1

$K \subseteq G$ , since every member of $H$ is a subset of $G$ and $H$ is nonempty.

givenL1

1.2

$e \in K$ , since $e \in H$ for every $H \in H$ ; in particular $K$ is nonempty.

1.3

Let $g, h \in K$ and let $H \in H$ be arbitrary. Then $g, h \in H$ , so $h^{- 1} \in H$ by closure under inverses and $g h^{- 1} \in H$ by closure under the operation.

L1given

2.1

Since $H$ was arbitrary in step 1.3, $g h^{- 1}$ lies in every member of $H$ , that is $g h^{- 1} \in K$ .

step 1.3

3.1

$K$ is a nonempty subset of $G$ satisfying the one-step test, hence a subgroup of $G$ .

step 1.1step 1.2step 2.1L2∎

Remarks

The hypothesis that $H$ is nonempty is load bearing. The intersection of the empty family of subsets of $G$ is not a subset of $G$ by any convention used here; the statement is made for a nonempty family so that step 1.1 is available.
This lemma is what makes The subgroup $⟨ S ⟩$ generated by a subset, the cyclic subgroup $⟨ g ⟩$ , and cyclic groups legitimate: the family of subgroups containing a given subset $S$ is nonempty, since $G$ itself belongs to it, so its intersection is a subgroup, and it is by construction the smallest subgroup containing $S$ .

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (z-ai/glm-5.2)audited 2026-07-27Open item page →

The subgroup $⟨ S ⟩$ generated by a subset, the cyclic subgroup $⟨ g ⟩$ , and cyclic groups

Definition

Let $G$ be a group (Group and abelian group) and $S \subseteq G$ a subset. The set of subgroups of $G$ containing $S$ is nonempty, since $G$ itself is such a subgroup, so its intersection is a subgroup of $G$ by The intersection of a nonempty family of subgroups of $G$ is a subgroup of $G$ . That intersection is the subgroup generated by $S$ ,

$⟨ S ⟩ : = ⋂ {H : H \leq G and S \subseteq H} .$

It contains $S$ , being an intersection of sets each containing $S$ , and it is contained in every subgroup of $G$ that contains $S$ ; so it is the smallest subgroup of $G$ containing $S$ , and these two properties determine it uniquely. The elements of $S$ are called generators.

For a single element $g \in G$ we write $⟨ g ⟩ : = ⟨ {g} ⟩$ and call it the cyclic subgroup generated by $g$ . A group $G$ is cyclic when $G = ⟨ g ⟩$ for some $g \in G$ .

By convention $⟨ \emptyset ⟩ = {e}$ : the trivial subgroup is the smallest subgroup containing the empty set, and this is a consequence of the definition, not a stipulation, since every subgroup contains $e$ (Subgroup).

Remarks

Two descriptions, one object. The definition above is "from outside": cut down from all subgroups containing $S$ . There is also a description "from inside", as the set of all finite products of generators and their inverses. For a single generator that inside description is $⟨ g ⟩ = {g^{n} : n \in Z}$ , proved in $⟨ g ⟩ = {g^{n} : n \in Z}$ , and every cyclic group is abelian. The general case belongs to a later page; nothing here needs it.
Cyclic does not mean finite. $(Z, +)$ is cyclic, generated by $1$ , and infinite; the generator may also fail to be unique, since $- 1$ generates it too.
Every cyclic group is abelian ( $⟨ g ⟩ = {g^{n} : n \in Z}$ , and every cyclic group is abelian), so a non-abelian group is never cyclic; the converse fails, and the Klein four-group on the companion page is an abelian group that is not cyclic.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-27Open item page →

$⟨ g ⟩ = {g^{n} : n \in Z}$ , and every cyclic group is abelian

Statement

Let $G$ be a group and $g \in G$ , with integer powers as in Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ . Then

$⟨ g ⟩ = {g^{n} : n \in Z},$

the cyclic subgroup generated by $g$ (The subgroup $⟨ S ⟩$ generated by a subset, the cyclic subgroup $⟨ g ⟩$ , and cyclic groups) being exactly the set of integer powers of $g$ . Consequently every cyclic group is abelian, and so is every cyclic subgroup of any group.

Facts & Assumptions

Given: A group $G$ with identity $e$ , an element $g \in G$ , and the set $P : = {g^{n} : n \in Z}$ of its integer powers (Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ ).

[L1]

$⟨ g ⟩$ is the smallest subgroup of $G$ containing $g$ : it is a subgroup, it contains $g$ , and it is contained in every subgroup containing $g$ (The subgroup $⟨ S ⟩$ generated by a subset, the cyclic subgroup $⟨ g ⟩$ , and cyclic groups).

[L2]

Exponent laws: $g^{m + n} = g^{m} g^{n}$ , $g^{- m} = (g^{m})^{- 1}$ , and $g^{m} g^{n} = g^{n} g^{m}$ , for all $m, n \in Z$ (Exponent laws in a group: $g^{m + n} = g^{m} g^{n}$ and $(g^{m})^{n} = g^{m n}$ for all $m, n \in Z$ , and $(g h)^{n} = g^{n} h^{n}$ when $g$ and $h$ commute).

[L3]

$g^{0} = e$ , $g^{1} = g$ , and $g^{σ (k)} = g^{k} g$ for $k \in N$ ; a natural number $k$ in an exponent means the integer $ι (k)$ (Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ , The naturals embed in the integers).

[L4]

One-step test: a nonempty $S \subseteq G$ with $x y^{- 1} \in S$ for all $x, y \in S$ is a subgroup (One-step subgroup test: a nonempty $H \subseteq G$ is a subgroup iff $g h^{- 1} \in H$ for all $g, h \in H$ ; the identity and the inverses of $H$ are then those of $G$ , Subgroup).

[L5]

$Z$ is a commutative ring, so $m + (- n)$ is again an integer and addition is commutative (The integers form a commutative ring, The integers as equivalence classes of pairs of naturals); its order is total, and every $x \geq 0$ is $ι (k)$ for a unique natural $k$ while every $x < 0$ has $- x = ι (k)$ for a unique natural $k$ (The integers form a totally ordered ring, Order on the integers, The naturals embed in the integers).

[L6]

Induction on $N$ (The principle of mathematical induction).

Proof

technique · direct

1.1

$P$ is nonempty, since $g^{0} = e \in P$ , and $P \subseteq G$ by construction.

L3given

1.2

For $x = g^{m}$ and $y = g^{n}$ in $P$ : $x y^{- 1} = g^{m} (g^{n})^{- 1} = g^{m} g^{- n} = g^{m + (- n)} \in P$ , since $m + (- n)$ is an integer.

L2L5

1.3

$g = g^{1} \in P$ .

1.4

Let $H$ be any subgroup of $G$ with $g \in H$ . Then $g^{k} \in H$ for every natural $k$ : the set of such $k$ contains $0$ , because $g^{0} = e \in H$ , and it is closed under $σ$ , because $g^{σ (k)} = g^{k} g$ is a product of two elements of $H$ ; induction finishes it.

L3L4L6given

2.1

By steps 1.1 and 1.2 and the one-step test, $P$ is a subgroup of $G$ , and by step 1.3 it contains $g$ ; hence $⟨ g ⟩ \subseteq P$ , since $⟨ g ⟩$ is contained in every subgroup containing $g$ .

step 1.1step 1.2step 1.3L1L4

2.2

Let $H$ be any subgroup of $G$ with $g \in H$ , and let $x \in Z$ . If $x \geq 0$ then $x = ι (k)$ and $g^{x} = g^{k} \in H$ by step 1.4. If $x < 0$ then $- x = ι (k)$ , so $g^{x} = (g^{k})^{- 1}$ , which lies in $H$ because $g^{k} \in H$ by step 1.4 and $H$ is closed under inverses. So $P \subseteq H$ .

step 1.4L3L4L5

3.1

Taking $H = ⟨ g ⟩$ in step 2.2, which is legitimate because $⟨ g ⟩$ is a subgroup containing $g$ , gives $P \subseteq ⟨ g ⟩$ ; with step 2.1 this proves $⟨ g ⟩ = P$ .

step 2.1step 2.2L1

4.1

Any two elements of $P$ commute: $g^{m} g^{n} = g^{n} g^{m}$ for all integers $m, n$ . Hence $⟨ g ⟩$ is abelian, by step 3.1.

step 3.1L2

5.1

If $G$ is cyclic, say $G = ⟨ g ⟩$ , then $G$ is abelian by step 4.1; and every cyclic subgroup of any group is abelian for the same reason.

step 3.1step 4.1L1∎

Remarks

The two inclusions are proved by different means, and both are needed: one shows the set of powers is a subgroup containing $g$ , the other shows every subgroup containing $g$ swallows all the powers. Only together do they identify the smallest one.
Step 1.4 is where induction does the work, and it is stated for natural exponents only; negative exponents are then handled in step 2.2 by closure under inverses, using $g^{x} = (g^{k})^{- 1}$ from the definition of integer powers rather than a second induction.
Nothing here says $⟨ g ⟩$ is finite, or that distinct exponents give distinct powers. Both questions are settled by If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ , which shows the powers repeat with period $ord (g)$ when that is finite and are pairwise distinct when it is not.

TheoremStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-27Open item page →

Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$

Statement

Let $a, b \in Z$ (The integers as equivalence classes of pairs of naturals) with $b > 0$ . Then there exist integers $q$ and $r$ with

$a = q b + r, 0 \leq r < b,$

and the pair $(q, r)$ with these two properties is unique.

We say $b$ divides $a$ , written $b ∣ a$ , when $a = q b$ for some $q \in Z$ ; by the above, for $b > 0$ this holds exactly when the remainder $r$ is $0$ .

Facts & Assumptions

Given: Integers $a$ and $b$ with $b > 0$ , and the embedding $ι : N \to Z$ , $ι (k) = [(k, 0)]$ , of The naturals embed in the integers.

[L1]

$Z$ is a commutative ring: addition and multiplication are associative and commutative, $x + 0 = x$ , $x \cdot 1 = x$ , multiplication distributes over addition, and every $x$ has an additive inverse $- x$ ; we write $u - v$ for $u + (- v)$ (The integers form a commutative ring, Arithmetic on the integers).

[L2]

The order on $Z$ is total, antisymmetric and transitive, is compatible with addition ( $x \leq y$ implies $x + z \leq y + z$ ), and positives are closed under multiplication ( $0 < x$ and $0 < y$ imply $0 < x y$ ) (The integers form a totally ordered ring, Order on the integers).

[L3]

[L4]

Every nonempty subset of $N$ has a least element (The well-ordering principle).

[L5]

On $N$ : every $k \neq 0$ is a successor $σ (j)$ (Every nonzero natural number is a successor); $σ (j) = j + 1 = 1 + j$ (The natural numbers $N$ (von Neumann), Addition is commutative); $m \leq n$ means $m + t = n$ for some $t \in N$ (Order on the natural numbers); and exactly one of $m < n$ , $m = n$ , $n < m$ holds (Trichotomy of the order on $N$ ).

Proof

technique · direct

1.1

Sums and products of nonnegative integers are nonnegative: if $0 \leq u$ and $0 \leq v$ then $u \leq u + v$ by compatibility with addition, so $0 \leq u + v$ by transitivity; and if either factor is $0$ then $u v = 0$ , while if both are positive then $0 < u v$ .

L1L2

1.2

Discreteness: if $0 < x$ in $Z$ then $1 \leq x$ . Indeed $x$ is nonnegative, so $x = ι (k)$ for some $k \in N$ , and $k \neq 0$ because $ι (0) = 0 \neq x$ ; hence $k = σ (j) = 1 + j$ for some $j$ , so $1 \leq k$ in $N$ , and applying $ι$ , which preserves the order, gives $1 = ι (1) \leq ι (k) = x$ .

L3L5

1.3

$ι$ reflects the order: if $ι (m) < ι (n)$ then $m < n$ . For otherwise trichotomy on $N$ gives $n \leq m$ , whence $ι (n) \leq ι (m)$ because $ι$ preserves the order, and this together with $ι (m) < ι (n)$ contradicts antisymmetry.

L2L3L5

1.4

Write $a = ι (a_{1}) - ι (a_{2})$ with $a_{1}, a_{2} \in N$ , which is possible because $a = [(a_{1}, a_{2})]$ for some naturals and $[(a_{1}, a_{2})] = [(a_{1}, 0)] + [(0, a_{2})] = ι (a_{1}) - ι (a_{2})$ .

L1L3given

1.5

Uniqueness. Suppose $a = q_{1} b + r_{1} = q_{2} b + r_{2}$ with $0 \leq r_{i} < b$ for $i = 1, 2$ , and set $d : = q_{1} - q_{2}$ . Ring arithmetic gives $d b = r_{2} - r_{1}$ .

L1given

2.1

From $0 < b$ and step 1.2, $1 \leq b$ , so $0 \leq b - 1$ by compatibility with addition.

step 1.2L1L2

2.2

Put $q_{0} : = - ι (a_{2})$ . Then $a - q_{0} b = a + ι (a_{2}) b = (ι (a_{1}) - ι (a_{2})) + ι (a_{2}) b = ι (a_{1}) + ι (a_{2}) (b - 1)$ , by ring arithmetic.

step 1.4L1

2.3

If $0 < d$ then $1 \leq d$ by step 1.2, so $0 \leq d - 1$ and hence $0 \leq (d - 1) b$ by step 1.1, that is $b \leq d b$ ; but $r_{1} \geq 0$ gives $r_{2} - r_{1} \leq r_{2} < b$ , so $b \leq d b = r_{2} - r_{1} < b$ , contradicting antisymmetry.

step 1.1step 1.2step 1.5L1L2

2.4

If $d < 0$ then $0 < - d$ , and the same computation with the roles of the two pairs interchanged, using $(- d) b = r_{1} - r_{2}$ , gives $b \leq r_{1} - r_{2} < b$ , again a contradiction.

step 1.1step 1.2step 1.5L1L2

3.1

The integer $a - q_{0} b$ is nonnegative: $ι (a_{1}) \geq 0$ and $ι (a_{2}) \geq 0$ because both lie in the image of $ι$ , $b - 1 \geq 0$ by step 2.1, and sums and products of nonnegative integers are nonnegative.

step 1.1step 2.1step 2.2L3

3.2

Hence $d = 0$ by totality, so $q_{1} = q_{2}$ , and then $r_{1} = a - q_{1} b = a - q_{2} b = r_{2}$ .

step 1.5step 2.3step 2.4L1L2

4.1

Hence the set $T : = {k \in N : ι (k) = a - q b for some q \in Z}$ is nonempty, since $a - q_{0} b$ is a nonnegative integer and therefore equals $ι (k)$ for some $k \in N$ .

step 3.1L3

5.1

By well-ordering let $r_{0}$ be the least element of $T$ , choose $q \in Z$ with $ι (r_{0}) = a - q b$ , and set $r : = ι (r_{0})$ . Then $a = q b + r$ and $0 \leq r$ .

step 4.1L1L3L4choose

6.1

Suppose $b \leq r$ . Then $0 \leq r - b$ by compatibility with addition, and $r - b = (a - q b) - b = a - (q + 1) b$ by ring arithmetic, so $r - b = ι (k^{'})$ for some $k^{'} \in N$ with $k^{'} \in T$ . Also $- b < 0$ , since $0 < b$ , so $r - b < r$ , that is $ι (k^{'}) < ι (r_{0})$ , whence $k^{'} < r_{0}$ by step 1.3. This contradicts the minimality of $r_{0}$ .

step 1.3step 5.1L1L2L3given

7.1

Therefore $b \leq r$ fails, and by totality of the order $r < b$ ; with step 5.1 this establishes existence of a pair $(q, r)$ with $a = q b + r$ and $0 \leq r < b$ .

step 5.1step 6.1L2

8.1

Existence is step 7.1 and uniqueness is step 3.2, so for every $a \in Z$ and every $b > 0$ there is exactly one pair $(q, r)$ of integers with $a = q b + r$ and $0 \leq r < b$ .

step 7.1step 3.2∎

Remarks

Stated for a positive divisor only. Nothing here needs an absolute value on $Z$ , and none is available at this point in the reading order. The version for $b \neq 0$ , with $0 \leq r < ∣ b ∣$ , follows once absolute values are in hand and is not needed by anything on this page.
Why it is proved here. The characterisation of the order of an element, $g^{k} = e$ exactly when $ord (g)$ divides $k$ , and the count $∣ ⟨ g ⟩ ∣ = ord (g)$ , are both unprovable without division with remainder (If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ). No earlier page in the library supplies it.
This is not a theory of divisibility. The relation $b ∣ a$ is defined here for use on this page and its companion; greatest common divisors, primes and unique factorisation are developed on a later page, and that page must record that its general divisibility in a ring restricts on $Z$ to the relation defined here, rather than introduce a second notion silently.
A published claim this theorem falsified. A published example on the metric spaces companion page used to record in its Remarks that this library had no divisibility theory at all in which to state or prove Euclid's lemma. That was true when it was written; the present item, which is earlier in the reading order, made it false, and the sentence has since been narrowed to say that the example itself neither establishes nor assumes that lemma. Nothing here depends on that example, and nothing here supplies Euclid's lemma either: what is proved above is division with remainder, and no more.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-27Open item page →

In a finite group, every element $g$ satisfies $g^{n} = e$ for some natural $n \geq 1$

Statement

Let $G$ be a group (Group and abelian group) whose underlying set is finite (Finite, countably infinite, countable, uncountable), and let $g \in G$ . Then there is a natural number $n \geq 1$ with $g^{n} = e$ , the power being the natural power of Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ .

Facts & Assumptions

Given: A group $G$ with identity $e$ whose underlying set is finite, and an element $g \in G$ ; natural powers $g^{k}$ with $g^{0} = e$ and $g^{σ (k)} = g^{k} g$ (Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ ).

[L1]

$G$ finite means $G \approx m$ for some $m \in N$ , that is, there is a bijection $β : G \to m$ (Finite, countably infinite, countable, uncountable, Equinumerous sets, $A \approx B$ and $A ⪯ B$ ).

[L2]

Claim 1 of the pigeonhole principle: for every $m \in N$ there is no injection $σ (m) \to m$ (The pigeonhole principle on $N$ ).

[L3]

On $N$ the order is membership, so the elements of the natural number $σ (m)$ are exactly the natural numbers $k < σ (m)$ , and the elements of $m$ are exactly the natural numbers $k < m$ (On $N$ the order is membership: $m < n ⟺ m \in n$ , The natural numbers $N$ (von Neumann)).

[L4]

A map $f$ is injective when $f (x) = f (y)$ forces $x = y$ ; a bijection is injective (Injection, surjection, bijection).

[L5]

$g^{i + k} = g^{i} g^{k}$ for natural $i, k$ , in any monoid (Exponent laws in a group: $g^{m + n} = g^{m} g^{n}$ and $(g^{m})^{n} = g^{m n}$ for all $m, n \in Z$ , and $(g h)^{n} = g^{n} h^{n}$ when $g$ and $h$ commute).

[L6]

Cancellation in a group: $g x = g y$ implies $x = y$ (Cancellation in a group: $g x = g y$ or $x g = y g$ forces $x = y$ ; equivalently left and right translation by $g$ are bijections of $G$ , so $g x = h$ and $x g = h$ each have exactly one solution).

[L7]

On $N$ : exactly one of $i < j$ , $i = j$ , $j < i$ holds (Trichotomy of the order on $N$ ); $i \leq j$ means $i + k = j$ for some $k$ (Order on the natural numbers); every $k \neq 0$ is a successor $σ (t) = 1 + t$ (Every nonzero natural number is a successor, Addition is commutative), so $k \neq 0$ implies $1 \leq k$ .

Proof

technique · direct

1.1

Fix a bijection $β : G \to m$ with $m \in N$ , available because $G$ is finite.

L1choose

2.1

Define $F : σ (m) \to m$ by $F (k) : = β (g^{k})$ . This is a function: every element $k$ of $σ (m)$ is a natural number, so the natural power $g^{k}$ is defined and lies in $G$ , and $β$ sends it into $m$ .

step 1.1L3given

3.1

$F$ is not injective, since there is no injection $σ (m) \to m$ . Hence there are $i, j \in σ (m)$ with $i \neq j$ and $F (i) = F (j)$ .

step 2.1L2choose

4.1

From $β (g^{i}) = β (g^{j})$ and injectivity of $β$ we get $g^{i} = g^{j}$ .

step 1.1step 3.1L4

4.2

By trichotomy and $i \neq j$ , one of $i < j$ and $j < i$ holds; interchanging the names if necessary, assume $i < j$ . Then $i + k = j$ for some $k \in N$ , and $k \neq 0$ , since $k = 0$ would give $i = j$ .

step 3.1L7

5.1

Hence $g^{i} g^{k} = g^{i + k} = g^{j} = g^{i} = g^{i} e$ , and cancelling $g^{i}$ on the left gives $g^{k} = e$ .

step 4.1step 4.2L5L6given

6.1

Finally $k \neq 0$ gives $1 \leq k$ , so $n : = k$ is a natural number with $n \geq 1$ and $g^{n} = e$ .

step 4.2step 5.1L7∎

Remarks

The route avoids "a subset of a finite set is finite". That statement is not available at this point in the reading order, so the argument does not build an injection $N \to G$ and contradict finiteness. It uses claim 1 of The pigeonhole principle on $N$ directly on the map $k \mapsto β (g^{k})$ from $σ (m)$ to $m$ : the $m + 1$ exponents $0, 1, \dots, m$ cannot receive $m + 1$ distinct values in a set of $m$ elements.
The conclusion is one-sided on purpose. It asserts that some positive power is the identity, not which one. Picking the least such power is what defines $ord (g)$ (The order $∣ G ∣$ of a finite group and the order $ord (g)$ of an element, with $ord (g) = \infty$ when no positive power of $g$ is the identity), and that step needs the well-ordering principle, not this lemma.
The hypothesis of finiteness cannot be dropped: in $(Z, +)$ the element $1$ satisfies $n \cdot 1 = n \neq 0$ for every $n \geq 1$ .

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (z-ai/glm-5.2)audited 2026-07-27Open item page →

The order $∣ G ∣$ of a finite group and the order $ord (g)$ of an element, with $ord (g) = \infty$ when no positive power of $g$ is the identity

Definition

The order of a finite group. Let $G$ be a group (Group and abelian group) whose underlying set is finite (Finite, countably infinite, countable, uncountable), so that $G \approx n$ for some $n \in N$ (Equinumerous sets, $A \approx B$ and $A ⪯ B$ ). That natural number is unique: if $G \approx n$ and $G \approx n^{'}$ then $n \approx n^{'}$ , since $\approx$ is symmetric and transitive, and then $n = n^{'}$ by claim 3 of The pigeonhole principle on $N$ . The order of $G$ is that unique natural number, written $∣ G ∣$ . A group is infinite when its underlying set is not finite, and $∣ G ∣$ is then not defined.

The order of an element. Let $G$ be any group and $g \in G$ , with natural powers as in Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ . Put

$S_{g} : = {k \in N : k \geq 1 and g^{k} = e} \subseteq N .$

If $S_{g} \neq \emptyset$ , the order of $g$ is its least element,

$ord (g) : = \min S_{g} \in N,$

which exists by the well-ordering principle (The well-ordering principle): every nonempty subset of $N$ has a least element, and that element is unique, being $\leq$ every element of $S_{g}$ and a member of it. We then say $g$ has finite order.
If $S_{g} = \emptyset$ we say $g$ has infinite order and write $ord (g) = \infty$ , where $\infty$ is a symbol reserved for this case and is not a natural number. No arithmetic is performed with it here.

By construction $ord (g) \geq 1$ whenever it is finite, and $ord (g) = 1$ exactly when $g = e$ , since $g^{1} = g$ .

Every element of a finite group has finite order. If $G$ is finite then $S_{g} \neq \emptyset$ for every $g \in G$ , by In a finite group, every element $g$ satisfies $g^{n} = e$ for some natural $n \geq 1$ , so $ord (g)$ is a natural number.

Remarks

Two well-definedness obligations, both discharged above and neither parenthetical. For $∣ G ∣$ it is that a finite set is equinumerous with exactly one natural number, which is claim 3 of The pigeonhole principle on $N$ . For $ord (g)$ it is that the set $S_{g}$ has a least element when it is nonempty, which is The well-ordering principle, and that it is nonempty at all in the finite case, which is In a finite group, every element $g$ satisfies $g^{n} = e$ for some natural $n \geq 1$ . Neither quantity is definable before those three items.
$∣ G ∣$ and $ord (g)$ are the same kind of thing, and that is not an accident. If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ proves $∣ ⟨ g ⟩ ∣ = ord (g)$ : the order of an element is the order of the group it generates. The shared word and the shared notation are justified by that identity, not by convention.
$\infty$ is not a value in $N$ , so a statement such as " $ord (g) ∣ k$ " is asserted only when the order is finite; the infinite case is always stated separately. The order on $N$ used above is the additive one of Order on the natural numbers, and $N$ contains $0$ (The natural numbers $N$ (von Neumann)), which is why $S_{g}$ carries the condition $k \geq 1$ : $g^{0} = e$ holds for every $g$ and says nothing.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-27Open item page →

If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$

Statement

Let $G$ be a group, $g \in G$ , and let orders be as in The order $∣ G ∣$ of a finite group and the order $ord (g)$ of an element, with $ord (g) = \infty$ when no positive power of $g$ is the identity. Throughout, a natural number written where an integer is expected means its image under the embedding $ι : N \to Z$ of The naturals embed in the integers.

Finite order. Suppose $ord (g) = n$ with $n \in N$ , $n \geq 1$ . Then:

for every $k \in Z$ , $g^{k} = e$ if and only if $k = q n$ for some $q \in Z$ , that is, if and only if $n ∣ k$ (Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ );
the powers $g^{0}, g^{1}, \dots, g^{n - 1}$ are pairwise distinct: if $i, j \in N$ with $i < n$ , $j < n$ and $g^{i} = g^{j}$ , then $i = j$ ;
$⟨ g ⟩ = {g^{s} : s \in N, s < n}$ and $⟨ g ⟩ \approx n$ ; so $⟨ g ⟩$ is finite with $∣ ⟨ g ⟩ ∣ = n = ord (g)$ .

Infinite order. If $ord (g) = \infty$ then for $j, k \in Z$ , $g^{j} = g^{k}$ implies $j = k$ ; so the integer powers of $g$ are pairwise distinct and $⟨ g ⟩$ is not finite.

Facts & Assumptions

Given: A group $G$ with identity $e$ and an element $g \in G$ ; $S_{g} = {k \in N : k \geq 1, g^{k} = e}$ , and $ord (g) = \min S_{g}$ when $S_{g} \neq \emptyset$ , $ord (g) = \infty$ otherwise (The order $∣ G ∣$ of a finite group and the order $ord (g)$ of an element, with $ord (g) = \infty$ when no positive power of $g$ is the identity).

[L1]

Exponent laws: $g^{x + y} = g^{x} g^{y}$ , $g^{- x} = (g^{x})^{- 1}$ and $(g^{x})^{y} = g^{x y}$ for all $x, y \in Z$ ; the first also holds for natural exponents in any monoid (Exponent laws in a group: $g^{m + n} = g^{m} g^{n}$ and $(g^{m})^{n} = g^{m n}$ for all $m, n \in Z$ , and $(g h)^{n} = g^{n} h^{n}$ when $g$ and $h$ commute, Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ ).

[L2]

$⟨ g ⟩ = {g^{x} : x \in Z}$ ( $⟨ g ⟩ = {g^{n} : n \in Z}$ , and every cyclic group is abelian).

[L3]

Division with remainder: for $k \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $k = q b + r$ and $0 \leq r < b$ (Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ ).

[L4]

$ι$ is injective, preserves addition, multiplication and order, and its image is exactly the nonnegative integers; $ι (0) = 0$ , $ι (1) = 1$ (The naturals embed in the integers). The order on $Z$ is total and antisymmetric and $Z$ is a commutative ring (The integers form a totally ordered ring, The integers form a commutative ring, Order on the integers, The integers as equivalence classes of pairs of naturals).

[L5]

Cancellation in a group (Cancellation in a group: $g x = g y$ or $x g = y g$ forces $x = y$ ; equivalently left and right translation by $g$ are bijections of $G$ , so $g x = h$ and $x g = h$ each have exactly one solution); $e^{- 1} = e$ and $(u^{- 1})^{- 1} = u$ (In a group $e^{- 1} = e$ , $(g^{- 1})^{- 1} = g$ and $(g h)^{- 1} = h^{- 1} g^{- 1}$ , the order of the last product being essential).

[L6]

Induction on $N$ (The principle of mathematical induction).

[L7]

On $N$ : the order is membership, so $n = {s \in N : s < n}$ (On $N$ the order is membership: $m < n ⟺ m \in n$ ); $i \leq j$ means $i + t = j$ for some $t$ (Order on the natural numbers); exactly one of $i < j$ , $i = j$ , $j < i$ holds (Trichotomy of the order on $N$ ).

[L8]

Finiteness and counting: $A$ is finite when $A \approx m$ for some $m \in N$ , and that $m$ is unique (Finite, countably infinite, countable, uncountable, Equinumerous sets, $A \approx B$ and $A ⪯ B$ , The pigeonhole principle on $N$ ); a bijection is an injective and surjective map (Injection, surjection, bijection).

Proof

technique · direct

1.1

$e^{x} = e$ for every $x \in Z$ . For natural exponents the set of $t$ with $e^{t} = e$ contains $0$ , since $e^{0} = e$ , and is closed under $σ$ , since $e^{σ (t)} = e^{t} e = e e = e$ ; induction gives it for all naturals. For $x < 0$ write $- x = ι (k)$ ; then $e^{x} = (e^{k})^{- 1} = e^{- 1} = e$ .

givenL1L4L5L6

1.2

Assume $ord (g) = n$ with $n \geq 1$ . Then $n \in S_{g}$ , so $g^{n} = e$ , and no natural $s$ with $1 \leq s < n$ satisfies $g^{s} = e$ , since $n$ is the least element of $S_{g}$ . Also $ι (n) > 0$ , because $n \geq 1$ and $ι$ preserves the order.

givenL4

1.3

Infinite order. Assume $S_{g} = \emptyset$ and suppose $g^{j} = g^{k}$ with $j, k \in Z$ and $j \neq k$ . Put $x : = j - k$ , so $x \neq 0$ and $g^{x} = g^{j} g^{- k} = g^{j} (g^{k})^{- 1} = e$ . Also $g^{- x} = (g^{x})^{- 1} = e^{- 1} = e$ . By totality one of $x$ and $- x$ is positive; call it $y$ , so $g^{y} = e$ and $y = ι (s)$ with $s \in N$ and $s \neq 0$ , hence $s \geq 1$ . Then $s \in S_{g}$ , contradicting $S_{g} = \emptyset$ .

givenL1L4L5

2.1

The "if" half of claim 1: if $k = q ι (n)$ for some $q \in Z$ , then $g^{k} = g^{ι (n) q} = (g^{ι (n)})^{q} = (g^{n})^{q} = e^{q} = e$ .

step 1.1step 1.2L1L4

2.2

The "only if" half. Suppose $g^{k} = e$ . Divide: $k = q ι (n) + r$ with $0 \leq r < ι (n)$ , legitimate since $ι (n) > 0$ . Then $e = g^{k} = g^{q ι (n)} g^{r} = (g^{n})^{q} g^{r} = e^{q} g^{r} = g^{r}$ . Since $0 \leq r$ , we have $r = ι (s)$ for a unique $s \in N$ , and $ι (s) < ι (n)$ forces $s < n$ , because otherwise $n \leq s$ and $ι$ would give $ι (n) \leq ι (s)$ , contradicting antisymmetry. So $g^{s} = e$ with $s < n$ .

step 1.1step 1.2L1L3L4L7

2.3

Claim 2. Let $i, j \in N$ with $i < n$ , $j < n$ and $g^{i} = g^{j}$ . By trichotomy we may assume $i \leq j$ , interchanging the names if necessary, and then $i + t = j$ for some $t \in N$ . Now $g^{i} g^{t} = g^{i + t} = g^{j} = g^{i} = g^{i} e$ , so $g^{t} = e$ by cancellation. Moreover $t \leq j$ , since $t + i = j$ , and $j < n$ , so $t < n$ . If $t \geq 1$ then $t \in S_{g}$ with $t < n$ , impossible; so $t = 0$ and $i = j$ .

step 1.2L1L5L7

2.4

Therefore in the infinite-order case $g^{j} = g^{k}$ forces $j = k$ . Moreover $⟨ g ⟩$ is then not finite: a bijection $ψ : ⟨ g ⟩ \to m$ with $m \in N$ would make $k \mapsto ψ (g^{ι (k)})$ a map $σ (m) \to m$ , and that map is injective, since $ι$ is injective, distinct integer exponents give distinct powers by step 1.3, and $ψ$ is injective; but claim 1 of the pigeonhole principle forbids an injection $σ (m) \to m$ .

step 1.3L2L4L8

3.1

In step 2.2 the case $s \geq 1$ is impossible, since it would put $s$ in $S_{g}$ below its least element; hence $s = 0$ , so $r = 0$ and $k = q ι (n)$ . With step 2.1 this is claim 1.

step 1.2step 2.1step 2.2L4

3.2

Every integer power of $g$ is one of $g^{0}, \dots, g^{n - 1}$ : given $x \in Z$ , divide $x = q ι (n) + r$ with $0 \leq r < ι (n)$ , write $r = ι (s)$ with $s \in N$ and $s < n$ as in step 2.2, and compute $g^{x} = (g^{n})^{q} g^{r} = e^{q} g^{s} = g^{s}$ .

step 1.1step 1.2step 2.2L1L3L4

4.1

Claim 3. By [L2] and step 3.2, $⟨ g ⟩ = {g^{s} : s \in N, s < n}$ . The map $φ : n \to ⟨ g ⟩$ with $φ (s) = g^{s}$ is well defined, the elements of the natural number $n$ being exactly the naturals $s < n$ ; it is surjective by the displayed description and injective by step 2.3. So $φ$ is a bijection, $⟨ g ⟩ \approx n$ , and $⟨ g ⟩$ is finite with $∣ ⟨ g ⟩ ∣ = n = ord (g)$ , the value $∣ ⟨ g ⟩ ∣$ being the unique natural equinumerous with $⟨ g ⟩$ .

step 2.3step 3.2L2L7L8

5.1

Claims 1, 2 and 3 are steps 3.1, 2.3 and 4.1, and the infinite-order statement is steps 1.3 and 2.4.

step 3.1step 2.3step 4.1step 1.3step 2.4∎

Remarks

The division algorithm is exactly what is needed and nothing more. Claim 1 reduces an arbitrary integer exponent to a remainder in ${0, \dots, n - 1}$ ; that reduction is the only place where arithmetic in $Z$ beyond the ring laws enters, and it is why Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ is proved on this page.
The count in claim 3 starts at exponent $0$ . The $n$ distinct powers are $g^{0} = e, g^{1}, \dots, g^{n - 1}$ ; there are $n$ of them because $n$ , as a von Neumann natural, is the set ${0, 1, \dots, n - 1}$ of exponents used (On $N$ the order is membership: $m < n ⟺ m \in n$ ). Reading the list as starting at $g^{1}$ would give a count off by one.
The identity $∣ ⟨ g ⟩ ∣ = ord (g)$ is what makes the order of an element a statement about a subgroup, and is the step on which the later result that the order of an element divides the order of the group rests.

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (z-ai/glm-5.2)audited 2026-07-27Open item page →

Monoid homomorphism and group homomorphism

Definition

Let $(M, \cdot, e)$ and $(M^{'}, \cdot^{'}, e^{'})$ be monoids (Semigroup and monoid). A monoid homomorphism from $M$ to $M^{'}$ is a function $f : M \to M^{'}$ such that

(H1) $f (x \cdot y) = f (x) \cdot^{'} f (y)$ for all $x, y \in M$ ;
(H2) $f (e) = e^{'}$ .

Let $G$ and $G^{'}$ be groups (Group and abelian group). A group homomorphism from $G$ to $G^{'}$ is a function $f : G \to G^{'}$ satisfying (H1) alone:

$f (x y) = f (x) f (y) for all x, y \in G .$

Condition (H2) is not imposed for groups because it follows: a group homomorphism automatically satisfies $f (e) = e^{'}$ and $f (x^{- 1}) = f (x)^{- 1}$ (A group homomorphism automatically satisfies $f (e) = e^{'}$ and $f (g^{- 1}) = f (g)^{- 1}$ , and $f (g^{n}) = f (g)^{n}$ for every $n \in Z$ ; for monoid homomorphisms preservation of the identity must be assumed). For monoids it does not follow and must be assumed, which is why the two definitions differ.

A homomorphism from a structure to itself is an endomorphism. The identity map of $M$ is a monoid homomorphism, and a composite of monoid homomorphisms is one, since $(g \circ f) (x y) = g (f (x) f (y)) = g (f (x)) g (f (y))$ and $(g \circ f) (e) = g (e^{'}) = e^{''}$ ; the same computation, without the second clause, shows a composite of group homomorphisms is a group homomorphism.

Remarks

(H1) is a statement about two different operations. On the left the product is formed in $M$ , on the right in $M^{'}$ ; the notation suppresses that and the reader must supply it. The definition says exactly that $f$ turns products into products, and nothing else.
The asymmetry between the two definitions is real, not stylistic. The map $Z \to Z$ sending every integer to $0$ satisfies (H1) for the multiplicative monoid of $Z$ , since $0 = 0 \cdot 0$ , and it sends the identity $1$ to $0 \neq 1$ , so it is not a monoid homomorphism. In a group the same phenomenon is impossible, and cancellation is the reason (A group homomorphism automatically satisfies $f (e) = e^{'}$ and $f (g^{- 1}) = f (g)^{- 1}$ , and $f (g^{n}) = f (g)^{n}$ for every $n \in Z$ ; for monoid homomorphisms preservation of the identity must be assumed).
Only the definition is given here. Kernels, images, isomorphisms and the isomorphism theorems belong to a later page; nothing on this page or its companion uses them.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passverified 2026-08-02 (claude-opus-5)Open item page →

A group homomorphism automatically satisfies $f (e) = e^{'}$ and $f (g^{- 1}) = f (g)^{- 1}$ , and $f (g^{n}) = f (g)^{n}$ for every $n \in Z$ ; for monoid homomorphisms preservation of the identity must be assumed

Statement

Let $G$ and $G^{'}$ be groups with identities $e$ and $e^{'}$ , and let $f : G \to G^{'}$ be a group homomorphism (Monoid homomorphism and group homomorphism), so $f (x y) = f (x) f (y)$ for all $x, y \in G$ . Then:

$f (e) = e^{'}$ ;
$f (g^{- 1}) = f (g)^{- 1}$ for every $g \in G$ ;
$f (g^{n}) = f (g)^{n}$ for every $g \in G$ and every $n \in Z$ , powers being those of Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ .

For monoid homomorphisms the analogue of claim 1 is false, so preservation of the identity has to be part of the definition: the map $u : Z \to Z$ with $u (x) = 0$ for every $x$ satisfies $u (x y) = u (x) u (y)$ for the multiplicative monoid $(Z, \cdot, 1)$ , yet $u (1) = 0 \neq 1$ .

Facts & Assumptions

Given: Groups $G$ , $G^{'}$ with identities $e$ , $e^{'}$ , and a function $f : G \to G^{'}$ with $f (x y) = f (x) f (y)$ for all $x, y \in G$ (Monoid homomorphism and group homomorphism).

[A1]

$f (x y) = f (x) f (y)$ for all $x, y \in G$ .

[L1]

The group laws in $G$ and in $G^{'}$ (Group and abelian group, Semigroup and monoid).

[L2]

Cancellation in $G^{'}$ : $a b = a c$ implies $b = c$ , and $b a = c a$ implies $b = c$ (Cancellation in a group: $g x = g y$ or $x g = y g$ forces $x = y$ ; equivalently left and right translation by $g$ are bijections of $G$ , so $g x = h$ and $x g = h$ each have exactly one solution).

[L3]

Uniqueness of inverses in the sharp form: if $x$ is invertible and $y x = e^{'}$ or $x y = e^{'}$ , then $y = x^{- 1}$ (In a monoid, a left inverse and a right inverse of the same element are equal; hence an invertible element has exactly one inverse, and it is two-sided); and $(u^{- 1})^{- 1} = u$ (In a group $e^{- 1} = e$ , $(g^{- 1})^{- 1} = g$ and $(g h)^{- 1} = h^{- 1} g^{- 1}$ , the order of the last product being essential).

[L4]

Powers: $g^{0} = e$ , $g^{σ (k)} = g^{k} g$ for $k \in N$ , and $g^{x} = (g^{k})^{- 1}$ when $x < 0$ and $- x = ι (k)$ , where $ι : N \to Z$ is the embedding of The naturals embed in the integers with image the nonnegative integers (Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ ).

[L5]

$g^{- x} = (g^{x})^{- 1}$ for every $x \in Z$ (Exponent laws in a group: $g^{m + n} = g^{m} g^{n}$ and $(g^{m})^{n} = g^{m n}$ for all $m, n \in Z$ , and $(g h)^{n} = g^{n} h^{n}$ when $g$ and $h$ commute).

[L6]

Induction on $N$ (The principle of mathematical induction).

[L7]

$Z$ is a totally ordered commutative ring, so exactly one of $0 \leq x$ and $x < 0$ holds, and $x < 0$ gives $0 < - x$ (The integers form a commutative ring, The integers form a totally ordered ring, Arithmetic on the integers, Order on the integers, The integers as equivalence classes of pairs of naturals).

[L8]

$(Z, \cdot, 1)$ is a commutative monoid: multiplication on $Z$ is associative and commutative with $x \cdot 1 = x$ , and $x \cdot 0 = 0$ for every $x$ (The integers form a commutative ring, Arithmetic on the integers).

Proof

technique · direct

1.1

Applying [A1] with $x = y = e$ gives $f (e) = f (e e) = f (e) f (e)$ ; and $f (e) = e^{'} f (e)$ because $e^{'}$ is the identity of $G^{'}$ .

A1L1

1.2

Applying [A1] with $y = g^{- 1}$ gives $f (g) f (g^{- 1}) = f (g g^{- 1}) = f (e)$ .

A1L1

1.3

Base of claim 3 for natural exponents: $f (g^{0}) = f (e)$ and $f (g)^{0} = e^{'}$ .

1.4

The monoid statement. In the commutative monoid $(Z, \cdot, 1)$ the constant map $u (x) = 0$ satisfies $u (x y) = 0 = 0 \cdot 0 = u (x) u (y)$ for all $x, y$ , so it obeys the product law; but $u (1) = 0$ and the identity of the monoid is $1$ , and $0 \neq 1$ in $Z$ . So a map obeying the product law between monoids need not send the identity to the identity, and (H2) is not redundant there.

L8given

2.1

From $e^{'} f (e) = f (e) f (e)$ and cancellation in $G^{'}$ we get $f (e) = e^{'}$ , which is claim 1.

step 1.1L2

3.1

By steps 1.2 and 2.1, $f (g) f (g^{- 1}) = e^{'}$ , so $f (g^{- 1})$ is a right inverse of the invertible element $f (g)$ , and uniqueness of inverses gives $f (g^{- 1}) = f (g)^{- 1}$ : claim 2.

step 1.2step 2.1L3

3.2

Claim 3 for natural exponents. The set of $k \in N$ with $f (g^{k}) = f (g)^{k}$ contains $0$ , by step 1.3 and step 2.1, which give $f (g^{0}) = f (e) = e^{'} = f (g)^{0}$ ; and it is closed under $σ$ , since $f (g^{σ (k)}) = f (g^{k} g) = f (g^{k}) f (g) = f (g)^{k} f (g) = f (g)^{σ (k)}$ . By induction it is all of $N$ .

step 1.3step 2.1A1L4L6

4.1

Claim 3 for negative exponents. Let $x < 0$ and write $- x = ι (k)$ with $k \in N$ , possible since $0 < - x$ . Then $g^{x} = (g^{k})^{- 1}$ , so $f (g^{x}) = f ((g^{k})^{- 1}) = f (g^{k})^{- 1} = (f (g)^{k})^{- 1} = f (g)^{x}$ , the last equality being the definition of the negative power of $f (g)$ .

step 3.1step 3.2L4L5L7

5.1

Every integer is either nonnegative, hence of the form $ι (k)$ and covered by step 3.2, or negative and covered by step 4.1; so claim 3 holds for every $n \in Z$ .

step 3.2step 4.1L4L7

6.1

Claims 1, 2 and 3 are steps 2.1, 3.1 and 5.1, and step 1.4 shows the corresponding automatic identity preservation fails for monoids.

step 2.1step 3.1step 5.1step 1.4∎

Remarks

Cancellation is the whole difference. Step 2.1 turns $f (e) f (e) = e^{'} f (e)$ into $f (e) = e^{'}$ , and it can do so only because $G^{'}$ is a group. In a monoid the element $f (e)$ is merely idempotent, and idempotents other than the identity exist, as $0$ in $(Z, \cdot)$ shows.
Claim 3 is what makes homomorphisms interact with orders. It gives $f (g)^{n} = e^{'}$ whenever $g^{n} = e$ , so the order of $f (g)$ divides the order of $g$ when the latter is finite (If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$ ). That consequence is used from the next page onwards.
Only one of the two one-sided equations is checked in step 3.1. That is enough: $f (g)$ is invertible in the group $G^{'}$ , and for an invertible element a single one-sided equation identifies the inverse (In a monoid, a left inverse and a right inverse of the same element are equal; hence an invertible element has exactly one inverse, and it is two-sided).

5 · Examples, counterexamples and false statements

None yet.

Binary Operations, Monoids, Groups and Subgroups

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Binary operation on a set; associativity, commutativity, and a subset closed under the operation

Definition

Remarks

Left identity, right identity, and two-sided identity for a binary operation

Definition

Remarks

A left identity and a right identity for the same binary operation are equal; hence there is at most one two-sided identity

Statement

Facts & Assumptions

Proof

Remarks

Semigroup and monoid

Definition

Remarks

Left inverse, right inverse, and invertible element of a monoid

Definition

Remarks

In a monoid, a left inverse and a right inverse of the same element are equal; hence an invertible element has exactly one inverse, and it is two-sided

Statement

Facts & Assumptions

Proof

Remarks

Group and abelian group

Definition

Remarks

In a group e−1=ee−1=e, (g−1)−1=g(g−1)−1=g and (gh)−1=h−1g−1(gh)−1=h−1g−1, the order of the last product being essential

Statement

Facts & Assumptions

Proof

Remarks

Cancellation in a group: gx=gygx=gy or xg=ygxg=yg forces x=yx=y; equivalently left and right translation by gg are bijections of GG, so gx=hgx=h and xg=hxg=h each have exactly one solution

Statement

Facts & Assumptions

Proof

Remarks

The invertible elements of a monoid form a group under the restricted operation

Statement

Facts & Assumptions

Proof

Remarks

The symmetric group Sym⁡(X)Sym(X): the bijections of a set XX under composition

Definition

Remarks

Sym⁡(X)Sym(X) is a group under composition, and it is non-abelian whenever XX has at least three distinct elements

Statement

Facts & Assumptions

Proof

Remarks

The product g0g1⋯gn−1g0​g1​⋯gn−1​ of a finite list in a monoid, by recursion, with the empty product (n=0n=0) equal to the identity

Definition

Remarks

Generalised associativity: in a monoid the product of a finite list does not depend on the bracketing, and in a commutative monoid it does not depend on the order of the factors either

Statement

Facts & Assumptions

Proof

Remarks

Powers gngn: natural exponents in a monoid and integer exponents in a group, with g0=eg0=e

Definition

Remarks

Exponent laws in a group: gm+n=gmgngm+n=gmgn and (gm)n=gmn(gm)n=gmn for all m,n∈Zm,n∈Z, and (gh)n=gnhn(gh)n=gnhn when gg and hh commute

Statement

Facts & Assumptions

Proof

Remarks

Subgroup

Definition

Remarks

One-step subgroup test: a nonempty H⊆GH⊆G is a subgroup iff gh−1∈Hgh−1∈H for all g,h∈Hg,h∈H; the identity and the inverses of HH are then those of GG

Statement

Facts & Assumptions

Proof

Remarks

The intersection of a nonempty family of subgroups of GG is a subgroup of GG

Statement

Facts & Assumptions

In a group $e^{- 1} = e$ , $(g^{- 1})^{- 1} = g$ and $(g h)^{- 1} = h^{- 1} g^{- 1}$ , the order of the last product being essential

Cancellation in a group: $g x = g y$ or $x g = y g$ forces $x = y$ ; equivalently left and right translation by $g$ are bijections of $G$ , so $g x = h$ and $x g = h$ each have exactly one solution

The symmetric group $Sym (X)$ : the bijections of a set $X$ under composition

$Sym (X)$ is a group under composition, and it is non-abelian whenever $X$ has at least three distinct elements

The product $g_{0} g_{1} \dots g_{n - 1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity

Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$

Exponent laws in a group: $g^{m + n} = g^{m} g^{n}$ and $(g^{m})^{n} = g^{m n}$ for all $m, n \in Z$ , and $(g h)^{n} = g^{n} h^{n}$ when $g$ and $h$ commute

One-step subgroup test: a nonempty $H \subseteq G$ is a subgroup iff $g h^{- 1} \in H$ for all $g, h \in H$ ; the identity and the inverses of $H$ are then those of $G$

The intersection of a nonempty family of subgroups of $G$ is a subgroup of $G$

The subgroup $⟨ S ⟩$ generated by a subset, the cyclic subgroup $⟨ g ⟩$ , and cyclic groups

$⟨ g ⟩ = {g^{n} : n \in Z}$ , and every cyclic group is abelian

Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$

In a finite group, every element $g$ satisfies $g^{n} = e$ for some natural $n \geq 1$

The order $∣ G ∣$ of a finite group and the order $ord (g)$ of an element, with $ord (g) = \infty$ when no positive power of $g$ is the identity

If $ord (g) = n$ then $g^{k} = e$ iff $k$ is an integer multiple of $n$ , the powers $g^{0}, \dots, g^{n - 1}$ are distinct, and $⟨ g ⟩$ has exactly $n$ elements; if $g$ has infinite order then $g^{j} = g^{k}$ only for $j = k$

A group homomorphism automatically satisfies $f (e) = e^{'}$ and $f (g^{- 1}) = f (g)^{- 1}$ , and $f (g^{n}) = f (g)^{n}$ for every $n \in Z$ ; for monoid homomorphisms preservation of the identity must be assumed