Free object

From Wikipedia, the free encyclopedia

In mathematics, the idea of a free object is one of the basics of abstract algebra. It is part of universal algebra, in the sense that it relates to all types of algebraic structure (with finitary operations); but on the other hand it has a clean formulation in terms of category theory (in yet more abstract terms). It is probably better to master some special case such as free groups first.

Starting from a familiar concept in group theory, of defining a group 'by generators and relations', we can say that in general a free object of a certain specific algebraic type will have 'generators and no relations'. If we want to use the method of generators and relations in generality, we split the approach up as

create an object with the generators which are left as general as possible;
impose relations, in the form of an equivalence relation which is a congruence.

Therefore in these terms from universal algebra we need to understand free objects for step 1, and the nature of congruences for step 2.

An example would be free monoids. These are rather simpler than free groups: 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. (See also Kleene star.)

As that example suggests, free objects look like constructions from syntax; and we can 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). An example for that is the way a free magma on X turns out to be the magma of binary trees labelled at the leaves by X. That construction generalises (from a single binary operation to any collection of 'arities') in a way the free object concept makes much more palatable. (See also Herbrand universe.)

In general, the setting for a free object is like this: a category C of algebraic structures (sets plus operations, obeying some laws) has a functor U to Sets, the category of sets and functions, that simply ignores the operations. We call U the forgetful functor. Free objects are created by a left adjoint F to F: for a set X the free object on X as 'generators' is F(X), an object of the category C, together with a C-morphism ε:X→U(F(X). More explicitly, F is (up to isomorphisms in C) characterized by the following universal property:

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ε = f.

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.

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.

For specific kinds of free objects see: