Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Friedman--Stanley: Borelness of bounded-rank tree isomorphism

Proved
FSCofinality.bounded_tree_isomorphism_borel

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

borel-reducibilitycountable-structuresdescriptive-set-theoryfriedman-stanleymodel-theory

For each countable ordinal a, isomorphism of the rooted tree codes with global reverse-tree height at most a is a Borel subset of the product of that bounded-tree measurable space with itself. Empty and finite trees are included and branch multiplicities are retained. This is the classical bounded-rank Borelness result used in the hierarchy comparison; it does not assert Borelness of isomorphism on all well-founded or all countable trees at once.

For every α<ω1\alpha<\omega_1α<ω1​, with Tα\mathfrak T_\alphaTα​ carrying the inherited measurable structure,

{(T,U)∈Tα2:T≅U} is Borel.\{(T,U)\in\mathfrak T_\alpha^2:T\cong U\}\text{ is Borel}.{(T,U)∈Tα2​:T≅U} is Borel.
Preamble
import Definitions.Def_FSCofinalityTrees20261102
import Definitions.Def_FSCofinalityHierarchy20261102

set_option autoImplicit false

Formal statement
theorem FSCofinality.bounded_tree_isomorphism_borel
    (a : Ordinal.{0}) (ha_countable : a < Ordinal.omega 1) :
    @MeasurableSet
      ((FSCofinality.RootedTrees.treeRelation a).Carrier ×
        (FSCofinality.RootedTrees.treeRelation a).Carrier)
      ((FSCofinality.RootedTrees.treeRelation a).measurableSpace.prod
        (FSCofinality.RootedTrees.treeRelation a).measurableSpace)
      {p | (FSCofinality.RootedTrees.treeRelation a).rel p.1 p.2} := by sorry
Source
H. Friedman and L. Stanley, A Borel reducibility theory for classes of countable structures, Journal of Symbolic Logic 54 (1989), 894--914, https://doi.org/10.2307/2274750, Section 1.2.1, pages 901--902 (Borelness via multiplicity codes). Also supplied draft, Proposition 4.15 proof.
Read-back

What the Lean code literally says, in plain math · Codex (GPT-6 family; exact runtime model identifier not exposed to auditor)

Blind read-back: bounded tree isomorphism is Borel

Declaration: FSCofinality.bounded_tree_isomorphism_borel.

Auditor model: Codex; the exact runtime model identifier is unavailable in this session.

