Weak order is a partial order with finite graded intervals; covers and the inversion-set criterion

Reflexivity and minimum: for every $v\in W$ one has $v=v\cdot 1$ with $\mathrm{\ell }(v)=\mathrm{\ell }(v)+\mathrm{\ell }(1)=\mathrm{\ell }(v)+0$, so $v{\le }_{R}v$, and $1\cdot v=v$ with $\mathrm{\ell }(v)=\mathrm{\ell }(1)+\mathrm{\ell }(v)$, so $1{\le }_{R}v$; reading the same products in the other order gives $v{\le }_{L}v$ and $1{\le }_{L}v$. Hence both relations are reflexive and $1$ is below every element in both orders.

Transitivity: if $u{\le }_{R}y$ and $y{\le }_{R}v$, write $y=ux$ and $v=y{x}^{\mathrm{\prime }}$ with $\mathrm{\ell }(y)=\mathrm{\ell }(u)+\mathrm{\ell }(x)$ and $\mathrm{\ell }(v)=\mathrm{\ell }(y)+\mathrm{\ell }(x^{\mathrm{\prime }})$. Then $v=u(x{x}^{\mathrm{\prime }})$, and $\mathrm{\ell }(v)=\mathrm{\ell }(u)+\mathrm{\ell }(x)+\mathrm{\ell }(x^{\mathrm{\prime }})\ge \mathrm{\ell }(u)+\mathrm{\ell }(x{x}^{\mathrm{\prime }})\ge \mathrm{\ell }(v)$ by subadditivity together with the word bound $v=u(x{x}^{\mathrm{\prime }})$; hence $\mathrm{\ell }(v)=\mathrm{\ell }(u)+\mathrm{\ell }(x{x}^{\mathrm{\prime }})$ and $u{\le }_{R}v$. The same computation with the products in the other order shows that ${\le }_L$ is transitive.

Inversion: the map $w\mapsto w^{-1}$ is a bijection of $W$ with inverse itself, and $u{\le }_{R}v⟺u^{-1}{\le }_L{v}^{-1}$ for all $u,v$; hence it is an order isomorphism $(W,{\le }_R)\to (W,{\le }_L)$. This completes clause (1).

Ball finiteness: every $w$ with $\mathrm{\ell }(w)\le k$ has a reduced expression of length $\mathrm{\ell }(w)\le k$, so the ball $\{w:\mathrm{\ell }(w)\le k\}$ is the set of values of the finitely many words in $S$ of lengths $0,1,\dots ,k$; those words number $1+\mathrm{\mid }S\mathrm{\mid }+\cdots +\mathrm{\mid }S{\mathrm{\mid }}^k$, and listing their values exhibits the ball as the image of a finite list, hence finite with at most that many elements.

The criterion, forward direction, and cardinalities: if $u{\le }_{R}v$, then $N(u^{-1})\subseteq N(v^{-1})$. By the prefix property there are reduced expressions $u=s_1\cdots s_k$ and $v=s_1\cdots s_k{s}_1^{\mathrm{\prime }}\cdots s_q^{\mathrm{\prime }}$. By the prefix-root formula, $N(u^{-1})=\{\rho (s_1\cdots s_{i-1})e_{s_i}:1\le i\le k\}$ and $N(v^{-1})=\{\rho (s_1\cdots s_{j-1})e_{s_j}:1\le j\le k+q\}$, so the first is contained in the second. The same formula gives $\mathrm{\mid }N(w)\mathrm{\mid }=\mathrm{\ell }(w)$ and $\mathrm{\mid }N(w^{-1})\mathrm{\mid }=\mathrm{\ell }(w)$ for every $w$.

