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.[edit]

An algebraic system is an object $ \mathbf A = \langle A,\ O,\ R \rangle $ consisting of a non-empty set $ A $, a family $ O $ of algebraic operations (cf. Algebraic operation) $ o _{i} : \ A ^ {n _ i} \rightarrow A $( $ i \in I $) and a family $ R $ of relations (cf. Relation) $ r _{j} \subseteq A ^ {m _ j} $( $ j \in J $) defined on $ A $. The indices $ n _{i} ,\ m _{j} $ of the Cartesian powers of $ A $ under consideration are assumed to be non-negative integers and are said to be the arities of the respective operations and relations. The set $ A $ is called the carrier or the underlying set of the algebraic system $ \mathbf A $, while its elements are called the elements of this system. The cardinality $ | A | $ of $ A $ is said to be the cardinality or order of the algebraic system $ \mathbf A $. The image $ o _{i} (a _{1} \dots a _{ {n _ i}} ) $ of the element $ (a _{1} \dots a _{ {n _ i}} ) \in A ^ {n _ i} $ under the mapping $ o _{i} : \ A ^ {n _ i} \rightarrow A $ is called the value of the operation $ o _{i} $ at the point $ ( a _{1} \dots a _{ {n _ i}} ) $. Similarly, if $ (a _{1} \dots a _{ {m _ j}} ) \in r _{j} $, then one says that the elements $ a _{1} \dots a _{ {m _ j}} $ of $ A $ are in relation $ r _{j} $, and one writes $ r _{j} ( a _{1} \dots a _{ {m _ j}} ) $. The operations $ o _{i} $( $ i \in I $) and the relations $ r _{j} $( $ j \in J $), unlike other operations and relations that may be defined on $ A $, are called basic or primitive.

The pair of families $ \langle \{ {n _ i} : {i \in I} \} ; \ \{ {m _ j} : {j \in J} \} \rangle $ is called the type of the algebraic system $ \mathbf A $. Two algebraic systems $ \mathbf A ,\ \mathbf A^ \prime $ have the same type if $ I = I^ \prime $, $ J = J^ \prime $ and $ n _{i} = n _ i^ \prime $, $ m _{j} = m _ j^ \prime $ for all $ i \in I $, $ j \in J $. Basic operations $ o _{i} $, $ o _ i^ \prime $ and basic relations $ r _{j} $, $ r _ j^ \prime $ of two algebraic systems $ \mathbf A $, $ \mathbf A^ \prime $ of the same type, with identical indices in $ I $, $ J $ respectively, are called similar.

An algebraic system $ \mathbf A $ is called finite if the set $ A $ is finite and it is called of finite type if the set $ I \cup J $ is finite. An algebraic system $ \mathbf A $ of finite type is written as $ A = \langle A; \ o _{1} \dots o _{s} ,\ r _{1} \dots r _{t} \rangle $.

An algebraic system $ \mathbf A = \langle A,\ O,\ R\rangle $ is called a universal algebra or an algebra if the set $ R $ of its basic relations is empty, and it is called a model (in logic) or a relational system if the set $ O $ 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 $ B $ of the underlying set $ A $ of an algebraic system $ \mathbf A = \langle A,\ O,\ R \rangle $ is called closed if for any elements $ b _{1} \dots b _{ {n _ i}} $ of $ B $ the value $ o _{i} (b _{1} \dots b _{ {n _ i}} ) $ of each basic operation $ o _{i} \in O $ also belongs to $ B $. By considering the operations of $ O $ and the relations of $ R $ on a closed subset $ B $, one obtains an algebraic system $ \mathbf B = \langle B ,\ O^ \prime ,\ R^ \prime \rangle $ which is of the same type as the given algebraic system and is called a subsystem of the algebraic system $ \mathbf A $. 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 $ \mathbf G $ is an algebra of type $ \langle 2\rangle $, i.e. an algebra with one basic operation $ G \times G \rightarrow G $. A groupoid $ \mathbf H $ with a distinguished unit $ e $ is an algebra of type $ \langle 2,\ 0\rangle $, the distinguished element of which has the property $ o(e,\ h) = o(h,\ e) = h $ for all $ h \in H $ with respect to the basic operation $ o : \ H \times H \rightarrow H $. For this reason any subgroupoid of a groupoid $ \mathbf H $ with a distinguished unit $ e $ contains $ e $, while a subgroupoid of a groupoid $ \langle H,\ o \rangle $ does not necessarily contain $ e $. Unlike algebras, any non-empty subset of a model may be considered as a submodel.

