View source for Free algebraic system

<!--
f0415101.png
$#A+1 = 105 n = 0
$#C+1 = 105 : ~/encyclopedia/old_files/data/F041/F.0401510 Free algebraic system
Automatically converted into TeX, above some diagnostics.
Please remove this comment and the {{TEX|auto}} line below,
if TeX found to be correct.
-->

{{TEX|auto}}
{{TEX|done}}

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|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, quasi-variety of]]; [[Algebraic systems, 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|Free module]]) all free modules of finite rank are isomorphic.

There are finitely-presented varieties of algebraic systems (see [[Algebraic system|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 [[#References|[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 [[#References|[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====
<table>
<TR><TD valign="top">[1]</TD> <TD valign="top">  A.I. Mal'tsev,   "Algebraic systems" , Springer  (1973)  (Translated from Russian)</TD></TR>
<TR><TD valign="top">[2]</TD> <TD valign="top">  B. Jónsson,   A. Tarski,   "On two properties of free algebras"  ''Math. Scand.'' , '''9'''  (1961)  pp. 95–101 {{ZBL|0111.02002}}</TD></TR>
<TR><TD valign="top">[3]</TD> <TD valign="top">  S. Swierczkowski,   "On isomorphic free algebras"  ''Fund. Math.'' , '''50''' :  1  (1961)  pp. 35–44</TD></TR>
<TR><TD valign="top">[4]</TD> <TD valign="top">  G. Grätzer,   "On the existence of free structures over universal classes"  ''Math. Nachr.'' , '''36''' :  3–4  (1968)  pp. 135–140</TD></TR>
</table>

====Comments====
The term [[Free algebra|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|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|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 Abelian group]]; [[Free algebra over a ring|Free algebra over a ring]]; [[Free associative algebra|Free associative algebra]]; [[Free Boolean algebra|Free Boolean algebra]]; [[Free group|Free group]]; [[Free groupoid|Free groupoid]]; [[Free lattice|Free lattice]]; [[Free module|Free module]]; [[Free semi-group|Free semi-group]].

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  P.M. Cohn,   "Universal algebra" , Reidel  (1981)</TD></TR></table>