Free algebraic system

A free object in a certain class of algebraic systems.

Let $ \mathfrak K $ be a non-empty class of algebraic systems (see Algebraic systems, class of). A system $ F $ is called free in the class $ \mathfrak K $, or $ \mathfrak K $- free, if it belongs to $ \mathfrak K $ and has a set $ X $ of generators such that every mapping $ \phi _ {0} : X \rightarrow A $ of $ X $ into any system $ A $ from $ \mathfrak K $ can be extended to a homomorphism $ \phi : F \rightarrow A $. In this case one also says that $ F $ is free over $ X $ in the class $ \mathfrak K $. A set of generators $ X $ with this property is called a $ \mathfrak K $- free base of the system $ F $, and its cardinality is called the rank of $ F $. $ \mathfrak K $- free systems of the same rank are isomorphic. If the class $ \mathfrak K $ has a free system of rank $ r $, then every system from $ \mathfrak K $ that admits a generating set of cardinality at most $ r $ is a homomorphic image of it. A $ \mathfrak K $- free base $ X $ of a $ \mathfrak K $- free system is also a minimal generating set; therefore, if the class $ \mathfrak K $ has isomorphic free systems $ F $ and $ F _ {1} $ of different ranks $ r $ and $ r _ {1} $, then both cardinal numbers $ r $ and $ r _ {1} $ are finite.

A class of algebraic systems is called trivial or degenerate if in each system the identity $ x = y $ is true, that is, if all its systems are one-element systems. Otherwise, the class is called non-trivial or non-degenerate. In any non-degenerate quasi-variety (respectively, variety) of algebraic systems (see Algebraic systems, quasi-variety of; Algebraic systems, variety of) there are free algebraic systems of arbitrary rank. A degenerate class of algebraic systems has only free systems of rank 1.

Suppose that a class $ \mathfrak K $ has free systems $ F _ {l} $ and $ F _ {k} $ of finite ranks $ l $ and $ k $, respectively, and suppose that $ k < l $. The isomorphism $ F _ {k} \simeq F _ {l} $ holds if and only if there are terms

$$ s _ {i} ( x _ {1} \dots x _ {k} ),\ \ i = 1 \dots l, $$

$$ t _ {j} ( x _ {1} \dots x _ {l} ),\ j = 1 \dots k, $$

in the signature of $ \mathfrak K $ such that the following identities are true in $ \mathfrak K $:

$$ s _ {i} ( t _ {1} ( x _ {1} \dots x _ {l} ) \dots t _ {k} ( x _ {1} \dots x _ {l} )) = x _ {i} , $$

$$ t _ {j} ( s _ {1} ( x _ {1} \dots x _ {k} ) \dots s _ {l} ( x _ {1} \dots x _ {k} )) = x _ {j} , $$

where $ i = 1 \dots l $; $ j = 1 \dots k $. If $ \mathfrak K $ contains a finite system $ A $ of cardinality $ \geq 2 $, then $ \mathfrak K $- free systems of different ranks are not isomorphic. In particular, in all varieties of groups, semi-groups, lattices, and associative rings, free systems of different ranks are not isomorphic. On the other hand, in certain varieties of modules (see Free module) all free modules of finite rank are isomorphic.

There are finitely-presented varieties of algebraic systems (see Algebraic system) in which all free algebraic systems of finite rank are isomorphic. An example is the variety $ \mathfrak A _ {1,2} $ of algebras $ \langle A, \phi _ {1} , \phi _ {2} , \omega \rangle $, of type $ \langle 1, 1, 2 \rangle $, defined by the identities

$$ \phi _ {i} ( \omega ( x _ {1} , x _ {2} )) = x _ {i} ,\ \ i = 1, 2, $$

$$ \omega ( \phi _ {1} ( x), \phi _ {2} ( x)) = x. $$

It has been proved (see [3]) that in the varieties $ \mathfrak A _ {m,n} $ $ ( 1 \leq m \leq n) $ of algebras $ \langle A, \phi _ {1} \dots \phi _ {n} , \omega _ {1} \dots \omega _ {m} \rangle $, with $ m $- ary operations $ \phi _ {1} \dots \phi _ {n} $ and $ n $- ary operations $ \omega _ {1} \dots \omega _ {m} $, defined by the identities

$$ \phi _ {i} ( \omega _ {1} ( x _ {1} \dots x _ {n} ) \dots \omega _ {m} ( x _ {1} \dots x _ {n} )) = x _ {i} , $$

