The max-plus algebra of the natural numbers has no finite equational basis (Q1870591): Difference between revisions

Let \({\mathbf N} = (N, \vee , +, 0)\) denote the algebra of the natural numbers equipped with the usual sum operation \(+\), constant \(0\) and the operation \(\vee\) for the maximum of two numbers. In the paper, it is proven that the equational theory of the algebra \({\mathbf N}\) is not finitely based, while the varieties generated by the reducts \((N, +, 0)\) and \((N, \vee, 0)\) of \({\mathbf N}\) have very simple finite equational axiomatizations. Moreover, for any \(n\), the equations in at most \(n\) variables that hold in \({\mathbf N}\) do not form an equational basis. As a stepping stone in the proof of these facts, several results of independent interest are obtained. In particular, explicit descriptions of the free algebras in the variety generated by \({\mathbf N}\) are offered. Such descriptions are based upon a geometric characterization of the equations that hold in \({\mathbf N}\), which also yields that the equational theory of \({\mathbf N}\) is decidable in exponential time.