AFTD Auto-Formalizing Theoretical Domains

prefixReversal_involutive

theoremverified

Applying a prefix reversal of length k twice in Equiv.Perm (Fin n) yields the identity permutation.

Statement

theorem prefixReversal_involutive (n k : ℕ) :
    prefixReversal n k * prefixReversal n k = 1
Source
arXiv:2610.30892 Section 1
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • prefixReversalFor integers n and k, prefixReversal n k is the permutation in the symmetric group Equiv.Perm (Fin n) that reverses the first k elements…

Read back from the Lean

For all natural numbers $n$ and $k$, the permutation prefixReversal n k of Fin n composed with itself is equal to the identity permutation $1$ on Fin n (that is, prefixReversal n k is an involution).

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

A prefix reversal is defined as a permutation whose forward and inverse maps are identical. Consequently, its `left_inv` field proves that applying the operation twice restores any input, and extensionality of equivalences (`Equiv.ext`) immediately lifts this pointwise involution to equality with the identity permutation in the symmetric group.

  1. Applying the prefix reversal twice equals the identity permutation: $\text{prefixReversal}(n, k) * \text{prefixReversal}(n, k) = 1$.

    By extensionality for equivalences (`Equiv.ext`), two permutations are equal if they agree on every element. Because the definition of `prefixReversal` uses the exact same function for both its forward map and inverse map, its built-in `left_inv` field already proves that applying the permutation twice pointwise yields the original element, matching the pointwise action of the identity permutation $1$.

    line 3

    uses Equiv.ext

        prefixReversal n k * prefixReversal n k = 1 := Equiv.ext (prefixReversal n k).left_inv
Equiv.ext
Two equivalences (or permutations) are equal if and only if they agree on every input element.

Written by a model (gemini-3.8-flash) from the Lean source alone (no goal states were available). Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

/-- Every prefix reversal permutation is an involution. -/theorem prefixReversal_involutive (n k : ℕ) :    prefixReversal n k * prefixReversal n k = 1 := Equiv.ext (prefixReversal n k).left_inv
See it in the graphDiscuss this resultChallenge it