coordinate_orbit_invariant_orderhom_iso
For a subgroup of coordinate permutations of the n-fold product of the finite chain Fin m and a partially ordered set T, the pointwise ordered invariant monotone maps into T are order-isomorphic to the monotone maps from the orbit quotient with the representative-comparison preorder into T.
Statement
theorem coordinate_orbit_invariant_orderhom_iso (n m : ℕ) (G : Subgroup (Equiv.Perm (Fin n))) (T : Type*) [PartialOrder T] : letI : MulAction G (Fin n → Fin m) := coord_perm_mul_action G; letI : Preorder (MulAction.orbitRel.Quotient G (Fin n → Fin m)) := quotient_poset_preorder n (Fin m) G; Nonempty ({f : (Fin n → Fin m) →o T // ∀ (g : G) (x : Fin n → Fin m), f (g • x) = f x} ≃o (MulAction.orbitRel.Quotient G (Fin n → Fin m) →o T))
- Source
- arXiv:2611.13887, Lemma 8
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- coord_perm_mul_actionA subgroup of the symmetric group on n elements acts on functions from Fin n to any type by permuting coordinates: (g • x) i = x (g⁻¹ i).
- quotient_poset_preorderThe preorder on the quotient poset of orbits of P^n under a subgroup G of S_n acting by coordinate permutations, where orbit Gx is less…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 1
- pgroup_coordinate_orbit_orderhom_card_modLet p be prime, G a p-subgroup of the permutations of Fin n acting by coordinate permutations on the n-fold product of the finite chain…
The proof, explained
The proof constructs an explicit order isomorphism between G-invariant monotone maps from Fin n → Fin m to T and monotone maps from the orbit quotient to T. In the forward direction, an invariant monotone map descends to the quotient via Quotient.lift, preserving monotonicity because the quotient preorder is defined by the existence of comparable orbit representatives. In the reverse direction, pulling back a monotone map on the quotient along the canonical projection yields an invariant monotone map because the projection is monotone and constant on orbits. Finally, the two constructions are shown to be mutually inverse and order-reflecting by quotient induction.
We equip the coordinate functions with the permutation action of G, the orbit quotient with its induced preorder, and define the orbit equivalence relation R.
The proof sets up the local context by defining the coordinate permutation action of G on functions Fin n → Fin m and setting the preorder on the orbit quotient where [x] ≤ [y] if there are representatives with x' ≤ y'. The orbit equivalence relation is denoted by R.
letI : MulAction G (Fin n → Fin m) := coord_perm_mul_action G letI : Preorder (MulAction.orbitRel.Quotient G (Fin n → Fin m)) := quotient_poset_preorder n (Fin m) G let R := MulAction.orbitRel G (Fin n → Fin m)The canonical projection to the quotient is order-preserving.
For any x and y with x ≤ y, their equivalence classes satisfy [x] ≤ [y] under the quotient preorder directly by taking x and y themselves as the required representatives.
have hmk : ∀ x y : Fin n → Fin m, x ≤ y → @LE.le (MulAction.orbitRel.Quotient G (Fin n → Fin m)) (quotient_poset_preorder n (Fin m) G).toLE (Quotient.mk R x) (Quotient.mk R y) := fun x y h => ⟨x, y, rfl, rfl, h⟩
Every G-invariant monotone map f descends to a well-defined monotone map toQ(f) on the orbit quotient.
Because f is invariant under the action of G, it takes identical values on any orbit, so Quotient.lift produces a well-defined function on equivalence classes. If [a] ≤ [b] in the quotient preorder, there exist representatives x ∈ [a] and y ∈ [b] with x ≤ y; applying the monotonicity of f yields f(x) ≤ f(y), establishing that toQ(f) is monotone.
uses
Quotient.liftlet toQ : {f : (Fin n → Fin m) →o T // ∀ (g : G) (x : Fin n → Fin m), f (g • x) = f x} → (MulAction.orbitRel.Quotient G (Fin n → Fin m) →o T) := fun f => { toFun := Quotient.lift f.1 (by rintro a b ⟨g, rfl⟩ exact f.2 g b) monotone' := by rintro a b ⟨x, y, rfl, rfl, hxy⟩ exact f.1.monotone hxy }
Every monotone map F on the orbit quotient pulls back to a G-invariant monotone map ofQ(F).
The pullback map sends x to F([x]). It is monotone because composing the order-preserving quotient projection with the monotone map F preserves order. Furthermore, for any g ∈ G, g • x and x lie in the same orbit, so Quotient.sound shows [g • x] = [x], meaning F([g • x]) = F([x]), which establishes G-invariance.
uses
Quotient.soundlet ofQ : (MulAction.orbitRel.Quotient G (Fin n → Fin m) →o T) → {f : (Fin n → Fin m) →o T // ∀ (g : G) (x : Fin n → Fin m), f (g • x) = f x} := fun F => ⟨{ toFun := fun x => F (Quotient.mk R x) monotone' := fun x y h => F.monotone (hmk x y h) }, fun g x => by show F (Quotient.mk R (g • x)) = F (Quotient.mk R x) congr 1 exact Quotient.sound ⟨g, rfl⟩⟩
To obtain the order isomorphism, it suffices to verify that toQ and ofQ are mutual inverses and preserve the order relation.
We package toQ and ofQ as the forward and inverse maps of an order isomorphism, leaving three verification obligations: left inverse, right inverse, and reflection of the order.
refine ⟨{ toFun := toQ, invFun := ofQ, left_inv := ?_, right_inv := ?_, map_rel_iff' := ?_ }⟩The map ofQ is a left inverse to toQ: ofQ(toQ(f)) = f.
For any invariant monotone map f and element x, (ofQ(toQ(f)))(x) is by definition toQ(f)([x]) = f(x), so the equality holds definitionally.
· intro f rfl
The map ofQ is a right inverse to toQ: toQ(ofQ(F)) = F.
By function extensionality, it suffices to evaluate at an arbitrary quotient element a. Applying Quotient.inductionOn, we write a as [x] for some x. Then (toQ(ofQ(F)))([x]) evaluates definitionally to ofQ(F)(x) = F([x]), concluding the proof.
uses
Quotient.inductionOn· intro F ext a induction a using Quotient.inductionOn with | h x => rfl
The map toQ is an order reflection: toQ(f) ≤ toQ(g) if and only if f ≤ g.
For the forward direction, assuming toQ(f) ≤ toQ(g), evaluating at the class [x] of any element x immediately gives f(x) ≤ g(x). For the reverse direction, assuming f ≤ g, evaluating at any quotient element a by quotient induction via Quotient.inductionOn writes a = [x], where toQ(f)([x]) = f(x) ≤ g(x) = toQ(g)([x]).
uses
Quotient.inductionOn· intro f g constructor · intro h x exact h (Quotient.mk R x) · intro h a induction a using Quotient.inductionOn with | h x => exact h x
Quotient.lift- Descends a function defined on representatives to the quotient type, provided the function takes equal values on equivalent elements.
Quotient.sound- Elements related by the equivalence relation have equal equivalence classes in the quotient type.
Quotient.inductionOn- To prove a property for all elements of a quotient, it suffices to prove it for all equivalence classes of representatives.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open scoped Classicaltheorem coordinate_orbit_invariant_orderhom_iso (n m : ℕ) (G : Subgroup (Equiv.Perm (Fin n))) (T : Type*) [PartialOrder T] : letI : MulAction G (Fin n → Fin m) := coord_perm_mul_action G; letI : Preorder (MulAction.orbitRel.Quotient G (Fin n → Fin m)) := quotient_poset_preorder n (Fin m) G; Nonempty ({f : (Fin n → Fin m) →o T // ∀ (g : G) (x : Fin n → Fin m), f (g • x) = f x} ≃o (MulAction.orbitRel.Quotient G (Fin n → Fin m) →o T)) := by letI : MulAction G (Fin n → Fin m) := coord_perm_mul_action G letI : Preorder (MulAction.orbitRel.Quotient G (Fin n → Fin m)) := quotient_poset_preorder n (Fin m) G let R := MulAction.orbitRel G (Fin n → Fin m) have hmk : ∀ x y : Fin n → Fin m, x ≤ y → @LE.le (MulAction.orbitRel.Quotient G (Fin n → Fin m)) (quotient_poset_preorder n (Fin m) G).toLE (Quotient.mk R x) (Quotient.mk R y) := fun x y h => ⟨x, y, rfl, rfl, h⟩ let toQ : {f : (Fin n → Fin m) →o T // ∀ (g : G) (x : Fin n → Fin m), f (g • x) = f x} → (MulAction.orbitRel.Quotient G (Fin n → Fin m) →o T) := fun f => { toFun := Quotient.lift f.1 (by rintro a b ⟨g, rfl⟩ exact f.2 g b) monotone' := by rintro a b ⟨x, y, rfl, rfl, hxy⟩ exact f.1.monotone hxy } let ofQ : (MulAction.orbitRel.Quotient G (Fin n → Fin m) →o T) → {f : (Fin n → Fin m) →o T // ∀ (g : G) (x : Fin n → Fin m), f (g • x) = f x} := fun F => ⟨{ toFun := fun x => F (Quotient.mk R x) monotone' := fun x y h => F.monotone (hmk x y h) }, fun g x => by show F (Quotient.mk R (g • x)) = F (Quotient.mk R x) congr 1 exact Quotient.sound ⟨g, rfl⟩⟩ refine ⟨{ toFun := toQ, invFun := ofQ, left_inv := ?_, right_inv := ?_, map_rel_iff' := ?_ }⟩ · intro f rfl · intro F ext a induction a using Quotient.inductionOn with | h x => rfl · intro f g constructor · intro h x exact h (Quotient.mk R x) · intro h a induction a using Quotient.inductionOn with | h x => exact h x