Read-back: existence of a reduced tree diagram representing an element

The ambient objects

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

An order-automorphism of $I$ is a bijection $f : I \to I$ such that for all $x,y \in I$ we have $x \le y$ if and only if $f(x) \le f(y)$. (The condition is required in both directions, so both $f$ and $f^{-1}$ are order preserving.) Such maps form a group $G$ under composition: the product $f \cdot g$ is the map $z \mapsto f(g(z))$, the unit is the identity map of $I$, and the inverse is the inverse function. Every element of $G$ is strictly increasing and satisfies $f(0)=0$ and $f(1)=1$, because $0$ and $1$ are the least and greatest elements of $I$ and an order isomorphism must carry each to itself.

A real number $x$ is called dyadic here if there are an integer $m$ and a natural number $k$ with

$$x = \frac{m}{2^{k}}.$$

The integer $m$ may be negative or zero, so this is the set of dyadic rationals of $\mathbb{R}$, not only those in $I$.

The generating property $T$

Say that $f \in G$ has property $T$ if there exists a finite set $B$ of real numbers such that

1. every element of $B$ is dyadic, and
2. for every pair of points $x,y \in I$ with $x < y$ whose open interval misses $B$, i.e. $(x,y) \cap B = \varnothing$, there exist an integer $n$ and a real number $c$ such that

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

Points worth making explicit about this predicate:

• The exponent $n$ ranges over $\mathbb{Z}$, so the admissible slopes are exactly the integral powers of $2$; in particular every slope is positive. The pair $(n,c)$ may depend on $x$ and $y$.
• The affine identity is asserted on the closed interval $[x,y]$, including its endpoints.
• $B$ is not required to be contained in $I$, is not required to consist of actual breakpoints of $f$, and is not required to be non-empty. Conversely, condition 2 forces $f$ to be affine with a power-of-two slope on every subinterval of $I$ avoiding $B$, so all genuine breakpoints of $f$ do lie in $B$ and are therefore dyadic.
• If $B$ is empty, condition 2 applied with $x = 0$, $y = 1$ says $f(z) = 2^n z + c$ on all of $I$, which together with $f(0)=0$ and $f(1)=1$ forces $f$ to be the identity. So the empty choice of $B$ is allowed but only the identity satisfies condition 2 with it.

The group $F$

$F$ is defined to be the subgroup of $G$ generated by the set $\{\, f \in G : f \text{ has property } T \,\}$: the smallest subgroup of $G$ containing every map with property $T$, equivalently the intersection of all subgroups of $G$ that contain that set.

Consequently the assertion "$f \in F$" means: $f$ lies in every subgroup of $G$ that contains all maps with property $T$ — equivalently, $f$ can be written as a finite product of maps with property $T$ and of inverses of such maps. It is not, as stated, the assertion that $f$ itself has property $T$. Having property $T$ implies membership in $F$; the reverse implication is a separate claim and is not part of what is written here.

Extending a map of $I$ to the whole line

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

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

This $\hat f$ is again an order isomorphism, now of $\mathbb{R}$ onto itself, and it agrees with $f$ on $I$.

Finite binary trees, their leaves, and their marks

A tree here is a finite rooted binary tree built from two constructions: a single leaf, or a node formed from an ordered pair of trees (its left and right subtrees). The leaf count of a leaf is $1$, and the leaf count of a node is the sum of the leaf counts of its two subtrees.

The marks of a tree $t$ are a finite list of real numbers, defined by the following subdivision recursion. For a tree $s$ and an interval $[a,b]$, put $M(s,a,b) =$ the empty list if $s$ is a leaf, and, if $s$ is a node with left subtree $\ell$ and right subtree $r$, put

$$M(s,a,b) = M\!\left(\ell, a, \tfrac{a+b}{2}\right) \; \frown \; \left(\tfrac{a+b}{2}\right) \; \frown \; M\!\left(r, \tfrac{a+b}{2}, b\right),$$

where $\frown$ denotes concatenation of lists. The marks of $t$ are then

$$\operatorname{marks}(t) = (0) \frown M(t,0,1) \frown (1).$$