$$ \omega _ {j} ( \phi _ {1} ( x _ {1} \dots x _ {m} ) \dots \phi _ {n} ( x _ {1} \dots x _ {m} )) = x _ {j} , $$

$$ i = 1 \dots n; \ j = 1 \dots m, $$

for fixed $ m $ and $ n $, two free algebras of finite rank $ k \neq l $ are isomorphic if and only if

$$ k \equiv l \mathop{\rm mod} ( n - m),\ \ k , l \geq m. $$

There are universal classes that do not have free systems. An example is the class of groups defined by the universal formulas

$$ ( x ^ {2} = 1) \lor \ ( x ^ {3} = 1),\ \ xy = yx $$

(the quantifiers have been omitted). A universal class $ \mathfrak U $ with free systems of arbitrary finite rank has free systems of arbitrary rank.

Let $ \Sigma $ be a consistent set of universal formulas $ G ( x _ {1} \dots x _ {n} ) $ of the form

$$ \neg G _ {1} \lor \dots \lor \ \neg G _ {p} \lor G _ {p + 1 } \lor \dots \lor G _ {q} , $$

where $ G _ {1} \dots G _ {q} $ are atomic formulas of the signature $ \Lambda $. Let

$$ ngG = G _ {1} \& \dots \& G _ {p} . $$

$ \Sigma $ is said to have the $ r $- substitution property $ ( r \geq 1) $ if for any formula $ G ( x _ {1} \dots x _ {n} ) $ from $ \Sigma $ and for any terms

$$ t _ {1} ( x _ {1} \dots x _ {r} ) \dots t _ {n} ( x _ {1} \dots x _ {r} ) $$

in $ r $ variables $ x _ {1} \dots x _ {r} $ the following assertion is true:

$$ \Sigma \vdash \ ( \forall x _ {1} ) \dots ( \forall x _ {r} ) \ ngG ( t _ {1} \dots t _ {n} ) \Rightarrow $$

$$ \Rightarrow \ ( \exists i > p) \ \Sigma \vdash ( \forall x _ {1} ) \dots ( \forall x _ {r} ) G _ {i} ( t _ {i} \dots t _ {n} ). $$

In a non-degenerate universal class $ [ \Sigma ] $ defined by a set $ \Sigma $ of universal formulas there is a free system of finite rank $ r \geq 1 $ if and only if $ \Sigma $ has the $ r $- substitution property [4]. In particular, if all the formulas in $ \Sigma $ are irreducible and $ \Sigma $ contains a positive formula

$$ ( \forall x _ {1} ) \dots ( \forall x _ {r} ) \ G _ {1} \lor \dots \lor G _ {q} $$

with $ q \geq 2 $ disjoint members, then the universal class $ [ \Sigma ] $ does not have free systems of rank $ n \geq r $. For example, the class of totally ordered groups in the signature $ \langle \leq , \cdot , {} ^ {-} 1 \rangle $ does not have free algebraic systems of rank $ r \geq 2 $.

References

[1]	A.I. Mal'tsev, "Algebraic systems" , Springer (1973) (Translated from Russian)
[2]	B. Jónsson, A. Tarski, "On two properties of free algebras" Math. Scand. , 9 (1961) pp. 95–101
[3]	S. Swierczkowski, "On isomorphic free algebras" Fund. Math. , 50 : 1 (1961) pp. 35–44
[4]	G. Grätzer, "On the existence of free structures over universal classes" Math. Nachr. , 36 : 3–4 (1968) pp. 135–140

Comments

The term free algebra is often used in place of "free algebraic system" , particularly if the signature of the class under consideration involves only operation-symbols. Clearly, every element of a free algebra with base $ X $ can be written as a word over the alphabet $ X $ in the signature of the free class under consideration; an important problem (the word problem) for free algebras is to find an algorithm for determining when two words are equal as elements of the free algebra. In some varieties of algebras (e.g. semi-groups, modules over a fixed ring, associative algebras) this problem has a trivial solution; in others (e.g. Lie algebras, lattices, Boolean algebras) the solution is known but non-trivial, and in yet others (e.g. alternative rings, modular lattices), it is known that no such algorithm exists. For more details of particular cases, see the entries Free Abelian group; Free algebra over a ring; Free associative algebra; Free Boolean algebra; Free group; Free groupoid; Free lattice; Free module; Free semi-group.

References

[a1]	P.M. Cohn, "Universal algebra" , Reidel (1981)