Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Rooted tree codes, isomorphism, and bounded reverse-tree height

Definition
FSCofinalityTrees20261102

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

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

Trees are prefix-closed Boolean subsets of finite natural-number sequences, including empty and finite trees, with their native product-subspace Borel sigma algebra. Tree isomorphism is an actual bijection of node sets preserving and reflecting the immediate-child relation. A bound by an ordinal a means existence of ordinal labels below a at every node, strictly decreasing from parent to child. Thus the empty tree has height zero and a single vertex height one. Bounded-tree carriers inherit their measurable spaces from the tree code space; labels are witnesses, not part of a code. This explicitly models global reverse-tree height without identifying it with the separate leaf-zero padding rank.

Definition code
import Definitions.Def_FSCofinalityStructures20261102
import Mathlib.SetTheory.Ordinal.Basic

set_option autoImplicit false
noncomputable section
open Set TopologicalSpace

namespace FSCofinality.RootedTrees

abbrev Node := List ℕ

def PrefixClosed (t : Node → Bool) : Prop :=
  ∀ s n, t (s ++ [n]) = true → t s = true

/-- Prefix-closed trees, including the empty tree and finite trees. -/
def TreeSpace := {t : Node → Bool // PrefixClosed t}

instance : TopologicalSpace TreeSpace :=
  inferInstanceAs (TopologicalSpace {t : Node → Bool // PrefixClosed t})

instance : CoeFun TreeSpace (fun _ => Node → Bool) := ⟨fun t => t.val⟩

theorem isClosed_prefixClosed : IsClosed {t : Node → Bool | PrefixClosed t} := by
  unfold PrefixClosed
  simp only [setOf_forall]
  apply isClosed_iInter
  intro s
  apply isClosed_iInter
  intro n
  have heq : {t : Node → Bool | t (s ++ [n]) = true → t s = true} =
      {t | t (s ++ [n]) = false} ∪ {t | t s = true} := by
    ext t
    cases h : t (s ++ [n]) <;> simp [h]
  rw [heq]
  exact (isClosed_eq (continuous_apply (s ++ [n])) continuous_const).union
    (isClosed_eq (continuous_apply s) continuous_const)

instance : PolishSpace TreeSpace := by
  letI : PolishSpace (Node → Bool) := {
    toSecondCountableTopology := inferInstance
    toIsCompletelyMetrizableSpace := inferInstance }
  exact isClosed_prefixClosed.polishSpace

instance : MeasurableSpace TreeSpace := borel TreeSpace
instance : BorelSpace TreeSpace := ⟨rfl⟩

def Nodes (T : TreeSpace) := {s : Node // T s = true}

/-- The first argument is an immediate child of the second. -/
def Child {T : TreeSpace} (s t : Nodes T) : Prop :=
  ∃ n : ℕ, s.val = t.val ++ [n]

/-- One actual node bijection preserves and reflects the parent relation.
In particular, empty trees cannot be isomorphic to nonempty trees. -/
def Isomorphic (T U : TreeSpace) : Prop :=
  ∃ e : Nodes T ≃ Nodes U, ∀ s t, Child s t ↔ Child (e s) (e t)

/-- A global bound for the reverse-tree well-founded height. Every node is
assigned an ordinal below `a`, and immediate children receive strictly
smaller ordinals. The empty tree has height zero and a one-node tree has
height one. This bounds the whole tree, rather than declaring its root
to have leaf-rank zero and then silently identifying ordinal indices. -/
def BoundedTree (T : TreeSpace) (a : Ordinal.{0}) : Prop :=
  ∃ ρ : Nodes T → Ordinal.{0},
    (∀ s, ρ s < a) ∧ ∀ s t, Child s t → ρ s < ρ t

def treeRelation (a : Ordinal.{0}) : CodedRelation where
  Carrier := {T : TreeSpace // BoundedTree T a}
  measurableSpace := inferInstance
  rel := fun T U => Isomorphic T.val U.val

def emptyTree : TreeSpace := ⟨fun _ => false, by simp [PrefixClosed]⟩

def oneNodeTree : TreeSpace := ⟨fun s => decide (s = []), by simp [PrefixClosed]⟩

theorem bounded_emptyTree (a : Ordinal.{0}) : BoundedTree emptyTree a := by
  have he (s : Nodes emptyTree) : False := by
    have h := s.property
    simp [emptyTree] at h
  exact ⟨fun s => False.elim (he s), fun s => False.elim (he s),
    fun s _ _ => False.elim (he s)⟩

theorem bounded_oneNodeTree : BoundedTree oneNodeTree 1 := by
  refine ⟨fun _ => 0, fun _ => zero_lt_one, ?_⟩
  intro s t h
  obtain ⟨n, hn⟩ := h
  have hs : s.val = [] := of_decide_eq_true s.property
  have ht : t.val = [] := of_decide_eq_true t.property
  simp [hs, ht] at hn

end FSCofinality.RootedTrees
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, Section 2.3, original tree hierarchy; Proposition 4.15, first assertion. Background: Friedman--Stanley (1989), https://doi.org/10.2307/2274750, pages 899, 901--902, Section 1.2.
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: tree declarations

Read-back model: the exact underlying model identifier is not exposed to this auditor. This read-back was made from the tree declarations and their imported structures declarations, without consulting an informal statement or source material.

Node. A node code is a finite list of natural numbers, including the empty list [][][].

PrefixClosed. For a function ttt from finite lists of natural numbers to Boolean values, prefix closure means that, for every finite list sss and every natural number nnn, if t(s+ ⁣+[n])t(s\mathbin{+\!+}[n])t(s++[n]) is true, then t(s)t(s)t(s) is true; here s+ ⁣+[n]s\mathbin{+\!+}[n]s++[n] is the list obtained by appending the single entry nnn to sss. No code is required to have value true, so the everywhere-false function satisfies this condition.

TreeSpace. A tree is a Boolean-valued function on finite lists of natural numbers together with a proof of the preceding prefix-closure condition. Thus its actual nodes are exactly its true entries. Empty trees, finite trees, and infinite trees are permitted; there is no requirement of finite branching, no requirement of infinitely many nodes, and no well-foundedness requirement in this definition. Every nonempty such tree contains the empty list, and its node set is countable because all node codes are finite lists of natural numbers.

Topology on TreeSpace. The topology on these trees is the subspace topology inherited from the product of copies of the discrete Boolean space indexed by all finite lists of natural numbers.

Function coercion for TreeSpace. Evaluating a tree TTT at a node code sss means evaluating its underlying Boolean function at sss; its stored prefix-closure proof contributes no additional Boolean values.

isClosed_prefixClosed. Within the product space of all Boolean-valued functions on finite lists of natural numbers, the subset of functions satisfying the stated prefix-closure condition is closed.

Polish-space instance for TreeSpace. The tree space with the preceding topology is second countable and admits a compatible complete metric.

Measurable-space instance for TreeSpace. The measurable sets of the tree space are its Borel sets for the preceding topology.

Borel-space instance for TreeSpace. The specified measurable structure on the tree space equals the Borel measurable structure of its specified topology.

Nodes. For every tree TTT, the type of actual nodes of TTT consists of finite lists sss together with a proof that T(s)T(s)T(s) is true. If TTT is empty this type is empty; no false entry is included as an actual node.

Child. For every tree TTT and every pair s,ts,ts,t of actual nodes of that same tree, sss is a child of ttt precisely when there exists a natural number nnn such that the list underlying sss is the list underlying ttt with nnn appended. The first argument is the child and the second argument is its immediate parent; this relation does not mean an arbitrary proper descendant.

Isomorphic. For every two trees T,UT,UT,U, they are isomorphic precisely when there exists one bijection eee from the entire actual node set of TTT onto the entire actual node set of UUU such that, for every ordered pair s,ts,ts,t of actual nodes of TTT, sss is a child of ttt if and only if e(s)e(s)e(s) is a child of e(t)e(t)e(t). The bijection is not required to preserve the natural-number entries of the node lists. This is a full bijection preserving and reflecting the immediate-child relation, rather than an embedding or a family of pairwise choices. It includes empty, finite, and infinite node sets: the empty tree is isomorphic to itself, and cannot be isomorphic to a nonempty tree.

BoundedTree. For every tree TTT and every ordinal aaa in the specified small ordinal universe, TTT is bounded by aaa precisely when there exists a function ρ\rhoρ assigning an ordinal in that same universe to every actual node of TTT such that both (i) for every actual node sss, ρ(s)<a\rho(s)<aρ(s)<a, and (ii) for every pair of actual nodes s,ts,ts,t, if sss is an immediate child of ttt, then ρ(s)<ρ(t)\rho(s)<\rho(t)ρ(s)<ρ(t). The quantifier over ρ\rhoρ is existential for the given T,aT,aT,a; the bounds and strict decrease are universal over all actual nodes and all immediate-child pairs. No countability restriction is imposed on the ordinal aaa or on the assigned ordinals. The function need not be unique, minimal, or a recursively defined node rank. In particular, leaves are not required to receive zero. This is a strict bound on all node labels, with child labels smaller than parent labels. The empty tree satisfies the condition for every aaa, including zero, since its labeling function has empty domain; a nonempty tree cannot satisfy it for a=0a=0a=0. The one-node tree satisfies it exactly when 0<a0<a0<a, by assigning its sole node zero. Infinite trees are included whenever such a labeling exists, including the tree with a root and infinitely many immediate leaves at bound 222; a tree with an infinite branch cannot have such a strictly decreasing ordinal labeling. Thus the least possible bound is zero for the empty tree and one for the one-node tree. No separate height function, least-bound function, or equation between a root label and a tree height is defined.

treeRelation. For every ordinal aaa in the specified small ordinal universe, the resulting coded relation has as its carrier all trees TTT together with a proof that there exists an ordinal labeling satisfying the preceding strict global bound aaa and strict decrease from parent to child. The carrier is a subtype of the actual tree space, and its measurable structure is the native inherited subtype measurable structure: it is generated by intersections with Borel sets of the ambient tree space. This does not assert that the bounded-tree subset is itself Borel or Polish. Two members of this carrier are related precisely when there is one bijection between all their actual nodes preserving and reflecting the immediate-child relation, as defined above; the relation ignores the stored proofs of boundedness. A coded relation here means only a carrier type, a specified measurable structure on it, and a binary proposition-valued relation on it. Its imported definition imposes no additional requirement that the relation have a Borel graph. The ordinal-labeling witness is asserted to exist by carrier membership; it is not a further selected component of a carrier element.

emptyTree. The specified empty tree assigns false to every finite list of natural numbers and satisfies prefix closure vacuously; it has no actual nodes.

oneNodeTree. The specified one-node tree assigns true exactly to the empty list and false to every other finite list of natural numbers. Its only actual node is the empty list, and it has no immediate-child pairs.

bounded_emptyTree. For every ordinal aaa in the specified small ordinal universe, the everywhere-false tree admits a function from its empty actual node set to ordinals for which every label is strictly below aaa and every immediate child has a strictly smaller label than its parent; both requirements are vacuous, including when a=0a=0a=0.

bounded_oneNodeTree. The tree whose only actual node is the empty list admits an ordinal labeling with every label strictly below 111 and with every immediate child strictly below its parent: its sole node is assigned 000, and there are no immediate-child pairs.

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