View source for Elementary theory

A collection of closed formulas of first-order predicate logic. The elementary theory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e0353601.png" /> of a class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e0353602.png" /> of algebraic systems (cf. [[Algebraic system|Algebraic system]]) of signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e0353603.png" /> is defined to be the collection of all closed formulas of the first-order predicate logic of signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e0353604.png" /> that are true in all systems of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e0353605.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e0353606.png" /> consists of a single system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e0353607.png" />, then the elementary theory of the class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e0353608.png" /> is the elementary theory of the system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e0353609.png" />. Two algebraic systems of the same signature are said to be elementarily equivalent if their elementary theories are the same. An algebraic system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536010.png" /> of signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536011.png" /> is called a model of an elementary theory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536012.png" /> of signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536013.png" /> if all formulas of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536014.png" /> are true in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536015.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536016.png" /> is denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536017.png" />. An elementary theory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536018.png" /> is called solvable (or decidable) if the set of formulas <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536019.png" /> (that is, the set of all logical consequences of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536020.png" />) is recursive. A class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536021.png" /> of algebraic systems of signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536022.png" /> is called axiomatizable if there exists an elementary theory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536023.png" /> of signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536024.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536025.png" />. In this case <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536026.png" /> is called a collection of axioms for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536027.png" />. A class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536028.png" /> is axiomatizable if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536029.png" />. 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536030.png" /> (cf. [[Categoricity in cardinality|Categoricity in cardinality]]) if all its models of cardinality <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536031.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536032.png" /> are equivalent in the theory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536033.png" /> if they contain the same variables and if, for any model <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536034.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536035.png" /> and any assignment of elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536036.png" /> to their free variables, the formulas are either both true or both false. A complete elementary theory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536037.png" /> of finite or countable signature is countably categorical if and only if for every <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536038.png" /> there are finitely many formulas with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536039.png" /> free variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536040.png" /> such that every formula of the appropriate signature with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536041.png" /> as free variables is equivalent in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536042.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536043.png" /> of signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536044.png" /> is called an elementary subsystem of a system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536045.png" /> of the same signature if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536046.png" /> is a subsystem of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536047.png" /> and if for every formula <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536048.png" /> of the first-order predicate logic of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536049.png" /> with free variables <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536050.png" /> and all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536051.png" />, the truth of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536052.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536053.png" /> implies its truth in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536054.png" />. An elementary theory <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536055.png" /> is called model complete if for any two models <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536056.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536057.png" /> of it the fact that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536058.png" /> is a subsystem of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536059.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536060.png" />-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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536061.png" /> of a class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536062.png" /> of algebraic systems of the same signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536063.png" /> is said to be inseparable if there is no recursive set of formulas containing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536064.png" /> and not containing any closed formula which is false in all systems in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536065.png" />. The elementary theory of a class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536066.png" /> of systems of signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536067.png" /> consisting of a single two-place predicate is called relatively definable in the elementary theory of a class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536068.png" /> of systems of signature <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536069.png" /> if there exist formulas <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536070.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536071.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536072.png" /> such that for every system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536073.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536074.png" /> one can find a system <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536075.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536076.png" /> and elements <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536077.png" /> in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536078.png" /> for which the set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536079.png" /> together with the predicate <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536080.png" />, defined on <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536081.png" /> so that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536082.png" /> is true if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536083.png" /> is true in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536084.png" />, forms an algebraic system isomorphic to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536085.png" />. This definition extends naturally to the theory of classes <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536086.png" /> of arbitrary signature. If the elementary theory of a class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536087.png" /> is inseparable and relatively definable in the elementary theory of a class <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536088.png" />, then that of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536089.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536090.png" /> 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====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  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)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  Yu.L. Ershov,   "Decision problems and constructivizable models" , Moscow  (1980)  (In Russian)</TD></TR></table>



====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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536091.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536092.png" /> are said to be recursively separable if there exists a recursive set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536093.png" /> containing <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536094.png" /> which is disjoint from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536095.png" />. This is a symmetric notion. The sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536096.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536097.png" /> are (recursively) inseparable if they are not recursively separable. The single theory definition of inseparability results if this is applied to the sets <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536098.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e03536099.png" /> of refutable and provable formulas, or rather their associated sets of Gödel numbers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e035360100.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035360/e035360101.png" />.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  C.C. Chang,   H.J. Keisler,   "Model theory" , North-Holland  (1973)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  R.M. Smullyan,   "Theory of formal systems" , Princeton Univ. Press  (1961)  pp. Chapt. III</TD></TR></table>