An algebraic system $ \mathbf A $ is isomorphic to an algebraic system $ \mathbf A^ \prime $ of the same type if there exists a one-to-one mapping $ \phi $ of the set $ A $ into the set $ A^ \prime $ such that

$$ \tag{1} \phi ( o _ i^ \prime ( a _{1} \dots a _{ {n _ i}} ) ) \ = \ o _ i^ \prime ( \phi ( a _{1} ) \dots \phi ( a _{ {n _ i}} ) ) , $$

$$ \tag{2} r _{j} ( a _{1} \dots a _{ {m _ j}} ) \ \iff \ r _ j^ \prime ( \phi ( a _{1} ) \dots \phi ( a _{ {m _ j}} ) ), $$

holds for all $ a _{1} ,\ a _{2} \dots $ of $ A $ and for all $ i \in I $, $ j \in J $. A mapping $ \phi $ 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 $ \mathbf A $, also contains all systems isomorphic to $ \mathbf A $. In considering a class $ \mathfrak K $ of algebraic systems, all systems in this class are usually written in a definite signature, as follows. Let the type of the class $ \mathfrak K $ be $ \langle \{ {n _ i} : {i \in I} \} ; \ \{ {m _ j} : {j \in J} \} \rangle $. To each $ i \in I $ is assigned some symbol $ F _{i} $, called a functional, while to each $ j \in J $ is assigned a symbol $ P _{j} $, called a predicate. If an algebraic system $ \mathbf A $ belongs to the class $ \mathfrak K $ and if $ o _{i} : \ A^{n} _{i} \rightarrow A $ is a basic operation in it, then the element $ o _{i} ( a _{1} \dots a _{ {n _ i}} ) $ of $ A $ is written as $ F _{i} ( a _{1} \dots a _{ {n _ i}} ) $. Similarly, if $ r _{j} \subseteq A^{m} _{j} $ is a basic relation in $ A $ and the element $ ( a _{1} \dots a _{ {m _ j}} ) \in r _{j} $, then one writes $ P _{j} ( a _{1} \dots a _{ {m _ j}} ) = T $( true) or simply $ P _{j} ( a _{1} \dots a _{ {m _ j}} ) $. If, on the other hand, $ ( a _{1} \dots a _{ {m _ j}} ) \notin r _{j} $, one writes $ P _{j} ( a _{1} \dots a _{ {m _ j}} ) = F $( false) or $ \neg P _{j} ( a _{1} \dots a _{ {m _ j}} ) $. Let $ \Omega _{f} = \{ {F _ j} : {i \in I} \} $, $ \Omega _{p} = \{ {P _ j} : {j \in J} \} $ and let $ \nu $ be the mapping of the union $ \Omega _{f} \cup \Omega _{p} $ into the set of natural numbers $ \{ 0,\ 1,\ 2 ,\dots \} $, defined by the formulas $ \nu ( F _{i} ) = n _{i} $( $ i \in I $), $ \nu (P _{j} ) = m _{j} $( $ j \in J $). The object $ \Omega = \langle \Omega _{f} ,\ \Omega _{p} ,\ \nu \rangle $ is the signature of the class $ \mathfrak K $. A finite signature is written as a string $ \langle F _{1} ^ {( n _{1} )} \dots F _{s} ^ {(n _{s} )} ; \ P _{1} ^ {( m _{1} )} \dots P _{t} ^ {( m _{t} )} \rangle $ or, more briefly, $ \langle F _{1} \dots F _{s} ; \ P _{1} \dots P _{t} \rangle $. An algebraic system $ \mathbf A $, written in the signature $ \Omega $, is known as an $ \Omega $- system and is denoted by $ \mathbf A = \langle A,\ \Omega \rangle $.