Concretely, if $t$ has $N$ leaves then $\operatorname{marks}(t)$ is a list of $N+1$ real numbers, strictly increasing, beginning with $0$ and ending with $1$; it lists the endpoints of the subdivision of $[0,1]$ into $N$ standard dyadic intervals obtained by repeatedly halving according to the shape of $t$. For example, the marks of a single leaf are $(0,1)$; the marks of the node with two leaf subtrees are $(0,\tfrac12,1)$; the marks of the node whose left subtree is a leaf and whose right subtree is the node with two leaf subtrees are $\left(0,\tfrac12,\tfrac34,1\right)$; and the marks of the node whose left subtree is the node with two leaf subtrees and whose right subtree is a leaf are $\left(0,\tfrac14,\tfrac12,1\right)$.

A tree diagram is a triple consisting of a tree $t_-$ (the domain tree), a tree $t_+$ (the range tree), and a guarantee that $t_-$ and $t_+$ have the same leaf count. In ordinary mathematical language: an ordered pair of trees with equally many leaves. Nothing else is required of the pair, and no bound is placed on the size of the trees.

Carets and reducedness

A node both of whose subtrees are single leaves will be called a caret. For a tree $t$ and a natural number $k$, say that $t$ has a caret at position $k$ when the $k$-th and $(k+1)$-st leaves of $t$, counted from $0$ in left-to-right order, are exactly the two leaves hanging from one such node. The underlying recursion is: a single leaf has a caret at no position; and for a node with left subtree $\ell$ of leaf count $L$ and right subtree $r$,

• if $k+1 < L$, the node has a caret at $k$ exactly when $\ell$ does;
• if $L \le k$, the node has a caret at $k$ exactly when $r$ has a caret at position $k - L$;
• in the remaining case $k = L-1$ (the two leaves straddle the root), the node has a caret at $k$ exactly when $\ell$ and $r$ are both single leaves.

In particular, if $t$ has $N$ leaves then $t$ has a caret at no position $k \ge N-1$: for such $k$ the recursion runs off the right-hand end of the tree and returns "no". For instance, the three-leaf tree with a leaf on the left and a caret on the right has a caret at position $1$ and nowhere else, while the three-leaf tree with a caret on the left and a leaf on the right has a caret at position $0$ and nowhere else.

A tree diagram $(t_-,t_+)$ is reduced when

$$\text{for every natural number } k: \quad \text{not both } t_- \text{ and } t_+ \text{ have a caret at position } k .$$

Because the quantifier runs over all natural numbers while a caret can only occur at a position below $N-1$ (where $N$ is the common leaf count), this is a genuine restriction only for $0 \le k \le N-2$; for every larger $k$ both conjuncts are false and the condition holds automatically. If either tree is a single leaf, the condition holds vacuously.

What it is for a diagram to represent a map

A tree diagram $(t_-,t_+)$ represents $f \in G$ when all three of the following hold. Write $\operatorname{marks}(t_-) = (u_0,u_1,\dots,u_N)$ and $\operatorname{marks}(t_+) = (v_0,v_1,\dots,v_N)$, which have the same length $N+1$ because the two trees have the same leaf count $N$.

1. $f \in F$, in the sense of the subgroup generated by the maps with property $T$ described above.

2. Affineness along the marks of the domain tree. For each index $i$ with $0 \le i \le N-1$ there exist real numbers $a_i$ and $c_i$ such that

$$\hat f(z) = a_i z + c_i \qquad \text{for all } z \text{ with } u_i \le z \le u_{i+1}.$$

The slopes $a_i$ here are arbitrary real numbers: they are not required to be powers of two, nor positive, nor non-zero. The condition is imposed on consecutive pairs of the marks of the domain tree only; no affineness condition is imposed along the marks of the range tree. Since $[u_i,u_{i+1}] \subseteq [0,1]$, on these intervals $\hat f$ is just $f$.

3. The marks are carried over in order. Applying $\hat f$ to each entry of $\operatorname{marks}(t_-)$ yields exactly the list $\operatorname{marks}(t_+)$:

$$\big(\hat f(u_0), \hat f(u_1), \dots, \hat f(u_N)\big) = (v_0,v_1,\dots,v_N),$$

