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.
Semigroup and monoid
Definition
A semigroup is a pair consisting of a set and an associative binary operation on (Binary operation on a set; associativity, commutativity, and a subset closed under the operation).
A monoid is a triple in which is a semigroup and is a two-sided identity for (Left identity, right identity, and two-sided identity for a binary operation), that is,
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 is determined by and may be called the identity of ; it is written , or when several monoids are in play, and or in multiplicative or additive notation. For that reason a monoid is often written simply as , or as .
A semigroup or monoid is commutative (for monoids also called abelian) when its operation is commutative.
A subset is a submonoid when and is closed under ; the restricted operation then makes 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. 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.
Depends on
Used by
- A rational root of xᵏ = m is an integer: if k ≥ 1, m ∈ ℤ, x ∈ ℚ and xᵏ is the image of m, then x is the image of an integer Corollary
- Every nonzero integer n is u ∏_i<r pᵢ with u ∈ {1,-1} and every pᵢ prime; u and r are determined by n, and the list is determined up to a permutation Corollary
- If a prime p divides a finite product ∏_i<n aᵢ of integers then p ∣ aᵢ for some i < n; at n = 0 the product is 1 and the hypothesis cannot hold Corollary
- A commutative monoid in which cancellation holds need not be a group: (ℕ, +) Counterexample
- If 1 were admitted as a prime, uniqueness would fail: 6 = 2 · 3 = 1 · 2 · 3 = 1 · 1 · 2 · 3, lists of different lengths that no permutation matches Counterexample
- In the multiplicative monoid H = {1, 4, 7, 10, …} of positive integers one more than a multiple of 3, the element 100 has two genuinely different factorisations into irreducibles, 4 · 25 and 10 · 10 Counterexample
- A finite sum in a commutative monoid indexed by an arbitrary finite set Definition
- Group and abelian group Definition
- Left inverse, right inverse, and invertible element of a monoid Definition
- Linear combination of a finite list, and the span span(S) as the smallest linear subspace containing S Definition
- Monoid homomorphism and group homomorphism Definition
- Powers gⁿ: natural exponents in a monoid and integer exponents in a group, with g⁰ = e Definition
- Ring homomorphism: additive, multiplicative, and required to send 1 to 1 Definition
- Ring: an abelian group under addition and a monoid under multiplication, with multiplication distributing over addition on both sides Definition
- The p-adic valuation vₚ(a) of a nonzero integer: the greatest k ∈ ℕ with pᵏ ∣ a Definition
- The product g₀ g₁ ⋯ gₙ₋₁ of a finite list in a monoid, by recursion, with the empty product (n = 0) equal to the identity Definition
- (ℤ, +) is an abelian group, (ℤ, ·) is a commutative monoid that is not a group, and its group of units is {1, -1} Example
- 360 = 2³ · 3² · 5 and 84 = 2² · 3 · 7, with gcd(360,84) = 12 and lcm(360,84) = 2520 read off the exponents Example
- For any field F, (F, +) and (F ∖ {0}, ·) are abelian groups; in particular (ℚ, +), (ℚ ∖ {0}, ·), (ℝ, +) and (ℝ ∖ {0}, ·) Example
- For every n ∈ ℕ there are n consecutive composite integers: with N := ∏_j<n(j+2), each of N+2, …, N+n+1 is composite Example
- No rational squares to 3 or to 6, and none cubes to 2: three instances of the rational-root corollary Example
- FALSE: every Fermat number 2^2ⁿ + 1 is prime False statement
- FALSE: for every finite list p₀, …, pₙ₋₁ of distinct primes, p₀ ⋯ pₙ₋₁ + 1 is prime False statement
- FALSE: n² + n + 41 is prime for every natural number n False statement
- (ℤ, ·, 1) is a commutative monoid whose group of units is {1, -1}; equivalently u ∣ 1 holds exactly for u = 1 and u = -1 Lemma
- A group homomorphism automatically satisfies f(e) = e' and f(g⁻¹) = f(g)⁻¹, and f(gⁿ) = f(g)ⁿ for every n ∈ ℤ; for monoid homomorphisms preservation of the identity must be assumed Lemma
- Every field is a commutative ring with 1 ≠ 0; it is an integral domain, and it is a commutative division ring Lemma
- Exponent laws in a group: gᵐ⁺ⁿ = gᵐgⁿ and (gᵐ)ⁿ = gᵐⁿ for all m, n ∈ ℤ, and (gh)ⁿ = gⁿhⁿ **when g and h commute** Lemma
- For a prime p and a nonzero integer a: p^vₚ(a) ∣ a and p^vₚ(a)+1 ∤ a; pᵏ ∣ a holds exactly for k ≤ vₚ(a); vₚ(a) ≥ 1 exactly when p ∣ a; vₚ(1) = vₚ(-1) = 0; and vₚ(p) = 1 Lemma
- 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 Lemma
- Sym(X) is a group under composition, and it is non-abelian whenever X has at least three distinct elements Lemma
- The invertible elements of a monoid form a group under the restricted operation Lemma
- The units of a ring are the invertible elements of its multiplicative monoid, and R^× is a group under multiplication; 0 ∈ R^× only in the zero ring Lemma
- vₚ(ab) = vₚ(a) + vₚ(b) for nonzero integers a, b, and vₚ(a+b) ≥ min{vₚ(a), vₚ(b)} whenever a, b and a+b are all nonzero Lemma
- A monoid is a one-object category, and a group is a one-object category in which every morphism is invertible Proposition
- Eckmann–Hilton: two unital operations satisfying interchange coincide and are commutative Theorem
- Euclid's theorem: for every n ∈ ℕ and every list p : n → ℤ of primes there is a prime not among p₀, …, pₙ₋₁; consequently the set of primes is not finite Theorem
- Every integer n ≥ 1 is a finite product of primes: there are r ∈ ℕ and a list p : r → ℤ of primes with n = ∏_i<r pᵢ, the case n = 1 being the empty product Theorem
- For every natural n, (ℤ/n,+) is an abelian group, multiplication is a commutative monoid operation, and both distributive laws hold Theorem
- For n ≥ 1 and any injective list p : r → ℤ of primes containing every prime divisor of n, one has n = ∏_i<r pᵢ^ v_pᵢ(n); the exponents are determined by n, and v_q(n) = 0 for every prime q outside the list Theorem
…and 4 more results.
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 13 results over 10 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.
Sources
- Monoid (Wikipedia) (standard reference, not scraped)
- Semigroup (Wikipedia) (standard reference, not scraped)