Lemma 2 (Central Lemma), p. 15 — Φ is injective on the state space, so |𝒮| = |Φ⟨𝒮⟩|
ProvedConsiderChoose.StateSpace.lemma_2Let be consideration sets over products numbered in the common preference order, let be the state space of the dynamic program of §3 (the distinct nontrivial connected subproblems generated from the components of by stocking or skipping ), and let
Then is injective on , and consequently
The lemma turns counting the states of the dynamic program into counting subsets of products, which is how Theorem 1 and the paper's later running-time bounds for structured consideration sets are obtained.
Formalization Note. is the inductively generated stateSpace C; trivial components (no product or no type) are not states. The second conjunct is the cardinality identity with Set.ncard on finite sets.
import Mathlib import Definitions.Def_ConsiderChoose_StateSpace_Model
namespace ConsiderChoose.StateSpace
theorem lemma_2 {N K : ℕ} (C : Fin K → Finset (Fin N)) :
Set.InjOn (fun p : Finset (Fin N) × Finset (Fin K) => Phi C p.1 p.2) (stateSpace C) ∧
((fun p : Finset (Fin N) × Finset (Fin K) => Phi C p.1 p.2) '' stateSpace C).ncard =
(stateSpace C).ncard := by sorry
end ConsiderChoose.StateSpace
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.