The ping-pong lemma
ProvedFamousTheorems.ping_pong_lemmaThe ping-pong lemma. Let a group act on a set , and let be groups with homomorphisms , where has at least two elements. Suppose there are nonempty, pairwise disjoint subsets such that for all and all with , . Assume also that has at least three elements or some has at least three elements. Then the induced homomorphism from the free product to is injective.
The lemma, due to Klein, is the standard method for proving that given group elements generate a free group or a free product. It is used in the Tits alternative and to show that and generate a free subgroup of .
Formalization note. Mathlib's Monoid.CoprodI.lift_injective_of_ping_pong. The free product is Monoid.CoprodI H and Monoid.CoprodI.lift f is the homomorphism induced by the . The cardinality conditions are stated with Cardinal.mk.
import Mathlib
namespace FamousTheorems
open Pointwise
theorem ping_pong_lemma {ι G : Type*} [Group G] {H : ι → Type*} [∀ i, Group (H i)] (f : ∀ i, H i →* G)
(hcard : 3 ≤ Cardinal.mk ι ∨ ∃ i, 3 ≤ Cardinal.mk (H i)) {α : Type*} [MulAction G α] (X : ι → Set α)
(hXne : ∀ i, (X i).Nonempty) (hXdisj : Pairwise (Function.onFun Disjoint X))
(hpp : Pairwise fun i j => ∀ h : H i, h ≠ 1 → f i h • X j ⊆ X i) [Nontrivial ι] :
Function.Injective (Monoid.CoprodI.lift f) := by sorry
end FamousTheorems