AFTD Auto-Formalizing Theoretical Domains

coordinate_orbit_invariant_orderhom_iso

theoremverified

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 1

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.

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

    lines 4–6

      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)
  2. 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.

    lines 7–10

      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⟩
  3. 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.

    lines 11–18

    uses Quotient.lift

      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 }
  4. 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.

    lines 19–26

    uses Quotient.sound

      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⟩⟩
  5. 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.

    line 27

      refine ⟨{ toFun := toQ, invFun := ofQ, left_inv := ?_, right_inv := ?_, map_rel_iff' := ?_ }⟩
  6. 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.

    lines 28–29

      · intro f
        rfl
  7. 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.

    lines 30–33

    uses Quotient.inductionOn

      · intro F
        ext a
        induction a using Quotient.inductionOn with
        | h x => rfl
  8. 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]).

    lines 34–40

    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

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
See it in the graphDiscuss this resultChallenge it