Algebraic system
A set with operations and relations defined on it. An algebraic system is one of the basic mathematical concepts and its general theory has been developed in depth. This was done in the 1950s, and the work took place on the interface between algebra and mathematical logic.
Fundamental concepts.
An algebraic system is an object 
consisting of a non-empty set 
, a family 
of algebraic operations (cf. Algebraic operation) 
(
) and a family 
of relations (cf. Relation) 
(
) defined on 
. The indices 
of the Cartesian powers of 
under consideration are assumed to be non-negative integers and are said to be the arities of the respective operations and relations. The set 
is called the carrier or the underlying set of the algebraic system 
, while its elements are called the elements of this system. The cardinality 
of 
is said to be the cardinality or order of the algebraic system 
. The image 
of the element 
under the mapping 
is called the value of the operation 
at the point 
. Similarly, if 
, then one says that the elements 
of 
are in relation 
, and one writes 
. The operations 
(
) and the relations 
(
), unlike other operations and relations that may be defined on 
, are called basic or primitive.
The pair of families 
is called the type of the algebraic system 
. Two algebraic systems 
have the same type if 
, 
and 
, 
for all 
, 
. Basic operations 
, 
and basic relations 
, 
of two algebraic systems 
, 
of the same type, with identical indices in 
, 
respectively, are called similar.
An algebraic system 
is called finite if the set 
is finite and it is called of finite type if the set 
is finite. An algebraic system 
of finite type is written as 
.
An algebraic system 
is called a universal algebra or an algebra if the set 
of its basic relations is empty, and it is called a model (in logic) or a relational system if the set 
of basic operations is empty. Classical algebraic systems are groups, rings, linear spaces, linear algebras, totally ordered sets, totally ordered groups, lattices, etc.
A non-empty subset 
of the underlying set 
of an algebraic system 
is called closed if for any elements 
of 
the value 
of each basic operation 
also belongs to 
. By considering the operations of 
and the relations of 
on a closed subset 
, one obtains an algebraic system 
which is of the same type as the given algebraic system and is called a subsystem of the algebraic system 
. Subsystems of algebras are called subalgebras, while subsystems of models are called submodels. The concept of a subalgebra strongly depends on the set of basic operations of the algebra under consideration. Thus, a groupoid 
is an algebra of type 
, i.e. an algebra with one basic operation 
. A groupoid 
with a distinguished unit 
is an algebra of type 
, the distinguished element of which has the property 
for all 
with respect to the basic operation 
. For this reason any subgroupoid of a groupoid 
with a distinguished unit 
contains 
, while a subgroupoid of a groupoid 
does not necessarily contain 
. Unlike algebras, any non-empty subset of a model may be considered as a submodel.
An algebraic system 
is isomorphic to an algebraic system 
of the same type if there exists a one-to-one mapping 
of the set 
into the set 
such that
 | (1) |
 | (2) |
holds for all 
of 
and for all 
, 
. A mapping 
possessing these properties is called an isomorphism.
In the following, a class of algebraic systems will be understood to mean only an abstract class, i.e. a class of algebraic systems of the same type which, whenever it contains a system 
, also contains all systems isomorphic to 
. In considering a class 
of algebraic systems, all systems in this class are usually written in a definite signature, as follows. Let the type of the class 
be 
. To each 
is assigned some symbol 
, called a functional, while to each 
is assigned a symbol 
, called a predicate. If an algebraic system 
belongs to the class 
and if 
is a basic operation in it, then the element 
of 
is written as 
. Similarly, if 
is a basic relation in 
and the element 
, then one writes 
(true) or simply 
. If, on the other hand, 
, one writes 
(false) or 
. Let 
, 
and let 
be the mapping of the union 
into the set of natural numbers 
, defined by the formulas 
(
), 
(
). The object 
is the signature of the class 
. A finite signature is written as a string 
or, more briefly, 
. An algebraic system 
, written in the signature 
, is known as an 
-system and is denoted by 
.
The conditions (1) and (2) for an isomorphism of the systems 
and 
become simplified if the systems are considered in one signature 
. Thus, if 
(
) and 
(
) are the signature symbols, equations (1) and (2) assume the form
 | (3) |
 | (4) |
A homomorphism of an 
-system 
into an 
-system 
is any mapping 
which fulfills both condition (3) and the condition
 | (5) |
for all 
and for all 
of 
. A homomorphism 
is called strong if, for any elements 
of 
and for any predicate symbol 
of 
, the relation 
implies the existence in 
of pre-images 
of the elements 
such that 
. The concepts of a homomorphism and of a strong homomorphism of algebras are identical. Models have homomorphisms that are not strong, and have one-to-one homomorphisms that are not isomorphisms. Under a homomorphism 
, images of subsystems of 
are subsystems in 
; and non-empty complete pre-images of subsystems of 
are subsystems in 
.
An equivalence relation 
is called a congruence of the 
-system 
if
 |
 |
for all 
of 
and all 
. For each homomorphism 
of an algebraic system 
the binary relation 
which holds if and only if 
is a congruence in 
, called its kernel congruence. For any congruence 
of an 
-system 
and for each element 
the set 
is called a coset of the algebraic system 
by the congruence 
. On the assumption that, for each 
, 
,
 |