The conditions (1) and (2) for an isomorphism of the systems $ \mathbf A $ and $ \mathbf A^ \prime $ become simplified if the systems are considered in one signature $ \Omega $. Thus, if $ F _{i} $( $ i \in I $) and $ P _{j} $( $ j \in J $) are the signature symbols, equations (1) and (2) assume the form

$$ \tag{3} \phi ( F _{i} ( a _{1} \dots a _{ {n _ i}} ) ) \ = \ F _{i} ( \phi ( a _{1} ) \dots \phi ( a _{ {n _ i}} ) ) , $$

$$ \tag{4} P _{j} ( a _{1} \dots a _{ {m _ j}} ) \ \iff \ P _{j} ( \phi ( a _{1} ) \dots \phi ( a _{ {m _ j}} ) ) . $$

A homomorphism of an $ \Omega $- system $ \mathbf A $ into an $ \Omega $- system $ \mathbf A^ \prime $ is any mapping $ \phi : \ A \rightarrow A^ \prime $ which fulfills both condition (3) and the condition

$$ \tag{5} P _{j} ( a _{1} \dots a _{ {m _ j}} ) \ \Rightarrow \ P _{j} ( \phi ( a _{1} ) \dots \phi ( a _{ {m _ j}} ) ) $$

for all $ F _{i} \in \Omega _{f} ,\ P _{j} \in \Omega _{p} $ and for all $ a _{1} ,\ a _{2} \dots $ of $ A $. A homomorphism $ \phi : \ \mathbf A \rightarrow \mathbf A^ \prime $ is called strong if, for any elements $ b _{1} \dots b _{ {m _ j}} $ of $ A^ \prime $ and for any predicate symbol $ P _{j} $ of $ \Omega _{p} $, the relation $ P _{j} (b _{1} \dots b _{ {m _ j}} ) = T $ implies the existence in $ A $ of pre-images $ a _{1} \dots a _{ {m _ j}} $ of the elements $ b _{1} \dots b _{ {m _ j}} $ such that $ P _{j} (a _{1} \dots a _{ {m _ j}} ) = T $. 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 $ \phi : \ \mathbf A \rightarrow \mathbf A^ \prime $, images of subsystems of $ \mathbf A $ are subsystems in $ \mathbf A^ \prime $; and non-empty complete pre-images of subsystems of $ \mathbf A^ \prime $ are subsystems in $ \mathbf A $.

An equivalence relation $ \theta \subseteq A \times A $ is called a congruence of the $ \Omega $- system $ \mathbf A $ if

$$ \theta ( a _{1} ,\ b _{1} ) \dots \theta ( a _{ {n _ i}} , \ b _{ {n _ i}} )\ \Rightarrow $$

$$ \Rightarrow \ \theta ( F _{i} ( a _{1} \dots a _{ {n _ i}} ) ,\ F _{i} ( b _{1} \dots b _{ {n _ i}} ) ) $$

for all $ a _{1} ,\ b _{1} \dots a _{ {n _ i}} ,\ b _{ {n _ i}} $ of $ A $ and all $ F _{i} \in \Omega _{f} $. For each homomorphism $ \phi $ of an algebraic system $ \mathbf A $ the binary relation $ \theta (a,\ b) $ which holds if and only if $ \phi (a) = \phi (b) $ is a congruence in $ \mathbf A $, called its kernel congruence. For any congruence $ \theta $ of an $ \Omega $- system $ \mathbf A $ and for each element $ a \in A $ the set $ a / \theta = \{ {x \in A} : {\theta (x,\ a)} \} $ is called a coset of the algebraic system $ \mathbf A $ by the congruence $ \theta $. On the assumption that, for each $ F _{i} \in \Omega _{f} $, $ P _{j} \in \Omega _{p} $,

