Binary meets, meets of arbitrary nonempty subsets, and joins of bounded subsets in weak order

For all $x,y\in W$ the set $E(x,y)=[1,x{]}_R\cap [1,y{]}_R$ is finite: by [F14] the interval $[1,x{]}_R=\{w:w{\le }_{R}x\}$ is finite, and $E(x,y)\subseteq [1,x{]}_R$ is a subset of a finite set, hence finite; in particular $E(x,y)$ has an element of maximal length.

Common atoms: let $z\in E(x,y)$ have maximal length and let $s\in S$ lie in $E(x,y)$; then $s{\le }_{R}z$. By [F9], $z{\le }_{R}x$ and $z{\le }_{R}y$ give reduced expressions $x=z{x}^{\mathrm{\prime }}$ and $y=z{y}^{\mathrm{\prime }}$ with $\mathrm{\ell }(x)=\mathrm{\ell }(z)+\mathrm{\ell }(x^{\mathrm{\prime }})$ and $\mathrm{\ell }(y)=\mathrm{\ell }(z)+\mathrm{\ell }(y^{\mathrm{\prime }})$. Suppose, for contradiction, that $\mathrm{\ell }(sz)=\mathrm{\ell }(z)+1$; by [F7] the only other possibility is $\mathrm{\ell }(sz)=\mathrm{\ell }(z)-1$, so this is the case to exclude. Since $s{\le }_{R}x$, the defining length-additive factorization gives $x=sa$ and $\mathrm{\ell }(x)=\mathrm{\ell }(s)+\mathrm{\ell }(a)$ for some $a$; as $s^2=1$, $a=sx$, and [A1] gives $\mathrm{\ell }(x)=1+\mathrm{\ell }(sx)$. Thus Tits exchange [F5] applies to the reduced expression $z_{\mathrm{r}\mathrm{e}\mathrm{d}}{x}_{\mathrm{r}\mathrm{e}\mathrm{d}}^{\mathrm{\prime }}$ of $x$ and the letter $s$: the element $sx$ is that word with exactly one letter deleted. If the deleted letter lies in $z_{\mathrm{r}\mathrm{e}\mathrm{d}}$, then $sx=\tilde{z}{x}^{\mathrm{\prime }}$ for the word $\tilde{z}$ obtained from $z_{\mathrm{r}\mathrm{e}\mathrm{d}}$ by deleting one letter, so $\mathrm{\ell }(\tilde{z})\le \mathrm{\ell }(z)-1$; cancelling $x^{\mathrm{\prime }}$ on the right in $x=z{x}^{\mathrm{\prime }}=s\tilde{z}{x}^{\mathrm{\prime }}$ gives $z=s\tilde{z}$, and $s^2=1$ gives $sz=\tilde{z}$, whence $\mathrm{\ell }(sz)=\mathrm{\ell }(\tilde{z})\le \mathrm{\ell }(z)-1$, contradicting $\mathrm{\ell }(sz)=\mathrm{\ell }(z)+1$. If instead the deleted letter lies in $x_{\mathrm{r}\mathrm{e}\mathrm{d}}^{\mathrm{\prime }}$, then $sx=z{x}^{\mathrm{\prime }\mathrm{\prime }}$ for the word $x^{\mathrm{\prime }\mathrm{\prime }}$ obtained from $x_{\mathrm{r}\mathrm{e}\mathrm{d}}^{\mathrm{\prime }}$ by deleting one letter, so $\mathrm{\ell }(x^{\mathrm{\prime }\mathrm{\prime }})\le \mathrm{\ell }(x^{\mathrm{\prime }})-1$. Since $z=s(sz)$, $s^2=1$ gives $x=(sz)x^{\mathrm{\prime }\mathrm{\prime }}$; therefore $\mathrm{\ell }(x)=\mathrm{\ell }(z)+\mathrm{\ell }(x^{\mathrm{\prime }})\le \mathrm{\ell }(sz)+\mathrm{\ell }(x^{\mathrm{\prime }\mathrm{\prime }})$ forces $\mathrm{\ell }(x^{\mathrm{\prime }\mathrm{\prime }})=\mathrm{\ell }(x^{\mathrm{\prime }})-1$. Hence $x=(sz)x^{\mathrm{\prime }\mathrm{\prime }}$ is length-additive and $sz{\le }_{R}x$ with $\mathrm{\ell }(sz)=\mathrm{\ell }(z)+1$; the same argument using $y=z{y}^{\mathrm{\prime }}$ gives $sz{\le }_{R}y$. Then $sz\in E(x,y)$ has length larger than the maximal length $\mathrm{\ell }(z)$, a contradiction. Hence $\mathrm{\ell }(sz)=\mathrm{\ell }(z)-1$, that is $s{\le }_{R}z$.

The remaining assertions of clause (1): if $E(x,y)=\{1\}$ then $1$ is the only common lower bound, hence the greatest one, so $x\wedge y=1$; conversely if $x\wedge y=1$ then every $w\in E(x,y)$ satisfies $w{\le }_{R}x\wedge y=1$ with $1{\le }_{R}w$, so $w=1$ by antisymmetry, and $E(x,y)=\{1\}$. This completes clause (1).

