# Free object

In

mathematics , the idea of a**free object**is one of the basic concepts ofabstract algebra . It is a part ofuniversal algebra , in the sense that it relates to all types of algebraic structure (withfinitary operations). It also has a clean formulation in terms ofcategory theory , although this is in yet more abstract terms. To understand the concept, it is best to master several special cases first, such asfree group s,tensor algebra s, orfree lattice s.**Introduction**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 analphabet . Then one imposes a set ofequivalence relation s upon the words, where the relations are the defining relations of the algebraic object at hand. The free object then consists of the set ofequivalence class es.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\}\}$. 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 alphabet 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 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, $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 or congruence by $sim$, the free object is then the collection of

equivalence class es of words. Thus, in this example, the free group in two generators is the quotient:$F\_2=W(S)/sim$

This is often written as

:$F\_2=W(S)/E$

where:$W(S)=\{a\_1a\_2ldots\; a\_n,vert;\; a\_kin\; S,;\; ,nmbox\{\; finite\; \}\; \}$

is the set of all words, and

:$E=\{a\_1a\_2ldots\; a\_n,vert;\; e=a\_1a\_2ldots\; a\_n,;,\; a\_kin\; S,;,nmbox\{\; finite\; \}\}$is the equivalence class of the identity, after the relations defining a group are imposed.

A simpler example are the

free monoid s. The free monoid on a set "X", is the monoid of all finite strings using "X" as alphabet, with operationconcatenation 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 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 a

binary tree or afree magma ; the leaves of the tree are the letters from the alphabet.The algebraic relations may then be general arities or

finitary relation s 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 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 algebra s in more than one generator [*Peter T. Johnstone, "Stone Spaces", (1982) Cambridge University Press, ISBN 0-521-23893-5."(A treatment of the one-generator free Heyting algebra is given in chapter 1,section 4.11)"*] . 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).**Free universal algebras**Let $S$ be any set, let $mathbf\{A\}$ be an

algebraic structure of type $ho$, and let $psi\; :S\; longrightarrow\; mathbf\{A\}$ be a function. we say that $(mathbf\{A\},\; psi)$ (or informally just $mathbf\{A\}$) is a "free algebra" (of type $ho$) on the set $S$ of "free generators" if, for every algebra $mathbf\{B\}$ of type $ho$ and function $au\; :\; S\; longrightarrow\; mathbf\{B\}$, there exists a unique homomorphism $sigma\; :mathbf\{A\}\; longrightarrow\; mathbf\{B\}$ such that $sigma\; psi\; =\; au$.**Free functor**The most general setting for a free object is in

category theory , where one defines afunctor , the**free functor**, that is theleft adjoint to theforgetful functor .Consider the category

**C**ofalgebraic structure s; these can be thought of as sets plus operations, obeying some laws. This category has a functor, $U:mathbf\{C\}\; omathbf\{Set\}$, theforgetful functor , which maps objects and functions in**C**to**Set**, thecategory 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, $F:mathbf\{Set\}\; omathbf\{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

**C**-morphism $eta:X\; o\; U(F(X)),!$. More explicitly, "F" is, up to isomorphisms in**C**, characterized by the followinguniversal property ::Whenever "A" is an algebra in**C**, and "g": "X"→"U"("A") is a function (a morphism in the category of sets), then there is a unique**C**-morphism "h": "F"("X")→"A" such that "U"("h")o"η" = "g".Concretely, this sends a set into the free object on that set; it's the "inclusion of a basis". Abusing notation, $X\; o\; F(X)$ (this abuses notation because "X" is a set, while "F(X)" is an algebra; correctly, it is $X\; o\; U(F(X))$).

The

natural transformation $eta:operatorname\{id\}\_mathbf\{Set\}\; o\; UF$ is called the unit; together with thecounit $varepsilon:FU\; o\; operatorname\; \{id\}\_mathbf\{C\}$, one may construct aT-algebra , and so a monad. This leads to the next topic: free functors exist when**C**is a monad over**Set**.**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 avector space as left adjoint to the functor onassociative algebra s that ignores the algebra structure. It is therefore often also called afree algebra .Likewise the

symmetric algebra andexterior algebra are free symmetric and anti-symmetric algebras on a vector space.**List of free objects**Specific kinds of free objects include:

*free magma

*free semigroup

*free monoid

**free commutative monoid

*free group

**free abelian group

*free semiring

**free commutative semiring

*free Kleene algebra

*free ring

*free module

*free algebra

**free commutative algebra

**free associative algebra

*free lattice

**free distributive lattice

**free Heyting algebra

**free Boolean algebra

*Generating set **ee also***

Term algebra **Notes**

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Free**— may refer to: Free will Political freedom Economic freedom Something given or supplied without payment (gratis) Gratis versus Libre, the distinction between the two meanings above Free may also refer to: Contents 1 Arts and philosophy … Wikipedia**Free algebra**— This article is about free algebras in ring theory. For the more general free algebras in universal algebra, see free object. In mathematics, especially in the area of abstract algebra known as ring theory, a free algebra is the noncommutative… … Wikipedia**Free lattice**— In mathematics, in the area of order theory, a free lattice is the free object corresponding to a lattice. As free objects, they have the universal property. The word problem for free lattices is also challenging.Formal definitionAny set X may be … Wikipedia**Free module**— In mathematics, a free module is a free object in the category of modules. Given a set S , a free module on S is a (particular construction of a) free module with basis S .Every vector space is free, and the free vector space on a set is a… … Wikipedia**Free group**— In mathematics, a group G is called free if there is a subset S of G such that any element of G can be written in one and only one way as a product of finitely many elements of S and their inverses (disregarding trivial variations such as st 1 =… … Wikipedia**Free Lie algebra**— In mathematics, a free Lie algebra, over a given field K, is a Lie algebra generated by a set X, without any imposed relations. Contents 1 Definition 2 Universal enveloping algebra 3 Hall sets … Wikipedia**Free monoid**— In abstract algebra, the free monoid on a set A is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from A , with the binary operation of concatenation. It is usually denoted A lowast;. The identity… … Wikipedia**Free product**— In abstract algebra, the free product of groups constructs a group from two or more given ones. Given, for example, groups G and H , the free product G*H can be constructed as follows: given presentations of G and of H , take the generators of G… … Wikipedia**Object Pascal**— Paradigm(s) imperative, structured, object oriented, functional (Delphi dialect only) Appeared in 1986 (1986) Designed by Apple, Niklaus Wirth, Anders Hejlsberg … Wikipedia**Object Pascal**— Семантика: императивная Класс языка: мультипарадигмальный: императивный, структурный, объектно ориентированный, обобщённый[1], процедурный Тип исполнения: компилируемый … Википедия