$$ F _{i} ( a _{1} / \theta \dots a _{ {n _ i}} / \theta ) \ = \ F _{i} ( a _{1} \dots a _{ {n _ i}} ) / \theta $$

and

$$ P _{j} ( b _{1} / \theta \dots b _{ {m _ j}} / \theta ) \ = \ T $$

if and only if there exist elements $ c _{1} \dots c _{ {m _ j}} $ in $ A $ such that $ \theta (b _{1} ,\ c _{1} ) \dots \theta ( b _{ {m _ j}} ,\ c _{ {m _ j}} ) $ and $ P _{j} (c _{1} \dots c _{ {m _ j}} ) $, one obtains the algebraic system $ \mathbf A / \theta $, which is of the same type as the given system; it is called the quotient system of the algebraic system $ \mathbf A $ by the congruence $ \theta $. For each congruence $ \theta $ of an algebraic system $ \mathbf A $ the canonical mapping $ \phi (a) = a/ \theta $( $ a \in A $) is a homomorphism of $ \mathbf A $ onto the quotient system $ \mathbf A / \theta $ for which the given congruence $ \theta $ is the kernel congruence. If $ \phi $ is a homomorphism of an algebraic system $ \mathbf A $ into an algebraic system $ \mathbf A^ \prime $ and $ \theta $ is the kernel congruence for $ \phi $, then the mapping $ \psi ( a/ \theta ) = \phi (a) $ is a homomorphism of the quotient system $ \mathbf A / \theta $ into the algebraic system $ \mathbf A^ \prime $. If the homomorphism $ \phi $ is strong, $ \psi $ is an isomorphism.

The Cartesian product of $ \Omega $- systems $ \mathbf A _ \alpha = \langle A _ \alpha ,\ \Omega \rangle $, $ \alpha \in \Lambda \neq \emptyset $, is the $ \Omega $- system $ \mathbf D = \langle D,\ \Omega \rangle $ in which $ D $ is the Cartesian product of the underlying sets $ A _ \alpha $( $ \alpha \in \Lambda $) and the basic operations and the basic relations on $ D $ are given by the conditions: $ F _{i} ( d _{1} \dots d _{ {n _ i}} ) $( $ d _{1} \dots d _{ {n _ i}} \in D $, $ F _{i} \in \Lambda _{f} $) is the element $ d \in D $ with coordinates $ d ( \alpha ) = F _{i} ( d _{1} ( \alpha ) \dots d _{ {n _ i}} ( \alpha ) ) $( $ \alpha \in \Lambda $), $ P _{j} ( d _{1} \dots d _{ {m _ j}} ) = T $( $ P _{j} \in \Omega _{p} $) if and only if $ P _{j} ( d _{1} ( \alpha ) \dots d _{ {m _ j}} ( \alpha ) ) = T $ for all $ \alpha \in \Lambda $.

A language of the first order.[edit]

The basic formal language of the theory of algebraic systems is the first-order language $ L $ which is constructed as follows. The alphabet of the language $ L $ in the given signature $ \Omega = \langle \Omega _{f} ,\ \Omega _{p} ,\ \nu \rangle $, $ \Omega _{f} = \{ {F _ i} : {i \in I} \} $, $ \Omega _{p} = \{ {P _ j} : {j \in J} \} $, consists of the object variables $ x _{1} ,\ x _{2} \dots $ the function symbols $ F _{i} $( $ i \in I $), the predicate symbols $ P _{j} $( $ j \in J $), the logical connectives

$$ \& ,\ \ \lor ,\ \ \rightarrow ,\ \ \neg ,\ \ =, $$

the quantifiers:

$ \forall x _{k} $ — "for each element xk" ;

$ \exists x _{k} $ — "there exists an element xk" ;

and the auxiliary symbols: brackets and commas. The (first-order) properties of $ \Omega $- 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 $ x _{k} $ or $ F _{i} $ is a term if $ \nu (F _{i} ) = 0 $; if $ f _{1} \dots f _{n} $ are terms and if $ n = \nu (F _{i} ) $, then $ F _{i} (f _{1} \dots f _{n} ) $ is also a term.

