Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 1.2 — Friedman--Stanley cofinality without Borel completeness

Proved
FSCofinality.theorem1_2

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

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

There are one fixed countable relational language L and one isomorphism-invariant Borel class K of L-structures on the natural numbers such that every countable level of the concrete product-limit Friedman--Stanley hierarchy Borel reduces to isomorphism on K, while graph isomorphism does not. Moreover, bounded-rank well-founded rooted tree isomorphism reduces to the same target for every nonzero countable bound, including finite and empty tree codes. Borelness is a property of K as a class of structures, not a requirement that its isomorphism graph be Borel. The language and target class are fixed before the ordinal quantifiers, while each ordinal may have its own reduction. The product-limit and original-tree presentations make the cofinality convention explicit.

The same LLL and K\mathcal KK satisfy

∀α<ω1,Jα≤B≅K,≅Graph̸≤B≅K,\forall\alpha<\omega_1,\quad\mathsf J_\alpha\leq_B\cong_{\mathcal K},\qquad \cong_{\mathrm{Graph}}\not\leq_B\cong_{\mathcal K},∀α<ω1​,Jα​≤B​≅K​,≅Graph​≤B​≅K​,

together with

∀ 0<α<ω1,≅Tα≤B≅K.\forall\,0<\alpha<\omega_1,\quad\cong_{\mathfrak T_\alpha}\leq_B\cong_{\mathcal K}.∀0<α<ω1​,≅Tα​​≤B​≅K​.

Here Tα\mathfrak T_\alphaTα​ uses the explicitly defined global reverse-tree-height presentation; ordinal indices are not identified with those of a different rank convention.

Preamble
import Definitions.Def_FSCofinalityHierarchy20261102
import Definitions.Def_FSCofinalityTrees20261102

set_option autoImplicit false

Formal statement
theorem FSCofinality.theorem1_2 :
    ∃ L : FSCofinality.CountableRelationalLanguage,
      ∃ K : Set (FSCofinality.Structures L),
        MeasurableSet K ∧ FSCofinality.IsInvariant K ∧
        (∀ a : Ordinal.{0}, a < Ordinal.omega 1 →
          (FSCofinality.fsTower a).Reduces (FSCofinality.classRelation L K)) ∧
        ¬ FSCofinality.graphRelation.Reduces (FSCofinality.classRelation L K) ∧
        (∀ a : Ordinal.{0}, 0 < a → a < Ordinal.omega 1 →
          (FSCofinality.RootedTrees.treeRelation a).Reduces
            (FSCofinality.classRelation L K)) := 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, Theorem 1.2, label thm:main, lines 130--143; assembly lines 1745--1763; hierarchy conventions in Section 2.3 and Propositions 4.13, 4.15.
Read-back

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

Literal read-back of FSCofinality.theorem1_2

Read-back model: Codex, based on GPT-6. The exact runtime model identifier is not exposed to this auditor; no more specific identifier is claimed.

Permitted sources read: the mission-auditor instructions, Theorems/Thm_FSCofinality_theorem1_2.lean, and the three imported definition files Def_FSCofinalityStructures20261102.lean, Def_FSCofinalityHierarchy20261102.lean, and Def_FSCofinalityTrees20261102.lean. No manuscript, metadata, informal description, or other chat was consulted.

