Martin Escardo, July 2026. Given a large, locally small setoid, we show that the free egroup on it is large, in the sense that no egroup whose underlying type and equivalence relation are both small is isomorphic to it. We then give an example, which is what the EGroups development is for, by taking the universe as a setoid under type equivalence. \begin{code} {-# OPTIONS --safe --without-K #-} open import MLTT.Spartan open import MLTT.List renaming (_β·_ to _β’_ ; _++_ to _β¦_) module EGroups.Large where open import UF.Equiv hiding (_β _) open import UF.Size open import Relations.SRTclosure open import Various.LawvereFPT open import EGroups.Setoid open import EGroups.Type open import EGroups.Size module large-free-egroup {π€ : Universe} (A : π€βΊ Μ ) (_β_ : A β A β π€ Μ ) (βr : reflexive _β_) (βs : symmetric _β_) (βt : transitive _β_) where open import EGroups.Reduction A _β_ βr βs βt open import EGroups.Free A _β_ βr βs βt \end{code} We introduce the setoid of generators, together with three lemmas. First, β-related generators are convertible, via a β·-peak. Second, if two generators are β[FA]-related, then their underlying unsigned elements are β-related. Third, a generator witness for s exhibits s as convertible to a single generator. \begin{code} πΈ : Setoid (π€ βΊ) π€ πΈ = A , _β_ , βr , βs , βt Ξ·-βΏ : (a a' : A) β a β a' β Ξ· a βΏ Ξ· a' Ξ·-βΏ a a' e = srt-transitive _β·_ (Ξ· a) w (Ξ· a') (srt-symmetric _β·_ w (Ξ· a) (srt-extension _β·_ w (Ξ· a) I)) (srt-extension _β·_ w (Ξ· a') I') where w : FA w = (β , a) β’ (β , a') β’ (β , a') β’ [] I' : w β· Ξ· a' I' = [] , ((β , a') β’ []) , (β , a) , (β , a') , refl , refl , (refl , βs a a' e) I : w β· Ξ· a I = ((β , a) β’ []) , [] , (β , a') , (β , a') , refl , refl , ( refl , βr a') Ξ·-β[FA]ββ : {a a' : A} β Ξ· a β[FA] Ξ· a' β a β a' Ξ·-β[FA]ββ ((_ , e) , _) = e generatorββΏ : (s : FA) (w : generator s) β s βΏ Ξ· (underlying-generator w) generatorββΏ s (n , Ο , a , p) = rt-gives-srt _β·_ s (Ξ· a) (n , I) where I : iteration _β·_ n s (Ξ· a) I = transport (iteration _β·_ n s) (p β»ΒΉ) (chain-lemmaβ s n Ο) \end{code} We now prove the theorem. If some egroup π whose underlying type and equivalence relation are both small is isomorphic to the free egroup, then πΈ is a small setoid. The map ΞΊ = G β Ξ· into β¨πβ© is both β-respecting and β-reflecting, so πΈ is setoid-isomorphic to the small setoid of generators inside β¨πβ©. \begin{code} small-copy-gives-small-setoid : (π : EGroup π€ π€) β π β free-egroup β is-small-setoid π€ πΈ small-copy-gives-small-setoid π (F , (F-resp , _) , G , (G-resp , _) , FG , GF) = T , iso where ΞΊ : A β β¨ π β© ΞΊ a = G (Ξ· a) ΞΊ-respects : (a a' : A) β a β a' β ΞΊ a ββ¨ π β© ΞΊ a' ΞΊ-respects a a' e = G-resp (Ξ·-βΏ a a' e) ΞΊ-reflects : (a a' : A) β ΞΊ a ββ¨ π β© ΞΊ a' β a β a' ΞΊ-reflects a a' r = Ξ·-β[FA]ββ (Ξ·-identifies-βΏ-related-points a a' (srt-transitive _β·_ (Ξ· a) (F (G (Ξ· a'))) (Ξ· a') (srt-transitive _β·_ (Ξ· a) (F (G (Ξ· a))) (F (G (Ξ· a'))) (srt-symmetric _β·_ (F (G (Ξ· a))) (Ξ· a) (FG (Ξ· a))) (F-resp r)) (FG (Ξ· a')))) abstract is-gen : β¨ π β© β π€ Μ is-gen y = resized (generator (F y)) (generator-is-small (F y)) to-gen : (y : β¨ π β©) β is-gen y β generator (F y) to-gen y = β resizing-condition (generator-is-small (F y)) β from-gen : (y : β¨ π β©) β generator (F y) β is-gen y from-gen y = β resizing-condition (generator-is-small (F y)) ββ»ΒΉ to-from-gen : (y : β¨ π β©) (w : generator (F y)) β to-gen y (from-gen y w) οΌ w to-from-gen y = inverses-are-sections β resizing-condition (generator-is-small (F y)) β (ββ-is-equiv (resizing-condition (generator-is-small (F y)))) β£Tβ£ : π€Μ β£Tβ£ = Ξ£ y κ β¨ π β© , is-gen y _βα΅_ : β£Tβ£ β β£Tβ£ β π€Μ (y , _) βα΅ (y' , _) = y ββ¨ π β© y' T : Setoid π€ π€ T = β£Tβ£ , _βα΅_ , (Ξ» (y , _) β erefl π y) , (Ξ» (y , _) (y' , _) r β esym π y y' r) , (Ξ» (y , _) (y' , _) (y'' , _) r r' β etrans π y y' y'' r r') gen-of : (a : A) β generator (F (ΞΊ a)) gen-of a = βΏβgenerator (srt-symmetric _β·_ (F (G (Ξ· a))) (Ξ· a) (FG (Ξ· a))) to : A β β£Tβ£ to a = ΞΊ a , from-gen (ΞΊ a) (gen-of a) from : β£Tβ£ β A from (y , w) = underlying-generator (to-gen y w) to-resp : is-setoid-map πΈ T to to-resp {a} {a'} e = ΞΊ-respects a a' e from-resp : is-setoid-map T πΈ from from-resp {y , w} {y' , w'} r = Ξ·-β[FA]ββ (Ξ·-identifies-βΏ-related-points (from (y , w)) (from (y' , w')) (srt-transitive _β·_ (Ξ· (from (y , w))) (F y') (Ξ· (from (y' , w'))) (srt-transitive _β·_ (Ξ· (from (y , w))) (F y) (F y') (srt-symmetric _β·_ (F y) (Ξ· (from (y , w))) (generatorββΏ (F y) (to-gen y w))) (F-resp r)) (generatorββΏ (F y') (to-gen y' w')))) to-from : (t : β£Tβ£) β to (from t) βα΅ t to-from (y , w) = etrans π (ΞΊ aβ) (G (F y)) y (esym π (G (F y)) (ΞΊ aβ) (G-resp (generatorββΏ (F y) (to-gen y w)))) (GF y) where aβ : A aβ = underlying-generator (to-gen y w) from-to : (a : A) β from (to a) β a from-to a = transport (Ξ» z β z β a) (ap (underlying-generator {F (ΞΊ a)}) ((to-from-gen (ΞΊ a) (gen-of a)) β»ΒΉ)) (underlying-generator-βΏβgenerator (srt-symmetric _β·_ (F (G (Ξ· a))) (Ξ· a) (FG (Ξ· a)))) iso : πΈ β Λ’ T iso = record { to = to ; from = from ; to-resp = to-resp ; from-resp = from-resp ; to-from = to-from ; from-to = from-to } \end{code} Taking the contrapositive, if πΈ is a large setoid then the free egroup on πΈ, which lives in the next universe, has no small copy. \begin{code} large-setoid-gives-large-egroup : is-large-setoid π€ πΈ β (π : EGroup π€ π€) β Β¬ (π β free-egroup) large-setoid-gives-large-egroup πΈ-large π iso = πΈ-large (small-copy-gives-small-setoid π iso) there-is-a-large-egroup : is-large-setoid π€ πΈ β Ξ£ π κ EGroup (π€βΊ) (π€ βΊ) , ((π : EGroup π€ π€) β Β¬ (π β π)) there-is-a-large-egroup πΈ-large = free-egroup , large-setoid-gives-large-egroup πΈ-large \end{code} An example of a large egroup, which is what the EGroups development is for. We instantiate the above with the universe π€, taken as a setoid under type equivalence _β_. This gives an egroup in the next universe π€βΊ that is isomorphic to no egroup in the universe π€, in a Spartan MLTT with no HoTT/UF assumptions. \begin{code} module _ (π€ : Universe) where open large-free-egroup (π€ Μ ) _β_ β-refl (Ξ» X Y β β-sym) (Ξ» X Y Z β _β_) renaming (πΈ to π) \end{code} The universe setoid π = (π€ Μ , _β_) is large. \begin{code} universe-setoid-is-large : is-large-setoid π€ π universe-setoid-is-large (T , iso) = generalized-Coquand.Lemmaβ β£ T β£ (_β Λ’_.from iso) (_β Λ’_.to iso) (_β Λ’_.from-to iso) \end{code} Therefore the free egroup on the universe setoid, which lives in the next universe, is isomorphic to no egroup whose underlying type and equivalence relation are both small. \begin{code} large-egroup-in-the-next-universe : Ξ£ π κ EGroup (π€ βΊ) (π€ βΊ) , ((π : EGroup π€ π€) β Β¬ (π β π)) large-egroup-in-the-next-universe = there-is-a-large-egroup universe-setoid-is-large \end{code}