AFTD Auto-Formalizing Theoretical Domains

seven_triple_system_not_two_colorable

theoremverified

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.

  1. 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.

    line 5

      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 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
See it in the graphDiscuss this resultChallenge it