There exist a relational language LLL and a set KKK of LLL-structures on the fixed domain N\mathbb NN with the following simultaneous properties. The language consists of a countable set of relation symbols and an assigned natural-number arity for each symbol; the definition permits finite or empty symbol sets and arity zero. A structure is a Boolean truth value for every pair (s,nˉ)(s,\bar n)(s,nˉ) consisting of a symbol sss and an arity⁡(s)\operatorname{arity}(s)arity(s)-tuple of natural numbers, with the product topology of the discrete Boolean coordinates and its Borel measurable space; these are structures on all of N\mathbb NN, not structures with arbitrary finite or empty domains. The set KKK is Borel in that structure space. It is invariant in the following precise sense: for every two structures M,NM,NM,N, if M∈KM\in KM∈K and there is a bijection e:N→Ne:\mathbb N\to\mathbb Ne:N→N such that, for every symbol sss and every tuple nˉ\bar nnˉ, the truth value of sss at nˉ\bar nnˉ in MMM equals its truth value at e∘nˉe\circ\bar ne∘nˉ in NNN, then N∈KN\in KN∈K. Write M≅LNM\cong_L NM≅L​N for existence of such a bijection, and give KKK the measurable space inherited from the ambient structure space. Define concrete measurable spaces XαX_\alphaXα​ and relations EαE_\alphaEα​ by the following recursion: X0={0,1}NX_0=\{0,1\}^{\mathbb N}X0​={0,1}N with its product measurable space and E0E_0E0​ equal to equality; at a successor, Xβ+1X_{\beta+1}Xβ+1​ consists of a distinguished code ⊥\bot⊥ and codes some⁡(u)\operatorname{some}(u)some(u) for all sequences u:N→Xβu:\mathbb N\to X_\betau:N→Xβ​, with the measurable space transported from the disjoint sum of a singleton and the product space XβNX_\beta^{\mathbb N}XβN​; the successor relation makes ⊥\bot⊥ related to itself, makes ⊥\bot⊥ unrelated to every sequence code in either order, and satisfies some⁡(u) Eβ+1 some⁡(v)\operatorname{some}(u)\,E_{\beta+1}\,\operatorname{some}(v)some(u)Eβ+1​some(v) exactly when (∀i∈N ∃j∈N  u(i) Eβ v(j))(\forall i\in\mathbb N\,\exists j\in\mathbb N\;u(i)\,E_\beta\,v(j))(∀i∈N∃j∈Nu(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_\beta\,v(j))(∀j∈N∃i∈Nu(i)Eβ​v(j)); thus order and repetitions are ignored, a finite nonempty represented set may be enumerated with repetitions, and the empty represented set has its own code. At each nonzero countable limit ordinal λ\lambdaλ, one fixed previously chosen strictly increasing cofinal sequence qλ:N→λq_\lambda:\mathbb N\to\lambdaqλ​:N→λ is used, where qλ(n)<λq_\lambda(n)<\lambdaqλ​(n)<λ for every nnn and ∀β<λ ∃n  (β≤qλ(n))\forall\beta<\lambda\,\exists n\;(\beta\le q_\lambda(n))∀β<λ∃n(β≤qλ​(n)); Xλ=∏n∈NXqλ(n)X_\lambda=\prod_{n\in\mathbb N}X_{q_\lambda(n)}Xλ​=∏n∈N​Xqλ​(n)​ has the product measurable space, and x Eλ yx\,E_\lambda\,yxEλ​y means ∀n∈N  x(n) Eqλ(n) y(n)\forall n\in\mathbb N\;x(n)\,E_{q_\lambda(n)}\,y(n)∀n∈Nx(n)Eqλ​(n)​y(n). For every ordinal α\alphaα of the universe used in the declaration with α<ω1\alpha<\omega_1α<ω1​, including α=0\alpha=0α=0 and every finite ordinal, there exists a measurable function fα:Xα→Kf_\alpha:X_\alpha\to Kfα​:Xα​→K such that, for every x,y∈Xαx,y\in X_\alphax,y∈Xα​, x Eα yx\,E_\alpha\,yxEα​y if and only if fα(x)≅Lfα(y)f_\alpha(x)\cong_L f_\alpha(y)fα​(x)≅L​fα​(y). Here ω1\omega_1ω1​ is the first uncountable ordinal, so no assertion is made at ω1\omega_1ω1​ or above; the definitions' default fundamental sequences outside the countable range play no role in this conclusion. There does not exist a measurable function ggg from the space of simple undirected graphs on N\mathbb NN to KKK such that, for every pair of graphs G,HG,HG,H, G≅HG\cong HG≅H if and only if g(G)≅Lg(H)g(G)\cong_L g(H)g(G)≅L​g(H): a graph here is a Boolean array G(m,n)G(m,n)G(m,n) with G(n,n)=0G(n,n)=0G(n,n)=0 for every nnn and G(m,n)=G(n,m)G(m,n)=G(n,m)G(m,n)=G(n,m) for every m,nm,nm,n, its measurable space is the Borel space of this subspace of {0,1}N×N\{0,1\}^{\mathbb N\times\mathbb N}{0,1}N×N, and G≅HG\cong HG≅H means that some bijection e:N→Ne:\mathbb N\to\mathbb Ne:N→N satisfies G(m,n)=H(e(m),e(n))G(m,n)=H(e(m),e(n))G(m,n)=H(e(m),e(n)) for all m,nm,nm,n. Finally, for every ordinal α\alphaα with 0<α<ω10<\alpha<\omega_10<α<ω1​, there exists a measurable function hα:Tα→Kh_\alpha:\mathcal T_\alpha\to Khα​:Tα​→K such that, for every T,U∈TαT,U\in\mathcal T_\alphaT,U∈Tα​, T≅treeUT\cong_{\mathrm{tree}}UT≅tree​U if and only if hα(T)≅Lhα(U)h_\alpha(T)\cong_L h_\alpha(U)hα​(T)≅L​hα​(U). To define this source precisely, a tree is a Boolean subset TTT of the finite sequences of natural numbers such that s⌢[n]∈Ts^\frown[n]\in Ts⌢[n]∈T implies s∈Ts\in Ts∈T, with the subspace topology inherited from the Boolean product on all finite sequences and its Borel measurable space; its nodes are exactly the sequences it contains, and sss is an immediate child of ttt exactly when s=t⌢[n]s=t^\frown[n]s=t⌢[n] for some n∈Nn\in\mathbb Nn∈N. The class Tα\mathcal T_\alphaTα​ is the subtype of those trees for which there exists a function ρ:Nodes⁡(T)→Ord⁡\rho:\operatorname{Nodes}(T)\to\operatorname{Ord}ρ:Nodes(T)→Ord satisfying both ∀s∈Nodes⁡(T)  (ρ(s)<α)\forall s\in\operatorname{Nodes}(T)\;(\rho(s)<\alpha)∀s∈Nodes(T)(ρ(s)<α) and ∀s,t∈Nodes⁡(T)  (s is an immediate child of t⇒ρ(s)<ρ(t))\forall s,t\in\operatorname{Nodes}(T)\;(s\text{ is an immediate child of }t\Rightarrow\rho(s)<\rho(t))∀s,t∈Nodes(T)(s is an immediate child of t⇒ρ(s)<ρ(t)); it has the measurable space inherited from the tree space. The witness ρ\rhoρ is an existence condition on each tree, not part of a tree code, not required to be a least rank function, and not required to be chosen measurably or uniformly across trees. Tree isomorphism means existence of an actual bijection between the two node sets that preserves and reflects the immediate-child relation on every ordered pair of nodes; it does not require preservation of the natural-number labels of nodes. Empty trees and finite trees are permitted in the underlying tree space, with no finite-branching assumption; the empty tree belongs to Tα\mathcal T_\alphaTα​ for every α\alphaα, a one-node tree belongs for every positive α\alphaα, and a finite tree belongs exactly when such a labelling exists. In particular, for positive finite α=n\alpha=nα=n, the labelling condition allows precisely trees whose paths have at most nnn nodes, including infinitely branching trees of that finite height; T1\mathcal T_1T1​ consists of the empty tree and the one-node tree. At α=0\alpha=0α=0 the bound permits only the empty tree, but the final reduction clause excludes that ordinal. The chosen LLL and KKK precede both universal ordinal quantifiers and therefore work simultaneously for all the stated stages, while the reduction functions are existentially quantified separately after each stage and need have no uniform or measurable dependence on α\alphaα; the bijections witnessing the isomorphism relations likewise may depend on the pair being compared. No separate nonemptiness hypothesis on KKK is stated, but the zero-stage reduction from nonempty Cantor space forces KKK to be nonempty. Throughout, a reduction requires exactly measurability of the function and preservation and reflection of the two relations on all pairs; the bundled relations carry no additional hypothesis that their graphs are Borel, and the statement does not assert that Tα\mathcal T_\alphaTα​ itself is a Borel subset of the ambient tree space.

Scope observations

The literal type fixes the product-at-limits hierarchy above and the global descending-label bound on trees. In particular, it does not identify its ordinal parameters with another convention for a Friedman–Stanley hierarchy or with an independently defined tree-rank convention. The inequalities on the labels are strict, but it would change their meaning to replace the displayed witness condition by the unexplained phrase “tree height strictly below α\alphaα”: the one-node tree already satisfies the bound at α=1\alpha=1α=1. Any comparison with a different height convention needs a separately specified translation.

The two families of reductions concern exactly the displayed concrete coded relations. The statement supplies neither a universal quantifier over all Borel equivalence relations nor a measurable family of reductions indexed by ordinals. Its use of measurable reductions also supplies no unstated Borel-graph hypothesis. These are limits of the asserted scope, without a claim about what scope was intended.

The source provides the theorem's asserted type followed by a sorry proof placeholder. This document reads back that type and does not certify a 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