Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

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

Proved
ProConChoice.Rational.lemma_2

by mikedeng1 · Oct 21, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsmobius-inversionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1

Let XXX be a finite set, a∈Xa \in Xa∈X, and let p,qp, qp,q be any two real-valued functions of an alternative and a subset of XXX. Then the following two families of identities are equivalent:

p(a,S)=∑S⊆T⊆Xq(a,T)for every S∋a(8)p(a, S) = \sum_{S \subseteq T \subseteq X} q(a, T) \quad \text{for every } S \ni a \qquad (8)p(a,S)=S⊆T⊆X∑​q(a,T)for every S∋a(8)

and

q(a,S)=∑S⊆T⊆X(−1)∣T∣−∣S∣ p(a,T)for every S∋a.(9)q(a, S) = \sum_{S \subseteq T \subseteq X} (-1)^{|T| - |S|}\, p(a, T) \quad \text{for every } S \ni a. \qquad (9)q(a,S)=S⊆T⊆X∑​(−1)∣T∣−∣S∣p(a,T)for every S∋a.(9)

This is Möbius inversion on the lattice of supersets of {a}\{a\}{a}. It is what makes the transform qqq of (9) recover ppp 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 aaa; for a single set SSS the two identities are not equivalent. No probability hypothesis is needed, so ppp and qqq are arbitrary functions X → Finset X → ℝ; the paper's convention q(a,S)=q(a,S∪{a})q(a, S) = q(a, S \cup \{a\})q(a,S)=q(a,S∪{a}) for a∉Sa \notin Sa∈/S is not used, since only sets containing aaa 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
  • Endorsed by Shuze Chen · Oct 21, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 21, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me