The subword characterization of Bruhat order and its independence of the reduced expression

For the implication from left to right in (1), let $u=x_0\to x_1\to \cdots \to x_m=w$ be a chain exhibiting $u\le w$, with $x_{j+1}=x_j{t}_j$, $t_j\in T$ and $\mathrm{\ell }(x_{j+1})>\mathrm{\ell }(x_j)$; the case $m=0$ (so $u=w$) is the case of the full subword, and we prove by downward induction on $j$ that every $x_j$ is the product of a subword of $s_1\cdots s_q$. For the base case $j=m$ this is clear since $x_m=w=s_1\cdots s_q$.

For the implication from right to left in (1), assume $u=s_{i_1}\cdots s_{i_k}$ with $1\le i_1<\cdots <i_k\le q$; reducing that word by two-letter deletions if necessary, we may suppose it is a reduced expression of $u$, since deletions only remove positions and so the result is still a subword of $s_1\cdots s_q$. Induct on $d:=\mathrm{\ell }(w)-\mathrm{\ell }(u)\ge 0$: if $d=0$ then $k=q$ and $u=w$, so $u\le w$ by reflexivity.

For the inductive step of step 1.1, suppose $x_{j+1}$ is the product of the subword at positions $P_{j+1}\subseteq \{1,\dots ,q\}$. If the word $(s_p{)}_{p\in P_{j+1}}$ is not reduced, apply the two-letter deletion property repeatedly to replace it by a reduced expression of $x_{j+1}$ obtained by deleting letters, so that the result is again a subword of $s_1\cdots s_q$; applying the right-handed strong exchange of [F2] to this reduced expression of $x_{j+1}$ and to $t_j$ (legal since $\mathrm{\ell }(x_{j+1}{t}_j)=\mathrm{\ell }(x_j)<\mathrm{\ell }(x_{j+1})$) exhibits $x_j=x_{j+1}{t}_j$ as that word with one letter deleted, hence as the product of a subword of $s_1\cdots s_q$.

For the inductive step of step 1.2, let $d>0$, so $u\mathrm{\ne }w$; the augmentation lemma [F1] applied to the fixed reduced expression $w=s_1\cdots s_q$ produces $v\in W$ with $u\to v$, $\mathrm{\ell }(v)=\mathrm{\ell }(u)+1$, and $v$ the product of a reduced subword of $s_1\cdots s_q$. The induction hypothesis applies to $v$ (the length gap is $d-1$) and gives $v\le w$, whence $u\le v\le w$ by transitivity.

This completes the downward induction of step 2.1: $x_0=u$ is the product of a subword of $s_1\cdots s_q$, and applying the two-letter deletion property once more to that subword word produces a reduced subword expression of $u$, whose length is $\mathrm{\ell }(u)$; hence the indices in (1) may always be chosen with $k=\mathrm{\ell }(u)$. Together with step 2.2 this proves (1) in both directions.

For (2), the statement of part (1) is formulated for an arbitrary reduced expression $w=s_1\cdots s_q$ of $w$ and its proof used nothing particular about that expression, so (a) implies (b); (b) trivially implies (c); and (c) implies (a) by the right-to-left direction of (1). Finally the empty subword of any reduced expression of $w$ realizes $1$ and is one of the subwords allowed in (1), so $1\le w$ for every $w$, which is (3). No use of the Axiom of Choice is made: the induction runs on natural numbers, deletions act on the current explicit word, and the subword expressions used are the given ones.