proofs
Provedattentionversion-9finite-lawconstructible-state

A maintained weighted-tree append preserves leaves labels root and path writes

For all A:Type⁡⋅\htmlData{mx=2}{A : \htmlData{mx=1}{\htmlData{mx=0}{\operatorname{Type}} \cdot }}, h∈N\htmlData{mx=1}{h \in \htmlData{mx=0}{\mathbb{N}}}, t∈MassTree⁡ A h\htmlData{mx=4}{t \in \htmlData{mx=3}{\htmlData{mx=0}{\operatorname{MassTree}}\,\htmlData{mx=1}{A}\,\htmlData{mx=2}{h}}}, ht∈valid⁡ t\htmlData{mx=3}{\mathit{ht} \in \htmlData{mx=2}{\htmlData{mx=0}{\operatorname{valid}}\,\htmlData{mx=1}{t}}}, z∈Copies⁡ Bool⁡ h\htmlData{mx=4}{z \in \htmlData{mx=3}{\htmlData{mx=0}{\operatorname{Copies}}\,\htmlData{mx=1}{\operatorname{Bool}}\,\htmlData{mx=2}{h}}} and w∈R\htmlData{mx=1}{w \in \htmlData{mx=0}{\mathbb{R}}}, if leafWeight⁡(t,z)=0\htmlData{mx=3}{\htmlData{mx=0}{\operatorname{leafWeight}}(\htmlData{mx=1}{t}, \htmlData{mx=2}{z})} \mathrel{\htmlData{mx=4}{=}} 0 and 0≤w0 \mathrel{\htmlData{mx=1}{\leq}} \htmlData{mx=0}{w}, then

(valid⁡(update⁡(t,z,w))∧mass⁡(update⁡(t,z,w))=mass⁡(t)+w∧updateWrites⁡(t,z)=h+1∧(∀u, returned⁡(update⁡(t,z,w),u)=returned⁡(t,u))∧(∀u,leafWeight⁡(update⁡(t,z,w),u)=@(ite⁡,R,u=z,propDecidable⁡(⋅),w,leafWeight⁡(t,u))))\begin{aligned} & \left(\right. \htmlData{mx=7}{\htmlData{mx=1}{\operatorname{valid}}(\htmlData{mx=6}{\htmlData{mx=2}{\operatorname{update}}(\htmlData{mx=3}{t}, \htmlData{mx=4}{z}, \htmlData{mx=5}{w})})} \\ & \htmlData{mx=0}{\land} \htmlData{mx=14}{\htmlData{mx=8}{\operatorname{mass}}(\htmlData{mx=13}{\htmlData{mx=9}{\operatorname{update}}(\htmlData{mx=10}{t}, \htmlData{mx=11}{z}, \htmlData{mx=12}{w})})} \mathrel{\htmlData{mx=20}{=}} \htmlData{mx=19}{\htmlData{mx=17}{\htmlData{mx=15}{\operatorname{mass}}(\htmlData{mx=16}{t})} + \htmlData{mx=18}{w}} \\ & \htmlData{mx=0}{\land} \htmlData{mx=24}{\htmlData{mx=21}{\operatorname{updateWrites}}(\htmlData{mx=22}{t}, \htmlData{mx=23}{z})} \mathrel{\htmlData{mx=27}{=}} \htmlData{mx=26}{\htmlData{mx=25}{h} + 1} \\ & \htmlData{mx=0}{\land} (\htmlData{mx=41}{\forall u,\ \htmlData{mx=35}{\htmlData{mx=28}{\operatorname{returned}}(\htmlData{mx=33}{\htmlData{mx=29}{\operatorname{update}}(\htmlData{mx=30}{t}, \htmlData{mx=31}{z}, \htmlData{mx=32}{w})}, \htmlData{mx=34}{u})} \mathrel{\htmlData{mx=40}{=}} \htmlData{mx=39}{\htmlData{mx=36}{\operatorname{returned}}(\htmlData{mx=37}{t}, \htmlData{mx=38}{u})}}) \\ & \htmlData{mx=0}{\land} \left(\right. \htmlData{mx=42}{\forall} u, \\ & \quad \htmlData{mx=51}{\htmlData{mx=44}{\operatorname{leafWeight}}(\htmlData{mx=49}{\htmlData{mx=45}{\operatorname{update}}(\htmlData{mx=46}{t}, \htmlData{mx=47}{z}, \htmlData{mx=48}{w})}, \htmlData{mx=50}{u})} \\ & \quad \quad \htmlData{mx=43}{=} \htmlData{mx=65}{\mathtt{@}(\htmlData{mx=52}{\operatorname{ite}}, \htmlData{mx=53}{\mathbb{R}}, \htmlData{mx=54}{u} \mathrel{\htmlData{mx=56}{=}} \htmlData{mx=55}{z}, \htmlData{mx=59}{\htmlData{mx=57}{\operatorname{propDecidable}}(\htmlData{mx=58}{\cdot})}, \htmlData{mx=60}{w}, \htmlData{mx=64}{\htmlData{mx=61}{\operatorname{leafWeight}}(\htmlData{mx=62}{t}, \htmlData{mx=63}{u})})} \left.\right) \left.\right) \end{aligned}
What the notation means · or point at any symbol
Type
Type: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (Type)
·Multiplication
Type times . (Type*)
NNatural numbers
The natural numbers 0, 1, 2, …. In Lean they start at 0. (ℕ)
MassTree
MassTree: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (MassTree)
f(x)Function application
MassTree applied to A, h. Lean writes f x; papers write f(x). (MassTree A h)
valid
valid: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (valid)
Copies
Copies: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (Copies)
leafWeight
leafWeight: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (leafWeight)
=Equality
leafWeight(t, z) and 0 are the same. (leafWeight t z=0)
RReal numbers
The real numbers: every point on the number line. (ℝ)
≤At most
0 is less than or equal to w. (0≤w)
Bool
Bool: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (Bool)
update
update: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (update)
mass
mass: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (mass)
+Addition
mass(t) plus w. (mass t+w)
updateWrites
updateWrites: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (updateWrites)
∧And
Both hold: ∀ u, returned(update(t, z, w), u) = returned(t, u), and ∀ u, leafWeight(update(t, z, w), u) = @(ite, ℝ, u = z, pro…. ((∀ u,returned (update t z w) u=returned…)
∀For all
The statement after the comma holds for every u. (∀ u,returned (update t z w) u=returned …)
returned
returned: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (returned)
ite
ite: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (ite)
propDecidable
Classical.propDecidable: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (Classical.propDecidable)

Version 9 exact frozen target. Proof references the validated additive definition library. This mathematical finite-law/invariant target does not certify compiled Rust RAM runtime or the general linear-summary LP bridge.

How it was proved

Proved
7 October 2026
By
Ajax
Checked by
Lean's kernel (Lean 4.33.1, with Mathlib); the proof is signed and replays offline
Axioms
Classical.choice, Quot.sound, propext
Proof
11 lines of Lean
Sign in to see the proofThe proof, its signed report and its history.

More proved statements