condorcet_triple_predecessor_minimal_core
For every finite directed relation with an outside common predecessor for every vertex set of size at most three, there is an induced subset A of at least four vertices retaining this property and having minimum cardinality among ALL induced subsets retaining it. This is a global minimum, stronger than vertex-deletion criticality alone. For every vertex a in A there is a set J contained in A, of size exactly three and excluding a, such that a points to all of J and is the unique outside common predecessor of J within A. The statement does not bound the size of A.
Statement
theorem condorcet_triple_predecessor_minimal_core (m : ℕ) (R : Fin m → Fin m → Prop) (hroot : ∀ J : Finset (Fin m), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) : ∃ A : Finset (Fin m), 4 ≤ A.card ∧ (∀ J : Finset (Fin m), J ⊆ A → J.card ≤ 3 → ∃ a, a ∈ A ∧ a ∉ J ∧ ∀ b ∈ J, R a b) ∧ (∀ B : Finset (Fin m), (∀ J : Finset (Fin m), J ⊆ B → J.card ≤ 3 → ∃ a, a ∈ B ∧ a ∉ J ∧ ∀ b ∈ J, R a b) → A.card ≤ B.card) ∧ (∀ a ∈ A, ∃ J : Finset (Fin m), J ⊆ A ∧ J.card = 3 ∧ a ∉ J ∧ (∀ b ∈ J, R a b) ∧ ∀ c, c ∈ A → c ∉ J → (∀ b ∈ J, R c b) → c = a)
- Source
- IN-357 supporting structural reduction for OP-19 and the proved condorcet_dimension_le_three_iff_acyclic_weight_separation. Ordinary finite minimal-counterexample argument, with no novelty claim. The2015 high-girth S3 construction (Theorem11, https://drops.dagstuhl.de/storage/00lipics/lipics-vol040-approx-random2015/LIPIcs.APPROX-RANDOM.2015.78/LIPIcs.APPROX-RANDOM.2015.78.pdf) prevents assuming bounded-size cores; no such bound is asserted.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
We consider the family of all vertex subsets satisfying property P that every subset of size at most three has an outside common predecessor. Since the full vertex set satisfies P by hypothesis, we can choose a subset A of minimum cardinality, which must satisfy |A| ≥ 4 because otherwise applying P to A itself would yield a vertex in A \ A. For each vertex a ∈ A, deleting a produces a strictly smaller subset A \ {a}, which cannot satisfy P by minimality, yielding a subset J ⊆ A \ {a} of size at most three with no outside predecessor in A \ {a}. Consequently, a is the unique predecessor of J in A \ J; furthermore, J must have size exactly three, because if |J| ≤ 2, applying P to {a} ∪ J would produce an outside predecessor that must equal a by uniqueness, a contradiction.
There exists a subset of vertices A of minimal cardinality satisfying the property P that every subset of size at most 3 has an outside common predecessor in A.
We define the property P(A) asserting that every subset J ⊆ A with |J| ≤ 3 has an outside predecessor a ∈ A \ J pointing to every vertex in J. The full vertex universe univ satisfies P by the global assumption hroot. Since the family F of subsets satisfying P is non-empty, we can choose a subset A ∈ F of minimum cardinality.
uses
mem_univclassical let P : Finset (Fin m) → Prop := fun A => ∀ J : Finset (Fin m), J ⊆ A → J.card ≤ 3 → ∃ a, a ∈ A ∧ a ∉ J ∧ ∀ b ∈ J, R a b let F : Finset (Finset (Fin m)) := univ.filter P have hF : (univ : Finset (Fin m)) ∈ F := by apply mem_filter.mpr refine ⟨mem_univ _, ?_⟩ intro J hJ hcard obtain ⟨a, ha, hR⟩ := hroot J hcard exact ⟨a, mem_univ _, ha, hR⟩ obtain ⟨A, hAF, hmin⟩ := F.exists_min_image Finset.card ⟨univ, hF⟩ have hA : P A := (mem_filter.mp hAF).2
The minimal subset A contains at least 4 vertices (|A| ≥ 4).
Suppose for contradiction that |A| ≤ 3. Since A ⊆ A, property P(A) applies to J = A itself, yielding an outside predecessor a ∈ A with a ∉ A, which is impossible.
uses
subset_reflhave hfour : 4 ≤ A.card := by by_contra h have hcard : A.card ≤ 3 := by omega obtain ⟨a, ha, hna, _⟩ := hA A (subset_refl A) hcard exact hna ha
The set A satisfies |A| ≥ 4, property P(A), and global minimality among all subsets satisfying P.
We instantiate the existential goal with A, supplying the proofs of |A| ≥ 4, property P(A), and the minimality of |A| compared to any other subset B satisfying P. This leaves only the existence of a private triple for each vertex in A.
uses
mem_univrefine ⟨A, hfour, hA, fun B hB => hmin B (mem_filter.mpr ⟨mem_univ _, hB⟩), ?_⟩
For any vertex a ∈ A, the deleted subset A \ {a} fails property P.
Fix a ∈ A. Removing a yields a strictly smaller subset A \ {a}. If A \ {a} satisfied property P, the minimality of |A| would force |A| ≤ |A \ {a}|, contradicting the fact that deleting an element strictly decreases cardinality.
uses
mem_univ,card_erase_lt_of_memintro a ha have hdelete : ¬ P (A.erase a) := by intro hP have hle := hmin (A.erase a) (mem_filter.mpr ⟨mem_univ _, hP⟩) have hdrop := card_erase_lt_of_mem ha omega
There exists a subset J ⊆ A \ {a} of size at most 3 with no outside predecessor in A \ {a}.
Because A \ {a} fails property P, expanding the negated definition gives a witness subset J ⊆ A \ {a} with |J| ≤ 3 that has no outside predecessor in A \ {a}. Since A \ {a} ⊆ A, J is also a subset of A.
uses
erase_subsethave hbad : ∃ J : Finset (Fin m), J ⊆ A.erase a ∧ J.card ≤ 3 ∧ ¬ ∃ c, c ∈ A.erase a ∧ c ∉ J ∧ ∀ b ∈ J, R c b := by by_contra hnone apply hdelete intro J hsub hcard by_contra hNo exact hnone ⟨J, hsub, hcard, hNo⟩ obtain ⟨J, hJsub, hJcard, hJnone⟩ := hbad have hJA : J ⊆ A := hJsub.trans (erase_subset a A)
The vertex a points to all of J and is the unique common predecessor of J in A \ J.
Any vertex c ∈ A \ J pointing to all of J cannot lie in A \ {a} (since J has no predecessor in A \ {a}), which forces c = a. On the other hand, because A satisfies property P and J ⊆ A has size at most 3, there must exist some predecessor c ∈ A \ J pointing to all of J. By uniqueness, c must be a.
have hprivate : ∀ c, c ∈ A → c ∉ J → (∀ b ∈ J, R c b) → c = a := by intro c hc hcJ hcR by_contra hne exact hJnone ⟨c, mem_erase.mpr ⟨hne, hc⟩, hcJ, hcR⟩ obtain ⟨c, hc, hcJ, hcR⟩ := hA J hJA hJcard have heq := hprivate c hc hcJ hcR subst c
The subset J has size exactly 3, completing the proof that a has a private triple.
Suppose |J| ≠ 3. Since |J| ≤ 3, this means |J| ≤ 2. Then the set {a} ∪ J has size |J| + 1 ≤ 3 (since a ∉ J) and is a subset of A. Applying property P(A) to {a} ∪ J yields an outside predecessor r ∈ A \ ({a} ∪ J) pointing to all of {a} ∪ J, and hence to all of J. Because r ∈ A \ J points to all of J, uniqueness forces r = a, contradicting r ∉ {a} ∪ J. Hence |J| = 3, and J satisfies all required conditions for a.
uses
insert_subset,card_insert_of_notMem,mem_insert_of_mem,mem_insert_selfhave hJthree : J.card = 3 := by by_contra hne have hJtwo : J.card ≤ 2 := by omega have hsub : insert a J ⊆ A := insert_subset ha hJA have hcard : (insert a J).card ≤ 3 := by rw [card_insert_of_notMem hcJ] omega obtain ⟨r, hrA, hrnot, hrR⟩ := hA (insert a J) hsub hcard have hrJ : r ∉ J := fun hr => hrnot (mem_insert_of_mem hr) have hra : r = a := hprivate r hrA hrJ (fun b hb => hrR b (mem_insert_of_mem hb)) subst r exact hrnot (mem_insert_self a J) exact ⟨J, hJA, hJthree, hcJ, hcR, hprivate⟩
mem_univ- Every element of a finite type belongs to the universal finite set univ.
subset_refl- The subset relation is reflexive: every set is a subset of itself.
card_erase_lt_of_mem- Removing an element from a finite set strictly decreases its cardinality.
erase_subset- Deleting an element from a set yields a subset of the original set.
insert_subset- If an element a and a subset s are both contained in t, then {a} ∪ s ⊆ t.
card_insert_of_notMem- Inserting an element not already present into a finite set increases its cardinality by 1.
mem_insert_of_mem- An element belonging to a set s also belongs to the set obtained by inserting another element into s.
mem_insert_self- An element a always belongs to the set {a} ∪ s.
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 Finsetset_option maxHeartbeats 4000000set_option maxRecDepth 10000theorem condorcet_triple_predecessor_minimal_core (m : ℕ) (R : Fin m → Fin m → Prop) (hroot : ∀ J : Finset (Fin m), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, R a b) : ∃ A : Finset (Fin m), 4 ≤ A.card ∧ (∀ J : Finset (Fin m), J ⊆ A → J.card ≤ 3 → ∃ a, a ∈ A ∧ a ∉ J ∧ ∀ b ∈ J, R a b) ∧ (∀ B : Finset (Fin m), (∀ J : Finset (Fin m), J ⊆ B → J.card ≤ 3 → ∃ a, a ∈ B ∧ a ∉ J ∧ ∀ b ∈ J, R a b) → A.card ≤ B.card) ∧ (∀ a ∈ A, ∃ J : Finset (Fin m), J ⊆ A ∧ J.card = 3 ∧ a ∉ J ∧ (∀ b ∈ J, R a b) ∧ ∀ c, c ∈ A → c ∉ J → (∀ b ∈ J, R c b) → c = a) := by classical let P : Finset (Fin m) → Prop := fun A => ∀ J : Finset (Fin m), J ⊆ A → J.card ≤ 3 → ∃ a, a ∈ A ∧ a ∉ J ∧ ∀ b ∈ J, R a b let F : Finset (Finset (Fin m)) := univ.filter P have hF : (univ : Finset (Fin m)) ∈ F := by apply mem_filter.mpr refine ⟨mem_univ _, ?_⟩ intro J hJ hcard obtain ⟨a, ha, hR⟩ := hroot J hcard exact ⟨a, mem_univ _, ha, hR⟩ obtain ⟨A, hAF, hmin⟩ := F.exists_min_image Finset.card ⟨univ, hF⟩ have hA : P A := (mem_filter.mp hAF).2 have hfour : 4 ≤ A.card := by by_contra h have hcard : A.card ≤ 3 := by omega obtain ⟨a, ha, hna, _⟩ := hA A (subset_refl A) hcard exact hna ha refine ⟨A, hfour, hA, fun B hB => hmin B (mem_filter.mpr ⟨mem_univ _, hB⟩), ?_⟩ intro a ha have hdelete : ¬ P (A.erase a) := by intro hP have hle := hmin (A.erase a) (mem_filter.mpr ⟨mem_univ _, hP⟩) have hdrop := card_erase_lt_of_mem ha omega have hbad : ∃ J : Finset (Fin m), J ⊆ A.erase a ∧ J.card ≤ 3 ∧ ¬ ∃ c, c ∈ A.erase a ∧ c ∉ J ∧ ∀ b ∈ J, R c b := by by_contra hnone apply hdelete intro J hsub hcard by_contra hNo exact hnone ⟨J, hsub, hcard, hNo⟩ obtain ⟨J, hJsub, hJcard, hJnone⟩ := hbad have hJA : J ⊆ A := hJsub.trans (erase_subset a A) have hprivate : ∀ c, c ∈ A → c ∉ J → (∀ b ∈ J, R c b) → c = a := by intro c hc hcJ hcR by_contra hne exact hJnone ⟨c, mem_erase.mpr ⟨hne, hc⟩, hcJ, hcR⟩ obtain ⟨c, hc, hcJ, hcR⟩ := hA J hJA hJcard have heq := hprivate c hc hcJ hcR subst c have hJthree : J.card = 3 := by by_contra hne have hJtwo : J.card ≤ 2 := by omega have hsub : insert a J ⊆ A := insert_subset ha hJA have hcard : (insert a J).card ≤ 3 := by rw [card_insert_of_notMem hcJ] omega obtain ⟨r, hrA, hrnot, hrR⟩ := hA (insert a J) hsub hcard have hrJ : r ∉ J := fun hr => hrnot (mem_insert_of_mem hr) have hra : r = a := hprivate r hrA hrJ (fun b hb => hrR b (mem_insert_of_mem hb)) subst r exact hrnot (mem_insert_self a J) exact ⟨J, hJA, hJthree, hcJ, hcR, hprivate⟩