Lemma C.12 — Singleton affine pruning and minion solutions
OpenAbelianPromises.Dichotomy.Supplement.pruning_minion_equivalenceLet be any finite Label Cover instance and any abstract minion. Every vertex of has a nonempty finite domain, and every directed edge carries a total projection, from source to target. There exists an -solution after constraint singleton AIP pruning exactly when the original instance has an -solution:
Here an -solution assigns a member at each vertex's domain arity and respects every edge minor. The construction runs tuple pinning and signed-integer AIP pruning to a fixed point and then restricts domains, leaving isolated domains unchanged. Rejection has no solution. The minion need not be finite, functional, or given with an oracle. Neither a solution nor an AIP feasibility certificate is assumed.
This is the supporting equivalence used by the companion characterisation in Theorem C.15. It applies to parallel edges, disconnected instances, isolated vertices, and the empty vertex set.
Differences from the source:
- encoding: arbitrary nonempty finite coordinate and column sets → all nonempty finite subsets of Nat for coordinates and Fin(j+1) for arbitrary finite columns; reason: a size-unbounded finite-set skeleton; bijective reindexing preserves every instance and minor.
- encoding: minor operations and the omega construction → the exact graph of each derived minor operation; reason: the graph records the same fibre-sum matrix and restricted minor without assuming derived closure facts.
- encoding: pruning to a fixed point and restricting domains → simultaneous tuple deletion for N0+1 rounds followed by all incident positional compatibility tests; reason: finite monotone deletion gives the same greatest fixed point, and fixed-point pinned feasibility makes all incident supports agree; isolated domains are unchanged.
- encoding: empty initial domains or relations interpreted as unsatisfiable → kappa returns rejection for any empty current domain or relation, including an initially empty isolated domain; reason: makes the nonempty-domain LC construction total on empty templates without removing any satisfiable source instance.
import Mathlib import Definitions.Def_AbelianPromises_Dichotomy_Supplement_LabelCover import Definitions.Def_AbelianPromises_Dichotomy_Supplement_SkeletalOmega set_option autoImplicit false
namespace AbelianPromises.Dichotomy.Supplement
/-- Lemma C.12, with all finite Label Cover instances and arbitrary abstract minions. -/
theorem pruning_minion_equivalence (L : LabelCover) (N : AbstractMinion) :
PrunedHasSolution L.toLCData N.presentation ↔
L.toLCData.HasSolution (omega N.presentation) := by sorry
end AbelianPromises.Dichotomy.Supplement