and
 |
if and only if there exist elements 
in 
such that 
and 
, one obtains the algebraic system 
, which is of the same type as the given system; it is called the quotient system of the algebraic system 
by the congruence 
. For each congruence 
of an algebraic system 
the canonical mapping 
(
) is a homomorphism of 
onto the quotient system 
for which the given congruence 
is the kernel congruence. If 
is a homomorphism of an algebraic system 
into an algebraic system 
and 
is the kernel congruence for 
, then the mapping 
is a homomorphism of the quotient system 
into the algebraic system 
. If the homomorphism 
is strong, 
is an isomorphism.
The Cartesian product of 
-systems 
, 
, is the 
-system 
in which 
is the Cartesian product of the underlying sets 
(
) and the basic operations and the basic relations on 
are given by the conditions: 
(
, 
) is the element 
with coordinates 
(
), 
(
) if and only if 
for all 
.
A language of the first order.
The basic formal language of the theory of algebraic systems is the first-order language 
which is constructed as follows. The alphabet of the language 
in the given signature 
, 
, 
, consists of the object variables 
the function symbols 
(
), the predicate symbols 
(
), the logical connectives
 |
the quantifiers:
— "for each element xk" ;
— "there exists an element xk" ;
and the auxiliary symbols: brackets and commas. The (first-order) properties of 
-systems are expressed by finite sequences of alphabet symbols, or words, constructed in accordance with specific rules and known as terms and formulas. It is inductively assumed that each word of the form 
or 
is a term if 
; if 
are terms and if 
, then 
is also a term.
If 
is an 
-system and if 
is a term of the signature 
containing object variables 
, then if one replaces 
by some elements 
in 
, and executes the operations in 
on the latter elements corresponding to the symbols of 
forming part of this term, then one obtains an element 
from 
, which is called the value of the term 
for 
. If 
is a homomorphism of an 
-system 
into an 
-system 
, then
 |
The concept of a formula of the signature 
, and of free and bound object variables in it, is also defined inductively:
1) If 
is any predicate symbol for 
or the equality sign 
, 
or 2 respectively, and if 
are arbitrary terms of the signature 
, then the word 
is a formula in which all object variables are free.
2) If 
is a formula, so is 
. Free (bound) object variables in the formula 
are those and only those variables which are free (bound) in 
.
3) If 
are formulas and if the object variables which form part of both formulas are free in both formulas, then the words
 | (6) |
are also formulas.
Object variables which are free (bound) in at least one of the formulas 
, 
are called free (bound) in the formulas (6) as well.
4) If an object variable 
occurs free in a formula 
, then the words 
, 
are again formulas in which the variable 
is bound, while all the other object variables which occur free or bound in the formula 
remain free or bound in the formulas 
, 
as well.
Let an 
-system 
and a formula 
of the signature 
be given. If one now assigns to all free object variables 
from 
some values 
from 
and if one interprets the function and the predicate symbols forming part of 
as the respective basic operations and basic relations in 
, then one obtains a definite statement which may be true or false. One accordingly assigns to the formula 
the value 
or 
, for 
denoted by 
. If 
is an isomorphic mapping of an 
-system 
into an 
-system 
, then
 |
for all 
from 
.
A formula 
is called closed if it contains no free object variables. For any closed formula 
of the signature 
and any 
-system 
one may speak of 
being true or false in 
. A set 
of closed formulas of a given signature 
is said to be realizable or consistent if there exists an 
-system in which all formulas from 
are true.
The compactness theorem or the Gödel–Mal'tsev theorem states: If each finite subset of an infinite set 
of closed formulas of a given signature 
is realizable, then the entire set 
is realizable as well.
Axiomatizable classes.
Let 
be some set of closed formulas of a signature 
. The class of all 
-systems in which all formulas of 
are true will be denoted by 
. The set 
of all closed formulas of a signature 
which are true in all 
-systems of the given class 
, is called the elementary theory of 
. In particular, if 
is the class of 
-systems isomorphic to the given 
-system 
, then 
is said to be the elementary theory of the 
-system 
and is simply denoted by 
. A class 
of 
-systems is said to be axiomatizable if 
. A class 
of 
-systems is axiomatizable if and only if there exists a set 
of closed formulas of the signature 
such that 
.
Along with the general concept of axiomatizability, axiomatizability using first-order formulas of a special kind may also be considered. The special formulas of a given signature which are the most important in algebra are:
Identities — the formulas
 |
where 
is some predicate symbol from 
or the equality sign 
, and 
are terms of the signature 
in 
.
Quasi-identities — the formulas
 |
 |
where 
are certain predicate symbols from 
or equality signs, while 
are terms of the signature 
in 
.
Universal formulas — the formulas 
, where 
is a formula of the signature 
not containing quantifiers.
If a set 
of identities (quasi-identities or universal formulas) of a signature 
is given, then the class 
is known as a variety (quasi-variety or universal class) of 
-systems.
Birkhoff's theorem: A non-empty class 
of 
-systems is a variety if and only if it is closed with respect to subsystems, Cartesian products and homomorphic images.
If 
is some 
-system, then, by exchanging each function symbol 
from 
for a predicate symbol 
of arity 
(higher by one) and putting, for elements 
from 
 |
