Read-back

The ambient group

Let $I = [0,1]$ be the closed unit interval of real numbers, regarded as an ordered set with the order it inherits from $\mathbb{R}$.

Let $G$ denote the set of order-isomorphisms $I \to I$: bijections $f : I \to I$ such that $x \le y \iff f(x) \le f(y)$. This is a group under composition, with

$$(f \cdot g)(x) = f(g(x)), \qquad 1 = \mathrm{id}_I, \qquad f^{-1} = \text{the inverse bijection}.$$

Every element of $G$ automatically satisfies $f(0) = 0$ and $f(1) = 1$, since an order-isomorphism carries the least element to the least element and the greatest to the greatest.

Dyadic numbers, and the generating property

A real number $x$ is dyadic if $x = m/2^{k}$ for some integer $m \in \mathbb{Z}$ and some natural number $k \ge 0$. (Since $k = 0$ is allowed, every integer is dyadic; $m$ may be negative, so dyadic numbers are not confined to $[0,1]$.)

Say that $f \in G$ has property $P$ if there exists a finite set $B \subseteq \mathbb{R}$, every element of which is dyadic, such that:

for all $x, y \in I$ with $x < y$ and $(x,y) \cap B = \varnothing$, there exist an integer $n \in \mathbb{Z}$ and a real number $c \in \mathbb{R}$ such that

$$f(z) = 2^{n} z + c \quad\text{for every } z \in I \text{ with } x \le z \le y.$$

Three points about property $P$ as stated. The exponent $n$ ranges over the integers, so the slope is a positive integer power of $2$ (possibly a negative power), never an arbitrary positive real; the intercept $c$ is an arbitrary real. The finite set $B$ is only required to consist of dyadic reals — it is not required to be contained in $[0,1]$, nor to contain $0$ or $1$, and it may be empty. The interval avoided is the open interval $(x,y)$, while the affine identity is asserted on the closed interval $[x,y]$.

Let $F \le G$ be the subgroup generated by the set $\{\,f \in G : f \text{ has property } P\,\}$, that is, the smallest subgroup of $G$ containing every $f$ with property $P$ (equivalently, the intersection of all such subgroups). So "$f \in F$" means: $f$ is a finite product of elements having property $P$ and of inverses of such elements. The statement below does not assume that the set of elements with property $P$ is already closed under composition or inversion; $F$ is its group closure whether or not that is so.

Finite binary trees

A tree is either a single leaf, or a node carrying an ordered pair of trees (its left and right subtrees). These are finite rooted ordered binary trees in which every internal node has exactly two children.

The leaf count $\lambda(t)$ is defined by $\lambda(\text{leaf}) = 1$ and $\lambda(\text{node}(l,r)) = \lambda(l) + \lambda(r)$. Thus $\lambda(t) \ge 1$ for every tree, and $\lambda(t) = 1$ exactly when $t$ is a single leaf.

The leaves of a tree are numbered $0, 1, \dots, \lambda(t) - 1$ from left to right, in the usual depth-first left-to-right order.

The marks of a tree

Assign real intervals to the nodes of $t$ by bisection: the root gets $[0,1]$, and a node holding $[a,b]$ gives its left subtree $\bigl[a, \tfrac{a+b}{2}\bigr]$ and its right subtree $\bigl[\tfrac{a+b}{2}, b\bigr]$. The intervals assigned to the leaves, read left to right, partition $[0,1]$ into $\lambda(t)$ consecutive standard dyadic intervals of the form $\bigl[\,a/2^{n},\ (a+1)/2^{n}\,\bigr]$.

The marks of $t$, written $\mu(t)$, are the endpoints of that partition listed in increasing order:

$$\mu(t) = \bigl(x_0, x_1, \dots, x_{N}\bigr), \qquad N = \lambda(t),$$

where $0 = x_0 < x_1 < \dots < x_{N} = 1$ and $[x_{i}, x_{i+1}]$ is the interval of the $i$-th leaf. This is a list (an ordered, finite sequence), of length $\lambda(t) + 1$; it always has at least the two entries $0$ and $1$, and for the single leaf it is exactly $(0, 1)$.

The caret predicate

