Namespaces
Variants
Actions

Difference between revisions of "Elementary theory"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
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.
+
<!--
 +
e0353601.png
 +
$#A+1 = 101 n = 0
 +
$#C+1 = 101 : ~/encyclopedia/old_files/data/E035/E.0305360 Elementary theory
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
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.
+
{{TEX|auto}}
 +
{{TEX|done}}
  
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.
+
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|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|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====
 
====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>
 
<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====
 
====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" />.
+
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====
 
====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>
 
<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>

Latest revision as of 19:37, 5 June 2020


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
How to Cite This Entry:
Elementary theory. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Elementary_theory&oldid=13131
This article was adapted from an original article by Yu.L. ErshovM.A. Taitslin (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article