Rooted tree codes, isomorphism, and bounded reverse-tree height
DefinitionFSCofinalityTrees20261102Trees 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.
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
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 from finite lists of natural numbers to Boolean values, prefix closure means that, for every finite list and every natural number , if is true, then is true; here is the list obtained by appending the single entry to . 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 at a node code means evaluating its underlying Boolean function at ; 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 , the type of actual nodes of consists of finite lists together with a proof that is true. If is empty this type is empty; no false entry is included as an actual node.
Child. For every tree and every pair of actual nodes of that same tree, is a child of precisely when there exists a natural number such that the list underlying is the list underlying with 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 , they are isomorphic precisely when there exists one bijection from the entire actual node set of onto the entire actual node set of such that, for every ordered pair of actual nodes of , is a child of if and only if is a child of . 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 and every ordinal in the specified small ordinal universe, is bounded by precisely when there exists a function assigning an ordinal in that same universe to every actual node of such that both (i) for every actual node , , and (ii) for every pair of actual nodes , if is an immediate child of , then . The quantifier over is existential for the given ; the bounds and strict decrease are universal over all actual nodes and all immediate-child pairs. No countability restriction is imposed on the ordinal 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 , including zero, since its labeling function has empty domain; a nonempty tree cannot satisfy it for . The one-node tree satisfies it exactly when , 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 ; 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 in the specified small ordinal universe, the resulting coded relation has as its carrier all trees together with a proof that there exists an ordinal labeling satisfying the preceding strict global bound 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 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 and every immediate child has a strictly smaller label than its parent; both requirements are vacuous, including when .
bounded_oneNodeTree. The tree whose only actual node is the empty list admits an ordinal labeling with every label strictly below and with every immediate child strictly below its parent: its sole node is assigned , and there are no immediate-child pairs.
Confirmed by the mission captain (proposal self-audit).