Bases for algebras over a monad.

One of the fundamental notions of linear algebra is the concept of a basis for a vector space. In the category theoretic formulation of universal algebra, vector spaces are the Eilenberg-Moore algebras over the free vector space monad on the category of sets. In this paper we show that the notion of a basis can be extended to algebras of arbitrary monads on arbitrary categories. On the one hand, we establish purely algebraic results, for instance about the existence and uniqueness of bases and the representation of algebra morphisms. On the other hand, we use the general notion of a basis in the context of coalgebraic systems and show that a basis for the underlying algebra of a bialgebra gives rise to an equivalent free bialgebra. As a result, we are, for instance, able to recover known constructions from automata theory, namely the so-called canonical residual finite state automaton. Finally, we instantiate the framework to a variety of example monads, including the powerset, downset, distribution, and neighbourhood monad.