Free object

Inmathematics,the idea of afree objectis one of the basic concepts ofabstract algebra.Informally, a free object over asetAcan be thought of as being a "generic"algebraic structureoverA:the only equations that hold between elements of the free object are those that follow from the defining axioms of the algebraic structure. Examples includefree groups,tensor algebras,orfree lattices.

The concept is a part ofuniversal algebra,in the sense that it relates to all types of algebraic structure (withfinitaryoperations). It also has a formulation in terms ofcategory theory,although this is in yet more abstract terms.

Definition

Free objects are the direct generalization tocategoriesof the notion ofbasisin a vector space. A linear functionu:E₁→E₂between vector spaces is entirely determined by its values on a basis of the vector spaceE₁.The following definition translates this to any category.

Aconcrete categoryis a category that is equipped with afaithful functortoSet,thecategory of sets.LetCbe a concrete category with a faithful functorU:C→Set.LetXbe a set (that is, an object inSet), which will be thebasisof the free object to be defined. Afree objectonXis a pair consisting of an object$A$inCand an injection$i:X\to U(A)$(called thecanonical injection), that satisfies the followinguniversal property:

For any objectBinCand any map between sets$g:X\to U(B)$,there exists a unique morphism$f:A\to B$inCsuch that$g=U(f)\circ i$.That is, the followingdiagramcommutes:

x

If free objects exist inC,the universal property impliesevery map between two sets induces a unique morphism between the free objects built on them, and this defines a functor$F:\mathbf {Set} \to \mathbf {C}$.It follows that, if free objects exist inC,the functorF,called thefree functoris aleft adjointto the faithful functorU;that is, there is a bijection

$\operatorname {Hom} _{\mathbf {Set} }(X,U(B))\cong \operatorname {Hom} _{\mathbf {C} }(F(X),B).$

Examples

The creation of free objects proceeds in two steps. For algebras that conform to theassociative law,the first step is to consider the collection of all possiblewordsformed from anAlpha bet.Then one imposes a set ofequivalence relationsupon the words, where the relations are the defining relations of the algebraic object at hand. The free object then consists of the set ofequivalence classes.

Consider, for example, the construction of thefree groupin twogenerators.One starts with an Alpha bet consisting of the five letters$\{e,a,b,a^{-1},b^{-1}\}$.In the first step, there is not yet any assigned meaning to the "letters"$a^{-1}$or$b^{-1}$;these will be given later, in the second step. Thus, one could equally well start with the Alpha bet in five letters that is$S=\{a,b,c,d,e\}$.In this example, the set of all words or strings$W(S)$will include strings such asaebecedeandabdc,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 agroupare that of multiplication by the identity,$ge=eg=g$,and the multiplication of inverses:$gg^{-1}=g^{-1}g=e$.Applying these relations to the strings above, one obtains

$aebecede=aba^{-1}b^{-1},$

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

$abdc=abb^{-1}a^{-1}=e.$

Denoting the equivalence relation orcongruenceby$\sim$,the free object is then the collection ofequivalence classesof words. Thus, in this example, the free group in two generators is thequotient

$F_{2}=W(S)/\sim.$

This is often written as$F_{2}=W(S)/E$where$W(S)=\{a_{1}a_{2}\ldots a_{n}\,\vert \;a_{k}\in S\,;\,n\in \mathbb {N} \}$is the set of all words, and$E=\{a_{1}a_{2}\ldots a_{n}\,\vert \;e=a_{1}a_{2}\ldots 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 thefree monoids.The free monoid on a setX,is the monoid of all finitestringsusingXas Alpha bet, with operationconcatenationof 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 theKleene 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 abinary treeor afree magma;the leaves of the tree are the letters from the Alpha bet.

The algebraic relations may then be generalaritiesorfinitary relationson the leaves of the tree. Rather than starting with the collection of all possible parenthesized strings, it can be more convenient to start with theHerbrand 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 offree Heyting algebrasin more than one generator.The problem of determining if two different strings belong to the same equivalence class is known as theword problem.

As the examples suggest, free objects look like constructions fromsyntax;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).

Free universal algebras

Main article:Term algebra

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

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

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

This means that$\sigma \circ \psi =\tau$.

Free functor

The most general setting for a free object is incategory theory,where one defines afunctor,thefree functor,that is theleft adjointto theforgetful functor.

Consider a categoryCofalgebraic structures;the objects can be thought of as sets plus operations, obeying some laws. This category has a functor,$U:\mathbf {C} \to \mathbf {Set}$,theforgetful functor,which maps objects and morphisms inCtoSet,thecategory of sets.The forgetful functor is very simple: it just ignores all of the operations.

The free functorF,when it exists, is the left adjoint toU.That is,$F:\mathbf {Set} \to \mathbf {C}$takes setsXinSetto their corresponding free objectsF(X) in the categoryC.The setXcan be thought of as the set of "generators" of the free objectF(X).

For the free functor to be a left adjoint, one must also have aSet-morphism$\eta _{X}:X\to U(F(X))\,\!$.More explicitly,Fis, up to isomorphisms inC,characterized by the followinguniversal property:

WheneverBis an algebra inC,and$g\colon X\to U(B)$is a function (a morphism in the category of sets), then there is a uniqueC-morphism$f\colon F(X)\to B$such that$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,$X\to F(X)$(this abuses notation becauseXis a set, whileF(X) is an algebra; correctly, it is$X\to U(F(X))$).

Thenatural transformation$\eta:\operatorname {id} _{\mathbf {Set} }\to UF$is called theunit;together with thecounit$\varepsilon:FU\to \operatorname {id} _{\mathbf {C} }$,one may construct aT-algebra,and so amonad.

Thecofree functoris theright adjointto the forgetful functor.

Existence

There are general existence theorems that apply; the most basic of them guarantees that

WheneverCis avariety,then for every setXthere is a free objectF(X) inC.

Here, a variety is a synonym for afinitary algebraic category,thus implying that the set of relations arefinitary,andalgebraicbecause it ismonadicoverSet.

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, thetensor algebraconstruction on avector spaceis the left adjoint to the functor onassociative algebrasthat ignores the algebra structure. It is therefore often also called afree algebra.Likewise thesymmetric algebraandexterior algebraare free symmetric and anti-symmetric algebras on a vector space.

List of free objects

See also:Category:Free algebraic structures

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
  • freemodular 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

See also

• Generating set

External links

• InnLab:free functor,free object,vector space