Friedman--Stanley: Borelness of bounded-rank tree isomorphism
ProvedFSCofinality.bounded_tree_isomorphism_borelFor 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 , with carrying the inherited measurable structure,
import Definitions.Def_FSCofinalityTrees20261102 import Definitions.Def_FSCofinalityHierarchy20261102 set_option autoImplicit false
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
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 in the universe of ordinals represented by well-orders of small types, and every proof of the hypothesis , where is the first uncountable ordinal, the following graph is measurable. Let be the set of all finite lists of natural numbers, including the empty list, and let consist of all Boolean functions satisfying for every list and every . Give its product topology with discrete Boolean coordinates, give its subspace topology, and equip with the Borel sigma algebra of that topology. For , write for its actual set of nodes and say that is an immediate child of precisely when for some . Let be the subtype of all for which there exists a function , with values in the same small-universe ordinals as , such that for every node , and whenever is an immediate child of . The function is existentially quantified separately for each tree; it is not extra chosen data in an element of , and no least or canonical rank function is specified. Equip with the sigma algebra induced from the Borel sigma algebra of by the inclusion , namely the sets of the form for Borel . The conclusion is that the set of all pairs for which there exists a bijection satisfying, for every ordered pair of nodes , for some if and only if for some , 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 . There are no additional quantified spaces, external measurable-space choices, or hypotheses on beyond ; in particular , 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 , the empty tree is allowed for every because all requirements on nodes are vacuous, and the one-node tree can receive label exactly when (so it is included at ). At only the empty tree belongs to ; at only the empty tree and the tree whose sole node is the empty list belong to . A chain with nodes is admitted exactly when the finite ordinal is at most . In the usual convention using the least well-founded node rank , assigning a leaf rank , and defining tree height as with supremum for the empty set, the empty and one-node trees have heights and , respectively; the actual condition in the declaration remains the existence of the function 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 with the specified product sigma algebra; the statement contains no separate assertion that itself is Borel in 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.
Confirmed by the mission captain (proposal self-audit).