condorcet_two_child_strict_half_bridge_obstruction
The explicit nine-vertex oriented relation in the definitions does not have S3. Integer weights totaling65 give every induced acyclic subset weight at most32, strictly below half. Nevertheless every nonnegative stationary occupation scheme on all outgoing two-element actions, with incoming mass twice each vertex marginal, has an induced acyclic subset with at least half the total marginal weight. Thus the general strict-half one-child bridge cannot be extended to two distinct children without extra hypotheses. This is not an election counterexample and does not refute an S3-specific policy claim.
Statement
theorem condorcet_two_child_strict_half_bridge_obstruction : (∀ a b : Fin 9, condorcet_two_child_gap_relation a b → ¬condorcet_two_child_gap_relation b a) ∧ (¬∀ J : Finset (Fin 9), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, condorcet_two_child_gap_relation a b) ∧ ((∑ a : Fin 9, condorcet_two_child_gap_weight a) = 65) ∧ (∀ A : Finset (Fin 9), WellFounded (fun a b : {a : Fin 9 // a ∈ A} => condorcet_two_child_gap_relation a.val b.val) → (∑ a ∈ A, condorcet_two_child_gap_weight a) ≤ 32) ∧ (∀ (x : Fin 9 → Finset (Fin 9) → ℝ) (w : Fin 9 → ℝ), (∀ a, ∀ J ∈ condorcet_two_child_gap_actions a, 0 ≤ x a J) → (∀ a, w a = ∑ J ∈ condorcet_two_child_gap_actions a, x a J) → (∀ b, 2 * w b = ∑ a, ∑ J ∈ condorcet_two_child_gap_actions a, if b ∈ J then x a J else 0) → ∃ A : Finset (Fin 9), WellFounded (fun a b : {a : Fin 9 // a ∈ A} => condorcet_two_child_gap_relation a.val b.val) ∧ (∑ a, w a) ≤ 2 * (∑ a ∈ A, w a)) ∧ (2 * (32 : ℕ) < 65)
- Source
- IN-380, OP-19 campaign session8, 2026-10-30. Numerical search9453, independent exact integer audit9457, and kernel-checked scratch TwoChildObstruction.lean. Supporting method obstruction; no new election bound, novelty or research advance is claimed.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The theorem proves an obstruction showing that the strict-half bridge from stationary Markov occupation schemes to induced acyclic subgraphs cannot be extended from 1-child transitions to 2-child branching actions without extra assumptions such as the S3 property. On an explicit 9-vertex oriented relation lacking S3, a static integer weighting totaling 65 assigns every induced acyclic subgraph a weight of at most 32, strictly below half. Conversely, via linear programming duality using a 5-element family of acyclic subgraphs and a potential function, every valid 2-child stationary flow scheme forces some induced acyclic subgraph to capture at least half the total marginal weight. Together with relation asymmetry and 2 * 32 < 65, this separates the dynamic 2-child occupation guarantee from static subgraph weight bounds.
The action-weighted sum of child potentials equals the marginal-weighted sum of incoming flow potentials: ∑ a, ∑ J ∈ F a, x a J * (∑ b ∈ J, h b) = ∑ b, 2 * w b * h b.
Rewriting the inner summation as an indicator over all vertices b, exchanging the order of summation between vertices and actions, and applying the flow-balance hypothesis (that each vertex b receives incoming action mass equal to 2 * w b) converts the total child potential into ∑ b, 2 * w b * h b.
uses
mul_sum,sum_comm,sum_mul,ite_mulclassical have hchildren : (∑ a, ∑ J ∈ F a, x a J * (∑ b ∈ J, h b)) = ∑ b, 2 * w b * h b := by calc (∑ a, ∑ J ∈ F a, x a J * (∑ b ∈ J, h b)) = ∑ a, ∑ J ∈ F a, ∑ b : Fin m, if b ∈ J then x a J * h b else 0 := by simp [mul_sum] _ = ∑ b : Fin m, ∑ a, ∑ J ∈ F a, if b ∈ J then x a J * h b else 0 := by simp_rw [sum_comm (s := F _)] rw [sum_comm] _ = ∑ b, (∑ a, ∑ J ∈ F a, if b ∈ J then x a J else 0) * h b := by simp [sum_mul, ite_mul] _ = _ := by simp_rw [← hflow]
Summing the dual inequality over all actions yields ∑ a, ∑ J ∈ F a, x a J * (c + ∑ b ∈ J, h b) ≤ ∑ a, ∑ J ∈ F a, x a J * (p a + 2 * h a).
Because each action weight x a J is nonnegative, multiplying the dual inequality c + ∑ b ∈ J, h b ≤ p a + 2 * h a by x a J preserves the inequality, and summing over all vertices a and actions J ∈ F a maintains it.
uses
sum_le_sum,mul_le_mul_of_nonneg_lefthave hsum : (∑ a, ∑ J ∈ F a, x a J * (c + ∑ b ∈ J, h b)) ≤ ∑ a, ∑ J ∈ F a, x a J * (p a + 2 * h a) := by apply sum_le_sum intro a ha apply sum_le_sum intro J hJ exact mul_le_mul_of_nonneg_left (hdual a J hJ) (hx a J hJ)
The general dual LP bound c * (∑ a, w a) ≤ ∑ a, w a * p a holds.
Expanding the left-hand side of the summed inequality yields c * (∑ a, w a) + ∑ a, 2 * w a * h a using the marginal definition w a = ∑ J, x a J and the child-potential identity. Similarly, expanding the right-hand side yields (∑ a, w a * p a) + ∑ a, 2 * w a * h a. Substituting both into the summed inequality, the potential terms cancel from both sides, leaving the desired bound.
uses
mul_add,sum_add_distrib,mul_sum,sum_congr,sum_mulhave hleft : (∑ a, ∑ J ∈ F a, x a J * (c + ∑ b ∈ J, h b)) = c * (∑ a, w a) + ∑ a, 2 * w a * h a := by simp_rw [mul_add, sum_add_distrib] rw [hchildren] congr 1 rw [mul_sum] apply sum_congr rfl intro a ha rw [← sum_mul, ← hw] ring have hright : (∑ a, ∑ J ∈ F a, x a J * (p a + 2 * h a)) = (∑ a, w a * p a) + ∑ a, 2 * w a * h a := by simp_rw [← sum_mul, ← hw, mul_add] rw [sum_add_distrib] congr 1 apply sum_congr rfl intro a ha ring rw [hleft, hright] at hsum linarith
When the payoff p a is a nonnegative combination of set indicators ∑ j, d j * 1_{a ∈ A j}, the dual bound becomes c * (∑ a, w a) ≤ ∑ j, d j * (∑ a ∈ A j, w a).
Specializing condorcet_two_child_action_dual_bound to the payoff p a = ∑ j, if a ∈ A j then d j else 0 gives c * ∑ a, w a ≤ ∑ a, w a * p a. Exchanging the order of summation between vertices a and set indices j rewrites the right-hand side as the sum over j of d j times the total marginal mass of A j.
uses
condorcet_two_child_action_dual_bound,mul_sum,sum_comm,sum_congr,mul_ite,mul_commclassical have hbound := condorcet_two_child_action_dual_bound m F x w (fun a => ∑ j, if a ∈ A j then d j else 0) h c hx hw hflow hdual have hswap : (∑ a, w a * (∑ j, if a ∈ A j then d j else 0)) = ∑ j, d j * (∑ a ∈ A j, w a) := by simp_rw [mul_sum] rw [sum_comm] apply sum_congr rfl intro j hj simp [mul_ite, mul_comm] rw [hswap] at hbound
There exists an index j such that c * (∑ a, w a) ≤ (∑ i, d i) * (∑ a ∈ A j, w a).
Since the number of candidate sets k is positive, there exists an index j maximizing the subset marginal mass ∑ a ∈ A j, w a. Because each coefficient d i is nonnegative, bounding each subset mass by the maximum allows factoring out ∑ i, d i.
uses
exists_max_image,mem_univ,sum_mul,sum_le_sum,mul_le_mul_of_nonneg_leftobtain ⟨j, hj, hmax⟩ := exists_max_image univ (fun j : Fin k => ∑ a ∈ A j, w a) ⟨⟨0,hk⟩, mem_univ _⟩ refine ⟨j, hbound.trans ?_⟩ rw [sum_mul] exact sum_le_sum (fun i hi => mul_le_mul_of_nonneg_left (hmax i hi) (hd i))
Every subset in the forbidden family of 22 sets is nonempty and has an in-neighbor within the subset for each of its elements. automation
Checked by finite exhaustive evaluation over the 22 explicit subsets of Fin 9.
B.Nonempty ∧ ∀ a ∈ B, ∃ b ∈ B, condorcet_two_child_gap_relation b a := by decide
Any subset of vertices containing none of the 22 forbidden subsets has total weight at most 32. automation
Checked by finite enumeration over all 512 subsets of vertices in Fin 9.
(∑ a ∈ A, condorcet_two_child_gap_weight a) ≤ 32 := by decide
Every subset A ⊆ Fin 9 that induces an acyclic (well-founded) relation has total weight at most 32.
If A contained any forbidden set B, then by well-foundedness B would possess a minimal element with respect to the relation, contradicting the fact that every vertex in B has an in-neighbor in B. Thus A contains no forbidden set, so condorcet_two_child_gap_weight_check implies its weight is at most 32.
uses
condorcet_two_child_gap_weight_check,condorcet_two_child_gap_forbidden_checkapply condorcet_two_child_gap_weight_check A intro B hB hsub obtain ⟨hne,hpred⟩ := condorcet_two_child_gap_forbidden_check B hB obtain ⟨b,hb⟩ := hne obtain ⟨a,ha,hmin⟩ := hA.has_min {a : {a : Fin 9 // a ∈ A} | a.val ∈ B} ⟨⟨b,hsub hb⟩,hb⟩ obtain ⟨c,hc,hca⟩ := hpred a.val ha exact hmin ⟨c,hsub hc⟩ hc hca
Along any directed edge in each of the 5 candidate sets, the assigned integer order strictly increases. automation
Checked by finite exhaustive evaluation over all pairs in each of the 5 candidate sets.
condorcet_two_child_gap_orders j a < condorcet_two_child_gap_orders j b := by decide
Each of the 5 candidate sets induces an acyclic (well-founded) relation.
Since the assigned integer orders strictly increase along every directed edge within each set, the induced relation embeds into the standard well-founded ordering on ℕ via measure, establishing acyclicity.
uses
measure,condorcet_two_child_gap_order_checkrefine (measure (fun a : {a : Fin 9 // a ∈ condorcet_two_child_gap_sets j} => condorcet_two_child_gap_orders j a.val)).wf.mono ?_ intro a b hab exact condorcet_two_child_gap_order_check j a b a.property b.property hab
The dual inequality holds with c = 3, potential h, and coefficients d = ![1, 1, 1, 2, 1] on the 5 candidate sets. automation
Checked by finite exhaustive evaluation across all 9 vertices and all their outgoing 2-actions.
2 * condorcet_two_child_gap_potential a := by decide
The dual inequality holds over the real numbers for the concrete gap configuration.
The pointwise natural-number dual inequality condorcet_two_child_gap_dual_check is coerced directly to ℝ.
uses
condorcet_two_child_gap_dual_checkhave hdual : ∀ a : Fin 9, ∀ J ∈ condorcet_two_child_gap_actions a, (3 : ℝ) + (∑ b ∈ J, (condorcet_two_child_gap_potential b : ℝ)) ≤ (∑ j : Fin 5, if a ∈ condorcet_two_child_gap_sets j then (condorcet_two_child_gap_coeff j : ℝ) else 0) + 2 * (condorcet_two_child_gap_potential a : ℝ) := by intro a J hJ exact_mod_cast condorcet_two_child_gap_dual_check a J hJ
Every valid 2-child action scheme on the 9-vertex relation admits an induced acyclic subset with at least half the total marginal weight: ∑ a, w a ≤ 2 * ∑ a ∈ A, w a.
Applying condorcet_two_child_action_dual_acyclic_mass with c = 3 and the 5 candidate sets produces an index j with 3 * ∑ a, w a ≤ (∑ i, d i) * ∑ a ∈ A j, w a. The sum of the coefficients is 6 by computation, simplifying the inequality to ∑ a, w a ≤ 2 * ∑ a ∈ A j, w a, and A j is acyclic by condorcet_two_child_gap_acyclic.
uses
condorcet_two_child_action_dual_acyclic_mass,Nat.cast_nonneg,condorcet_two_child_gap_acyclicobtain ⟨j,hj⟩ := condorcet_two_child_action_dual_acyclic_mass 9 5 (by decide) condorcet_two_child_gap_actions x w (fun a => (condorcet_two_child_gap_potential a : ℝ)) condorcet_two_child_gap_sets (fun j => (condorcet_two_child_gap_coeff j : ℝ)) 3 (fun j => Nat.cast_nonneg _) hx hw hflow hdual have hsumN : (∑ j : Fin 5, condorcet_two_child_gap_coeff j) = 6 := by decide have hsumR : (∑ j : Fin 5, (condorcet_two_child_gap_coeff j : ℝ)) = 6 := by exact_mod_cast hsumN rw [hsumR] at hj exact ⟨_,condorcet_two_child_gap_acyclic j,by linarith⟩
All six conjuncts of the obstruction theorem hold simultaneously.
Asymmetry of the relation, failure of the S3 property (existence of an external dominating vertex for every triple), total vertex weight equaling 65, and the strict inequality 2 * 32 < 65 are all verified by finite computation (decide). The maximum acyclic weight bound of 32 is supplied by condorcet_two_child_gap_mass, and the half-weight guarantee for 2-child flow schemes is supplied by condorcet_two_child_gap_bound.
uses
condorcet_two_child_gap_mass,condorcet_two_child_gap_boundexact ⟨by decide,by decide,by decide,condorcet_two_child_gap_mass,condorcet_two_child_gap_bound,by decide⟩
mul_sum- Multiplication distributes over finite sums from the left: a * ∑ i, f i = ∑ i, a * f i.
sum_comm- Fubini's theorem exchanging the order of two finite summations: ∑ x ∈ s, ∑ y ∈ t, f x y = ∑ y ∈ t, ∑ x ∈ s, f x y.
sum_mul- Multiplication distributes over finite sums from the right: (∑ i, f i) * a = ∑ i, f i * a.
ite_mul- Multiplication distributes over an if-then-else from the right: (if P then a else b) * c = if P then a * c else b * c.
sum_le_sum- If f i ≤ g i for all i in a finite set, then the sum of f is at most the sum of g.
mul_le_mul_of_nonneg_left- Multiplying an inequality b ≤ c by a nonnegative scalar a preserves the inequality: a * b ≤ a * c.
mul_add- Left distributivity of multiplication over addition: a * (b + c) = a * b + a * c.
sum_add_distrib- The sum of a sum distributes: ∑ x, (f x + g x) = ∑ x, f x + ∑ x, g x.
sum_congr- If two summations have equal index sets and pointwise equal terms, their sums are equal.
condorcet_two_child_action_dual_bound- For any nonnegative action scheme with 2-to-1 flow balance, if a dual inequality c + ∑_{b ∈ J} h(b) ≤ p(a) + 2 h(a) holds for all outgoing actions J, then c ∑ a, w a ≤ ∑ a, w a * p a.
mul_ite- Multiplication distributes over an if-then-else from the left: a * (if P then b else c) = if P then a * b else a * c.
mul_comm- Multiplication is commutative: a * b = b * a.
exists_max_image- Any nonempty finite set contains an element achieving the maximum of a given real-valued function.
mem_univ- Every element of a finite type belongs to the universal finset univ.
condorcet_two_child_gap_weight_check- Every subset of vertices in Fin 9 containing none of the 22 forbidden subsets has total weight at most 32.
condorcet_two_child_gap_forbidden_check- Every subset in the 22-element forbidden family is nonempty and every vertex in it has an in-neighbor belonging to the subset.
measure- Constructs a well-founded relation by pulling back the standard ordering on ℕ along a measure function.
condorcet_two_child_gap_order_check- Along any directed edge within one of the 5 candidate sets, the assigned integer order strictly increases.
condorcet_two_child_gap_dual_check- The dual linear inequality with c = 3, potential h, and coefficients d on the 5 candidate sets holds for all vertices and all their outgoing 2-actions.
condorcet_two_child_action_dual_acyclic_mass- For any nonnegative 2-child action scheme satisfying flow balance, if the dual inequality holds for a combination of indicator sets A_j with nonnegative weights d_j, then some set A_j satisfies c ∑ a, w a ≤ (∑ i, d i) * w(A_j).
Nat.cast_nonneg- The coercion of a natural number to an ordered semiring is nonnegative: 0 ≤ (n : ℝ).
condorcet_two_child_gap_acyclic- Each of the 5 candidate gap subsets induces an acyclic (well-founded) subrelation.
condorcet_two_child_gap_mass- Any subset of vertices in the 9-vertex relation that induces an acyclic subrelation has total weight at most 32.
condorcet_two_child_gap_bound- For every nonnegative 2-child action scheme satisfying flow balance on the 9-vertex relation, there exists an induced acyclic subset with at least half the total marginal weight.
- Several finite combinatorial checks—including the cycle property of the 22 forbidden subsets, the 32 weight bound across all 512 vertex subsets, the strict monotonicity of topological orders, the failure of the S3 property, and arithmetic inequalities—are verified by Lean's computational decision procedure (`decide`).
- Acyclicity of an induced subgraph is formalized as well-foundedness (`WellFounded`) of the restricted directed relation, which for finite sets is equivalent to the absence of directed cycles.
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 Finsetopen scoped BigOperatorsset_option maxHeartbeats 20000000set_option maxRecDepth 20000theorem condorcet_two_child_action_dual_bound (m : ℕ) (F : Fin m → Finset (Finset (Fin m))) (x : Fin m → Finset (Fin m) → ℝ) (w p h : Fin m → ℝ) (c : ℝ) (hx : ∀ a, ∀ J ∈ F a, 0 ≤ x a J) (hw : ∀ a, w a = ∑ J ∈ F a, x a J) (hflow : ∀ b, 2 * w b = ∑ a, ∑ J ∈ F a, if b ∈ J then x a J else 0) (hdual : ∀ a, ∀ J ∈ F a, c + (∑ b ∈ J, h b) ≤ p a + 2 * h a) : c * (∑ a, w a) ≤ ∑ a, w a * p a := by classical have hchildren : (∑ a, ∑ J ∈ F a, x a J * (∑ b ∈ J, h b)) = ∑ b, 2 * w b * h b := by calc (∑ a, ∑ J ∈ F a, x a J * (∑ b ∈ J, h b)) = ∑ a, ∑ J ∈ F a, ∑ b : Fin m, if b ∈ J then x a J * h b else 0 := by simp [mul_sum] _ = ∑ b : Fin m, ∑ a, ∑ J ∈ F a, if b ∈ J then x a J * h b else 0 := by simp_rw [sum_comm (s := F _)] rw [sum_comm] _ = ∑ b, (∑ a, ∑ J ∈ F a, if b ∈ J then x a J else 0) * h b := by simp [sum_mul, ite_mul] _ = _ := by simp_rw [← hflow] have hsum : (∑ a, ∑ J ∈ F a, x a J * (c + ∑ b ∈ J, h b)) ≤ ∑ a, ∑ J ∈ F a, x a J * (p a + 2 * h a) := by apply sum_le_sum intro a ha apply sum_le_sum intro J hJ exact mul_le_mul_of_nonneg_left (hdual a J hJ) (hx a J hJ) have hleft : (∑ a, ∑ J ∈ F a, x a J * (c + ∑ b ∈ J, h b)) = c * (∑ a, w a) + ∑ a, 2 * w a * h a := by simp_rw [mul_add, sum_add_distrib] rw [hchildren] congr 1 rw [mul_sum] apply sum_congr rfl intro a ha rw [← sum_mul, ← hw] ring have hright : (∑ a, ∑ J ∈ F a, x a J * (p a + 2 * h a)) = (∑ a, w a * p a) + ∑ a, 2 * w a * h a := by simp_rw [← sum_mul, ← hw, mul_add] rw [sum_add_distrib] congr 1 apply sum_congr rfl intro a ha ring rw [hleft, hright] at hsum linariththeorem condorcet_two_child_action_dual_acyclic_mass (m k : ℕ) (hk : 0 < k) (F : Fin m → Finset (Finset (Fin m))) (x : Fin m → Finset (Fin m) → ℝ) (w h : Fin m → ℝ) (A : Fin k → Finset (Fin m)) (d : Fin k → ℝ) (c : ℝ) (hd : ∀ j, 0 ≤ d j) (hx : ∀ a, ∀ J ∈ F a, 0 ≤ x a J) (hw : ∀ a, w a = ∑ J ∈ F a, x a J) (hflow : ∀ b, 2 * w b = ∑ a, ∑ J ∈ F a, if b ∈ J then x a J else 0) (hdual : ∀ a, ∀ J ∈ F a, c + (∑ b ∈ J, h b) ≤ (∑ j, if a ∈ A j then d j else 0) + 2 * h a) : ∃ j, c * (∑ a, w a) ≤ (∑ i, d i) * (∑ a ∈ A j, w a) := by classical have hbound := condorcet_two_child_action_dual_bound m F x w (fun a => ∑ j, if a ∈ A j then d j else 0) h c hx hw hflow hdual have hswap : (∑ a, w a * (∑ j, if a ∈ A j then d j else 0)) = ∑ j, d j * (∑ a ∈ A j, w a) := by simp_rw [mul_sum] rw [sum_comm] apply sum_congr rfl intro j hj simp [mul_ite, mul_comm] rw [hswap] at hbound obtain ⟨j, hj, hmax⟩ := exists_max_image univ (fun j : Fin k => ∑ a ∈ A j, w a) ⟨⟨0,hk⟩, mem_univ _⟩ refine ⟨j, hbound.trans ?_⟩ rw [sum_mul] exact sum_le_sum (fun i hi => mul_le_mul_of_nonneg_left (hmax i hi) (hd i))def condorcet_two_child_gap_pred : Fin 9 → Finset (Fin 9) := ![{3,4,6,8},{0,4,5,7},{0,1,5,6},{2,7},{2,5,8},{0,3,6,8},{1,3,4},{0,4,6},{1,2,3,6,7}]def condorcet_two_child_gap_relation (a b : Fin 9) : Prop := a ∈ condorcet_two_child_gap_pred binstance (a b : Fin 9) : Decidable (condorcet_two_child_gap_relation a b) := inferInstanceAs (Decidable (a ∈ condorcet_two_child_gap_pred b))def condorcet_two_child_gap_actions (a : Fin 9) : Finset (Finset (Fin 9)) := (univ.powersetCard 2).filter (fun J => ∀ b ∈ J, condorcet_two_child_gap_relation a b)def condorcet_two_child_gap_sets : Fin 5 → Finset (Fin 9) := ![{0,1,2,5,7},{2,4,5,7},{1,2,6,8},{0,3,5,6,8},{1,2,3,7,8}]def condorcet_two_child_gap_coeff : Fin 5 → ℕ := ![1,1,1,2,1]def condorcet_two_child_gap_potential : Fin 9 → ℕ := ![0,0,0,0,1,0,0,0,0]def condorcet_two_child_gap_orders : Fin 5 → Fin 9 → ℕ := ![![0,3,4,0,0,1,0,2,0],![0,0,1,0,2,0,0,3,0],![0,0,2,0,0,0,1,0,3],![3,0,0,0,0,4,1,0,2],![0,1,2,3,0,0,0,0,4]]def condorcet_two_child_gap_forbidden : Finset (Finset (Fin 9)) := {{0,2,3},{0,2,4},{1,2,4},{2,3,5},{0,4,5},{0,1,6},{2,3,6},{2,4,6},{1,5,6},{4,5,6},{0,3,7},{3,4,5,7},{1,6,7},{3,6,7},{0,1,8},{0,2,8},{1,4,8},{1,5,8},{2,5,8},{4,6,8},{0,7,8},{4,7,8}}def condorcet_two_child_gap_weight : Fin 9 → ℕ := ![6,8,7,3,13,6,8,5,9]theorem condorcet_two_child_gap_forbidden_check : ∀ B ∈ condorcet_two_child_gap_forbidden, B.Nonempty ∧ ∀ a ∈ B, ∃ b ∈ B, condorcet_two_child_gap_relation b a := by decidetheorem condorcet_two_child_gap_weight_check : ∀ A : Finset (Fin 9), (∀ B ∈ condorcet_two_child_gap_forbidden, ¬B ⊆ A) → (∑ a ∈ A, condorcet_two_child_gap_weight a) ≤ 32 := by decidetheorem condorcet_two_child_gap_mass (A : Finset (Fin 9)) (hA : WellFounded (fun a b : {a : Fin 9 // a ∈ A} => condorcet_two_child_gap_relation a.val b.val)) : (∑ a ∈ A, condorcet_two_child_gap_weight a) ≤ 32 := by apply condorcet_two_child_gap_weight_check A intro B hB hsub obtain ⟨hne,hpred⟩ := condorcet_two_child_gap_forbidden_check B hB obtain ⟨b,hb⟩ := hne obtain ⟨a,ha,hmin⟩ := hA.has_min {a : {a : Fin 9 // a ∈ A} | a.val ∈ B} ⟨⟨b,hsub hb⟩,hb⟩ obtain ⟨c,hc,hca⟩ := hpred a.val ha exact hmin ⟨c,hsub hc⟩ hc hcatheorem condorcet_two_child_gap_order_check : ∀ j : Fin 5, ∀ a b : Fin 9, a ∈ condorcet_two_child_gap_sets j → b ∈ condorcet_two_child_gap_sets j → condorcet_two_child_gap_relation a b → condorcet_two_child_gap_orders j a < condorcet_two_child_gap_orders j b := by decidetheorem condorcet_two_child_gap_acyclic (j : Fin 5) : WellFounded (fun a b : {a : Fin 9 // a ∈ condorcet_two_child_gap_sets j} => condorcet_two_child_gap_relation a.val b.val) := by refine (measure (fun a : {a : Fin 9 // a ∈ condorcet_two_child_gap_sets j} => condorcet_two_child_gap_orders j a.val)).wf.mono ?_ intro a b hab exact condorcet_two_child_gap_order_check j a b a.property b.property habtheorem condorcet_two_child_gap_dual_check : ∀ a : Fin 9, ∀ J ∈ condorcet_two_child_gap_actions a, 3 + (∑ b ∈ J, condorcet_two_child_gap_potential b) ≤ (∑ j : Fin 5, if a ∈ condorcet_two_child_gap_sets j then condorcet_two_child_gap_coeff j else 0) + 2 * condorcet_two_child_gap_potential a := by decidetheorem condorcet_two_child_gap_bound (x : Fin 9 → Finset (Fin 9) → ℝ) (w : Fin 9 → ℝ) (hx : ∀ a, ∀ J ∈ condorcet_two_child_gap_actions a, 0 ≤ x a J) (hw : ∀ a, w a = ∑ J ∈ condorcet_two_child_gap_actions a, x a J) (hflow : ∀ b, 2 * w b = ∑ a, ∑ J ∈ condorcet_two_child_gap_actions a, if b ∈ J then x a J else 0) : ∃ A : Finset (Fin 9), WellFounded (fun a b : {a : Fin 9 // a ∈ A} => condorcet_two_child_gap_relation a.val b.val) ∧ (∑ a, w a) ≤ 2 * (∑ a ∈ A, w a) := by have hdual : ∀ a : Fin 9, ∀ J ∈ condorcet_two_child_gap_actions a, (3 : ℝ) + (∑ b ∈ J, (condorcet_two_child_gap_potential b : ℝ)) ≤ (∑ j : Fin 5, if a ∈ condorcet_two_child_gap_sets j then (condorcet_two_child_gap_coeff j : ℝ) else 0) + 2 * (condorcet_two_child_gap_potential a : ℝ) := by intro a J hJ exact_mod_cast condorcet_two_child_gap_dual_check a J hJ obtain ⟨j,hj⟩ := condorcet_two_child_action_dual_acyclic_mass 9 5 (by decide) condorcet_two_child_gap_actions x w (fun a => (condorcet_two_child_gap_potential a : ℝ)) condorcet_two_child_gap_sets (fun j => (condorcet_two_child_gap_coeff j : ℝ)) 3 (fun j => Nat.cast_nonneg _) hx hw hflow hdual have hsumN : (∑ j : Fin 5, condorcet_two_child_gap_coeff j) = 6 := by decide have hsumR : (∑ j : Fin 5, (condorcet_two_child_gap_coeff j : ℝ)) = 6 := by exact_mod_cast hsumN rw [hsumR] at hj exact ⟨_,condorcet_two_child_gap_acyclic j,by linarith⟩theorem condorcet_two_child_strict_half_bridge_obstruction : (∀ a b : Fin 9, condorcet_two_child_gap_relation a b → ¬condorcet_two_child_gap_relation b a) ∧ (¬∀ J : Finset (Fin 9), J.card ≤ 3 → ∃ a, a ∉ J ∧ ∀ b ∈ J, condorcet_two_child_gap_relation a b) ∧ ((∑ a : Fin 9, condorcet_two_child_gap_weight a) = 65) ∧ (∀ A : Finset (Fin 9), WellFounded (fun a b : {a : Fin 9 // a ∈ A} => condorcet_two_child_gap_relation a.val b.val) → (∑ a ∈ A, condorcet_two_child_gap_weight a) ≤ 32) ∧ (∀ (x : Fin 9 → Finset (Fin 9) → ℝ) (w : Fin 9 → ℝ), (∀ a, ∀ J ∈ condorcet_two_child_gap_actions a, 0 ≤ x a J) → (∀ a, w a = ∑ J ∈ condorcet_two_child_gap_actions a, x a J) → (∀ b, 2 * w b = ∑ a, ∑ J ∈ condorcet_two_child_gap_actions a, if b ∈ J then x a J else 0) → ∃ A : Finset (Fin 9), WellFounded (fun a b : {a : Fin 9 // a ∈ A} => condorcet_two_child_gap_relation a.val b.val) ∧ (∑ a, w a) ≤ 2 * (∑ a ∈ A, w a)) ∧ (2 * (32 : ℕ) < 65) := by exact ⟨by decide,by decide,by decide,condorcet_two_child_gap_mass,condorcet_two_child_gap_bound,by decide⟩