TheInfoList

In
mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It has no generally ...
, the idea of a free object is one of the basic concepts of abstract algebra. It is a part of
universal algebraUniversal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures themselves, not examples ("models") of algebraic structures. For instance, rather than take particular Group (mathematics), groups as t ...
, 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 Category theory formalizes mathematical structure and its concepts in terms of a Graph labeling, labeled directed graph called a ''Category (mathematics), category'', whose nodes are called ''objects'', and whose labelled directed edges are cal ...
, although this is in yet more abstract terms. Examples include
free group for the free group on two generators would look like. Each vertex represents an element of the free group, and each edge represents multiplication by ''a'' or ''b''. In mathematics Mathematics (from Ancient Greek, Greek: ) includes the stud ...
s,
tensor algebraIn mathematics, the tensor algebra of a vector space ''V'', denoted ''T''(''V'') or ''T''(''V''), is the algebra over a field, algebra of tensors on ''V'' (of any rank) with multiplication being the tensor product. It is the free algebra on ''V'', in ...
s, or free lattices. 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.

# Definition

Free objects are the direct generalization to
categories Category, plural categories, may refer to: Philosophy and general uses *Categorization Categorization is the human ability and activity of recognizing shared features or similarities between the elements of the experience of the world (such ...
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 ''E''1. The following definition translates this to any category. A
concrete category Interior of the Pantheon dome, seen from beneath. The concrete for the coffered dome was laid on moulds, mounted on temporary scaffolding. Concrete is a composite material A composite material (also called a composition material or shorte ...
is a category that is equipped with a faithful functor to Set, the
category of setsIn the mathematics, mathematical field of category theory, the category of sets, denoted as Set, is the Category (mathematics), category whose Category theory, objects are Set (mathematics), sets. The arrows or morphisms between sets ''A'' and ''B'' ...
. Let ''C'' be a concrete category with faithful functor . Let ''X'' be an object in Set (that is, ''X'' is a set, here called a ''basis''), let ''A'' be an object in C, and let be an injective map between the sets ''X'' and ''F''(''A'') (called the ''canonical insertion''). Then ''A'' is said to be the free object on ''X'' (with respect to ''i'') if and only if it satisfies the following
universal property In category theory Category theory formalizes mathematical structure and its concepts in terms of a Graph labeling, labeled directed graph called a ''Category (mathematics), category'', whose nodes are called ''objects'', and whose labelled d ...
: :for any object ''B'' in C and any map between sets , there exists a unique morphism in C such that . That is, the following
diagram A diagram is a symbolic representation of information Information can be thought of as the resolution of uncertainty; it answers the question of "What an entity is" and thus defines both its essence and the nature of its characteristics. T ...
commutes: ::$\begin X \xrightarrow F\left(A\right) \\ _f \searrow \quad \swarrow _ \\ F\left(B\right) \quad \\ \end$ In this way the free functor that builds the free object ''A'' from the set ''X'' becomes left adjoint to the forgetful functor.

# 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
word In linguistics, a word of a spoken language can be defined as the smallest sequence of phonemes that can be uttered in isolation with semantic, objective or pragmatics, practical meaning (linguistics), meaning. In many languages, words also corres ...
s formed from an
alphabet An alphabet is a standardized set of basic written symbols or graphemes (called letter (alphabet), letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each ...
. 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 $\$. In the first step, there is not yet any assigned meaning to the "letters" $a^$ or $b^$; these will be given later, in the second step. Thus, one could equally well start with the alphabet in five letters that is $S=\$. In this example, the set of all words or strings $W\left(S\right)$ 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 (mathematics), group are that of multiplication by the identity, $ge=eg=g$, and the multiplication of inverses: $gg^=g^g=e$. Applying these relations to the strings above, one obtains :$aebecede = aba^b^,$ where it was understood that $c$ is a stand-in for $a^$, and $d$ is a stand-in for $b^$, while $e$ is the identity element. Similarly, one has :$abdc = abb^a^ = e.$ Denoting the equivalence relation or congruence relation, congruence by $\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 set, quotient :$F_2=W\left(S\right)/\sim.$ This is often written as $F_2=W\left(S\right)/E$ where $W\left(S\right) = \$ is the set of all words, and $E = \$ 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 string (computer science), 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 binary tree or a free magma; the leaves of the tree are the letters from the alphabet. The algebraic relations may then be general arity, 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.Peter T. Johnstone, ''Stone Spaces'', (1982) Cambridge University Press, . ''(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 (mathematics), 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, and let $\mathbf$ be an algebraic structure of type $\rho$ generated by $S$. Let the underlying set of this algebraic structure $\mathbf$, sometimes called its universe, be $A$, and let $\psi: S \to A$ be a function. We say that $\left(A, \psi\right)$ (or informally just $\mathbf$) is a ''free algebra'' (of type $\rho$) on the set $S$ of ''free generators'' if, for every algebra $\mathbf$ of type $\rho$ and every function $\tau: S \to B$, where $B$ is a universe of $\mathbf$, there exists a unique homomorphism $\sigma: A \to B$ such that $\sigma \circ \psi = \tau.$

# Free functor

The most general setting for a free object is in
category theory Category theory formalizes mathematical structure and its concepts in terms of a Graph labeling, labeled directed graph called a ''Category (mathematics), category'', whose nodes are called ''objects'', and whose labelled directed edges are cal ...
, where one defines a functor, the free functor, that is the left adjoint to the forgetful functor. Consider the category C of algebraic structures; these can be thought of as sets plus operations, obeying some laws. This category has a functor, $U:\mathbf\to\mathbf$, the forgetful functor, which maps objects and functions in C to Set, the
category of setsIn the mathematics, mathematical field of category theory, the category of sets, denoted as Set, is the Category (mathematics), category whose Category theory, objects are Set (mathematics), sets. The arrows or morphisms between sets ''A'' and ''B'' ...
. 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\to\mathbf$ 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 $\eta:X\to U\left(F\left(X\right)\right)\,\!$. More explicitly, ''F'' is, up to isomorphisms in C, characterized by the following
universal property In category theory Category theory formalizes mathematical structure and its concepts in terms of a Graph labeling, labeled directed graph called a ''Category (mathematics), category'', whose nodes are called ''objects'', and whose labelled d ...
: :Whenever ''A'' is an algebra in C, and is a function (a morphism in the category of sets), then there is a unique C-morphism such that . Concretely, this sends a set into the free object on that set; it is the "inclusion of a basis". Abusing notation, $X \to F\left(X\right)$ (this abuses notation because ''X'' is a set, while ''F''(''X'') is an algebra; correctly, it is $X \to U\left(F\left(X\right)\right)$). The natural transformation $\eta:\operatorname_\mathbf\to UF$ is called the unit (category theory), unit; together with the counit $\varepsilon:FU\to \operatorname _\mathbf$, one may construct a T-algebra, and so a monad (category theory), monad. The cofree functor is the right adjoint to the forgetful functor.

## Existence

There are general existence theorems that apply; the most basic of them guarantees that :Whenever C is a variety (universal algebra), 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 relation, finitary, and ''algebraic'' because it is monad (category theory), 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 algebraIn mathematics, the tensor algebra of a vector space ''V'', denoted ''T''(''V'') or ''T''(''V''), is the algebra over a field, algebra of tensors on ''V'' (of any rank) with multiplication being the tensor product. It is the free algebra on ''V'', in ...
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 for the free group on two generators would look like. Each vertex represents an element of the free group, and each edge represents multiplication by ''a'' or ''b''. In mathematics Mathematics (from Ancient Greek, Greek: ) includes the stud ...
**free abelian group **free partially commutative group *Kleene algebra#Examples, free Kleene algebra * free lattice **free Boolean algebra **distributive lattice#Free distributive lattices, free distributive lattice **free Heyting algebra ** free modular lattice *free Lie algebra *free magma *free module, and in particular, vector space *free monoid **free monoid#The free commutative monoid, free commutative monoid **free partially commutative monoid *free ring *free semigroup *free semiring **semiring#Examples, free commutative semiring *free theory *term algebra *discrete space