Free object

Examples

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 ${\displaystyle \{e,a,b,a^{-1},b^{-1}\}}$. In the first step, there is not yet any assigned meaning to the "letters" ${\displaystyle a^{-1}}$ or ${\displaystyle b^{-1}}$; these will be given later, in the second step. Thus, one could equally well start with the alphabet in five letters that is ${\displaystyle S=\{a,b,c,d,e\}}$. In this example, the set of all words or strings ${\displaystyle W(S)}$ 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, ${\displaystyle ge=eg=g}$, and the multiplication of inverses: ${\displaystyle g{g}^{-1}=g^{-1}g=e}$. Applying these relations to the strings above, one obtains

${\displaystyle aebecede=ab{a}^{-1}{b}^{-1},}$

where it was understood that ${\displaystyle c}$ is a stand-in for ${\displaystyle a^{-1}}$, and ${\displaystyle d}$ is a stand-in for ${\displaystyle b^{-1}}$, while ${\displaystyle e}$ is the identity element. Similarly, one has

${\displaystyle abdc=ab{b}^{-1}{a}^{-1}=e.}$

Denoting the equivalence relation or congruence by ${\displaystyle \sim }$, 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

${\displaystyle F_2=W(S)/\sim .}$

This is often written as ${\displaystyle F_2=W(S)/E}$ where ${\displaystyle W(S)=\{a_1{a}_2\dots a_n|a_k\in S;n\in \mathbb{N}\}}$ is the set of all words, and ${\displaystyle E=\{a_1{a}_2\dots a_n|e=a_1{a}_2\dots a_n;a_k\in S;n\in \mathbb{N}\}}$ is the equivalence class of the identity, after the relations defining a group are imposed.

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.

General case

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 (full) binary tree or a free magma; the leaves of the tree are labeled by 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 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; on the other hand, syntactical systems themselves can be characterized as free objects. From this perspective, heavy punctuation in notation (e.g., in programming languages) is a side effect of serializing free structure.

Free universal algebras

Let ${\displaystyle S}$ be a set and ${\displaystyle A}$ be an algebraic structure of type ${\displaystyle \rho }$ generated by ${\displaystyle S}$. The underlying set of this algebraic structure ${\displaystyle A}$, often called its universe, is denoted by ${\displaystyle A}$ . Let ${\displaystyle \psi :S\to A}$ be a function. We say that ${\displaystyle (A,\psi )}$ (or informally just ${\displaystyle A}$) is a free algebra of type ${\displaystyle \rho }$ on the set ${\displaystyle S}$ of free generators if the following universal property holds:

For every algebra ${\displaystyle B}$ of type ${\displaystyle \rho }$ and every function ${\displaystyle \tau :S\to B}$, where ${\displaystyle B}$ is the universe of ${\displaystyle B}$, there exists a unique homomorphism ${\displaystyle \sigma :A\to B}$ such that the following diagram commutes:

${\displaystyle \begin{array}{ccc}S& \stackrel{\psi }{\to }& A\\ & {\searrow }_{\tau }& {\downarrow }^{\sigma }\\ & & B\end{array}}$

This means that ${\displaystyle \sigma \circ \psi =\tau }$.

Free functor

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, ${\displaystyle U:\mathbf{C}\to \mathbf{S}\mathbf{e}\mathbf{t}}$, the forgetful functor, which maps objects and morphisms in C to Set, the category of sets. 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. That is, ${\displaystyle F:\mathbf{S}\mathbf{e}\mathbf{t}\to \mathbf{C}}$ takes sets X in Set to their corresponding free objects F(X) in the category C. The set X can be thought of as the set of "generators" of the free object F(X).

For the free functor to be a left adjoint, one must also have a Set-morphism ${\displaystyle {\eta }_X:X\to U(F(X))}$. More explicitly, F is, up to isomorphisms in C, characterized by the following universal property:

Whenever B is an algebra in C, and ${\displaystyle g:X\to U(B)}$ is a function (a morphism in the category of sets), then there is a unique C-morphism ${\displaystyle f:F(X)\to B}$ such that ${\displaystyle g=U(f)\circ {\eta }_X}$.

Concretely, this sends a set into the free object on that set; it is the "inclusion of a basis". Abusing notation, ${\displaystyle X\to F(X)}$ (this abuses notation because X is a set, while F(X) is an algebra; correctly, it is ${\displaystyle X\to U(F(X))}$).

The natural transformation ${\displaystyle \eta :{\mathrm{id}}_{\mathbf{S}\mathbf{e}\mathbf{t}}\to UF}$ is called the unit; together with the counit ${\displaystyle \epsilon :FU\to {\mathrm{id}}_{\mathbf{C}}}$, one may construct a T-algebra, and so a monad.

The cofree functor is the right adjoint to the forgetful functor. See, for example, cofree coalgebra.

Existence

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.

General case

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.

List of free objects

Specific kinds of free objects include:

• free algebra
  • free associative algebra
  • free commutative algebra
• free category
  • free strict monoidal category
• free group
  • free abelian group
  • free partially commutative group
• free Kleene algebra
• free lattice
  • free Boolean algebra
  • free distributive lattice
  • free Heyting algebra
  • free modular lattice
• free Lie algebra
• free magma
• free module, and in particular, vector space
• free monoid
  • free commutative monoid
  • free partially commutative monoid
• free ring
• free semigroup
• free semiring
  • free commutative semiring
• free theory
• term algebra
• discrete space