AFTD Auto-Formalizing Theoretical Domains

efx_min_cycle_subset_complete

theoremverified

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.

  1. 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.

    lines 1–4

    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
  2. 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.

    lines 9–12

    uses Finset.mem_image, Finset.mem_filter, Finset.mem_univ, true_and, decide_eq_true_eq

      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]
  3. 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.

    lines 13–15

      constructor
      · rintro ⟨t, ht, rfl⟩
        exact ht
  4. 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.

    lines 16–18

    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

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⟩
See it in the graphDiscuss this resultChallenge it