|
In mathematics, the idea of a free object is one of the basic concepts of abstract algebra. It is a part of universal algebra, in the sense that it relates to all types of algebraic structure (with finitary operations). It also has a clean formulation in terms of category theory, although this is in yet more abstract terms. To understand the concept, it is best to master several special cases first, such as free groups, tensor algebras, or free lattices. Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ...
Abstract algebra is the field of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras. ...
Universal algebra (sometimes called General algebra) is the field of mathematics that studies the ideas common to all algebraic structures. ...
In mathematics or logic, a finitary operation is one, like those of arithmetic, that take a number of input values to produce an output. ...
In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them. ...
The Cayley graph of the free group on two generators a and b 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...
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. ...
In mathematics, in the area of order theory, a free lattice is the free object corresponding to a lattice. ...
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 an alphabet. 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. In mathematics, associativity is a property that a binary operation can have. ...
In computer programming and formal language theory, (and other branches of mathematics), a string is an ordered sequence of symbols. ...
For other uses, see Alphabet (disambiguation). ...
In mathematics, an equivalence relation, denoted by an infix ~, is a binary relation on a set X that is reflexive, symmetric, and transitive. ...
In mathematics, given a set X and an equivalence relation ~ on X, the equivalence class of an element a in X is the subset of all elements in X which are equivalent to a: [a] = { x ∈ X | x ~ a } The notion of equivalence classes is useful for constructing sets out...
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 − 1g = e. Applying these relations to the strings above, one obtains This picture illustrates how the hours on a clock form a group under modular addition. ...
- aebecede = aba − 1b − 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 − 1a − 1 = e
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 mathematics and especially in abstract algebra, a congruence relation or simply congruence is an equivalence relation that is compatible with some algebraic operation(s). ...
In mathematics, given a set X and an equivalence relation ~ on X, the equivalence class of an element a in X is the subset of all elements in X which are equivalent to a: [a] = { x ∈ X | x ~ a } The notion of equivalence classes is useful for constructing sets out...
In ring theory, a branch of abstract algebra, an ideal is a special subset of a ring which generalizes important properties of integers. ...
- F2 = W(S) / ˜
This is often written as - F2 = W(S) / E
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 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 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. ...
In computer programming and formal language theory, (and other branches of mathematics), a string is an ordered sequence of symbols. ...
Concatenation is a standard operation in computer programming languages (a subset of formal language theory). ...
In mathematical logic and computer science, the Kleene star (or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. ...
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 parenthesis, which are used to indicate the non-associative groupings of letters. Such a string may be equivalently be represented by a binary tree or a free magma; the leaves of the tree are the letters from the alphabet. In computer science, a binary tree is a tree data structure in which each node has at most two children. ...
In abstract algebra, a magma (also called a groupoid) is a particularly basic kind of algebraic structure. ...
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[1]. The problem of determining if two different strings belong to the same equivalence class is known as the word problem. The mathematical term arity sprang from words like unary, binary, ternary, etc. ...
In mathematics, the concept of a relation is a generalization of 2-place relations, such as the relation of equality, denoted by the sign = in a statement like 5 + 7 = 12, or the relation of order, denoted by the sign < in a statement like 5 < 12. Relations that involve two...
In mathematical logic, for any formal language with a set of symbols (constants and functional symbols), the Herbrand universe recursively defines the set of all terms that can be composed by applying functional composition from the basic symbols. ...
In mathematics, Heyting algebras are special partially ordered sets that constitute a generalization of Boolean algebras. ...
In mathematics and computer science, a word problem for a set S with respect to a system of finite encodings of its elements, is the algorithmic problem of deciding whether two given representatives represent the same element of the set. ...
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). For other uses, see Syntax (disambiguation). ...
Free functor The general setting for a free object is in category theory, where one defines a functor, the free functor, that is the left adjoint to the forgetful functor. In mathematics, category theory deals in an abstract way with mathematical structures and relationships between them. ...
Did somebody just say functor? In category theory, a functor is a special type of mapping between categories. ...
The existence of many pairs of adjoint functors is a major observation of the branch of mathematics known as category theory. ...
A forgetful functor is a type of functor in mathematics. ...
Consider the category C of algebraic structures; these 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. The forgetful functor is very simple: it just ignores all of the operations. In universal algebra, a branch of pure mathematics, an algebraic structure consists of one or more sets closed under one or more operations, satisfying some axioms. ...
A forgetful functor is a type of functor in mathematics. ...
In mathematics, the category of sets is the category whose objects are all sets and whose morphisms are all functions. ...
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 C-morphism  . More explicitly, F is, up to isomorphisms in C, characterized by the following universal property: In various branches of mathematics, certain constructions are frequently defined or characterised by an abstract property which requires the existence of a unique morphism under certain conditions. ...
- 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,  (this abuses notation because X is a set, while F(X) is an algebra; correctly, it is  ).
The natural transformation  is called the counit; together with the unit  , one may construct a T-algebra, and so a monad. This leads to the next topic: free functors exist when C is a monad over Set. In category theory, an abstract branch of mathematics, a natural transformation provides a way of transforming one functor into another while respecting the internal structure (i. ...
In mathematics, coalgebras are structures that are in a certain sense dual to the unital associative algebras. ...
In category theory, a monad or triple is an (endo-)functor, together with two associated natural transformations. ...
In category theory, a monad or triple is a type of functor, together with two associated natural transformations. ...
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. In universal algebra, a variety of algebras is the class of all algebraic structures of a given signature satifying a given set of identities. ...
In universal algebra, a variety of algebras is the class of all algebraic structures of a given signature satisfying a given set of identities. ...
In mathematics, the concept of a relation is a generalization of 2-place relations, such as the relation of equality, denoted by the sign = in a statement like 5 + 7 = 12, or the relation of order, denoted by the sign < in a statement like 5 < 12. Relations that involve two...
In category theory, a monad or triple is a type of functor, together with two associated natural transformations. ...
General case Other types of forgetfulness also give rise to objects quite like free objects: for example the tensor algebra construction on a vector space as left adjoint to the functor on associative algebras that ignores the algebra structure. It is therefore often also called a free 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. ...
In mathematics, a vector space (or linear space) is a collection of objects (called vectors) that, informally speaking, may be scaled and added. ...
In mathematics, an associative algebra is a vector space (or more generally, a module) which also allows the multiplication of vectors in a distributive and associative manner. ...
In abstract algebra, a free algebra is the noncommutative analogue of a polynomial ring. ...
List of free objects Specific kinds of free objects include: In abstract algebra, a magma (also called a groupoid) is a particularly basic kind of algebraic structure. ...
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. ...
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. ...
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. ...
The Cayley graph of the free group on two generators a and b 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...
In abstract algebra, a free abelian group is an abelian group that has a basis in the sense that every element of the group can be written in one and only one way as a finite linear combination of elements of the basis, with integer coefficients. ...
In abstract algebra, a semiring is an algebraic structure, similar to a ring, but without additive inverses. ...
In mathematics, a Kleene algebra (named after Stephen Cole Kleene, pronounced clay-knee) is either of two different things: A bounded distributive lattice with an involution satisfying De Morgans laws, and the inequality x∧−x ≤ y∨−y. ...
In abstract algebra, a free algebra is the noncommutative analogue of a polynomial ring. ...
In mathematics, a free module is a module having a free basis. ...
In abstract algebra, a free algebra is the noncommutative analogue of a polynomial ring. ...
In abstract algebra, a polynomial ring is the set of polynomials in one or more variables with coefficients in a ring. ...
In abstract algebra, a free algebra is the noncommutative analogue of a polynomial ring (which may be regarded as a free commutative algebra). ...
In mathematics, in the area of order theory, a free lattice is the free object corresponding to a lattice. ...
In mathematics, distributive lattices are lattices for which the operations of join and meet distribute over each other. ...
In mathematics, Heyting algebras are special partially ordered sets that constitute a generalization of Boolean algebras. ...
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 operations, and The generators are as independent as possible, in the sense...
Notes - ^ 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)
See also To discuss anything talk on this forum - http://www.talkanything.uni.cc/ In universal algebra, a term algebra is an algebraic structure which is freely generated from a signature specifying the operations of the algebra (including constants, which are nullary operations). ...
|
Feeds |
Contact