Antisymmetry and equal-length uniqueness: if $u{\le }_{R}v$ and $v{\le }_{R}u$ then $\mathrm{\ell }(u)\le \mathrm{\ell }(v)\le \mathrm{\ell }(u)$, so $\mathrm{\ell }(u)=\mathrm{\ell }(v)$; then $\mathrm{\ell }(u^{-1}v)=\mathrm{\ell }(v)-\mathrm{\ell }(u)=0$ by the length identity, so $u^{-1}v=1$ and $v=u$. In particular $u{\le }_{R}v$ together with $\mathrm{\ell }(u)=\mathrm{\ell }(v)$ forces $u=v$; the same argument in ${\le }_L$ gives antisymmetry there. Together with steps 1.1 and 1.2 this shows that ${\le }_R$ and ${\le }_L$ are partial orders with minimum $1$.

The criterion, converse direction, by induction on $\mathrm{\ell }(u)$: assume $N(u^{-1})\subseteq N(v^{-1})$; then $u{\le }_{R}v$. If $\mathrm{\ell }(u)=0$ then $u=1$ and $1{\le }_{R}v$ by step 1.1. Otherwise choose a reduced expression $u=s{t}_2\cdots t_k$ with $k=\mathrm{\ell }(u)\ge 1$. By [F12], $su=t_2\cdots t_k$, so $\mathrm{\ell }(su)\le k-1=\mathrm{\ell }(u)-1$; by the length-change property [F4] this forces $\mathrm{\ell }(su)=\mathrm{\ell }(u)-1$, hence $s\in D_L(u)$ by [F8]. The root-length criterion applied to $u^{-1}$ and the definition of $N$ give $e_s\in N(u^{-1})\subseteq N(v^{-1})$, and the same criterion for $v^{-1}$ gives $s\in D_L(v)$. By the left-translation property [F15] it suffices to prove $su{\le }_{R}sv$; the induction hypothesis applies to the shorter element $su$ once $N((su{)}^{-1})\subseteq N((sv{)}^{-1})$ is shown. Now $(su{)}^{-1}=u^{-1}s$ and $(sv{)}^{-1}=v^{-1}s$. By [F6], $\mathrm{\ell }((su{)}^{-1})=\mathrm{\ell }(su)=\mathrm{\ell }(u)-1<\mathrm{\ell }(u^{-1})$; likewise $\mathrm{\ell }((sv{)}^{-1})<\mathrm{\ell }(v^{-1})$, so the descent case of the recursion [F5] gives $N(u^{-1}s)=s(N(u^{-1})\setminus \{e_s\})$ and $N(v^{-1}s)=s(N(v^{-1})\setminus \{e_s\})$. Since $e_s$ lies in both $N(u^{-1})$ and $N(v^{-1})$, the inclusion remains true after removing $e_s$, and applying the map $\rho (s)$ to both sets preserves inclusion; hence $N((su{)}^{-1})\subseteq N((sv{)}^{-1})$. Thus $su{\le }_{R}sv$ by induction and $u{\le }_{R}v$ by left translation.

