Let us consider the subgroups of a given group 
. It may happen that some of them, say 
1, 2, …, r generate the full group. We are interested in knowing to what extent the structure of is determined by the structure of the generating subgroups 1, 2, …r With this in mind, we make the following definition:
A semi-group 
with a unit element 1 is called a product over the system H of semi-groups with unit element if for each semigroup contained in H there is given a homomorphism σ of into such that σ(1) = 1 and is generated by all the images σ (h) with running over H and h running over the elements of the semi-group of H.
A homomorphic mapping Θ of one product over H, say , onto another such product, say 
, is called a homomorphism over H if Θσ(h) = 
(h) for any element h of the semi-group running over H. Here, of course, denotes the homomorphism corresponding to σ in the definition of as a product over H. It is clear that there can be at most one homomorphism over H between any two given products over H, since every element xof can be written as
where hi belongs to the semi-group i of H for i = 1, 2, . . ., r, and thus
The relation ‘homomorph over H’ is reflexive and transitive, but not symmetric. In fact, the identity mapping provides an isomorphism over H for any product over H. If Θ1 is a homomorphism over H of the product 1 onto the product 2 over H and if Θ2 is a homomorphism over H of the product 2 onto the product 3 over H, then Θ2Θ1 is a homomorphism over H of 1 onto 3. The group of one element together with the set of mappings of each element h of each member of H onto the unit element provides the trivial product over H. For every product over H we obtain a homomorphism over H onto the trivial product over H by mapping each element onto the unity element. But there is no converse homomorphism over H unless both products over H are trivial. More generally, two products over H are mutually homomorphic over H if and only if they are isomorphic over H in one direction.
DEFINITION: A product over H is called a free product over H if it can be mapped homomorphically over H onto any product over H.
It is immediate that two free products over H are isomorphic over H. There always is a free product over H. As a first step in constructing a free product over H, we denote by 
(H) the system of all ‘words’ over H, i. e. all expressions h1h2 · · · hr—denoted for brevity by W—where the length r ranges over all the natural numbers and the letters hi of the word W denote any element of any semi-group i belonging to H. Furthermore, we denote by Z the empty word, which has no letters and which, by definition, is the only word of length 0. Two words are called equal if they are of equal length and if corresponding letters denote equal elements of equal semi-groups. This notion of equality has the usual three properties.
Two words W1, W2 are multiplied by juxtaposition, e. g., for W1 = h1h2 · · · hr, W2 = hr+1hr+2 · · · hr+s we define the product by W1W2 = h1h2 … hr+s; in particular, ZW = WZ = W for any word W.
It is important to note that the product of a word of length r and a word of length s is uniquely defined as a word of length r + s.
From the definition it is clear that the associative law of multiplication holds. Thus the words over H form a semi-group (H), with the empty word as unit element.
In a word W = h1h2 · · · hr, it may happen
1. in case i = i+1 that the product h′ of the two elements hi, hi+1 is defined within the semi-group i, or
2. that hi = 1i.
In the first case, we replace the two letters concerned by h′; in the second case, we simply omit 1i . Either process will be called a reduction, and we will write
Case 1: W = · · · hihi+1 · · · → W′ = · · · h′ · · ·,
Case 2: W = · · · 1i.· · · → W′ = ……,
where the dots always refer to unaltered letters.
The reverse process we will call an anti-reduction. Both processes are referred to as elementary transformations. Writing W → W′ if the word W′ is obtained by a reduction from the word W, we establish a binary relation in the set (H) of words over H. The normalized relation is the congruencerelation between words, defined as follows:
if there is a chain of words W = W0, W1, …, Ws = W′ such that for each index i = 0, 1, 2, … s — 1 either Wi = Wi+1 or Wi → Wi+1 or Wi+1 → Wi. This congruence relation is normal and multiplicative. In fact, the normality follows from the definition as normalized relation (see Chap. I, Ex. 17). The substitution law of multiplication follows by repeated application of the following statement:
which can be verified directly without any difficulty.
We denote the class of words congruent to the word W by |W|. The factor semi-group 
of (H) over the normal multiplicative relation defined above (for its definition, see Chap. II, Ex. 12) formed by the classes of congruent words that are multiplied by multiplication of the representatives, is a product over H. The correspondence of the element h of the member of H with the class |h| represented by the one-letter word h, in fact, defines a homomorphism of the semi-group into , since for hh′ = h" in it follows that hh′ → h" in (H) and hence |hh′| = |h" |, |h| · |h′| = |h"|. Furthermore, for each word W = h1h2…hr of positive length we have |W| = |h1| · |h2| · |h3| · · · |hr|. Finally, the empty word Z is congruent to each of the words 1, being any member of H, so that |Z| = |1|. Hence the totality of the homomorphic images of in H generates .
The product over H is free. To see this, let the semi-group with unit element be an arbitrary product over H for which the given homomorphism of each semi-group contained in H into is σ. Note that σ(1) = 1. Furthermore, the semi-group is generated by the sub-semigroups σ(), with a member of H. Let us construct the homomorphism θ of onto over H which maps the class |h1h2 · · · hr| onto σ1(h1)σ2 · · · σr (hr)) and |Z| onto 1. This mapping is unique, since if
then
and if
then
The preservation of multiplication follows from considering two words W1 = h1h2 · · · hr and W2 = hr+1 · · · hr+s. We have
We denote the free product over H, as constructed in the preceding, by
or, more briefly, by
If H consists of finitely many semi-groups 1, 2, · · ·, r, then we also write 1 * 2 * … * r for the free product. It is independent of the order of the factors, and it is associative.
For many applications it is necessary to solve the word problem for a given product, that is, to determine a general procedure by which it can be decided in a finite number N of computational steps whether two given words W1, W2 interpreted as elements of the product are equal. This is understood to imply that the number N be not greater than a certain recursive function that depends only on the length of W1 and W2; we speak in that case of an effective solution of the word problem.
It has been shown that an effective solution of the word problem does not always exist. However, in free products we can solve it quite easily. For the most elegant solution, see Ex. 1, Appendix D. A method of solution that lends itself to other applications will now be given.
We call a word irreducible if no reduction can be made. Since any reduction diminishes the length by 1, it follows that every word of length r can be reduced to an irreducible word by at most r reductions.
LEMMA: If W → W1, W → W2, W1 
W2, then there is a word W3such that W1→ W3,W2 → W3.
Proof: a) If no unit elements are eliminated, then we distinguish two cases.
Set W3 = …h′ … h" ···.
Thus the semi-groups i, i+1, i+2 coincide, and within i the equations hihi+1 = h′, hi+1hi+2 = h′′, h′h′′ = h hold. Set W3= · · · h · · ·.
b) In the event that unit elements are to be eliminated, we have
Set W3 = · · · h′ · · ·.
Set W3 = ........
Note that there is no loss of generality in considering the particular orders we have selected and that in each case W1 → W3, W2 → W3.
On the basis of the preceding observations, let us investigate the problem of reduction in general.
To every binary relation a → b in a set S there belongs a poset, where a ≥ b signifies the fact that there is a chain a = a0, a1, …, ar = b of length r ≥ 0 Linking a and b such that either (i) r = 0 and a = b or (ii) r > 0 and a0 → a1, a1 → a2, …, ar-1 → ar.
That the ≥ relation is reflexive and transitive is immediate. Also, if a → b, then a ≥ b. The two relations coincide if and only if the relation → is itself reflexive and transitive.
An element x of a ≥ poset is called minimal if x ≥ y implies y ≥ x. Any element equivalent to a minimal element is itself minimal.
An element of a set S is called irreducible with respect to a given binary relation a → b if it is minimal in the corresponding poset.
A chain of elements a = a0, a1, …, ar = b of S leading from a to b such that b is irreducible and either r = 0 and a = b or r > 0, a0 → a1, …, ar-1 → ar is called a complete reduction of a to its result b. The element a is called completely reducible if there is a complete reduction of a. Every irreducible element, for example, is completely reducible.
As another example, in our special case of the set of all words over a system of semi-groups with unit element, every word is completely reducible. A word is irreducible if and only if it has no unit letter and adjacent letters belong to different semi-groups.
A set with reduction is defined as a set S with a binary relation a → b, where:
1. The poset belonging to the relation → satisfies the minimal condition: In any monotonie decreasing sequence α1 ≥ a2 ≥ a3 ≥ · · · there is an index n for which all members an, an+1, an+2, … of the sequence from the n-th member on are equivalent;
2. (Birkhoff condition.) If a → b, a → c, then there is an element d such that b ≥ d, c ≥ d.
For example, the set of all words over a system of semi-groups with unit element in which the → relation is defined as above is a set with reduction.
For such sets we have the
PRINCIPLE OF REDUCTION: Every element is completely reducible, and the result of a complete reduction is uniquely determined up to equivalence.
Proof of the Principle of Reduction: Owing to the minimal condition for each element a, there is an irreducible element b satisfying a ≥ b which can be obtained by a complete reduction from a.
It is convenient to write a > b in place of ‘a ≥ b but not b ≥ a’. This relation is transitive, but not reflexive.
We form the subset S′ of S which consists of all the elements p of S having the property that p ≥ x, p ≥ y in S implies the existence of an element z of S satisfying x ≥ z, y ≥ z. All irreducible elements of S, for example, belong to S′. If x, y are the results of two complete reductions of the element p of S′, then it follows that there is an element z in S satisfying x ≥ z, y ≥ z, and since both x and y are irreducible, we find that xis equivalent to z, z equivalent to y, and thus x equivalent to z. Hence for each element of S′ the result of a complete reduction is uniquely determined up to equivalence. We now wish to show that the difference set S — S′ is empty.
If a is in S but not in S′, then there are two elements x, y of S such that a ≥ x, a ≥ y, and for any element z of S satisfying x ≥ z we never have y ≥ z. Since y ≥ y, it follows that x ≥ y cannot hold. Hence x ≥ a cannot hold, and thus a > x. Similarly, a > y. There are chains a = a0 → a1 → → ··· → ar = x, a = b0 → b1 → … → bs = y and indices i, j satisfying 0 ≤ i < r, 0 ≤ j < s such that (i) a0, a1, …, ai are equivalent, but ai > ai+1 (ii) b0, b1, …, bj are equivalent, but bj > bj+1. Hence a > ai+1, a > bj+1. Using the Birkhoff condition, we deduce from ai → ai+1, ai equivalent to bj, and bj → bj+1 the existence of an element z of S satisfying ai+1 ≥ z, bj+1 ≥ z. Let 
be the result of a complete reduction of z, and similarly let 
and 
be the result of a complete reduction of x and y respectively. Since ai+1 ≥ x, it follows that also is the result of a complete reduction of ai+1. Similarly, we deduce from ai+l ≥ z that z is the result of a complete reduction of ai+1.
Now, either ai+1 does not belong to S′, in which case we set a′ = ai+1, or ai+1 belongs to S′, in which case the elements , , being the results of complete reductions of ai+1, must be equivalent. From x ≥ , equivalent to we have x ≥ , and hence y ≥ does not hold. Using the same argument applied to y, bj+1 instead of x, ai+1, we come to the conclusion that bj+1 does not belong to S′. In this case we set a′ = bj+1.
At any rate, for every element a of S not belonging to S′ there is a successor a′ satisfying a > a′ and not belonging to S′. Since repetition of this construction leads to a strictly monotonically decreasing sequence, we find a contradiction with the minimal condition; and hence every element of S belongs to S′, Q. E. D.
For a partial converse of the principle of reduction see Ex. 2 of Appendix D.
COROLLARY TO THE PRINCIPLE OF REDUCTION: The normalized relation of the relation → on a set with redaction is the relation:
‘a ≡ b if the complete reduction of a, b leads to equivalent results.’
Proof: If a ≡ b, then there are full reductions a = a0 → a1 → ··· → ar,b = b0 → b1 → ··· → bs such that ar, bs are equivalent irreducible elements. Hence there is a chain ar → ar+1 → ··· → ai = bs. But from a → a 1→ … a1, b → b1 → ··· → bs-1 → ai it follows that a, b satisfy the normalized relation of the relation Conversely, if a, b satisfy the normalized relation of the relation →, then there is a chain a = a0, a1, …, ar = b such that either ai = ai+1 or → ai+1 or ai+1 → ai for i = 0, 1, 2, …, r — 1. At any rate, complete reduction of and ai+1 leads to equivalent results. Hence complete reduction of a and b also leads to equivalent results.
Applying these concepts and conclusions to the relation → previously studied, we find that poset equivalence of two words is the same as their equality and that, furthermore, the words form a set with reduction. The reduction principle yields: Each word over a system H of semi-groups with unit element is congruent to the uniquely determined result of any complete reduction of the given word. The free product over H may be formed by taking the set of all irreducible words in which the combination of two irreducible words to a third irreducible word is obtained by juxtaposition followed by complete reduction.
It quite often happens that a product over H is required to satisfy a system 
of relations between the generating elements of the form
where hi is contained in a member i of H and i runs from 1 to s. We call a semi-group a product over H defined by the system of defining relations if:
1. is a product over H, i. e., to each member of H there is assigned a homomorphism σ of into , mapping 1 onto 1, such that is generated by the sub-semigroups σ(), with running over H,
2. each relation (1) holds in , i. e., in there hold all of the equations
3. is homomorphic over H with every product over H having the properties 1 and 2.
A product over H defined by can be constructed as follows. Two words are called congruent modulo if one word can be obtained from the other word by a combination of
1. a finite number of elementary transformations,
2. a finite number of replacements of W1h1h2 ··· hrW2 by W1hr+1 ··· hsW 2or of W1hr+1 ··· hsW2 by W1h1 ··· hrW2, in accordance with the relations comprising .
This congruence relation is normal and multiplicative, and hence the residue classes form a semi-group (H)/. Denoting by W() the residue class represented by the word W, we find that the correspondence between h and σ(h) = h() defines a homomorphism of the element h of the member of H onto a sub-semigroup () of (H)/ such that σ(1) = Z() is the unit element of (H)/ and such that for each relation (1) we have
Hence (H)/ is a product over H satisfying the relations comprising .
Now let be another product over H satisfying the relations comprising ; that is, the mapping of any word W onto 
defines a homomorphism of (H) onto for which 1= 2 whenever W1 is congruent to W2 modulo . From this definition, which is equivalent to the statement that is a product over H satisfying the relations , it follows that the mapping of W() onto defines a homomorphism over H of (H)/ onto . This shows that (H)/ is a product over H defined by . It is clear that any two products over H defined by are isomorphic over H.
Let us study some examples.
1. is empty. Then (H)/ is the free product over H.
2. consists of relations of the type h = h′, with h, h′ contained in the same member of H.
The subset of all relations in pertaining to one member of H defines a factor semi-group of /. We now show that the free product of all factor semi-groups / is a product over H defined by . For ai contained in the member i of H (i = 1, 2, … t) the correspondence between a1(1)a2(2) …ai (t) and ā1ā2 … ār defines a homomorphism of over H onto each product over H defined by , and certainly all the relations in are satisfied in .
3. consists of all relations
with h, h′ belonging to different members of H. Often the permutability of any two elements x, y of a multiplicative domain expressed by the equation xy = yx is also denoted by x ↔ y. Thus in our case we have the defining relations
for any pair of elements belonging to different members of H. The product over H defined by elementwise permutability of different factors is called the direct product over H and is denoted by 
or, more concisely, by 
H . The direct product can be constructed by taking the semi-group of all functions f defined on H with the properties
a) f() is an element of ;
b) f() = l for all but a finite number of members of H;
c) fg() = f()g().
It is easy to verify that is a semi-group and that the correspondence between the element h of the member of H and the function 
on H which assumes the value h on , but the value 1, on all members of Hother than , defines a homomorphism of onto a sub-semigroup of such that appears as a product over H satisfying all relations in . On the other hand, given any word W, we can form its -component by taking the product in of all the letters of W belonging to . If no letter belonging to occurs, then the -component is defined to be 1. The -component remains unchanged under all elementary transformations and all substitutions derived from one of the relations in . Also, after imposing an order on each word over H is congruent modulo to the word made up from the -components different from the unit element, with the ’s concerned following in the same order as they occur in the ordering imposed on H We may call the word thus constructed the direct normal form of the given word. It is uniquely determined by the given word. Two words are congruent modulo if and only if they have the same direct normal form, that is, if they coincide in each component. Of course, all but a finite number of the -components are equal to 1. There are no other restrictions. The -component of a product of two words is equal to the product of the -components of the factors. Hence there is the homomorphic mapping of onto (H)/ over H which maps the function f onto the residue class characterized by having its -component equal to f(), with running over H. This shows that is a direct product over . We verify easily that the new definition of the direct product coincides with the one given in § 1 in the case of a finite number of direct factors.
4. If every member of H is a group, then every product over H is a group. The inverse element of h1h2 ··· hr is the element 
. The word 
is called the inverse word of the word W = h1h2 ··· hr. The inverse word of the empty word is the empty word. It holds true that 
. By elementary transformations the word W W-1 can be carried over into the empty word, for any given word W.
The product over H, a system of groups, defined by a system of relations can be obtained as the factor group of the free product = 
over the normal subgroup () generated by all quotients (5)
derived from (1). The elements of this normal subgroup are often called the consequence relations of . This name is chosen because, as a consequence of (1), in any product over H in which all of the relations (1) hold, all of the consequence relations become 1. A consequence relation may be characterized as an element of the free product over H which is of the form 
with ai either 1 or —1, Ri one of the quotients (5) derived from (1), and Wi an arbitrary element of . But since elementary transformations do change the appearance of the elements of F, even though they do not change the elements themselves, it is often extremely difficult to recognize a given element of F as a consequence relation of a given system of defining relations.
5. If each member of H is an infinite cyclic group, say the group generated by the element x, then the free product over H is called the free group with generators x. Its elements can be uniquely represented by expressions 
member of H where i is different from i+1 if i < r; i = 1, 2, …, r; r = 0, 1, 2, …), and the product of two such expressions is formed by juxtaposition and the subsequent cancelling of adjacent factors as often as possible, e. g.
6. The group given by generators S1, S2, …, Ss and defining relations Ri(S1, S2, … Ss = 1 (i = 1, 2, …, r) is obtained as the factor group of the free group with the generators S1, S2, …, Ss over the normal subgroup generated by the r elements Ri(S1, S2, …, Ss). A correspondence between the generators of and some elements 
of another group which maps Si onto S′i, can be extended to a homomorphism of onto if and only if 
for i = 1, 2, …, r.
The problem of determining a method whereby it can be effectively recognized whether a group generated by finitely many generators Sl, S2, …, Ss satisfying the finitely many defining relations
is isomorphic to another group generated by the finitely many elements U1, U2, …, Uu and satisfying the finitely many defining relations
is called the isomorphism problem.
A necessary and sufficient condition that be isomorphic to 
is the existence of some words W1, W2, …, Wu in S1, S2, …, Ss and X1, X2, …, Xs in U1, U2, …, Uu such that the words
and the words
are consequence relations of the relations (6). In the special case s = u, Si = Uí (i = 1, 2, … s) and Wi = Si, Xj = Uj, we call (6) and (7) equivalent systems of defining relations if each relation of one system is a consequence relation of the other system, i. e., if they define isomorphic groups with the same set of generators.
For free groups the isomorphism problem is easily solved. Two free groups with the same number of generators are isomorphic. Furthermore, for a free group of s generators S1, S2, …, Ss the index of the subgroup by all squares is 2s, the representatives of the cosets being the elements 
with ai either 0 or 1 for i = 1, 2, . . ., s. For isomorphic groups the index over the subgroup generated by the squares must be the same; hence if is isomorphic with a free group of u generators, then 2s = 2u if s is finite, and s = u if s is infinite. At any rate, s = u.
7. The factor commutator group of a group generated by the elements S1, S2, …, Ss with the defining relations (6) is obtained by including among the defining relations the additional relations
Proof: Denote by s the free group generated by S1 S2, …, Ss, and let be the normal subgroup formed by the consequence relations of (6); then is isomorphic to s/; hence /D is isomorphic to (s/)/D(/) = (s/)/(Ds/); and hence /D is also isomorphic to the factor group of over the normal subgroup · Ds consisting of the consequence relations of (6) and (8).
We may find an equivalent system of defining relations for /D by permuting the order of the letters in each relation so that the letters are ordered lexicographically; let the group n, for example, be generated by A1, A2, …, An-1 subject to the defining relations
Then n/Dn is generated by A1, A2, …, An-1 subject to the defining relations
which are equivalent to
Hence the generators A2, A3, …, An-1 can be eliminated, and n/Dnis generated by A1, subject to the defining relation 
, giving n: Dn = 2.
8. To give another example of the reduction principle, let H be the system of the n — 1 infinite cyclic groups (A1), (A2), …, (An-1) Define a reduction R in (H) as follows:
We easily prove that (H) is a set with reduction R. In the corresponding poset, equivalence is equality. For example, if
and
then we have
For every word a1a2 ··· ar that is irreducible with respect to R, each section ai ai+1 ··· aj is also irreducible with respect to R. The letter An-1 occurs at most once. If it occurs, then the section beginning with An-1 and terminating with ar is one of the words An-1, An-1 An-2, An-1An-2, An-3, … An-1An-2 ··· A1. Conversely, if An-1 does not occur in the given R-irreducible word, then any of the above n — 1 expressions may be affixed to the given word to give another irreducible word. By induction on n, the number of R-irreducible words turns out to be 1 · 2 ·… · n = n!. The normalized relation of the relation R is normal and multiplicative. The corresponding factor group is the group n occurring in 7. It has the order n!.
Since the mapping of Ai onto the transposition (i, i + 1) of the n digits 1, 2, …, n, which is defined for i = 1, 2, … n — 1, preserves the defining relations of n, it follows that the mapping can be extended to a homomorphism of n onto n. But since the order of n is finite and coincides with the order of the symmetric permutation group of n digits n, it follows that n is isomorphic with n, where we made use of the fact that the transpositions (1, 2), (2, 3), …, (n — 1, n) generate n. Moreover a set of defining relations for the generators Ai = (i, i + 1)(i = 1, 2, …, n — 1) is given by (9).
