Borel complexity, reductions, and well-founded tree indices
DefinitionModNullCore20261109The bundle defines and sets by countable unions of closed and compact sets. It defines by countable unions of sets and by countable intersections of sets, with their intersection. The separate difference-of-two- predicate is a stronger refinement, not a definition of all 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.
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
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 sets.
IsFSigma. For any type equipped with a topology, and any subset , this predicate means that there exists a sequence of subsets of such that every is closed and . The natural-number index includes . The topology and are otherwise unrestricted, so 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 equipped with a topology, and any subset , this predicate means that there exists a sequence of subsets of such that every is compact and . The natural-number index includes . There is no separation assumption on the topology; in particular, the declaration only requires compactness of each , without an additional closedness condition. The type may be empty, and the sequence may contain empty or repeated sets and need not be nested.
IsSigma3. For any type equipped with a topology, and any subset , this predicate means that there exists a sequence of subsets of such that and, for every , there exists an at most countable collection of open subsets of with . The natural-number index includes , and an empty collection is permitted, in which case its intersection is all of . 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 equipped with a topology, and any subset , this predicate means that there exists a sequence of subsets of such that and, for every , there exists a sequence of closed subsets of with . Both natural-number indices include . The type and topology are otherwise unrestricted, may be empty, all of the displayed sequences may contain empty or repeated sets, and no nesting condition is imposed.
IsDelta3. For any type equipped with a topology, and any subset , this predicate requires both of the following representations of the same set : there exists a sequence with , where for every there is an at most countable collection of open subsets of such that ; and there exists a sequence with , where for every there exists a sequence of closed subsets of such that . The witnesses for the two representations are independent. Every natural-number index includes ; an empty collection of open sets has intersection , 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 equipped with a topology, and any subset , this predicate means that there exist subsets , a sequence of closed subsets of , and a sequence of closed subsets of , with , , and ; thus means exactly and . Both indices include . There is no requirement that , that the sequences be nested, or that any set be nonempty; and its topology are otherwise unrestricted and may be empty.
BorelReducible. For any types and , each equipped with a measurable-space structure, and any binary relations on and on , this predicate means that there exists a function such that the inverse image under of every measurable subset of is a measurable subset of , and such that, for every , holds if and only if 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 . Empty types are allowed: if is empty measurability is automatic, the relation condition is vacuous, and the empty function exists even when is empty; if is nonempty and is empty no function witness exists.
StandardBorelEquivalence. This structure consists of a carrier type in the base type universe, a measurable-space structure on , a proof that there exists a Polish topology on whose Borel measurable sets are exactly those of the specified measurable-space structure, a binary relation on , a proof that is an equivalence relation, and a proof that is measurable for the product measurable-space structure. The equivalence proof requires for every , whenever for every , and whenever and for every . 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 , 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 .
PrefixClosed. For a function from finite lists of natural numbers to the two Boolean values, this predicate means that for every finite list of natural numbers and every natural number , if takes the value true on the list obtained by appending the single entry to the end of , then takes the value true on . The list may be empty and may be . The condition has no requirement that ever be true, so the constantly false function satisfies it; for each appended list on which is false, that particular implication is vacuous.
TreeSpace. This type consists of pairs formed by a Boolean-valued function on all finite lists of natural numbers and a proof that for every finite list and every natural number , implies , where is with the one entry appended. Finite lists include the empty list and natural numbers include . 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 on finite lists of natural numbers together with a proof that acceptance of implies acceptance of for every finite list and natural number , this predicate means that there exists a function such that, for every , . Here the displayed list is the list of exactly the first entries, and for it is the empty list, which must therefore also be accepted. Both 's indices and its values range over all natural numbers including ; no further property of is required. In particular, the constantly false Boolean function has no such witness.
WF. This type consists of a Boolean-valued function on all finite lists of natural numbers, a proof that implies for every finite list and natural number , and a proof that there does not exist a function for which for every . The list at is empty; equivalently, for each function , some , possibly , has this length- list assigned false. All entries and indices may be , and the constantly false Boolean function satisfies both proof conditions and is admitted.
IsInvariant. For any type , any binary relation on , and any subset , this predicate means that for every , if holds then if and only if . There are no topological, measurable-space, or equivalence-relation hypotheses. The type may be empty, and the implication is vacuous for each pair for which is false; in particular an everywhere-false relation makes every subset satisfy the predicate. The empty subset and all of satisfy the predicate for any relation.
LInfinityRelation. For any two functions , this predicate means that there exists one real number such that for every natural number , including . The same must work for all coordinates, the inequalities are non-strict, and neither sequence is required individually to be bounded. The quantified real number has no explicit sign restriction, although the coordinate forces every successful witness to satisfy . A witness is permitted and requires equality of the two functions at every coordinate.
Confirmed by the mission captain (proposal self-audit).