Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Borel complexity, reductions, and well-founded tree indices

Definition
ModNullCore20261109

by username · Nov 9, 2026 · Mathlib c5ea003 (Lean v4.30.0)

borel-reducibilitydescriptive-set-theoryhaar-measuremeasure-theory

The bundle defines FσF_\sigmaFσ​ and KσK_\sigmaKσ​ sets by countable unions of closed and compact sets. It defines Σ30\Sigma^0_3Σ30​ by countable unions of GδG_\deltaGδ​ sets and Π30\Pi^0_3Π30​ by countable intersections of FσF_\sigmaFσ​ sets, with Δ30\Delta^0_3Δ30​ their intersection. The separate difference-of-two-FσF_\sigmaFσ​ predicate is a stronger refinement, not a definition of all Δ30\Delta^0_3Δ30​ sets.

A Borel reduction is a measurable map preserving and reflecting the relation for every pair. A standard Borel equivalence bundles its carrier, actual measurable structure, standard-Borel property, equivalence laws, and measurable graph; empty target spaces are permitted. Tree codes are prefix-closed Boolean functions on finite natural-number lists. The index type consists of those codes admitting no infinite natural-number branch; the empty tree is included, and the index type is not asserted countable. The bundle also defines invariant domains and the bounded-difference relation on real sequences.

Definition code
import Mathlib.MeasureTheory.Constructions.Polish.Basic
import Mathlib.MeasureTheory.Measure.Typeclasses.Probability
import Mathlib.Topology.GDelta.Basic
import Mathlib.Data.List.OfFn

set_option autoImplicit false

namespace ModNullUniversality

def IsFSigma {X : Type*} [TopologicalSpace X] (s : Set X) : Prop :=
  ∃ C : ℕ → Set X, (∀ n, IsClosed (C n)) ∧ s = ⋃ n, C n

def IsKSigma {X : Type*} [TopologicalSpace X] (s : Set X) : Prop :=
  ∃ C : ℕ → Set X, (∀ n, IsCompact (C n)) ∧ s = ⋃ n, C n

def IsSigma3 {X : Type*} [TopologicalSpace X] (s : Set X) : Prop :=
  ∃ C : ℕ → Set X, (∀ n, IsGδ (C n)) ∧ s = ⋃ n, C n

def IsPi3 {X : Type*} [TopologicalSpace X] (s : Set X) : Prop :=
  ∃ C : ℕ → Set X, (∀ n, IsFSigma (C n)) ∧ s = ⋂ n, C n

def IsDelta3 {X : Type*} [TopologicalSpace X] (s : Set X) : Prop :=
  IsSigma3 s ∧ IsPi3 s

def DifferenceFSigma {X : Type*} [TopologicalSpace X] (s : Set X) : Prop :=
  ∃ A B : Set X, IsFSigma A ∧ IsFSigma B ∧ s = A \ B

def BorelReducible {X Y : Type*} [MeasurableSpace X] [MeasurableSpace Y]
    (E : X → X → Prop) (F : Y → Y → Prop) : Prop :=
  ∃ f : X → Y, Measurable f ∧ ∀ x y, E x y ↔ F (f x) (f y)

structure StandardBorelEquivalence where
  Carrier : Type
  [measurable : MeasurableSpace Carrier]
  [standard : StandardBorelSpace Carrier]
  rel : Carrier → Carrier → Prop
  equivalence : Equivalence rel
  measurable_graph : MeasurableSet {p : Carrier × Carrier | rel p.1 p.2}

attribute [instance] StandardBorelEquivalence.measurable StandardBorelEquivalence.standard

abbrev Node := List ℕ

def PrefixClosed (T : Node → Bool) : Prop :=
  ∀ s n, T (s ++ [n]) = true → T s = true

