AFTD Auto-Formalizing Theoretical Domains

picking_turn_alloc_subset

theoremverified

One turn never un-allocates a good: the set of goods already allocated before a picking turn is contained in the set of allocated goods after it.

Statement

theorem picking_turn_alloc_subset {N G : Type*} [DecidableEq N] [DecidableEq G] (l : List G) (i : N)
    (st : (N → Finset G) × Finset G) : st.2 ⊆ (picking_turn l i st).2
Source
step towards picking_prefix_state_alloc_mono
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • picking_turnOne turn of a picking-sequence mechanism: the active agent i receives the first good of its reported ranking l (best first) that is not…
Used by 2

The proof, explained

The proof proceeds by unfolding the definition of `picking_turn` and performing case analysis on whether an unallocated good is found in the list `l`. If an available good is found, it is added to the allocated set, which trivially preserves containment by `Finset.subset_insert`. If no available good is found, the state is left unchanged, and containment holds by reflexivity (`subset_refl`).

  1. The claim reduces to two cases depending on whether an unallocated good is found.

    Unfolding the definition of `picking_turn`, the function inspects the list `l` to find the first good not already in `st.2`. Splitting on this search yields two cases: either some available good is found, or no such good exists.

    lines 4–5

      unfold picking_turn
      split
  2. If an unallocated good is found, the old allocated set is a subset of the updated allocated set.

    When an unallocated good g is found, the updated allocated set is `insert g st.2`. Any finite set is a subset of the result of inserting an element into it, by `Finset.subset_insert`.

    line 6

    uses Finset.subset_insert

      · exact Finset.subset_insert _ _
  3. If no unallocated good is found, the old allocated set is contained in itself.

    When no item in `l` is available, the state is returned unchanged, so the goal is `st.2 ⊆ st.2`, which holds by reflexivity (`subset_refl`).

    line 7

    uses subset_refl

      · exact subset_refl _
Finset.subset_insert
A finite set is a subset of the set obtained by inserting an element into it: s ⊆ insert a s.
subset_refl
Subset inclusion is reflexive: every set is a subset of itself (a ⊆ a).

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

/-- A single picking turn only inserts a good into the allocated set (or does nothing), so the old allocated set stays contained in the new one. -/theorem picking_turn_alloc_subset {N G : Type*} [DecidableEq N] [DecidableEq G] (l : List G) (i : N)    (st : (N → Finset G) × Finset G) : st.2 ⊆ (picking_turn l i st).2 := by  unfold picking_turn  split  · exact Finset.subset_insert _ _  · exact subset_refl _
See it in the graphDiscuss this resultChallenge it