Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proposition 4.15 — original tree hierarchy compared with the set-jump tower

Proved
FSCofinality.original_tree_comparison

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

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

For every nonzero countable ordinal a, there is a countable ordinal b such that isomorphism on the bounded-rank rooted tree class at bound a Borel reduces to the product-limit Friedman--Stanley relation J_b. Empty and finite trees and all branch multiplicities are included. This formalizes the first assertion of Proposition 4.15; no equality of the indices a and b, and no simultaneous Borel choice over ordinal codes, is asserted. The separate structural sentence-tower assertion is outside this milestone.

The comparison has independently quantified countable indices:

∀ 0<α<ω1 ∃β<ω1,≅Tα≤BJβ.\forall\,0<\alpha<\omega_1\ \exists\beta<\omega_1,\qquad \cong_{\mathfrak T_\alpha}\leq_B\mathsf J_\beta.∀0<α<ω1​ ∃β<ω1​,≅Tα​​≤B​Jβ​.
Preamble
import Definitions.Def_FSCofinalityHierarchy20261102
import Definitions.Def_FSCofinalityTrees20261102

set_option autoImplicit false

Formal statement
theorem FSCofinality.original_tree_comparison
    (a : Ordinal.{0}) (ha_pos : 0 < a) (ha_countable : a < Ordinal.omega 1) :
    ∃ b : Ordinal.{0}, b < Ordinal.omega 1 ∧
      (FSCofinality.RootedTrees.treeRelation a).Reduces (FSCofinality.fsTower b) := by sorry
Source
Friedman--Stanley cofinality and Borel completeness: A proposed negative answer to the Friedman--Stanley question, supplied research draft dated 2 November 2026, FriedmanStanleyQuestion.tex, Proposition 4.15, first assertion, lines 1701--1740; original tree codes: Friedman--Stanley (1989), Section 1.2.1, page 901.
Read-back

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

Read-back: FSCofinality.original_tree_comparison

Auditor model: GPT-6-based Codex agent; exact model identifier unavailable.

