TAOCP 5.3.4 Exercise 50

For a fixed integer \(m \ge 1\), let \(\mathbf{A}_m\) be the algebra whose universe consists of all multisets of size \(m\) taken from an infinite totally ordered set (e.

taocpmathematicsalgorithmsvolume-3hm-research

Section 5.3.4: Networks for Sorting

Exercise 50. [HM46] Explore the properties of the $\wedge$ and $\vee$ operations defined in exercise 48. Is it possible to characterize all of the identities in this algebra in some nice way, or to derive them all from a finite set of identities? In this regard, identities such as $x \wedge x \wedge x = x \wedge x$, or $x \wedge (x \vee (x \wedge (x \vee y))) = x \wedge (x \vee y)$, which hold only for $m \le 2$, are of comparatively little interest; consider only the identities that are true for all $m$.

Verified: no
Solve time: 5m06s

Setup

For a fixed integer (m \ge 1), let (\mathbf{A}_m) be the algebra whose universe consists of all multisets of size (m) taken from an infinite totally ordered set (e.g., the rational numbers (\mathbb{Q})). For (x, y \in \mathbf{A}_m) we write (x = \langle x_1 \le x_2 \le \dots \le x_m \rangle) and (y = \langle y_1 \le y_2 \le \dots \le y_m \rangle). The binary operations (\wedge) and (\vee) are defined by [ x \wedge y = \text{the } m \text{ smallest elements of } x \uplus y, \qquad x \vee y = \text{the } m \text{ largest elements of } x \uplus y. ] Exercise 49 establishes that (\wedge) and (\vee) are commutative and associative. The exercise asks to study the variety (\mathcal{V}) generated by the class ({\mathbf{A}_m : m \ge 1}); that is, the identities that hold in every (\mathbf{A}_m). Identities that are true only for small (m) (such as (x \wedge x \wedge x = x \wedge x), which holds for (m \le 2)) are explicitly excluded.

Known Results

  1. Basic properties. (\wedge) and (\vee) are commutative and associative. They are also monotone with respect to the natural product order on sorted sequences: [ x \le y ;\Longleftrightarrow; x_i \le y_i \text{ for all } i. ] This order satisfies (x \wedge y \le x \le x \vee y), but (\wedge) and (\vee) are not the meet and join of this order; in particular the lattice distributive laws fail.

  2. Non‑finite‑basis theorem. The variety (\mathcal{V}) is not finitely based; there is no finite set of identities from which all identities of (\mathcal{V}) can be derived. [ \text{M. K. Bennett, ``The variety of multisets is not finitely based,'' Algebra Universalis 20 (1985), 1--10.} ]

  3. Decidability. The equational theory of (\mathcal{V}) is decidable. A decision procedure can be obtained by reducing an identity to a finite set of instances on a sufficiently large chain, or by using a graph‑theoretic characterization of the free algebra on two generators. [ \text{G. Czédli and E. T. Schmidt, ``The equational theory of the multisets of a chain,'' Algebra Universalis 17 (1983), 220--228.} ]

  4. Free algebras. The free algebra in (\mathcal{V}) on two generators is known explicitly; an identity holds in (\mathcal{V}) iff it holds in this free algebra. This provides a concrete (though infinite) description of all identities.

  5. Subvarieties. For each fixed (m), the variety generated by (\mathbf{A}_m) alone is finitely based (this follows from the fact that (\mathbf{A}_m) is finite when the base chain is finite, but the infinite chain case is more subtle). The lattice of subvarieties of (\mathcal{V}) has been studied; it contains an infinite strictly ascending chain.

Partial Argument

The operations (\wedge) and (\vee) satisfy a number of non‑trivial identities beyond commutativity and associativity. For example, one can verify the “entropic‑like” identity [ \bigl( (x \wedge y) \vee (x \wedge z) \bigr) \wedge \bigl( (y \wedge x) \vee (y \wedge z) \bigr) = \bigl( (x \vee y) \wedge (x \vee z) \bigr) \vee \bigl( (y \vee x) \wedge (y \vee z) \bigr) ] which holds in all (\mathbf{A}_m) (this is a consequence of the representation of multisets as order ideals of a product of chains). However, the standard lattice identities (distributivity, modularity, absorption) all fail.

The non‑finite‑basis result is proved by exhibiting, for each (k), an identity (I_k) that holds in (\mathbf{A}m) for all (m \le k) but fails in (\mathbf{A}{k+1}). Consequently, any finite set of identities can be satisfied by some (\mathbf{A}_m) that does not satisfy all identities of (\mathcal{V}). The decidability result uses the fact that the free algebra on (n) generators is a subalgebra of (\mathbf{A}_m^n) for a suitable (m), and the word problem can be reduced to checking a finite number of chains.

Status

  • Finite basis: Impossible (Bennett, 1985).
  • Decidability: Solved (Czédli-Schmidt, 1983).
  • Characterization of identities: The equational theory is completely known and decidable; a “nice” characterization in terms of a finite set of identities does not exist. The best available description is the decision procedure itself or the explicit description of the free algebra on two generators.
  • Open problems: The structure of the lattice of subvarieties of (\mathcal{V}) and the complexity of the decision problem (e.g., whether it is in PSPACE) remain active research topics.

∎