# What are Free Objects?

I've read the wikipedia article, but couldn't grasp the concept. Is there an informal definition?

Are there examples of uses of free objects in calculus?

Are free objects somehow connected to constructiveness? Maybe there are some computer program examples (in Haskell preferably).

A reference to a short introductory text is welcome.

-
The informal idea is that a free object, $A$, has a subobject called a basis, $X$. Any map $X\rightarrow B$ determines a unique map $A\rightarrow B$ that extends the map on the basis. An example is a vector space over a field and a basis for that vector space. –  Joe Johnson 126 Apr 13 '12 at 18:03
And, I might add, one doesn't see a whole lot of applications of the notion of free object in calculus. It really belongs in abstract algebra. –  Harald Hanche-Olsen Apr 13 '12 at 18:36
I would like to note on Joe Johnson's post that the map $X \rightarrow B$ is a set map, not necessarily a homomorphism in the category $B$ lives in. –  John Stalfos Apr 13 '12 at 19:10
@JoeJohnson126 And what about $A \to B \Rightarrow X \to B \;\;$ ? In vector spaces each linear map determines a unique map on basis. What is the analogue of a linear map in the case of free objects? –  Yrogirg Apr 13 '12 at 19:12
@Yrogirg: In vector spaces, every object is a free object. But you are still going in the wrong direction. In any concrete category, given any object $A$ and any subset $S$ of the underlying set of $A$, a map $A\to B$ induces a unique set-theoretic map from $S$ into the underlying set of $B$ by restriction. –  Arturo Magidin Apr 13 '12 at 19:31

I'll just add some consideration which I think complete plm answer and try to explaining wikipedia definition of free objects.

Free objects are structures (of some type, they can be groups, monoids, vector spaces, algebras or other kind of things) which have a special subset of generators, called the free generators of the structure. Because the definition of generation depend on the type of structure we are considering, i.e. the category we are working with, also the property of being a free object is related to the category we are considering: for instance $\mathbb Z^2$ is a free abelian group but it isn't a free group.

In the algebraic context there's always an explicit way to describe such structures, namely as the quotient of the term algebras (for the given signature of your algebraic structure) by the relations/equations that the structure should satisfy.

Term algebras over a given set $S$ are simply symbolic combinations, i.e. strings, of elements of $S$ and some special symbols (called operation's symbols) build up according to some rules [of some grammar]. Free algebras are obtained simply identifying in term algebras some strings according to the relations that we want out structure satisfy. Clearly term algebras are free objects to, they are free objects in the category of those algebras having some type of operations which doesn't satisfy any equations.

The real cool feature of free objects is that given a set of free generators, we can extend (in a unique way) every map from the set of free generators to another structure (of the same type) to a morphism from the free object to the said structure. So to build up homomorphisms from free objects to other structures we just need to decide where to send the free generators. That's the cool property the we always use in a theoretical context when dealing for instance with vector spaces, where to provide linear homomorphisms instead of providing an explicit function between vector spaces we simply provide a function from a basis of one vector space to (the underling set of) a vector space.

This property is the definition of free objects, I suppose that the problems you've found are due to the use of the categorical language, which is the right formalism in which express properties of this type.

I hope this answer help in clarifying wikipedia's definition of free object.

-
Are things that expressible via algebraic data types in Haskell free objects? That is we specify constructors for a data type and then define a function on this type by pattern matching against this constructors. So this constructors are generators. See for example en.wikipedia.org/wiki/Algebraic_data_types –  Yrogirg Apr 15 '12 at 15:45
@Yrogirg I think I'm imagining what you're thinking of but I have to ask you to rephrase you question, because in this form it's ill-posed: to talk about free objects you have to specify the categories your working with and a functor between these categories, otherwise talking of free object doesn't make sense. –  Giorgio Mossa Apr 15 '12 at 21:08
What about the usual Haskell category? (en.wikibooks.org/wiki/Haskell/…) Types are objects, functions are morphisms. Functors are certain type constructors. Well, I've encountered the notion of a free object in "Lectures on constructive functional programming" (cs.ox.ac.uk/files/3390/PRG69.pdf). It is said that List of SomeType ([SomeType],++,[]) is a free monoid, but it doesn't go into details what are free objects. Maybe I shall start another question about free objects in Haskell? –  Yrogirg Apr 16 '12 at 6:34
As you pointed out lists are free monoids, meaing that they are free objects in the category of monoids. The categories involved in this case are Set, the category of sets and functions between them (or in Haskell case the category Hask) and Mon the category of monoids, the functor is the forgetful functor which sends every monoid in is underlining set/type. –  Giorgio Mossa Apr 16 '12 at 8:23
@Yrogirg About the Haskell category Hask, there's a more general fact, for every category $\mathbf C$ every object $c \in \mathbf C$ is a free object for the identity functor $1_\mathbf{C}$. So clearly every type is a free object in the category of haskell types, by the way I don't think this kind of free objects are interesting. If you like we could talk about this in a chat, let me know. Meanwhile I'll try to read the pdf you've linked. –  Giorgio Mossa Apr 16 '12 at 8:44

The free objects you will encounter most often are free abelian groups (e.g $\mathbb Z^n$), free modules (e.g. vector spaces, say $\mathbb R^n$), free commutative algebras (polynomial rings, say $\mathbb C[X]$), free groups ($\mathbb Z$ again, on 1 generator, but on 2 and more generators you lose commutativity, elements are words in the generators).

The idea is building the simplest set with a desired algebraic structure from your chosen generators. For instance the simplest group from "$a$" is $\{a^n|\ n=...,-1,0,1,2,...\}$, which is abelian.

The wikipedia general definition of a free object is interesting but rather from the point of view of an algebraist, or category-theorist, it is fundamental in understanding algebraic theories as monads. It is really part of universal algebra, a subject with relatively few applications, though it is good to know it exists.

Also, I think there is an error in the wiki article, free objects are not analogues of bases of vector spaces, it is the generating sets of free objects that are.

Actually, from the wiki article: "let X be a set (called basis)" and later "A is the free object on X".

As Harald, I wonder why you mention calculus. It may be interesting to find contrived examples of free objects in calculus. First you would have to find categories in calculus.

EDIT: I should have stressed that the word "free" comes from "having no relation of dependence" -think "linear dependence" for example. This applies to the elements of your object. For instance, in a free abelian group you do not have any equality other than $xy=yx$ and those derived from this -$xyx=x^2y$, etc. (I cheat because you also have the associativity condition, $x(yz)=(xy)z$, the equality for 1, $1x=x$, and inverses, $xx^{-1}=1$, i.e. the group axioms.)

-
I would consider the free monoid to be another important example. The free monoid on a set $S$ is the set of finite ordered lists of elements of $S$, with list concatenation as the monoid operation. If $\Sigma$ is an alphabet of symbols, the free monoid on $\Sigma$ is the set $\Sigma^*$ of strings over $\Sigma$. This example is ubiquitous in programming language theory. –  MJD Apr 13 '12 at 19:34
Thanks, it's true that they are important in computer science. They are close to free groups, their "positive exponent" part. And actually I should have said "elements are words in the generators and their inverses with appropriate cancellation, e.g. $aa^{-1}=1$". –  plm Apr 13 '12 at 22:00