Cover characterization: $u{⋖}_{R}v$ if and only if $v=us$ for some $s\in S$ with $\mathrm{\ell }(v)=\mathrm{\ell }(u)+1$. For the forward direction assume $u{⋖}_{R}v$; then $u{\le }_{R}v$ with $u\mathrm{\ne }v$, so $v=ux$ with $\mathrm{\ell }(v)=\mathrm{\ell }(u)+\mathrm{\ell }(x)$ and $x\mathrm{\ne }1$. Write a reduced expression $x=s_1\cdots s_k$, $k=\mathrm{\ell }(x)\ge 1$, and put $u_i:=u{s}_1\cdots s_i$ for $0\le i\le k$. For each $i$, subadditivity gives $\mathrm{\ell }(u_i)\le \mathrm{\ell }(u)+i$. Put $y_i:=s_{i+1}\cdots s_k$ (the empty word when $i=k$); its displayed word gives $\mathrm{\ell }(y_i)\le k-i$, and $v=u_i{y}_i$. Hence $\mathrm{\ell }(v)\le \mathrm{\ell }(u_i)+\mathrm{\ell }(y_i)\le \mathrm{\ell }(u_i)+k-i$, so $\mathrm{\ell }(u_i)\ge \mathrm{\ell }(u)+i$ and therefore $\mathrm{\ell }(u_i)=\mathrm{\ell }(u)+i$. Since $\mathrm{\ell }(v)=\mathrm{\ell }(u)+k$ and $\mathrm{\ell }(u_i)=\mathrm{\ell }(u)+i$, subadditivity in $v=u_i{y}_i$ also gives $\mathrm{\ell }(y_i)\ge k-i$; together with the displayed-word bound this yields $\mathrm{\ell }(y_i)=k-i$ for every $i$. If $k\ge 2$, then $u_1=u{s}_1$ and $\mathrm{\ell }(s_1)=1$ by [A1], so $u{<}_R{u}_1$. Since $v=u_1{y}_1$ and $\mathrm{\ell }(y_1)=k-1$, one has $u_1{\le }_{R}v$; also $\mathrm{\ell }(u_1)<\mathrm{\ell }(v)$, giving $u{<}_R{u}_1{<}_{R}v$, contrary to the cover. Thus $k=1$, $v=u{s}_1$ and $\mathrm{\ell }(v)=\mathrm{\ell }(u)+1$. For the converse assume $v=us$ and $\mathrm{\ell }(v)=\mathrm{\ell }(u)+1$; by [A1], $\mathrm{\ell }(s)=1$, so $u{\le }_{R}v$. If $u{\le }_{R}w{\le }_{R}v$, the length identity [F2] gives $\mathrm{\ell }(u)\le \mathrm{\ell }(w)\le \mathrm{\ell }(u)+1$. If $\mathrm{\ell }(w)=\mathrm{\ell }(u)$ then $w=u$ by step 2.1; if $\mathrm{\ell }(w)=\mathrm{\ell }(v)$ then $w=v$ by step 2.1. Hence no element lies strictly between $u$ and $v$, and $u\mathrm{\ne }v$, so $u{⋖}_{R}v$. For the left-handed version, $u{⋖}_{L}v$ is equivalent under the inversion isomorphism [F1] to $u^{-1}{⋖}_R{v}^{-1}$; the right-handed result and length invariance [F6] give $v^{-1}=u^{-1}s$ with a one-length rise, hence $v=su$ with $\mathrm{\ell }(v)=\mathrm{\ell }(u)+1$, and conversely.

The left criterion and the embedding: by [F1], $u{\le }_{L}v⟺u^{-1}{\le }_R{v}^{-1}$, and applying steps 1.5 and 2.2 to the pair $(u^{-1},v^{-1})$ gives $u{\le }_{L}v⟺N(u)\subseteq N(v)$. Hence $w\mapsto N(w^{-1})$ preserves and reflects ${\le }_R$ and is injective, since $N(u^{-1})=N(v^{-1})$ yields $u{\le }_{R}v$ and $v{\le }_{R}u$, hence $u=v$ by antisymmetry; it is length-preserving by $\mathrm{\mid }N(w^{-1})\mathrm{\mid }=\mathrm{\ell }(w)$. This completes clause (4).

Chains of covers: $u{\le }_{R}v$ if and only if there is a chain $u=u_0{⋖}_R{u}_1{⋖}_R\cdots {⋖}_R{u}_m=v$, and then $m=\mathrm{\ell }(v)-\mathrm{\ell }(u)$. If $u{\le }_{R}v$, put $x:=u^{-1}v$, so $\mathrm{\ell }(x)=\mathrm{\ell }(v)-\mathrm{\ell }(u)$; choose a reduced expression $x=s_1\cdots s_m$ and set $u_i:=u{s}_1\cdots s_i$. The estimates in step 3.1 give $\mathrm{\ell }(u_i)=\mathrm{\ell }(u)+i$ and $\mathrm{\ell }(s_{i+1}\cdots s_m)=m-i$, so $u{\le }_R{u}_i{\le }_{R}v$ for every $i$. Since $u_{i+1}=u_i{s}_{i+1}$ and $\mathrm{\ell }(u_{i+1})=\mathrm{\ell }(u_i)+1$, each consecutive pair is a cover by step 3.1's converse, giving a chain of $m=\mathrm{\ell }(v)-\mathrm{\ell }(u)$ covers. Conversely, if $u=u_0{⋖}_R\cdots {⋖}_R{u}_m=v$, then repeated transitivity from step 1.2 gives $u{\le }_{R}v$, and each cover adds exactly one to the length by step 3.1's forward direction, so $\mathrm{\ell }(v)=\mathrm{\ell }(u)+m$ and $m=\mathrm{\ell }(v)-\mathrm{\ell }(u)$. For left order, apply the right-hand result to $u^{-1}{\le }_R{v}^{-1}$ and invert each element of the chain; inversion preserves covers by [F1] and lengths by [F6].

