Problems of associativity: a simple proof for the lattice property of systems ordered by a semi-associative law

The following theorem is proved by \textit{H. Fredan} and \textit{D. Tamari} [ibid. 2, 215--242 (1967; Zbl 0158.01904)]: \(\left(T_{n},\rightarrow\right)\), the set of all binary bracketings (b.b.) built up from \(n+1\) factors by \(n\) pairs of parentheses, ordered by the so called semi-associative law, \((A(B C)) \to ((A B) C)\), is a lattice. The reviewed paper gives a considerably simpler proof. A b.b. is determined by its right brackets (r.b.), or dually, left brackets (l.b.). This essentially determines a bijective canonical map from \(T_{n}\) onto the family of general bracketings (g.b.) of \(n\) pairs of parentheses [\textit{D. Tamari}, Nieuw Arch. Wiskd., III. Ser. 10, 131--146 (1962; Zbl 0109.24502)]. Therefore, \(T_{n}\) can be faithfully represented by bracketing functions, \(i. e.\), maps \(E: J^{n} \rightarrow J^{n}\), \(i\mapsto i^{E}\), where \(J^{n}=\{1,2, \ldots, n\}\), satisfying (I) \(i \leq i^{E}\), (II) \(i \leq j \leq i^{E} \Rightarrow j^{E} \leq i^{E}\) (the basic bracket property). Denoting \(E_{i}=\left\{i, \ldots, i^{E}\right\}\), \(E\) becomes a family of intervals of natural numbers \(E=\left\{E_{1}, \ldots, E_{n}\right\}\). Define the intrinsic order of these families of sets; \(E \geq F\) if and only if \(E_{i} \geq F_{i}, \forall i \in J^{n}\), then \(\left(T_{n}, \geq\right)\) is a lattice (corollary 1 of proposition 1). The intrinsic order of \(T_{n}\) turns out to be the same as the order relation ``\(\rightarrow\); induced by the semi-associative law: the map \(\sigma_{1}: T_{n} \rightarrow T_{n}\), assigning \(E \mapsto \sigma_{1}(E)=E^{1}\) (\(E, E^{1} \in T_{n}\)), replaces \(E_{1}\) in \(E\) by the complement of its greatest confinal \(E_j\), \(j=\min \left\{x \mid x^{E}=i^{E}, x>i\right\}\), i.e., by \(E_{i}^{1}=\{i, \ldots, j-1\}\). Therefore, \(E \geq E^{i}\), more generally, \(E \rightarrow F\) (i.e., \(F=E^{i_{1} i_{2}, \ldots, i_{k}}, i_{1}, \ldots, i_{k} \in J^{n}\)) in \(\left(T_{n}, \rightarrow\right)\) implies \(E \geq F\) in \(\left(T_{n}, >\right)\). Conversely, \(E \gneqq F\) in \(\left(T_{n}, >\right)\) implies the existence of a greatest \(i\), \(i<n\), such that \(E_{1}\supsetneqq F_{1}\). One shows \(E^{1} \geq F\) and deduces \(E>F\) in \(\left(T_{n},>\right)\) implies \(E \rightarrow F\) in \(\left(T_{n}, \rightarrow\right)\). Therefore, \(\left(T_{n}, \rightarrow\right) \cong\left(T_{n},>\right)\); which implies \(\left(T_{n}, \rightarrow\right)\) is also a lattice.

Cites work

Cited in

(65)

This page was built for publication: Problems of associativity: a simple proof for the lattice property of systems ordered by a semi-associative law

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2556426)