Finite Lattice Projections and Coxeter Chain Labels

Assume $x{\equiv }_{\theta }y$. Apply [F1] to the pairs $(x{\equiv }_{\theta }y,y{\equiv }_{\theta }y)$, the second entry being licensed by reflexivity in [F3]: this gives $x\wedge y{\equiv }_{\theta }y\wedge y$ and $x\vee y{\equiv }_{\theta }y\vee y$. By [F2] with antisymmetry, $y\wedge y=y=y\vee y$, so $x\wedge y{\equiv }_{\theta }y$ and $x\vee y{\equiv }_{\theta }y$.

$C$ is a subset of the finite set $L$, so $C$ is finite with $k:=\mathrm{\mid }C\mathrm{\mid }\le \mathrm{\mid }L\mathrm{\mid }$ by [F4]; since $x\in C$ by [F3], $C\mathrm{\ne }\mathrm{\varnothing }$, hence $k\ge 1$ and there is a bijection $\mathrm{\ell }:k\to C$. Put $z_i:=\mathrm{\ell }(i)$ for $i\in k$, so that $C=\{z_0,\dots ,z_{k-1}\}$. The bijection $\mathrm{\ell }$ is a single witness of an existence statement in the definition of $\mathrm{\mid }C\mathrm{\mid }$; no choice function on a family of sets is used.

Assume $x{\equiv }_{\theta }{x}^{\mathrm{\prime }}$ and $y{\equiv }_{\theta }{y}^{\mathrm{\prime }}$. By [F1], $x\vee y{\equiv }_{\theta }{x}^{\mathrm{\prime }}\vee y^{\mathrm{\prime }}$ and $x\wedge y{\equiv }_{\theta }{x}^{\mathrm{\prime }}\wedge y^{\mathrm{\prime }}$, so $[x\vee y{]}_{\theta }=[x^{\mathrm{\prime }}\vee y^{\mathrm{\prime }}{]}_{\theta }$ and $[x\wedge y{]}_{\theta }=[x^{\mathrm{\prime }}\wedge y^{\mathrm{\prime }}{]}_{\theta }$ by [F3]. Hence the proposed operations $[x{]}_{\theta }\vee [y{]}_{\theta }:=[x\vee y{]}_{\theta }$ and $[x{]}_{\theta }\wedge [y{]}_{\theta }:=[x\wedge y{]}_{\theta }$ do not depend on the chosen representatives, and the class of $x$, hence the proposed pair of endpoints of its class, depends only on $[x{]}_{\theta }$.

Let $z_1,\dots ,z_k$ be a listing of a nonempty finite subfamily of $C$ and define $m_1:=z_1$, $m_j:=m_{j-1}\wedge z_j$ for $2\le j\le k$. By induction on $j$ each $m_j$ lies in $C$: $m_1=z_1\in C$, and if $m_{j-1}\in C$ then $m_{j-1}{\equiv }_{\theta }{z}_j$ because any two members of a class are equivalent by [F3], so step 1.1 gives $m_j=m_{j-1}\wedge z_j{\equiv }_{\theta }{z}_j\in C$. The same induction with $\vee$ in place of $\wedge$ shows that the left-nested iterated join of $z_1,\dots ,z_k$ lies in $C$. The left-nested iterated meet $m_k$ is the meet of the subfamily: it is a common lower bound by [F2], and every common lower bound $w$ satisfies $w\le m_j$ for all $j\le k$ by induction, since $w\le m_{j-1}$ and $w\le z_j$ give $w\le m_{j-1}\wedge z_j=m_j$ by [F2]; dually the iterated join is the join of the subfamily. Hence each class is closed under the meet and the join of any nonempty finite subfamily of its members.

