Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1 — no Borel upper bound for all FσF_\sigmaFσ​ equivalence relations

Proved
NoBorelUpperBoundFSigma.theorem1

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

borel-reducibilitydescriptive-set-theoryequivalence-relationspolish-spaces

For every Polish space Y, there is no equivalence relation F on Y such that its graph is Borel and every equivalence relation E with an F-sigma graph on every Polish space X Borel reduces to F. Explicitly, there is no such F for which every pair (X,E)(X,E)(X,E) admits a Borel map f:X→Yf:X\to Yf:X→Y satisfying E(x,x′)  ⟺  F(f(x),f(x′))E(x,x^{\prime})\iff F(f(x),f(x^{\prime}))E(x,x′)⟺F(f(x),f(x′)) for all source pairs. The target graph may have arbitrary Borel complexity; no F-sigma hypothesis is imposed on it. The source spaces are not required to be compact or sigma-compact.

Formalization note. Polish sources range over the ordinary Lean type universe, containing the standard presentations of all Polish spaces; the target universe is arbitrary. Empty spaces are permitted. Borel measurability and graph Borelness use the specified topologies.

Preamble
import Definitions.Def_NoBorelUpperBound20261101

set_option autoImplicit false
universe u

Formal statement
theorem NoBorelUpperBoundFSigma.theorem1
    {Y : Type u} [TopologicalSpace Y] [PolishSpace Y] :
    ¬ ∃ F : Setoid Y,
      NoBorelUpperBoundFSigma.IsBorelRelation F.r ∧
      NoBorelUpperBoundFSigma.IsFSigmaUpperBound F.r := by sorry
Source
No Borel upper bound for the F_sigma equivalence relations, research proof note dated 1 November 2026, supplied manuscript UniversalBorelEquivalence-20261101.tex, Section 1, Theorem 1, lines 48–51; conventions in lines 35–46.
Read-back

What the Lean code literally says, in plain math · GPT-6 (Codex; exact runtime model identifier unavailable)

For every universe level uuu and every type YYY at that level, equipped with a topology for which YYY is a Polish space, there does not exist an equivalence relation FFF on YYY (a binary relation that is reflexive, symmetric, and transitive) satisfying both of the following properties: its graph {(y,z)∈Y×Y:F(y,z)}\{(y,z)\in Y\times Y:F(y,z)\}{(y,z)∈Y×Y:F(y,z)} is a Borel subset of Y×YY\times YY×Y with the product topology; and, for every type XXX in universe level 000, every topology on XXX for which XXX is Polish, and every equivalence relation EEE on XXX, if there is a sequence (Cn)n∈N(C_n)_{n\in\mathbb N}(Cn​)n∈N​ of closed subsets of X×XX\times XX×X such that {(x,x′)∈X×X:E(x,x′)}=⋃n∈NCn\{(x,x')\in X\times X:E(x,x')\}=\bigcup_{n\in\mathbb N}C_n{(x,x′)∈X×X:E(x,x′)}=⋃n∈N​Cn​, then there exists a function f:X→Yf:X\to Yf:X→Y such that the inverse image under fff of every Borel subset of YYY is a Borel subset of XXX, using the Borel sigma algebras generated by their specified topologies, and such that for all x,x′∈Xx,x'\in Xx,x′∈X, E(x,x′)E(x,x')E(x,x′) holds if and only if F(f(x),f(x′))F(f(x),f(x'))F(f(x),f(x′)) holds. Neither XXX nor YYY is assumed nonempty, so the quantifiers include empty Polish spaces; the closed-set sequence is indexed by all natural numbers, including 000, and its members may be empty or repeated. The reduction function is not required to be injective or surjective.

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

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