Graded intervals: if $u{\le }_{R}v$, then $[u,v{]}_R\subseteq \{w:\mathrm{\ell }(w)\le \mathrm{\ell }(v)\}$ by the length identity, so $[u,v{]}_R$ is finite by step 1.4 and is a finite poset with least element $u$; its unique minimal element is $u$, because every $x\in [u,v{]}_R$ satisfies $u{\le }_{R}x$. The map $x\mapsto \mathrm{\ell }(x)-\mathrm{\ell }(u)$ takes values in $\mathbb{N}$ on $[u,v{]}_R$ and has value $0$ at $u$. If $x⋖y$ in the interval poset, then $x{<}_{R}y$ and no $z$ with $x{<}_{R}z{<}_{R}y$ lies in $[u,v{]}_R$; an intermediate $z$ in $W$ would satisfy $u{\le }_{R}x{<}_{R}z{<}_{R}y{\le }_{R}v$, hence lie in $[u,v{]}_R$, so $x{⋖}_{R}y$ in $W$ as well, and step 3.1's forward direction gives $\mathrm{\ell }(y)=\mathrm{\ell }(x)+1$. Thus $x\mapsto \mathrm{\ell }(x)-\mathrm{\ell }(u)$ is a rank function, so $[u,v{]}_R$ is graded. A maximal chain $u=x_0<\cdots <x_t=v$ in it consists of covers, so its ranks increase by one at each step from $0$ to $\mathrm{\ell }(v)-\mathrm{\ell }(u)$: it has exactly $\mathrm{\ell }(v)-\mathrm{\ell }(u)+1$ elements. Finally, for a reduced expression $u^{-1}v=s_1^{\mathrm{\prime }}\cdots s_m^{\mathrm{\prime }}$, the chain of step 4.1, $u{⋖}_{R}u{s}_1^{\mathrm{\prime }}{⋖}_R\cdots {⋖}_{R}u{s}_1^{\mathrm{\prime }}\cdots s_m^{\mathrm{\prime }}=v$, is a chain of covers in $W$ between elements of $[u,v{]}_R$, hence a maximal chain in $[u,v{]}_R$. For left order, inversion identifies $[u,v{]}_L$ with $[u^{-1},v^{-1}{]}_R$ and [F6] shows that the length shift is preserved; the same rank and maximal-chain conclusions follow.

The descent-root dictionary: for $w\in W$ and $s\in S$, $s\in D_L(w)$ means $\mathrm{\ell }(sw)<\mathrm{\ell }(w)$; since $\mathrm{\ell }(sw)=\mathrm{\ell }((sw{)}^{-1})=\mathrm{\ell }(w^{-1}s)$ and [F6] gives $\mathrm{\ell }(w^{-1})=\mathrm{\ell }(w)$, the root-length criterion applied to $w^{-1}$ gives $s\in D_L(w)⟺\rho (w^{-1})e_s\in {\mathrm{\Phi }}_{-}$, which by [F13] is equivalent to $e_s\in N(w^{-1})$. Similarly, $s\in D_R(w)$ means $\mathrm{\ell }(ws)<\mathrm{\ell }(w)$, which by the root-length criterion applied to $w$ is equivalent to $\rho (w)e_s\in {\mathrm{\Phi }}_{-}$, that is to $e_s\in N(w)$. No Choice was used anywhere in this proof.