Proof of Theorem 2 — sufficiency, is permutation invariant
ProvedDeepSets.sum_decomposition_isPermInvariantdeep-setsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1permutation-invarianceset-functions
Let be any set of elements, and . The function that sends a listing of distinct elements of (any ) to
is permutation invariant (Property 1).
This is the sufficiency half of Theorem 2: every function of the form is a valid set function.
Differences from the source:
- generalization: countable universe 𝔛 → any type U; reason: the argument uses no countability; it specializes to a countable U
- encoding: a set X = {x₁, …, x_M} and Σ_{x∈X} φ(x) → an injective tuple x : Fin M → U and Σ_m φ(x m); reason: Lean convention; for distinct x_m the two sums are equal
Preamble
import Mathlib import Definitions.Def_DeepSets_IsPermInvariant
Formal statement
namespace DeepSets
/-- Zaheer et al., *Deep Sets*, arXiv:1703.06114v3, §A.1, proof of Theorem 2, p.12,
"The sufficiency follows by observing that the function `ρ(∑_{x∈X} φ(x))` satisfies the
permutation invariance condition."
For every `φ : U → ℝ` and `ρ : ℝ → ℝ`, the function `X = {x₁, …, x_M} ↦ ρ(∑_{m=1}^M φ(x_m))`
satisfies Property 1.
**Formalization Note** No countability is assumed: the statement holds for every type `U`. -/
theorem sum_decomposition_isPermInvariant {U : Type*} (φ : U → ℝ) (ρ : ℝ → ℝ) :
IsPermInvariant (fun (M : ℕ) (x : Fin M → U) => ρ (∑ m, φ (x m))) := by sorry
end DeepSets
Source
Zaheer, Kottur, Ravanbakhsh, Póczos, Salakhutdinov, Smola, Deep Sets, arXiv:1703.06114v3, §A.1, proof of Theorem 2, p.12 (PDF p.12), "The sufficiency follows by observing …"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.