def TreeSpace := {T : Node → Bool // PrefixClosed T}

def HasBranch (T : TreeSpace) : Prop :=
  ∃ b : ℕ → ℕ, ∀ n, T.val (List.ofFn (fun i : Fin n => b i)) = true

def WF := {T : TreeSpace // ¬ HasBranch T}

def IsInvariant {X : Type*} (E : X → X → Prop) (C : Set X) : Prop :=
  ∀ x y, E x y → (x ∈ C ↔ y ∈ C)

def LInfinityRelation (x y : ℕ → ℝ) : Prop :=
  ∃ M : ℝ, ∀ n, |x n - y n| ≤ M

end ModNullUniversality
Source
Universality modulo null sets in the Borel hierarchy, user-supplied unpublished manuscript dated 9 November 2026; SHA-256 48745c75427f83370292c2e4cf91ec06377e80472252db0182599edcd05e2d97, Sections 2 and 5; the bounded-difference benchmark is specified in Section 6.
Read-back

What the Lean code literally says, in plain math · Codex; exact runtime model identifier unavailable

Blind read-back of the core declarations

Runtime author: Codex. The exact runtime model identifier is unavailable. This read-back was written from the auditor instructions, the core Lean file, and the imported Mathlib definitions of standard Borel spaces and GδG_\deltaGδ​ sets.

IsFSigma. For any type XXX equipped with a topology, and any subset s⊆Xs\subseteq Xs⊆X, this predicate means that there exists a sequence (Cn)n∈N(C_n)_{n\in\mathbb N}(Cn​)n∈N​ of subsets of XXX such that every CnC_nCn​ is closed and s=⋃n∈NCns=\bigcup_{n\in\mathbb N}C_ns=⋃n∈N​Cn​. The natural-number index includes 000. The topology and XXX are otherwise unrestricted, so XXX may be empty; the sets in the sequence may be empty or repeated, and no nesting or nonemptiness condition is imposed.

IsKSigma. For any type XXX equipped with a topology, and any subset s⊆Xs\subseteq Xs⊆X, this predicate means that there exists a sequence (Cn)n∈N(C_n)_{n\in\mathbb N}(Cn​)n∈N​ of subsets of XXX such that every CnC_nCn​ is compact and s=⋃n∈NCns=\bigcup_{n\in\mathbb N}C_ns=⋃n∈N​Cn​. The natural-number index includes 000. There is no separation assumption on the topology; in particular, the declaration only requires compactness of each CnC_nCn​, without an additional closedness condition. The type XXX may be empty, and the sequence may contain empty or repeated sets and need not be nested.

IsSigma3. For any type XXX equipped with a topology, and any subset s⊆Xs\subseteq Xs⊆X, this predicate means that there exists a sequence (Cn)n∈N(C_n)_{n\in\mathbb N}(Cn​)n∈N​ of subsets of XXX such that s=⋃n∈NCns=\bigcup_{n\in\mathbb N}C_ns=⋃n∈N​Cn​ and, for every nnn, there exists an at most countable collection Un\mathcal U_nUn​ of open subsets of XXX with Cn=⋂U∈UnUC_n=\bigcap_{U\in\mathcal U_n}UCn​=⋂U∈Un​​U. The natural-number index includes 000, and an empty collection Un\mathcal U_nUn​ is permitted, in which case its intersection is all of XXX. The type and topology are otherwise unrestricted, the type may be empty, the outer sequence may contain empty or repeated sets, and no nesting condition is imposed.

IsPi3. For any type XXX equipped with a topology, and any subset s⊆Xs\subseteq Xs⊆X, this predicate means that there exists a sequence (Cn)n∈N(C_n)_{n\in\mathbb N}(Cn​)n∈N​ of subsets of XXX such that s=⋂n∈NCns=\bigcap_{n\in\mathbb N}C_ns=⋂n∈N​Cn​ and, for every nnn, there exists a sequence (Dn,m)m∈N(D_{n,m})_{m\in\mathbb N}(Dn,m​)m∈N​ of closed subsets of XXX with Cn=⋃m∈NDn,mC_n=\bigcup_{m\in\mathbb N}D_{n,m}Cn​=⋃m∈N​Dn,m​. Both natural-number indices include 000. The type and topology are otherwise unrestricted, XXX may be empty, all of the displayed sequences may contain empty or repeated sets, and no nesting condition is imposed.

IsDelta3. For any type XXX equipped with a topology, and any subset s⊆Xs\subseteq Xs⊆X, this predicate requires both of the following representations of the same set sss: there exists a sequence (Cn)n∈N(C_n)_{n\in\mathbb N}(Cn​)n∈N​ with s=⋃nCns=\bigcup_n C_ns=⋃n​Cn​, where for every nnn there is an at most countable collection Un\mathcal U_nUn​ of open subsets of XXX such that Cn=⋂U∈UnUC_n=\bigcap_{U\in\mathcal U_n}UCn​=⋂U∈Un​​U; and there exists a sequence (Dn)n∈N(D_n)_{n\in\mathbb N}(Dn​)n∈N​ with s=⋂nDns=\bigcap_n D_ns=⋂n​Dn​, where for every nnn there exists a sequence (Fn,m)m∈N(F_{n,m})_{m\in\mathbb N}(Fn,m​)m∈N​ of closed subsets of XXX such that Dn=⋃mFn,mD_n=\bigcup_m F_{n,m}Dn​=⋃m​Fn,m​. The witnesses for the two representations are independent. Every natural-number index includes 000; an empty collection of open sets has intersection XXX, empty or repeated sequence terms are permitted, and no nesting is required. The type may be empty and its topology has no further assumptions.

DifferenceFSigma. For any type XXX equipped with a topology, and any subset s⊆Xs\subseteq Xs⊆X, this predicate means that there exist subsets A,B⊆XA,B\subseteq XA,B⊆X, a sequence (An)n∈N(A_n)_{n\in\mathbb N}(An​)n∈N​ of closed subsets of XXX, and a sequence (Bn)n∈N(B_n)_{n\in\mathbb N}(Bn​)n∈N​ of closed subsets of XXX, with A=⋃nAnA=\bigcup_n A_nA=⋃n​An​, B=⋃nBnB=\bigcup_n B_nB=⋃n​Bn​, and s=A∖Bs=A\setminus Bs=A∖B; thus x∈sx\in sx∈s means exactly x∈Ax\in Ax∈A and x∉Bx\notin Bx∈/B. Both indices include 000. There is no requirement that B⊆AB\subseteq AB⊆A, that the sequences be nested, or that any set be nonempty; XXX and its topology are otherwise unrestricted and XXX may be empty.

BorelReducible. For any types XXX and YYY, each equipped with a measurable-space structure, and any binary relations EEE on XXX and FFF on YYY, this predicate means that there exists a function f:X→Yf:X\to Yf:X→Y such that the inverse image under fff of every measurable subset of YYY is a measurable subset of XXX, and such that, for every x,y∈Xx,y\in Xx,y∈X, E(x,y)E(x,y)E(x,y) holds if and only if F(f(x),f(y))F(f(x),f(y))F(f(x),f(y)) holds. The relations are arbitrary predicates, with no equivalence-relation or measurability hypotheses, and the measurable spaces have no standard-Borel or topological assumptions. There is no injectivity or surjectivity requirement on fff. Empty types are allowed: if XXX is empty measurability is automatic, the relation condition is vacuous, and the empty function exists even when YYY is empty; if XXX is nonempty and YYY is empty no function witness exists.

StandardBorelEquivalence. This structure consists of a carrier type XXX in the base type universe, a measurable-space structure on XXX, a proof that there exists a Polish topology on XXX whose Borel measurable sets are exactly those of the specified measurable-space structure, a binary relation RRR on XXX, a proof that RRR is an equivalence relation, and a proof that {(x,y)∈X×X:R(x,y)}\{(x,y)\in X\times X:R(x,y)\}{(x,y)∈X×X:R(x,y)} is measurable for the product measurable-space structure. The equivalence proof requires R(x,x)R(x,x)R(x,x) for every x∈Xx\in Xx∈X, R(y,x)R(y,x)R(y,x) whenever R(x,y)R(x,y)R(x,y) for every x,y∈Xx,y\in Xx,y∈X, and R(x,z)R(x,z)R(x,z) whenever R(x,y)R(x,y)R(x,y) and R(y,z)R(y,z)R(y,z) for every x,y,z∈Xx,y,z\in Xx,y,z∈X. A Polish topology means a topology compatible with a complete separable metric; the structure records its existence rather than a chosen topology. The carrier may be empty, in which case the three equivalence conditions are vacuous and the graph is empty. The stored measurable-space structure and standard-Borel proof are registered for automatic use as instances on the carrier.

Node. This abbreviation denotes the type of all finite lists of natural numbers. A list may have length 000, in which case it is the empty list, and a list of positive finite length is ordered and may contain repetitions; its entries may include 000.

PrefixClosed. For a function TTT from finite lists of natural numbers to the two Boolean values, this predicate means that for every finite list sss of natural numbers and every natural number nnn, if TTT takes the value true on the list obtained by appending the single entry nnn to the end of sss, then TTT takes the value true on sss. The list sss may be empty and nnn may be 000. The condition has no requirement that TTT ever be true, so the constantly false function satisfies it; for each appended list on which TTT is false, that particular implication is vacuous.

TreeSpace. This type consists of pairs formed by a Boolean-valued function TTT on all finite lists of natural numbers and a proof that for every finite list sss and every natural number nnn, T(s+ ⁣ ⁣+[n])=trueT(s\mathbin{+\!\!+}[n])=\mathrm{true}T(s++[n])=true implies T(s)=trueT(s)=\mathrm{true}T(s)=true, where s+ ⁣ ⁣+[n]s\mathbin{+\!\!+}[n]s++[n] is sss with the one entry nnn appended. Finite lists include the empty list and natural numbers include 000. The constantly false function is admitted, so an element need not accept the empty list or any other list; no other property of the Boolean-valued function is required.

HasBranch. For any element of the type consisting of a Boolean-valued function TTT on finite lists of natural numbers together with a proof that acceptance of s+ ⁣ ⁣+[k]s\mathbin{+\!\!+}[k]s++[k] implies acceptance of sss for every finite list sss and natural number kkk, this predicate means that there exists a function b:N→Nb:\mathbb N\to\mathbb Nb:N→N such that, for every n∈Nn\in\mathbb Nn∈N, T([b(0),b(1),…,b(n−1)])=trueT([b(0),b(1),\ldots,b(n-1)])=\mathrm{true}T([b(0),b(1),…,b(n−1)])=true. Here the displayed list is the list of exactly the first nnn entries, and for n=0n=0n=0 it is the empty list, which must therefore also be accepted. Both bbb's indices and its values range over all natural numbers including 000; no further property of bbb is required. In particular, the constantly false Boolean function has no such witness.

WF. This type consists of a Boolean-valued function TTT on all finite lists of natural numbers, a proof that T(s+ ⁣ ⁣+[k])=trueT(s\mathbin{+\!\!+}[k])=\mathrm{true}T(s++[k])=true implies T(s)=trueT(s)=\mathrm{true}T(s)=true for every finite list sss and natural number kkk, and a proof that there does not exist a function b:N→Nb:\mathbb N\to\mathbb Nb:N→N for which T([b(0),…,b(n−1)])=trueT([b(0),\ldots,b(n-1)])=\mathrm{true}T([b(0),…,b(n−1)])=true for every n∈Nn\in\mathbb Nn∈N. The list at n=0n=0n=0 is empty; equivalently, for each function b:N→Nb:\mathbb N\to\mathbb Nb:N→N, some n∈Nn\in\mathbb Nn∈N, possibly 000, has this length-nnn list assigned false. All entries and indices may be 000, and the constantly false Boolean function satisfies both proof conditions and is admitted.

IsInvariant. For any type XXX, any binary relation EEE on XXX, and any subset C⊆XC\subseteq XC⊆X, this predicate means that for every x,y∈Xx,y\in Xx,y∈X, if E(x,y)E(x,y)E(x,y) holds then x∈Cx\in Cx∈C if and only if y∈Cy\in Cy∈C. There are no topological, measurable-space, or equivalence-relation hypotheses. The type XXX may be empty, and the implication is vacuous for each pair for which E(x,y)E(x,y)E(x,y) is false; in particular an everywhere-false relation makes every subset satisfy the predicate. The empty subset and all of XXX satisfy the predicate for any relation.

LInfinityRelation. For any two functions x,y:N→Rx,y:\mathbb N\to\mathbb Rx,y:N→R, this predicate means that there exists one real number MMM such that ∣x(n)−y(n)∣≤M\lvert x(n)-y(n)\rvert\le M∣x(n)−y(n)∣≤M for every natural number nnn, including 000. The same MMM must work for all coordinates, the inequalities are non-strict, and neither sequence is required individually to be bounded. The quantified real number MMM has no explicit sign restriction, although the coordinate n=0n=0n=0 forces every successful witness to satisfy M≥0M\ge0M≥0. A witness M=0M=0M=0 is permitted and requires equality of the two functions at every coordinate.

Human review
  • Endorsed by Shuze Chen · Nov 9, 2026

  • Endorsed by username · Nov 9, 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