For a tree $t$ and a natural number $k$, define a truth value $\chi_t(k)$ by the following recursion on $t$. For the single leaf, $\chi_{\text{leaf}}(k)$ is false for every $k$. For $t = \text{node}(l,r)$:

• if $k + 1 < \lambda(l)$, then $\chi_t(k) = \chi_l(k)$;
• otherwise, if $\lambda(l) \le k$, then $\chi_t(k) = \chi_r\bigl(k - \lambda(l)\bigr)$;
• otherwise (the remaining case is exactly $k + 1 = \lambda(l)$, i.e. $k$ is the index of the rightmost leaf of $l$), $\chi_t(k)$ is true if both $l$ and $r$ are single leaves, and false otherwise.

The first two guards are mutually exclusive — $k + 1 < \lambda(l)$ and $\lambda(l) \le k$ cannot both hold — so the three clauses are genuinely a case split with no ambiguity, and the third clause governs precisely the single index $k = \lambda(l) - 1$.

What this computes is:

$$\chi_t(k) = \text{true} \quad\Longleftrightarrow\quad \begin{array}{l}\text{leaves number } k \text{ and } k+1 \text{ of } t \text{ both exist and are}\\ \text{the two children of one common node.}\end{array}$$

Equivalently: $t$ has a node both of whose children are leaves, and those two leaves are the $k$-th and $(k+1)$-st leaves of $t$. In particular $\chi_t(k)$ is false whenever $k + 1 \ge \lambda(t)$ — so it is false at every index at or beyond the last leaf, and false for every $k$ when $t$ is a single leaf. (This equivalence was checked exhaustively against a direct implementation for all $677$ trees of depth at most $4$, which includes trees with up to $16$ leaves, at every index up to $\lambda(t) + 3$.)

Tree diagrams

A tree diagram $d$ consists of three pieces of data: a tree $\mathrm{dom}(d)$, a tree $\mathrm{ran}(d)$, and a proof of the assertion $\lambda(\mathrm{dom}(d)) = \lambda(\mathrm{ran}(d))$. The third component is a proof of a proposition and carries no further information: two tree diagrams are equal if and only if their two trees agree,

$$d_1 = d_2 \iff \bigl(\mathrm{dom}(d_1) = \mathrm{dom}(d_2) \ \text{ and }\ \mathrm{ran}(d_1) = \mathrm{ran}(d_2)\bigr),$$

where equality of trees is equality of the tree shapes as combinatorial objects. So a tree diagram is, in effect, an ordered pair of trees with the same number of leaves.

Extension to the line

For $f \in G$, let $\hat{f} : \mathbb{R} \to \mathbb{R}$ be

$$\hat{f}(x) = \begin{cases} f(x), & 0 \le x \le 1, \\ x, & \text{otherwise.}\end{cases}$$

This $\hat f$ is an order-isomorphism of $\mathbb{R}$ (it is well defined and order-preserving across the seams because $f(0) = 0$ and $f(1) = 1$).

What it means for a diagram to represent a map