If $ \mathbf A $ is an $ \Omega $- system and if $ f (x _{1} \dots x _{n} ) $ is a term of the signature $ \Omega $ containing object variables $ x _{1} \dots x _{k} $, then if one replaces $ x _{1} \dots x _{k} $ by some elements $ a _{1} \dots a _{k} $ in $ A $, and executes the operations in $ \mathbf A $ on the latter elements corresponding to the symbols of $ \Omega _{f} $ forming part of this term, then one obtains an element $ f (a _{1} \dots a _{k} ) $ from $ A $, which is called the value of the term $ f (x _{1} \dots x _{k} ) $ for $ x _{1} = a _{1} \dots x _{k} = a _{k} $. If $ \phi $ is a homomorphism of an $ \Omega $- system $ \mathbf A $ into an $ \Omega $- system $ \mathbf A^ \prime $, then

$$ \phi ( f ( a _{1} \dots a _{k} ) ) \ = \ f ( \phi ( a _{1} ) \dots \phi ( a _{k} ) ) . $$

The concept of a formula of the signature $ \Omega $, and of free and bound object variables in it, is also defined inductively:

1) If $ P $ is any predicate symbol for $ \Omega $ or the equality sign $ = $, $ m = \nu (P) $ or 2 respectively, and if $ f _{1} \dots f _{m} $ are arbitrary terms of the signature $ \Omega $, then the word $ P( f _{1} \dots f _{m} ) $ is a formula in which all object variables are free.

2) If $ \mathfrak F $ is a formula, so is $ \neg \mathfrak F $. Free (bound) object variables in the formula $ \neg \mathfrak F $ are those and only those variables which are free (bound) in $ \mathfrak F $.

3) If $ \mathfrak F _{1} ,\ \mathfrak F _{2} $ are formulas and if the object variables which form part of both formulas are free in both formulas, then the words

$$ \tag{6} \mathfrak F _{1} \& \mathfrak F _{2} ,\ \ \mathfrak F _{1} \lor \mathfrak F _{2} ,\ \ \mathfrak F _{1} \rightarrow \mathfrak F _{2} , $$

are also formulas.

Object variables which are free (bound) in at least one of the formulas $ \mathfrak F _{1} $, $ \mathfrak F _{2} $ are called free (bound) in the formulas (6) as well.

4) If an object variable $ x _{k} $ occurs free in a formula $ \mathfrak F $, then the words $ ( \forall x _{k} ) \mathfrak F $, $ ( \exists x _{k} ) \mathfrak F $ are again formulas in which the variable $ x _{k} $ is bound, while all the other object variables which occur free or bound in the formula $ \mathfrak F $ remain free or bound in the formulas $ ( \forall x _{k} ) \mathfrak F $, $ ( \exists x _{k} ) \mathfrak F $ as well.

Let an $ \Omega $- system $ \mathbf A $ and a formula $ \mathfrak F $ of the signature $ \Omega $ be given. If one now assigns to all free object variables $ x _{1} \dots x _{k} $ from $ \mathfrak F $ some values $ a _{1} \dots a _{k} $ from $ A $ and if one interprets the function and the predicate symbols forming part of $ \mathfrak F $ as the respective basic operations and basic relations in $ \mathbf A $, then one obtains a definite statement which may be true or false. One accordingly assigns to the formula $ \mathfrak F $ the value $ T $ or $ F $, for $ x _{1} = a _{1} \dots x _{k} = a _{k} $ denoted by $ \mathfrak F (a _{1} \dots a _{k} ) $. If $ \phi $ is an isomorphic mapping of an $ \Omega $- system $ \mathbf A $ into an $ \Omega $- system $ \mathbf A^ \prime $, then

$$ \mathfrak F ( a _{1} \dots a _{k} ) \ = \ \mathfrak F ( \phi ( a _{1} ) \dots \phi ( a _{k} ) ), $$

for all $ a _{1} \dots a _{k} $ from $ A $.

