Gorn addresses #
A GornAddress is a position in a tree, written as in [Gor67]: the list of daughter indices
on the way down from the root. Addresses chain, with the root address as identity, so they form
the free monoid on ℕ, and his partial ordering of addresses puts an address below those it is a
head of: p ≤ q exactly when q = p * r for some r, which
is divisibility. Under it the addresses form the rooted tree in which every node has a daughter for
each natural number, with the order structure of Mathlib/Order/SuccPred/Tree.lean: the root 1
is least, Order.pred drops the last index, p ⊓ q is the longest common head, and strict
dominance is well founded. An address
is covered exactly by its immediate successors p * of i, and
lies below at most one of them. Chaining on the left is an
order embedding and the depth of an address is additive. The addresses of a concrete tree form a
set closed under predecessors (RoseTree.validPaths); [Gor67] calls a finite such set, closed
also under earlier sisters, a tree domain.
p precedes q when the two part at some address with p taking the earlier daughter.
Precedence is lexicographic order between addresses neither of which dominates the
other. It is a decidable strict order, it passes to
dominated addresses, and any two addresses are related by dominance or by
precedence.
Two addresses are left-aligned when they differ only in trailing first-daughter steps, so that the subtrees at them begin with the same leaf, which is to say that descending through first daughters from each reaches a common address. Left-alignment is a decidable equivalence relation, and left-aligned addresses lie on one branch.
Implementation notes #
The type is a structure over List ℕ, not a synonym of FreeMonoid ℕ, because lists carry the
lexicographic order that precedence compares against dominance; GornAddress.toFreeMonoid is the
isomorphism. Dominance unfolds to the prefix relation on the lists, and is divisibility by
GornAddress.le_iff_dvd. The order is one-sided: chaining on the left is monotone, chaining on the
right is
not, so the addresses are not a canonically ordered monoid.
References #
A Gorn address: the daughter indices on the way down from the root of a tree.
- toList : List ℕ
The daughter indices, from the root down.
Instances For
Equations
- instDecidableEqGornAddress.decEq { toList := a } { toList := b } = if h : a = b then h ▸ isTrue ⋯ else isFalse ⋯
Instances For
Equations
- instReprGornAddress.repr x✝ prec✝ = Std.Format.bracket "{ " (Std.Format.nil ++ Std.Format.text "toList" ++ Std.Format.text " := " ++ (Std.Format.nest 10 (repr ↑x✝)).group) " }"
Instances For
Equations
- instReprGornAddress = { reprPrec := instReprGornAddress.repr }
An address is read as its list of indices wherever a list is expected.
Equations
- instCoeOutGornAddressListNat = { coe := GornAddress.toList }
Chaining #
Chaining: the address reached by following q from p.
Equations
- GornAddress.instMul = { mul := fun (p q : GornAddress) => { toList := ↑p ++ ↑q } }
Equations
- One or more equations did not get rendered due to their size.
The address of the ith daughter of the root.
Equations
- GornAddress.of i = { toList := [i] }
Instances For
Addresses are the free monoid on the daughter indices.
Equations
- One or more equations did not get rendered due to their size.
Instances For
The partial ordering of addresses #
An address dominates the addresses it is a head of.
Equations
- GornAddress.instLE = { le := fun (p q : GornAddress) => ↑p <+: ↑q }
An address dominates another exactly when the other is obtained from it by chaining.
Dominance is divisibility in the monoid of addresses.
Equations
- x✝¹.instDecidableLE x✝ = decidable_of_iff (↑x✝¹ <+: ↑x✝) ⋯
Equations
- One or more equations did not get rendered due to their size.
Equations
- x✝¹.instDecidableLT x✝ = decidable_of_iff (x✝¹ ≤ x✝ ∧ ¬x✝ ≤ x✝¹) ⋯
The root address is the least address.
Equations
- GornAddress.instOrderBot = { bot := 1, bot_le := GornAddress.instOrderBot._proof_1 }
Chaining an address on the left is an order embedding of addresses.
Equations
- r.mulLeft = { toFun := fun (p : GornAddress) => r * p, inj' := ⋯, map_rel_iff' := ⋯ }
Instances For
An address above a chained one is above the first part or is itself chained from it.
Depth #
The depth of an address: the number of steps from the root.
Equations
- p.depth = (↑p).length
Instances For
Heads #
The addresses dominating an address, from the root down to the address itself.
Equations
- p.inits = List.map GornAddress.mk (↑p).inits
Instances For
The addresses at or above an address are its heads, finitely many.
Equations
- GornAddress.instLocallyFiniteOrderBot = LocallyFiniteOrderBot.ofIic GornAddress (fun (p : GornAddress) => p.inits.toFinset) ⋯
The head of an address of depth n, or the address itself if it is shallower.
Equations
- GornAddress.take n p = { toList := List.take n ↑p }
Instances For
The relative address of q with respect to p: what remains of q below p.
Equations
- q.relativeTo p = { toList := List.drop p.depth ↑q }
Instances For
Parents #
The parent of an address drops its last index. The root is its own parent.
Instances For
The last index of an address: which daughter of its parent it is. The root has none.
Equations
- p.last? = (↑p).getLast?
Instances For
An address other than the root is a daughter of its parent.
Equations
- GornAddress.instPredOrder = { pred := GornAddress.parent, pred_le := GornAddress.parent_le, min_of_le_pred := ⋯, le_pred_of_lt := ⋯ }
Immediate successors #
An address is covered exactly by its immediate successors.
An address lies below at most one immediate successor of an address.
The addresses below distinct immediate successors are disjoint.
Least common ancestors #
The meet of two addresses is their longest common head, the deepest address dominating both.
Equations
- One or more equations did not get rendered due to their size.
Linear precedence #
p precedes q when, at some common address, p continues into an earlier daughter than
q.
Equations
- p.Precedes q = ∃ (r : GornAddress) (i : ℕ) (j : ℕ), i < j ∧ r * GornAddress.of i ≤ p ∧ r * GornAddress.of j ≤ q
Instances For
An address comes lexicographically before every address it precedes.
Precedence is preserved by chaining on the left.
p precedes q exactly when p comes lexicographically before q without dominating it.
Equations
- p.instDecidablePrecedes q = decidable_of_iff (↑p < ↑q ∧ ¬p ≤ q) ⋯
Any two addresses are related by dominance or by precedence.
Two daughters of an address stand in precedence exactly as their indices are ordered.
Left edges #
Two positions are left-aligned when their addresses agree once trailing first-daughter steps are dropped, so that the subtrees at them begin with the same leaf.
Equations
- p.LeftAligned q = (List.dropWhile (fun (x : ℕ) => x == 0) (↑p).reverse = List.dropWhile (fun (x : ℕ) => x == 0) (↑q).reverse)
Instances For
Equations
Positions are left-aligned exactly when descending through first daughters from each reaches a common position.