AFTD Auto-Formalizing Theoretical Domains

digraph_cyclic_seven_prescribed_neighborhood_counterexample

theoremverified

The displayed eight-vertex graph contains the cyclic seven-tournament, but no quasi-kernel covers the closed out-neighborhood of vertex 0 within that tournament.

Statement

theorem digraph_cyclic_seven_prescribed_neighborhood_counterexample :
    (∀ v, v ∉ in541_forced_parent_out v) ∧
    (∀ u v : Fin 8, u.val < 7 → v.val < 7 →
      (v ∈ in541_forced_parent_out u ↔
        (v.val + 7 - u.val) % 7 ∈ ({1,2,4} : Finset ℕ))) ∧
    (∀ Q : Finset (Fin 8), in541_forced_parent_qk Q →
      ¬ (∀ v ∈ ({0,1,2,4} : Finset (Fin 8)),
        ∃ q ∈ Q, q = v ∨ v ∈ in541_forced_parent_out q))
Source
Explicit finite counterexample discovered and audited in the cited computations; no novelty is claimed.
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

The proof, explained

The theorem is proved by finite exhaustive computation using the `decide` tactic. First, the property of being a quasi-kernel is shown to be decidable by expanding its definition into finite quantifications over `Fin 8`. Then, Lean mechanically evaluates the claim across the entire finite graph, checking looplessness, agreement on the first seven vertices with the cyclic tournament $T_7$, and non-coverage of $\{0, 1, 2, 4\}$ by all 256 candidate quasi-kernels.

  1. The property of being a quasi-kernel is decidable for any subset of vertices.

    Expanding the definition of `in541_forced_parent_qk` expresses the quasi-kernel property in terms of first-order conditions with bounded universal and existential quantifiers over the finite vertex set `Fin 8` and finite sets of vertices. Since equality, membership, and bounded quantifiers over finite types are decidable, typeclass resolution (`infer_instance`) automatically synthesizes a `Decidable` instance for this proposition.

    lines 16–17

      unfold in541_forced_parent_qk
      infer_instance
  2. The 8-vertex digraph is loopless, agrees with the cyclic 7-tournament on vertices 0 through 6, and has no quasi-kernel that dominates the closed out-neighborhood of vertex 0. automation

    Because all vertex domains and power sets are finite, the entire proposition is decidable. The `decide` tactic checks every condition by exhaustive evaluation: it verifies the lack of self-loops for each of the 8 vertices, checks all pairs among the first 7 vertices to confirm that edge directions match quadratic residues modulo 7 ({1, 2, 4}), and iterates over all 256 subsets of Fin 8, checking that any subset that is a quasi-kernel fails to 1-step dominate {0, 1, 2, 4}.

    line 27

      decide

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

set_option maxRecDepth 50000set_option maxHeartbeats 50000000def in541_forced_parent_out (v : Fin 8) : Finset (Fin 8) :=  if v = 0 then {1,2,4} else if v = 1 then {2,3,5} else  if v = 2 then {3,4,6} else if v = 3 then {0,4,5} else  if v = 4 then {1,5,6} else if v = 5 then {0,2,6} else  if v = 6 then {0,1,3} else {0}def in541_forced_parent_qk (Q : Finset (Fin 8)) : Prop :=  (∀ u ∈ Q, ∀ v ∈ Q, u ≠ v → v ∉ in541_forced_parent_out u) ∧  (∀ v, ∃ u ∈ Q, u = v ∨ v ∈ in541_forced_parent_out u ∨    ∃ w, w ∈ in541_forced_parent_out u ∧ v ∈ in541_forced_parent_out w)instance (Q : Finset (Fin 8)) : Decidable (in541_forced_parent_qk Q) := by  unfold in541_forced_parent_qk  infer_instancetheorem digraph_cyclic_seven_prescribed_neighborhood_counterexample :    (∀ v, v ∉ in541_forced_parent_out v) ∧    (∀ u v : Fin 8, u.val < 7 → v.val < 7 →      (v ∈ in541_forced_parent_out u ↔        (v.val + 7 - u.val) % 7 ∈ ({1,2,4} : Finset ℕ))) ∧    (∀ Q : Finset (Fin 8), in541_forced_parent_qk Q →      ¬ (∀ v ∈ ({0,1,2,4} : Finset (Fin 8)),        ∃ q ∈ Q, q = v ∨ v ∈ in541_forced_parent_out q)) := by  decide
See it in the graphDiscuss this resultChallenge it