pick_game_root_allocation_partition
For any root continuation bundle, the two-agent root allocation gives disjoint bundles whose union is the whole item set.
Statement
theorem pick_game_root_allocation_partition {n : ℕ} (F : List (Fin n) → Finset (Fin n)) :
Disjoint (pick_game_root_allocation F 0) (pick_game_root_allocation F 1) ∧
pick_game_root_allocation F 0 ∪ pick_game_root_allocation F 1 = Finset.univ- Source
- Sanity check for the root allocation in the operational picking game for OP-1323.
- Verified
- 10 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- pick_game_root_allocationThe root allocation from the continuation assigns its root bundle to agent 0 and all remaining objects to agent 1.
The proof, explained
In a two-agent picking game, the root allocation gives agent 0 the bundle F([]) and agent 1 its complement Finset.univ \ F([]). The proof splits the goal into showing that these two bundles are disjoint and that their union equals the whole set of items. Both claims follow directly from standard finite set identities: any set is disjoint from its relative complement, and the union of any subset with its complement in the universe is the universe itself.
The goal reduces to proving that the allocations to agent 0 and agent 1 are disjoint, and that their union is the universal set.
The goal is a conjunction of two properties: disjointness and exhaustiveness. Splitting the conjunction with constructor produces two separate subgoals.
constructorThe root allocations to agent 0 and agent 1 are disjoint.
By definition, pick_game_root_allocation F i evaluates to F [] when i = 0, and to Finset.univ \ F [] otherwise. For agent 0, the condition 0 = 0 is true, so agent 0 receives F []. For agent 1, the condition 1 = 0 is false, so agent 1 receives Finset.univ \ F []. By Finset.disjoint_sdiff, any set F [] is disjoint from Finset.univ \ F [].
uses
if_true,if_neg,Finset.disjoint_sdiff· unfold pick_game_root_allocation simp only [Fin.isValue, if_true] rw [if_neg (by decide : ¬ ((1 : Fin 2) = 0))] exact Finset.disjoint_sdiff
The union of the root allocations to agent 0 and agent 1 is the universal set.
Rewriting using the definition of pick_game_root_allocation, the allocation for agent 0 evaluates to F [] and the allocation for agent 1 evaluates to Finset.univ \ F []. Since F [] is a subset of Finset.univ (by Finset.subset_univ), their union F [] ∪ (Finset.univ \ F []) equals Finset.univ by Finset.union_sdiff_of_subset.
uses
if_true,if_neg,Finset.union_sdiff_of_subset,Finset.subset_univ· rw [pick_game_root_allocation, pick_game_root_allocation] simp only [Fin.isValue, if_true] rw [if_neg (by decide : ¬ ((1 : Fin 2) = 0))] exact Finset.union_sdiff_of_subset (Finset.subset_univ _)
if_true- An if-then-else expression whose condition is True evaluates to the then-branch.
if_neg- An if-then-else expression whose condition is false evaluates to the else-branch.
Finset.disjoint_sdiff- Any finite set s is disjoint from the relative complement t \ s.
Finset.union_sdiff_of_subset- If s is a subset of t, then s ∪ (t \ s) = t.
Finset.subset_univ- Every finite set of elements of a finite type is a subset of the universal set Finset.univ.
- The inequality 1 ≠ 0 in Fin 2 is verified inline by computational evaluation using the decide tactic.
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.
theorem pick_game_root_allocation_partition {n : ℕ} (F : List (Fin n) → Finset (Fin n)) : Disjoint (pick_game_root_allocation F 0) (pick_game_root_allocation F 1) ∧ pick_game_root_allocation F 0 ∪ pick_game_root_allocation F 1 = Finset.univ := by constructor · unfold pick_game_root_allocation simp only [Fin.isValue, if_true] rw [if_neg (by decide : ¬ ((1 : Fin 2) = 0))] exact Finset.disjoint_sdiff · rw [pick_game_root_allocation, pick_game_root_allocation] simp only [Fin.isValue, if_true] rw [if_neg (by decide : ¬ ((1 : Fin 2) = 0))] exact Finset.union_sdiff_of_subset (Finset.subset_univ _)