Theorem 2 — over a countable universe, a set function is permutation invariant iff
ProvedDeepSets.theorem_2_countableLet be a countable universe (finite or countably infinite), and let assign a real number to every finite set , presented as a listing of its distinct elements. Then is a valid set function, that is, permutation invariant (Property 1), if and only if there are functions and such that
for every size and every listing of distinct elements. The same pair serves sets of every size, including the empty set ().
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 , summing, and post-processing with .
Formalization Note The universe is a type U with [Countable U]; a listing of a set is an injective tuple and . No continuity is required of or .
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
import Mathlib import Definitions.Def_DeepSets_IsPermInvariant
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
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.