In
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 ' ...
. 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 ...
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 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, 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 operatio ...
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 of ...
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 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 of ...
. 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 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
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 ...
, the first step is to consider the collection of all possible
words formed from an
alphabet
An alphabet is a standardized set of basic written 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 character ...
. 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 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 classes 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 elem ...
s. 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 concatena ...
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 tr ...
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 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 eleme ...
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. 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; 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 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, the free functor, that is the
left adjoint to the
forgetful functor.
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 ...
s; the objects can be thought of as sets plus operations, obeying some laws. This category has a functor,
, the
forgetful functor, 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 of ...
. 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 is called the
unit; 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
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'', an ...
.
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, 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 operatio ...
, 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 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 multiplica ...
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 p ...
. 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
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 p ...
**
free associative algebra
**
free commutative algebra
*
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 obje ...
**
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
**
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
*
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
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, and in particular,
vector space
*
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 elem ...
**
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
Notes
{{DEFAULTSORT:Free Object
Mathematics articles needing expert attention
Abstract algebra
Combinatorics on words
Adjoint functors