AFTD Auto-Formalizing Theoretical Domains

triangle_hypergraph_stable_minimum_cover_incompatible_pair

theoremverified

In the existing six-triple linear obstruction, every point is active and can be omitted by a maximum one-triple packing; the triple {0,1,6} is a maximum packing, {1,2,4} is a minimum cover, and its two points 2 and 4 outside the packing do not occur together in any maximum packing.

Statement

theorem triangle_hypergraph_stable_minimum_cover_incompatible_pair :
    ({0,1,6} : Finset (Fin 7)) ∈ triangle_hypergraph_obstruction ∧
    (∀ x : Fin 7, ∃ t ∈ triangle_hypergraph_obstruction, x ∈ t) ∧
    (∀ x : Fin 7, ∃ t ∈ triangle_hypergraph_obstruction, x ∉ t) ∧
    (∀ t ∈ triangle_hypergraph_obstruction,
      ¬ Disjoint ({1,2,4} : Finset (Fin 7)) t) ∧
    (2 : Fin 7) ∉ ({0,1,6} : Finset (Fin 7)) ∧
    (4 : Fin 7) ∉ ({0,1,6} : Finset (Fin 7)) ∧
    (∀ t ∈ triangle_hypergraph_obstruction, ¬ ((2 : Fin 7) ∈ t ∧ (4 : Fin 7) ∈ t))
Source
Experiment 16046 and the existing certified six-triple obstruction.
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

The theorem asserts seven concrete properties of `triangle_hypergraph_obstruction` on the vertex set `Fin 7`: the triple {0, 1, 6} is an edge; every vertex appears in at least one edge; every vertex is absent from at least one edge; {1, 2, 4} intersects every edge; neither 2 nor 4 belongs to {0, 1, 6}; and no edge contains both 2 and 4. Because all sets and quantifiers are finite, the entire conjunction is decidable and verified by exhaustive computation.

  1. The seven structural properties hold for `triangle_hypergraph_obstruction`: {0, 1, 6} is an edge, every vertex is active and omitted by some edge, {1, 2, 4} intersects every edge, 2 and 4 are outside {0, 1, 6}, and 2 and 4 do not co-occur in any edge. automation

    Since the vertex set `Fin 7` has only 7 elements and `triangle_hypergraph_obstruction` is an explicitly enumerated collection of 6 triples, each quantifier and set-theoretic condition is decidable. The `decide` tactic computes the truth value of the conjunction by exhaustive evaluation of all cases.

    line 10

      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

theorem triangle_hypergraph_stable_minimum_cover_incompatible_pair :    ({0,1,6} : Finset (Fin 7)) ∈ triangle_hypergraph_obstruction ∧    (∀ x : Fin 7, ∃ t ∈ triangle_hypergraph_obstruction, x ∈ t) ∧    (∀ x : Fin 7, ∃ t ∈ triangle_hypergraph_obstruction, x ∉ t) ∧    (∀ t ∈ triangle_hypergraph_obstruction,      ¬ Disjoint ({1,2,4} : Finset (Fin 7)) t) ∧    (2 : Fin 7) ∉ ({0,1,6} : Finset (Fin 7)) ∧    (4 : Fin 7) ∉ ({0,1,6} : Finset (Fin 7)) ∧    (∀ t ∈ triangle_hypergraph_obstruction, ¬ ((2 : Fin 7) ∈ t ∧ (4 : Fin 7) ∈ t)) := by  decide
See it in the graphDiscuss this resultChallenge it