Basis (universal algebra)

In universal algebra, a basis is a structure inside of some (universal) algebras, which are called free algebras. It generates all algebra elements from its own elements by the algebra operations in an independent manner. It also represents the endomorphisms of an algebra by certain indexings of algebra elements, which can correspond to the usual matrices when the free algebra is a vector space.
Definitions.
A basis (or reference frame) of a (universal) algebra is a function formula_1 that takes some algebra elements as values formula_2 and satisfies either one of the following two equivalent conditions. Here, the set of all formula_2 is called the basis set, whereas several authors call it the "basis". The set formula_4 of its arguments formula_5 is called the dimension set. Any function, with all its arguments in the whole formula_4, that takes algebra elements as values (even outside the basis set) will be denoted by formula_7. Then, formula_1 will be an formula_7.
Outer condition.
This condition will define bases by the set formula_10 of the formula_4-ary elementary functions of the algebra, which are certain functions formula_12 that take every formula_7 as argument to get some algebra element as value formula_14 In fact, they consist of all the projections formula_15 with formula_5 in formula_17 which are the functions such that formula_18 for each formula_7, and of all functions that rise from them by repeated "multiple compositions" with operations of the algebra. 
(When an algebra operation has a single algebra element as argument, the value of such a composed function is the one that the operation takes from the value of a single previously computed formula_4-ary function as in composition. When it does not, such compositions require that many (or none for a nullary operation) formula_4-ary functions are evaluated before the algebra operation: one for each possible algebra element in that argument. In case formula_4 and the numbers of elements in the arguments, or “arity”, of the operations are finite, this is the finitary multiple composition .) 
Then, according to the "outer condition" a basis formula_1 has to "generate" the algebra (namely when formula_12 ranges over the whole formula_10, formula_26 gets every algebra element) and must be "independent" (namely whenever any two formula_4-ary elementary functions coincide at formula_1, they will do everywhere: formula_29 implies formula_30). This is the same as to require that there exists a "single" function formula_31 that takes every algebra element as argument to get an formula_4-ary elementary function as value and satisfies formula_33 for all formula_12 in formula_10.
Inner condition.
This other condition will define bases by the set "E" of the endomorphisms of the algebra, which are the homomorphisms from the algebra into itself, through its analytic representation formula_36 by a basis. The latter is a function that takes every endomorphism "e" as argument to get a function "m" as value: formula_37, where this "m" is the "sample" of the values of "e" at "b", namely formula_38 for all "i" in the dimension set.
Then, according to the "inner condition" "b" is a basis, when formula_36 is a bijection from "E" onto the set of all "m", namely for each "m" there is one and only one endomorphism "e" such that formula_40. This is the same as to require that there exists an extension function, namely a function formula_41 that takes every (sample) "m" as argument to extend it onto an endomorphism formula_42 such that formula_43.
The link between these two conditions is given by the identity formula_44, which holds for all "m" and all algebra elements "a". Several other conditions that characterize bases for universal algebras are omitted.
As the next example will show, present bases are a generalization of the bases of vector spaces. Then, the name "reference frame" can well replace "basis". Yet, contrary to the vector space case, a universal algebra might lack bases and, when it has them, their dimension sets might have different finite positive cardinalities.
Examples.
Vector space algebras.
In the universal algebra corresponding to a vector space with finite dimension the bases essentially are the ordered bases of this vector space. Yet, this will come after several details.
When the vector space is finite-dimensional, for instance formula_45 with formula_46, the functions formula_12 in the set "L" of the "outer condition" exactly are the ones that provide the spanning and linear independence properties with linear combinations formula_48 and present generator property becomes the spanning one. On the contrary, linear independence is a mere instance of present independence, which becomes equivalent to it in such vector spaces. (Also, several other generalizations of linear independence for universal algebras do not imply present independence.)
The functions "m" for the "inner condition" correspond to the square arrays of field elements (namely, usual vector-space square matrices) that serve to build the endomorphisms of vector spaces (namely, linear maps into themselves). Then, the "inner condition" requires a bijection property from endomorphisms also to arrays. In fact, each column of such an array represents a vector formula_49 as its "n"-tuple of coordinates with respect to the basis "b". For instance, when the vectors are "n"-tuples of numbers from the underlying field and "b" is the Kronecker basis, "m" is such an array "seen by columns", formula_36 is the sample of such a linear map at the reference vectors and formula_41 extends this sample to this map as below.
formula_52 
When the vector space is not finite-dimensional, further distinctions are needed. In fact, though the functions formula_12 formally have an infinity of vectors in every argument, the linear combinations they evaluate never require infinitely many addenda formula_54 and each formula_12 determines a finite subset "J" of formula_4 that contains all required "i". Then, every value formula_57 equals an formula_58, where formula_59 is the restriction of "m" to "J" and formula_60 is the "J"-ary elementary function corresponding to formula_12. When the formula_60 replace the formula_12, both the linear independence and spanning properties for infinite basis sets follow from present "outer condition" and conversely. 
Therefore, as far as vector spaces of a positive dimension are concerned, the only difference between present bases for universal algebras and the ordered bases of vector spaces is that here no order on formula_4 is required. Still it is allowed, in case it serves some purpose. 
When the space is zero-dimensional, its ordered basis is empty. Then, being the empty function, it is a present basis. Yet, since this space only contains the null vector and its only endomorphism is the identity, any function "b" from any set formula_4 (even a nonempty one) to this singleton space works as a present basis. This is not so strange from the point of view of universal algebra, where singleton algebras, which are called "trivial", enjoy a lot of other seemingly strange properties.
Word monoid.
Let formula_66 be an "alphabet", namely a (usually finite) set of objects called "letters". Let "W" denote the corresponding set of words or "strings", which will be denoted as in strings, namely either by writing their letters in sequence or by formula_67 in case of the empty word (formal language notation). Accordingly, the juxtaposition "formula_68" will denote the concatenation of two words "v" and "w", namely the word that begins with "v" and is followed by "w".
Concatenation is a binary operation on "W" that together with the empty word formula_67 defines a free monoid, the monoid of the words on formula_4, which is one of the simplest universal algebras. Then, the "inner condition" will immediately prove that one of its bases is the function "b" that makes a single-letter word formula_71 of each letter formula_72, formula_73.
(Depending on the set-theoretical implementation of sequences, "b" may not be an identity function, namely formula_5 may not be formula_72, rather an object like formula_76, namely a singleton function, or a pair like formula_77 or formula_78.) 
In fact, in the theory of D0L systems (Rozemberg & Salomaa 1980) such formula_40 are the tables of "productions", which such systems use to define the simultaneous substitutions of every formula_5 by a single word formula_81 in any word "u" in "W": if formula_82, then formula_83. Then, "b" satisfies the "inner condition", since the function formula_36 is the well-known bijection that identifies every word endomorphism with any such table. (The repeated applications of such an endomorphism starting from a given "seed" word are able to model many growth processes, where words and concatenation serve to build fairly heterogeneous structures as in L-system, not just "sequences".)