In mathematics, the idea of a free object is one of the basic concepts of abstract algebra. Informally, a free object over a set A can be thought of as being a "generic" algebraic structure over A: the only equations that hold between elements of the free object are those that follow from the defining axioms of the algebraic structure. Examples include free groups, tensor algebras, or free lattices.
The concept is a part of universal algebra, in the sense that it relates to all types of algebraic structure (with finitary operations). It also has a formulation in terms of category theory, although this is in yet more abstract terms.
Free objects are the direct generalization to categories of the notion of basis in a vector space. A linear function between vector spaces is entirely determined by its values on a basis of the vector space The following definition translates this to any category.
A concrete category is a category that is equipped with a faithful functor to Set, the category of sets. Let be a concrete category with a faithful functor . Let be a set (that is, an object in Set), which will be the basis of the free object to be defined. A free object on is a pair consisting of an object
A
i:X\toU(A)
For any object in and any map between sets
g:X\toU(B)
f:A\toB
g=U(f)\circi
If free objects exist in, the universal property implies every map between two sets induces a unique morphism between the free objects built on them, and this defines a functor
F:Set\toC
\operatorname{Hom}Set(X,U(B))\cong\operatorname{Hom}C(F(X),B).
The creation of free objects proceeds in two steps. For algebras that conform to the associative law, the first step is to consider the collection of all possible words formed from an alphabet. Then one imposes a set of equivalence relations upon the words, where the relations are the defining relations of the algebraic object at hand. The free object then consists of the set of equivalence classes.
Consider, for example, the construction of the free group in two generators. One starts with an alphabet consisting of the five letters
\{e,a,b,a-1,b-1\}
a-1
b-1
S=\{a,b,c,d,e\}
W(S)
In the next step, one imposes a set of equivalence relations. The equivalence relations for a group are that of multiplication by the identity,
ge=eg=g
gg-1=g-1g=e
aebecede=aba-1b-1,
where it was understood that
c
a-1
d
b-1
e
abdc=abb-1a-1=e.
Denoting the equivalence relation or congruence by
\sim
F2=W(S)/\sim.
This is often written as
F2=W(S)/E
W(S)=\{a1a2\ldotsan\vert ak\inS;n\inN\}
E=\{a1a2\ldotsan\vert e=a1a2\ldotsan;ak\inS;n\inN\}
A simpler example are the free monoids. The free monoid on a set X, is the monoid of all finite strings using X as alphabet, with operation concatenation of strings. The identity is the empty string. In essence, the free monoid is simply the set of all words, with no equivalence relations imposed. This example is developed further in the article on the Kleene star.
In the general case, the algebraic relations need not be associative, in which case the starting point is not the set of all words, but rather, strings punctuated with parentheses, which are used to indicate the non-associative groupings of letters. Such a string may equivalently be represented by a binary tree or a free magma; the leaves of the tree are the letters from the alphabet.
The algebraic relations may then be general arities or finitary relations on the leaves of the tree. Rather than starting with the collection of all possible parenthesized strings, it can be more convenient to start with the Herbrand universe. Properly describing or enumerating the contents of a free object can be easy or difficult, depending on the particular algebraic object in question. For example, the free group in two generators is easily described. By contrast, little or nothing is known about the structure of free Heyting algebras in more than one generator.[1] The problem of determining if two different strings belong to the same equivalence class is known as the word problem.
As the examples suggest, free objects look like constructions from syntax; one may reverse that to some extent by saying that major uses of syntax can be explained and characterised as free objects, in a way that makes apparently heavy 'punctuation' explicable (and more memorable).
See main article: Term algebra.
Let
S
A
\rho
S
A
A
\psi\colonS\toA
(A,\psi)
A
\rho
S
B
\rho
\tau\colonS\toB
B
B
\sigma\colonA\toB
\sigma\circ\psi=\tau.
The most general setting for a free object is in category theory, where one defines a functor, the free functor, that is the left adjoint to the forgetful functor.
Consider a category C of algebraic structures; the objects can be thought of as sets plus operations, obeying some laws. This category has a functor,
U:C\toSet
The free functor F, when it exists, is the left adjoint to U. That is,
F:Set\toC
For the free functor to be a left adjoint, one must also have a Set-morphism
ηX:X\toU(F(X))
Whenever is an algebra in, and
g\colonX\toU(B)
f\colonF(X)\toB
g=U(f)\circηX
Concretely, this sends a set into the free object on that set; it is the "inclusion of a basis". Abusing notation,
X\toF(X)
X\toU(F(X))
η:\operatorname{id}Set\toUF
\varepsilon:FU\to\operatorname{id}C
The cofree functor is the right adjoint to the forgetful functor.
There are general existence theorems that apply; the most basic of them guarantees that
Whenever C is a variety, then for every set X there is a free object F(X) in C.
Here, a variety is a synonym for a finitary algebraic category, thus implying that the set of relations are finitary, and algebraic because it is monadic over Set.
Other types of forgetfulness also give rise to objects quite like free objects, in that they are left adjoint to a forgetful functor, not necessarily to sets.
For example, the tensor algebra construction on a vector space is the left adjoint to the functor on associative algebras that ignores the algebra structure. It is therefore often also called a free algebra. Likewise the symmetric algebra and exterior algebra are free symmetric and anti-symmetric algebras on a vector space.
Specific kinds of free objects include: