AFTD Auto-Formalizing Theoretical Domains

Physlib.Fin.involutionAddEquiv

defimported Lean

Given an involution of Fin n, the optional choice of an element in Fin n which maps to itself is equivalent to the optional choice of an element in Fin (Finset.univ.filter fun i => f.1 i = i).card.

Statement

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Nat in
def Physlib.Fin.involutionAddEquiv {n : ℕ} (f : {f : Fin n → Fin n // Function.Involutive f}) :
    {i : Option (Fin n) // ∀ (h : i.isSome), f.1 (Option.get i h) = (Option.get i h)} ≃
    Option (Fin (Finset.univ.filter fun i => f.1 i = i).card)
Defined in
Physlib, `Physlib.Fin.involutionAddEquiv`
Lean proof
By Joseph Tooby-Smith, from github.com/leanprover-community/physlib at e411c6e89692 (Copyright (c) 2024 Joseph Tooby-Smith. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.34.1.
Verified
09 Oct 2026
Axioms
none listed
Used by 2

Lean source view module on GitHub

set_option autoImplicit true in
set_option relaxedAutoImplicit true in
open Nat in
/-- Given an involution of `Fin n`, the optional choice of an element in `Fin n` which maps to itself is equivalent to the optional choice of an element in `Fin (Finset.univ.filter fun i => f.1 i = i).card`. -/
def Physlib.Fin.involutionAddEquiv {n : ℕ} (f : {f : Fin n → Fin n // Function.Involutive f}) :
    {i : Option (Fin n) // ∀ (h : i.isSome), f.1 (Option.get i h) = (Option.get i h)} ≃
    Option (Fin (Finset.univ.filter fun i => f.1 i = i).card) := by
  let e1 : {i : Option (Fin n) // ∀ (h : i.isSome), f.1 (Option.get i h) = (Option.get i h)}
        ≃ Option {i : Fin n // f.1 i = i} :=
    { toFun := fun i => match i with
        | ⟨some i, h⟩ => some ⟨i, by simpa using h⟩
        | ⟨none, h⟩ => none
      invFun := fun i => match i with
        | some ⟨i, h⟩ => ⟨some i, by simpa using h⟩
        | none => ⟨none, by simp⟩
      left_inv := by
        rintro ⟨_ | i, h⟩ <;> rfl
      right_inv := by
        rintro (_ | ⟨i, h⟩) <;> rfl }
  let s : Finset (Fin n) := Finset.univ.filter fun i => f.1 i = i
  let e2' : { i : Fin n // f.1 i = i} ≃ {i // i ∈ s} := by
    apply Equiv.subtypeEquivProp
    simp [s]
  let e2 : {i // i ∈ s} ≃ Fin (Finset.card s) := by
    refine (Finset.orderIsoOfFin _ ?_).symm.toEquiv
    simp [s]
  refine e1.trans (Equiv.optionCongr (e2'.trans (e2)))
See it in the graphDiscuss this resultChallenge it