AFTD Auto-Formalizing Theoretical Domains

orientation_perfect_matching_sign_two

theoremverified

In the complete graph on Fin 2, the perfect matching consisting of its single edge, oriented from 0 to 1, has sign 1.

Statement

theorem orientation_perfect_matching_sign_two :
    orientation_perfect_matching_sign (G := (⊤ : SimpleGraph (Fin 2)))
      ⟨fun u v => u = 0 ∧ v = 1⟩ (⊤ : (⊤ : SimpleGraph (Fin 2)).Subgraph) = 1
Source
arXiv:2611.00468 (The symbolic pfaffian method I), sanity check of the sign of a perfect matching
Verified
07 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • orientation_perfect_matching_signFor n : ℕ, a simple graph G : SimpleGraph (Fin n) (implicit), a digraph D : Digraph (Fin n) and a subgraph M : G.Subgraph, the integer…

The proof, explained

By definition, the sign of an oriented perfect matching is the sign of a permutation that pairs vertices into matching edges compatible with the digraph orientation, or 0 if no such permutation exists. The proof first shows that such a permutation exists by testing the identity permutation on Fin 2, which reduces the sign to that of the classically chosen witness. Because the single edge is oriented from 0 to 1, any valid permutation must fix both 0 and 1, forcing the chosen witness to be the identity permutation, whose sign is 1.

  1. There exists a permutation of Fin 2 whose pairs (2j, 2j + 1) are edges of the matching oriented from 0 to 1.

    We witness the existential by the identity permutation. For j ∈ ℕ, the bound 2j + 1 < 2 implies j = 0 by linear arithmetic. For j = 0, the identity pairs 0 with 1, which is an edge in the complete graph on two vertices and matches the prescribed directed orientation 0 → 1.

    lines 4–10

      have hex : ∃ π : Equiv.Perm (Fin 2), ∀ (j : ℕ) (hj : 2 * j + 1 < 2),
          (⊤ : (⊤ : SimpleGraph (Fin 2)).Subgraph).Adj (π ⟨2 * j, by omega⟩) (π ⟨2 * j + 1, hj⟩) ∧
          (⟨fun u v => u = 0 ∧ v = 1⟩ : Digraph (Fin 2)).Adj (π ⟨2 * j, by omega⟩) (π ⟨2 * j + 1, hj⟩) := by
        refine ⟨1, fun j hj => ?_⟩
        have : j = 0 := by omega
        subst this
        simp
  2. The expression for the sign reduces to the sign of the classically chosen witness.

    Unfolding `orientation_perfect_matching_sign`, the definition branches on whether an admissible permutation exists. Rewriting with `dif_pos` using the existence hypothesis `hex` selects the positive branch, reducing the goal to showing that the sign of `hex.choose` is 1.

    lines 11–12

    uses dif_pos

      unfold orientation_perfect_matching_sign
      rw [dif_pos hex]
  3. The classically chosen permutation `hex.choose` is the identity permutation.

    Specializing the specification of `hex.choose` at the only index j = 0, the chosen permutation π must satisfy the directed adjacency condition, which explicitly states π(0) = 0 and π(1) = 1. By function extensionality on Fin 2 and case analysis on i ∈ {0, 1}, any permutation fixing both 0 and 1 is the identity permutation.

    lines 13–19

    uses congrArg, Fin.val

      have hspec := hex.choose_spec 0 (by norm_num)
      have h1 : hex.choose = 1 := by
        obtain ⟨_, h0, h1⟩ := hspec
        ext i
        fin_cases i
        · simpa using congrArg Fin.val h0
        · simpa using congrArg Fin.val h1
  4. The sign of `hex.choose` is 1, concluding the proof.

    Substituting `hex.choose = 1`, simplification computes the sign of the identity permutation to be 1.

    line 20

      rw [h1]; simp
dif_pos
A dependent if-then-else evaluates to its `then` branch when the condition is proven true.
congrArg
Equality is preserved under function application: if a₁ = a₂, then f(a₁) = f(a₂).
Fin.val
The projection embedding an element of Fin n to its underlying natural number in {0, ..., n - 1}.

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

theorem orientation_perfect_matching_sign_two :    orientation_perfect_matching_sign (G := (⊤ : SimpleGraph (Fin 2)))      ⟨fun u v => u = 0 ∧ v = 1⟩ (⊤ : (⊤ : SimpleGraph (Fin 2)).Subgraph) = 1 := by  have hex : ∃ π : Equiv.Perm (Fin 2), ∀ (j : ℕ) (hj : 2 * j + 1 < 2),      (⊤ : (⊤ : SimpleGraph (Fin 2)).Subgraph).Adj (π ⟨2 * j, by omega⟩) (π ⟨2 * j + 1, hj⟩) ∧      (⟨fun u v => u = 0 ∧ v = 1⟩ : Digraph (Fin 2)).Adj (π ⟨2 * j, by omega⟩) (π ⟨2 * j + 1, hj⟩) := by    refine ⟨1, fun j hj => ?_⟩    have : j = 0 := by omega    subst this    simp  unfold orientation_perfect_matching_sign  rw [dif_pos hex]  have hspec := hex.choose_spec 0 (by norm_num)  have h1 : hex.choose = 1 := by    obtain ⟨_, h0, h1⟩ := hspec    ext i    fin_cases i    · simpa using congrArg Fin.val h0    · simpa using congrArg Fin.val h1  rw [h1]; simp
See it in the graphDiscuss this resultChallenge it