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 term ''a ...
. 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 of ...
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 group
In mathematics, the free group ''F'S'' over a given set ''S'' consists of all words that can be built from members of ''S'', considering two words to be different unless their equality follows from the group axioms (e.g. ''st'' = ''suu''−1' ...
s,
tensor algebra
In mathematics, the tensor algebra of a vector space ''V'', denoted ''T''(''V'') or ''T''(''V''), is the algebra of tensors on ''V'' (of any rank) with multiplication being the tensor product. It is the free algebra on ''V'', in the sense of being ...
s, or
free lattices.
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
In mathematics and logic, an operation is finitary if it has finite arity, i.e. if it has a finite number of input values. Similarly, an infinitary operation is one with an infinite number of input values.
In standard mathematics, an operation ...
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, cate ...
, although this is in yet more abstract terms.
Definition
Free objects are the direct generalization to
categories
Category, plural categories, may refer to:
Philosophy and general uses
*Categorization, categories in cognitive science, information science and generally
*Category of being
* ''Categories'' (Aristotle)
*Category (Kant)
* Categories (Peirce)
* ...
of the notion of
basis
Basis may refer to:
Finance and accounting
* Adjusted basis, the net cost of an asset after adjusting for various tax-related items
*Basis point, 0.01%, often used in the context of interest rates
* Basis trading, a trading strategy consisting ...
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 ...
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
In mathematics, specifically category theory, adjunction is a relationship that two functors may exhibit, intuitively corresponding to a weak form of equivalence between two related categories. Two functors that stand in this relationship are kno ...
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
In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement f ...
, the first step is to consider the collection of all possible
word
A word is a basic element of language that carries an semantics, objective or pragmatics, practical semantics, meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of w ...
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 syll ...
. 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 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 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 mathematics, the free group ''F'S'' over a given set ''S'' consists of all words that can be built from members of ''S'', considering two words to be different unless their equality follows from the group axioms (e.g. ''st'' = ''suu''−1' ...
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
A group is a number of persons or things that are located, gathered, or classed together.
Groups of people
* Cultural group, a group whose members share the same cultural identity
* Ethnic group, a group whose members share the same ethnic ide ...
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
In arithmetic, a quotient (from lat, quotiens 'how many times', pronounced ) is a quantity produced by the division of two numbers. The quotient has widespread use throughout mathematics, and is commonly referred to as the integer part of a ...
:
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 monoid In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero eleme ...
s. The free monoid on a set ''X'', is the monoid of all finite
strings
String or strings may refer to:
*String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects
Arts, entertainment, and media Films
* ''Strings'' (1991 film), a Canadian anim ...
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
In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. In mathematics,
it is more commonly known as the free monoid ...
.
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; the leaves of the tree are the letters from the alphabet.
The algebraic relations may then be general
arities or
finitary relation
In mathematics, a finitary relation over sets is a subset of the Cartesian product ; that is, it is a set of ''n''-tuples consisting of elements ''x'i'' in ''X'i''. Typically, the relation describes a possible connection between the elemen ...
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 the
Herbrand universe
In first-order logic, a Herbrand structure ''S'' is a structure over a vocabulary σ that is defined solely by the syntactical properties of σ. The idea is to take the symbols of terms as their values, e.g. the denotation of a constant symbol '' ...
. 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 algebra
Free may refer to:
Concept
* Freedom, having the ability to do something, without having to obey anyone/anything
* Freethought, a position that beliefs should be formed only on the basis of logic, reason, and empiricism
* Emancipate, to proc ...
s 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 ( constituency) ...
; 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 of ...
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, cate ...
, where one defines a
functor
In mathematics, specifically category theory, a functor is a Map (mathematics), mapping between Category (mathematics), categories. Functors were first considered in algebraic topology, where algebraic objects (such as the fundamental group) ar ...
, the free functor, that is the
left adjoint
In mathematics, specifically category theory, adjunction is a relationship that two functors may exhibit, intuitively corresponding to a weak form of equivalence between two related categories. Two functors that stand in this relationship are kno ...
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 of ...
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'' (alb ...
; 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, and so a
monad
Monad may refer to:
Philosophy
* Monad (philosophy), a term meaning "unit"
**Monism, the concept of "one essence" in the metaphysical and theological theory
** Monad (Gnosticism), the most primal aspect of God in Gnosticism
* ''Great Monad'', a ...
.
The cofree functor is the
right adjoint
In mathematics, specifically category theory, adjunction is a relationship that two functors may exhibit, intuitively corresponding to a weak form of equivalence between two related categories. Two functors that stand in this relationship are kn ...
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
In mathematics and logic, an operation is finitary if it has finite arity, i.e. if it has a finite number of input values. Similarly, an infinitary operation is one with an infinite number of input values.
In standard mathematics, an operation ...
, 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
In mathematics, the tensor algebra of a vector space ''V'', denoted ''T''(''V'') or ''T''(''V''), is the algebra of tensors on ''V'' (of any rank) with multiplication being the tensor product. It is the free algebra on ''V'', in the sense of being ...
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
In mathematics, especially in the area of abstract algebra known as ring theory, a free algebra is the noncommutative analogue of a polynomial ring since its elements may be described as "polynomials" with non-commuting variables. Likewise, the po ...
. 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
In mathematics, especially in the area of abstract algebra known as ring theory, a free algebra is the noncommutative analogue of a polynomial ring since its elements may be described as "polynomials" with non-commuting variables. Likewise, the po ...
**
free associative algebra
**
free commutative algebra
In mathematics, especially in the field of algebra, a polynomial ring or polynomial algebra is a ring (which is also a commutative algebra) formed from the set of polynomials in one or more indeterminates (traditionally also called variabl ...
*
free category In mathematics, the free category or path category generated by a directed graph or quiver is the category that results from freely concatenating arrows together, whenever the target of one arrow is the source of the next.
More precisely, the objec ...
**
free strict monoidal category
Free may refer to:
Concept
* Freedom, having the ability to do something, without having to obey anyone/anything
* Freethought, a position that beliefs should be formed only on the basis of logic, reason, and empiricism
* Emancipate, to procure ...
*
free group
In mathematics, the free group ''F'S'' over a given set ''S'' consists of all words that can be built from members of ''S'', considering two words to be different unless their equality follows from the group axioms (e.g. ''st'' = ''suu''−1' ...
**
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
**
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
In mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set un ...
**
free Heyting algebra
Free may refer to:
Concept
* Freedom, having the ability to do something, without having to obey anyone/anything
* Freethought, a position that beliefs should be formed only on the basis of logic, reason, and empiricism
* Emancipate, to proc ...
** 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 In mathematics, a free Lie algebra over a field ''K'' is a Lie algebra generated by a set ''X'', without any imposed relations other than the defining relations of alternating ''K''-bilinearity and the Jacobi identity.
Definition
The definition ...
*
free magma
*
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 field in t ...
, 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 In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero eleme ...
**
free commutative monoid
**
free partially commutative monoid
*
free ring
*
free semigroup In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero ele ...
*
free semiring
**
free commutative semiring
*
free theory
Free may refer to:
Concept
* Freedom, having the ability to do something, without having to obey anyone/anything
* Freethought, a position that beliefs should be formed only on the basis of logic, reason, and empiricism
* Emancipate, to procure ...
*
term algebra
In universal algebra and mathematical logic, a term algebra is a freely generated algebraic structure over a given signature. For example, in a signature consisting of a single binary operation, the term algebra over a set ''X'' of variables is exa ...
*
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 to ...
See also
*
Generating set
In mathematics and physics, the term generator or generating set may refer to any of a number of related concepts. The underlying concept in each case is that of a smaller set of objects, together with a set of operations that can be applied to ...
Notes
{{DEFAULTSORT:Free Object
Mathematics articles needing expert attention
Abstract algebra
Combinatorics on words
Adjoint functors