Elementary theory

A collection of closed formulas of first-order predicate logic. The elementary theory $ \mathop{\rm Th} ( K) $ of a class $ K $ of algebraic systems (cf. Algebraic system) of signature $ \Omega $ is defined to be the collection of all closed formulas of the first-order predicate logic of signature $ \Omega $ that are true in all systems of $ K $. If $ K $ consists of a single system $ A $, then the elementary theory of the class $ K $ is the elementary theory of the system $ A $. Two algebraic systems of the same signature are said to be elementarily equivalent if their elementary theories are the same. An algebraic system $ A $ of signature $ \Omega $ is called a model of an elementary theory $ T $ of signature $ \Omega $ if all formulas of $ T $ are true in $ A $. An elementary theory is called consistent if it has models. A consistent elementary theory is called complete if any two models of it are elementarily equivalent. The class of all models of an elementary theory $ T $ is denoted by $ \mathop{\rm Mod} ( T) $. An elementary theory $ T $ is called solvable (or decidable) if the set of formulas $ \textrm{ Th Mod } ( T) $( that is, the set of all logical consequences of $ T $) is recursive. A class $ K $ of algebraic systems of signature $ \Omega $ is called axiomatizable if there exists an elementary theory $ T $ of signature $ \Omega $ such that $ K = \mathop{\rm Mod} ( T) $. In this case $ T $ is called a collection of axioms for $ K $. A class $ K $ is axiomatizable if and only if $ K = \textrm{ Mod Th } ( K) $. For example, the class of dense linear orders without a smallest or largest element is axiomatizable, its elementary theory is solvable and any two systems of this class are elementarily equivalent, since the elementary theory of this class is complete; moreover, its elementary theory is finitely axiomatizable. The class of finite cyclic groups is not axiomatizable; however, its elementary theory is solvable, and hence recursively axiomatizable. There are examples of finitely-axiomatizable unsolvable elementary theories. They include those of groups, rings, fields, and others. However, a complete recursively-axiomatizable elementary theory is necessarily solvable. Therefore, to prove the solvability of a recursively-axiomatizable elementary theory it is sufficient to observe that it is complete.

Several methods for proving completeness are known. An elementary theory is called categorical in cardinality $ \alpha $( cf. Categoricity in cardinality) if all its models of cardinality $ \alpha $ are isomorphic. An elementary theory that is categorical in some infinite cardinality and has no finite models is necessarily complete. For example, the elementary theory of algebraically closed fields of a given characteristic is recursively axiomatizable and categorical in every uncountable cardinality; it has no finite models, and therefore it is complete and solvable. In particular, the elementary theory of the field of complex numbers is solvable. Two formulas in the same signature as that of a theory $ T $ are equivalent in the theory $ T $ if they contain the same variables and if, for any model $ A $ of $ T $ and any assignment of elements of $ A $ to their free variables, the formulas are either both true or both false. A complete elementary theory $ T $ of finite or countable signature is countably categorical if and only if for every $ n $ there are finitely many formulas with $ n $ free variables $ v _ {1} \dots v _ {n} $ such that every formula of the appropriate signature with $ v _ {1} \dots v _ {n} $ as free variables is equivalent in $ T $ to one of those formulas. A complete theory of finite or countable signature that is categorical in one uncountable cardinality is also categorical in every other uncountable cardinality. A system $ A $ of signature $ \Omega $ is called an elementary subsystem of a system $ B $ of the same signature if $ A $ is a subsystem of $ B $ and if for every formula $ \Phi ( v _ {1} \dots v _ {n} ) $ of the first-order predicate logic of $ \Omega $ with free variables $ v _ {1} \dots v _ {n} $ and all $ a _ {1} \dots a _ {n} \in A $, the truth of $ \Phi ( a _ {1} \dots a _ {n} ) $ in $ A $ implies its truth in $ B $. An elementary theory $ T $ is called model complete if for any two models $ A $ and $ B $ of it the fact that $ A $ is a subsystem of $ B $ implies that it is an elementary subsystem. It turns out that a model-complete theory having a model that can be isomorphically imbedded in every model of the theory is complete. Two systems of the same signature which satisfy the same prenex formulas without existential quantifiers are called universally equivalent. A model-complete elementary theory all models of which are universally equivalent is complete. Using the technique of model completeness one can prove that real-closed fields, in particular, the field of real numbers, have a complete and solvable elementary theory. Among the other solvable elementary theories are those of addition of natural numbers and integers, of Abelian groups, of $ p $- adic number fields, of finite fields, of residue class fields, of ordered Abelian groups, and of Boolean algebras.