Write $\mu(\mathrm{dom}(d)) = (x_0, \dots, x_M)$ and $\mu(\mathrm{ran}(d)) = (y_0, \dots, y_{M'})$. The diagram $d$ represents $f \in G$ when all three of the following hold.

1. $f \in F$.

2. (Affine on the pieces of the domain tree.) For every $i$ with $0 \le i \le M - 1$ — that is, for each pair of consecutive entries of $\mu(\mathrm{dom}(d))$ — there exist real numbers $a_i$ and $c_i$ such that

$$\hat{f}(z) = a_i z + c_i \quad\text{for every } z \in [x_i, x_{i+1}].$$

The numbers $a_i, c_i$ are arbitrary reals: nothing here requires $a_i > 0$, nor that $a_i$ be a power of $2$, nor that the $a_i$ be related to one another. The condition is imposed only on consecutive pairs of marks, and says nothing directly about non-adjacent pairs. The interval is the closed interval $[x_i, x_{i+1}]$, so consecutive conditions overlap at the shared endpoint.

3. (The marks are carried to the marks, in order.) Applying $\hat{f}$ entrywise to the list $\mu(\mathrm{dom}(d))$ yields the list $\mu(\mathrm{ran}(d))$ exactly:

$$\bigl(\hat{f}(x_0), \hat{f}(x_1), \dots, \hat{f}(x_M)\bigr) = \bigl(y_0, y_1, \dots, y_{M'}\bigr).$$

Being an equality of lists, this forces $M = M'$ — hence $\lambda(\mathrm{dom}(d)) = \lambda(\mathrm{ran}(d))$, which the diagram already carries as its third component — and forces $\hat f(x_i) = y_i$ for every index $i$ separately, in the same order.

What it means for a diagram to be reduced

The diagram $d$ is reduced when, for every natural number $k$, it is not the case that both $\chi_{\mathrm{dom}(d)}(k)$ and $\chi_{\mathrm{ran}(d)}(k)$ are true. In words: there is no index $k$ at which the domain tree and the range tree both have a node whose two children are exactly their $k$-th and $(k+1)$-st leaves.

The quantifier runs over all natural numbers $k$, including those at or beyond the last leaf, where both caret predicates are false anyway, so those indices impose nothing. The condition permits the domain tree to have such a node at one index and the range tree to have one at a different index; only coincidence of indices is forbidden.

The assertion

Let $f$ be any order-isomorphism of $[0,1]$, and let $d_1$ and $d_2$ be any tree diagrams. Suppose that $d_1$ is reduced and represents $f$, and that $d_2$ is reduced and represents $f$. Then $d_1 = d_2$.

Unfolded completely: for every order-isomorphism $f : [0,1] \to [0,1]$ and all trees $T_1, S_1, T_2, S_2$ with $\lambda(T_1) = \lambda(S_1)$ and $\lambda(T_2) = \lambda(S_2)$, if

• there is no $k$ with $\chi_{T_1}(k)$ and $\chi_{S_1}(k)$ both true, and
• $f$ lies in the subgroup $F$, and $\hat f$ is affine on each interval between consecutive marks of $T_1$, and $\hat f$ carries the list of marks of $T_1$ entrywise onto the list of marks of $S_1$, and
• there is no $k$ with $\chi_{T_2}(k)$ and $\chi_{S_2}(k)$ both true, and
• $f$ lies in $F$, and $\hat f$ is affine on each interval between consecutive marks of $T_2$, and $\hat f$ carries the list of marks of $T_2$ entrywise onto the list of marks of $S_2$,

then $T_1 = T_2$ and $S_1 = S_2$.

Scope, quantifiers and edge cases

• The map $f$ and the two diagrams $d_1, d_2$ are universally quantified; they are the only variables. There are no side conditions of a typeclass or structural nature beyond those spelled out above.

• The clause "$f \in F$" occurs inside each of the two representation hypotheses, so it is assumed twice with identical content; it is the same $f$ in both.

• The hypotheses are jointly satisfiable, so the statement is not vacuous. Taking $f$ to be the identity map of $[0,1]$ and $d_1 = d_2$ to be the diagram whose two trees are both a single leaf: the identity lies in $F$ (it is the neutral element of a subgroup); the marks of a single leaf are $(0,1)$, on which the identity is affine with $a = 1$, $c = 0$; the identity carries $(0,1)$ to $(0,1)$; and the caret predicate of a single leaf is false everywhere, so the diagram is reduced. All four hypotheses hold simultaneously. (Verified by elaboration.)

• The conclusion is equality of the diagrams, which as noted above is exactly equality of both underlying trees. It is not merely equality of leaf counts, nor equality of the induced piecewise-linear maps, nor equality up to some notion of isomorphism of diagrams.

• The statement asserts uniqueness only: at most one reduced diagram represents a given $f$. It makes no claim that any reduced diagram representing $f$ exists, and no claim about which $f \in F$ (or which $f \in G$) are representable at all. Correspondingly, if for some $f$ no reduced representing diagram exists, the statement holds for that $f$ with nothing to say.

• If the domain tree of a diagram is a single leaf, then its leaf count is $1$, so by the diagram's own third component the range tree also has leaf count $1$ and is therefore also a single leaf; such a diagram is automatically reduced.

• Nothing in the representation condition refers to the marks of the range tree except as the target list in clause 3; in particular the affineness in clause 2 is imposed relative to the subdivision coming from the domain tree only.

• The notion of "reduced" used here is the one defined above — absence of a common index at which both trees have a node with two leaf children. No further minimality, irreducibility or normal-form condition on the diagram is assumed.