Free object
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.
Free objects are the direct generalization to categories of the notion of basis in a vector space.
Let C be a concrete category with a faithful functor U : C → Set.
(called the canonical injection), that satisfies the following universal property: If free objects exist in C, 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
For algebras that conform to the associative law, the first step is to consider the collection of all possible words formed from an alphabet.
The free object then consists of the set of equivalence classes.
Consider, for example, the construction of the free group in two generators.
will include strings such as aebecede and abdc, and so on, of arbitrary finite length, with the letters arranged in every possible order.
In the next step, one imposes a set of equivalence relations.
The equivalence relations for a group are that of multiplication by the identity,
Applying these relations to the strings above, one obtains where it was understood that
Similarly, one has Denoting the equivalence relation or congruence by
, the free object is then the collection of equivalence classes of words.
Thus, in this example, the free group in two generators is the quotient This is often written as
is the equivalence class of the identity, after the relations defining a group are imposed.
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.
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.
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).
of free generators if the following universal property holds: For every algebra
Consider a category C of algebraic structures; the objects can be thought of as sets plus operations, obeying some laws.
The forgetful functor is very simple: it just ignores all of the operations.
The free functor F, when it exists, is the left adjoint to U.
More explicitly, F is, up to isomorphisms in C, characterized by the following universal property: Concretely, this sends a set into the free object on that set; it is the "inclusion of a basis".
(this abuses notation because X is a set, while F(X) is an algebra; correctly, it is
There are general existence theorems that apply; the most basic of them guarantees that 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.
