in715_deficit_p_disj
Finite certificate for the explicit fourteen-vertex graph.
Statement
theorem in715_deficit_p_disj : (P : Set (Finset (Fin 14))).Pairwise (fun a b => (a ∩ b).card ≤ 1)
- 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
- in715_deficit_p_sizeFinite certificate for the explicit fourteen-vertex graph.
- Used by 2
- in715_deficit_preciseAn explicit fourteen-vertex graph has a maximum seven-triangle packing, a seven-edge triangle cover, an outside five-cycle link and a…
- in715_deficit_pack_eqFinite certificate for the explicit fourteen-vertex graph.
The proof, explained
The theorem establishes that any two distinct sets in the family P of seven 3-element subsets of {0, ..., 13} have at most one element in common. The proof proceeds by exhaustive finite verification: after introducing two arbitrary distinct members of P, their membership is expanded into seven-way disjunctions, yielding 49 pairs of sets. The 7 diagonal cases where the sets coincide are ruled out by the distinctness assumption, while the 42 off-diagonal cases are verified by kernel evaluation of the set intersections.
Arbitrary distinct elements a, b ∈ P are introduced, and their membership is unpacked into explicit disjunctions over the seven triples defining P.
By definition of `Pairwise`, we introduce distinct elements a, b ∈ P under the assumption a ≠ b. Unfolding the definition of P and simplifying membership in finite set insertions rewrites both a ∈ P and b ∈ P into seven-fold disjunctions stating that the set is one of {0, 1, 5}, {1, 2, 6}, {2, 3, 7}, {3, 4, 8}, {0, 4, 9}, {0, 11, 12}, or {1, 11, 13}.
uses
Finset.mem_coe,P,Finset.mem_insert,Finset.mem_singletonintro a ha b hb hab simp only [Finset.mem_coe, P, Finset.mem_insert, Finset.mem_singleton] at ha hb
The goal is divided into 49 cases corresponding to all pairs of triples (a, b) ∈ P × P.
We perform exhaustive case analysis on the disjunctions for a and b. In each of the 7 × 7 = 49 resulting branches, a and b are instantiated to concrete 3-element subsets of Fin 14.
rcases ha with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> rcases hb with rfl | rfl | rfl | rfl | rfl | rfl | rfl
Every case is closed: diagonal cases contradict distinctness, while off-diagonal pairs share at most one element.
In the 7 diagonal cases where a and b are identical, the hypothesis a ≠ b produces an immediate contradiction. In the 42 off-diagonal cases where a and b are distinct triples, Lean's kernel evaluates the intersection of the two sets and confirms that its cardinality is at most 1.
all_goals first | contradiction | decide +kernel
Finset.mem_coe- An element belongs to a finite set coerced to a set if and only if it belongs to the finite set.
P- The explicit family of seven 3-element subsets of Fin 14: {0, 1, 5}, {1, 2, 6}, {2, 3, 7}, {3, 4, 8}, {0, 4, 9}, {0, 11, 12}, and {1, 11, 13}.
Finset.mem_insert- An element belongs to insert b s if and only if it equals b or belongs to s.
Finset.mem_singleton- An element belongs to the singleton {a} if and only if it equals a.
- The tactic `decide +kernel` verifies the 42 off-diagonal set intersections via computational reflection in Lean's kernel rather than through deductive rewrite steps.
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.
open scoped Sym2set_option maxRecDepth 100000set_option maxHeartbeats 30000000open In701Deficit14theorem in715_deficit_p_disj : (P : Set (Finset (Fin 14))).Pairwise (fun a b => (a ∩ b).card ≤ 1) := by intro a ha b hb hab simp only [Finset.mem_coe, P, Finset.mem_insert, Finset.mem_singleton] at ha hb rcases ha with rfl | rfl | rfl | rfl | rfl | rfl | rfl <;> rcases hb with rfl | rfl | rfl | rfl | rfl | rfl | rfl all_goals first | contradiction | decide +kernel