Read-back. For every ordinal aaa in the universe of ordinals represented by well-orders of small types, and every proof of the hypothesis a<ω1a<\omega_1a<ω1​, where ω1\omega_1ω1​ is the first uncountable ordinal, the following graph is measurable. Let S=N<ωS=\mathbb N^{<\omega}S=N<ω be the set of all finite lists of natural numbers, including the empty list, and let T\mathcal TT consist of all Boolean functions T:S→{false,true}T:S\to\{\mathrm{false},\mathrm{true}\}T:S→{false,true} satisfying T(s⌢[n])=true⇒T(s)=trueT(s^\frown[n])=\mathrm{true}\Rightarrow T(s)=\mathrm{true}T(s⌢[n])=true⇒T(s)=true for every list sss and every n∈Nn\in\mathbb Nn∈N. Give {false,true}S\{\mathrm{false},\mathrm{true}\}^S{false,true}S its product topology with discrete Boolean coordinates, give T\mathcal TT its subspace topology, and equip T\mathcal TT with the Borel sigma algebra of that topology. For T∈TT\in\mathcal TT∈T, write NT={s∈S:T(s)=true}N_T=\{s\in S:T(s)=\mathrm{true}\}NT​={s∈S:T(s)=true} for its actual set of nodes and say that sss is an immediate child of ttt precisely when s=t⌢[n]s=t^\frown[n]s=t⌢[n] for some n∈Nn\in\mathbb Nn∈N. Let CaC_aCa​ be the subtype of all T∈TT\in\mathcal TT∈T for which there exists a function ρ:NT→Ord⁡\rho:N_T\to\operatorname{Ord}ρ:NT​→Ord, with values in the same small-universe ordinals as aaa, such that ρ(s)<a\rho(s)<aρ(s)<a for every node sss, and ρ(s)<ρ(t)\rho(s)<\rho(t)ρ(s)<ρ(t) whenever sss is an immediate child of ttt. The function ρ\rhoρ is existentially quantified separately for each tree; it is not extra chosen data in an element of CaC_aCa​, and no least or canonical rank function is specified. Equip CaC_aCa​ with the sigma algebra induced from the Borel sigma algebra of T\mathcal TT by the inclusion Ca↪TC_a\hookrightarrow\mathcal TCa​↪T, namely the sets of the form Ca∩BC_a\cap BCa​∩B for Borel B⊆TB\subseteq\mathcal TB⊆T. The conclusion is that the set Ga⊆Ca×CaG_a\subseteq C_a\times C_aGa​⊆Ca​×Ca​ of all pairs (T,U)(T,U)(T,U) for which there exists a bijection e:NT→NUe:N_T\to N_Ue:NT​→NU​ satisfying, for every ordered pair of nodes s,t∈NTs,t\in N_Ts,t∈NT​, s=t⌢[n]s=t^\frown[n]s=t⌢[n] for some n∈Nn\in\mathbb Nn∈N if and only if e(s)=e(t)⌢[m]e(s)=e(t)^\frown[m]e(s)=e(t)⌢[m] for some m∈Nm\in\mathbb Nm∈N, belongs to the product of these two induced sigma algebras. Thus one bijection must preserve and reflect the immediate-child relation for all node pairs; the numerical entries appended to form children need not be preserved, and the existential bijection may depend on the pair (T,U)(T,U)(T,U). There are no additional quantified spaces, external measurable-space choices, or hypotheses on aaa beyond a<ω1a<\omega_1a<ω1​; in particular a=0a=0a=0, finite successors, and countable limit ordinals are included. The rank convention is the displayed strict bound on every node label, with children strictly below parents: leaves may receive label 000, the empty tree is allowed for every aaa because all requirements on nodes are vacuous, and the one-node tree can receive label 000 exactly when 0<a0<a0<a (so it is included at a=1a=1a=1). At a=0a=0a=0 only the empty tree belongs to CaC_aCa​; at a=1a=1a=1 only the empty tree and the tree whose sole node is the empty list belong to CaC_aCa​. A chain with kkk nodes is admitted exactly when the finite ordinal kkk is at most aaa. In the usual convention using the least well-founded node rank rrr, assigning a leaf rank 000, and defining tree height as sup⁡{r(s)+1:s∈NT}\sup\{r(s)+1:s\in N_T\}sup{r(s)+1:s∈NT​} with supremum 000 for the empty set, the empty and one-node trees have heights 000 and 111, respectively; the actual condition in the declaration remains the existence of the function ρ\rhoρ above. Every nonempty prefix-closed tree contains the empty list, so its root is present without a separate root datum; a child-preserving and child-reflecting bijection necessarily sends this root to the root. There is no requirement that the tree be infinite, have bounded finite branching, or contain every possible child; infinite node sets are allowed when the stated ordinal labeling exists, while an infinite descending chain of child ranks is excluded. The empty tree is isomorphic to itself and cannot be isomorphic to a nonempty tree, because a bijection of their actual node sets would not exist. The asserted measurability is relative to Ca×CaC_a\times C_aCa​×Ca​ with the specified product sigma algebra; the statement contains no separate assertion that CaC_aCa​ itself is Borel in T\mathcal TT and no assertion of a measurable choice of the bijections.

Reading scope: The target theorem file, its transitive Definitions/*.lean imports, and Mathlib definitions of the first uncountable ordinal and the subtype/product measurable-space constructions were consulted. No other theorem file, manuscript, informal statement, proposal metadata, or task history was consulted. The theorem source ends with a placeholder proof (by sorry); this document renders its asserted proposition and does not certify a completed proof.

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