Bruhat order on a finite Weyl group

Define a temporary relation $u⪯v$ by the existence of the displayed saturated reflection chain. Empty chains prove reflexivity, concatenation proves transitivity, and each nonempty chain strictly increases length, so $u⪯v⪯u$ forces $u=v$. Each chain has exactly $\mathrm{\ell }(v)-\mathrm{\ell }(u)$ steps. Thus this is a partial order before any subword assertion has been established. Right multiplication $x\mapsto xs$ by a simple reflection is also a root-reflection step when it increases length, since $xs=(xs{x}^{-1})x$ and the reflection formula gives $x{s}_{\alpha }{x}^{-1}=s_{x\alpha }$, a root reflection because $W$ preserves the root set.

Fix a simple reflection $s$, and set $x^{+}=xs$ if $\mathrm{\ell }(xs)=\mathrm{\ell }(x)+1$, and $x^{+}=x$ otherwise. We show that a single saturated step $x⪯y=tx$, with $\mathrm{\ell }(y)=\mathrm{\ell }(x)+1$, implies $x^{+}⪯y^{+}$. If both right products increase length, $ys=t(xs)$ is one saturated step. If both decrease, the original step suffices. If $xs$ decreases and $ys$ increases, use $x⪯y⪯ys$, the second step supplied by step 1.1. In the remaining case $xs$ increases and $ys$ decreases, take a reduced word for $y$ ending in $s$, possible by F2. As $x=ty$ and $\mathrm{\ell }(x)=\mathrm{\ell }(y)-1$, strong exchange deletes one letter from that word to give a reduced word for $x$. If a letter before its last one were deleted, this reduced word for $x$ would still end in $s$, forcing $xs$ to decrease length. Therefore the deleted letter is the last one, $x=ys$, and $x^{+}=y=y^{+}$. These four cases are exhaustive.

Conversely suppose $u⪯v$ and fix any reduced expression for $v$. Follow a saturated chain backwards from $v$ to $u$. At each step, F2 deletes one letter from the current reduced expression to represent the next element. Since the new length is exactly one less, the resulting expression is already reduced. Repeating leaves a reduced expression for $u$ as an ordered subword of the original expression for $v$. A zero-length chain leaves the whole expression unchanged. Thus a saturated chain implies the subword condition in every reduced expression, not just some one.

Apply step 2.1 to each edge of a saturated chain and concatenate the resulting chains, omitting repeated endpoints. It follows that $a⪯b$ implies $a^{+}⪯b^{+}$. This is a proved lifting property of the temporary order; it has not used any subword or expression-independence assertion.

Suppose a reduced word $\mathbf{v}$ for $v$ contains a specified reduced subword for $u$. Induct on $\mathrm{\ell }(v)$ to prove $u⪯v$. The empty word is immediate. Write $\mathbf{v}={\mathbf{v}}^{\mathrm{\prime }}s$, where ${\mathbf{v}}^{\mathrm{\prime }}$ is reduced for $v^{\mathrm{\prime }}$. If the chosen subword omits the last letter, induction gives $u⪯v^{\mathrm{\prime }}$ and step 1.1 gives $v^{\mathrm{\prime }}⪯v$. If it uses the last letter, its preceding selected letters are reduced for some $a$ with $u=as$ and $\mathrm{\ell }(u)=\mathrm{\ell }(a)+1$; otherwise shortening those preceding letters would contradict reducedness of the subword. Induction gives $a⪯v^{\mathrm{\prime }}$. Both $a$ and $v^{\mathrm{\prime }}$ increase length on right multiplication by $s$, so step 3.1 gives $u=a^{+}⪯(v^{\mathrm{\prime }}{)}^{+}=v$. This proves the implication by a finite induction.

Steps 2.2 and 4.1 prove that the Definition's subword condition is exactly $⪯$, and also prove independence of the chosen reduced expression. Step 1.1 therefore supplies all partial-order axioms and the asserted saturated-chain equivalence. The identity is represented by the empty subword; rank zero gives the one-element order. Length-one cases are included in the induction, and equality $u=v$ has an empty chain. All arguments concern finite words or chains and use no AC.