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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.coprodCongr

Definition 4.1.4

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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) : False

Theorem 4.1.13

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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_decomposition

4.2 — Higman-Neumann-Neumann Extensions and Free Products with Amalgamation

Definition 4.2.1

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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 φ ≠ 1

Definition 4.2.3

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 = 1

Lemma 4.2.6

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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.fst

Theorem 4.2.7

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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) x

Theorem 4.2.8

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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.length

Definition 4.2.9

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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 w

Theorem 4.2.10

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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) x

Theorem 4.2.12

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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 a

4.3 — Some Embedding Theorems

Theorem 4.3.1

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 y

Definition 4.3.4

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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 f

Theorem 4.3.6

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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 ≤ 6

Theorem 4.3.7

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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 R

4.4 — Some Decision Problems

Definition 4.4.1

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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 f

Theorem 4.4.2

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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 P

Lemma 4.4.3

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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 v

Definition 4.4.5

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

Theorem 4.4.8

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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 G

Theorem 4.4.9

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 Group

Remark 4.4.12

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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 Group

Theorem 4.4.13

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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 G

4.5 — One-Relator Groups

Theorem 4.5.1

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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_properPower

Theorem 4.5.3

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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_generatorImageSubgroup

Definition 4.5.4

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 ≤ N

Lemma 4.6.2

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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 W

Lemma 4.6.3

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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.

Source header · Attribution source

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 K

Lemma 4.6.8

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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 • K

Theorem 4.6.9

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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 G

Theorem 4.7.2

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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 H

Theorem 4.7.3

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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 f

Definition 4.7.5

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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) = 0

Theorem 4.7.7

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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.

Source header · Attribution source

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 f

4.8 — Algebraically Closed Groups

Theorem 4.8.1

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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 f

Theorem 4.8.2

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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 G

Theorem 4.8.3

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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 R

Theorem 4.8.4

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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 G

Theorem 4.8.5

Lean contributors (project-level attribution): Zichen Wang.

Source header · Attribution source

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