Elementary substructure

The term elementary substructure (or elementary substructure ) comes from model theory , an area of mathematical logic .

A structure is an elementary substructure of the structure if it is a substructure in the algebraic sense and the same statements apply to its elements in both structures. ${\displaystyle {\mathfrak {B}}}$ ${\displaystyle {\mathfrak {A}}}$

Then one also says, is elementary extension of and used as a mathematical symbol notation (or , people thought and written). ${\displaystyle {\mathfrak {A}}}$ ${\displaystyle {\mathfrak {B}}}$ ${\displaystyle {\mathfrak {B\prec A}}}$ ${\displaystyle {\mathfrak {A\succ B}}}$ ${\displaystyle {\mathfrak {B\preccurlyeq A}}}$ ${\displaystyle {\mathfrak {A\succcurlyeq B}}}$

Clarification

${\displaystyle {\mathfrak {A}}}$should be any structure and the language that contains the corresponding function, relation and constant symbols for the signature of and a structure with the same signature. ${\displaystyle {\mathcal {L}}_{\mathfrak {A}}}$ ${\displaystyle {\mathfrak {A}}}$ ${\displaystyle {\mathfrak {B}}}$

Then the statement " is an elementary substructure of " is defined by the following two conditions: ${\displaystyle {\mathfrak {B}}}$ ${\displaystyle {\mathfrak {A}}}$

• applies to the carrier quantities . ${\displaystyle B\subseteq A}$
• The following applies to every formula with free variables and every assignment of these variables to elements : ${\displaystyle \varphi \in {\mathcal {L}}_{\mathfrak {A}}}$ ${\displaystyle x_{1},\dots ,x_{n}}$ ${\displaystyle b_{1},\dots ,b_{n}\in B}$ ${\displaystyle {\mathfrak {A}}\models \varphi (b_{1},\dots ,b_{n})\Longleftrightarrow {\mathfrak {B}}\models \varphi (b_{1},\dots ,b_{n})}$

The second condition can also be expressed as follows:

• If the language is expanded by a set of constants , then the following applies to the expanded structures (if the constant is occupied by), i. H. the extended structures are elementarily equivalent . ${\displaystyle {\mathcal {L}}_{\mathfrak {A}}}$ ${\displaystyle \left\{{\dot {a}}|a\in A\right\}}$ ${\displaystyle {\mathfrak {A\equiv B}}}$ ${\displaystyle {\dot {a}}}$ ${\displaystyle a\,}$

Is a monomorphism , i. H. an injective strong homomorphism , whose image is an elementary substructure of , then one calls an elementary embedding . ${\displaystyle \Phi :{\mathfrak {B\hookrightarrow A}}}$ ${\displaystyle {\mathfrak {\widehat {B}}}}$ ${\displaystyle {\mathfrak {A}}}$ ${\displaystyle \Phi }$

The phrase “ there is an elementary extension of ${\displaystyle {\mathfrak {A}}}$ ” is also used when there is a structure and an elementary embedding . ${\displaystyle {\mathfrak {B}}}$ ${\displaystyle {\mathfrak {A\to B}}}$

A theory is called model-complete if the following applies to two models of : from follows . ${\displaystyle {\mathcal {T}}}$ ${\displaystyle {\mathcal {T}}}$ ${\displaystyle {\mathfrak {B\subseteq A}}}$ ${\displaystyle {\mathfrak {B\prec A}}}$

Statements about elementary substructures

