AFTD Auto-Formalizing Theoretical Domains

in715_deficit_p_size

theoremverified

Finite certificate for the explicit fourteen-vertex graph.

Statement

theorem in715_deficit_p_size : In701Deficit14.P.card = 7
Source
Finite graph and certificates from experiments 20940 and 20968; see state/campaigns/triangle_reductions/outside_induced_kernel_in701.md.
Verified
10 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 30

The proof, explained

The theorem asserts that the family of vertex subsets P defined for the 14-vertex graph has cardinality 7. Because P is an explicit finite set of finite sets with decidable equality, the statement is proved by direct computation using Lean's kernel decision procedure (`decide +kernel`). The file also sets up the underlying simple graph on Fin 14, verifying the symmetry of its adjacency relation via Sym2.eq_swap.

  1. The edge membership condition for adjacency is symmetric: if s(u, v) ∈ E, then s(v, u) ∈ E.

    Rewriting with the symmetry of unordered pairs (`Sym2.eq_swap`) transforms s(v, u) into s(u, v), which is immediately discharged by the first conjunct of the adjacency hypothesis h.

    line 8

    uses Sym2.eq_swap

      symm := ⟨fun u v h => ⟨by rw [Sym2.eq_swap]; exact h.1, h.2.symm⟩⟩
  2. The family of subsets P has cardinality 7. automation

    The set P is explicitly defined by enumerating seven 3-element subsets of vertices in Fin 14. Lean's kernel decision procedure (`decide +kernel`) computes the cardinality directly by verifying pairwise distinctness of the elements.

    line 18

    theorem in715_deficit_p_size : In701Deficit14.P.card = 7 := by decide +kernel
Sym2.eq_swap
The unordered pair constructor is symmetric: s(a, b) = s(b, a).

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

open scoped Sym2set_option maxRecDepth 100000set_option maxHeartbeats 30000000namespace In701Deficit14def E : Finset (Sym2 (Fin 14)) := {s(0,1), s(0,4), s(0,5), s(0,6), s(0,7), s(0,8), s(0,9), s(0,10), s(0,11), s(0,12), s(1,2), s(1,5), s(1,6), s(1,7), s(1,8), s(1,9), s(1,10), s(1,11), s(1,13), s(2,3), s(2,5), s(2,6), s(2,7), s(2,8), s(2,9), s(2,10), s(3,4), s(3,5), s(3,6), s(3,7), s(3,8), s(3,10), s(4,5), s(4,6), s(4,7), s(4,8), s(4,9), s(4,10), s(9,11), s(11,12), s(11,13)}def G : SimpleGraph (Fin 14) where  Adj u v := s(u,v) ∈ E ∧ u ≠ v  symm := ⟨fun u v h => ⟨by rw [Sym2.eq_swap]; exact h.1, h.2.symm⟩⟩  loopless := ⟨fun u h => h.2 rfl⟩instance : DecidableRel G.Adj := fun _ _ => inferInstanceAs (Decidable (_ ∈ E ∧ _ ≠ _))def P : Finset (Finset (Fin 14)) := {{0,1,5}, {1,2,6}, {2,3,7}, {3,4,8}, {0,4,9}, {0,11,12}, {1,11,13}}def C : Finset (Sym2 (Fin 14)) := {s(0,1), s(1,2), s(2,3), s(3,4), s(0,4), s(0,11), s(1,11)}def Z : Finset (Finset (Fin 14)) := {{0,1,9}, {1,2,9}, {0,4,9}, {0,9,11}, {1,9,11}}def X : Finset (Finset (Fin 14)) := {{0,1,10}, {1,2,10}, {2,3,10}, {3,4,10}, {0,4,10}}def color (v : Fin 14) : Bool := decide (v ∈ ({0,1,2,3,4,11} : Finset (Fin 14)))end In701Deficit14theorem in715_deficit_p_size : In701Deficit14.P.card = 7 := by decide +kernel
See it in the graphDiscuss this resultChallenge it