For every ordinal aaa in universe 000, assuming 0<a0<a0<a and a<ω1a<\omega_1a<ω1​, where ω1\omega_1ω1​ is the first uncountable ordinal, there exists an ordinal bbb in the same universe with b<ω1b<\omega_1b<ω1​ and a measurable function f:Xa→Ybf:X_a\to Y_bf:Xa​→Yb​ such that, for every T,U∈XaT,U\in X_aT,U∈Xa​, the underlying trees of TTT and UUU are isomorphic if and only if f(T) Eb f(U)f(T)\,E_b\,f(U)f(T)Eb​f(U). Here XaX_aXa​ consists of Boolean-valued functions on the finite lists of natural numbers, together with proofs of the following conditions: whenever the value at s⌢[n]s^\frown[n]s⌢[n] is true, the value at sss is true; and there exists a function ρ\rhoρ from the lists whose value is true to the universe-000 ordinals such that ρ(s)<a\rho(s)<aρ(s)<a for every such list sss and ρ(s)<ρ(t)\rho(s)<\rho(t)ρ(s)<ρ(t) whenever s=t⌢[n]s=t^\frown[n]s=t⌢[n] for some natural number nnn. Thus sss is an immediate child of ttt, and ordinals strictly decrease from parent to child. The function ρ\rhoρ is existentially required; a particular ranking function is not additional data supplied to fff. The measurable structure on XaX_aXa​ is the subtype measurable structure inherited from the Borel measurable structure on the space of prefix-closed Boolean functions, whose topology is the subspace topology of the product of discrete Boolean spaces indexed by finite lists of natural numbers; there is no additional hypothesis that the bounded-tree subtype is a Borel subset. Two underlying trees are isomorphic precisely when there exists one bijection eee between their sets of present lists such that, for every ordered pair of present lists s,ts,ts,t, sss is an immediate child of ttt if and only if e(s)e(s)e(s) is an immediate child of e(t)e(t)e(t). The natural-number labels and list lengths are not separately required to be preserved; the stipulated condition is preservation and reflection of the immediate-child relation by that bijection. The target code space YbY_bYb​ and relation EbE_bEb​ are defined recursively as follows. At stage 000, Y0={0,1}NY_0=\{0,1\}^{\mathbb N}Y0​={0,1}N with its product measurable structure, and E0E_0E0​ is literal equality of Boolean sequences. At a successor stage γ+1\gamma+1γ+1, Yγ+1Y_{\gamma+1}Yγ+1​ consists of one distinguished code ⊥\bot⊥ and all natural-number-indexed sequences u:N→Yγu:\mathbb N\to Y_\gammau:N→Yγ​. Its measurable structure is pulled back from the disjoint sum of a singleton and the product measurable space YγNY_\gamma^{\mathbb N}YγN​ by the map taking ⊥\bot⊥ to the singleton summand and a sequence to the sequence summand. The relation Eγ+1E_{\gamma+1}Eγ+1​ relates ⊥\bot⊥ to itself, never relates ⊥\bot⊥ to a sequence in either direction, and relates two sequence codes u,vu,vu,v exactly when both (∀i∈N)(∃j∈N) u(i) Eγ v(j)(\forall i\in\mathbb N)(\exists j\in\mathbb N)\,u(i)\,E_\gamma\,v(j)(∀i∈N)(∃j∈N)u(i)Eγ​v(j) and (∀j∈N)(∃i∈N) u(i) Eγ v(j)(\forall j\in\mathbb N)(\exists i\in\mathbb N)\,u(i)\,E_\gamma\,v(j)(∀j∈N)(∃i∈N)u(i)Eγ​v(j) hold. Thus the nonempty sequence codes do not retain enumeration order or multiplicity at the level of this relation, whereas the distinguished empty code is separate. At a nonzero countable limit ordinal λ\lambdaλ, a single fixed choice of sequence qλ:N→λq_\lambda:\mathbb N\to\lambdaqλ​:N→λ is used: qλ(n)<λq_\lambda(n)<\lambdaqλ​(n)<λ for every nnn, qλq_\lambdaqλ​ is strictly increasing, and for every δ<λ\delta<\lambdaδ<λ there exists nnn with δ≤qλ(n)\delta\le q_\lambda(n)δ≤qλ​(n). Then Yλ=∏n∈NYqλ(n)Y_\lambda=\prod_{n\in\mathbb N}Y_{q_\lambda(n)}Yλ​=∏n∈N​Yqλ​(n)​ with the dependent product measurable structure, and x Eλ yx\,E_\lambda\,yxEλ​y means that x(n) Eqλ(n) y(n)x(n)\,E_{q_\lambda(n)}\,y(n)x(n)Eqλ​(n)​y(n) for every n∈Nn\in\mathbb Nn∈N. These are actual sequence, option, and product code spaces, rather than quotient spaces of equivalence classes. Measurability of fff means that every measurable target set has measurable inverse image in the specified source subtype. The existential choices of bbb and fff occur after the choice of aaa and its two stated hypotheses, and before the universal quantification over the pair T,UT,UT,U: one bbb and one function work for all trees with that bound. There is no further ordinal inequality relating aaa and bbb, no positivity condition on bbb, and no uniqueness assertion. The hypothesis excludes a=0a=0a=0 and all uncountable aaa, but includes every positive finite aaa and every positive countable successor or limit ordinal. The empty tree belongs to XaX_aXa​ because its ranking requirements are vacuous, and it would also satisfy those requirements at bound 000; any nonempty prefix-closed tree contains the empty list as its root. A single-root tree admits the constant-zero ranking exactly when the bound is positive, so its least global bound is 111. At a=1a=1a=1, the only underlying trees in the source are the empty tree and the tree containing just that root. More generally the condition bounds every node's ordinal strictly below aaa; it is not a condition assigning the root ordinal aaa, and it allows finite trees and infinitely branching trees whenever such a ranking exists while excluding trees with an infinite child chain. Empty and nonempty trees cannot be isomorphic because their node sets cannot be bijective. Neither relation is assumed in this declaration to have a Borel graph, and no measurable choice of the existential ranking witnesses is required.

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