• The following versions of the Löwenheim-Skolem theorem, which are also referred to as the Löwenheim-Skolem-Tarski theorems (with ZFC ), go back to Alfred Tarski :
  • ( "Down" ) If any (infinite) structure and the associated language, then there is for all cardinalities with an elementary substructure with ${\displaystyle {\mathfrak {A}}}$ ${\displaystyle {\mathcal {L}}_{A}}$ ${\displaystyle \kappa }$ ${\displaystyle \operatorname {card} ({{\mathcal {L}}_{A}})\leq \kappa \leq \operatorname {card} (A)}$ ${\displaystyle {\mathfrak {B\prec A}}}$ ${\displaystyle \operatorname {card} (B)=\kappa }$
  • ( “Upwards” ) There is an elementary expansion for everyone . ${\displaystyle \kappa \geq \max(\operatorname {card} ({{\mathcal {L}}_{A}},\operatorname {card} (B))}$ ${\displaystyle {\mathfrak {B\succ A}}}$

→ Main article : Löwenheim-Skolem theorem

• Is finite, then has no real elementary substructures. ${\displaystyle \operatorname {card} (A)}$ ${\displaystyle {\mathfrak {A}}}$

Tarski Vaught test

The Tarski-Vaught test, named after Alfred Tarski and Robert Vaught , specifies a criterion for checking the relationship in the first-order predicate logic . In order to demonstrate that one has to show that every formula that is valid for elements from is also valid in . A look at the inductive construction of the formulas shows that here the statements about existence are most likely to lead to failure, because what there is in to elements does not have to exist in a smaller amount , as the examples below show . The Tarski Vaught test says that that's all you have to pay attention to: ${\displaystyle {\mathfrak {B\prec A}}}$ ${\displaystyle {\mathfrak {B\prec A}}}$ ${\displaystyle {\mathfrak {A}}}$ ${\displaystyle B}$ ${\displaystyle {\mathfrak {B}}}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle B}$

Tarski-Vaught test : It applies if and only if , that is, is a substructure of , and it applies ${\displaystyle {\mathfrak {B\prec A}}}$ ${\displaystyle {\mathfrak {B}}\subset {\mathfrak {A}}}$ ${\displaystyle {\mathfrak {B}}}$ ${\displaystyle {\mathfrak {A}}}$

• The following applies to all natural numbers and all formulas with free variables in and all tuples : If , then there is a with . ${\displaystyle n}$ ${\displaystyle \varphi =\varphi (v_{0},\ldots ,v_{n})}$ ${\displaystyle v_{0},\ldots ,v_{n}}$ ${\displaystyle n}$ ${\displaystyle (b_{1},\ldots ,b_{n})\in B^{n}}$ ${\displaystyle {\mathfrak {A}}\models \exists x\varphi (x,b_{1},\ldots ,b_{n})}$ ${\displaystyle b\in B}$ ${\displaystyle {\mathfrak {A}}\models \varphi (b,b_{1},\ldots ,b_{n})}$

Examples

• If you look at and as pure order structures, then applies . For reasons of cardinality, elementary substructures do not have to be isomorphic to the original structure. ${\displaystyle \mathbb {Q} }$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {Q} \prec \mathbb {R} }$
• On the other hand, however , if you consider both as rings . . It can therefore depend on the signature in question whether it is valid or not. ${\displaystyle \mathbb {Q} \not \prec \mathbb {R} }$ ${\displaystyle \left[\mathbb {R} \models \ \exists x:x^{2}=2\right]}$ ${\displaystyle {\mathfrak {B\prec A}}}$
• Denotes the structure of the even numbers (as a pure order structure), then is . This shows that an isomorphic substructure does not have to be an elementary substructure. ${\displaystyle 2\mathbb {Z} }$ ${\displaystyle 2\mathbb {Z} \not \prec \mathbb {Z} }$ ${\displaystyle \left[\mathbb {Z} \models \ \exists x:\left(0<x\land x<2\right)\right]}$
• The theory of algebraically closed fields is model-complete, although it is not complete!
• In nonstandardanalysis , the structure of the hyperreal numbers is an elementary extension of . (Both the theory of real-closed bodies and the theory of real-closed ordered bodies are model-complete.) ${\displaystyle \mathbb {R} }$

Individual evidence

1. ↑ The term was introduced by A. Tarski and RL Vaught in their work: A. Tarski, RL Vaught: Arithmetical Extensions of Relational Systems; in: Compositio Math., vol 13 (1956/58), pages 81-102
2. ↑ Philipp Rothmaler: Introduction to Model Theory, Spektrum Akademischer Verlag 1995, ISBN 978-3-86025-461-5 , sentence 8.3.2

swell

• Lexicon of Mathematics, Spektrum Akademischer Verlag, 2003, (CD-Rom edition), Art. "Elementary expansion of an L-structure"

• Chang, Chen C., Keisler, H. Jerome, Model Theory , Amsterdam [et al.], North-Holland (1998); Cape. 3