A formula $ \mathfrak F $ is called closed if it contains no free object variables. For any closed formula $ \mathfrak F $ of the signature $ \Omega $ and any $ \Omega $- system $ \mathbf A $ one may speak of $ \mathfrak F $ being true or false in $ \mathbf A $. A set $ S $ of closed formulas of a given signature $ \Omega $ is said to be realizable or consistent if there exists an $ \Omega $- system in which all formulas from $ S $ are true.

The compactness theorem or the Gödel–Mal'tsev theorem states: If each finite subset of an infinite set $ S $ of closed formulas of a given signature $ \Omega $ is realizable, then the entire set $ S $ is realizable as well.

Axiomatizable classes.[edit]

Let $ S $ be some set of closed formulas of a signature $ \Omega $. The class of all $ \Omega $- systems in which all formulas of $ S $ are true will be denoted by $ KS $. The set $ \mathop{\rm Th}\nolimits \ \mathfrak K $ of all closed formulas of a signature $ \Omega $ which are true in all $ \Omega $- systems of the given class $ \mathfrak K $, is called the elementary theory of $ \mathfrak K $. In particular, if $ ( \mathbf A ) $ is the class of $ \Omega $- systems isomorphic to the given $ \Omega $- system $ \mathbf A $, then $ \mathop{\rm Th}\nolimits \ ( \mathbf A ) $ is said to be the elementary theory of the $ \Omega $- system $ \mathbf A $ and is simply denoted by $ \mathop{\rm Th}\nolimits \ \mathbf A $. A class $ \mathfrak K $ of $ \Omega $- systems is said to be axiomatizable if $ \mathfrak K = K \ \mathop{\rm Th}\nolimits \ \mathfrak K $. A class $ \mathfrak K $ of $ \Omega $- systems is axiomatizable if and only if there exists a set $ S $ of closed formulas of the signature $ \Omega $ such that $ \mathfrak K = KS $.

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

$$ ( \forall x _{1} ) \dots (\forall x _{s} ) P ( f _{1} \dots f _{m} ) , $$

where $ P $ is some predicate symbol from $ \Omega $ or the equality sign $ = $, and $ f _{1} \dots f _{m} $ are terms of the signature $ \Omega $ in $ x _{1} \dots x _{s} $.

Quasi-identities — the formulas

$$ ( \forall x _{1} ) \dots ( \forall x _{s} ) [ P ( f _{1} \dots f _{k} ) \& \dots \& Q ( g _{1} \dots g _{m} )\ \rightarrow $$

$$ \rightarrow \ {} R ( h _{1} \dots h _{n} ) ] , $$

where $ P \dots Q,\ R $ are certain predicate symbols from $ \Omega _{p} $ or equality signs, while $ f _{1} \dots f _{k} ,\ g _{1} \dots g _{m} ,\ h _{1} \dots h _{n} $ are terms of the signature $ \Omega $ in $ x _{1} \dots x _{s} $.

Universal formulas — the formulas $ ( \forall x _{1} ) \dots ( \forall x _{s} ) \mathfrak F $, where $ \mathfrak F $ is a formula of the signature $ \Omega $ not containing quantifiers.

If a set $ S $ of identities (quasi-identities or universal formulas) of a signature $ \Omega $ is given, then the class $ KS $ is known as a variety (quasi-variety or universal class) of $ \Omega $- systems.

Birkhoff's theorem: A non-empty class $ \mathfrak K $ of $ \Omega $- systems is a variety if and only if it is closed with respect to subsystems, Cartesian products and homomorphic images.

If $ \mathbf A = \langle A,\ \Omega \rangle $ is some $ \Omega $- system, then, by exchanging each function symbol $ F _{i} $ from $ \Omega _{f} $ for a predicate symbol $ F _ i^{*} $ of arity $ n _{i} + 1 $( higher by one) and putting, for elements $ a _{1} \dots a _{ {n _ i}} ,\ a $ from $ A $

$$ F _ i^{*} ( a _{1} \dots a _{ {n _ i}} ,\ a ) \ \iff \ F _{i} ( a _{1} \dots a _{ {n _ i}} ) \ = \ a , $$