one obtains a model 
for which 
. Submodels of the model 
are called submodels of the 
-system 
. For any non-empty finite subsets 
, 
, the model 
is called a finite depletion of the finite submodel 
of the 
-system 
. An 
-system 
is said to be locally imbeddable in a class 
of 
-systems if for each finite depletion 
of any finite submodel 
of the 
-system 
there exists in the class 
an 
-system 
(depending on the chosen finite depletion 
) such that the model 
is isomorphic to the model 
for a suitable subset 
.
A subclass 
of a class 
of 
-systems is called universal (or universally axiomatizable) in 
if there exists a set 
of universal formulas of the signature 
such that 
.
The Tarski–Los theorem: A subclass 
of a class 
of 
-systems is universal in 
if and only if 
contains all systems from 
which are locally imbeddable in 
.
Filtered products.
Let 
be the Cartesian product of the 
-systems 
(
, 
) and let 
be some filter over 
. The relation
 |
is an equivalence relation on the underlying set 
of the 
-system 
. For each element 
, let 
be the coset by this equivalence and let 
. Putting
 |
 |
 |
 |
one obtains the 
-system 
, which is called the product of the 
-systems 
(
) filtered through the filter 
. The 
-systems 
(
) are said to be the factors of this product. If 
is an ultrafilter over 
, the filtered product 
is known as the ultraproduct of the 
-systems 
(
).
The ultraproduct theorem: If 
is the ultraproduct of the 
-systems 
(
) and if 
is an arbitrary formula of the signature 
in which 
are free object variables, then for any elements 
:
 |
 |
In particular, a closed formula 
of the signature 
is true in the ultraproduct 
of the 
-systems 
(
) if and only if the set of numbers of factors in which the formula 
is true belongs to the ultrafilter 
. Therefore, any axiomatizable class of 
-systems is closed with respect to ultraproducts.
A class 
of 
-systems is universally axiomatizable if and only if it is closed with respect to subsystems and ultraproducts.
An 
-system 
is said to be a unit if its underlying set consists of a single element, e.g. an element 
, and if 
for all 
.
Mal'tsev's theorem: A class 
of 
-systems is a quasi-variety if and only if it contains a unit 
-system and is closed with respect to subsystems and filtered products (through an arbitrary filter).
Completeness and categoricity.
A non-empty class 
of 
-systems is called categorical if all 
-systems from 
are mutually isomorphic. Any categorical axiomatizable class of 
-systems consists of one (up to an isomorphism) finite 
-system.
A class 
of 
-systems is called categorical in cardinality 
if it contains an 
-system of cardinality 
and if all 
-systems from 
of cardinality 
are mutually isomorphic. For example, the class of algebraically closed fields of fixed characteristic is categorical in any uncountable infinite cardinality. A non-empty class 
of 
-systems is called complete if for any 
-systems 
from 
the equality 
is valid.
Vaught's theorem. If an axiomatizable class 
of 
-systems is categorical in some cardinality 
and if all 
-systems in 
are infinite, then 
is a complete class.
In particular, the class of all algebraically closed fields of fixed characteristic is complete.
See also Algebraic system, automorphism of an; Algebraic systems, quasi-variety of; Algebraic systems, class of; Algebraic systems, variety of.
References
| [1] | A.I. Mal'tsev, "Algebraic systems" , Springer (1973) (Translated from Russian) |
| [2] | P.M. Cohn, "Universal algebra" , Reidel (1981) |
| [3] | G. Grätzer, "Universal algebra" , Springer (1979) |
| [4] | J.L. Bell, A.B. Slomson, "Models and ultraproducts: an introduction" , North-Holland (1971) |
| [5] | C.C. Chang, H.J. Keisler, "Model theory" , North-Holland (1973) |
Comments
The terminology in use for this subject in English-speaking countries differs in a number of respects from the Russian terminology. What is here called an algebraic system is usually called a (first-order) structure (a structure of type 
, if a given signature or similarity type 
has been specified); the term algebra is often used instead of "structure" in the case when 
has no primitive relations. The term model is reserved for a structure which satisfies a given set of first-order sentences (closed formulas); it is not normally used in the sense defined above. The underlying set of a structure is sometimes called its universe.
Although the text is correct in saying that the subject was largely developed in the 1950s (principally through work of L.A. Henkin [L.A. Khenkin], A.I. Mal'tsev, A. Robinson and A. Tarski), two important precursors dating from 1935 should be mentioned. They are Birkhoff's theorem characterizing varieties of algebras [a1] and Tarski's definition of validity of formulas in a first-order structure [a2].
References
| [a1] | G. Birkhoff, "On the structure of abstract algebras" Proc. Cambridge Philos. Soc. , 31 (1935) pp. 433–454 |
| [a2] | A. Tarski, "Der Wahrheitsbegriff in den formalisierten Sprachen" Studia Philos. , 1 (1935) pp. 261–405 |
Algebraic system. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Algebraic_system&oldid=44373