Every $w\in E(x,y)$ satisfies $w{\le }_{R}z$ for every $z\in E(x,y)$ of maximal length; hence such a $z$ is the meet $x\wedge y$. We prove the first claim by induction on $\mathrm{\ell }(x)+\mathrm{\ell }(y)$; the case $w=1$ is the minimum property of $1$, so assume $w\mathrm{\ne }1$. Choose a reduced expression $w=sv$ with first letter $s$. Its suffix $v$ must be reduced, since otherwise replacing it by a shorter expression would shorten $w$; hence $\mathrm{\ell }(v)=\mathrm{\ell }(w)-1$; since $s^2=1$, $sw=v$, and therefore $s\in D_L(w)$ by [F7]. Since $w{\le }_{R}x$, the length identity gives $\mathrm{\ell }(x)=\mathrm{\ell }(w)+\mathrm{\ell }(w^{-1}x)$, so $\mathrm{\ell }(sx)\le \mathrm{\ell }(sw)+\mathrm{\ell }(w^{-1}x)=\mathrm{\ell }(x)-1$ by subadditivity. The $\pm 1$ length change in [F7] forces $\mathrm{\ell }(sx)=\mathrm{\ell }(x)-1$, hence $s\in D_L(x)$; symmetrically $s\in D_L(y)$. By step 1.2, $s{\le }_{R}z$. The length-additive factorization of $z$ by $s$ and $s^2=1$ give $z=s(sz)$ and $\mathrm{\ell }(sz)=\mathrm{\ell }(z)-1$, so $s\in D_L(z)$ by [F7]. Since $x=z\cdot (z^{-1}x)$ and $z=s(sz)$ are length-additive, $sx=(sz)(z^{-1}x)$ and $\mathrm{\ell }(sx)=\mathrm{\ell }(x)-1=\mathrm{\ell }(sz)+\mathrm{\ell }(z^{-1}x)$; hence $sz{\le }_{R}sx$ and, symmetrically, $sz{\le }_{R}sy$. The induction hypothesis applied to $(sx,sy)$, whose length sum is $\mathrm{\ell }(x)+\mathrm{\ell }(y)-2$, provides the meet $z^{\mathrm{\prime }}:=sx\wedge sy$, and $sz{\le }_R{z}^{\mathrm{\prime }}$ by its universal property. Because $s\in D_L(w)\cap D_L(x)$ and $w{\le }_{R}x$, [F10] gives $sw{\le }_{R}sx$; similarly $sw{\le }_{R}sy$, so the meet property gives $sw{\le }_R{z}^{\mathrm{\prime }}$. Next, $s{z}^{\mathrm{\prime }}{\le }_{R}x$ and $s{z}^{\mathrm{\prime }}{\le }_{R}y$: from $z^{\mathrm{\prime }}{\le }_{R}sx$ the inversion criterion gives $N(z^{\mathrm{\prime }-1})\subseteq N((sx{)}^{-1})=N(x^{-1}s)$. Since $s\in D_L(x)$, the descent dictionary gives $e_s\in N(x^{-1})$, and [F15] gives $\mathrm{\ell }(x^{-1}s)=\mathrm{\ell }((sx{)}^{-1})=\mathrm{\ell }(sx)=\mathrm{\ell }(x)-1<\mathrm{\ell }(x^{-1})$; thus the descent recursion gives $N(x^{-1}s)=s(N(x^{-1})\setminus \{e_s\})$. By [F7] and [F3], $\mathrm{\ell }(z^{\mathrm{\prime }-1}s)$ differs from $\mathrm{\ell }(z^{\mathrm{\prime }-1})$ by $1$, so one of the two recursions in [F6] gives $N(z^{\mathrm{\prime }-1}s)\subseteq \{e_s\}\cup sN(z^{\mathrm{\prime }-1})$. Applying $\rho (s)$ to $N(z^{\mathrm{\prime }-1})\subseteq s(N(x^{-1})\setminus \{e_s\})$ and using [F11] gives $sN(z^{\mathrm{\prime }-1})\subseteq N(x^{-1})\setminus \{e_s\}$, so $N((s{z}^{\mathrm{\prime }}{)}^{-1})=N(z^{\mathrm{\prime }-1}s)\subseteq \{e_s\}\cup (N(x^{-1})\setminus \{e_s\})=N(x^{-1})$ because $e_s\in N(x^{-1})$. The inversion criterion gives $s{z}^{\mathrm{\prime }}{\le }_{R}x$, and the same argument gives $s{z}^{\mathrm{\prime }}{\le }_{R}y$. Hence $s{z}^{\mathrm{\prime }}\in E(x,y)$ and $\mathrm{\ell }(s{z}^{\mathrm{\prime }})\le \mathrm{\ell }(z)$ by maximality. If $\mathrm{\ell }(s{z}^{\mathrm{\prime }})=\mathrm{\ell }(z^{\mathrm{\prime }})-1$, then $z^{\mathrm{\prime }}=s(s{z}^{\mathrm{\prime }})$ with additive length, so $s{\le }_R{z}^{\mathrm{\prime }}$; transitivity with $z^{\mathrm{\prime }}{\le }_{R}sx$ would give $s{\le }_{R}sx$. By $s^2=1$ and $\mathrm{\ell }(s)=1$, this means $\mathrm{\ell }(sx)=\mathrm{\ell }(s)+\mathrm{\ell }(x)=1+\mathrm{\ell }(x)$, contradicting $\mathrm{\ell }(sx)=\mathrm{\ell }(x)-1$. Thus $\mathrm{\ell }(s{z}^{\mathrm{\prime }})=\mathrm{\ell }(z^{\mathrm{\prime }})+1$ and $\mathrm{\ell }(z^{\mathrm{\prime }})=\mathrm{\ell }(s{z}^{\mathrm{\prime }})-1\le \mathrm{\ell }(z)-1=\mathrm{\ell }(sz)\le \mathrm{\ell }(z^{\mathrm{\prime }})$, the last inequality from $sz{\le }_R{z}^{\mathrm{\prime }}$. Hence $\mathrm{\ell }(sz)=\mathrm{\ell }(z^{\mathrm{\prime }})$ and the equal-length property in [F3] yields $sz=z^{\mathrm{\prime }}$. We now have $sw{\le }_R{z}^{\mathrm{\prime }}=sz$, and $s\in D_L(w)\cap D_L(z)$; [F10] in its reverse direction gives $w{\le }_{R}z$, completing the induction. Therefore every element of $E(x,y)$ lies below $z$, while $z\in E(x,y)$; so $z$ is the greatest lower bound $x\wedge y$, and in particular the meet exists and is an element of $E(x,y)$ of maximal length.