With the well-defined operations of step 1.3, the classes satisfy the lattice identities by transport along representatives: $[x]\wedge [x]=[x\wedge x]=[x]$ and $[x]\vee [x]=[x]$; commutativity $[x]\wedge [y]=[y]\wedge [x]$ and $[x]\vee [y]=[y]\vee [x]$; associativity, because $(x\wedge y)\wedge z$ and $x\wedge (y\wedge z)$ are both the greatest lower bound of $\{x,y,z\}$ — each is a common lower bound, and every common lower bound lies below both by [F2] — hence they are equal by antisymmetry, and dually for $\vee$; and absorption $[x]\wedge ([x]\vee [y])=[x\wedge (x\vee y)]=[x]$, since $x$ is the greatest lower bound of $\{x,x\vee y\}$ by [F2], together with the dual absorption. The projection $x\mapsto [x{]}_{\theta }$ preserves these operations by construction.

For classes $A,B$ define $A\le B$ to mean $A\vee B=B$. The identities of step 2.2 make this a partial order: idempotence gives $A\le A$; if $A\vee B=B$ and $B\vee A=A$, commutativity gives $A=B$; and if $A\vee B=B$ and $B\vee C=C$, then $A\vee C=A\vee (B\vee C)=(A\vee B)\vee C=B\vee C=C$. Moreover $A\le B$ if and only if $A\wedge B=A$: the forward direction is $A\wedge B=A\wedge (A\vee B)=A$ by absorption, and the reverse is $A\vee B=(A\wedge B)\vee B=B$ by commutativity and absorption.

Apply step 2.1 to the listing $z_0,\dots ,z_{k-1}$ of the nonempty finite class $C$ from step 1.2. Its iterated meet $m$ lies in $C$ and is a common lower bound of all its members, so it is a least member of $C$; its iterated join $b$ lies in $C$ and is a common upper bound, so it is a greatest member. Both are unique by [F5], independently of the chosen listing. Define ${\pi }_{\downarrow }(x):=m$ and ${\pi }_{\uparrow }(x):=b$.

The operations are the bounds for the order of step 3.1. Indeed $A\le A\vee B$ since $A\vee (A\vee B)=A\vee B$, and likewise $B\le A\vee B$. If $A\le C$ and $B\le C$, then $(A\vee B)\vee C=A\vee (B\vee C)=A\vee C=C$, so $A\vee B\le C$. Dually $(A\wedge B)\wedge A=A\wedge B$ and $(A\wedge B)\wedge B=A\wedge B$ show $A\wedge B\le A,B$; if $C\le A,B$, then $C\wedge (A\wedge B)=(C\wedge A)\wedge B=C\wedge B=C$, so $C\le A\wedge B$. Thus the classes form the lattice $L\mathrm{/}\theta$ in the order-theoretic sense of [F2].

By the quotient order constructed in step 3.1, $[x{]}_{\theta }\le [y{]}_{\theta }$ if and only if $[x{]}_{\theta }\vee [y{]}_{\theta }=[y{]}_{\theta }$. The operation of step 1.3 identifies the latter equality with $[x\vee y{]}_{\theta }=[y{]}_{\theta }$, which holds if and only if $x\vee y{\equiv }_{\theta }y$ by [F3].

Let $z\in L$. If $z\in C$ then ${\pi }_{\downarrow }(x)\le z\le {\pi }_{\uparrow }(x)$, since these are the least and the greatest member of $C$. Conversely assume ${\pi }_{\downarrow }(x)\le z\le {\pi }_{\uparrow }(x)$ and put $a:={\pi }_{\downarrow }(x)$, $b:={\pi }_{\uparrow }(x)$; both lie in $C$, so $a{\equiv }_{\theta }b$ by [F3]. Apply [F1] to the pairs $a{\equiv }_{\theta }b$ and $z{\equiv }_{\theta }z$: $a\wedge z{\equiv }_{\theta }b\wedge z$. Since $a\le z$ we have $a\wedge z=a$ by [F2], and since $z\le b$ we have $b\wedge z=z$ by [F2]; hence $a{\equiv }_{\theta }z$, so $z\in C$ by [F3]. Therefore $[x{]}_{\theta }=\{z\in L:{\pi }_{\downarrow }(x)\le z\le {\pi }_{\uparrow }(x)\}$, the asserted interval identity.

