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. 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^{-1}g=e. Applying these relations to the strings above, one obtains :aebecede = aba^{-1}b^{-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^{-1}a^{-1} = e. Denoting the equivalence relation or
congruence by \sim, 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 :F_2=W(S)/\sim. This is often written as F_2=W(S)/E where W(S) = \{a_1 a_2 \ldots a_n \, \vert \; a_k \in S \, ; \, n \in \mathbb{N}\} is the set of all words, and E = \{a_1 a_2 \ldots a_n \, \vert \; e = a_1 a_2 \ldots a_n \, ; \, a_k \in S \, ; \, n \in \mathbb{N}\} 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.
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 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 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. 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==