Claim 1, p. 15 — if Φ(S₁,T₁) = Φ(S₂,T₂) and u′ ∈ T₂ \ T₁, then C_{u′} ∩ S₁ = ∅
ProvedConsiderChoose.StateSpace.claim_1Let be consideration sets over products numbered in the common preference order, and let be the state space of the dynamic program of §3: the subproblems generated from the nontrivial connected components of by repeatedly stocking or skipping the most preferred remaining product and splitting the residual graph into its nontrivial components. Let .
Suppose satisfy , and let . Then
In the paper this claim is the key step of the proof of Lemma 2 (injectivity of on ), which argues by contradiction from .
Formalization Note. The hypotheses are exactly those under which the paper states and proves the claim (Appendix EC.1.1). Because the claim sits inside a proof by contradiction, Lemma 2 shows that they can never all hold, so this statement is equivalent, given the rest of the paper's argument, to the key step of Lemma 2; it is not a statement about an inhabited situation.
import Mathlib import Definitions.Def_ConsiderChoose_StateSpace_Model
namespace ConsiderChoose.StateSpace
theorem claim_1 {N K : ℕ} (C : Fin K → Finset (Fin N))
{S₁ S₂ : Finset (Fin N)} {T₁ T₂ : Finset (Fin K)}
(h₁ : Reachable C S₁ T₁) (h₂ : Reachable C S₂ T₂) (hΦ : Phi C S₁ T₁ = Phi C S₂ T₂)
{u' : Fin K} (hu : u' ∈ T₂ \ T₁) : C u' ∩ S₁ = ∅ := by sorry
end ConsiderChoose.StateSpace
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.