In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, the idea of a free object is one of the basic concepts of
abstract algebra
In mathematics, more specifically algebra, abstract algebra or modern algebra is the study of algebraic structures. Algebraic structures include groups, rings, fields, modules, vector spaces, lattices, and algebras over a field. The ter ...
. Informally, a free object over a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
''A'' can be thought of as being a "generic"
algebraic structure
In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set o ...
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. Examples include
free groups,
tensor algebras, or
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.
Formal definition
Any set ''X'' may be used to generate the free semilattice ''FX''. Th ...
s.
The concept is a part of
universal algebra
Universal 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 groups as the object of study ...
, 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 is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, ca ...
, although this is in yet more abstract terms.
Definition
Free objects are the direct generalization to
categories 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 The following definition translates this to any category.
A
concrete category
In mathematics, a concrete category is a category that is equipped with a faithful functor to the category of sets (or sometimes to another category, ''see Relative concreteness below''). This functor makes it possible to think of the objects of t ...
is a category that is equipped with a
faithful functor
In category theory, a faithful functor is a functor that is injective on hom-sets, and a full functor is surjective on hom-sets. A functor that has both properties is called a full and faithful functor.
Formal definitions
Explicitly, let ''C'' ...
to Set, the
category of sets
In the mathematical field of category theory, the category of sets, denoted as Set, is the category whose objects are sets. The arrows or morphisms between sets ''A'' and ''B'' are the total functions from ''A'' to ''B'', and the composition o ...
. Let be a concrete category with a faithful functor . Let be a set (that is, an object in Set), which will be the ''basis'' of the free object to be defined. A free object on is a pair of an object
in and an injection
(called the ''canonical injection''), that satisfies the following
universal property
In mathematics, more specifically in category theory, a universal property is a property that characterizes up to an isomorphism the result of some constructions. Thus, universal properties can be used for defining some objects independently fr ...
:
:For any object in and any map between sets
there exists a unique morphism
in such that
That is, the following
diagram
A diagram is a symbolic representation of information using visualization techniques. Diagrams have been used since prehistoric times on walls of caves, but became more prevalent during the Enlightenment. Sometimes, the technique uses a three ...
commutes:
::
If free objects exist in , it is straightforward to verify that the universal property implies that every map between two sets induces a unique morphism between the free objects build on them, and that this defines a functor
It follows that, if free objects exist in , the functor , called the ''free-object functor'' is a
left adjoint to the forgetful functor ; that is, there is a bijection
:
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
A word is a basic element of language that carries an objective or practical meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of what a word is, there is no conse ...
s formed from an
alphabet
An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a syllab ...
. Then one imposes a set of
equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relatio ...
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 of
equivalence class
In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements a ...
es.
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"
or
; these will be given later, in the second step. Thus, one could equally well start with the alphabet in five letters that is
. In this example, the set of all words or strings
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,
, and the multiplication of inverses:
. Applying these relations to the strings above, one obtains
:
where it was understood that
is a stand-in for
, and
is a stand-in for
, while
is the identity element. Similarly, one has
:
Denoting the equivalence relation or
congruence by
, the free object is then the collection of
equivalence class
In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements a ...
es of words. Thus, in this example, the free group in two generators is the
quotient
:
This is often written as
where
is the set of all words, and
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
In formal language theory and computer programming, string concatenation is the operation of joining character strings end-to-end. For example, the concatenation of "snow" and "ball" is "snowball". In certain formalisations of concatenat ...
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
In computer science, a binary tree is a k-ary k = 2 tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a (non-empty) binary t ...
or a
free magma
In abstract algebra, a magma, binar, or, rarely, groupoid is a basic kind of algebraic structure. Specifically, a magma consists of a set equipped with a single binary operation that must be closed by definition. No other properties are imposed.
...
; the leaves of the tree are 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.
[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.
As the examples suggest, free objects look like constructions from
syntax
In linguistics, syntax () is the study of how words and morphemes combine to form larger units such as phrases and sentences. Central concerns of syntax include word order, grammatical relations, hierarchical sentence structure ( constituenc ...
; 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
be any set, and let
be an
algebraic structure
In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set o ...
of type
generated by
. Let the underlying set of this algebraic structure
, sometimes called its universe, be
, and let
be a function. We say that
(or informally just
) is a ''free algebra'' (of type
) on the set
of ''free generators'' if, for every algebra
of type
and every function
, where
is a universe of
, there exists a unique homomorphism
such that
Free functor
The most general setting for a free object is in
category theory
Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, ca ...
, where one defines a
functor, the free functor, that is the
left adjoint to the
forgetful functor In mathematics, in the area of category theory, a forgetful functor (also known as a stripping functor) 'forgets' or drops some or all of the input's structure or properties 'before' mapping to the output. For an algebraic structure of a given sign ...
.
Consider a category C of
algebraic structure
In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set o ...
s; the objects can be thought of as sets plus operations, obeying some laws. This category has a functor,
, the
forgetful functor In mathematics, in the area of category theory, a forgetful functor (also known as a stripping functor) 'forgets' or drops some or all of the input's structure or properties 'before' mapping to the output. For an algebraic structure of a given sign ...
, which maps objects and functions in C to Set, the
category of sets
In the mathematical field of category theory, the category of sets, denoted as Set, is the category whose objects are sets. The arrows or morphisms between sets ''A'' and ''B'' are the total functions from ''A'' to ''B'', and the composition o ...
. 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,
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
. More explicitly, ''F'' is, up to isomorphisms in C, characterized by the following
universal property
In mathematics, more specifically in category theory, a universal property is a property that characterizes up to an isomorphism the result of some constructions. Thus, universal properties can be used for defining some objects independently fr ...
:
: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,
(this abuses notation because ''X'' is a set, while ''F''(''X'') is an algebra; correctly, it is
).
The
natural transformation
In category theory, a branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure (i.e., the composition of morphisms) of the categories involved. Hence, a natur ...
is called the
unit
Unit may refer to:
Arts and entertainment
* UNIT, a fictional military organization in the science fiction television series ''Doctor Who''
* Unit of action, a discrete piece of action (or beat) in a theatrical presentation
Music
* ''Unit'' (a ...
; together with the
counit In mathematics, coalgebras or cogebras are structures that are dual (in the category-theoretic sense of reversing arrows) to unital associative algebras. The axioms of unital associative algebras can be formulated in terms of commutative diagram ...
, one may construct a
T-algebra
In category theory, a branch of mathematics, a monad (also triple, triad, standard construction and fundamental construction) is a monoid in the category of endofunctors. An endofunctor is a functor mapping a category to itself, and a monad is ...
, and so a
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
Variety may refer to:
Arts and entertainment Entertainment formats
* Variety (radio)
* Variety show, in theater and television
Films
* ''Variety'' (1925 film), a German silent film directed by Ewald Andre Dupont
* ''Variety'' (1935 film), ...
, 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
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
is the left adjoint to the functor on
associative algebra
In mathematics, an associative algebra ''A'' is an algebraic structure with compatible operations of addition, multiplication (assumed to be associative), and a scalar multiplication by elements in some field ''K''. The addition and multiplic ...
s that ignores the algebra structure. It is therefore often also called a
free algebra. Likewise the
symmetric algebra
In mathematics, the symmetric algebra (also denoted on a vector space over a field is a commutative algebra over that contains , and is, in some sense, minimal for this property. Here, "minimal" means that satisfies the following universal ...
and
exterior algebra
In mathematics, the exterior algebra, or Grassmann algebra, named after Hermann Grassmann, is an algebra that uses the exterior product or wedge product as its multiplication. In mathematics, the exterior product or wedge product of vectors is a ...
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
In mathematics, a free abelian group is an abelian group with a basis. Being an abelian group means that it is a set with an addition operation that is associative, commutative, and invertible. A basis, also called an integral basis, is a subse ...
**
free partially commutative group
*
free Kleene algebra
*
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.
Formal definition
Any set ''X'' may be used to generate the free semilattice ''FX''. Th ...
**
free Boolean algebra In mathematics, a free Boolean algebra is a Boolean algebra with a distinguished set of elements, called ''generators'', such that:
#Each element of the Boolean algebra can be expressed as a finite combination of generators, using the Boolean opera ...
**
free distributive lattice
**
free Heyting algebra
** free
modular lattice
In the branch of mathematics called order theory, a modular lattice is a lattice that satisfies the following self- dual condition,
;Modular law: implies
where are arbitrary elements in the lattice, ≤ is the partial order, and & ...
*
free Lie algebra
*
free magma
In abstract algebra, a magma, binar, or, rarely, groupoid is a basic kind of algebraic structure. Specifically, a magma consists of a set equipped with a single binary operation that must be closed by definition. No other properties are imposed.
...
*
free module
In mathematics, a free module is a module that has a basis – that is, a generating set consisting of linearly independent elements. Every vector space is a free module, but, if the ring of the coefficients is not a division ring (not a fiel ...
, and in particular,
vector space
In mathematics and physics, a vector space (also called a linear space) is a set whose elements, often called '' vectors'', may be added together and multiplied ("scaled") by numbers called ''scalars''. Scalars are often real numbers, but can ...
*
free monoid
**
free commutative monoid
**
free partially commutative monoid
*
free ring
*
free semigroup
*
free semiring
**
free commutative semiring
*
free theory
*
term algebra
*
discrete space
In topology, a discrete space is a particularly simple example of a topological space or similar structure, one in which the points form a , meaning they are ''isolated'' from each other in a certain sense. The discrete topology is the finest top ...
See also
*
Generating set
Notes
{{DEFAULTSORT:Free Object
Mathematics articles needing expert attention
Abstract algebra
Combinatorics on words
Adjoint functors