one obtains a model $ \mathbf A^{*} = \langle A,\ \Omega^{*} \rangle $ for which $ \Omega _ p^{*} = \Omega _{p} \cup \{ {F _{i} ^ *} : {F _{i} \in \Omega _ f} \} $. Submodels of the model $ \mathbf A^{*} $ are called submodels of the $ \Omega $- system $ \mathbf A $. For any non-empty finite subsets $ A _ \alpha \subseteq A $, $ \Omega _ \beta^{*} \subseteq \Omega^{*} $, the model $ \mathbf A _{ {\alpha \beta}} = \langle A _ \alpha ,\ \Omega _ \beta^{*} \rangle $ is called a finite depletion of the finite submodel $ \mathbf A _ \alpha = \langle A _ \alpha ,\ \Omega^{*} \rangle $ of the $ \Omega $- system $ \mathbf A $. An $ \Omega $- system $ \mathbf A $ is said to be locally imbeddable in a class $ \mathfrak K $ of $ \Omega $- systems if for each finite depletion $ \mathbf A _{ {\alpha \beta}} $ of any finite submodel $ \mathbf A _ \alpha $ of the $ \Omega $- system $ \mathbf A $ there exists in the class $ \mathfrak K $ an $ \Omega $- system $ \mathbf B $( depending on the chosen finite depletion $ \mathbf A _{ {\alpha \beta}} $) such that the model $ \mathbf A _{ {\alpha \beta}} = \langle A _ \alpha ,\ \Omega _ \beta^{*} \rangle $ is isomorphic to the model $ \mathbf B _{ {\alpha \beta}} = \langle B _ \alpha ,\ \Omega _ \beta^{*} \rangle $ for a suitable subset $ B _ \alpha \subseteq B $.

A subclass $ \mathfrak L $ of a class $ \mathfrak K $ of $ \Omega $- systems is called universal (or universally axiomatizable) in $ \mathfrak K $ if there exists a set $ S $ of universal formulas of the signature $ \Omega $ such that $ \mathfrak L = KS \cap \mathfrak K $.

The Tarski–Los theorem: A subclass $ \mathfrak L $ of a class $ \mathfrak K $ of $ \Omega $- systems is universal in $ \mathfrak K $ if and only if $ \mathfrak L $ contains all systems from $ \mathfrak K $ which are locally imbeddable in $ \mathfrak L $.

Filtered products.[edit]

Let $ \mathbf D = \prod \mathbf A _ \alpha $ be the Cartesian product of the $ \Omega $- systems $ \mathbf A _ \alpha $( $ \alpha \in \Lambda $, $ \Lambda \neq \emptyset $) and let $ \Phi $ be some filter over $ \Lambda $. The relation

$$ d \equiv {} _ \Phi h \ \iff \ \{ {\alpha \in \Lambda} : {d ( \alpha ) = h ( \alpha )} \} \in \Phi \ \ ( d ,\ h \in D ) $$

is an equivalence relation on the underlying set $ D $ of the $ \Omega $- system $ \mathbf D $. For each element $ d \in D $, let $ d / \Phi $ be the coset by this equivalence and let $ D / \Phi = \{ {d / \Phi} : {d \in D} \} $. Putting

$$ F _{i} ( d _{1} / \Phi \dots d _{ {n _ i}} / \Phi ) \ = \ d \Phi\ \iff $$

$$ \iff \ \{ \alpha : \ F _{i} ( d _{1} ( \alpha ) \dots d _{ {n _ i}} ( \alpha ) ) = d ( \alpha ) \} \ \in \ \Phi \ \ ( F _{i} \in \Omega _{f} ) , $$

$$ P _{j} ( d _{1} / \Phi \dots d _{ {m _ j}} / \Phi )\ \iff $$

$$ \iff \ \{ \alpha : \ P _{j} ( d _{1} ( \alpha ) \dots d _{ {m _ j}} ( \alpha ) ) \} \ \in \ \Phi \ \ ( P _{j} \in \Omega _{p} ) , $$

