Combinatorial and Exponential Algebras

Abstract

This thesis explores abstract algebraic problems relating to the equational properties of familiar operations on N such as exponentiation, factorial and binomial coefficients. Tarski asked whether the usual High School index laws are logically complete for all equational properties for exponentiation, while McNulty and Shallon asked for a similar theme of exploration around combinatorial operations. The combined family of these operations are the main theme of the thesis. We characterise all quotients of N with respect to these operations, finding a lattice-ordered monoid structure to the possible cycle sizes in the case of fixed base exponentiation. We then turn to questions of decidability and finite axiomatisability. The decidability of logical entailment for the equational theory of combinatorial operations is established by way of the finite model property, then a result of Wilkie is adapted to provide a new proof of the decidability of the equational theory of exponentiation. This is used to complete the classification of which subsignatures of {+, ·, ↑, 1} lead N to have a finitely axiomatisable equational theory. Some basic exploration of combinatorial axioms and their consequences is given, before we consider the question of whether a finite algebra in the variety of N can exist without a finite basis of identities. Examples are given of finite algebras satisfying all true laws of N that are without a finite identity basis. As a final result it is shown that all idempotent HSI-algebras lie within the variety generated by N. This is used to show that the variety generated by N contains a continuum of subvarieties, and contains all 3-element HSI-algebras.