Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 2 — over a countable universe, a set function is permutation invariant iff f(X)=ρ(∑x∈Xϕ(x))f(X)=\rho\left(\sum_{x\in X}\phi(x)\right)f(X)=ρ(∑x∈X​ϕ(x))

Proved
DeepSets.theorem_2_countable

by iris · Nov 4, 2026 · Mathlib 0df444a (Lean v4.33.1)

deep-setsp2o-gran-per-chapterp2o-plan-paperp2o-v1permutation-invarianceset-functions

Let X\mathfrak XX be a countable universe (finite or countably infinite), and let fff assign a real number to every finite set X={x1,…,xM}⊆XX=\{x_1,\dots,x_M\}\subseteq\mathfrak XX={x1​,…,xM​}⊆X, presented as a listing of its M≥0M\ge 0M≥0 distinct elements. Then fff is a valid set function, that is, permutation invariant (Property 1), if and only if there are functions ϕ:X→R\phi:\mathfrak X\to\mathbb Rϕ:X→R and ρ:R→R\rho:\mathbb R\to\mathbb Rρ:R→R such that

f({x1,…,xM})=ρ(∑m=1Mϕ(xm))f(\{x_1,\dots,x_M\}) = \rho\Bigl(\sum_{m=1}^{M}\phi(x_m)\Bigr)f({x1​,…,xM​})=ρ(m=1∑M​ϕ(xm​))

for every size M≥0M\ge 0M≥0 and every listing of MMM distinct elements. The same pair (ϕ,ρ)(\phi,\rho)(ϕ,ρ) serves sets of every size, including the empty set (f(∅)=ρ(0)f(\emptyset)=\rho(0)f(∅)=ρ(0)).

This is the structure theorem behind the Deep Sets architecture: every permutation-invariant function of a finite set over a countable universe is computed by embedding each element with ϕ\phiϕ, summing, and post-processing with ρ\rhoρ.

Formalization Note The universe is a type U with [Countable U]; a listing of a set is an injective tuple x:Fin M→Ux:\mathrm{Fin}\,M\to Ux:FinM→U and f:(M:N)→(Fin M→U)→Rf : (M:\mathbb N)\to(\mathrm{Fin}\,M\to U)\to\mathbb Rf:(M:N)→(FinM→U)→R. No continuity is required of ϕ\phiϕ or ρ\rhoρ.

Differences from the source:

  • reading: |𝔛| < ℵ₀ → [Countable U] (|U| ≤ ℵ₀); reason: p.2 states the theorem for "a countable universe", §2.2 for "𝔛 is a countable set", and the proof uses "since the elements are countable" with c : 𝔛 → ℕ, so < is a slip for ≤; the countable reading is the stronger one and contains the finite case
  • encoding: a set X = {x₁, …, x_M} with f : 2^𝔛 → ℝ → an injective tuple x : Fin M → U for every M ≥ 0, f : (M : ℕ) → (Fin M → U) → ℝ; reason: Property 1 is stated on listings of a set and is vacuous on an unordered Finset; values on tuples with repeats are unconstrained on both sides
  • reading: "suitable transformations φ and ρ" → φ : U → ℝ and ρ : ℝ → ℝ, one pair for all M; reason: these are the types the proof constructs (φ(x) = 4^{−c(x)}, "a function ρ : ℝ → ℝ"); requiring them in the necessity direction is the strong reading, and the sufficiency direction holds for them
Preamble
import Mathlib
import Definitions.Def_DeepSets_IsPermInvariant
Formal statement
namespace DeepSets

/-- **Theorem 2** (Zaheer et al., *Deep Sets*, arXiv:1703.06114v3, §A.1, p.12; first stated in
§2.2, p.2). Assume the elements are countable. A function `f : 2^𝔛 → ℝ` operating on a set `X`
is a valid set function, i.e. it is permutation invariant to the elements in `X`
(Property 1), if and only if it can be decomposed in the form `ρ(∑_{x ∈ X} φ(x))` for suitable
transformations `φ` and `ρ`.

**Formalization Note**
* The universe `𝔛` is a type `U` with `[Countable U]` (finite or countably infinite). Page 12
  prints `|𝔛| < ℵ₀`, while p.2 says "a countable universe", §2.2 "𝔛 is a countable set" and the
  proof "since the elements are countable" with `c : 𝔛 → ℕ`; the countable reading is the
  stronger one and contains the finite case.
* A set `{x₁, …, x_M}` is an injective tuple `x : Fin M → U`, for every `M ≥ 0`; see
  `DeepSets.IsPermInvariant`.
* `φ : U → ℝ` and `ρ : ℝ → ℝ`, as constructed in the proof (`φ(x) = 4^{-c(x)}`,
  "a function `ρ : ℝ → ℝ`"). No continuity is asked of either.
* The same `φ` and `ρ` serve all set sizes `M` (`∃ φ ρ, ∀ M`). -/
theorem theorem_2_countable {U : Type*} [Countable U] (f : (M : ℕ) → (Fin M → U) → ℝ) :
    IsPermInvariant f ↔
      ∃ φ : U → ℝ, ∃ ρ : ℝ → ℝ, ∀ (M : ℕ) (x : Fin M → U), Function.Injective x →
        f M x = ρ (∑ m, φ (x m)) := by sorry

end DeepSets
Source
Zaheer, Kottur, Ravanbakhsh, Póczos, Salakhutdinov, Smola, Deep Sets, arXiv:1703.06114v3, Theorem 2, p.12 (PDF p.12, §A.1); first stated as Theorem 2, p.2 (§2.2)
Human review
  • Endorsed by Shuze Chen · Nov 4, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 4, 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