Proof of Theorem 2 — a permutation-invariant function depends only on the set
ProvedDeepSets.invariant_factors_through_setdeep-setsp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1permutation-invarianceset-functions
Let be any set of elements and let assign a real number to every listing of distinct elements of , for every size . If is permutation invariant (Property 1), then is a function of the set of listed elements: there is a function on the finite subsets of such that
for every and every listing of distinct elements.
This is the first sentence of the proof of Theorem 2: since a set has no order, an invariant function is really a function on sets, and the rest of the proof decomposes that set function.
Formalization Note The set is the image of the injective tuple , a Finset U.
Differences from the source:
- reading: "Permutation invariance follows from the fact that sets have no particular order, hence any function on a set must not exploit any particular order either" → an invariant f factors through g : Finset U → ℝ via the image of the listing; reason: this is the precise content of the sentence in the proof; it is what the necessity argument (a function f(X) of the set X) uses
- generalization: countable universe 𝔛 → any type U; reason: the argument uses no countability; it specializes to a countable U
- encoding: a set {x₁, …, x_M} → an injective tuple x : Fin M → U, its set is Finset.univ.image x; reason: Lean convention; the same sets of every size M ≥ 0
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,
"Permutation invariance follows from the fact that sets have no particular order, hence any
function on a set must not exploit any particular order either."
A permutation-invariant `f` (Property 1) is a function of the set `{x₁, …, x_M}` alone: there is
`g` on finite subsets of `U` with `f M x = g {x₁, …, x_M}` for every size `M` and every injective
listing `x`.
**Formalization Note** The set `{x₁, …, x_M}` is `Finset.univ.image x`. No countability is
assumed: the statement holds for every type `U`, and specializes to the countable universe of
Theorem 2. -/
theorem invariant_factors_through_set {U : Type*} [DecidableEq U]
(f : (M : ℕ) → (Fin M → U) → ℝ) (hf : IsPermInvariant f) :
∃ g : Finset U → ℝ, ∀ (M : ℕ) (x : Fin M → U), Function.Injective x →
f M x = g (Finset.univ.image x) := 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), "Permutation invariance follows from the fact that sets have no particular order …"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.