AFTD Auto-Formalizing Theoretical Domains

rearrangement_operator_apply

theoremverified

Under the source-index convention, the entry at index $i$ of the rearranged array $\widehat{P}(A)$ equals $A(P(i))$ for any permutation $P$, array $A$, and index $i$.

Statement

theorem rearrangement_operator_apply {m : ℕ} (P : Equiv.Perm (Fin m)) (A : Arr m) (i : Fin m) :
    rearrangement_operator P A i = A (P i)
Source
arXiv:2611.05397, Section 2.2, Definition 2: Ranking and Unranking Permutations in Heap's Order
Verified
09 Nov 2026
Axioms
Quot.sound
Built on 2
  • ArrThe set of arrangement arrays of order $m$ is represented as the type of functions from $\mathrm{Fin}\,m$ to $\mathrm{Fin}\,m$.
  • rearrangement_operatorFor a permutation $P \in \mathrm{Equiv.Perm}(\mathrm{Fin}\,m)$, the rearrangement operator $\widehat{P}$ acts on an array…
Used by 1
  • rearrangement_operator_comp_applyFor any array $A$ of order $m$, index $i \in \mathrm{Fin}\,m$, and permutations $P, Q \in \mathrm{Equiv.Perm}(\mathrm{Fin}\,m)$, applying…

Read back from the Lean

For any natural number $m$, any permutation $P$ of $\mathrm{Fin}(m)$, any array (function) $A : \mathrm{Fin}(m) \to \mathrm{Fin}(m)$, and any index $i \in \mathrm{Fin}(m)$, the result of applying the rearrangement operator with permutation $P$ to array $A$ at index $i$ equals $A(P(i))$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The rearrangement operator $\\widehat{P}(A)$ is defined directly as the function composition $A \\circ P$. Evaluating this composite function at an index $i$ yields $(A \\circ P)(i) = A(P(i))$ by definition, so the statement holds by reflexivity.

  1. $(\\widehat{P}(A))(i) = A(P(i))$

    By definition, the rearrangement operator $\\widehat{P}(A)$ is the composite function $A \\circ P$. Evaluating $(A \\circ P)$ at index $i$ gives $A(P(i))$. Because both sides of the equality are definitionally identical, the goal is closed immediately by reflexivity (`rfl`).

    line 3

        rearrangement_operator P A i = A (P i) := by rfl

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

/-- Pointwise evaluation of the rearrangement operator under the source-index convention. -/theorem rearrangement_operator_apply {m : ℕ} (P : Equiv.Perm (Fin m)) (A : Arr m) (i : Fin m) :    rearrangement_operator P A i = A (P i) := by rfl
See it in the graphDiscuss this resultChallenge it