Finiteness of Bruhat intervals, the chain refinement property, and grading by length

For (1), fix a reduced expression $v=s_1\cdots s_q$. For every $x\in [u,v]$ the relation $x\le v$ and [F1] provide at least one subset $P\subseteq \{1,\dots ,q\}$ with $x$ the product of the letters at the positions in $P$ in increasing order; assign to $x$ the lexicographically first such subset, a determinate rule on a nonempty finite set of subsets of $\{1,\dots ,q\}$. The resulting map $[u,v]\to \{0,1{\}}^q$ is injective, because a subset determines $x$ as the product of its letters in the given order; hence $\mathrm{\mid }[u,v]\mathrm{\mid }\le 2^q=2^{\mathrm{\ell }(v)}$, which proves (1).

For (2), induct on $d:=\mathrm{\ell }(v)-\mathrm{\ell }(u)\ge 0$. If $d=0$ then $u=v$ by the strict length increase of [F3], and the one-element chain $x_0:=u=v$ works.

For the inductive step of step 1.2, let $d>0$, so that $u\mathrm{\ne }v$. Fix a reduced expression $v=s_1\cdots s_q$ and a reduced subword expression of $u$ inside it, written in deleted-position form; the augmentation lemma [F2] gives $x_1\in W$ with $u\to x_1$, $\mathrm{\ell }(x_1)=\mathrm{\ell }(u)+1$, and $x_1$ the product of a reduced subword of the same word $s_1\cdots s_q$. By the subword criterion [F1], $x_1\le v$; the length gap $\mathrm{\ell }(v)-\mathrm{\ell }(x_1)$ is $d-1$, so the induction hypothesis of step 1.2 applies to the pair $(x_1,v)$ and produces a chain $x_1<y_2<\cdots <y_m=v$ with lengths $\mathrm{\ell }(x_1)+1,\dots ,\mathrm{\ell }(v)$; prepending the edge $u\to x_1$ gives the required chain, each step of which is a Bruhat edge increasing the length by exactly one. This proves (2).

For (3), along a strict step the length strictly increases by [F3], so a chain from $u$ to $v$ with $m$ strict steps satisfies $\mathrm{\ell }(v)\ge \mathrm{\ell }(u)+m$, that is, $m\le \mathrm{\ell }(v)-\mathrm{\ell }(u)$. If $m<\mathrm{\ell }(v)-\mathrm{\ell }(u)$, then some step $x_{i-1}<x_i$ of the chain has $\mathrm{\ell }(x_i)-\mathrm{\ell }(x_{i-1})\ge 2$, and step 2.1 applied to that pair produces $z$ with $x_{i-1}<z<x_i$, so the chain is not maximal; hence every maximal chain has exactly $\mathrm{\ell }(v)-\mathrm{\ell }(u)$ steps, that is, $\mathrm{\ell }(v)-\mathrm{\ell }(u)+1$ elements. Thus the rank function $x\mapsto \mathrm{\ell }(x)-\mathrm{\ell }(u)$ is well defined on $[u,v]$ and every maximal chain between two comparable elements has the same length. If $x<y$ with no $z$ satisfying $x<z<y$, then the two-element chain $x<y$ is maximal in $[x,y]$, so it has exactly $\mathrm{\ell }(y)-\mathrm{\ell }(x)$ strict steps, whence $\mathrm{\ell }(y)=\mathrm{\ell }(x)+1$. No use of the Axiom of Choice is made: the only selection is the lexicographically first subword of step 1.1, a deterministic rule on a finite set.