Basis (Universal Algebra)
Encyclopedia
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
.
is a function b that takes some algebra elements as values
and satisfies either one of the following two equivalent conditions. Here, the set of all 
is called basis set, whereas several authors call it the "basis". The set 
of its arguments i is called dimension set. Any function, with all its arguments in the whole 
, that takes algebra elements as values (even outside the basis set) will be denoted by m. Then, b will be an m.
-ary elementary functions of the algebra, which are certain functions 
that take every m as argument to get some algebra element as value 
. In fact, they consist of all the projections 
with i in 
, which are the functions such that 
for each m, 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
-ary function as in composition
. When it does not, such compositions require that many (or none for a nullary operation)
-ary functions are evaluated before the algebra operation: one for each possible algebra element in that argument. In case 
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 has to generate the algebra (namely when
ranges over the whole L, 
gets every algebra element) and must be independent (namely whenever any two 
-ary elementary functions coincide at b, they will do everywhere: 
implies 
). This is the same as to require that there exists a single function 
that takes every algebra element as argument to get an 
-ary elementary function as value and satisfies 
for all 
in L.
from the algebra into itself, through its analytic representation
by a basis. The latter is a function that takes every endomorphism e as argument to get a function m as value: 
, where this m is the "sample" of the values of e at b, namely 
for all i in the dimension set.
Then, according to the inner condition b is a basis, when
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 
. This is the same as to require that there exists an extension function, namely a function 
that takes every (sample) m as argument to extend it onto an endomorphism 
such that 
.
The link between these two conditions is given by the identity
, 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.
When the vector space is finite-dimensional, for instance
with 
, the functions 
in the set L of the outer condition exactly are the ones that provide the spanning and linear independence properties
with linear combinations
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 numbers (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
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,
is the sample of such a linear map at the reference vectors and 
extends this sample to this map as below.
When the vector space is not finite-dimensional, further distinctions are needed. In fact, though the functions
formally have an infinity of vectors in every argument, the linear combinations they evaluate never require infinitely many addenda 
and each 
determines a finite subset J of 
that contains all required i. Then, every value 
equals an 
, where 
is the restriction of m to J and 
is the J-ary elementary function corresponding to 
. When the 
replace the 
, 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
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
(even a nonempty one) to this singleton space work 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 seeming strange properties.
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
in case of the empty word ( Formal Language
notation). Accordingly, the juxtaposition
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
defines a free monoid, the monoid of the words on 
, 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 
of each letter 
, 
.
(Depending on the set-theoretical implementation of sequences, b may not be an identity function, namely
may not be 
, rather an object like 
, namely a singleton function, or a pair like 
or 
.)
In fact, in the theory of D0L systems (Rozemberg & Salomaa 1980) such
are the tables of "productions"
, which such systems use to define the simultaneous substitutions of every
by a single word 
in any word u in W: if 
, then 
. Then, b satisfies the inner condition, since the function 
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".)
Universal algebra
Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....
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
Vector space
A vector space is a mathematical structure formed by a collection of vectors: objects that may be added together and multiplied by numbers, called scalars in this context. Scalars are often taken to be real numbers, but one may also consider vector spaces with scalar multiplication by complex...
.
Definitions
The basis (or reference frame) of a (universal) algebraUniversal algebra
Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....
is a function b that takes some algebra elements as values
and satisfies either one of the following two equivalent conditions. Here, the set of all is called basis set, whereas several authors call it the "basis". The set of its arguments i is called dimension set. Any function, with all its arguments in the whole , that takes algebra elements as values (even outside the basis set) will be denoted by m. Then, b will be an m.Outer condition
This condition will define bases by the set L of the-ary elementary functions of the algebra, which are certain functions that take every m as argument to get some algebra element as value . In fact, they consist of all the projections with i in , which are the functions such that for each m, 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
-ary function as in compositionFunction composition
In mathematics, function composition is the application of one function to the results of another. For instance, the functions and can be composed by computing the output of g when it has an argument of f instead of x...
. When it does not, such compositions require that many (or none for a nullary operation)
-ary functions are evaluated before the algebra operation: one for each possible algebra element in that argument. In case and the numbers of elements in the arguments, or “arity”, of the operations are finite, this is the finitary multiple compositionClone (algebra)
In universal algebra, a clone is a set C of operations on a set A such that*C contains all the projections , defined by ,*C is closed under composition : if f, g1, …, gm are members of C such that f is m-ary, and gj is n-ary for every j, then the n-ary operation is in C.Given an algebra...
.)
Then, according to the outer condition a basis has to generate the algebra (namely when
ranges over the whole L, gets every algebra element) and must be independent (namely whenever any two -ary elementary functions coincide at b, they will do everywhere: implies ). This is the same as to require that there exists a single function that takes every algebra element as argument to get an -ary elementary function as value and satisfies for all in L.Inner condition
This other condition will define bases by the set E of the endomorphisms of the algebra, which are the homomorphismsUniversal algebra
Universal algebra is the field of mathematics that studies algebraic structures themselves, not examples of algebraic structures....
from the algebra into itself, through its analytic representation
by a basis. The latter is a function that takes every endomorphism e as argument to get a function m as value: , where this m is the "sample" of the values of e at b, namely for all i in the dimension set.Then, according to the inner condition b is a basis, when
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 . This is the same as to require that there exists an extension function, namely a function that takes every (sample) m as argument to extend it onto an endomorphism such that . The link between these two conditions is given by the identity
, 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
Basis (linear algebra)
In linear algebra, a basis is a set of linearly independent vectors that, in a linear combination, can represent every vector in a given vector space or free module, or, more simply put, which define a "coordinate system"...
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.
Vector space algebras
In the universal algebra corresponding to a vector space with positive 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
with , the functions in the set L of the outer condition exactly are the ones that provide the spanning and linear independence propertiesBasis (linear algebra)
In linear algebra, a basis is a set of linearly independent vectors that, in a linear combination, can represent every vector in a given vector space or free module, or, more simply put, which define a "coordinate system"...
with linear combinations
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 numbers (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
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 basisStandard basis
In mathematics, the standard basis for a Euclidean space consists of one unit vector pointing in the direction of each axis of the Cartesian coordinate system...
, m is such an array seen by columns,
is the sample of such a linear map at the reference vectors and extends this sample to this map as below.When the vector space is not finite-dimensional, further distinctions are needed. In fact, though the functions
formally have an infinity of vectors in every argument, the linear combinations they evaluate never require infinitely many addenda and each determines a finite subset J of that contains all required i. Then, every value equals an , where is the restriction of m to J and is the J-ary elementary function corresponding to . When the replace the , 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
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
Empty function
In mathematics, an empty function is a function whose domain is the empty set. For each set A, there is exactly one such empty functionf_A: \varnothing \rightarrow A....
, 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
(even a nonempty one) to this singleton space work 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 seeming strange properties.Word monoid
Let 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 stringsString (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
, namely either by writing their letters in sequence or by
in case of the empty word ( Formal LanguageFormal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
notation). Accordingly, the juxtaposition
will denote the concatenationConcatenation
In computer programming, string concatenation is the operation of joining two character strings end-to-end. For example, the strings "snow" and "ball" may be concatenated to give "snowball"...
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
defines a free monoid, the monoid of the words on , 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 of each letter , .(Depending on the set-theoretical implementation of sequences, b may not be an identity function, namely
may not be , rather an object like , namely a singleton function, or a pair like or .)In fact, in the theory of D0L systems (Rozemberg & Salomaa 1980) such
are the tables of "productions"L-system
An L-system or Lindenmayer system is a parallel rewriting system, namely a variant of a formal grammar, most famously used to model the growth processes of plant development, but also able to model the morphology of a variety of organisms...
, which such systems use to define the simultaneous substitutions of every
by a single word in any word u in W: if , then . Then, b satisfies the inner condition, since the function 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-systemL-system
An L-system or Lindenmayer system is a parallel rewriting system, namely a variant of a formal grammar, most famously used to model the growth processes of plant development, but also able to model the morphology of a variety of organisms...
, not just "sequences".)