Meets of nonempty subsets: let $A\mathrm{\ne }\mathrm{\varnothing }$ and $x_0\in A$. We run the procedure of the statement and verify its invariants. If $u$ is a lower bound of $A$ and $u{\le }_R{x}_i$, and $x_{i+1}=x_i\wedge y_i$ with $y_i\in A$, then $u{\le }_R{x}_i$ and $u{\le }_R{y}_i$ (the latter because $u$ is a lower bound of $A$), so $u{\le }_R{x}_{i+1}$ by the universal property of the meet; the invariant "every lower bound of $A$ is below the current candidate" therefore persists from $x_0$, which satisfies it because $x_0\in A$. Each replacement gives $x_{i+1}=x_i\wedge y_i{\le }_R{x}_i$ and $x_{i+1}\mathrm{\ne }{x}_i$ (else $x_i{\le }_R{y}_i$, contrary to the choice of $y_i$), so $\mathrm{\ell }(x_{i+1})<\mathrm{\ell }(x_i)$ by the equal-length property of [F3]; as $\mathrm{\ell }$ takes values in $\mathbb{N}$ by [F4], the procedure stops after at most $\mathrm{\ell }(x_0)$ replacements. At a stopping stage $x_i{\le }_{R}y$ for all $y\in A$, so $x_i$ is a lower bound of $A$; and every lower bound $u$ of $A$ satisfies $u{\le }_R{x}_i$ by the invariant, so $x_i$ is the greatest lower bound $\bigwedge A$. At each nonstopping stage, failure of $x_i{\le }_{R}y$ for all $y\in A$ supplies a witness $y_i\in A$. The strictly decreasing natural lengths bound the recursion by $\mathrm{\ell }(x_0)$ updates, so it selects at most $\mathrm{\ell }(x_0)+1$ elements including $x_0$; this finite recursion uses no Axiom of Choice, and each meet $x_i\wedge y_i$ is uniquely determined.

Joins of bounded subsets: let $A\mathrm{\ne }\mathrm{\varnothing }$ be bounded above in ${\le }_R$, so that its set of upper bounds $U(A)$ is nonempty. By step 3.1 the meet $z:=\bigwedge U(A)$ exists. For every $a\in A$ and every $u\in U(A)$ one has $a{\le }_{R}u$, so each $a\in A$ is a lower bound of $U(A)$ and therefore $a{\le }_{R}z$; hence $z$ is an upper bound of $A$. If $u$ is any upper bound of $A$, then $u\in U(A)$ and $z{\le }_{R}u$ because $z$ is the greatest lower bound of $U(A)$. Therefore $z$ is the least upper bound $\bigvee A$.

The left-order statements follow by inversion: the map $w\mapsto w^{-1}$ is an order isomorphism $(W,{\le }_R)\to (W,{\le }_L)$, so it carries $E(x,y)$, $U(A)$ and every universal bound property for ${\le }_R$ into the corresponding objects for ${\le }_L$; explicitly, meets in ${\le }_L$ are the inverses of meets in ${\le }_R$ of the inverted sets. No Choice was used anywhere in this proof.