seven_triple_system_not_two_colorable
For the seven displayed triples on seven points, every two-coloring of the points makes at least one triple monochromatic.
Statement
theorem seven_triple_system_not_two_colorable : let L : Fin 7 → Finset (Fin 7) := ![({0,1,2} : Finset (Fin 7)), {0,3,4}, {0,5,6}, {1,3,5}, {1,4,6}, {2,3,6}, {2,4,5}]; ∀ A : Finset (Fin 7), ∃ i : Fin 7, L i ⊆ A ∨ Disjoint (L i) A
- Source
- Classical seven-point triple system; explicitly tested in experiment 26841.
- Verified
- 14 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The theorem asserts that the Fano plane (the Steiner triple system on 7 points) is not 2-colorable: any 2-coloring of the 7 vertices leaves at least one triple monochromatic. Because the vertex set has size 7, there are only 2⁷ = 128 subsets to consider as color classes. The proof succeeds by finite exhaustive verification via Lean's `decide` tactic.
For every subset A of Fin 7, at least one of the seven triples is either entirely contained in A or entirely disjoint from A. automation
The property is decidable because Fin 7 is a finite type with 7 elements, so there are only 2⁷ = 128 subsets A to check, and for each subset there are only 7 triples to inspect. The `decide` tactic checks every case by finite computation, finding a monochromatic triple for each coloring.
decide
- The proof relies entirely on computational reflection (`decide`), evaluating the decidable proposition by exhaustively checking all 128 possible subsets of the 7-element set.
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.
set_option maxRecDepth 100000set_option maxHeartbeats 10000000theorem seven_triple_system_not_two_colorable : let L : Fin 7 → Finset (Fin 7) := ![({0,1,2} : Finset (Fin 7)), {0,3,4}, {0,5,6}, {1,3,5}, {1,4,6}, {2,3,6}, {2,4,5}]; ∀ A : Finset (Fin 7), ∃ i : Fin 7, L i ⊆ A ∨ Disjoint (L i) A := by decide