Monotonicity of the upper endpoint map. Assume $x\le y$. By [F3], ${\pi }_{\uparrow }(x){\equiv }_{\theta }x$ and ${\pi }_{\uparrow }(y){\equiv }_{\theta }y$, so [F1] gives ${\pi }_{\uparrow }(x)\vee {\pi }_{\uparrow }(y){\equiv }_{\theta }x\vee y=y{\equiv }_{\theta }{\pi }_{\uparrow }(y)$; thus ${\pi }_{\uparrow }(x)\vee {\pi }_{\uparrow }(y)$ lies in the class of $y$, whose greatest member is ${\pi }_{\uparrow }(y)$, so ${\pi }_{\uparrow }(x)\vee {\pi }_{\uparrow }(y)\le {\pi }_{\uparrow }(y)$. With ${\pi }_{\uparrow }(y)\le {\pi }_{\uparrow }(x)\vee {\pi }_{\uparrow }(y)$ from [F2], antisymmetry gives ${\pi }_{\uparrow }(x)\vee {\pi }_{\uparrow }(y)={\pi }_{\uparrow }(y)$, and then ${\pi }_{\uparrow }(x)\le {\pi }_{\uparrow }(x)\vee {\pi }_{\uparrow }(y)={\pi }_{\uparrow }(y)$ by [F2].

Monotonicity of the lower endpoint map. Assume $x\le y$. By [F3], ${\pi }_{\downarrow }(x){\equiv }_{\theta }x$ and ${\pi }_{\downarrow }(y){\equiv }_{\theta }y$, so [F1] gives ${\pi }_{\downarrow }(x)\wedge {\pi }_{\downarrow }(y){\equiv }_{\theta }x\wedge y=x{\equiv }_{\theta }{\pi }_{\downarrow }(x)$; thus ${\pi }_{\downarrow }(x)\wedge {\pi }_{\downarrow }(y)$ lies in the class of $x$, whose least member is ${\pi }_{\downarrow }(x)$, so ${\pi }_{\downarrow }(x)\le {\pi }_{\downarrow }(x)\wedge {\pi }_{\downarrow }(y)$. With ${\pi }_{\downarrow }(x)\wedge {\pi }_{\downarrow }(y)\le {\pi }_{\downarrow }(x)$ from [F2], antisymmetry gives equality, and then ${\pi }_{\downarrow }(x)={\pi }_{\downarrow }(x)\wedge {\pi }_{\downarrow }(y)\le {\pi }_{\downarrow }(y)$ by [F2].

Clause (i) is steps 1.1 and 2.1; clause (ii) is steps 1.2, 3.2 and 4.3, where finiteness enters only through the listing $z_0,\dots ,z_{k-1}$ of the finite class and the iterated meet is formed along that listing; clause (iii) is steps 1.3, 2.2, 3.1, 4.1 and 4.2; clause (iv) is steps 4.4 and 4.5. No choice principle is used: the listing is a bijection with a natural number, its existence is a single existential witness, and no family of nonempty sets is selected from.

Rank preliminaries. If $u<u^{\mathrm{\prime }}$ in $P$, start with the chain $u<u^{\mathrm{\prime }}$ and insert an intermediate vertex whenever two consecutive vertices are not covers. Each insertion adds a new vertex of the finite interval $[u,u^{\mathrm{\prime }}]$, so the process stops at a saturated chain. Along it the rank increases by exactly one at each step by [F1], giving $\rho (u^{\mathrm{\prime }})=\rho (u)+s>\rho (u)$, where $s\ge 1$ is its number of steps. Consequently, for a strict chain $w=y_0>y_1>\cdots >y_t=v$ with $k:=\rho (v,w)$, the interior rank shifts $\rho (y_i)-\rho (v)$ are distinct members of $\{1,\dots ,k-1\}$. Their set has exactly $t-1$ elements, and $t\le k$.

