§3, p. 8 — the null set is consistent, unions of consistent sets are consistent, and every set has a unique maximal consistent subset
ProvedFourColourRSST.Ring.consistent_closureconsistent-setedge-colouringfour-colour-theoremp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a circuit of length . Then:
- the empty set of edge-colourings of is consistent;
- if and are consistent, so is ;
- every set of edge-colourings of has a unique maximal consistent subset , in the sense that there is exactly one which is consistent and contains every consistent subset of :
The maximal consistent subset is the object the reducibility computations of §3 evaluate; the paper notes that for rings of small size it can be computed from by machine.
Formalization Note. "Maximal" is rendered as greatest (contains every consistent subset of ), which is the meaning the paper's "unique maximal" carries given closure under unions. The circuit is cycleGraph k on Fin k, with restricting to the circuits this encoding represents.
Preamble
import Mathlib import Definitions.Def_FourColourRSST_Ring_Setting
Formal statement
namespace FourColourRSST.Ring
theorem consistent_closure {k : ℕ} [NeZero k] (hk : 3 ≤ k) :
Consistent (∅ : Set (EdgeColouring k)) ∧
(∀ C₁ C₂ : Set (EdgeColouring k), Consistent C₁ → Consistent C₂ → Consistent (C₁ ∪ C₂)) ∧
(∀ S : Set (EdgeColouring k), ∃! S' : Set (EdgeColouring k),
S' ⊆ S ∧ Consistent S' ∧ ∀ T ⊆ S, Consistent T → T ⊆ S') := by sorry
end FourColourRSST.Ring
Source
Robertson, Sanders, Seymour and Thomas, The Four-Colour Theorem, J. Combin. Theory Ser. B 70 (1997), author's manuscript (rev. 16 January 1997), p. 8, §3, "Since the null set is consistent, and the union of any two consistent sets is consistent, it follows that any set of edge-colourings 𝒮 has a unique maximal consistent subset 𝒮′"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.