The general study of unsolvable elementary theories was initiated by A. Tarski in the 1940s, but even earlier, in 1936, A. Church had proved the unsolvability of first-order predicate logic and J. Rosser, also in 1936, had proved the unsolvability of the arithmetic of the natural numbers. The elementary theory $ \mathop{\rm Th} ( K) $ of a class $ K $ of algebraic systems of the same signature $ \Omega $ is said to be inseparable if there is no recursive set of formulas containing $ \mathop{\rm Th} ( K) $ and not containing any closed formula which is false in all systems in $ K $. The elementary theory of a class $ K _ {1} $ of systems of signature $ \langle P ^ {(} 2) \rangle $ consisting of a single two-place predicate is called relatively definable in the elementary theory of a class $ K _ {2} $ of systems of signature $ \Omega _ {2} $ if there exist formulas $ \Phi ( v _ {0} ; u _ {1} \dots u _ {s} ) $ and $ \Psi ( v _ {1} , v _ {2} ; u _ {1} \dots u _ {s} ) $ of $ \Omega _ {2} $ such that for every system $ A _ {1} $ in $ K _ {1} $ one can find a system $ A _ {2} $ in $ K _ {2} $ and elements $ b _ {1} \dots b _ {s} $ in $ A _ {2} $ for which the set $ X = \{ {x \in A _ {2} } : {\Phi ( x ; b _ {1} \dots b _ {s} ) \textrm{ is true in } A _ {2} } \} $ together with the predicate $ P ^ {(} 2) $, defined on $ X $ so that $ P ^ {(} 2) ( x , y ) $ is true if and only if $ \Psi ( x , y ; b _ {1} \dots b _ {s} ) $ is true in $ A _ {2} $, forms an algebraic system isomorphic to $ A _ {1} $. This definition extends naturally to the theory of classes $ K _ {1} $ of arbitrary signature. If the elementary theory of a class $ K _ {1} $ is inseparable and relatively definable in the elementary theory of a class $ K _ {2} $, then that of $ K _ {2} $ is also inseparable. This makes it possible to prove that the elementary theories of many classes of algebraic systems are inseparable. Here it is convenient to take as $ \mathop{\rm Th} ( K _ {1} ) $ the elementary theory of all finite binary relations or that of all finite symmetric relations, or similar elementary theories. Inseparable elementary theories are unsolvable. So are those of the field of rational numbers and of many classes of rings and fields. The unsolvability of the elementary theory of finite groups is an important result of A.I. Mal'tsev.

References

[1]	Yu.L. Ershov, I.A. Lavrov, A.D. Taimanov, M.A. Taitslin, "Elementary theories" Uspekhi Mat. Nauk , 20 : 4 (1965) pp. 37–108 (In Russian)
[2]	Yu.L. Ershov, "Decision problems and constructivizable models" , Moscow (1980) (In Russian)

Comments

Somewhat more generally one defines recursive separability and inseparability for pairs of theories rather than for a single theory. Thus, two disjoint sets of natural numbers $ A $ and $ B $ are said to be recursively separable if there exists a recursive set $ A _ {1} $ containing $ A $ which is disjoint from $ B $. This is a symmetric notion. The sets $ A $ and $ B $ are (recursively) inseparable if they are not recursively separable. The single theory definition of inseparability results if this is applied to the sets $ R $ and $ T $ of refutable and provable formulas, or rather their associated sets of Gödel numbers $ R ^ { \star } $ and $ T ^ { \star } $.

References

[a1]	C.C. Chang, H.J. Keisler, "Model theory" , North-Holland (1973)
[a2]	R.M. Smullyan, "Theory of formal systems" , Princeton Univ. Press (1961) pp. Chapt. III