Lemma 2, p. 17 — Möbius inversion over supersets: p(a,S) = Σ_{T⊇S} q(a,T) for all S ∋ a iff (9) for all S ∋ a
ProvedProConChoice.Rational.lemma_2combinatoricsmobius-inversionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1
Let be a finite set, , and let be any two real-valued functions of an alternative and a subset of . Then the following two families of identities are equivalent:
and
This is Möbius inversion on the lattice of supersets of . It is what makes the transform of (9) recover by (8), the identity (24) at the end of Step 1 of the paper's proof.
Formalization Note The equivalence is between the two families for a fixed ; for a single set the two identities are not equivalent. No probability hypothesis is needed, so and are arbitrary functions X → Finset X → ℝ; the paper's convention for is not used, since only sets containing occur.
Preamble
import Mathlib
Formal statement
namespace ProConChoice.Rational
/-- Lemma 2 (p. 17): Möbius inversion over supersets. For a fixed alternative `a`, the family of
identities (8) `p(a, S) = ∑_{S ⊆ T ⊆ X} q(a, T)` (all `S ∋ a`) holds iff the family (9)
`q(a, S) = ∑_{S ⊆ T ⊆ X} (-1)^{|T|-|S|} p(a, T)` (all `S ∋ a`) holds. -/
theorem lemma_2 {X : Type*} [Fintype X] [DecidableEq X]
(p q : X → Finset X → ℝ) (a : X) :
(∀ S : Finset X, a ∈ S →
p a S = ∑ T ∈ (Finset.univ : Finset X).powerset.filter (fun T => S ⊆ T), q a T) ↔
(∀ S : Finset X, a ∈ S →
q a S = ∑ T ∈ (Finset.univ : Finset X).powerset.filter (fun T => S ⊆ T),
(-1 : ℝ) ^ (T.card - S.card) * p a T) := by sorry
end ProConChoice.Rational
Source
Dogan & Yildiz, Every choice function is pro-con rationalizable, SSRN 3085542 (January 10, 2021), p. 17, Lemma 2, eqs. (8) and (9)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.