efx_min_cycle_subset_complete
Every subset of an old triple plus good 12 has a Boolean-mask encoding.
Statement
theorem efx_min_cycle_subset_complete (j : Fin 4) (T : Finset (Fin 13))
(hT : T ⊆ insert 12 (efx_no_self_three_split_old j)) :
∃ b : Fin 4 → Bool, efx_min_cycle_subset j b = T- Source
- Minimum-cardinality champion-cycle swap obstruction for OP-7, experiments 11442–11449; comparison with arXiv:2002.05119 Section 3.1.
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- efx_min_cycle_subsetEncode an arbitrary subset of the four goods in old bundle j plus good 12 using four Boolean flags.
- efx_min_cycle_goodsFor each target old bundle, list its three goods followed by the unallocated good.
- efx_no_self_three_split_oldThe old partial allocation consists of four consecutive triples; good 12 is unallocated.
- Used by 2
- efx_nondeg_cycle_no_selfNo agent has an inclusion-minimal self-champion set in the nondegenerate cycle instance.
- efx_min_cycle_no_selfNo source self-champions, even when champion sets are allowed to be arbitrary inclusion-minimal envied subsets.
The proof, explained
To show that any subset T of an old triple plus good 12 can be encoded as a Boolean mask, we define the mask to select exactly those indices whose corresponding goods belong to T. By extensionality, equality of the resulting set with T reduces to showing both inclusions: any selected good is in T by definition, and conversely every element of T is covered by some index via finite case exhaustion, hence is selected by the mask.
The map indexing goods for cycle j surjectively covers the old triple plus good 12. automation
We exhaustively check all 4 choices of j and all 13 elements x by finite case analysis and computation.
lemma efx_min_cycle_subset_complete_goods_surj (j : Fin 4) (x : Fin 13) (hx : x ∈ insert 12 (efx_no_self_three_split_old j)) : ∃ t : Fin 4, efx_min_cycle_goods j t = x := by fin_cases j <;> fin_cases x <;> revert hx <;> decide
Choose the characteristic mask indicating membership in T, and reduce equality of sets to elementhood.
We pick the mask b sending t to whether the corresponding good is in T. By extensionality, the generated subset equals T if and only if they have the same elements. Expanding the definitions of subset selection, image, filter, and universals simplifies membership in the generated set to whether x is the image of some good belonging to T.
uses
Finset.mem_image,Finset.mem_filter,Finset.mem_univ,true_and,decide_eq_true_equse fun t => decide (efx_min_cycle_goods j t ∈ T) ext x simp only [efx_min_cycle_subset, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and, decide_eq_true_eq]
If an element is generated by the mask, it belongs to T.
Any element in the generated set is of the form efx_min_cycle_goods j t for some t such that efx_min_cycle_goods j t is in T, which immediately implies the element is in T.
constructor · rintro ⟨t, ht, rfl⟩ exact ht
Conversely, every element in T is generated by the mask.
Given x in T, the assumption that T is a subset of the old triple plus good 12 means x belongs to that 4-good set. By surjectivity, x is efx_min_cycle_goods j t for some index t. Since x is in T, this index t satisfies the mask condition, witnessing that x is in the generated set.
uses
efx_min_cycle_subset_complete_goods_surj· intro hx obtain ⟨t, ht⟩ := efx_min_cycle_subset_complete_goods_surj j x (hT hx) exact ⟨t, ht ▸ hx, ht⟩
efx_min_cycle_subset_complete_goods_surj- Every element of a 4-good bundle is indexed by some t in Fin 4.
Finset.mem_image- x is in image f s iff x = f a for some a in s.
Finset.mem_filter- x is in filter p s iff x is in s and p x holds.
Finset.mem_univ- Every element belongs to the universal finset.
true_and- True and p is equivalent to p.
decide_eq_true_eq- decide p = true is equivalent to p.
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.
lemma efx_min_cycle_subset_complete_goods_surj (j : Fin 4) (x : Fin 13) (hx : x ∈ insert 12 (efx_no_self_three_split_old j)) : ∃ t : Fin 4, efx_min_cycle_goods j t = x := by fin_cases j <;> fin_cases x <;> revert hx <;> decidetheorem efx_min_cycle_subset_complete (j : Fin 4) (T : Finset (Fin 13)) (hT : T ⊆ insert 12 (efx_no_self_three_split_old j)) : ∃ b : Fin 4 → Bool, efx_min_cycle_subset j b = T := by use fun t => decide (efx_min_cycle_goods j t ∈ T) ext x simp only [efx_min_cycle_subset, Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and, decide_eq_true_eq] constructor · rintro ⟨t, ht, rfl⟩ exact ht · intro hx obtain ⟨t, ht⟩ := efx_min_cycle_subset_complete_goods_surj j x (hT hx) exact ⟨t, ht ▸ hx, ht⟩