that is, $f(u_i) = v_i$ for every $i$. This is an equality of lists, so it includes the assertion that the two lists have the same length; that part is automatic from the equality of leaf counts.

The statement being asserted

For every order-automorphism $f$ of the unit interval $[0,1]$ which belongs to $F$ — the subgroup of the group of order-automorphisms of $[0,1]$ generated by all maps having property $T$ (piecewise affine with slopes integral powers of two, with finitely many breakpoints, all dyadic) — there exists a tree diagram $(t_-,t_+)$, i.e. a pair of finite binary trees with the same number $N$ of leaves, such that:

• the diagram is reduced: there is no position $k$ at which $t_-$ and $t_+$ both have a caret whose two children are leaves; and
• the diagram represents $f$: $f$ lies in $F$; the extension of $f$ by the identity outside $[0,1]$ is affine (with some real slope and intercept, possibly different on each piece) on each of the $N$ closed intervals cut out by consecutive marks of $t_-$; and $f$ carries the $N+1$ marks of $t_-$, in order, onto the $N+1$ marks of $t_+$.

The quantifier over $f$ is universal; $f$ is an ordinary variable of the statement (it is supplied implicitly rather than written out at each use, which does not change the assertion). The quantifier over diagrams is a bare existential: existence of such a diagram is claimed, not uniqueness, and no bound on $N$ is claimed. There are no side conditions of any other kind: no typeclass or structural hypotheses beyond those already contained in "$f$ is an order-automorphism of $[0,1]$" and "$f \in F$".

Note that the first clause of "represents" repeats the hypothesis verbatim, so it adds nothing to what must be produced.

Degenerate and edge cases

• The hypothesis is satisfiable, and by more than one map. $F$ is a subgroup, so the identity map of $[0,1]$ lies in $F$. It also contains non-identity maps: the map

$$z \mapsto \begin{cases} z/2, & 0 \le z \le 1/2,\\ z - 1/4, & 1/2 \le z \le 3/4,\\ 2z-1, & 3/4 \le z \le 1,\end{cases}$$

has property $T$, taking $B = \{1/2, 3/4\}$ (both dyadic), and hence lies in $F$; it is not the identity, since it sends $1/2$ to $1/4$. So the statement is not vacuous.

• The conclusion can be met. For the identity map, the diagram in which both trees are a single leaf works: it is reduced (a single leaf has no carets), its domain marks are $(0,1)$, the identity is affine on $[0,1]$ with slope $1$ and intercept $0$, and the image of $(0,1)$ is $(0,1)$, the marks of the range tree. For the non-identity map displayed above, the diagram whose domain tree has marks $\left(0,\tfrac12,\tfrac34,1\right)$ (a node with a leaf on the left and a caret on the right) and whose range tree has marks $\left(0,\tfrac14,\tfrac12,1\right)$ (a node with a caret on the left and a leaf on the right) works: the two trees have three leaves each, their caret positions are $1$ and $0$ respectively, so no position carries a caret in both, and the map is affine on each of $[0,\tfrac12]$, $[\tfrac12,\tfrac34]$, $[\tfrac34,1]$ and sends $0,\tfrac12,\tfrac34,1$ to $0,\tfrac14,\tfrac12,1$. So the conclusion is satisfiable, and not only by the one-leaf diagram.

• The one-leaf diagram is not a universal witness. If both trees of a diagram are a single leaf, the reducedness condition is automatic, but the representation conditions say exactly that $\hat f$ is affine on all of $[0,1]$ and sends $(0,1)$ to $(0,1)$; combined with $f(0)=0$ and $f(1)=1$ this forces $f$ to be the identity. For any other $f$ in $F$ the existential must be witnessed by a larger diagram.

• Reducedness beyond the last leaf. As noted, the condition is quantified over all natural numbers $k$ including those exceeding the number of leaves; at those positions neither tree has a caret, so nothing is asserted there. Reducedness is exactly the finitely many conditions at positions $0,\dots,N-2$.

• No dyadic or power-of-two condition appears in the conclusion. The slopes in the affineness clause are unconstrained reals, and there is no separate requirement that the marks form a standard dyadic partition — though they do so automatically, by the construction of marks from a tree.