one obtains the $ \Omega $- system $ \mathbf D / \Phi = \langle D / \Phi ,\ \Omega \rangle $, which is called the product of the $ \Omega $- systems $ \mathbf A _ \alpha $( $ \alpha \in \Lambda $) filtered through the filter $ \Phi $. The $ \Omega $- systems $ \mathbf A _ \alpha $( $ \alpha \in \Lambda $) are said to be the factors of this product. If $ \Phi $ is an ultrafilter over $ \Lambda $, the filtered product $ \mathbf D / \Phi $ is known as the ultraproduct of the $ \Omega $- systems $ \mathbf A _ \alpha $( $ \alpha \in \Lambda $).

The ultraproduct theorem: If $ \mathbf D / \Phi $ is the ultraproduct of the $ \Omega $- systems $ \mathbf A _ \alpha $( $ \alpha \in \Lambda $) and if $ \mathfrak F ( x _{1} \dots x _{k} ) $ is an arbitrary formula of the signature $ \Omega $ in which $ x _{1} \dots x _{k} $ are free object variables, then for any elements $ d _{1} \dots d _{k} \in D $:

$$ \mathfrak F ( d _{1} / \Phi \dots d _{k} / \Phi ) \ = \ T\ \iff $$

$$ \iff \ \{ \alpha : \ \mathfrak F ( d _{1} ( \alpha ) \dots d _{k} ( \alpha ) ) = T \} \ \in \ \Phi . $$

In particular, a closed formula $ \mathfrak F $ of the signature $ \Omega $ is true in the ultraproduct $ \mathbf D / \Phi $ of the $ \Omega $- systems $ \mathbf A _ \alpha $( $ \alpha \in \Lambda $) if and only if the set of numbers of factors in which the formula $ \mathfrak F $ is true belongs to the ultrafilter $ \Phi $. Therefore, any axiomatizable class of $ \Omega $- systems is closed with respect to ultraproducts.

A class $ L $ of $ \Omega $- systems is universally axiomatizable if and only if it is closed with respect to subsystems and ultraproducts.

An $ \Omega $- system $ \mathbf E = \langle \{ e \} ,\ \Omega \rangle $ is said to be a unit if its underlying set consists of a single element, e.g. an element $ e $, and if $ P _{j} ( e \dots e ) = T $ for all $ P _{j} \in \Omega _{p} $.

Mal'tsev's theorem: A class $ \mathfrak K $ of $ \Omega $- systems is a quasi-variety if and only if it contains a unit $ \Omega $- system and is closed with respect to subsystems and filtered products (through an arbitrary filter).

Completeness and categoricity.[edit]

A non-empty class $ \mathfrak K $ of $ \Omega $- systems is called categorical if all $ \Omega $- systems from $ \mathfrak K $ are mutually isomorphic. Any categorical axiomatizable class of $ \Omega $- systems consists of one (up to an isomorphism) finite $ \Omega $- system.

A class $ \mathfrak K $ of $ \Omega $- systems is called categorical in cardinality $ \mathfrak m $ if it contains an $ \Omega $- system of cardinality $ \mathfrak m $ and if all $ \Omega $- systems from $ \mathfrak K $ of cardinality $ \mathfrak m $ 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 $ \mathfrak K $ of $ \Omega $- systems is called complete if for any $ \Omega $- systems $ \mathbf A ,\ \mathbf B $ from $ \mathfrak K $ the equality $ \mathop{\rm Th}\nolimits \ \mathbf A = \mathop{\rm Th}\nolimits \ \mathbf B $ is valid.

Vaught's theorem. If an axiomatizable class $ \mathfrak K $ of $ \Omega $- systems is categorical in some cardinality $ \mathfrak m \geq | \Omega _{f} \cup \Omega _{p} | $ and if all $ \Omega $- systems in $ \mathfrak K $ are infinite, then $ \mathfrak K $ 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[edit]

Comments[edit]

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 $ \Omega $, if a given signature or similarity type $ \Omega $ has been specified); the term algebra is often used instead of "structure" in the case when $ \Omega $ 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[edit]