Chapter 04 — Free Products and HNN Extensions
Proofs omitted. Hover over highlighted terms to see their Lean types.
4.1 — Free Products
Definition 4.1.1
Lean contributors (project-level attribution): Zichen Wang.
Definition 4-1-1: for groups A and B with disjoint chosen presentations, the free product A * B is the group obtained by taking the combined generators and relators of those two presentations. This item is a direct recall of mathlib's canonical free-product owner expression for groups, so the file records the type expression A ∗ B itself rather than introducing a redundant alias.
universe u v
open scoped Monoid.Coprod
variable (A : Type u) (B : Type v) [Group A] [Group B]
-- Layer triage:
-- `source-facing`: the textbook definition of the free product of two groups `A` and `B`,
-- presented by adjoining the generators and relators of two disjoint presentations.
-- `core/canonical`: `Monoid.Coprod`, with scoped notation `A ∗ B`, is mathlib's owner
-- abstraction for the coproduct of two groups.
-- `bridge/view`: no extra bridge is needed here, because the textbook item is only recalling the
-- basic owner construction itself rather than asserting a new universal property or comparison
-- theorem.
-- Domain sampling:
-- 1. `Monoid.Coprod` in `Mathlib/GroupTheory/Coprod/Basic` is the canonical free-product
-- construction for monoids and groups.
-- 2. The scoped notation `A ∗ B` is the canonical source-facing notation for that owner
-- construction.
-- 3. `Proposition_1_6_4` and `Proposition_3_12_3` already use `Monoid.Coprod` and the notation
-- `G₁ ∗ G₂` as the project's free-product API for groups.
-- 4. `Definition_4_1_2` immediately derives the factor subgroups from the canonical embeddings
-- `Monoid.Coprod.inl` and `Monoid.Coprod.inr`, so this owner file should expose only the
-- ambient free-product object itself.
-- Primitive vs. derived:
-- the primitive mathematical content of this item is just the ambient free-product object; the
-- universal property maps and later structural lemmas are derived API on top of `Monoid.Coprod`.
#check (A ∗ B)Definition 4.1.2
Lean contributors (project-level attribution): Zichen Wang.
Definition 4-1-2: inside the free product A ∗ B, the two textbook factor subgroups are the ranges of the canonical embeddings inl : A →* A ∗ B and inr : B →* A ∗ B. This item is a direct bridge/view recall of mathlib's canonical range expressions, so the file records those expressions directly instead of introducing parallel local aliases.
universe u v
open Monoid.Coprod
open scoped Monoid.Coprod
variable (A : Type u) (B : Type v) [Group A] [Group B]
#check (((inl : A →* A ∗ B).range) : Subgroup (A ∗ B))Lemma 4.1.3
Lean contributors (project-level attribution): Zichen Wang.
Lemma 4-1-3: the free product is uniquely determined by the factor groups, via the canonical equivalence MulEquiv.coprodCongr induced from equivalences of the two factors.
open scoped Monoid.Coprod
open Monoid.Coprod
universe u v
#check MulEquiv.coprodCongrDefinition 4.1.4
Lean contributors (project-level attribution): Zichen Wang.
Definition 4-1-4: a reduced sequence (normal form) for the free product of A and B is mathlib's canonical reduced-word object specialized to the two-factor free product. This item keeps Monoid.CoprodI.Word as the public owner of reduced words. The only extra chapter API introduced here is the reusable bridge Monoid.CoprodI.twoFactorFamily, which specializes the indexed owner to the two-factor case without creating a second reduced-word wrapper.
universe u v
open Monoid.CoprodI
variable (A : Type u) (B : Type v) [Monoid A] [Monoid B]
-- Primary domain: reduced words for free products of monoids, later specialized to groups.
-- Layer triage:
-- `source-facing`: the textbook notion of a reduced normal form in the free product of two
-- factors `A` and `B`.
-- `core/canonical`: `Monoid.Coprod` is mathlib's two-factor free-product owner, and `Word` in
-- `Monoid.CoprodI` is mathlib's owner abstraction for reduced words in an indexed free product.
-- `bridge/view`: `Monoid.CoprodI.twoFactorFamily A B` is the chapter's shared `Bool`/`ULift`
-- specialization used to view the two-factor case through the indexed owner.
-- No separate public two-factor reduced-word owner is introduced.
-- Domain sampling:
-- 1. `Monoid.Coprod` is mathlib's canonical two-factor free product, implemented via a
-- `Bool`-indexed family of factor types behind the scenes.
-- 2. `Monoid.CoprodI.twoFactorFamily` is the chapter's minimal same-kind bridge from two factors
-- to the
-- indexed free-product word owner.
-- 3. `Word` is the canonical reduced-word owner for indexed free products.
-- 4. `Word.empty`, `Word.prod`, and `Word.equiv` are the canonical empty-word, evaluation, and
-- normal-form API.
-- Primitive vs. derived:
-- the primitive data remain the reduced list of nontrivial letters with adjacent-factor
-- inequality; the empty word, evaluation map, and normal-form equivalence are derived API from the
-- owner abstraction. The shared two-factor specialization is exposed only as the minimal bridge
-- needed to reuse that owner abstraction in later chapter files.
#check (Word (twoFactorFamily A B))Remark 4.1.11
Lean contributors (project-level attribution): Zichen Wang.
Remark 4-1-11: in the free product A ∗ B, the commutators a b a⁻¹ b⁻¹ with a ∈ A \ {1} and b ∈ B \ {1} form a free basis of the subgroup that they generate. Via closure_freeProductFactorCommutatorSet_eq_factorSubgroupCommutator, this generated subgroup is the canonical subgroup commutator of the two factor ranges, so the basis statement is recorded in that canonical ambient subgroup.
universe u v
open Monoid.Coprod
open scoped Monoid.Coprod commutatorElement
variable (A : Type u) (B : Type v) [Group A] [Group B]
-- Layer triage:
-- `source-facing`: the explicit set of commutators `⁅a, b⁆` with `a ∈ A`, `b ∈ B`, and
-- `a ≠ 1`, `b ≠ 1`, viewed inside the free product `A ∗ B`.
-- `core/canonical`: `Monoid.Coprod` with notation `A ∗ B` is mathlib's owner for the free
-- product, the two canonical factor subgroups inside `A ∗ B` are `(inl : A →* A ∗ B).range` and
-- `(inr : B →* A ∗ B).range`, and `⁅-, -⁆` is the canonical owner for the subgroup commutator of
-- those factor subgroups.
-- `bridge/view`: the displayed commutator set is the source-facing subset of the canonical
-- subgroup commutator whose closure recovers
-- `⁅(inl : A →* A ∗ B).range, (inr : B →* A ∗ B).range⁆`.
-- Domain sampling:
-- 1. `Monoid.Coprod` and its maps `inl`, `inr` are mathlib's owner API for free products.
-- 2. The canonical factor subgroups inside `A ∗ B` are the ranges of `inl` and `inr`.
-- 3. `⁅H, K⁆` is mathlib's canonical owner for the subgroup generated by commutators of elements
-- from subgroups `H` and `K`.
-- 4. `IsFreeGroupBasis` from Definition `1-1-1` is the project's canonical source-facing way to
-- state that a displayed subset is a free basis of the subgroup it generates.
-- Primitive vs. derived:
-- the primitive source data are the nonidentity factor elements and their displayed commutators
-- in `A ∗ B`; the derived canonical subgroup is
-- `⁅(inl : A →* A ∗ B).range, (inr : B →* A ∗ B).range⁆`.
theorem freeProduct_factor_commutators_isFreeGroupBasis :
IsFreeGroupBasis
{ g : (⁅(inl : A →* A ∗ B).range, (inr : B →* A ∗ B).range⁆ : Subgroup (A ∗ B)) |
(g : A ∗ B) ∈ freeProductFactorCommutatorSet A B }Remark 4.1.12
Lean contributors (project-level attribution): Zichen Wang.
Remark 4-1-12: a group that is isomorphic to a free product A ∗ B with both factors nontrivial cannot also be isomorphic to a direct product D × E with both factors nontrivial.
universe u v w x y
open scoped Monoid.Coprod
variable {G : Type u} [Group G]
theorem not_nontrivial_directProduct_of_nontrivial_freeProduct
{A : Type v} [Group A] {B : Type w} [Group B]
{D : Type x} [Group D] {E : Type y} [Group E]
(hA : Nontrivial A) (hB : Nontrivial B)
(hfree : G ≃* A ∗ B)
(hD : Nontrivial D) (hE : Nontrivial E)
(hdirect : G ≃* D × E) : FalseTheorem 4.1.13
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-1-13 adds no new owner-level API beyond Proposition 3-3-7, so this file recalls that upstream theorem directly instead of restating its interface as a parallel local item.
universe u v w
open Monoid
variable {ι : Type v} {F : Type u} {A : ι → Type w}
variable [Group F] [IsFreeGroup F] [Group.FG F]
variable [∀ i, Group (A i)]
#check (exists_freeProduct_subgroup_family_lifting_surjection_to_indexed_freeProduct :
∀ (_ : Nonempty ι) (φ : F →* CoprodI A) (_ : Function.Surjective φ),
∃ H : ι → Subgroup F, ∃ e : CoprodI (fun i ↦ H i) ≃* F,
(∀ i, e.toMonoidHom.comp CoprodI.of = (H i).subtype) ∧
∀ i, Subgroup.map φ (H i) = (CoprodI.of : A i →* CoprodI A).range)Corollary 4.1.14
Lean contributors (project-level attribution): Zichen Wang.
Corollary 4-1-14: for a finite free product *ᵢ A i, the minimum number of generators is the sum of the minimum numbers of generators of the factors.
universe u v
open Monoid
variable {ι : Type u} {A : ι → Type v}
variable [Fintype ι] [∀ i, Group (A i)] [∀ i, Group.FG (A i)]
theorem rank_coprodI_eq_sum :
Group.rank (CoprodI A) = ∑ i, Group.rank (A i)Theorem 4.1.15
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-1-15 (Kurosh Subgroup Theorem): every subgroup of an indexed free product is itself a free product of one free group together with subgroup factors whose ambient images are conjugate to subgroups of the original free factors. This item adds no new source-facing construction beyond Proposition 3-3-6, so the file keeps a direct recall of that canonical theorem instead of restating its interface locally.
universe u v w
open Monoid
open scoped Pointwise
variable {ι : Type u} (G : ι → Type v) [∀ i, Group (G i)]
#check exists_kurosh_freeProduct_decomposition4.2 — Higman-Neumann-Neumann Extensions and Free Products with Amalgamation
Definition 4.2.1
Lean contributors (project-level attribution): Zichen Wang.
Definition 4-2-1: a reduced sequence in the source HNN-extension convention is mathlib's canonical reduced-word object HNNExtension.NormalWord.ReducedWord G B A. The textbook sequence g₀, t^{ε₁}, g₁, ..., t^{εₙ}, gₙ is represented by the initial base-group term head := g₀ together with the syllable list toList := [(ε₁, g₁), ..., (εₙ, gₙ)]. The stored chain condition in this specialization is exactly the requirement that there be no consecutive pinch t⁻¹, gᵢ, t with gᵢ ∈ A and no consecutive pinch t, gᵢ, t⁻¹ with gᵢ ∈ B, because toSubgroup B A 1 = B and toSubgroup B A (-1) = A.
universe u
open HNNExtension
open HNNExtension.NormalWord
variable {G : Type u} [Group G] (A B : Subgroup G)
#check (ReducedWord G B A)Lemma 4.2.2
Lean contributors (project-level attribution): Zichen Wang.
Lemma 4-2-2: if a reduced HNN word has at least one stable-letter syllable, then its product in the HNN extension is not the identity. Equivalently, a reduced sequence g₀, t^{ε₁}, g₁, ..., t^{εₙ}, gₙ with n ≥ 1 does not represent 1.
universe u
open HNNExtension
open HNNExtension.NormalWord
open HNNExtension.NormalWord.ReducedWord
variable {G : Type u} [Group G]
variable {A B : Subgroup G} {φ : A ≃* B}
theorem reducedWord_toHNNExtension_ne_one_of_toList_ne_nil
(w : ReducedWord G B A) (hw : w.toList ≠ []) :
w.toHNNExtension φ ≠ 1Definition 4.2.3
Lean contributors (project-level attribution): Zichen Wang.
Definition 4-2-3: after choosing right-coset representatives for A and B, a normal form in the HNN extension is mathlib's canonical type NormalWord d. Here d : TransversalPair G B A records the chosen representative of each right coset of B and of A, with 1 as the representative of the subgroup coset itself. A value of NormalWord d is exactly a sequence g₀, t^{ε₁}, g₁, ..., t^{εₙ}, gₙ in which the syllable gᵢ lies in the chosen transversal for B when εᵢ = 1 and in the chosen transversal for A when εᵢ = -1, and the inherited reduced-word chain condition excludes a consecutive subsequence t^ε, 1, t^{-ε}.
universe u
open HNNExtension
open HNNExtension.NormalWord
variable {G : Type u} [Group G] (A B : Subgroup G) (d : TransversalPair G B A)
#check (NormalWord d)Theorem 4.2.4
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-2-4: part (I), if a reduced HNN word represents the identity, then it contains no stable-letter syllables. Equivalently, a reduced sequence with n ≥ 1 cannot equal 1.
universe u
open HNNExtension
open HNNExtension.NormalWord
open HNNExtension.NormalWord.ReducedWord
variable {G : Type u} [Group G]
variable {A B : Subgroup G} {φ : A ≃* B}
theorem reducedWord_toList_eq_nil_of_toHNNExtension_eq_one
(w : ReducedWord G B A) (hprod : w.toHNNExtension φ = 1) :
w.toList = []Corollary 4.2.5
Lean contributors (project-level attribution): Zichen Wang.
Corollary 4-2-5: if the base group G has solvable word problem, the generalized word problems for A and B are solvable in G, and the subgroup isomorphism φ : A ≃* B is effectively calculable, then the HNN extension has solvable word problem. The conclusion is stated on raw HNN input words, while Britton reduction through reduced words is a derived internal step.
universe u
open HNNExtension
variable {G : Type u} [Group G] [Primcodable G]
variable {A B : Subgroup G} {φ : A ≃* B}
local notation "E" => HNNExtension G A B φ
local notation "t" => (HNNExtension.t : E)
theorem hnnExtension_hasSolvableWordProblem
[Primcodable A] [Primcodable B]
(hG : ComputablePred fun g : G ↦ g = 1)
(hA : ComputablePred fun g : G ↦ g ∈ A)
(hB : ComputablePred fun g : G ↦ g ∈ B)
(hφ : φ.toEquiv.Computable) :
ComputablePred fun w : G × List (ℤˣ × G) ↦
of w.1 * (w.2.map fun x ↦ t ^ (x.1 : ℤ) * of x.2).prod = 1Lemma 4.2.6
Lean contributors (project-level attribution): Zichen Wang.
Lemma 4-2-6: if two reduced HNN words represent the same element, then their stable-letter exponent lists agree. Equivalently, the two words have the same number of stable letters and the same exponent ±1 at each position.
universe u
open HNNExtension
open HNNExtension.NormalWord
open HNNExtension.NormalWord.ReducedWord
variable {G : Type u} [Group G]
variable {A B : Subgroup G} {φ : A ≃* B}
theorem reducedWord_exponentList_eq_of_toHNNExtension_eq
(w₁ w₂ : ReducedWord G B A) (hprod : w₁.toHNNExtension φ = w₂.toHNNExtension φ) :
w₁.toList.map Prod.fst = w₂.toList.map Prod.fstTheorem 4.2.7
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-2-7 (1): every finite-order element of an HNN extension is conjugate to the image of an element of the base group. The finite-order conclusion for that base element is derived from conjugacy and injectivity of of.
universe u
open HNNExtension
variable {G : Type u} [Group G]
variable {A B : Subgroup G} {φ : A ≃* B}
local notation "E" => HNNExtension G A B φ
local notation "of" => (HNNExtension.of : G →* E)
theorem exists_base_isConj_of_hnnExtension_isOfFinOrder (x : E) (hx : IsOfFinOrder x) :
∃ g : G, IsConj (of g) xTheorem 4.2.8
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-2-8 (1): conjugate cyclically reduced reduced words in an HNN extension with at least one stable-letter syllable have the same stable-letter length.
universe u
open List
open HNNExtension
open HNNExtension.NormalWord
variable {G : Type u} [Group G]
variable {A B : Subgroup G} {φ : A ≃* B}
namespace HNNExtension.NormalWord
namespace ReducedWord
local notation "W" => ReducedWord G B A
theorem conjugacy_length_eq_of_isCyclicallyReduced
(u v : W) (hu_nonempty : u.toList ≠ [])
(hu_cyclic : u.IsCyclicallyReduced) (hv_cyclic : v.IsCyclicallyReduced)
(hconj : IsConj (u.toHNNExtension φ) (v.toHNNExtension φ)) :
u.toList.length = v.toList.lengthDefinition 4.2.9
Lean contributors (project-level attribution): Zichen Wang.
Definition 4-2-9: a word in the free product of G and H with A and B amalgamated along e is reduced when it is an alternating word in the two factors and either has length at most one or, if it has length greater than one, every letter lies outside the amalgamated subgroup in its factor. The alternating nontrivial-word clauses are already carried by Monoid.CoprodI.Word; this source-facing predicate only adds the textbook length-one exception on top of the canonical owner-side predicate Monoid.PushoutI.Reduced.
universe u v w
open Monoid
open Monoid.CoprodI Monoid.PushoutI
open MulEquiv
namespace Subgroup
variable {G : Type u} {H : Type v} [Group G] [Group H]
variable {A : Subgroup G} {B : Subgroup H}
namespace amalgamatedProductAlong
variable (e : A ≃* B)
local notation "Family" => Monoid.CoprodI.twoFactorFamily G H
local notation "P" => Subgroup.amalgamatedProductAlong e
local notation "ιA" => A.subtype
local notation "ιB" => B.subtype.comp e.toMonoidHom
local notation "Maps" => twoFactorAmalgamatingMaps ιA ιB
abbrev Reduced (w : Word Family) : Prop :=
TwoFactorReduced ιA ιB wTheorem 4.2.10
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-2-10: a reduced sequence of positive length in a free product with amalgamation represents a nontrivial element of the pushout.
universe uA uG uH
open Monoid
open Monoid.CoprodI Monoid.PushoutI
open MulEquiv
variable {A : Type uA} {G : Type uG} {H : Type uH}
variable [Group A] [Group G] [Group H]
variable (φG : A →* G) (φH : A →* H)
local notation "Family" => Monoid.CoprodI.twoFactorFamily G H
local notation "Maps" => Monoid.CoprodI.twoFactorAmalgamatingMaps φG φH
local notation "P" => PushoutI Maps
local notation "W" => Word Family
theorem reduced_sequence_prod_ne_one
(hφG : Function.Injective φG) (hφH : Function.Injective φH)
{word : W}
(hw : TwoFactorReduced φG φH word)
(hn : 1 ≤ word.toList.length) :
PushoutI.ofCoprodI word.prod ≠ (1 : P)Theorem 4.2.11
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-2-11: every finite-order element of the amalgamated product P = ⟨G * H; A = B, e⟩ is conjugate to a finite-order element of one of the two factors.
universe u
open Monoid
variable {G H : Type u} [Group G] [Group H]
variable {A : Subgroup G} {B : Subgroup H} (e : A ≃* B)
open Subgroup.amalgamatedProductAlong
local notation "P" => Subgroup.amalgamatedProductAlong e
theorem exists_factor_isConj_of_amalgamatedProduct_isOfFinOrder
(x : P) (hx : IsOfFinOrder x) :
(∃ g : G, IsOfFinOrder g ∧ IsConj (left e g) x) ∨
∃ h : H, IsOfFinOrder h ∧ IsConj (right e h) xTheorem 4.2.12
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-2-12: in the free product with amalgamation of G and H over A = B via e, if a reduced word u is cyclically reduced and has at least two syllables, then every cyclically reduced conjugate reduced word v is obtained by cyclically permuting the syllables of u and then conjugating by an element of the amalgamated subgroup A.
universe u
open List
open Monoid
open Monoid.CoprodI Monoid.PushoutI
variable {G H : Type u} [Group G] [Group H]
variable {A : Subgroup G} {B : Subgroup H}
variable (e : A ≃* B)
open Subgroup.amalgamatedProductAlong
local notation "Family" => Monoid.CoprodI.twoFactorFamily G H
local notation "W" => Word Family
local notation "ιA" => A.subtype
local notation "ιB" => B.subtype.comp e.toMonoidHom
theorem exists_amalgamatedConjugator_and_cyclicPermutation_of_isConj_of_cyclicallyReduced
{u v : W}
(hu : u.IsCyclicallyReduced ιA ιB)
(hu_len : 2 ≤ u.toList.length)
(hv : v.IsCyclicallyReduced ιA ιB)
(hconj : IsConj (ofWord e u) (ofWord e v)) :
∃ a : A, ∃ w : W,
u.toList ~r w.toList ∧
ofWord e v = (base e a)⁻¹ * ofWord e w * base e a4.3 — Some Embedding Theorems
Theorem 4.3.1
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-3-1: every countable group embeds in a group generated by two elements of infinite order. The ambient group has an element of exact positive order n if and only if C does, and finite presentability of C implies finite presentability of the ambient group.
universe u
variable (C : Type u) [Group C]
variable [Countable C]
theorem exists_embedding_into_two_generator_group_with_infiniteOrder_generators :
∃ (G : Type u) (_ : Group G) (f : C →* G),
Function.Injective f ∧
∃ a b : G,
Subgroup.closure ({a, b} : Set G) = ⊤ ∧
orderOf a = 0 ∧
orderOf b = 0 ∧
(∀ n : ℕ+, (∃ g : G, orderOf g = n) ↔ ∃ c : C, orderOf c = n) ∧
(Group.IsFinitelyPresented C → Group.IsFinitelyPresented G)Theorem 4.3.2
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-3-2: there exists a continuum-sized family of pairwise non-isomorphic groups, each generated by at most two elements.
universe u
theorem continuum_many_pairwise_nonisomorphic_two_generator_groups :
∃ (G : Set ℕ → Type u) (_ : ∀ S, Group (G S)) (_ : ∀ S, Group.FG (G S)),
(∀ S, Group.rank (G S) ≤ 2) ∧ Pairwise fun S T ↦ IsEmpty (G S ≃* G T)Theorem 4.3.3
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-3-3: every countable group embeds in a countable group in which any two elements of the same order are conjugate.
universe u
variable (C : Type u) [Group C] [Countable C]
theorem countable_group_embeds_in_countable_group_with_orderOf_eq_isConj :
∃ (G : Type u) (_ : Group G) (_ : Countable G) (f : C →* G),
Function.Injective f ∧ ∀ x y : G, orderOf x = orderOf y → IsConj x yDefinition 4.3.4
Lean contributors (project-level attribution): Zichen Wang.
Definition 4-3-4: a group G is divisible when every element of G has an nth root for every positive integer n. Mathlib records the chapter-facing owner of this notion as RootableBy G ℕ. For groups this is equivalent to the integer-indexed rootability structure, but the ℕ-indexed form matches the textbook definition directly. The textbook existential wording is recovered by the companion theorem below, so the main labeled entry is the direct recall of this canonical type expression rather than a redundant local alias.
universe u
variable (G : Type u) [Group G]
#check (RootableBy G ℕ)Theorem 4.3.5
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-3-5: every countable group embeds into a countable simple group in which every element has roots of all positive integer orders.
universe u
variable (C : Type u) [Group C] [Countable C]
theorem countable_group_embeds_in_countable_simple_divisible_group :
∃ (G : Type u) (_ : Group G) (f : C →* G) (_ : RootableBy G ℕ),
Countable G ∧ IsSimpleGroup G ∧ Function.Injective fTheorem 4.3.6
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-3-6: every countable group embeds in a simple group generated by at most six elements.
universe u
variable (C : Type u) [Group C] [Countable C]
theorem countable_group_embeds_in_six_generator_simple_group :
∃ (S : Type u) (_ : Group S) (_ : Group.FG S) (f : C →* S),
IsSimpleGroup S ∧ Function.Injective f ∧ Group.rank S ≤ 6Theorem 4.3.7
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-3-7: if a recursive presentation (X; R) presents a simple group, equivalently if its canonical presented group PresentedGroup R is simple, then (X; R) has solvable word problem.
universe u
namespace GroupPresentation
variable {X : Type u} [Primcodable X]
theorem hasSolvableWordProblem_of_isRecursive_of_simple_presentedGroup
(R : Set (FreeGroup X)) (hR : IsRecursive R) (hsimple : IsSimpleGroup (PresentedGroup R)) :
HasSolvableWordProblem R4.4 — Some Decision Problems
Definition 4.4.1
Lean contributors (project-level attribution): Zichen Wang.
Definition 4-4-1: a property P of finitely presented groups is a Markov property when it is invariant under isomorphism of finitely presented groups, some finitely presented group has P, and some finitely presented group embeds in no finitely presented group having P.
universe u
namespace Group
class IsMarkovProperty (P : (G : Type u) → [Group G] → Prop) : Prop where
/-- The property is preserved along multiplicative equivalences out of a finitely presented
group. -/
of_mulEquiv {G H : Type u} [Group G] [Group H]
(e : G ≃* H) (_ : IsFinitelyPresented G) :
P G → P H
/-- Some finitely presented group satisfies the property. -/
exists_with_property :
∃ (G₁ : Type u) (_ : Group G₁) (_ : IsFinitelyPresented G₁), P G₁
/-- Some finitely presented group cannot embed in any finitely presented group satisfying the
property. -/
exists_embedding_obstruction :
∃ (G₂ : Type u) (_ : Group G₂) (_ : IsFinitelyPresented G₂),
∀ {H : Type u} [Group H] (_ : IsFinitelyPresented H) (_ : P H) (f : G₂ →* H),
¬ Function.Injective fTheorem 4.4.2
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-4-2: every Markov property of finitely presented groups has unsolvable recognition problem.
universe u
namespace GroupPresentation
variable (P : (G : Type u) → [Group G] → Prop)
-- Proof sketch: Adian-Rabin encodes the obstruction group from `IsMarkovProperty P` into a finite
-- presentation so that deciding whether the presented group has `P` would decide whether a given
-- word becomes trivial in an arbitrary finitely presented group. Since the latter is unsolvable,
-- the recognition problem for `P` cannot be computable.
theorem not_hasSolvableRecognitionProblem [Group.IsMarkovProperty P] :
¬ HasSolvableRecognitionProblem PLemma 4.4.3
Lean contributors (project-level attribution): Zichen Wang.
Lemma 4-4-3: a pair of free-group words lies in the textbook subgroup L_H if and only if the two words represent the same element of H = PresentedGroup rels. Here the local notation LH is the owner-side rendering of the textbook subgroup L_H by the canonical equalizer subgroup eqLocus (q.comp (fst F F)) (q.comp (snd F F)).
universe u
open MonoidHom
variable {X : Type u} (rels : Set (FreeGroup X))
-- Layer triage:
-- `source-facing`: the textbook subgroup `L_H ⊆ F(X) × F(X)` attached to
-- `H = PresentedGroup rels`, together with the criterion that `(u, v) ∈ L_H` exactly when `u`
-- and `v` represent the same element of `H`.
-- `core/canonical`: `PresentedGroup.mk rels` is the canonical quotient map
-- `FreeGroup X → PresentedGroup rels`, and `eqLocus` is the canonical subgroup equalizer of two
-- homomorphisms.
-- `bridge/view`: `L_H` is rendered directly by the equalizer of the two coordinate composites
-- into `PresentedGroup rels`, and membership in that equalizer is the textbook equality of the
-- two quotient images.
-- Domain sampling:
-- 1. `PresentedGroup rels` is the chapter owner for the quotient by relators `rels`.
-- 2. `PresentedGroup.mk rels` is the canonical map sending a free-group word to its class in the
-- presented group.
-- 3. `eqLocus` is mathlib's owner subgroup of elements on which two homomorphisms agree.
-- 4. `fst` and `snd` are the canonical product projections used to compare the two coordinates
-- after applying `PresentedGroup.mk rels`.
-- Primitive vs. derived:
-- the primitive source data are the relator set `rels` and the words `u`, `v`; the textbook
-- subgroup `L_H` is a derived owner-side equalizer construction, so no separate public wrapper is
-- introduced for it.
local notation "F" => FreeGroup X
local notation "q" => PresentedGroup.mk rels
local notation "LH" =>
eqLocus (comp (PresentedGroup.mk rels) (fst F F)) (comp (PresentedGroup.mk rels) (snd F F))
theorem mem_LH_iff (u v : F) : (u, v) ∈ LH ↔ q u = q vDefinition 4.4.5
Lean contributors (project-level attribution): Zichen Wang.
Definition 4-4-5: the generating problem for F_n × F_n is solvable when one can compute from a finite list of pairs of words whether their values generate the whole direct product.
namespace FreeGroupProduct
variable (n : ℕ)
local notation "F" => FreeGroup (Fin n)
local notation "Word" => List (Fin n × Bool)
local notation "WordPair" => Word × Word
def HasSolvableGeneratingProblem : Prop :=
ComputablePred fun L : List WordPair ↦
Subgroup.closure (wordPairValue n '' {w | w ∈ L}) = ⊤Theorem 4.4.6
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-4-6: if n ≥ 6, then the generating problem for F_n × F_n is unsolvable.
namespace FreeGroupProduct
theorem not_hasSolvableGeneratingProblem (n : ℕ) (hn : 6 ≤ n) :
¬ HasSolvableGeneratingProblem n-
Theorem 4.4.7 — no statement yet (Lean source)
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4.4.8
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-4-8: a finitely presented residually finite group has solvable word problem.
universe u
namespace Group
variable {G : Type u} [Group G]
-- Proof sketch: the chosen presentation equivalence together with the owner-side solvable word
-- problem for that presentation is exactly the data required by `HasSolvableWordProblem G`.
theorem hasSolvableWordProblem_of_isFinitelyPresented_of_residuallyFinite
(G : Type u) [Group G] [IsFinitelyPresented G] [ResiduallyFinite G] :
HasSolvableWordProblem GTheorem 4.4.9
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-4-9 (1): a finitely generated group has only finitely many subgroups of any fixed positive index n.
universe u
variable {G : Type u} [Group G] [Group.FG G]
namespace Subgroup
-- Layer triage:
-- `source-facing`: finite generation of `G`, subgroups of a fixed finite index, and a
-- characteristic finite-index subgroup contained in a given finite-index subgroup.
-- `core/canonical`: `Subgroup.index`, `H.FiniteIndex`, `K.Characteristic`, and finite
-- intersections of finite-index subgroups.
-- `bridge/view`: the first clause packages the textbook "number of subgroups" as finiteness of
-- the set `{H : Subgroup G | H.index = n}`, and the second clause keeps the source-facing
-- existential conclusion with the canonical finite-index owner property instead of introducing an
-- auxiliary bundled wrapper.
-- Domain sampling:
-- 1. `Subgroup.index` is mathlib's owner for subgroup index.
-- 2. `Subgroup.FiniteIndex` is the canonical finite-index hypothesis on a subgroup.
-- 3. `Subgroup.characteristic_iff_map_eq` is the owner criterion for invariance under
-- automorphisms.
-- 4. `Subgroup.finiteIndex_iInf'` is the finite-intersection owner theorem used by the textbook's
-- intersection construction.
-- Primitive vs. derived:
-- the primitive public data are only the ambient finitely generated group `G`, the index `n` in
-- the first clause, and the finite-index subgroup `H` in the second clause. The finite set of
-- index-`n` subgroups and the characteristic finite-index subgroup contained in `H` are derived
-- owner-level conclusions.
-- Proof sketch: encode each subgroup of index `n` by its transitive action on the `n` right
-- cosets, producing a homomorphism into the symmetric group on `n` letters. A finitely generated
-- group has only finitely many homomorphisms into a fixed finite group, so only finitely many
-- index-`n` subgroups can occur.
theorem finite_setOf_index_eq (n : ℕ+) :
Set.Finite {H : Subgroup G | H.index = (n : ℕ)}Theorem 4.4.10
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-4-10: if G is finitely generated and residually finite, then its automorphism group Aut(G) is residually finite.
universe u
variable {G : Type u} [Group G] [Group.FG G] [Group.ResiduallyFinite G]
-- Layer triage:
-- `source-facing`: a finitely generated residually finite group `G` and the automorphism group
-- `Aut(G)`.
-- `core/canonical`: `Group.FG G`, `Group.ResiduallyFinite G`, `FiniteIndexNormalSubgroup`, and
-- `MulAut G`.
-- `bridge/view`: the textbook notation `Aut(G)` is the canonical multiplicative automorphism group
-- `MulAut G`; residual finiteness is stated directly via the mathlib class on that owner.
-- Domain sampling:
-- 1. `Group.ResiduallyFinite` is mathlib's owner predicate for residual finiteness.
-- 2. `Group.residuallyFinite_iff_exists_finiteIndexNormalSubgroup` is the owner-level separation
-- criterion for residual finiteness.
-- 3. `Subgroup.exists_characteristic_le_of_finiteIndex` from Theorem `4-4-9` is the chapter's
-- canonical bridge from an arbitrary finite-index subgroup to a characteristic one.
-- 4. `MulAut G` is the canonical group of automorphisms of `G`.
--
-- Primitive vs. derived:
-- the primitive public content is only the owner instance
-- `Group.ResiduallyFinite (MulAut G)`. The separating finite-index normal subgroup of `MulAut G`
-- used in the textbook argument is derived owner-level data, so it should not be promoted to a
-- separate wrapper or existentially chosen public definition.
-- Proof sketch: for a nontrivial automorphism `α`, choose `c : G` moved by `α`, so
-- `α c * c⁻¹ ≠ 1`. By
-- `Group.residuallyFinite_iff_exists_finiteIndexNormalSubgroup`, choose a finite-index normal
-- subgroup of `G` missing that element, then apply Theorem `4-4-9` to refine it to a
-- characteristic finite-index subgroup `K`. Every automorphism of `G` then descends to `G ⧸ K`,
-- yielding a homomorphism `MulAut G →* MulAut (G ⧸ K)` into a finite group that does not kill
-- `α`.
instance residuallyFinite_mulAut_of_fg_residuallyFinite :
Group.ResiduallyFinite (MulAut G)Theorem 4.4.11
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-4-11: the group ⟨ b, t ; t⁻¹ b^2 t = b^3 ⟩ is non-Hopfian.
namespace BaumslagSolitar23
local notation "b" => y
local notation "t" => x
theorem not_isHopfian : ¬ IsHopfian GroupRemark 4.4.12
Lean contributors (project-level attribution): Zichen Wang.
Remark 4-4-12: the Baumslag-Solitar group ⟨ b, t ; t⁻¹ b^2 t = b^3 ⟩ is not residually finite.
namespace BaumslagSolitar23
theorem not_residuallyFinite : ¬ Group.ResiduallyFinite GroupTheorem 4.4.13
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-4-13: every finitely generated residually finite group is Hopfian.
universe u
variable {G : Type u} [Group G] [Group.FG G] [Group.ResiduallyFinite G]
-- Primary domain: Hopfianity of finitely generated residually finite groups.
--
-- Layer triage:
-- `source-facing`: a group `G` that is both finitely generated and residually finite.
-- `core/canonical`: `Group.FG`, `Group.ResiduallyFinite`, and the chapter owner `IsHopfian`.
-- `bridge/view`: the textbook endomorphism formulation is a thin consequence of the owner
-- predicate `IsHopfian`.
-- Domain sampling:
-- 1. `Group.FG` from `Mathlib.GroupTheory.Finiteness` is the canonical owner predicate for finite
-- generation of a group.
-- 2. `Group.ResiduallyFinite` from `Mathlib.GroupTheory.ResiduallyFinite` is the canonical owner
-- predicate for residual finiteness.
-- 3. `IsHopfian` from Proposition `1-3-5` is the project's owner predicate for the Hopfian
-- conclusion.
-- 4. `MonoidHom.injective_of_surjective` is the canonical bridge from `IsHopfian G` back to the
-- source-facing endomorphism statement.
--
-- Primitive vs. derived:
-- the primitive public content is the owner instance `IsHopfian G`; the endomorphism-level
-- injectivity statement is derived API and should not remain the main declaration.
instance isHopfian_of_fg_residuallyFinite : IsHopfian G4.5 — One-Relator Groups
Theorem 4.5.1
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-5-1 adds no new owner-level construction beyond Theorem 2-6-1. The recalled theorem already contains the source-facing free-basis conclusion together with the stronger injectivity statement for the generator images.
universe u
variable {X : Type u} (r : FreeGroup X)
local notation "basis" => FreeGroupBasis.ofFreeGroup X
local notation "G" => PresentedGroup (Set.singleton r)
local notation "gen" => (PresentedGroup.of : X → G)
#check (freiheitssatz_injOn_presentedGroup_of_and_isFreeGroupBasis r :
∀ (L : Set X) {x : X},
FreeGroup.IsCyclicallyReduced r.toWord →
basisLetterOccurs basis x r →
x ∉ L →
Set.InjOn gen L ∧
IsFreeGroupBasis {g : Subgroup.closure (gen '' L) | (g : G) ∈ gen '' L})Theorem 4.5.2
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-5-2 (1): if the relator r of a one-relator group is not a proper power in the ambient free group, then the quotient PresentedGroup ({r} : Set (FreeGroup X)) is torsion free. This is exactly Proposition 2-5-17, so the file reuses that canonical theorem directly rather than keeping a duplicate local wrapper.
universe u
variable {X : Type u}
#check isMulTorsionFree_presentedGroup_singleton_of_relator_not_properPowerTheorem 4.5.3
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-5-3 adds no new owner-level construction beyond Proposition 2-5-5. The upstream theorem already has the exact source-faithful interface for deciding whether a signed word represents an element of the subgroup generated by a recursive subset of the distinguished generators in a one-relator quotient.
universe u
namespace GroupPresentation
variable {X : Type u} [Primcodable X]
#check computable_represents_element_of_generatorImageSubgroupDefinition 4.5.4
Lean contributors (project-level attribution): Zichen Wang.
Definition 4-5-4: a subgroup M of the one-relator group G = ⟨X ; r⟩ is a Magnus subgroup when M is generated by the image of a subset L ⊆ X omitting some generator that occurs in the relator r.
universe u
variable {X : Type u} (r : FreeGroup X)
local notation "G" => PresentedGroup (Set.singleton r)
def IsMagnusSubgroup (M : Subgroup G) : Prop :=
∃ L : Set X, ∃ x : X,
basisLetterOccurs (FreeGroupBasis.ofFreeGroup X) x r ∧
x ∉ L ∧
M = Subgroup.closure (PresentedGroup.of '' L)Theorem 4.5.5
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-5-5: if r is cyclically reduced, M is a Magnus subgroup of the one-relator group PresentedGroup (Set.singleton r), and g does not lie in M, then the intersection gMg⁻¹ ∩ M is cyclic.
universe u
open scoped Pointwise
variable {X : Type u}
variable (r : FreeGroup X)
local notation "G" => PresentedGroup (Set.singleton r)
theorem conjugate_intersection_isCyclic_of_isMagnusSubgroup
(hred : FreeGroup.IsCyclicallyReduced r.toWord)
(M : Subgroup G) (hM : IsMagnusSubgroup r M) (g : G)
(hg : g ∉ M) :
IsCyclic ↥((MulAut.conj g • M) ⊓ M)Theorem 4.5.6
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-5-6: if G = ⟨X ; r^n = 1⟩ with r cyclically reduced and n > 1, and a freely reduced word w is equal in G to a word v omitting some generator that occurs in w, then w contains a contiguous subword that is also a subword of the reduced word of r^n or r⁻ⁿ, and whose length is greater than (n - 1) / n times the length of r^n. The fractional bound is rendered as the equivalent natural-number inequality n * segment.length > (n - 1) * (((FreeGroup.mk relator : FreeGroup X) ^ n).toWord.length).
universe u
open List
variable {X : Type u}
local notation "basis" => FreeGroupBasis.ofFreeGroup X
theorem exists_long_relatorPower_subword_of_eq_in_oneRelatorTorsion
(relator w v : List (X × Bool)) (n : ℕ)
(hr_cyclic : FreeGroup.IsCyclicallyReduced relator)
(hw_reduced : FreeGroup.IsReduced w)
(hn : 1 < n)
(heq :
PresentedGroup.mk (Set.singleton ((FreeGroup.mk relator : FreeGroup X) ^ n))
(FreeGroup.mk w) =
PresentedGroup.mk (Set.singleton ((FreeGroup.mk relator : FreeGroup X) ^ n))
(FreeGroup.mk v))
(homit : ∃ x : X, x ∈ w.map Prod.fst ∧ x ∉ v.map Prod.fst) :
∃ segment : List (X × Bool),
segment <:+: w ∧
(segment <:+: (FreeGroup.mk relator ^ n).toWord ∨
segment <:+: ((FreeGroup.mk relator ^ n)⁻¹).toWord) ∧
n * segment.length >
(n - 1) * ((FreeGroup.mk relator ^ n).toWord.length)4.6 — Bipolar Structures
Definition 4.6.1
Lean contributors (project-level attribution): Zichen Wang.
Definition 4-6-1: a bipolar structure on a group is a decomposition of the group into the subgroup piece F and the four sectors EE, EE*, E*E, and E*E*, satisfying the subgroup, nontriviality, right-translation, inverse, product, and boundedness axioms from the text.
universe u
open Function Pole
structure BipolarStructure (G : Type u) [Group G] where
/-- The subgroup piece `F`. -/
F : Subgroup G
/-- The sector `XY` for `X,Y ∈ {E,E*}`. -/
sector : Pole → Pole → Set G
/-- The fixed subgroup piece together with the four sectors cover the whole group. -/
pieces_cover :
(F : Set G) ∪ ⋃ X : Pole, ⋃ Y : Pole, sector X Y = (Set.univ : Set G)
/-- The fixed subgroup piece is disjoint from every sector. -/
fixed_disjoint_sector (X Y : Pole) :
Disjoint (F : Set G) (sector X Y)
/-- Distinct sectors are pairwise disjoint. -/
sector_pairwiseDisjoint :
Pairwise (Disjoint on fun p : Pole × Pole ↦ sector p.1 p.2)
/-- The mixed sector `EE*` is nonempty. -/
eeStar_nonempty : (sector E EStar).Nonempty
/-- Right multiplication by an element of `F` preserves each sector. -/
sector_mul_mem {X Y : Pole} {g f : G} (hg : g ∈ sector X Y) (hf : f ∈ F) :
g * f ∈ sector X Y
/-- Inversion sends the sector `XY` to the sector `YX`. -/
inv_mem_sector {X Y : Pole} {g : G} (hg : g ∈ sector X Y) :
g⁻¹ ∈ sector Y X
/-- Multiplying an `XY` element by a `Y*Z` element lands in `XZ`. -/
mul_mem_sector {X Y Z : Pole} {g h : G} (hg : g ∈ sector X Y)
(hh : h ∈ sector (star Y) Z) :
g * h ∈ sector X Z
/-- The lengths of admissible sector factorizations of a fixed group element are
uniformly bounded. -/
bounded_factorizations (g : G) :
∃ N : ℕ, ∀ n : ℕ, HasSectorFactorization sector g n → n ≤ NLemma 4.6.2
Lean contributors (project-level attribution): Zichen Wang.
Lemma 4-6-2: if g ∈ XY, h ∈ YZ, and h admits no length-two admissible sector factorization, then gh lies either in the fixed subgroup piece F or in some sector XW.
universe u
namespace BipolarStructure
variable {G : Type u} [Group G]
theorem mul_mem_fixed_or_sector_of_irreducible
(B : BipolarStructure G) {X Y Z : Pole} {g h : G}
(hg : g ∈ B X Y) (hh : h ∈ B Y Z) (hirr : B.IsIrreducible h) :
g * h ∈ B.F ∨ ∃ W : Pole, g * h ∈ B X WLemma 4.6.3
Lean contributors (project-level attribution): Zichen Wang.
Lemma 4-6-3: if g ∈ XY and h ∈ YZ are both irreducible, meaning that neither admits a length-two sector factorization, then gh is an irreducible element of F ∪ XZ.
universe u
namespace BipolarStructure
variable {G : Type u} [Group G]
theorem mul_mem_fixed_union_sector_and_isIrreducible
(B : BipolarStructure G) {X Y Z : Pole} {g h : G}
(hg : g ∈ B X Y) (hh : h ∈ B Y Z)
(hgirr : B.IsIrreducible g) (hhirr : B.IsIrreducible h) :
g * h ∈ (B.F : Set G) ∪ B X Z ∧ B.IsIrreducible (g * h)Lemma 4.6.4
Lean contributors (project-level attribution): Zichen Wang.
Lemma 4-6-4: right multiplication by an element of the fixed subgroup preserves irreducibility in a sector.
universe u
namespace BipolarStructure
variable {G : Type u} [Group G]
theorem isIrreducibleIn_mul_fixed_right
(B : BipolarStructure G) {X Y : Pole} {g f : G}
(hg : g ∈ B X Y) (hgirr : B.IsIrreducible g) (hf : f ∈ B.F) :
g * f ∈ B X Y ∧ B.IsIrreducible (g * f)Theorem 4.6.5
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-6-5: a group has a bipolar structure if and only if it is either a nontrivial free product with amalgamation, including the ordinary free product case, or an HNN extension.
universe u v w
open Subgroup
theorem nonempty_bipolarStructure_iff_nontrivialAmalgamatedFreeProduct_or_hnnExtension
(G : Type u) [Group G] :
Nonempty (BipolarStructure G) ↔
(∃ (G₁ : Type v) (_ : Group G₁) (G₂ : Type w) (_ : Group G₂)
(A : Subgroup G₁) (B : Subgroup G₂) (e : A ≃* B)
(_ : G ≃* amalgamatedProductAlong e),
A < ⊤ ∧ B < ⊤) ∨
∃ (G₀ : Type v) (_ : Group G₀) (A : Subgroup G₀) (B : Subgroup G₀) (φ : A ≃* B),
Nonempty (G ≃* HNNExtension G₀ A B φ)Theorem 4.6.6
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-6-6 (1): in a two-factor free product with amalgamation, a subgroup that meets every conjugate of the amalgamated subgroup trivially is a free product of one free factor together with subgroup factors which are the corresponding conjugate intersections with the left or right factor subgroups.
universe u v w
open Monoid
open HNNExtension
open scoped Pointwise
variable {G1 : Type u} {G2 : Type v} [Group G1] [Group G2]
variable {A : Subgroup G1} {B : Subgroup G2} (e : A ≃* B)
open Subgroup.amalgamatedProductAlong
local notation "P" => Subgroup.amalgamatedProductAlong e
theorem exists_kurosh_factor_decomposition_of_disjoint_base_conjugates_amalgamatedProductAlong
(H : Subgroup P)
(hbase : ∀ p : P, Disjoint H (MulAut.conj p⁻¹ • (base e).range)) :
∃ (κ : Type w) (K : κ → Subgroup H) (F : Subgroup H)
(ψ : CoprodI (kuroshFactorFamily F K) ≃* H),
IsKuroshFactorDecomposition H K F ψ ∧
∀ j,
∃ p : P,
K j = Subgroup.comap H.subtype (MulAut.conj p⁻¹ • (left e).range) ∨
K j = Subgroup.comap H.subtype (MulAut.conj p⁻¹ • (right e).range)Corollary 4.6.7
Lean contributors (project-level attribution): Zichen Wang.
Corollary 4-6-7 (1): in a free product with amalgamation, a subgroup that meets every conjugate of each factor subgroup trivially is free.
universe u v
open scoped Pointwise
variable {G1 : Type u} {G2 : Type v} [Group G1] [Group G2]
variable {A : Subgroup G1} {B : Subgroup G2} (e : A ≃* B)
open Subgroup.amalgamatedProductAlong
local notation "P" => Subgroup.amalgamatedProductAlong e
theorem isFreeGroup_of_disjoint_factor_conjugates_amalgamatedProductAlong
(K : Subgroup P)
(hleft : ∀ p : P, Disjoint K (MulAut.conj p⁻¹ • (left e).range))
(hright : ∀ p : P, Disjoint K (MulAut.conj p⁻¹ • (right e).range)) :
IsFreeGroup KLemma 4.6.8
Lean contributors (project-level attribution): Zichen Wang.
Lemma 4-6-8 (1): a finitely generated subgroup of a nontrivial free product with amalgamation is either contained in a conjugate of one of the two factor subgroups, or some conjugate of that subgroup contains a cyclically reduced element represented by a reduced word of length at least two.
universe u
open Monoid.CoprodI
open Monoid.CoprodI.Word
open HNNExtension
open HNNExtension.NormalWord
open scoped Pointwise
variable {G1 : Type u} {G2 : Type u} [Group G1] [Group G2]
variable {A : Subgroup G1} {B : Subgroup G2} (e : A ≃* B)
open Subgroup.amalgamatedProductAlong
local notation "P" => Subgroup.amalgamatedProductAlong e
local notation "Family" => Monoid.CoprodI.twoFactorFamily G1 G2
local notation "W" => Word Family
local notation "ιA" => A.subtype
local notation "ιB" => B.subtype.comp e.toMonoidHom
theorem subgroup_le_conjugate_factor_or_exists_cyclicallyReduced_conjugate_amalgamatedProductAlong
(K : Subgroup P) (hK : K.FG) :
(∃ p : P, K ≤ MulAut.conj p • (left e).range) ∨
(∃ p : P, K ≤ MulAut.conj p • (right e).range) ∨
∃ p : P, ∃ w : W,
w.IsCyclicallyReduced ιA ιB ∧
2 ≤ w.toList.length ∧
ofWord e w ∈ MulAut.conj p • KTheorem 4.6.9
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-6-9 adds no new owner-level API beyond Proposition 3-13-8. The upstream theorem already states the source-faithful Bass-Serre decomposition on the canonical subgroup objects, so this file keeps only a direct recall instead of a parallel local Monoid.PushoutI presentation.
universe u
open scoped MatrixGroups
variable {K : Type u} [Field K]
#check (glPolynomial_amalgamatedProductComparison_bijective K :
Function.Bijective
(Subgroup.amalgamatedProductComparison
(constantLinearSubgroup K)
(upperTriangularSubgroup : Subgroup (GL (Fin 2) (Polynomial K)))))4.7 — The Higman Embedding Theorem
Theorem 4.7.1
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-7-1 (Higman Embedding Theorem): a finitely generated group embeds in some finitely presented group if and only if it is recursively presented.
universe u
namespace Group
variable {G : Type u} [Group G]
variable (G : Type u) [Group G] [FG G]
theorem exists_finitelyPresented_embedding_iff_isRecursivelyPresented :
(∃ (H : Type u) (_ : Group H) (_ : IsFinitelyPresented H) (f : G →* H),
Function.Injective f) ↔ IsRecursivelyPresented GTheorem 4.7.2
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-7-2: there exists a finitely presented group with unsolvable word problem.
universe u
namespace Group
theorem exists_finitelyPresented_not_hasSolvableWordProblem :
∃ (H : Type u) (_ : Group H),
IsFinitelyPresented H ∧ ¬ HasSolvableWordProblem HTheorem 4.7.3
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-7-3: there exists a finitely presented group containing an embedded copy of every recursively presented group.
universe u v
namespace Group
theorem exists_finitelyPresented_group_embedding_all_recursivelyPresented_groups :
∃ (H : Type u) (_ : Group H),
IsFinitelyPresented H ∧
∀ {G : Type v} [Group G], IsRecursivelyPresented G →
∃ (f : G →* H), Function.Injective fDefinition 4.7.5
Lean contributors (project-level attribution): Zichen Wang.
Definition 4-7-5: a subset S ⊆ ℤⁿ is Diophantine when some integer polynomial enumerates S.
universe u
namespace Set
def IsDiophantine {n : ℕ} (S : Set (Fin n → ℤ)) : Prop :=
∃ m : ℕ, ∃ p : MvPolynomial (Fin n ⊕ Fin m) ℤ,
∀ s : Fin n → ℤ, s ∈ S ↔ ∃ y : Fin m → ℤ, p.eval (Sum.elim s y) = 0Theorem 4.7.7
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-7-7: there exists a recursively enumerable non-recursive set of positive integers. In the canonical owner language, this is an r.e. but noncomputable subset of ℕ+.
open Nat.Partrec (Code)
theorem exists_recursivelyEnumerable_not_recursive_set_positiveIntegers :
∃ S : Set ℕ+, REPred (· ∈ S) ∧ ¬ ComputablePred (· ∈ S)Definition 4.7.8
Lean contributors (project-level attribution): Zichen Wang.
Definition 4-7-8: a subgroup H of G is benign in G if the HNN extension G_H adjoining one stable letter that centralizes H embeds in a finitely presented group.
universe u
variable {G : Type u} [Group G]
namespace Subgroup
def IsBenign (H : Subgroup G) : Prop :=
∃ (K : Type u) (_ : Group K) (_ : Group.IsFinitelyPresented K)
(f : HNNExtension G H H (MulEquiv.refl H) →* K),
Function.Injective f4.8 — Algebraically Closed Groups
Theorem 4.8.1
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-8-1: every countable group can be embedded in a countable algebraically closed group.
universe u v
open scoped Monoid.Coprod
variable {G : Type u} [Group G] {ι : Type v}
variable (C : Type u) [Group C] [Countable C]
theorem countable_group_embeds_in_countable_algebraically_closed_group :
∃ (A : Type u) (_ : Group A) (f : C →* A),
Countable A ∧ IsAlgebraicallyClosedGroup A ∧ Function.Injective fTheorem 4.8.2
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-8-2 (1): every algebraically closed group is simple.
universe u
namespace IsAlgebraicallyClosedGroup
variable {G : Type u} [Group G]
instance isSimpleGroup [IsAlgebraicallyClosedGroup G] : IsSimpleGroup GTheorem 4.8.3
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-8-3: if PresentedGroup R ≃* G presents an algebraically closed group G on generators indexed by ℕ, then the relator set R is not recursive. Equivalently, no algebraically closed group admits an infinite recursive presentation.
universe u
namespace Group
variable (G : Type u) [Group G]
theorem not_isRecursive_of_presentation_of_algebraicallyClosedGroup
(hG : IsAlgebraicallyClosedGroup G) {R : Set (FreeGroup ℕ)} (P : PresentedGroup R ≃* G) :
¬ GroupPresentation.IsRecursive RTheorem 4.8.4
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-8-4: every finitely generated group with solvable word problem embeds in every algebraically closed group. The finite generation in the source statement is derived by hG.fg.
universe u v w
namespace Group
namespace HasSolvableWordProblem
theorem embedsInAllAlgebraicallyClosedGroups {G : Type u} [Group G]
(hG : Group.HasSolvableWordProblem G) :
EmbedsInAllAlgebraicallyClosedGroups GTheorem 4.8.5
Lean contributors (project-level attribution): Zichen Wang.
Theorem 4-8-5: if a finitely generated group embeds in every algebraically closed group, then it has solvable word problem.
universe u
namespace Group
variable {G : Type u} [Group G]
namespace EmbedsInAllAlgebraicallyClosedGroups
-- Proof sketch: this file introduces no new owner abstraction. It records the converse half of
-- the embedding criterion whose forward direction is Theorem `4-8-4`; the companion `↔` theorem
-- below is then just the direct pairing of those two owner-level implications.
theorem hasSolvableWordProblem [FG G] (hG : EmbedsInAllAlgebraicallyClosedGroups G) :
HasSolvableWordProblem G