orientation_perfect_matching_sign_two
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.
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.
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
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.
uses
dif_posunfold orientation_perfect_matching_sign rw [dif_pos hex]
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.
uses
congrArg,Fin.valhave 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
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.
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}.
- The definition of `orientation_perfect_matching_sign` uses Hilbert's choice operator (`Classical.choose`) to select an arbitrary permutation satisfying the matching conditions. Consequently, rather than simply computing the sign of the identity permutation, the formal proof must establish that the chosen witness itself is the identity.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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