Chain-sum identity. For $v<w$ put $c_t(v,w):=\mathrm{\#}\{$strict chains $w=y_0>y_1>\cdots >y_t=v\}$ and $A(v,w):={\sum }_{t=1}^{\mathrm{\mid }[v,w]\mathrm{\mid }-1}(-1{)}^t{c}_t(v,w)$; the sum includes every strict chain, since one with $t$ steps has $t+1$ distinct vertices of $[v,w]$ by [F9]. We prove $A(v,w)=\mu (v,w)$ by strong induction on $\mathrm{\mid }[v,w]\mathrm{\mid }$. The direct chain $w>v$ contributes $-1$. Every other chain has a unique first vertex $\zeta$ below $w$, with $v<\zeta <w$, and consists of the first step $w>\zeta$ followed by a strict chain from $\zeta$ to $v$. Thus $A(v,w)=-1-{\sum }_{v<\zeta <w}A(v,\zeta )$. Each $[v,\zeta ]$ is a proper subset of $[v,w]$, hence has smaller cardinality by [F9]; the induction hypothesis and [F6] give $A(v,w)=-1-{\sum }_{v<\zeta <w}\mu (v,\zeta )=-{\sum }_{v\le z<w}\mu (v,z)=\mu (v,w)$. When no intermediate vertex exists, the intermediate sum is empty and this is also the base case.

Setup of (i). Let $m^{\mathrm{\prime }},m$ be maximal chains of $[x,y]$ with $\lambda (m^{\mathrm{\prime }})\prec \lambda (m)$. Since $m_0=m_0^{\mathrm{\prime }}=y$ and $m_n=m_n^{\mathrm{\prime }}=x$, the index $d:=\max \{i:m_j=m_j^{\mathrm{\prime }}$ for all $j\le i\}$ and $g:=\min \{i>d:m_i=m_i^{\mathrm{\prime }}\}$ are defined, and $g\ge d+2$ because $m_{d+1}\mathrm{\ne }{m}_{d+1}^{\mathrm{\prime }}$. Each step of a maximal chain is a cover by [F2], so $\rho (m_i)=\rho (y)-i=\rho (m_i^{\mathrm{\prime }})$; hence a common vertex of the two chains is some $m_i=m_i^{\mathrm{\prime }}$, and $m_i\mathrm{\ne }{m}_i^{\mathrm{\prime }}$ for $d<i<g$ while $m_i=m_i^{\mathrm{\prime }}$ for $i\le d$ and $i=g$, so $m^{\mathrm{\prime }}\cap m=\{m_i:m_i=m_i^{\mathrm{\prime }}\}\subseteq \{m_i:i\le d\text{ or }i\ge g\}$. The subchains $m_d⋗\cdots ⋗m_g$ and $m_d^{\mathrm{\prime }}⋗\cdots ⋗m_g^{\mathrm{\prime }}$ are maximal chains of the rooted interval $([m_g,m_d],c)$ with $c=m_0⋗\cdots ⋗m_d$, and by [F2] their words there are the windows $\omega :=({\lambda }_{d+1}(m),\dots ,{\lambda }_g(m))$ and ${\omega }^{\mathrm{\prime }}:=({\lambda }_{d+1}(m^{\mathrm{\prime }}),\dots ,{\lambda }_g(m^{\mathrm{\prime }}))$. The window $\omega$ is not increasing: suppose it were; then the window subchain of $m$ is an increasing maximal chain of the rooted interval, hence the unique increasing one and lexicographically first by [F3], so $\omega ⪯{\omega }^{\mathrm{\prime }}$. If $\omega \prec {\omega }^{\mathrm{\prime }}$, then, the two full words agreeing in positions $1,\dots ,d$, their first difference lies in $\{d+1,\dots ,g\}$ and has ${\lambda }_i(m)<{\lambda }_i(m^{\mathrm{\prime }})$, so $\lambda (m)\prec \lambda (m^{\mathrm{\prime }})$, contradicting $\lambda (m^{\mathrm{\prime }})\prec \lambda (m)$; while if ${\omega }^{\mathrm{\prime }}=\omega$, then the window subchain of $m^{\mathrm{\prime }}$ is a maximal chain of the same rooted interval, distinct from that of $m$ because $m_{d+1}\mathrm{\ne }{m}_{d+1}^{\mathrm{\prime }}$, whose word $\omega$ is increasing, contradicting the uniqueness in (L). Therefore $\omega$ has an index $j\in \{1,\dots ,g-d-1\}$ with ${\omega }_j\ge {\omega }_{j+1}$, and ${\omega }_j\mathrm{\ne }{\omega }_{j+1}$ by (N) applied to the window chain, so with $e:=d+j\in \{d+1,\dots ,g-1\}$ we have ${\lambda }_e(m)>{\lambda }_{e+1}(m)$.

Replacement chain of (i). Put $c^{\mathrm{\prime }}:=m_0⋗\cdots ⋗m_{e-1}$. The segment $m_{e-1}⋗m_e⋗m_{e+1}$ is a maximal chain of the rooted interval $([m_{e+1},m_{e-1}],c^{\mathrm{\prime }})$, and by [F2] its word there is $({\lambda }_e(m),{\lambda }_{e+1}(m))$, which is falling by step 1.3, hence not increasing. By (L) of [F3] this rooted interval has exactly one increasing maximal chain; it is not the segment, so it has the form $m_{e-1}⋗y^{\mathrm{\prime }}⋗m_{e+1}$ with $m_{e+1}<y^{\mathrm{\prime }}<m_{e-1}$ and $y^{\mathrm{\prime }}\mathrm{\ne }{m}_e$, and its word $(a,b)$ satisfies $a<b$ and $(a,b)\prec ({\lambda }_e(m),{\lambda }_{e+1}(m))$ because it is lexicographically first. Define $k:=m_0⋗\cdots ⋗m_{e-1}⋗y^{\mathrm{\prime }}⋗m_{e+1}⋗\cdots ⋗m_n$.

Setup of (ii). Fix a rooted interval $([v,w],c)$ of $[x,y]$ and put $k:=\rho (v,w)$; we treat $k\ge 1$ and return to $k=0$ below. For a subset $S$ of $\{1,\dots ,k-1\}$ write $k-S:=\{k-s:s\in S\}$. For $T\subseteq \{1,\dots ,k-1\}$ let $f(T)$ be the number of maximal chains $m$ of $[v,w]$ (maximal in the poset $[v,w]$, carrying the labeling induced by the root chain $c$ as in [F2]) with $D(m)\subseteq T$, and for $S\subseteq \{1,\dots ,k-1\}$ let $\alpha (S)$ be the number of strict chains $w=y_0>y_1>\cdots >y_t=v$ with $t\ge 1$ whose rank set $\{\rho (y_i)-\rho (v):1\le i\le t-1\}$ equals $S$. Both are finite counts by [F9], and by step 1.1 the rank set of each such chain is a subset of $\{1,\dots ,k-1\}$.

Refinement construction. Given a strict chain $w=y_0>y_1>\cdots >y_t=v$ with rank set $S$, construct a maximal chain $m$ of $[v,w]$ top-down: starting from the top segment $[y_1,y_0]$ and continuing downwards, replace the segment $[y_i,y_{i-1}]$ by the unique increasing maximal chain of the rooted interval $([y_i,y_{i-1}],c_i)$, where $c_i$ is the original root $c$ extended by the part already constructed from $w$ down to $y_{i-1}$, so it ends at the upper endpoint $y_{i-1}$ (and $c_1=c$). Each replacement exists and is unique by (L) of [F3], and the resulting chain is a maximal chain of $[v,w]$. Inside each segment the word is increasing, so a descent of $\lambda (m)$ can occur only at a junction $y_i$, $1\le i\le t-1$, whose word position is $k-(\rho (y_i)-\rho (v))\in k-S$; hence $D(m)\subseteq k-S$.

Verification of the replacement. By [F2] the chain $k$ of step 2.1 is a maximal chain of $[x,y]$: it has length $n$, and each of its steps is a cover of $P$. Its word agrees with $\lambda (m)$ in positions $1,\dots ,e-1$ because $k$ and $m$ share the chain $m_0⋗\cdots ⋗m_{e-1}$ and the covers among these vertices, while at positions $e$ and $e+1$ the entries are $(a,b)$ and $({\lambda }_e(m),{\lambda }_{e+1}(m))$ with $(a,b)\prec ({\lambda }_e(m),{\lambda }_{e+1}(m))$; hence $\lambda (k)\prec \lambda (m)$. Moreover $k\cap m=m\setminus \{m_e\}$: the only vertex of $m$ strictly between $m_{e+1}$ and $m_{e-1}$ is $m_e$ and $y^{\mathrm{\prime }}\mathrm{\ne }{m}_e$, while every other vertex of $m$ lies outside that open interval, so $\mathrm{\mid }k\cap m\mathrm{\mid }=\mathrm{\mid }m\mathrm{\mid }-1$; and since $d<e<g$, step 1.3 gives $m^{\mathrm{\prime }}\cap m\subseteq \{m_i:i\le d\text{ or }i\ge g\}\subseteq m\setminus \{m_e\}=k\cap m$.

Truncation construction and the count. Conversely, given a maximal chain $m$ of $[v,w]$ with $D(m)\subseteq k-S$, keep the elements $m_j$ with $k-j\in S$; these are exactly $\mathrm{\mid }S\mathrm{\mid }$ indices in $\{1,\dots ,k-1\}$, and together with the endpoints $w=m_0$ and $v=m_k$ they form a strict chain of $\mathrm{\mid }S\mathrm{\mid }+1$ steps whose rank set is $S$. Between two consecutive kept elements there is no descent of $D(m)$: a junction $m_i$ strictly between two consecutive kept elements has $k-i\mathrm{\notin }S$, hence $i\mathrm{\notin }k-S$, and $D(m)\subseteq k-S$ gives $i\mathrm{\notin }D(m)$; so the word of each segment is weakly increasing, hence strictly increasing by (N), hence the segment is the unique increasing chain of its rooted interval by (L), so refining the kept chain returns $m$. Thus the constructions of step 3.1 and of this step are mutually inverse bijections, and $\alpha (S)=f(k-S)$ for every $S\subseteq \{1,\dots ,k-1\}$.

Facets and the open interval. Interpreting the maximal chains as facets of the order complex by [F5], step 3.2 says that for facets $C_{m^{\mathrm{\prime }}}$ preceding $C_m$ in the lexicographic order of label words there is a facet $C_k$ with $C_{m^{\mathrm{\prime }}}\cap C_m\subseteq C_k\cap C_m$ and $\mathrm{\mid }{C}_k\cap C_m\mathrm{\mid }=\mathrm{\mid }{C}_m\mathrm{\mid }-1$, and $\lambda (k)\prec \lambda (m)$ so that $C_k$ precedes $C_m$; this is the pairwise facet criterion of the statement. Indeed, every face of $C_m$ shared with an earlier facet lies in an earlier intersection obtained by deleting one vertex from $C_m$. Distinct facets have the same cardinality by [F2], so no earlier intersection is larger; hence the intersection of the simplex on $C_m$ with the union of earlier facet simplices is pure of codimension one, which is the shelling condition. A chain of the open interval $(x,y)$ is contained in no larger chain of $(x,y)$ precisely when, after adjoining $x$ and $y$, it becomes a maximal chain of $[x,y]$: if it could be enlarged inside $(x,y)$, so could the enlarged chain in $[x,y]$, and conversely an enlargement in $[x,y]$ of a chain already containing $x$ and $y$ lies in $(x,y)$. Hence the facets of $\mathrm{\Delta }((x,y))$ are the sets $m\setminus \{x,y\}$ for maximal chains $m$ of $[x,y]$, and since $x,y\in C_k\cap C_m$, deleting $x,y$ from all facets preserves $C_{m^{\mathrm{\prime }}}\cap C_m\subseteq C_k\cap C_m$ and gives $\mathrm{\mid }(C_k\cap C_m)\setminus \{x,y\}\mathrm{\mid }=\mathrm{\mid }{C}_m\setminus \{x,y\}\mathrm{\mid }-1$. For $n=0$ or $n=1$ there is only one maximal chain and one open-interval facet, the empty face, so the shelling condition is vacuous.