Theorem 1.2 — Friedman--Stanley cofinality without Borel completeness
ProvedFSCofinality.theorem1_2There 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 and satisfy
together with
Here uses the explicitly defined global reverse-tree-height presentation; ordinal indices are not identified with those of a different rank convention.
import Definitions.Def_FSCofinalityHierarchy20261102 import Definitions.Def_FSCofinalityTrees20261102 set_option autoImplicit false
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
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 and a set of -structures on the fixed domain 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 consisting of a symbol and an -tuple of natural numbers, with the product topology of the discrete Boolean coordinates and its Borel measurable space; these are structures on all of , not structures with arbitrary finite or empty domains. The set is Borel in that structure space. It is invariant in the following precise sense: for every two structures , if and there is a bijection such that, for every symbol and every tuple , the truth value of at in equals its truth value at in , then . Write for existence of such a bijection, and give the measurable space inherited from the ambient structure space. Define concrete measurable spaces and relations by the following recursion: with its product measurable space and equal to equality; at a successor, consists of a distinguished code and codes for all sequences , with the measurable space transported from the disjoint sum of a singleton and the product space ; the successor relation makes related to itself, makes unrelated to every sequence code in either order, and satisfies exactly when and ; 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 , one fixed previously chosen strictly increasing cofinal sequence is used, where for every and ; has the product measurable space, and means . For every ordinal of the universe used in the declaration with , including and every finite ordinal, there exists a measurable function such that, for every , if and only if . Here is the first uncountable ordinal, so no assertion is made at or above; the definitions' default fundamental sequences outside the countable range play no role in this conclusion. There does not exist a measurable function from the space of simple undirected graphs on to such that, for every pair of graphs , if and only if : a graph here is a Boolean array with for every and for every , its measurable space is the Borel space of this subspace of , and means that some bijection satisfies for all . Finally, for every ordinal with , there exists a measurable function such that, for every , if and only if . To define this source precisely, a tree is a Boolean subset of the finite sequences of natural numbers such that implies , 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 is an immediate child of exactly when for some . The class is the subtype of those trees for which there exists a function satisfying both and ; it has the measurable space inherited from the tree space. The witness 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 for every , a one-node tree belongs for every positive , and a finite tree belongs exactly when such a labelling exists. In particular, for positive finite , the labelling condition allows precisely trees whose paths have at most nodes, including infinitely branching trees of that finite height; consists of the empty tree and the one-node tree. At the bound permits only the empty tree, but the final reduction clause excludes that ordinal. The chosen and 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 ; the bijections witnessing the isomorphism relations likewise may depend on the pair being compared. No separate nonemptiness hypothesis on is stated, but the zero-stage reduction from nonempty Cantor space forces 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 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 ”: the one-node tree already satisfies the bound at . 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.
Confirmed by the mission captain (proposal self-audit).